The impact of storage capacity on end-to-end delay in time varying networks

Abstract

Recent technological advances have rendered storage a cheap and at large scale available resource. Yet, there exist only few examples in networking that consider storage for enhancing data transfer capabilities. In this paper we study networks with time varying link capacitiy and analyze the impact of node storage on their capability to convey data from source to destination. We show that storage capacity is quite beneficial in terms of the amount of data that can be pushed from the source to the destination within a given time horizon. Equivalently, storage can be used to reduce incurred delay for the delivery of a certain amount of data. For linear networks, we show that this performance improvement depends on the relative patterns of link capacity variations. We extend our study to general networks and we use a novel method that iteratively updates the minimum cut of the time expanded graph, in a constructive manner, in the sense that during the process, the storage capacity allocation in the network is shown. Next, we incorporate routing in our methodology and derive a joint storage capacity management and routing policy to maximize the amount of data transferred to the destination. This policy stems from the solution of the maximum flow problem defined for the dynamic network over a certain time period, by using the ε-relaxation solution method. The later is amenable to distributed implementation, which is a very desirable property for the large scale modern networks which operate without central control. © 2011 IEEE.