Average-case analysis of greedy packet scheduling (extended astract)

ABSTRACT

We study the average number of delays suffered by packets routed using greedy (work conserving) scheduling policies. We obtain tight bounds on the worst-case average number of delays in a few cases as follows. First, we show that the average number of delays is a function of the number of sources of packets, which is interesting in case a node may send many packets. Then, using a new concept we call delay race, we prove a tight bound on the average number of delays in a leveled graph. Finally, using delay races in a more involved way, we prove nearly-tight bounds on the average number of delays in directed acyclic graphs (DAGs). The upper bound for DAGs is expressed in terms of the underlying topology, and as a result it holds for any acyclic set of routes, even if they are not shortest paths. The lower bound for DAGs, on the other hand, holds even for shortest paths routes.

REFERENCES

• 1: Micah Adler , Sanjeev Khanna , Rajmohan Rajaraman , Adi Rosén, Time-constrained scheduling of weighted packets on trees and meshes, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.1-12, June 27-30, 1999, Saint Malo, France [doi>10.1145/305619.305620]
• 2: Micah Adler , Ramesh K. Sitaraman , Arnold L. Rosenberg , Walter Unger, Scheduling time-constrained communication in linear networks, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.269-278, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277651.277693]
• 3: William Aiello , Eyal Kushilevitz , Rafail Ostrovsky , Adi Rosén, Adaptive packet routing for bursty adversarial traffic, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.359-368, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276788]
• 4: 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
• 5: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 6: 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]
• 7: Frank P. Kelly. Reversibility and Stochastic Networks. Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons, Chichester, 1979.
• 8: S. Keshav, An engineering approach to computer networking: ATM networks, the Internet, and the telephone network, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 9: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 10: Tom Leighton, Bruce Maggs, and Satish Rao. Universal packet routing algorithms. In 29th Annual Symposium on Foundations of Computer Science, pages 256-269, White Plains, NY, October 1988.
• 11: T. Leighton , B. Maggs, Fast algorithms for finding O(congestion+dilation) packet routing schedules, Proceedings of the 28th Hawaii International Conference on System Sciences (HICSS'95), p.555, January 04-07, 1995
• 12: King-Shan Lui , Shmuel Zaks, Scheduling in Synchronous Networks and the Greedy Algorithm (Extended Abstract), Proceedings of the 11th International Workshop on Distributed Algorithms, p.66-80, September 24-26, 1997
• 13: 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 ]
• 14: L. G. Valiant, General purpose parallel architectures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Algorithms, Design, Management