On per-session end-to-end delay distributions and the call admission problem for real-time applications with QOS requirements

ABSTRACT

A crucial problem facing the designers and deployers of future high-speed networks is providing applications with quality of service (QOS) guarantees. For soft real-time applications, which are delay sensitive but loss tolerant, delay distribution is an important QOS measure of interest. In this paper we study (through simulation) the end-to-end delay distribution seen by individual sessions under simple first-come first-served (FCFS) multiplexing in a network model with two significant features: (1) all traffic is connection-oriented, (2) cross traffic along routes is representative of that seen by calls in a moderately sized wide area network (i.e., less than 100 switches). We compare these delay distributions with the worst case point-valued analytic delay bounds predicted by three different techniques for providing such bounds (two of which require a more sophisticated link-level scheduling policy). We also consider the per-hop delay distributions seen as a session progresses "deeper" into the network and determine the sensitivity of these delay distributions to the manner in which the interfering traffic is modeled. Finally, we use our delay distribution results to examine the tradeoff between the QOS requested by a call, the manner in which the QOS guarantee is provided, and the number of calls that are admitted at the requested QOS.

REFERENCES

• 1: BRADY, P. T. A statistical analysis of on-off patterns in 16 conversations. Bell System Technical Journal ~t 7, 1 (Jan. 1968), 73-91.
• 2: CHANG, C.-S. Stability, queue length, and delay, part I: Deterministic queueing networks. Research Report RC 17708, IBM T. J. Watson Research Center, Yorktown Heights, NY, Feb. 1992.
• 3: CHANG, C.-S. Stability, queue length, and delay, part II: Stochastic queueing networks. Research Report RC 17709, IBM T. J. Watson Research Center, Yorktown Heights, IVY, Feb. 1992.
• 4: 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
• 5: CRUZ, R. L. A calculus for network delay, part I: Network elements in isolation. IEEE Teansaetions on Information Theory 37, 1 (Jan. 1991), 114-131.
• 6: CRuz, R. L. A calculus for network delay, part Ih Network analysis. IEEE Transactions on Information Theory 37, 1 (Jan. 1991), 132-141.
• 7: Dt~MERS, A., KBSHAV, S., AND SHENKER, S. Analysis and simulation of a fair queueing algorithm. Internetworking: Research and Ezperience 1, 1 (Jan. 1990), 3-26.
• 8: Anwar I. Elwalid , Debasis Mitra, Effective bandwidth of general Markovian traffic sources and admission control of high speed networks, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.329-343, June 1993 [doi>10.1109/90.234855]
• 9: F~.RaAtU, D., AND VErandA, D. C. A scheme for real-tlme channel establishment in wide-area networks. iEEE Journal on Selected Areas in Communications 8, 3 (Apr. 1990), 368-379.
• 10: GOLBSTANI, S. J. Congestion-free communication in high-speed packet networks. IEEE Transactions on Communications 39, 12 (Dec. 1991), 1802-1812.
• 11: GOLESTANI, S. J. A framing strategy for congestion management. IEEE Journal on Selected Areas in Communications 9, 7 (Sept. 1991), 1064-1077.
• 12: Albert G. Greenberg , Neal Madras, Comparison of a Fair Queueing Discipline to Processor Sharing, Proceedings of the 14th IFIP WG 7.3 International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.193-207, September 12-14, 1990
• 13: GmilUN, R., AHMADI, H., AND NAGHSHINEH, M. Equivalent capacity and its application to bandwidth allocation in high-speed networks. IEEE Journal on Selected Areas in Communications 9, 7 (Sept. 1991), 968-981.
• 14: HEFFES, H., AND LUCANTONI, D. M. A Markov modulated characterization of packetized voice and data traffic and related statistical multiplexer performance. IEEE Journal on Selected Areas in Communications SAC-g, 6 (Sept. 1986), 856-868.
• 15: Sugih Jamin , Scott Shenker , Lixia Zhang , David D. Clark, An Admission Control Algorithm for Predictive Real-Time Service (Extended Abstract), Proceedings of the Third International Workshop on Network and Operating System Support for Digital Audio and Video, p.349-356, November 12-13, 1992
• 16: KAMITAKE, T., ANO StmA, T. Evaluation of an admission control scheme for an ATM network considering fluctuations in cell loss rate. In Proceeding8 of the Conference on Global Communications (GLOBECOM) (Dallas, Texas, Nov. 1989), IEEE, pp. 1774--1780.
• 17: 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
• 18: Jim Kurose, Open issues and challenges in providing quality of service guarantees in high-speed networks, ACM SIGCOMM Computer Communication Review, v.23 n.1, p.6-15, Jan. 1993 [doi>10.1145/173942.173943]
• 19: MITRA, D. Optimal design of windows for high speed data networks. In P~oceedings of the Con/erence on Computer Communications (IEEE Infocom) (San Francisco, CA, June 1990), IEEE, pp. 1156-1163.
• 20: MURATA, M., OIE, Y., SUDA, T., AND MIYAHAltA, H. Analysis of a discrete-time single-server queue with bursty inputs for traffic control in ATM networks. IEEE Journal on Selected Areas in Communications 8, 3 (Apr. 1990), 447-458.
• 21: OHBA, Y., MUaATA, M., AND MIYAHARA, }I. Analysis of interdeparture processes for bursty traffic in ATM networks. IEEE Journal on Selected Areas in Communications 9, 3 (Apr. 1991), 468-476.
• 22: 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
• 23: PAI~KH, A. K., AND GALLAGER, R. G. A generalized processor sharing approach to flow control in integrated services networks- the multiple node case. In Proceedings of the Conference on Computer Communications {IEEE In. focom) (San Francisco, CA, Mar. 1993), voI. 2, 1EEE, pp. 521-530 (SA.1).
• 24: PARBKH, A. K. J. A generalized processor sharing approach to fiotv control in integ~ted services nettvorlcz. PhD thcaiz, Massachusetts Institute of Technology, Cambridge, MA, Feb. 1992.
• 25: RASMUSSEN, C., AND SORBNSEN, J. A simple call acceptance procedure in an ATM network. Computer Net. tvorkz and ISDN Systems ttO, 1-5 (Dec. 1990), 197-202. ITC Specialist Seminar, 25-29 September 1989, Adelaide, Australia.
• 26: SAITO, H., AND SHiOMOTO, K. Dynamic call admission control in ATM networks. IEEE Journal on Selected Areas in Communications 9, 7 (Sept. 1991), 982-989.
• 27: SRIRAM, K., AND WHITT, W. Characterizing superposition arrival processes in packet multiplexers for voice and data. IEEE Journal on Selected Areas in Communications $AC-4, 6 (Sept. 1986), 833-846.
• 28: VE~, D. C., ZHANG, H., AND FBntt~I, D. Delay jitter control for real-time communication in a packet switching network. In Proceedings of Tricomm '9i (Chapel Hill, NC, Apr. 1991), IEEE.
• 29: WOODRm~F, G. M., A~'O KOSITPAmOON, R. Multimedis traffic management principles for guaranteed ATM network performance, iEEE Journal on Selected A~eas in Communications 8, 3 (Apr. 1990), 437-446.
• 30: YAP. ON, O., ANO SIp{, M. Calculating performance bounds in communication networks. In Proceedings o/ the Conference on Computer Communications (IEEE Infocom) (San Francisco, CA, Mar. 1993), vol. 2, IEEE, pp. sag-s46 (SA.a).
• 31: Lixia Zhang, VirtualClock: a new traffic control algorithm for packet-switched networks, ACM Transactions on Computer Systems (TOCS), v.9 n.2, p.101-124, May 1991 [doi>10.1145/103720.103721]

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: Network topology
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes; Modeling techniques

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Design, Measurement, Performance