Leave-in-Time: a new service discipline for real-time communications in a packet-switching network

ABSTRACT

Leave-in-Time is a new rate-based service discipline for packet-switching nodes in a connection-oriented data network. Leave-in-Time provides sessions with upper bounds on end-to-end delay, delay jitter, buffer space requirements, and an upper bound on the probability distribution of end-to-end delays. A Leave-in-Time session's guarantees are completely determined by the dynamic traffic behavior of that session, without influence from other sessions. This results in the desirable property that these guarantees are expressed as functions derivable simply from a single fixed-rate server (with rate equal to the session's reserved rate) serving only that session. Leave-in-Time has a non-work-conserving mode of operation for sessions desiring low end-to-end delay jitter. Finally, Leave-in-Time supports the notion of delay shifting, whereby the delay bounds of some sessions may be decreased at the expense of increasing those of other sessions. We present a set of admission control algorithms which support the ability to do delay shifting in a systematic way.

REFERENCES

• 1: David D. Clark , Scott Shenker , Lixia Zhang, Supporting real-time applications in an Integrated Services Packet Network: architecture and mechanism, Conference proceedings on Communications architectures & protocols, p.14-26, August 17-20, 1992, Baltimore, Maryland, United States
• 2: R.L. Cruz, "A Calculus for Network Delay, Part I: Network Elements in Isolation," In IEEE Transactions on Information Theory, Vol. 37, No. 1, pp. 114-131, January 1991.
• 3: R.L. Cruz, "A Calculus for Network Delay, Part II: Network Analysis," In IEEE Transactions on Information Theory, Vol. 37, No. 1, pp. 132-141, January 1991.
• 4: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, Symposium proceedings on Communications architectures & protocols, p.1-12, September 25-27, 1989, Austin, Texas, United States
• 5: D. Ferrari and D. Verma, "A Scheme for Real-Time Channel Establishment in Wide-Area Networks," In IEEE JSAC, Vol. 8, No. 4, pp. 368-379, April 1990.
• 6: Ribeiro Norival Figueira, A new approach to the control of real-time traffic in packet switching data networks, University of California at San Diego, La Jolla, CA, 1996
• 7: Norival R. Figueira , Joseph Pasquale, An upper bound on delay for the VirtualClock service discipline, IEEE/ACM Transactions on Networking (TON), v.3 n.4, p.399-408, Aug. 1995 [doi>10.1109/90.413214]
• 8: N.R. Figueira and Joseph Pasquale, "Leave-in-Time: A Service Discipline for Real-Time Communications in a Packet Switching Network," Technical Report CSE95-426, University of California, San Diego, May 1995.
• 9: S. J. Golestani, A stop-and-go queueing framework for congestion management, Proceedings of the ACM symposium on Communications architectures & protocols, p.8-18, September 26-28, 1990, Philadelphia, Pennsylvania, United States
• 10: S. J. Golestani, "Congestion-Free Transmission of Real-Time Traffic in Packet Networks," In Proceedings of IEEE INFO- COM '90, pp. 527-536, June 1990.
• 11: S. J. Golestani, "Duration-Limited Statistical Multiplexing of Delay-Sensitive Traffic in Packet Networks," in Proceedings oflEEE INFOCOM '91, pp. 323-332, April 1991.
• 12: S. J. Golestani, "A Self-Clocked Fair Queueing Scheme for Broadband Applications," In Proceedings of IEEE INFO- COM '94, pp. 636-646, June 1994.
• 13: C. Kalmanek, H. Kanakia, and S. Keshav, "Rate Controlled Servers for Very High-Speed Networks," In Proceedings of IEEE GlobeCom '90, pp. 300.3.1-300.3.9, December 1990.
• 14: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 15: Jim Kurose, On computing per-session performance bounds in high-speed multi-hop computer networks, Proceedings of the 1992 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.128-139, June 01-05, 1992, Newport, Rhode Island, United States
• 16: A. M. Lee, Applied Queueing Theory. London: Macmillan, New York: St. Martin's Press, 1966.
• 17: A. K. Parekh, "A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks," Ph.D. Dissertation, Massachusetts Institute of Technology, LiDS-TH- 2089, February 1992.
• 18: Abhay K. Parekh , Robert G. Gallager, A generalized processor sharing approach to flow control in integrated services networks—the single node case, Proceedings of the eleventh annual joint conference of the IEEE computer and communications societies on One world through communications (Vol. 2), p.915-924, May 1992, Florence, Italy
• 19: A. K. Parekh, and G. Gallager, "A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks -- The Multiple Node Case," In Proceedings of IEEE INFOCOM '93, Vol. 2, pp. 521-530, March 1993.
• 20: 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]
• 21: J. R. Shelton, "Solution Methods for Waiting Line Problems," Journal of Industrial Engineering, pp. 293-303, July-August 1960.
• 22: D. Verma, H. Zhang, and D. Ferrari, "Delay Jitter Control for Real-Time Communication in a Packet Switching Network," In Proceedings of lEEE TriCom '91, pp. 35-43, April 1991.
• 23: R. W. Wolff, Stochastic Modelling and the Theory of Queues. Englewood Cliffs, NJ: Prentice Hall, 1989.
• 24: O. Yaron and M. Sidi, "Calculating Performance Bounds in Communication Networks," In Proceedings of IEEE INFO- COM '93, Vol. 2, pp. 539-545, March 1993.
• 25: David Yates , James Kurose , Don Towsley , Michael G. Hluchyj, On per-session end-to-end delay distributions and the call admission problem for real-time applications with QOS requirements, Conference proceedings on Communications architectures, protocols and applications, p.2-12, September 13-17, 1993, San Francisco, California, United States
• 26: H. Zhang and D. Ferrari, "Rate-Controlled Static-Priority Queueing," In Proceedings of IEEE INFOCOM '93, pp. 227- 236, March 1993.
• 27: H. Zhang and D. Ferrari, "Improving Utilization for Deterministic Service in Multimedia Communication," In Proceedings of the International Conference on Multimedia Computing and Systems, pp. 295-304, May 1994.
• 28: Hui Zhang , Srinivasan Keshav, Comparison of rate-based service disciplines, Proceedings of the conference on Communications architecture & protocols, p.113-121, September 03-06, 1991, Zurich, Switzerland
• 29: L. Zhang, Virtual clock: a new traffic control algorithm for packet switching networks, ACM SIGCOMM Computer Communication Review, v.20 n.4, p.19-29, Sep. 1990

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.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Algorithms, Design, Performance