Modeling and simulation of self-similar variable bit rate compressed video: a unified approach

ABSTRACT

Variable bit rate (VBR) compressed video is expected to become one of the major loading factors in high-speed packet networks such as ATM-based B-ISDN. However, recent measurements based on long empirical traces (complete movies) revealed that VBR video traffic possesses self-similar (or fractal) characteristics, meaning that the dependence in the traffic stream lasts much longer than traditional models can capture.In this paper, we present a unified approach which, in addition to accurately modeling the marginal distribution of empirical video records, also models directly both the short and the long-term empirical autocorrelation structures. We also present simulation results using synthetic data and compare with results based on empirical video traces.Furthermore, we extend the application of efficient estimation techniques based on importance sampling that we had used before only for simple fractal processes. We use importance sampling techniques to efficiently estimate low probabilities of packet losses that occur when a multiplexer is fed with synthetic traffic from our self-similar VBR video model.

REFERENCES

• 1: R. Addie, M. Zukerman, and T. Neame. Performance of a Single Server Queue with Self Similar Input. In Proc. IEEE ICe '95, Seattle, June 1995.
• 2: J. Beran, R. Sherman, M. S. Taqqu, and W. Willinger. Long-Range Dependence in Variable-Bit-Rate Video Traffic. To appear on IEEE Transactions on Communications, 1994.
• 3: J. A. Bucklew. Large deviation Techniques in Decision, Simulation, and Estimation. John Wiley and Sons, 1990.
• 4: J. W. Cohen. The Single Server Queue. North-Holland, 1982.
• 5: Michael Devetsikiotis , J. Keith Townsend, Statistical optimization of dynamic importance sampling parameters for efficient simulation of communication networks, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.293-305, June 1993 [doi>10.1109/90.234852]
• 6: N. G. Duffield and N. O'Connell. Large Deviations and Overflow Probabilities for the General Single-Server Queue, with Applications. Technical Report DIAS- STP-93-30, Dublin Institute for Advanced Studies, 1993.
• 7: 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
• 8: P W. Glynn , D. L. Iglehart, Importance sampling for stochastic simulations, Management Science, v.35 n.11, p.1367-1392, Nov. 1989 [doi>10.1287/mnsc.35.11.1367]
• 9: Philip Heidelberger, Fast Simulation of Rare Events in Queueing and Reliability Models, Performance Evaluation of Computer and Communication Systems, Joint Tutorial Papers of Performance '93 and Sigmetrics '93, p.165-202, May 10-14, 1993
• 10: D. Heyman, T. V. Lakshman, A. Tabatabai, and H. Heeke. Modeling Teleconference Traffic from VBR Video Coders. In Proc. IEEE ICC '9~, New Orleans, 1994.
• 11: J. R. M. Hosking. Fractional Differencing. Biometrika, 68(1):165-176, 1981.
• 12: J. R. M. Hosking. Modeling Persistence in Hydrological Time Series Using Fractional Differencing. Water Resources Research, 20(12):1898-1908, 1984.
• 13: C. Huang, M. Devetsikiotis, I. Lambadaris, and A. R. Kaye. Fast Simulation for Self-Similar Traffic in ATM Networks. In Proc. IEEE ICC '95, Seattle, June 1995.
• 14: H. E. Hurst. Long-Term Storage Capacity of Reservoirs. Trans. of the Am. Soc. of Civil Eng., 116:770-799, 1951.
• 15: M. R. Ismail , I. E. Lambadaris , M. Devetsikiotis , A. R. Kaye, Modelling prioritized MPEG video using TES and a frame spreading strategy for transmission in ATM networks, Proceedings of the Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies (Vol. 2)-Volume, p.762, April 02-06, 1995
• 16: ISO. MPEG~I Specification. CD 11172.
• 17: Didier Le Gall, MPEG: a video compression standard for multimedia applications, Communications of the ACM, v.34 n.4, p.46-58, April 1991 [doi>10.1145/103085.103090]
• 18: Will E. Leland , Murad S. Taqqu , Walter Willinger , Daniel V. Wilson, On the self-similar nature of Ethernet traffic (extended version), IEEE/ACM Transactions on Networking (TON), v.2 n.1, p.1-15, Feb. 1994 [doi>10.1109/90.282603]
• 19: B. B. Mandelbrot. The Fractal Geometry of Nature. Freeman, 1983.
• 20: B. B. Mandelbrot and J. W. Van Ness. Fractional Brownian Motions, Fractional Noises and Applications. SIAM Review, 10(4):422-437, 1968.
• 21: B. Melamed and D. Pendarakis. A TES-Based Model for Compressed "Star Wars" Video. In Proc. Comm. Theory Mini-Con}., IEEE Globecorn '9~, San Fransisco, November 1994.
• 22: B. Melamed, D. Raychaudhuri, B. Sengupta, and J. Zdepski. TES-Based Video Source Modeling For Performance Evaluation of Integrated Networks. IEEE Trans. Commun., 42(10), Oct. 1994.
• 23: I. Norros. A Storage Model with Self-Similar Input. Queueing Systems, 16:387- 396, 1994.
• 24: P. Pancha and M. El Zarki. Bandwidth Allocation Schemes for Variable Bit Rate MPEG Sources in ATM Networks". IEEE Trans. Circ. Syst. Video Tech., Vol. 3(3), June 1993.
• 25: Portable Video Research Group, Stanford University. PVRG-MPEG Codec 1.1, June 1993.
• 26: F. L. Ramsey. Characterization of the Partial Autocorrelation Function. The Annals of Statistics, 2(6):1296- 1301, 1974.
• 27: A. R. Reibman and B. G. HaskeU. Constraints on Variable Bit Rate Video for ATM Networks~. IEEE Trans. Circ. Syst. Video Tech., Vol. 2(4), Dec. 1992.
• 28: D. Reininger, D. Raychaudhuri, B. Melamed, B. Sen- ~upta, and J. Hill. Statistical Multiplexing of VBR MPEG Compressed Video on ATM Networks. In Proc. IEEE INFOCOM '93, San Fransisco, Mar. 1993.
• 29: C. M. Sharon, M. Devetsikiotis, I. Lambadaris, and A. R. Kaye. Rate Control of VBR H.261 Video on Frame Relay Networks. in Proc. IEEE ICC '95, Seattie, June 1995.
• 30: Paul Skelly , Mischa Schwartz , Sudhir Dixit, A histogram-based model for video traffic behavior in an ATM multiplexer, IEEE/ACM Transactions on Networking (TON), v.1 n.4, p.446-459, Aug. 1993 [doi>10.1109/90.251897]
• 31: Sun Microsystems Computer Corporation. Sun Vid~o 1.0 User's Guide, Oct. 1993.
• 32: F. Yegenoglu, B. Jabbari, and Ya-Qin Zhang. Motion- Classified Autoregressive Modeling of Variable Bit Rate Video. IEEE Trans. Circ. Syst. Video Tech., Vol. 3(1), Feb. 1993.

INDEX TERMS

Primary 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)

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

General Terms:
Algorithms, Performance