Dynamic routing on networks with fixed-size buffers

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.

REFERENCES

• 1: W. Aiello, Y. Mansour, S. Rajagopolan, A. Rosén, "Competitive Queue Policies for Differentiated Services," Proc. of 19th INFOCOM, pp. 431--440, 2000.
• 2: A. Fernandez, Universal stability results for greedy contention-resolution protocols, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.380, October 14-16, 1996
• 3: B. Awerbuch, Y. Azar, and S. Plotkin, "Throughput Competitive On-Line Routing," 34th FOCS, pp. 32--40, 1993.
• 4: B. Awerbuch, A. Brinkman, C. Scheideler, "Any-casting and Multicasting in Adversarial Systems: Routing and Admission Control," manuscript, http://www.cs.jhu.edu/~scheideler.
• 5: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 6: A. Z. Broder , A. M. Frieze, A general approach to dynamic packet routing with bounded buffers, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.390, October 14-16, 1996
• 7: Allan Borodin , Jon Kleinberg , Prabhakar Raghavan , Madhu Sudan , David P. Williamson, Adversarial queueing theory, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.376-385, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237984]
• 8: Andrei Broder , Eli Upfal, Dynamic deflection routing on arrays (preliminary version), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.348-355, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237981]
• 9: David Gamarnik, Stability of adaptive and non-adaptive packet routing policies in adversarial queueing networks, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.206-214, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301306]
• 10: Ellen L. Hahne , Alexander Kesselman , Yishay Mansour, Competitve buffer management for shared-memory switches, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.53-58, July 2001, Crete Island, Greece [doi>10.1145/378580.378589]
• 11: Mor Harchol-Balter , Paul E. Black, Queueing analysis of oblivious packet-routing networks, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.583-592, January 23-25, 1994, Arlington, Virginia, United States
• 12: Mor Harchol-Balter , David Wolfe, Bounding delays in packet-routing networks, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.248-257, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225133]
• 13: Anil Kamath , Omri Palmon , Serge Plotkin, Routing and admission control in general topology networks with Poisson arrivals, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.269-278, January 28-30, 1996, Atlanta, Georgia, United States
• 14: Alexander Kesselman , Zvi Lotker , Yishay Mansour , Boaz Patt-Shamir , Baruch Schieber , Maxim Sviridenko, Buffer overflow management in QoS switches, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.520-529, July 2001, Hersonissos, Greece [doi>10.1145/380752.380847]
• 15: J. Kzeinberg , E. Tardos, Disjoint paths in densely embedded graphs, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.52, October 23-25, 1995
• 16: Tom Leighton, Methods for message routing in parallel machines, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.77-96, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129721]
• 17: T. Leighton, B. Maggs, S. Rao, "Packet Routing and Job-Shop Scheduling in O(congestion+dilation) Steps," Combinatorica, Vol. 14, No. 2, pp. 167--180, 1994.
• 18: T. Leighton, B. Maggs and A. Richa, "Fast Algorithms for Finding O(Congestion+Dilation) Packet Routing Schedules," Combinatorica, to appear.
• 19: Yishay Mansour , Boaz Patt-Shamir, Greedy packet scheduling on shortest paths, Journal of Algorithms, v.14 n.3, p.449-465, May 1993 [doi>10.1006/jagm.1993.1024]
• 20: Yishay Mansour , Boaz Patt-Shamir , Ofer Lapid, Optimal smoothing schedules for real-time streams (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.21-29, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343511]
• 21: M. Mihail, "Conductance and Convergence of Markov Chains---A Combinatorial Treatment of Expanders," Proc. of 30th FOCS, pp. 526--531, 1989.
• 22: Michael Mitzenmacher, Bounds on the greedy routing algorithm for array networks, Journal of Computer and System Sciences, v.53 n.3, p.317-327, Dec. 1996 [doi>10.1006/jcss.1996.0072]
• 23: Rafail Ostrovsky , Yuval Rabani, Universal O(congestion + dilation + log1+&egr;N) local control packet switching algorithms, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.644-653, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258659]
• 24: C. Partridge, The end of simple traffic models. IEEE Network, Vol. 7 No. 5, Editor note. 1993.
• 25: Abhay K. Parekh , Robert G. Gallager, A generalized processor sharing approach to flow control in integrated services networks: the single-node case, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.344-357, June 1993 [doi>10.1109/90.234856]
• 26: Abhay K. Parekh , Robert G. Gallagher, A generalized processor sharing approach to flow control in integrated services networks: the multiple node case, IEEE/ACM Transactions on Networking (TON), v.2 n.2, p.137-150, April 1994 [doi>10.1109/90.298432]
• 27: Yuval Rabani , Éva Tardos, Distributed packet switching in arbitrary networks, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.366-375, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237983]
• 28: Aravind Srinivasan , Chung-Piaw Teo, A constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.636-643, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258658]
• 29: G. Stamoulis and J. Tsitsiklis, "The Efficiency of Greedy Routing in Hypercubes and Butterflies," IEEE Transactions on Communications, 42 (11), pp. 3051--208, 1994.
• 30: Christian Scheideler , Berthold Vöcking, Universal continuous routing strategies, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.142-151, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237519]
• 31: A. Veres, and M. Boda, The chaotic nature of TCP congestion control. In Proc. of INFOCOM 2000, 2000.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Theory