RCBR: a simple and efficient service for multiple time-scale traffic

ABSTRACT

Compressed video traffic is expected to be a significant component of the traffic mix in integrated services networks. This traffic is hard to manage, since it has strict delay and loss requirements, but at the same time, exhibits burstiness at multiple time-scales. In this paper, we observe that slow time-scale variations can cause sustained peaks in the source rate, substantially degrading performance. We use large deviation theory to study this problem and to motivate the design of Renegotiated Constant Bit Rate Service (RCBR), that adds renegotiation and buffer monitoring to traditional CBR service. We argue the the load placed on signalling by RCBR can be handled by current technology. We present a) an algorithm to compute the optimal renegotiation schedule for stored (off-line) traffic, and b) a heuristic to approximate the optimal schedule for online traffic. Simulation experiments show that RCBR is able to extract almost all of the statistical multiplexing gain available by exploiting slow time-scale variations in traffic. In more general terms, we believe that a clean system design must match control time-scales to the time scales over which the workload varies. RCBR works well because it makes intelligent use of this time-scale separation.

REFERENCES

• 1: ITU-T Draft Standard Q.2963. Preliminary Draft, ITU- T, 1995.
• 2: D.D. Botvich and N.G. Duffield. Large Deviations, the Shape of the Loss Curve, and Economies of Scale in Large Multiplexers. Preprint.
• 3: Pierre E. Boyer , Didier P. Tranchier, A reservation principle with applications to the ATM traffic control, Computer Networks and ISDN Systems, v.24 n.4, p.321-334, May 15, 1992 [doi>10.1016/0169-7552(92)90116-8]
• 4: S. Chong, S.Q. Li, and J. Ghosh. Predictive Dynamic Bandwidth Allocation for Efficient Transport of Real- Time VBR Video over ATM. IEEE Journal on Selected Areas of Communications, 13:12-23, January 1995.
• 5: G. de Veciana and J. Walrand. Traffic Shaping for ATM Networks: Asymptotic Analysis and Simulations. submitted to iEEE/A CM Transactions on Networking, 1992.
• 6: A. Dembo and O. Zeitouni. Large Deviation Techniques and Applications. Jones and Bartlett Publishers, 1992.
• 7: B. Doshi and S. Dravida. Congestion Controls for Bursty Data Traffic in Wide Area High Speed Networks: In-Call Negotiations. Proc. {TC Specialist Seminar 7, Mormstown, N J, 1990.
• 8: Alexandros Eleftheriadis , Dimitris Anastassiou, Meeting Arbitrary QoS Constraints Using Dynamic Rate Shaping of Coded Digital Video, Proceedings of the 5th International Workshop on Network and Operating System Support for Digital Audio and Video, p.89-100, April 19-21, 1995
• 9: 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]
• 10: A.I. Elwalid, D. Heyman, T.V. Lakshman, D. Mitra, and A. Weiss. Fundamental Bounds and Approximations for ATM Multiplexers with Applications to Video Teleconferencing. to appear in }EEE JSA C, special issue on Advances in the Fundamentals of Networking, 1995.
• 11: Mark William Garrett, Contributions toward real-time services on packet switched networks, Columbia University, New York, NY, 1993
• 12: Mark W. Garrett , Walter Willinger, Analysis, modeling and generation of self-similar VBR video traffic, Proceedings of the conference on Communications architectures, protocols and applications, p.269-280, August 31-September 02, 1994, London, United Kingdom
• 13: R. J. Gibbens , P. J. Hunt, Effective bandwidths for the multi-type UAS channel, Queueing Systems: Theory and Applications, v.9 n.1-2, p.17-28, Oct. 1991 [doi>10.1007/BF01158790]
• 14: G.C. Goodwin and K.S. Sin. Adaptive Filtering Prediction and Uontrol. Prentice Hall, 1984.
• 15: I. Hsu and J. Walrand. Quick Detection of Changes in Traffic Statistics: Application to Variable Rate Compression. In Proceedings of the 3~nd Allerton Conference or, Communications, Control and Computing, Monticello, IL, 1993.
• 16: J.Y. Hut. Resource Allocation for Broadband Networks. IEEE Journal on Selected Areas in Communications, 6(9), December 1988.
• 17: Hemant Kanakia , Partho P. Mishra , Amy Reibman, An adaptive congestion control scheme for real-time packet video transport, Conference proceedings on Communications architectures, protocols and applications, p.20-31, September 13-17, 1993, San Francisco, California, United States
• 18: George Kesidis , Jean Walrand , Cheng-Shang Chang, Effective bandwidths for multiclass Markov fluids and other ATM sources, IEEE/ACM Transactions on Networking (TON), v.1 n.4, p.424-428, Aug. 1993 [doi>10.1109/90.251894]
• 19: M. Nomura, T. Fujii, and N. Ohta. Basic Characteristics of Variable Rate Video Coding in ATM Environment. IEEE Journal or, Selected Areas of Communications, 7(5), June 1989.
• 20: E. P. Rathgeb. Modeling and Performance Comparison of Policing Mechanisms for ATM Network. IEEE Journal on Selected Areas In Communzcations, 9(3):325- 334, April 1991.
• 21: E. P. Rathgeb. Policing of Realistic VBR Video Traffic in an ATM Network. International Journal of Digital and Analog Uommun~cations Systems, 6:213-226, 1993.
• 22: R. J. Safranek , C. R. ,. Jr. Kalmanek , R. Garg, Methods for matching compressed video to ATM networks, Proceedings of the 1995 International Conference on Image Processing (Vol. 1)-Volume 1, p.13, October 23-26, 1995
• 23: P. Sen, B. Maglaris, N. Ritdi, and D. Anastassiou. Models for Packet Switching of Variable-Bit-Rate Video Sources. IEEE Journal on Selected Areas of Communications, 7(5), June 1989.
• 24: D. Tse, R. Gallager, and J. Tsitsiklis. Statistical Multiplexing of Multiple Time-Scale Markov Streams. to appear in IEEE JSA U, special issue on Advances in the Fundamentals of Networking, 1995.
• 25: J.S. Turner. Managing Bandwidth in ATM Networks with Bursty Traffic. IEEE Network Magazine, September 1992.
• 26: Andrew J. Viterbi , James K. Omura, Principles of Digital Communication and Coding, McGraw-Hill, Inc., New York, NY, 1979
• 27: A. Weiss. A New Technique for Analyzing Large Traffic Systems. Advances in Applied Probability, 18:506-532, 1986.
• 28: Lars C. Wolf , Luca Delgrossi , Ralf Steinmetz , Sybille Schaller , Hartmut Wittig, Issues ofReserving Resources in Advance, Proceedings of the 5th International Workshop on Network and Operating System Support for Digital Audio and Video, p.28-38, April 19-21, 1995
• 29: Hui Zhang , Edward W. Knightly, RED-VBR: A New Approach to Support Delay-Sensitive VBR Video in Packet-Switched Networks, Proceedings of the 5th International Workshop on Network and Operating System Support for Digital Audio and Video, p.258-272, April 19-21, 1995

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.1 Multimedia Information Systems
          Subjects: Video (e.g., tape, disk, DVI)

General Terms:
Algorithms, Design, Experimentation, Performance