On delivery times in packet networks under adversarial traffic

ABSTRACT

We consider packet networks and make use of the "adversarial queuing theory" model [10]. We are interested in the question of guaranteeing that all packets are actually delivered to destination, and of having an upper bound on the delivery times of all packets. Whether this is possible against all rate-1 adversaries was previously posed as an open question [15, 10].Among other, we give a queuing policy that guarantees bounded delivery time whenever the rate-1 adversary itself can deliver all packets in bounded time and adheres to certain additional conditions. On the negative side we show that even the adversary itself cannot deliver all packets in bounded time for all rate-1 sequences of packets. We thus answer the open question posed by Gamarnik [15]. We further show that delivering all packets while maintaining stability (we coin the term "reliability" for this property) can be done by an offline scheduler whenever the injection of packets is done at rate of at most 1. Thus any rate-1 adversary can have this property. But, on the other hand, we also show that there is no online protocol (even centralized) that can achieve that property against all rate-1 adversaries. We thus answer an open question of Borodin et al. [10].

REFERENCES

• 1: Micah Adler , Adi Rosén, Tight Bounds for the Performance of Longest-in-System on DAGs, Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, p.88-99, March 14-16, 2002
• 2: William Aiello , Eyal Kushilevitz , Rafail Ostrovsky , Adi Rosén, Adaptive packet routing for bursty adversarial traffic, Journal of Computer and System Sciences, v.60 n.3, p.482-509, June 2000 [doi>10.1006/jcss.1999.1681 ]
• 3: Carme Àlvarez , Maria Blesa , Maria Serna, Universal stability of undirected graphs in the adversarial queueing model, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564903]
• 4: Matthew Andrews, Instability of FIFO in session-oriented networks, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.440-447, January 09-11, 2000, San Francisco, California, United States
• 5: Matthew Andrews , Baruch Awerbuch , Antonio Fernández , Tom Leighton , Zhiyong Liu , Jon Kleinberg, Universal-stability results and performance bounds for greedy contention-resolution protocols, Journal of the ACM (JACM), v.48 n.1, p.39-69, Jan. 2001 [doi>10.1145/363647.363677]
• 6: M. Andrew , A. Goel , A. Fernández, Source Routing and Scheduling in Packet Networks, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.168, October 14-17, 2001
• 7: Matthew Andrews , Lisa Zhang, The effects of temporary sessions on network performance, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.448-457, January 09-11, 2000, San Francisco, California, United States
• 8: P. Berenbrink , A. Brinkmann , C. Scheideler, Simple Routing Strategies for Adversarial Systems, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.158, October 14-17, 2001
• 9: Rajat Bhattacharjee , Ashish Goel, Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.160, October 11-14, 2003
• 10: Allan Borodin , Jon Kleinberg , Prabhakar Raghavan , Madhu Sudan , David P. Williamson, Adversarial queuing theory, Journal of the ACM (JACM), v.48 n.1, p.13-38, Jan. 2001 [doi>10.1145/363647.363659]
• 11: Allan Borodin , Rafail Ostrovsky , Yuval Rabani, Stability preserving transformations: packet routing networks with edge capacities and speeds, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.601-610, January 07-09, 2001, Washington, D.C., United States
• 12: R. Cruz, A Calculus for Network Delay, Part I: Network Elements in Isolation, IEEE Transactions on Information Theory, pp. 114--131, 1991.
• 13: R. Cruz, A Calculus for Network Delay, Part II: Network Analysis, IEEE Transactions on Information Theory, pp. 132--141, 1991.
• 14: Josep Díaz , Dimitrios Koukopoulos , Sotiris Nikoletseas , Maria Serna , Paul Spirakis , Dimitrios M. Thilikos, Stability and non-stability of the FIFO protocol, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.48-52, July 2001, Crete Island, Greece [doi>10.1145/378580.378588]
• 15: 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]
• 16: D. Gamarnik, Using Fluid Models to Prove Stability of Adversarial Queueing Networks. In IEEE Transactions on Automatic Control, Vol. 45, No. 4, pp. 741--747, 2000.
• 17: A. Goel. Stability of Networks and Protocols in the Adversarial Queueing Model for Packet Routing. Networks, 37(4):219--224, 2001.
• 18: D. Koukopoulos, S. E. Nikoletseas, P. G. Spirakis, The Range of Stability for Heterogeneous and FIFO Queueing Networks. Electronic Colloquium on Computational Complexity (ECCC TR01-099), 2001.
• 19: Zvi Lotker , Boaz Patt-Shamir , Adi Rosén, New Stability Results for Adversarial Queuing, SIAM Journal on Computing, v.33 n.2, p.286-303, 2004 [doi>10.1137/S0097539702413306]
• 20: Adi Rosén, A note on models for non-probabilistic analysis of packet switching networks, Information Processing Letters, v.84 n.5, p.237-240, 16 December 2002

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Store and forward networks

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

Keywords:
adversarial queuing theory, delivery time, packet networks, protocols, stability