Dynamic Routing on Networks with Fixed-Sized Buffers
William Aiello, Rafail Ostrovsky, Eyal Kushilevitz, Adi Rosen
Abstract:
The combination of the buffer size of routers deployed in the Internet and the Internet traffic itself leads routinely to routers dropping packets. Motivated by this, we initiate the rigorous study of dynamic store-and-forward routing on arbitrary networks in a model in which dropped packets must explicitly be taken into account. To avoid the uncertainties of traffic modeling, we consider arbitrary traffic on the network. We analyze and compare the effectiveness of several greedy, on-line, local-control protocols using a competitive analysis of the throughput . One goal of our approach is for the competitive results to continue to hold as a network grows without requiring the memory in the nodes to increase with the size of the network. Thus, in our model, we have link buffers of fixed size, $B$, which is independent of the size of the network, and $B$ becomes a parameter of the model.
Our results are in contrast to another adversarial traffic model known as Adversarial Queuing Theory (AQT), which studies the stability and growth rate of queues as a function of the network and traffic parameters. For example, in AQT the Furthest-To-Go (FTG) protocol is stable for all networks whereas Nearest-To-Go (NTG) can be unstable for some networks. Unlike AQT, in our setting NTG is preferable to FTG: we show that the NTG protocol is throughput-competitive on all networks whereas the FTG protocol has unbounded competitiveness whenever a network contains even small cycles.
comment: Appeared in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA-2003)
Fetch PostScript file of the paper Fetch PDF file of the paper