1‘ ’ turn... .34.... \p0. . ."l 'u.’ b. ..t.. 3. 32.5.7 I. 43 p.993. .. ..X C? . o '0. 00‘. ‘00, . not... .. o. .505... B" o...- V .. .0 . It! ’9‘}... o9...-?"...u.... . a... ’\‘!~. .. . o . u .p... 0.3:! .fi ... . ...l...-. 315%.... . 3. .“.h.h..o...xo’v \ .. .4 a: . 83$. . O . 22.1.0 ... . . ‘15-..3vnu: .o‘vo..‘.h-. 1". .v‘ . u. c. .ub’...‘-..o.. 5-0.8...XI .n. . .‘l'l . cog-Ins" I. I ..‘v . .-...I. o. I.... .- 357. . Al. .0 o.¢voto,.‘€.-.. . c I .J '23.... . bl...?\.:... . ‘0... 5.3%.: fig: lo .3. 6.92.0306) ...:oc.‘i.. .. no‘u ..‘I.-o.5 O .01 . ..- . . .1. P... .S:.. r . .... 9‘..’.o . O 1.... . r... .o .83.. ..-i.. 0‘ rt.-I.IO-Da‘l .. h. a... .3‘ii .0...n.n.c.¢l O . .0...) O .A‘v..l ..'.—.Ooh I". i D O 0 C.‘. A .- ‘5! L. .t.. M. ...‘n.on .. O 4.. I. On . .:.-on. 34.. o 3...... Id ... . . ... v.It... . .. .a"..l..c .v...’ .35... . 1..'.. .o.\.l.. 01.! D‘I4l’ . .?.O. n .30.... 0.. t .0... . . . «It . ..-9 8:31 .. )I. ..A ' ... u . . $2.. . It...) I ‘31.. . .0. LI... . . ... ...v.»...~.n . . on... ’? .- Inu’f .. .Y‘35z . . ., .. I. ... . . . .‘I .oo. ‘vlo' ’.r|..o.... a . .3... .‘..a. . . 30.... 9' '0‘. . , .0. ‘03:. ‘. O .0... “fivn' 1": 9‘”. .o. r o.G.-I . .11. . . . . 1.11.... . o. .. 'u .09 ..o to... . .0 . ..I~.!.t\ 4|. ’9': ..‘.II‘1..I-.‘ it. 09': v-.‘ 0....— l '0. §..’0....> it‘..- on . Ago'lf3l .’.'f.o“$ Sit; .. . J': '1 . .3 .1. "313. o... 1.3... ..l 30" . . 0. urn-35...... . (I 0'9... 03‘s. _. 35 .v... 3.. . I . In... -0..-..v,"b..‘. coo . I. .v..ow.ltl..0..o...+.ee.lflt Q o. q .S‘ !!I,£.£OI..‘U£¢39. .‘1044 95-011 :.tt..‘§.! . 9.. .n’.9’.~t Yo . '. to. a v)— ‘ .‘: -IO . .ovlfv... .0. . . . 1.... 3:...)1. . . Tr , L .7 I u.....‘......\. . . . . . '3}..3..I.9I§ 7. 3. ...o"¢.¢. .t’Z? .......‘o.1..6 141...... u. .. 5. ‘..o,'9.... . 8!: . o.'..l3I. 2 fl ...I‘..:.o.)~ . 10.1.35)" (Gail? .. 215...... '3.....c07~ .v. 1... . 10.... .3‘....’..I7 7 .. . ‘l... .....¢... . L. ...l’.t§a..‘.o . 177...... . no“, ‘3. ~ . ...v ‘-§ .0 J'......:.. z a... :v‘aié30353 ....o .v.’ -. .."“.|O..Io.u.oaol.l‘ C. 052...}? 1630.403! .I’S.....‘ 8.; 3|-.. .‘ 08:... .32..) .9... .o...l’£'lk . .. ,{voulI-‘R \. :o.‘ 90.1'50...’ . ll.u|.3.§..... 0r]: 6.0.3:... .‘réQ'EV .. 3” . O.ou.‘...!.o..:‘l.‘ .1 .9 .30.,»0. .0“ .loul.:.\.‘o.‘a. .. -0203! .o 5... 33. 3...! 1.. Y..I..'Q.bo-of"$l..l .- . .o... .-.lco‘c¢ 2.3.1.... ..'. 0......1L 0...": .5. Q. v. .1:.'.vznu.0 O . .‘fil. 1‘ ‘2'"! ‘I. 9 1' 1,339....- ,'. '0’... ’u. .r Z... .9.‘ I: .Ifi... .05.]- . .0. .Qos. (I. (X. 30.19 3'. 3 2 . 0-..0. 13.3. 113:5... no... ‘21:}... . . E... A}. . . . . "‘.u‘. 9 up Dav . .03.... 0‘ 2 . . to‘n .4"....O‘u. .- fog)...” v. 736.. no lQJKICZ :6: .0! .Cl'.’ 5 .3 :- ...O'“‘.l OI...»(£...I0 .A). ,3 ... ..Q... .‘3....t.||’ 0:33.] . 0. ...0. .‘O... . c .. . A .7. \y o .1 0.. .O..'..2:.¢ofi.|uv ‘m .9\ 3:54... .H‘r .’.3u.l.o.u.u90....:~n.. 3.... . 1v .. . . v V , P . ION v . C9 v . ..-. . .. n ... A...» .. . . .. . .L .l 3...... . I. 0. .V ..| .3 .... v. .I... .u. . \ '\ a .0 ”VA Ilol’. .o.|. {h}. .‘ .‘. I . L ‘0 § 0‘ I. t T . o . . . .v .. 9 .. . . u...- wTJJlmuu‘ohut.wJ...N‘3.-auun.. §. .0 _.....8..Wn0.om.‘v........h. .. .. o.t.r91JvoM.H-2."thc 0 3:30.. Oni~Ov .0‘2‘l’fi ”‘49.... hfg 'V’Vi. . Us. +h‘rb".u.n.t..tii’o ... .. o '. .1... 0, Q... o- . ...o.. o... .Q.|o. ..bb .9}... only...» ..\\..D to...- v’..‘o.:' . a . . ,. ..~ . 0‘ . .....\\ . . I ... . ‘. C nl‘llu ll nl'", .‘I' II‘! I ..I.. I m |Illllllllll|lllllllllllllllllllllilll N 3 1293 01402 7928 This is to certify that the dissertation entitled DESIGN AND ANALYSIS OF A BUFFER MANAGEMENT SCHEME FOR MULTIMEDIA TRAFFIC IN ATM NETWORKS presented by MARNAN M. KRUNZ has been accepted towards fulfillment of the requirements for Ph.D. degree in ETECtrical Eng. ém .» / Date MSU i: an Affirmative Action/Equal Opportunity Institution 0-12771 24/ // Major profess/or g 7 _, / f- 7; "'1 . ' wt ~—— .fl .*—_.__—. . - A_,_._.__~.-w fl w _ _fi___-—._ LIBRARY Michigan State University PLACE ll RETURN BOX to remove this checkout from your rooord. To AVOID FINES rotum on or baton «to duo. DATE DUE DATE DUE DATE DUE * JET? MSU to An Attirmotm AotioNEquol Opportunity Imtttmion WM: DESIGN AND ANALYSIS OF A BUFFER MANAGEMENT SCHEME FOR MULTIMEDIA TRAFFIC IN ATM NETWORKS By Manuan M. Kmnz A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Electrical Engineering 1995 ABSTRACT DESIGN AND ANALYSIS OF A BUFFER MANAGEMENT SCHEME FOR MULTIMEDIA TRAFFIC IN ATM NETWORKS By M arwan M. K mm This research is concerned with the design and analysis of a buffer management scheme to be implemented in the switching and multiplexing nodes of a broadband network such as Broadband Integrated Services Digital Network (B—ISDN). The goal of B-ISDN is to provide a unified means of communications for many types of appli- cations which generate data, voice, video streams, and combinations of these streams (i.e., multimedia sources). Such a goal has been made possible through the stan- dardization of the Asynchronous Transfer Mode (ATM) protocol. One of the most challenging issues in the design of B-ISDN / ATM networks is to guarantee the perfor- mance requirements (known as Quality-of-Scrvice (QoS)) of many traffic sources that differ in their statistical characteristics. Since these streams also differ in their cell loss and delay sensitivities, the network must be designed to support multiple levels of loss and delay performance. ’ In this work, we introduce a new approach to providing QoS guarantees based on buffer management. In this approach, loss and delay priority mechanisms are both used in the design of a buffer management scheme that supports multiple levels of QoS requirements. The pr0posed scheme is referred to as N ested Threshold Cell Discarding with Multiple Buflers (NTCD / MB). We describe the general structure of NTCD / MB and demonstrate its effectiveness via analysis and simulation. NTCD / MB is found particularly useful when the aggregate traffic arriving at an ATM node consists of several heterogeneous streams. We study the performance of N TCD / MB under different types of traffic, including bursty traffic streams (e.g., data sources) and variable-bit-rate (VBR) video streams. Accurate models will be used to characterize the traffic sources under study. Some of these models are already being used in the literature, such as the fluid model and the Markov-modulated Poisson process model. Additionally, we propose new traffic models to characterize the VBR video streams that are generated based on the emerging Moving Picture Expert Group (MPEG) compression standard. Performance evaluation of the NTCD/ MB is used in the dimensioning and partitioning of the buffer space, so that multiple levels of loss and delay performance requirements can be supported by the network. To my wife, Carine iv ACKNOWLEDGMENTS Achievements are meaningless if no one else shares in them. This pinnacle of my efforts would not have been possible without the assistance and contributions of several people. Foremost among those whom I thank is my advisor, Dr. Herman Hughes, for his continuous support and guidance during the course of this research. I owe him no less gratitude for the manner in which he has overseen my career as a graduate student. I would like to thank the members of my guidance committee: Dr. David Fisher for his editorial, technical, and thematic comments on this dissertation; Dr. Diane Rover for providing me constantly with valuable advice on my career goals and also for her thought-provoking questions and comments; Dr. Vince Melfi for sharing his valuable insights in probability theory; and Dr. Philip Mckinley for helping me understand the basic concepts of computer networks. This dissertation could not have been completed if it were not for the generosity and patience of my beloved wife. Through her love and support I overcame many times of hardship and frustration. I must also extend my thanks and appreciation to my family who continuously provided me with their love and support. Many thanks to my friends Mohannad Bataineh, Ahmad Al—Ostaz, and Eman El-Sheikh for providing me with many valuable comments for my oral presentation. This research was supported by a grant from the National Science Foundation (# NCR 9305122). TABLE OF CONTENTS LIST OF TABLES x LIST OF FIGURES xi 1 Introduction 1 1.1 Scope and General Goals ........................... 1 1.2 Contributions of the Thesis ......................... 5 2 Buffer Management and Priority Mechanisms 8 2.1 Introduction .................................. 8 2.2 Design of Buffer Management Schemes ................... 10 2.2.1 Delay Priority Mechanisms ........................ 10 2.2.2 Loss Priority Mechanisms ......................... 13 2.2.2.1 The Push-Out Mechanism ........................ 15 2.2.2.2 The NTCD Mechanism ......................... 15 2.3 Analysis of Buffer Management Schemes .................. 17 2.3.1 Burstiness and Traffic Correlations .................... 17 2.3.2 Traffic Models in ATM Networks ..................... 19 2.3.2.1 The MMPP Model ............................ 19 2.3.2.2 ON/ OFF Models ............................. 20 2.3.2.3 Fluid Models ............................... 20 2.3.2.4 T ime-Series Models ........................... 21 2.3.2.5 The TES Model ............................. 23 2. 4 The Proposed Buffer Management Scheme ................. 23 2.4.1 Motivation ................................. 23 2. 4. 2 The General Structure of the NTCD / MB Scheme ............ 25 3 Simulation Studies of NTCD / MB 27 3.1 Introduction .................................. 27 3.2 Case Study I: Two Buffers and One Threshold ............... 28 3.2.1 The Mechanism ............................... 28 3.2.2 Traffic Description ............................. 29 3.2.3 Simulation Results ............... ‘ .............. 30 3.3 Case Study II: Two Buffers and No Thresholds .............. 36 3.3.1 The Mechanism ............................... 36 3.3.2 Traffic Description ............................. 38 3.3.3 Simulation Results ............................. 38 3.4 Case Study III: Two Buffers and Two Thresholds ............. 41 vi vii 3.4.1 The Mechanism ............................... 41 3.4.2 Traffic Description ............................. 45 3.4.3 Simulation Results ............................. 45 4 Fluid Analysis of N TCD / MB 49 4.1 Introduction .................................. 49 4.2 Traffic Description .............................. 51 4.3 The Conditional Equilibrium Distributions ................. 54 4.4 Boundary Conditions ............................. 56 4.5 The Unconditional Distributions ....................... 57 4.6 Performance Statistics ............................ 59 4.7 Numerical Investigations ........................... 62 4.7.1 Computational Considerations ....................... 62 4.7.2 Numerical Results and Simulations .................... 62 4.8 A Note on Fluid Models for Video Traffic .................. 67 5 Characterization of MPEG-Coded Video Streams 74 5.1 Introduction .................................. 74 5.2 Overview of the MPEG Standard . ..................... 77 5.2.1 Features of the MPEG Compression Algorithm ............. 78 5.2.2 Temporal Redundancy Reduction ..................... 79 5.2.3 Spatial Redundancy Reduction ...................... 81 5.3 The Experimental Setup ........................... 81 5.4 Empirical Statistics .............................. 84 5.4.1 Frame-Size Measurements ......................... 84 5.4.2 The Correlation Structure ......................... 89 5.5 Proposed Traffic Models for MPEG Streams ................ 92 5.5.1 First Model ................................. 93 5.5.1.1 Model Description ............................ 93 5.5.1.2 Frame Size Distribution ......................... 94 5.5.1.3 Autocorrelation Function ........................ 100 5.5.2 Second Model ................................ 103 5.5.2.1 Motivation ................................ 103 5.5.2.2 Scene Length Distribution ........................ 105 5.5.2.3 Frame Size Distributions . . . . . . . . . . . . . . . . . . . . . . , . 106 5.6 Queueing Performance under MPEG Streams ............... 114 5.6.1 Trace-Driven Simulations ......................... 116 5.6.2 Queueing Performance Based on Proposed Models ........... 120 6 The Performance of NTCD / MB under Multimedia 'ITaffic 123 6.1 Introduction .................................. 123 6.2 Input Traffic and Associated (.208 Requirements .............. 124 6.3 Efficient Allocation of Buffers and Bandwidth ............... 127 6.3.1 Buffer-Bandwidth Tradeoff for Data Traffic ............... 129 6.3.2 Buffer-Bandwidth Tradeoff for Voice Traffic ............... 131 viii 6.3.3 Buffer-Bandwidth Tradeoff for Video Traffic ............... 135 6.3.4 Performance under a Work-Conserving Discipline ............ 138 7 Summary and Future Research 144 7.1 Summary ................................... 144 7.2 Future Research ................................ 146 7.2.1 Generalizing the Proposed Video Models ................. 146 7.2.2 Analyzing the Queueing Performance of MPEG Streams ........ 147 Bibliography 148 4.1 5.1 5.2 5.3 5.4 6.1 LIST OF TABLES Cases used to obtain the conditional distributions .............. Summary statistic for the frame size sequence ................ Maximum likelihood estimates for the parameters of the lognormal fits. . Average, maximum, and minimum cell loss rates. ............. Multiplexing gain at different loss rates. .................. Optimal values for T3 and 33 that guarantee the QoS requirements. . . . ix 2.1 2.2 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14 3.15 3.16 3.17 3.18 3.19 3.20 3.21 3.22 3.23 3.24 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 LIST or FIGURES Structure of NTCD with one buffer ...................... 16 General structure of NTCD/ MB. ...................... 26 Structure of NTCD/ MB mechanism. .................... 28 Loss probabilities versus total load using NTCD / MB ............ 31 Average response time versus total offered load under NTCD / MB. . . . . 32 Average response time versus total offered load under NTCD. ...... 33 Loss probabilities versus total load for RL cells. .............. 33 Loss probabilities versus threshold using N TCD / MB. ........... 34 Average response time versus threshold using NTCD / MB. ........ 35 Loss probabilities versus the size of BNR using NTCD / MB. ....... 35 Loss probabilities versus RT load ratio using N TCD / MB .......... 36 Structure of NTCD/ MB in Case Study II. ................. 37 Structure of a single-buffer NTCD in Case Study 11 ............. 37 Cell loss probability for N RT traffic versus pm (p, is varied) ........ 40 Cell loss probability for RT traffic versus pm (p, is varied) ......... 40 Cell loss probability for N RT traffic versus pm (pfl is varied) ........ 42 Cell loss probability for RT traffic versus pm (pn is varied) ......... 42 Average waiting time of a NRT cell versus pm (p, is varied) ........ 43 Average waiting time of a RT cell versus pm (p, is varied) ......... 43 Average waiting time of a NRT cell versus pm (pn is varied) ........ 44 Average waiting time of a RT cell versus pm (,0n is varied) ......... 44 Structure of NTCD/ MB in Case Study III .................. 45 Cell loss rate versus pm in Case Study III (Pr is varied). ......... 46 Cell loss rate versus pm in Case Study III (pn is varied). ......... 47 Cell loss rate versus threshold of BR in Case Study III ........... 48 Cell loss rate versus RT load ratio in Case Study III. ........... 48 Point process and fluid representations of an ON / OF F traffic source. . . 50 Structure of NTCD / MB mechanism. .................... 51 State transition diagram for a (N4 + 1)-state MMFF. ........... 53 Loss probability of NRT cells versus the size of BNR. ........... 64 Complementary buffer distribution for BR .................. 65 Loss probability for RL cells versus threshold. ............... 66 Average waiting time for RH cells versus threshold. ............ 66 Loss probability for RL and average waiting time for RH versus threshold. 68 Probability that the waiting time for RT cells exceeds t = 0.2841. . . . . 68 X xi 4.10 Loss probability for RL cells versus RT load ratio .............. 4.11 Average waiting time for a RH cell versus RT load ratio. ......... 4.12 Aggregate arrival rate from NW; video sources ................ 4.13 Transition diagram for the fluid model of video traffic. .......... 5.1 A sequence of MPEG frames. ........................ 5.2 A schematic diagram of the experimental setup. .............. 5.3 Pseudo-code for the program used in digitizing video frames ........ 5.4 Compression pattern used to generate the empirical data .......... 5.5 Frame size sequence (frames 1 to 2000). .................. 5.6 Frame size sequence (frames 2001 to 4000) .................. 5.7 Frame size sequence (frames 1401 to 1550) .................. 5.8 Frame size histogram. ............................ 5.9 Sample path from I -frames subsequence. .................. 5.10 Sample path from P-frames subsequence ................... 5.11 Sample path from B-frames subsequence ................... 5.12 Autocorrelation function for the frame size of the VBR sequence. 5.13 Correlations in the I-frames subsequence ................... 5.14 Correlations in the P-frames subsequence. ................. 5.15 Correlations in the B—frames subsequence. ................. 5.16 Histogram and fitting pdfs for the size of an I frame. ........... 5.17 Histogram and fitting pdfs for the size of a P frame ............. 5.18 Histogram and fitting pdfs for the size of a B frame. ........... 5.19 The pdf for the size of an arbitrary frame based on first model. ..... 5.20 Autocorrelation function for the frame size sequence based on first model. 5.21 Frame size sequence for a synthetic stream based on the first model. . . . 5.22 Frame size histogram for a synthetic stream based on the first model. . . 5.23 Empirical acf for the frame size sequence of a synthetic stream generated using first model. ............................. 5.24 Scene length histogram. ........................... 5.25 Q-Q plot for the scene-length distribution. ................. 5.26 Histogram and fitted pdfs for the average size of I frames in a scene. . . . 5.27 The sequence {A}(n)} ............................. 5.28 The acf for the sequence {A}(n)} and for an AR(2) model. ....... 5.29 Partial autocorrelation function for the sequence {A}(n)}. ........ 5.30 Histogram for the sequence {A}(n)}. .................... 5.31 Histogram of the residuals in an AR(2) fitted model. ........... 5.32 Autocorrelation function for the residuals in the AR(2) fit. ........ 5.33 Generating a synthetic stream based on the second model. ........ 5.34 A multiplexer for MPEG streams ....................... 5.35 Average cell loss rate versus buffer size in trace-driven simulations. 5.36 Average cell loss rate versus utilization .................... 5.37 Average cell loss rate versus buffer size .................... 5.38 Mean queue length versus buffer size ..................... 87 88 88 90 91 91 92 94 95 99 103 104 104 105 107 107 109 110 110 111 112 113 114 115 116 118 119 121 122 xii 6.1 Structure of N TCD / MB for data, voice, and video streams ......... 128 6.2 Loss probability versus buffer size for data traffic with N1 = l ....... 130 6.3 Loss probability versus buffer size for data traffic with N1 = 10. ..... 130 6.4 Buffer-bandwidth tradeoff for data traffic. ................. 131 6.5 Loss probability versus buffer size for voice traffic with N2 = 1 ....... 132 6.6 Loss probability versus buffer size for voice traffic with N2 = 10 ...... 133 6.7 Buffer-bandwidth tradeoff for voice traffic. ................. 134 6.8 Loss probability for low priority (P and B) cells versus buffer size. . . . . 136 6.9 Loss probability for low priority (P and B) cells versus threshold. . . . . 136 6.10 Loss probability for high priority (1) cells versus buffer size at T = T‘. . 138 6.11 Buffer-bandwidth tradeoff for video traffic .................. 139 6.12 Cell loss rates versus buffer, sizes for data and voice traffic. ........ 142 Chapter 1 Introduction 1.1 Scope and General Goals This research is concerned with the design and analysis of a buffer management scheme for multimedia traffic in a Broadband-Integrated Services Digital Network (B—ISDN). Buffer management is an important aspect in the design of a switching or multiplexing B—ISDN node. The goal of B-ISDN is to provide a unified means of com- munications for a wide range of applications including video-telephony, multi-spectral imaging, High-Definition TV, medical imaging, multimedia conferencing, and LAN interconnections. Achieving this goal became possible through the standardization of the Asynchronous Transfer Mode (ATM) transport protocol [10, 55]. ATM is an at- tractive switching technology which is characterized by high-speed fiber transmission facilities and simple hardwired network protocols. These protocols are designed to match the transmission speeds of communication links. In ATM, data generated by various traffic sources are encapsulated into fixed-length packets known as cells. The size of an ATM cell is 53 bytes, of which 5 bytes are used as a header. As a backbone switching network, ATM is designed to minimize the overhead incurred in processing network protocols. The switching in an ATM network is done in hardware ATM 1 2 switches, unlike traditional packet-switched networks in which switching is done by computer running communication processes. One of the most challenging issues in the design of B-ISDN / ATM networks is to provide guaranteed service to diverse traffic streams without underutilizing the available bandwidth capacity. These performance guarantees, which are known as the Quality-of-Service (QoS) requirements, are particularly important for time—critical applications such as interactive video and voice communications. Common measures for the QoS requirements are the cell loss rate, the absolute end-to—end cell delay, and cell delay variation (i.e., jitter). Other measures include the cell loss rate within a burst and the call blocking probability. The notion of guaranteed service is a major migration from the design methodology of conventional packet networks that provides either a best-effort delivery or a reliable transport delivery (e.g., TCP/IP transport technology). The new types of traffic that will be transported over B-ISDN require more than just reliability; they require guarantees on the delivery performance perceived by their cells. In packetized voice, for example, each voice packet (or cell), must be delivered in no more than 200 msec so that this packet can be decoded and played back in real-time. It should be noted, however, that providing performance guarantees in ATM net- works does not necessarily imply that a fixed amount of bandwidth must be exclu- sively reserved for a given connection (as in the case of circuit-switched networks which are based on time-division multiplexing (TDM)). Instead of using TDM, ATM networks employ statistical multiplexing to efficiently utilize network resources (i.e., bandwidth and buffers). In statistical multiplexing cells from various connections share the network resources on a need basis. Statistical multiplexing is particularly useful when the aggregate traffic consists of a number of sources each of which is characterized by alternating active and idle periods, with the active periods being shorter (on the average) than the idle periods [70]. 3 Ideally, the network must guarantee the QoS requirements of all communicat- ing sessions while, simultaneously, taking advantage of statistical multiplexing. Since traffic sources generally differ in their QoS requirements, the network is being designed to provide multiple grades of service. Each grade of service guarantees specific (pre- determined) levels of loss and delay performance. Designing the network to guarantee multiple grades of service while employing statistical multiplexing poses difficult chal- lenges concerning the proper buffer management and bandwidth allocation schemes to be implemented at ATM nodes. In certain cases, the loss of some bandwidth by non-statistical (i.e., synchronous) multiplexing could be justified by the need to provide QoS guarantees for certain types of traffic. A combination of statistical and non-statistical multiplexing may result in moderate bandwidth utilization and simple traffic control [70]. Performance guarantees are classified as deterministic and statistical [69]. Deter- ministic guarantees provide bounds on the performance experienced by all cells within a session. Statistical guarantees ensure that not more than a certain fraction of the cells within a session will experience a performance worse than some specified value. Statistical guarantees are often provided asymptotically (i.e., over an infinite time interval), but can also be given over fixed time intervals. Three general approaches to providing deterministic and statistical QoS guarantees can be identified [44]: 1. The tightly controlled approach — This approach provides deterministic guaran— tees by sacrificing some bandwidth to preserve the characteristics of a traffic stream when this stream traverses multiple nodes. In addition to low utiliza- tion, this approach results in increasing the implementation complexity of buffer management. 2. The approximate approach - Here, traffic models are used to analyze the queue— ing behavior of the traffic and to provide approximate statistical guarantees. This approach depends mainly on queueing analysis of ATM networks. Com- 4 plex nontrivial models are being used to characterize the stochastic behavior of the traffic. Such models take into consideration the correlations between arrivals and the variability of the arrival rate of a given stream [12, 22, 52, 56]. 3. The bounding approach - Bounds on performance can be developed to provide statistical and deterministic guarantees. No assumptions are being made about the stochastic behavior of the traffic. This approach has been used to provide asymptotic stochastic bounds on performance, as well as bounds that hold over fixed time intervals. Many factors influence the choice of a particular approach to guaranteeing the QoS requirements. These factors include the nature of the requested QoS (e.g., cell loss rate over finite duration versus infinite duration), the complexity of the admitted traffic streams (e.g., correlations between cell interarrival times), and the interactions among different streams at various multiplexing and switching nodes. Hence, it is not always possible to analytically evaluate the performance of the network and provide QoS guarantees using a given approach. In this research, we adopt the approximate statistical approach to guaranteeing the QoS requirements. This approach is favored over other approaches because it permits us to derive many tractable performance results, and consequently, provide closed-form expressions for several measures of performance (e.g., cell loss rates and mean queueing delay). Our emphasis here is on the performance guaranteed by a single ATM node (a multiplexer or a switch). Since the user QoS requirements are requested on an end-to-end basis, it is the responsibility of the service provider (i.e., the network) to assign various proportions of these requirements to individual nodes along the path of the connection. If each of these nodes can guarantee its proportion, then the end-to-end QoS requirements are consequently guaranteed. Throughout this thesis, the QoS will be used to refer to the fraction of the end-to—end QoS that has been assigned to a single node. 5 The general goal of this research is to introduce a new approach to providing QoS guarantees based on buffer management. In this approach, loss and delay priority mechanisms are both used in the design of a buffer management scheme that supports multiple levels of cell loss and cell delay performance. We propose such a scheme and refer to it as Nested Threshold Cell Discarding with Multiple Bufl'ers (NTCD/MB)). As will be demonstrated later, NTCD / MB is most appropriate in heterogeneous and multimedia traffic environments, where multiple grades of service are needed. Our objectives can be summarized as follows: 1. Introduce the NTCD / MB scheme and demonstrate its effectiveness in guaran- teeing multiple levels of loss and delay performance. 2. Evaluate the performance of N TCD / MB under different types of traffic, includ- ing data, voice, and video sources. 3. Provide “optimal” dimensioning and partitioning for the buffer space associated with the proposed scheme. 1.2 Contributions of the Thesis The three objectives listed above have been addressed throughout the course of this research. A general structure for the NTCD / MB buffer management scheme was developed and is outlined at the end of Chapter 2. Because of the merits of this scheme (with regard to performance and implementation complexity), we propose its implementation in ATM switches and multiplexers. Analysis and simulations were used to study the performance of NTCD / MB. Our focus was on particular forms of this mechanism that are useful for realistic traffic mixes. Simulations of the NTCD/ MB (Chapter 3) were conducted to evaluate the performance of the NTCD / MB under data and voice traffic inputs. In these simula- 6 tions, the aggregate trafic is modeled using the Markov-modulated Poisson process (MMPP) model. This complicated random process is appropriate in characterizing voice and data streams. Simulations of buffer systems become prohibitive when the values for buffer overflow probabilities are below 10'6. The QoS requirements for many applications include a cell loss rate in the order of 10'10 (e.g., File Trans- fer Protocols (FTP)). In these cases, traffic control studies must rely on analytical results to predict and evaluate the queueing performance in a given buffer system. We provide a complete fluid-flow analysis for the proposed N TCD / MB (Chap- ter 4). The fluid models used in this analytical study are appropriate in character— izing data and voice streams. In addition, our analysis can be easily extended to certain types of compressed video (based on the model of Maglaris et al. [52]). Our analytical results include the distribution for the buffer occupancy (for each buffer in the NTCD/ MB mechanism), the waiting time distributions, the overflow probabili- ties, the throughputs, and other statistics. Based on these results, it was possible to predict the cell loss probability for each buffer in the range of 10’”. These values are impossible to achieve via simulations. Performance studies in Chapter 3 and 4 are restricted to voice and data sources since trafic models for these sources have been developed and are widely accepted. On the other hand, models for compressed video traffic are still in the very early stages of development. This is mainly due to the complexity of video traffic and the variety of compression algorithms in use. Current models for video streams are only applicable to certain types of video (e.g., video-phones) and based on certain (non- standard) compression techniques. In 1991, the International Standards Organization (ISO) completed the first draft on a standard compression algorithm known as Mov- ing Picture Expert Group (MPEG) [26]. This draft (referred to as MPEG4) defines the compressed bit stream for video and audio at 1.5 Mbits/s bit rate. The stan- dardization of MPEG makes it worthwhile to study the performance of NTCD / MB 7 under MPEG-compressed video streams. To conduct such a study, we needed a traffic model for an MPEG stream or, alternatively, actual traces of MPEG streams to be used in trace-driven simulations of N TCD / MB. Unfortunately, neither traffic models nor empirical data were available when our research was initiated. (mainly due to the short history of MPEG). For this reason, we extend the goals of our research to include the characterization and modeling of MPEG-compressed streams. The result- ing models are to be used in studying the performance of NTCD / MB under video (as well as data and voice) traffic. Empirical studies were first conducted to capture, digitize, and MPEG-compress a long stream of video taken from an entertainment movie. We used these data to develop two models for an MPEG stream (Chapter 5). The first model is based on fitting the number of cells in MPEG frames by lognormal probability density functions (pdfs). These pdfs were used along with the compres- sion pattern to generate synthetic streams based on this model. In addition to the lognormal fits and the compression pattern, the second model incorporates, as well, the scene dynamics in the movie. Both models proved to be sufficiently accurate in capturing several aspects of the actual traffic. More importantly, their queueing performance is quite similar to the trace-driven performance. With traffic models for MPEG video streams in hand, we studied the performance of the NTCD/ MB mechanism under data, voice, and MPEG video streams (Chap- ter 6). By combining our analytical and simulation results, we computed the optimal buffer-bandwidth pairs that are needed to guarantee given sets of QoS requirements. Although the treatment in Chapter 6 was carried for a case study, it can be used, in general, for the dimensioning and optimization of resources in any structure of the NTCD / MB mechanism and under any sets of QoS requirements. Finally, the thesis is concluded in Chapter 7, and pointers to future research are also provided. Chapter 2 Buffer Management and Priority Mechanisms 2.1 Introduction Traffic streams transported over a fully evolved multimedia network such as B-ISDN are expected to have a wide range of performance requirements (i.e., QoS). Not only is this true for a heterogeneous mix of traffic, but also for certain individual traffic sources that generate cells with several loss and / or delay requirements, as in the case of subband coded video [35]. To satisfy the QoS requirements for all streams, the network may choose to provide indistinguishable transport service based on the most stringent QoS requirements. Such a strategy is too restrictive and significantly underutilizes network resources, particularly when the traffic streams with the most demanding requirements constitute a minor fraction of the total traffic. Alternatively, the network may offer multiple bearer capabilities (i.e., grades of service), resulting in efficient resource utilization. This requires assigning different levels of ‘delivery’ priority to incoming cells, and then offering differential service to these cells using priority queueing mechanisms. Such mechanisms can be implemented at various 8 9 buffering stages in the network. A priority mechanism in this context refers to the scheduling and / or admission algorithm in a buffer (queue), and is often called a bufier management scheme. To maintain a simple and fast traffic control, it is reasonable to support a small number of priority classes. The use of priority gives the network the flexibility to dynamically adjust to different traffic mixes, resulting in an increase in the total admissible load as compared to non—prioritization [35]. Priority mechanisms are also useful in other areas of traffic control such as traffic policing. Policing is a preventive control mechanism which ensures that an admitted traffic stream conforms to its contract with the network. This contract normally specifies certain traffic parameters that characterize the behavior of the source (e.g., peak bit rate, mean bit rate, average burst length). If a stream violates its contract, the network provider can assign a lower priority to the violating cells and transport them with less performance guarantees (or with no guarantees at all). Once priority classes have been defined, the network must be designed to map these classes into corresponding guaranteed grades of service. This requires a proper buffer management scheme to be implemented in the buffers of switching and mul- tiplexing ATM nodes. Such a scheme ensures that the loss or delay performance experienced by a traffic stream is directly related to its class. The study of priority queueing schemes (as to their role in providing guaranteed Q08 in ATM networks) involves two main issues: one is the design of these schemes and the other is the evaluation of their performance. In designing a priority scheme for ATM networks, one must take into account the hardware requirements to imple- ment such a scheme. These requirements could limit the practicality of the priority scheme. Evaluating the performance of a priority scheme is often more challenging than the design itself since it requires a considerable amount of research to provide a theoretical or an experimental assessment of performance. In this section, we review 10 the most relevant literature which addressed both issues. We further demonstrate the main drawback of current buffer management schemes, namely their inefficiency in providing multiple grades of service in both principal measures of performance: loss and delay. This motivates the introduction of a new buffer management scheme, which is the focus of this research. 2.2 Design of Buffer Management Schemes Buffer management can be decomposed into two components: service discipline, which determines the order in which cells in the buffer are served; and buffer access control, which deals with admitting cells to the buffers [50]. Explicit or implicit priority rules may be applied to either or both disciplines. Accordingly, two types of priority queueing mechanisms can be identified, based on where the priority rule is enforced: delay and loss priority mechanisms. 2.2.1 Delay Priority Mechanisms In a delay priority mechanism, the priority rule takes place at the output of the buffer when a cell is to be served. It is in essence a scheduling algorithm. Higher priority cells are given preferential service over lower priority cells in the scheduling order. Delay priority mechanisms are quite useful in the presence of time-critical traffic (for example, alarms and real-time control messages in manufacturing environments) that requires a rapid transfer of data across the network. Under certain traffic mixes, these mechanisms are also found to enhance the overall performance by reducing the cell loss rate in the network. Some of the popular delay priority mechanisms are as follows [9, 49]: o Head-Of-the-Line (HOL). o Queue Length Threshold (QLT). 11 0 Minimum Laxity Threshold (MLT). o Head-Of-the-Line with Priority Jumps (HOL-PJ). o Earliest-DeadlineFirst (EDF). The HOL scheme is a static priority scheduling policy which has been extensively studied in queueing theory books. It is static in the sense that high priority cells (assuming two classes for illustration purposes) are always scheduled to be served before all low priority cells, regardless of the traffic conditions and the relative buffer occupancy from the two classes. The high priority class is usually a delay-sensitive (e.g., real-time) traffic. The low-priority class contains all other types of traffic which are non-delay-sensitive, but possibly loss-sensitive. A non—preemptive priority is usu- ally assumed. When the queue contains more than one high—priority cell, these cells are served in a FCFS fashion. This applies also to low priority cells when the queue does not contain high priority cells. HOL provides relatively low delays for the delay- sensitive traffic while causing high losses for other types of traffic. The performance of the low priority traffic is severely degraded if a large portion of the network traffic belongs to the high priority class. Better scheduling can be achieved using dynamic priority schemes such as QLT, MLT, and HOL-PJ. In these schemes, priority lev- els are dynamically adjusted to cope with the traffic conditions and the content of the buffer. Chipalkatti et al. [9] have shown that the QLT and MLT schemes offer better performance for the low priority traffic compared to HOL. The QLT scheme gives priority to the real-time traffic whenever the number of nonreal-time cells in the buffer reaches a certain threshold; otherwise the real-time traffic is given priority. In the MLT scheme, the scheduling priority is given to real—time traffic as long as the minimum laxity of real-time cells is less than some threshold (the laxity of a cell is defined as the time spent in queue before its deadline expires). Therefore, a real-time cell remains in the queue until either the cell is transmitted within its deadline or 12 discarded and considered lost. In this case the priority is given to the nonreal-time trafic. Both the MLT and QLT schemes can be used to achieve a desired level of performance for each traffic class by choosing an appropriate value for the threshold parameter. The QLT discipline, however, is easier to implement because it involves less processing at each switching node. Analytical studies of these disciplines were reported in [9]. The HOL—PJ scheme was proposed by Lim and Kobza [49] for an ATM switch serving multiple classes of delay-sensitive traffic. In this scheme, cells with different delay requirements (sometimes within a single traffic stream) enter one of several queues. Each queue is associated with a certain delay constraint, with tighter con- straints having higher priority. For example, voice and video traffic are assigned a higher priority than other types of traffic, since their cells must be delivered no later than a predetermined play-out time. Each queue in the HOL-PJ scheme implements a FCF S discipline, with higher priority queues having non-preemptive priority over lower priority queues. A cell leaves its queue when its maximum queueing delay ex- ceeds a predetermined limit, and it joins the end of the next higher priority queue. This process continues until the cell is served. Therefore, the maximum queueing delay for a given cell is determined by the sum of delay constraints at all the queues with priority levels equal to or higher than the starting priority level of the cell. The performance for each class can be controlled by adjusting the values of the delay limit. The processing overhead required to move cells between queues and the need for time stamps and time-outs are some undesirable features of this scheme. Under the EDF scheme [8], the delays experienced by cells along long routes are reduced at the expense of longer delays for cells along short routes. One popular sim- plified version of EDF is called Older-Customer—First (OCF). In this policy, higher priority is given to older cells (based on time stamps); a new arriving cell joins a queue behind older cells and ahead of younger ones. Thus, the older cells should 13 expect shorter waiting times. OCF can be used, for example, in packetized voice communications to compensate for the variable delays incurred due to queueing of cells at previous nodes. This improves the quality of the speech by minimizing the de- lay variability of voice cells. A disadvantage of this scheme is the processing overhead required to move and monitor cells among queues. The practicality of this scheme is not clear yet and awaits future study. Several other delay-dependent priority disci- plines have also been proposed (see [8] and references therein). One major disadvantage of delay priority mechanisms is the need for a selection algorithm to determine the order in which cells are to be served. Such an algorithm significantly increases the implementation complexity of these schemes and limits the switching speed. Recent emphasis has focused on loss priority mechanisms because of their simplicity that is necessary to implement fast ATM switches. 2.2.2 Loss Priority Mechanisms In this type of priority mechanisms, the priority rule is applied at the input to the buffer. Cells of higher classes have priority over cells of lower classes with regard to being admitted to the buffer. A loss priority mechanism is, therefore, a selective cell discarding scheme in which a cell of a given class is dropped (rather than delayed) to accommodate a higher priority cell in the bufier. Loss priority mechanisms were first introduced to control congestion in ATM nodes [3]. They are needed to protect an ATM node from the stochastic fluctuations in the traffic which may temporarily deplete network resources (nodal buffers and transmission links) and cause congestion to develop. These schemes are also used to guarantee different cell loss requirements of various classes of traffic. The use of a loss priority scheme results in an increase in the total admissible load (i.e., overall utilization) or, alternatively, decrease in the required buffer space. Several loss priority schemes were proposed and analyzed [76, 59, 35, 34, 72, 50, 78]. 14 The scheme studied by Yin et al. [76] is based on selectively discarding voice cells whose loss will produce the least degradation in the reconstructed voice signal. The results in [76] indicate that during congestion periods the average waiting time of data cells can be significantly reduced by discarding a small fraction of voice cells. An advantage of this mechanism is that it lends itself to simple hardware implementation. Petr et al. [59] used a similar technique to control temporal congestion in a combined voice-data network by taking advantage of the inherent structure of the speech signal. For instance, the relative importance of different segments of the speech is recognized, and active speech is given priority over background noise during silence periods. A minimum short-term signal degradation is deliberately introduced by dropping less important information in order to improve the overall network performance. An early example of this scheme is found in the older T1 multiplexer systems, in which the least significant bit of the PCM speech samples is periodically discarded to provide signaling information. Congestion control in packetized voice systems using priority discarding was also proposed in [77] and [75]. In these systems, by using either an embedded coding technique [19] or even/odd sample method [31], the more significant information is carried by high priority cells, and the less significant information by low priority ones. It is obvious that some low priority cells experience fairly long waiting times and can not be included in reconstructing the voice signal. Therefore, it is appropriate to discard these cells at the transmitter in order to reduce congestion in the network. In other studies [11, 57], a slightly different priority discarding scheme was pro- posed for voice traffic. More important bits (not cells) are given higher priority over less important ones. A possible disadvantage of this discipline is the excessive per-bit processing overhead, which makes it less attractive for the ATM environment. Priority discarding mechanisms were also proposed for video traffic [32, 18]. An image that is encoded by a layered coding technique is divided into two segments: a 15 high priority segment that contains the important cells (e.g., synchronization infor- mation), and a low priority segment that consists of the ordinary video data. When congestion occurs, the low priority cells are dropped. A layered coding technique for video signals was introduced by Kishino et al. [32] which was shown to be suitable for cell loss compensation in ATM networks. A two—layer conditional replenishment coding technique of variable bit rate (VBR) video signals was proposed by Ghanbari [18], where the more important video cells (referred to as ‘guaranteed’ cells) are given priority over ordinary cells. The first layer of coding generates the guaranteed cells while the second layer produces enhancement (addoon) cells. Reconstruction of the picture is based primarily on high priority cells. When a loss mechanism is being examined from a buffer access prospective, it is commonly referred to as a space priority mechanism. This is due to the fact that this mechanism deals with priorities regarding the utilization of the buffer space. One bit in the ATM cell header was reserved to implement space priorities. Policing functions and buffer access mechanisms may use this bit to mark cells based on a negotiated contract for bandwidth allocation. Therefore, violating cells are marked as low priority and are rejected from entering the network when congestion occurs. Cell marking may be done either at the call level or at the cell level. Several space priority mechanisms have been proposed [20, 16, 25, 60, 71]. These schemes are variations of two basic priority mechanisms, which are described below. 2.2.2.1 The Push-Out Mechanism In this mechanism [20], cells enter one shared buffer up to the maximum buffer size. If a high priority cell arrives at a saturated buffer that contains low priority cells, a low priority cell is dropped and its place is given to the high priority cell. Despite its efficiency, push-out requires a complicated buffer management to preserve the sequencing of cells. 16 2.2.2.2 The NTCD Mechanism The Nested Threshold Cell Discarding (NTCD) mechanism [16, 25, 72, 40, 39, 60, 71, 12, 50, 59] was first introduced and analyzed by Garcia and Casals [16]. It is also known as the partial bufier sharing. Under N TCD (Fig. 2.1) the buffer is partitioned by a number of thresholds n that corresponds to the number of priority classes. Cells of priority class i enter the buffer up to threshold level T.-. If the buffer occupancy is above T,-, arriving cells of class i are dropped. NTCD results in a slightly less total admissible load compared to push-out [35]. The advantages of using this scheme for congestion control in the network are: 1. The N TCD mechanism combines good performance characteristics with a simple buffer management that can be implemented in hardware. 2. By adjusting the threshold values T,- (i = 1,...,n), the NTCD mechanism provides the flexibility to adapt an ATM node to different traffic mixes. Compared to other mechanisms, NTCD appears to be the best candidate for loss- based congestion control, as it provides a good compromise between performance and complexity. m. Incoming 8%\ 3113f ed Buffer Server W s | l ------- l l I 8 5 E _, __, __, Figure 2.1: Structure of N TCD with one buffer. 17 2.3 Analysis of Buffer Management Schemes Performance evaluation of buffer management schemes is essential to predict the over- all network performance and consequently provide guaranteed QoS requirements to all traffic Streams. It is also used for optimization and dimensioning of the network resources (i.e., buffer space and bandwidth). Ideally, performance evaluation should be based on measurements taken directly from an actual fully-operating ATM net- work. Since a such network does not exist yet, two other approaches to performance evaluation have been used by network analysts. The first (and most common) ap— proach is based on a presumed traffic model that encapsulates some of the stochastic characteristics of the actual input stream(s). Such a model can be used in subsequent queueing analysis or simulations of buffers at ATM nodes. The second approach is based on traces of actual traffic streams. These traces can be used as traffic in- puts to simulations (i.e., trace-driven simulations). Indeed, this latter approach relies heavily on the availability of such traces. Whatever assumptions are used to charac- terize the arrival process of the traflic will have a significant impact on the predicted performance. Therefore, it is necessary when studying the performance of buffer man- agement schemes to use traffic models that capture the most important (with regard to queueing performance) characteristics of the actual traffic. Before describing some of the traffic models which have been used in the literature for the analysis of ATM networks, we briefly discuss one important feature of the traffic that has a significant impact on performance, namely traffic correlations. 2.3.1 Burstiness and Traffic Correlations The complexity of the trafic in B—ISDN is a natural consequence of integrating over a. single communication channel a diverse range of traffic sources (i.e., video, voice, and data) that significantly differ in their traffic patterns as well as their performance 18 requirements. This heterogeneous traffic mix can not be adequately approximated by a simple Poisson process [65]. Specifically, bursty traffic patterns generated by data sources and VBR real-time applications (e.g., compressed video and audio) exhibit certain degrees of correlations between arrivals that preclude the use of renewal pro— cesses to model these patterns, not to mention a Poisson process. Even if the traffic generated by a single source was approximated by a renewal process, the aggregate traffic of the superposition of several sources is a complex non-renewal process which is modulated (i.e., controlled) by the number of active sources at each instant [22]. Correlationsbetween arrivals have been found to cause a considerable degradation in the network performance (as measured by cell loss rate and delay jitter), which can not be predicted by a Poisson model. This situation was investigated in [65] for the case of multiplexed voice packets using the index of dispersion for intervals (IDI), and will be summarized by the following theorem. Theorem 1 Let {Xh h 2 1} be a sequence of interarrival times of a stationary arrival process that represents one voice source, and let 3;. = 5;, X.-. The IDI for a single trafi‘ic stream is the sequence {6‘2" 1: Z 1} defined by W = _V‘"'(Sk) = C2 + ii=1.i¢jC°”(Xia Xi) [E (5.»? k[E(X1)]’ ‘ k[E(X1)]2 ”“21 (2'1) c: = where Cov (X;, X,) is the covariance between X,- and Xj. For k > 1, of measures the cumulative covariance (normalized by the square mean) among 1: consecutive in- terarrival times in the traffic stream. Let cf", denote the IDI associated with the superposition process of n independent and identically distributed arrival processes. Then, 1:13:10 Cir; = CiI >> 1 (22) Proof: see [65]. D Note first that large values of oi, rather than individual covariances, are the cause for performance degradations; being represented in [65] by excessive packet delays 19 under heavy load. For a Poisson process, Ci = 1 for all k. In other words, the superposition process of a finite number of voice sources deviates asymptotically from a Poisson process. A similar result applies as well to video traffic. 2.3.2 Trafic Models in ATM Networks To capture the effect of correlations between cell arrivals in bursty streams and to accommodate the variability of arrival rates in VBR sources, a number of traffic models have been developed recently [33, 2, 52, 56, 22, 54, 46, 15]. These models have been used either as part of an analytical queueing model or to drive discrete- event simulations of buffer systems. In the following, we describe some of these models that are relevant to this research. 2.3.2.1 The MMPP Model The MMPP is a doubly stochastic Poisson process whose arrival rate is a random variable which is modulated (i.e., controlled) by the state of a continuous-time Markov chain [14]. A 2-state MMPP was used in [22] to approximate the aggregate arrival rate of several voice sources. Yegani [72] analyzed an MMPP / G / 1 / K queueing system which implements an NTCD mechanism with one buffer and a threshold. More complicated traffic mixes can be modeled using the superposition principle of MMPPs: “The superposition of two MMPP processes (with possibly difl'erent parameters) is another MMPP ( with expanded state space)” [14]. The major advantage of the MMPP model is that it captures some of the important correlations between cell arrivals, while remaining analytically tractable. However, and like any queueing approach, its computational complexity is proportional to the buffer size, which makes this model computationally impractical for systems with large buffers. The MMPP was mainly used to model voice and data traffic sources. It is still questionable whether it is an appropriate model for VBR video traffic. Modeling a heterogeneous traffic mix using 20 MMPP is also an open issue. 2.3.2.2 ON/OFF Models These models capture the alternating active / idle behavior of a typical data source. A voice source with a. silent detector can also be characterized using an ON / OF F model. In its basic form, an ON / OFF source alternates between burst (active) and silence (idle) periods. A burst consists of a random number of consecutive cells. For this reason, this model is- often referred to as packet-train model [30]. Commonly, the number of cells in a burst is assumed to follow a geometric distribution. No cell arrivals occur during idle periods. Some analytical results for the queuing performance of a statistical multiplexer with ON / OF F traffic inputs were reported in [64]. 2.3.2.3 Fluid Models In stochastic fluid models [2, 12, 13, 33, 52, 56, 51, 66, 67, 78], a traffic source is viewed as a stream of fluid which is characterized by a flow rate. The notion of discrete arrivals of individual packets is lost as packets are assumed to be infinitesimally small. The fluid approach has been found appropriate to model the trafic in high-speed ATM-based networks for several reasons [12]. First, the burst level of the trafic in ATM networks is well-captured in fluid models. Second, the granularity of the traffic, which resulted from the standardization of small fixed-length ATM cells along with high transmission speeds (in the order of hundreds of megabits and above), makes the impact of individual cells insignificant. This provides a strong justification for the separation of time scales, which is the basis of the fluid approach. Third, the computational complexity in fluid analysis is, unlike queueing analysis, independent of the buffer size, which makes the fluid approach particularly useful for systems with large buffers. The fluid approach was used in [12] to analyze a buffer that implements the N TCD scheme with one threshold. In [78], Zhang analyzed a two—buffer system with complete 21 preemptive priority for one buffer, i.e., the multiplexer dedicates up to its full capacity to the high priority buffer, with the low priority buffer being served only when the high priority buffer is empty. Other variations can be found in [67] and [51]. In its simplest from, a traffic source in the fluid approach alternates between ON (burst) and OFF (silence) periods whose durations are random with some probability distribution (often exponentially distributed). During ON periods, infinitesimally small units of information arrive at a constant rate, similar to the flow of liquid. ON periods (also OFF periods) are independent and identically distributed. For N independent voice sources (or ON / OFF sources, in general), the aggregate arrival process is modeled as an ( N +1)-state Markov-modulated fluid flow (MMFF) process, where each state represents the number of simultaneously active sources. In addition to modeling ON / OFF sources, a fluid model was also proposed to analyze VBR video traffic from video-phones [52]. Although the fluid analysis is tractable, its numerical solution has two major computational problems: one is the possibility of ‘state explosion’ resulting from a large state space, and the second is the inherent numerical instability that results when trying to obtain solutions for finite (or partitioned) buffers. In [66] a decomposition of the state space was proposed followed by a functional transformation, which solves the first of these problems for homogeneous sources. 2.3.2.4 Time-Series Models These models are particularly suitable for compressed video streams. The VBR out- put of a video compressor consists of a sequence of frames generated at a fixed rate (e.g., 30 frames/ sec in the NTSC standard). Therefore, inter-frame times are con- stant for the whole video stream. Because of the natural visual similarities between successive images in a typical video stream, frame sizes (within a range of consecutive frames) are highly correlated. Only scene changes (and other visual discontinuities) can cause an abrupt change in the frame size. The strong correlations in the VBR 22 sequence, along with the constant interarrival times between successive frames, sug- gest that VBR traffic streams can be adequately modeled using time-series analysis and, particularly, autoregressive models. The class of linear autoregressive models has the following general form: P Xn = a0 + Z a,X,,_,. + en, n > 0 (2.3) r=l where Xn can be the size of a frame or part of a frame such as a slice (horizontal strip in an image), and {en} is a sequence of iid random variables, called the residuals, which are used to explain the randomness in the empirical data. Equation 2.3 describes an autoregressive model of order p, i.e., AR( p). In [52] an AR(I) model was used to approximate the frame size sequence taken from a video-phone that generates a VBR stream based on a conditional replenishment compression scheme. Although this model cannot capture accurately the behavior of many empirically observed video sources, its main advantage is simplicity. Higher order autoregressive models were used in [24, 23, 61] to match the first two moments and the autocorrelation function (acf) of a measured VBR stream. A sophisticated ARMA process was proposed in [21] to model the number of ATM cells generated by a video codec (coder / decoder). With the growing complexity of video compression schemes, more complicated models, such as Autoregressive Integrated Moving Average (ARIMA) processes [5], are being considered. Fractal ARIMA models were first used to characterize Ethernet traffic [48]. Later, these models were found appropriate for certain types of VBR video [17]. The use of ARIMA models, in general, was motivated by empirical evidence of non- stationarity (or near-non—stationarity) in the arrival process of VBR video streams [6]. A major disadvantage of a fractal ARIMA model is the large number of parameters that are needed to describe the model (i.e., the model is non-parsimonious). 23 2.3.2.5 The TES Model Correlated random variates can be generated using the Transform-Expand—Sample (TES) technique [54, 28, 29]. This technique is used to generate synthetic traf- fic streams to be used in trace-driven simulations. The main characteristic of this technique is that it captures both the marginal probability distribution and the au- tocorrelation structure of an arbitrary empirical record of data. For a given set of parameters, the acf of a TES-based stream has a closed-form analytical expression. Therefore, by systematically searching in the parameter space and numerically com- puting the resulting acf of the model, one is able to approximately match the acf of a given VBR sequence. The TES approach was used in [46] to evaluate the perfor- mance of a multiplexer whose input consists of a number of VBR video streams taken from an entertainment movie. A disadvantage of the TES model is that it requires the availability of the empirical data. It is not possible to use the parameters of the model that were obtained for a given trace to characterize other traces. Moreover, the TES model cannot capture negative correlations that are observed in MPEG streams. 2.4 The Proposed Buffer Management Scheme 2.4.1 Motivation Current research on priority mechanisms and buffer management in ATM nodes have been mostly concerned with priorities as a preventive approach to congestion control. Only few researchers addressed the role of priorities in providing QoS guarantees to communicating sessions. The common strategy to buffer management is to provide differential service to incoming cells based on the loss or delay requirements of these cells (but not both). While this strategy could possibly provide an acceptable perfor- mance for certain traffic mixes, it is not efficient under a diverse mix of traffic which requires various loss and delay performance guarantees. In such mixes, implementing 24 a loss-oriented or delay-oriented priority mechanism would underutilize the available resources (buffer storage or bandwidth capacity). To alleviate this problem, we propose a hybrid buffer management scheme that implements a mixed priority mechanism (i.e., based on both loss and delay priority queueing strategies). This scheme can efficiently support a diverse range of perfor- mance requirements to be expected in a multimedia high-speed networking environ- ment. The introduction of mixed priority mechanisms, in general, can be justified as follows: 1. End-to-end delay jitter has to be reduced for services that require rapid transfer of cells. 2. Loss-sensitive cells have stringent loss requirements which can not be met by the sole implementation of a delay priority mechanism. 3. To preserve the. cell sequence integrity, delay priorities should be assigned only on a call basis, whereas loss priority could be assigned on a cell basis. 4. Layer coding information may be used to simultaneously assign delay and loss priorities to cells in ATM networks. The proposed buffer management scheme will be evaluated using sufficiently accurate traffic models. Some of these models have already been used in the literature, such as the MMPP and fluid models. New traffic models will be developed to characterize the emerging VBR video streams from MPEG coders. Video traffic will be of particular interest to this research, as it will constitute the largest proportion of the overall traffic in the future B—ISDN / ATM networks. Once input sources have been accurately characterized, we use analysis and sim- ulations to optimize the buffer and bandwidth resources while satisfying the QoS requirements of several types of traffic. Optimizations of buffer resources include: (1) 25 determining the pr0per number of loss and delay priority classes, (2) dimensioning of the total buffer space, and (3) partitioning of each buffer among several classes of traffic (to be accommodated within that particular buffer). 2.4.2 The General Structure of the NTCD / MB Scheme To provide several levels of loss and delay performance guarantees for a heterogeneous mix of traffic sources arriving at an ATM node, we proposed a new buffer management scheme which is referred to as Nested Threshold Cell Discarding with Multiple Bufl'ers (NTCD / MB) [40, 39, 73]. This mechanism is based on mixed loss and delay priority queueing strategies. Delay priority is supported through the use of multiple buffers (one for each class of delay priorities). Loss priority is provided on a buffer-by-buffer basis using the conventional N TCD loss priority queueing scheme. NTCD was chosen over push-out (which has a slightly better performance than NTCD [35]) because of its simplicity that makes it attractive for implementation in the fast-switching ATM environment. In NTCD / MB an ATM cell arriving at a node enters one of several buffers, depending on the delay requirements of that cell. The number of buffers is the same as the number of delay levels to be supported by the network. Cells in a given buffer are guaranteed the same amount of delay performance (with possibly some of them experiencing less delay than the guaranteed level). An NTCD mechanism can be implemented in each buffer to provide cells in that buffer with different cell loss rates, depending on the loss priorities of these cells. An example of an NTCD/ MB mechanism which consists of n buffers with different number of thresholds in each buffer is shown in Figure 2.2. Note that the number of the thresholds and their values depend on the set of cell loss rates to be guaranteed by the network and the relative offered load from each class. Queues are served cyclically by a multiplexer whose capacity is divided unequally among the queues, favoring the ones with higher delay priority. The fractional capacities guaranteed for each buffer are determined 26 based on the actual values of delay levels to be supported by the network. The server is work-conserving which means that no service cycles are wasted waiting at an empty queue if another queue is not empty. T1“) Buffer 1 IT?) ITI‘” Buffer 2 T1“) I C Z (130 Multiplexer Buffer 3 To Link > anC 21.5") T5") T1") [ l l 03a,51fori=l,---an Buffer n E ai = 1 Figure 2.2: General structure of NTCD / MB. Chapter 3 Simulation Studies of NTCD / MB 3.1 Introduction In this chapter, we study the performance of NTCD/ MB via simulations. Three case studies were used to investigate three different forms of NTCD / MB. In each case study, the input traffic consists of two general types: real-time (RT) traffic and nonreal-time (N RT) traffic. RT traffic consists of a number of voice sources while NRT traffic consists of a number of data sources. Clearly, voice traffic is more sensitive to cell delay than data traffic. Hence, two classes of delay priority are associated with RT and N RT traffic types. In the first case study, we additionally assume that RT traffic consists of two types of cells: loss sensitive cells, which we refer as real high (RH) (or class 1) and cells that are less sensitive to loss, which we refer as real low (RL) (or class 2). RH and RL cells are treated as two classes of loss priority cells. No such classes of loss priority are used in the second case study. The third study assumes that RT and N RT streams both contain cells of two loss requirements. The objectives of our simulations are to study the overall performance of NTCD/ MB, compare this performance with that of a single—buffer NTCD, and investigate the effect of the various parameters associated with N TCD / MB. 27 28 3.2 Case Study I: Two Buffers and One Threshold 3.2.1 The Mechanism In this case study, RT trafic (i.e., voice) consists of RH and RL cells. To support two classes of delay priority (RT and NRT), a two-buffer NTCD / MB is needed. Ad- ditionally, a threshold is required in one of the buffers to support the two classes of loss priority within RT traffic. NRT cells enter one buffer, denoted by BNR (of size Bl), while RT cells enter another buffer, denoted by BR (of size 32). Since RT cells have two loss requirements, BR implements an NTCD mechanism with a threshold T (0 S T S 82) which represents the amount of buffer space shared by RH and RL cells. If a RL cell arrives at some instant when the content of BR is above T, it is discarded. An arriving RH cell is discarded only if the content of BR was Bg. The size of BR is naturally smaller than that of BNR, and is determined by the maxi- mum queueing delay requirements of RT cells. For the present case, the structure of NTCD/ MB takes the form shown in Figure 3.1. NRT Traffic D t S ( a 8‘ wees) > Buffer 1 (BNR) I Z (1 - 7) 0 __C RT Traffic (RH + RL) (Voice Sources) Buffer 2 (BR) T , 2 70 T Figure 3.1: Structure of NTCD / MB mechanism. Both buffers are served by a multiplexer whose capacity, C, is divided such that a fraction of the capacity '70 (where 0 S 7 S 1) is guaranteed for BR, while (1 — 7)C is guaranteed for BN R. If the service discipline divides the cycles equally between the 29 two buffers, then the cell loss rate for RT traffic will degrade because of the small size of BR. A better approach is to serve a maximum of a RT cells followed by a maximum of B NRT cells (with a > B) such that 7 2 0%. The server is work-conserving so that if the trafic in one buffer does not completely utilize its reserved fraction of the capacity, the residual capacity is made available to the traffic in the other buffer. The selection of a specific service discipline defines the interaction between the two buffers, and can be used to facilitate the adaptation of the node to different QoS requirements. 3.2.2 Traffic Description The packet stream from a voice source alternates between talkspurts and silence periods. During a talkspurt, cells arrive at fixed intervals. It is reasonable to assume that talkspurts and silence periods form an alternating renewal process. Nevertheless, the aggregate traffic (i.e., the superposition of a finite number of voice sources) is a complex non-renewal arrival process that possesses correlations between arrivals and fluctuations in the arrival rate. Recent studies indicated that such a trafic can be adequately characterized by a 2-state MMPP model [22, 65]. Hence, we model the aggregate RT traffic by a 2-state MMPP (denoted by MMPPr). Similarly, the aggregate N RT traffic is modeled as a 2-state MMPP (denoted by MMPP“). Using the MMPP model for both types of traffic is justified by the fact that voice and data streams are alike in their alternating ON / OFF behavior (of course, they differ in the distributions of the ON and OFF periods). An MMPP, in general, is characterized by a generator matrix R and a correspond- ing arrival rate matrix A. Let the generator matrix and the arrival rate matrix for MMPP, be —vr1 v71 A1 0 R, = , A, = (3.1) 2 12,, —v,.2 0 A, 30 where v... is the inverse of the average sojourn time in state i for the Markov chain of MMPP,, and [\f. is the total arrival rate when MMPP, is in state i (i = 1,2). Then, A: = 2 (Ai), (3.2) k where (hi),c is the arrival rate of class It real-time cells when MMPP, is in state i (here I: = 1, 2). Similar expressions are used to characterize MMPPfl by replacing the index r in (3.1) and (3.2) with the index 12. 3.2.3 Simulation Results Simulations of the underlying buffer system were conducted using a CSIM program‘. The following parameters were used [40]: o Deterministic service time which is equal to the transmission time of a cell. c Inverse average sojourn times for the Markov chain in MMPP, are or, = 0.01, v,.2 = 0.03. Likewise, on, = 0.04, and v"2 = 0.01 for MMPP... The stationary probability vector for the Markov chain of MMPP, is defined by2 Ur; + Ur; vrl + vrg 71’,- = lflri "rel = (33) o The real-time traffic consists of two classes of cells with arrival rates (Ai)high and (ADM), where i, j E {1, 2}, depending on the phase of the process.2 The load ratio for MMPP, is defined as 5 = (ADM-9h / (Ai) law, where i can be 1 or 2. This says that both classes of RT traffic are modulated by the same Markov chain (thus, 6 remains constant throughout the alternating phases of the chain). 0 The server discipline is implemented with a = 2, and B = 1. 1CSIM is a C—based discrete-event simulation language. 2Similar definition applies for MMPP" with subscript r replaced by n. 31 The first experiment demonstrates the performance of NTCD / MB using different values for the total offered load, pm, and BI = 40, B; = 6, T = 4, .f = 0.3, and burstiness levels r, = 1.2, 7“,, = 2.6 (the burstiness level is defined here as the ratio of the maximum arrival rate to the average arrival rate). Figure 3.2 shows the loss probabilities for RL and NRT cells at various pm. The total offered load is varied by either varying RT traffic load p, and fixing NRT traffic load at [In = 0.38, or vice versa (with p, = 0.44). Increasing p,, and therefore pm, results in higher cell loss rates for both types of traffic. Figure 3.3 illustrates the average response time of the system for both types of traffic. It is obvious that using NTCD / MB, RT cells of both classes experience a much smaller delay than NRT cells. From Figure 3.2 the cell loss rate of RT cells is slightly affected by increasing p... Notice that ,0, has more impact on the performance of NRT traffic than the impact of pn on RT traffic. 0.1 , r , 1 VT. 1 I ' RL (constant NRT load)-0-' NRT (constant NRT load) 4*" RL (constant RT load)-Bul NRT (constant RT load) -x-—~ Ayn-i- f' " 0.01 ,- 1 = I 3 l .d H q.‘ 1 .O a 8 0.001 .- 1 H ' 1 m a (D o a 0.0001 F 1 18-05 1 l J l l l 0.7 0.75 0.8 0.85 0.9 0.95 1 1.05 Total Offered Load Figure 3.2: Loss probabilities versus total load using NTCD / MB. 32 100 _ . ml (constant? NRT load)“.- RL (constant NRT load) ~P~ NRT (constant NRT load) '8'" RH (constant RT load) 49* RL (constant RT load) 4"- NRT (constant RT load) 4*“ ,La 10' Response Time (5 lots) 0.7 0.75 0.8 0.85 0.9 0.95 1 1.05 Total Offered Load Figure 3.3: Average response time versus total offered load under NTCD / MB. The previous simulations were repeated for a shared-buffer NTCD with buffer size B = 81 + 82. Figure 3.4 shows the average response times at various offered loads (either p, or pa was varied). Apparently, NTCD does not distinguish between the two types of traffic with regard to delay performance. The loss probability of RL cells is shown in Figure 3.5 for different RT and NRT loads, using NTCD and NTCD/MB. In particular, the figure shows that in NTCD/ MB the change in NRT traffic load has a very slight effect on the perfor- mance of RT cells. The effect of the threshold (T) of BR in N TCD/ MB is shown in Figure 3.6 using Bl = 40, B; = 6, and pm = 0.82. As expected, increasing T improves the performance for RL cells. Note that T has no effect on the loss rate of N RT cells. The response time of the system for the same experiment is shown in Figure 3.7. The choice of a particular value for T does not affect the queueing delay of cells from both types of traffic. Therefore, the value of T can be adjusted to 33 100 1 RH. l r l r l R1. +~ < NRT-8" J fvfivvvv ‘3 3 ~ . H m 2 :1 1°? 1 o i ' 0‘) ' . c , . O Q F C U) o a: F r I 1 J l M 1 4 l 0.7 0.75 0.8 0.35 0.9 0.95 1 1.05 Total Offered Load Figure 3.4: Average response time versus total offered load under N TCD. 0.1 . ; NTCD/H (constanthRT load)I +— U I 1 ; NTCD (constant NRT load) +-- 1 1 NTCD/MB (constant RT load) -8°-- . b NTCD (constant RT load) *- ] 0.01 ':' 1 i 1 >1 . ‘ U , 1 q-t H .4 l ’ .o a 3 0.001 f 1 H 1 o. i . 3 I . o > .2 F I 0.0001 f ‘- r 1 L a f N 1e-05 1 l l Jn l l 0.7 0.75 0.8 0.85 0 9 0.95 1 1.05 Total Offered Load Figure 3.5: Loss probabilities versus total load for RL cells. 34 0 l: n I I l I I . I RL-O—: * NRT -i-~--I 0.01% 1 I I I . >0 t 1 .13 > 4 H .o-l ’ 1 .Q 6 '8 0.001 .— 1 LI ‘ . m C I m C 00 0 s3 """ .— 4 a 1 1 0.0001 7 * """ - I b le-os L M l I L 1 2 3 4 5 6 7 Threshold T Figure 3.6: Loss probabilities versus threshold using NTCD / MB. provide certain loss performance for RL cells independent of the delay performance experienced by these cells. The effect of the size of BNR is shown in Figure 3.8 using pm = 0.82 (p, = 0.44 and pn = 0.38), B; = 6, and T = 4. It is clear that the loss performance for NRT traffic depends strongly on the value of 8;, whereas the loss rate for RT trafic is almost independent of 8;. Finally, the effect of the load ratio of RT traffic on the performance is shown in Figure 3.9. This is for pm = 0.9, p, = 0.52, pn = 0.38, B; = 40, B; = 6, and T = 4. Increasing 6 tends to degrade the performance for both classes of RT cells. Obviously, the effect is more severe with RH cells because high load ratio means that larger proportion of RH cells are to be accommodated in the buffer. Therefore, more of these cells will arrive at a saturated buffer and be dropped. The loss rate of NRT cells is not affected by the load ratio of RT traffic. Response Time (slots) Loss Probability 35 1.0 I I I ”I I I 8 - _____ a. .............. G """""""" ‘El‘ """"""" '6 .. .‘T-B .......... Ef"'.. 6 ' - RH 4*— IKI. ‘+"' IIIIT‘ 'E3--- 4 r - 2 I- .I 0 l l 1 1 1 l 0 1 2 5 6 7 3 4 Threshold T Figure 3.7: Average response time versus threshold using NTCD / MB. 0 .(ll. . I I 1’ I I 1 : + . ' RL -0— . - "x NRT +-- l P \‘\ ‘ ‘\ r ‘~,‘ “ \‘\ 0. 001 ,- .. I \ : n ‘ q I \‘ 1 ’ 'v‘ 3 ¢ 3 f q 4; 4v? vv“ fig 9 ‘v‘ ‘ . ‘h‘.‘ d F “+s‘ J P \ < - s‘ 4 D \ d h ‘\\ 1 b “ ‘ h ‘\ \\ \ b “ q \ 'k \x 18" o 5 I.- ‘\\ 1 I ‘ I \ \ ‘ C \ ‘ I \ \ \ . a. 1e-06 J l l L l 10 20 30 40 SO 60 70 Figure 3.8: Size of Nonreal Buffer NBR Loss probabilities versus the size of BNR using NTCD / MB. 0.001_ 0.0001 _ L L] Loss Probability 1e-OS , 1e-06 r 1e—07 ‘ 4 * ‘rx L1.1 ‘ ‘ ‘ ‘ ““‘J ‘ ‘ ‘ ‘ ‘ 11. 0.1 1 10 100 Load Ratio Figure 3.9: Loss probabilities versus RT load ratio using NTCD / MB. 3.3 Case Study II: Two Buffers and No Thresholds 3.3.1 The Mechanism In the early implementations of integrated voice/ data networks (i.e., ISDN), voice traffic was often given a complete non-preemptive priority over data [68]. Such a design can be formulated as a special case of the NTCD/ MB mechanism [73]. As before, two buffers, BR and BN R, are used to accommodate RT (voice) and NRT (data) traffic types. RT does not have multiple classes of loss priority, so there is no need to implement a threshold-discarding mechanism. The structure for this particular NTCD/ MB is shown in Figure 3.10. Notice that in this case cells in BR have a complete scheduling priority over cells in BNR. Therefore, RT traffic can use up to the full bandwidth capacity, if needed (since a non-preemptive priority is assumed, RT traffic may experience a service rate which 37 NRT Traffic D t S ( a a ources) ; Buffer 1 (BNR) . Z 0 _2 RT Traffic (Voice Sources) A Buffer 2 (BR) , , m C Figure 3.10: Structure of NTCD/ MB in Case Study II. is slightly smaller than C). Cells in BNR are served only when BR is empty, i.e., BNR is not guaranteed any amount of bandwidth (this is indicated by the “_>_ 0” notation). Despite the popularity of such a configuration, it fails to provide any performance guarantees to data traffic (which is needed in certain cases). Nonetheless, we would like to study the performance of this configuration and compare it to that of a single- buffer NTCD (Figure 3.11). When using a single-buffer NTCD, we assume that RT traffic has a higher priority than NRT, and this priority is supported using a threshold. Notice that no distinction is being made between loss and delay priority types in the case of a singlebuffer NTCD. N RT Traffic (low priority) (Data Sources) \ Shared Buffer ‘i / , RT Traffic (high priority) l (Voice Sources) T Figure 3.11: Structure of a single-buffer NTCD in Case Study II. 38 3.3.2 Trafic Description As before, RT traffic consists of the superposition of several voice sources. In this case, we assume that each voice stream is modeled using a 2-state MMPP with average --1 7! sojourn times 2) and 22,721 for states 1 and 2, respectively. State 1 represents the active period (i.e., talkspurt) in the stream, while state 2 represents the idle period (i.e., silence). As indicated by empirical results [22], appropriate values for the average sojourn times are: val = 352 msec and 12:21 = 650 msec. The average arrival rates in state 1 and 2 are, respectively, A? = 32kbps (based on ADPCM coding) and A} = 0. We model the aggregate NRT traffic as a Poisson process with average arrival rate A... Characterizing data traffic using a Poisson process has been justified in [22]. Such an assumption is only valid when the number of data sources is very large. Therefore, their superposition tends to a Poisson process. Notice that the model used for RT traffic in this case study is different from the one used in Case Study I in which the aggregate voice traffic (i.e., the superposition of several voice sources) was modeled by a 2—state MMPP. The rationale for modeling each voice stream using a 2—state MMPP in the present study is related to an im- portant property of the MMPP, namely the superposition principle for MMPPs [14] (see Section 2.3.2.1). When each voice stream is modeled using a 2-state MMPP, the aggregate voice traffic is another MMPP with expanded state space (the number of states for this MMPP is twice the number of superposed voice streams). To avoid a state explosion situation, we let RT traffic consist of 2 voice sources only. 3.3.3 Simulation Results In this section, we present simulation results for the NTCD and NTCD / MB mecha- nisms. The time unit chosen is 352 msec, which corresponds to the average duration of an ON period in a voice source. The total output capacity (C) is adjusted to attain 39 the desired level of utilization. Because of the complete priority given to BR in the examined NTCD / MB, BNR should always be designed with a larger size than BR. In all experiments, the size of BR is 30 cells and the size of BNR is 50 cells. Let p, and pn denote the RT and NRT offered loads, respectively. When using a single-buffer NTCD, it is assumed that RT has higher priority over N RT traffic. Thus, NRT cells can be admitted as long as the content of the shared buffer is below the threshold level T. Three values for T were used: 25%, 50%, and 75% of B (the total size of the shared buffer), where B = 81 + B; = 80 cells. It is shown that the performance for both types of traffic is significantly affected by the value of T. The performance of both mechanisms was observed in terms of the cell loss rate and average cell delay (queueing time plus service time). Simulation run times were selected so that the traffic with the smallest loss probability loses at least 100 cells. Otherwise, the results could be inaccurate. More intense simulations were run for particular experiments to confirm the correctness of the results. In all the experi- ments, the traffic intensities, p, and pn, were varied. When p, is varied, pn is held constant at 0.4, and vice versa. In Figures 3.12 and 3.13, p, is varied. Figure 3.12 shows the loss probability for NRT cells versus offered load based on NTCD / MB and also NTCD (with three values for T). For pm 2 0.7 (pm 3— p, + pn), the performance of NTCD / MB lies between the performance of NTCD with T = 40 (in cells) and the performance of NTCD with T = 60. For pm < 0.7, the performance (in terms of cell loss) of NTCD/ MB becomes worse than both cases. As expected, NTCD with the highest T (i.e., T = 60) provides the best performance for NRT traffic. The loss rate of RT cells in the same experiment is depicted in Figure 3.13. Observe that NTCD / MB has the worst relative performanCe (compared to NTCD using three different threshold values) under heavy load and next to best performance under light load. Also, the smaller the threshold in NTCD, the better the performance experienced by RT cells. Probability LOSS 1e+00 . le-Ol le-OZ 1e-03 1e-04 1e-05 1e-06 40 I T T I l r I I _. i i r 1 ’ l r d r NTCD/MB -F-'1 - “ NTCD,T=20 9#- - _ NTCD,T=4O 4F— 1 _ NTCD,T=60 ak- F 1 L I I I l l l l I .55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 Total Offered Load Figure 3.12: Cell loss probability for NRT traffic versus pm (p, is varied). Probability Loss 1e-01 . I I I I I I I 1 1e-02 r 1 i 1e-03 f - l . 1e-04 r 1 1e-05 r 1 L . 1e-06 r j" NTCD/MB -I— -. ' NTCD,T=20 9+—'l - NTCD,T=40 4*— - 1e—O7 r NTCD,T=60 iF—‘1 1e-08 ’ I I I 14 I J I I 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 Total Offered Load Figure 3.13: Cell loss probability for RT traffic versus pm (p, is varied). 41 The same set of experiments were repeated with p,, varied and p, = 0.4. Cell loss rates for RT and NRT traffic are depicted in Figures 3.14 and 3.15, respectively. In Figure 3.14, the same behavior as in Figure 3.12 is observed except for the perfor- mance of NTCD / MB under light load. Here, NTCD / MB had the best performance. It is observed that when using NTCD/ MB, the cell loss rate for the RT traffic is independent of pn. Although it has a worse performance than NTCD in this case, N TCD / MB can be used to dimension the buffer space by allowing the size of BR to be chosen based on the requirements of real-time traffic only. Average delay of a cell in the previous experiments is shown in Figures 3.16 and 3.17 (with p, being varied and p" = 0.4), and in Figures 3.18 and 3.19 (with pa being varied and p, = 0.4). Figure 3.16 shows the average waiting time in the system for a NRT cell. NTCD / MB results in the longest waiting time among the four cases. This is acceptable since NRT traffic is not delay—sensitive. In contrast, the delay performance experienced by RT cells (Figure 3.17) is the best when using NTCD / MB. In this case, delay is a significant performance measure. Note that for N TCD the larger the value of the threshold the longer is the waiting time. Similar conclusions can be drawn from Figures 3.18 and 3.19 when pn is varied and p, = 0.4. 3.4 CaSe Study III: Two Buffers and Two Thresh- olds 3.4.1 The Mechanism It is possible that both voice and data sources contain cells with two loss requirements. In this case, NRT would consist of nonreal high (NH) cells and nonreal low (NL) cells. RT traffic consists, as in Case Study 1, of RL and RH cells. To support the requirements of such a traffic mix, an NTCD / MB with two buffers is needed. Probability Loss 42 1e+00 E I I I I F F l l 1 ” i le-Ol f i 1e-02 ; F t le—03 g I 1e_04 l l 1 l I I I l 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 Total Offered Load Figure 3.14: Cell loss probability for NRT traffic versus ptot (pn is varied). Probability Loss 1e-02 I F H l I T .1 T 1 le-04 E 1 1e-05 r NTCD/MB -t—': ~ NTCD,T=20 49— - _ NTCD,T=40 4*- , 1e—06 r NTCD,T=60'dP-1 1e-07 r 1 1e-08 . I LEI I 41 I I I I d 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 Total Offered Load Figure 3.15: Cell loss probability for RT traffic versus pm (pn is varied). 43 1-3 I I I I I T I I 1.6 ' NTCD/MB —F— ‘ NTCD,T=20 99— 0 1.4 - NTCD,T=40 4— J E NTCD,T=60 *— E" 1.2 ' a i G '3 1 - - '3 3 o 8 F .. 2"; H 0.6 P -' g ‘3 0.4 i" - 0.2 ' - /- 0 MIL I I I I I 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 Total Offered Load Figure 3.16: Average waiting time of a NRT cell versus pm (p, is varied). 1.2 14* I I 4, I r’ .j I NTCD/MB —F— NTCD,T=20 99— 1 ' NTCD,T=40 4— " g NTCD,T=60'fiF— .,..; K E‘ 0.8 - a U) G -H ti .6 O 6 ' ‘ 3 d) 3 H 0.4 - r 3 d 0.2 - 4 0 “ i l L SJ I I I 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 Total Offered Load Figure 3.17: Average waiting time of a RT cell versus pm (p, is varied). 44 Average Waiting Time 1 0 l l M l L L l J 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 Total Offered Load Figure 3.18: Average waiting time of a NRT cell versus pm (pn is varied). 0.8 I i I F Total Offered Load I —I I I NTCD/MB -F— 0.7 - NTCD,T=20 ee- _ NTCD,T=40 4*— ,” NTCD,T=60 *— E 0.6 r 0H e L. g 0.5 -H 11 .0 0 4 '" ‘ 3 5’: 0.3 - .. o it 3, 0.2 - -[ 0.1 — f L vlr f —+ — 0 l L l L 1 I L I 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 Figure 3.19: Average waiting time of a RT cell versus pm (pn is varied). 45 NRT Traffic (NH + NL) D t S ( a a Olll‘CCS) > Buffer 1 (BNR) ‘ Z 0 if C Tn RT Traffic (RH + RL) (Voice Sources) Buffer 2 (BR) > A z C Tr Figure 3.20: Structure of NTCD/ MB in Case Study III. Each buffer implements an NTCD with one threshold, as shown in Figure 3.20. The thresholds are denoted by Tu and T, for BNR and BR, respectively. As in Case Study II, the scheduling discipline of the server provides complete priority to BR. 3.4.2 Traffic Description The same traffic models in Case Study II were used to characterize RT and N RT traffic types (i.e., each voice source is a 2-state MMPP and the aggregate data traffic is a Poisson process). Let {r and 6,, be the load ratios for RT and NRT traffic, respectively. For each type of traffic, the load ratio is defined by the fraction of high priority cells among all cells of that type. We assume that RT traffic consists of two voice sources (parameters of the MMPPs are given in the previous case study). 3.4.3 Simulation Results We investigated the effect of the offered load of both RT and NRT traffic types, the threshold of BR (T,), and the load ratio for RT traffic (6,). As before, the total offered load pm is varied by varying p, and keeping pfl constant, and vice versa. In all the 46 results below, the sizes of the buffers (in cells) were kept at Bl = 40 and 32 = 25. In Figure 3.21, the cell loss rates for the various classes of traffic are shown as a function of pm which is varied by varying p, (pa = 0.4). The other parameters are: T, = 20 (in cells), Ta = 30, g, = 0.4, and 5,, = 0.2. The trend in each of the performance curves'is expected. Clearly, increasing p, will result in higher loss rates of RH and RL cells. Since BR has a complete scheduling priority over BN R, the increase in p, decreases the chances that BR is empty, thus increasing the probability of overflow at BN R. Varying pm via pn (with p, = 0.4) shows different trends (Figure 3.22). RT cells (both RH and RL) are not affected by the NRT traffic load. This is useful in guaranteeing the performance for RT traffic. The increase in loss probability as a function of pm is faster for NH cells. In general, one should expect loss probability curves to increase slowly when the loss probability is relatively large (say, above 10”). This means that the performance experienced by NL cells is less sensitive to traffic variations than that of NH cells. 1e+00 . t RHr-O— I I l 1 I : - RL *— x- ......... -x 16-01 V NH ‘0'" ......... x ————————— _. - 4 18-02 :- d 1% 19-03 :- 1 a r . ’ 'l % 19-04 E- 1 8 ' . —| . . 19-05 C 1 19-06 :- 1 L . 16'07 l I l l l l 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 Total Offered Load Figure 3.21: Cell loss rate versus pm in Case Study III (p, is varied). 16+00 F RHI I I r I I q _ +— . - .51: + . _ -°--- .............. x _ 1e-O1 : NL -x--- ...... *_,,.-.-.-.x ...... x : .—-—X"" L x ----- g 16-02E- X— 4* x x ....... “a: ...... :2 - «‘6 l .«s """""" ° . ‘3 19-03 - .7 - a : ........ ' : m 0' In . . o -‘ 1e-O4 :- 1 L . 16-05 r M 1 r v c c - 1e-m I. I l l l l I .1 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 Total Offered Load Figure 3.22: Cell loss rate versus pm in Case Study III (p, is varied). Figure 3.23 depicts the cell loss probability versus T, using T, = 30, 6, = 0.4, f, = 0.2, p, = 0.6, and p, = 0.25 (thus, pm = 0.85). The effect of T, on RH traffic is quite drastic. Intuitively, we expected that increasing T, would decrease the cell loss rate of RL cells and increase that of RH cells. As shown in Figure 3.23, the loss rate of RL cells slowly decreases with T,. This, again, can be justified by the relatively high loss rates of RL, which makes the performance for that traffic less sensitive to variations in the values of the parameters of NTCD / MB. The depicted figures are useful when dimensioning and partitioning the buffers to attain certain levels of cell loss performance. Observe that NRT traffic is slightly affected by T,. The effect of the load ratio of RT traffic (5,) is investigated in Figure 3.24. Results shown in the figure were obtained using T, = 20, T,. = 30, {n = 0.2, and pm = 0.85 (p, = 0.6 and p, = 0.25). Increasing 5, causes a rapid increase in the cell loss rate for RH traffic. RL, NH, and NL trafic types are very insensitive to 5,. Loss Probability Loss Probability 19+00 1 9-01 19-02 1 9-03 19-04 1 9-05 19-06 1 9-07 Figure 3.23: Cell loss rate versus threshold of BR in Case Study III. 19-05 19-06 1 9-07 V'lj rrI I r" I J l l L J l l 12 14 16 18 20 22 24 Threshold of BR (Tr) 26 '1' I Itr I' 'l V TT II I I l l I III I IJL l 0.2 0.4 0.6 0.8 Load Ratio of Real-Time Traffic Figure 3.24: Cell loss rate versus RT load ratio in Case Study III. Chapter 4 Fluid Analysis of NTCD / MB 4.1 Introduction The use of simulations for performance evaluation of buffers systems becomes com— putationally prohibitive when the desired loss rates are below 10'6. In an ATM network, some traffic streams require an end-to-end cell loss performance in the order of 10"”. In such cases, performance evaluation must rely on analytical techniques to predict the performance. Most of these techniques are based on queueing analysis in which the arrival process of a traffic stream is modeled as a point process with certain stochastic characteristics. A different approach for traffic modeling, which is adopted in this chapter, is based on stochastic fluid models [2, 33, 56]. In this approach, a traffic source ,say an ON / OF F source, is viewed as a fluid stream with random arrival rate (the flow rate). The notion of discrete arriVals of individual packets is lost as packets are assumed to be infinitesimally small. Consider, for example, the ON / OFF traffic stream depicted in Figure 4.1. Such a stream represents the behavior of a data or a voice source (with silent detectors) transmitted over a line of constant bit rate. The fluid representation for this stream is shown in part (c) of Figure 4.1. 49 50 cell |< silencet‘e- burst —-’| (a) Actual Stream .222: Hi i llllll 22...... fl Figure 4.1: Point process and fluid representations of an ON / OFF traffic source. The fluid approach has been found particularly appropriate to model traffic streams in high-speed ATM-based networks for a number of reasons [12]. First, this approach captures the bursty nature of traffic sources in ATM networks. Second, the standardization of small fixed-size ATM cells along with high transmission speeds (in the order of hundreds of megabits and above) makes the impact of individual cell arrivals insignificant. This provides a strong justification for the separation of time scales which is the basis of the fluid approach. Third, the computational complexity involved in fluid analysis is, unlike queueing analysis, independent of the buffer size. In the following sections, we provide a complete fluid analysis for one particular form of NTCD / MB that was used in Case Study I of Chapter 3. This form is shown again in Figure 4.2. We use fluid analysis to derive the probability distributions for the content of each buffer, the cell loss probabilities, throughputs for each type of traffic, and approximate waiting time distributions [36, 41]. The results can be extended to any other form of NTCD / MB in a straightforward manner. We chose to analyze the scheme in Figure 4.2 because it contains all the main components of a general NTCD / MB: multiple buffers, thresholds, fractional guaranteed service rates, 51 NRT Traffic D t S ( a a ources) > Buffer l (BNR) 2(1" 7) C _C RT Traffic (RH + RL) (Voice Sources) Buffer 2 (BR) T Figure 4.2: Structure of NTCD/ MB mechanism. and a work-conserving service discipline. Elwalid and Mitra [12] analyzed a single—buffer NTCD scheme with one threshold. In [78], Zhang analyzed a two-buffer system in which complete preemptive priority is given to one buffer, i.e., the multiplexer dedicates up to its full capacity to the high priority buffer, with the low priority buffer served only when the high priority buffer is empty (this scheme is shown in Figure 3.10). The particular significance of our analysis is that it does not assume a preemptive priority to any of the bufl'ers analyzed; it guarantees a fractional capacity to each bufl'er, which can be used to provide performance guarantees; and it assumes a work-conserving service discipline. Such extensions are by no means trivial, as they imply dependency between the contents of the two buffers. Our approach is based on obtaining the conditional probability distribution for each buffer given the content of the other buffer, then solving for the unconditional probability distributions. 4.2 Trafiic Description As in Case Study I of Chapter 3, we assume a trafic mix which consists of two general types of traffic: RT and NRT where, as before, RT traffic consists of two classes of 52 priority cells: RH and RL. The analysis to be presented is valid for a general traf- fic source whose arrival process can be modeled by a Markov modulated fluid flow (MMFF) process. NRT traffic represents Nd number of data sources, while RT traffic represents NW voice sources. Video traffic can be incorporated in the analysis using the fluid model for video traffic which was proposed by Maglaris et al. [52] (we will discuss this issue further in Section 4.8). However, such a model is applicable only to a video stream from a video-phone, using the conditional replenishment compression algorithm. It is very unlikely that this model can capture the dynamics of compressed streams from video movies, or even the dynamics of a video-phone stream which is compressed based on a compression algorithm other than the conditional replenish- ment technique. Characterization of video traffic is investigated in Chapter 5 of this thesis. Each data or voice source is characterized using the fluid representation of an ON / OFF stream. ON and OFF periods are exponentially distributed with respective average durations p51 and r;1 for a data source, and pg and r301 for a voice source. During ON periods, cells arrive at a constant rate of ad for a data source, and aw for a voice source. Each voice source contains two classes of traffic: RH and RL. Except for a multiplying constant (i.e., the load ratio), the instantaneous arrival rates for the two classes are the same (i.e., the two classes are modulated using the same Markov chain). For convenience, we will frequently use the subscripts 1 and 2 to refer to quantities associated with BNR and BR, respectively. Let Sd(t) denote the state of the arrival process (i.e., number of data sources that are simultaneously ON) at BNR at time t. Then, Sd(t) 6 {0,1, . . . , Nd}. The total arrival rate of NRT traffic when Sd(t) = i is Ad(i) = iad. A transition from state i to state i + 1 occurs when one idle data source goes ON. Since data sources are independent, and ON and OFF periods are exponentially distributed, such a transition will occur after a random time which has an exponential distribution with 53 rate (Nd — i)rd. In a similar fashion, a transition from state i to state i — 1 will occur after an exponentially distributed period with average rate ipd. Accordingly, the arrival process of the aggregate NRT traffic is Markovian with a transition diagram as shown in Figure 4.3. This arrival process is an (N; + 1)-state MMFF (Markov- modulated fluid flow) process [2]. Nd rd (Nd'l) rd (Nd-1) lid Figure 4.3: State transition diagram for a (N; + 1)-state MMFF. T Let H4 = [r30 rid) . . . age] be the stationary probability vector for the modulat— ,Nd). ing chain. It is known that H4 is a binomial distribution with parameters (r fly, The j ’th element of H4 is given by (d) A . . Nd rd j #d Nd-j 7r,- =,1_lgloPr{Sd(t) =J} = j ' rd+pd n+1,“ (4-1) The effective arrival rate of NRT traffic is X; = 2:,- Ad(j)7rJ(-d). Let Q; denote the generator matrix of the Markov chain. Then, “'7‘de 7'de 0 0 . . . 0 [1d —rd(Nd — 1) - pd rd(Nd — l) 0 - - - 0 Qt! = 0 2;” —Td(Nd - 2) - 211d Td(Nd — 2) 0 0 ’1de _#de- A similar description applies to RT traffic. Hence, the aggregate traffic of NW voice sources is described by a (NW + 1)-state MMFF with generator matrix Qvo and 54 equilibrium probability vector Hm, (defined similar to H4 and Qd). The aggregate arrival rate of RT traffic at state 5,0(t) = i (i = 0, 1, . . . , NW) is /\W(i) = iavo. Let f = A£(i)/z\w(i) denote the load ratio for RT traffic (AvHO(i) is the arrival rate of RH cells when the RT arrival process is in state i). Note that E is constant and does not depend on the state of the process. The combined total arrival rate of NRT and RT traffic can be described by a global K—state MMF F process, where K = (N; + 1)(Nvo + 1). At time t. the state of the Markov chain of this process is S'(t) é (Sd(t),S,,o(t)) E .C, where .C 2 {(i,j) : i = 0,1,. . . ,Nd, j = 0, 1,.. . ,Nvo}- The pairs in .C are ordered lexi- cographically. We say S'(t) = (i,j) = k where k = 1,2,...,K, to mean that the integer It represents the kth ordered pair in L. The global generator matrix Q and the stationary probability vector H for the global arrival process are given by: Q = QdEBQvO (4.2) II n. a 11.. =[1r17r2 221T (4.3) where for every global state k = (i, j) 6 .C, 7n. = iridbrj-w). The symbols “EB” and “(8)” above indicate the Kronecker sum and the Kronecker product, respectively. 4.3 The Conditional Equilibrium Distributions In this section, we provide the conditional equilibrium distributions for the contents of both buffers [41]. Let X1 (t) and X2(t) denote the instantaneous content of BNR and BR, respectively. In addition to the state of the arrival process, the drift rate at each buffer depends on the content of the other buffer and (for BR only) the threshold T. This dependency is caused by implementing a work-conserving service discipline. Accordingly, six cases (two for BNR and four for BR) were considered, as shown in Table 4.1. Note that the quantity dglUc) in the fourth column of Table 4.1 is the drift 55 rate dX;(t)/dt for the case l-a at some global state I: = (i, j) 6 L. Case # Buffer Condition Drift at S (t) = k = (i, j) l-a. BNR 0 < X1 < B] and X2 = 0 Jana?) = Ada) - C + min{7Ci Avo(j)} 1—b BNR o < X1 < B. and X: > 0 d§"(k) = Mi) — C(l - r) 2-a BR 0 < X; < T and X1 = 0 d£2)(k) = Am,(j) — C + min{(1-— 7)C’ 2.1) BR T < X2 < 32 and X1 = o d§2)(k) .—. 233,0“) - C' + min{(1- 7)c 2-c BR 0 < X; < T and X1 > 0 dglec) = Avo(j) — 7C 2—d BR T < X2 < 32 and X1 > o (13%) = Aflj) -— 70 Table 4.1: Cases used to obtain the conditional distributions. For each of the above cases, define a drift matrix pg) 2 diag {dg)(k) : k = (i, j) e r} (4.4) where l = 1,2, and a = a,b (ifl = 1), or a = a,b,c,d (ifl = 2). The elements along the diagonal of D3) are ordered lexicographically. At equilibrium, the steady-state conditional probability distributions are defined by Fg)(k,a:) 3 113510 Pr{S(t) = k, X1(t) S 1: /cond. of case l-a} (4.5) for all I and a. Let 179(3) be the column vector from {F glUc, x)}f___l. Using similar development to the one in [2], the system is governed by the following set of differential equations: (1) Dgii‘l—ng—(‘Q = QFg)(:c), for all z and a (4.6) For each I and or, (4.6) provides K linear differential equations. The solution for this system takes the following form: F2>=§3Ag>uwsm marrow} (4.7) i=0 56 where the set of pairs {(290), \I'g)(i)) : i=1,...,K} consists of the K eigenvalues-eigenvector solutions for the generalized eigenvalue problem zg’lu) 0929(2) = Q 149(2), Vi e L. (4.8) 4.4 Boundary Conditions To obtain the constants {119(2)}, 6 K boundary conditions are required. First, define the following sets of states: (JO) 0: {m E E : dg)(m) < 0} 03’ 2 {m€£ : dg>(m)>o} Note that My) (03)) represents the set of global states in E that cause an underload (overload) drift for the case l-a. The boundary conditions are: 9 Boundary conditions for BNR. F;1)(k,0) = 0 v k e 09) and a = a, b (4.9) F;I)(k, Bl) = 7:... v k 6 L19) and a = a, b (4.10) which provides 2 K equations that can be used to solve for {Ag1)(i)} where a = a, b. 0 Boundary conditions for BB. F;2)(k,0) = 0 W: e 053) and a = a, c (4.11) F§2)(k, B.) = 7:. v k e at?) and a = b, d (4.12) F§2>(k,T) = F5222, T) v k e a?) U0?) (4.13) F§2)(k,r) = Fj2)(k,T) Vkeu§2>U0§2) (4.14) 57 Equations (4.11) - (4.14) provide 4 K equations which are used to solve for {A£2)(i)}, where a = a, b, c,d. 4.5 The Unconditional Distributions In this section, we derive the (unconditional) equilibrium distribution for the content of each buffer, independent of the other buffer. Consider a countable mutually exclu- sive class of events {3;} that partitions an event A. Let Pr{Bg} > 0 for all i. By the law of total probability, Pr{A} = Z,- Pr{A/B,-} Pr{Bg}. We apply the same concept to find the steady-state distribution of the buffer contents. Let H(i,x) 2 3:30 Pr {5(2) = i, X1(t) g 3:} for o g a: < 191 (4.15) G1(i,a:) = 21311510 Pr {S(t) = i, X2(t) S 2:} for 0 S :I: < T (4.16) G2(i,a:) 3 211310 Pr {S(t) = i, X2(t) _<_ 2:} for T < a: < B2 (4.17) In the following, H(i,:c), G1(i,x) and G2(i,:z:) are to be found from F§’)(i,$). Consider first the nonreal-time buffer. Pr {5(t) = i, X1(t) S 2:} = Pr {3(t) = i, X1(t) S :1: / X2(t) = 0} - Pr {X2(t) = 0} + Pr{S(t) = i, X1(t) g 1: / X2(t) > 0} - Pr {X2(t) > 0} Hence, H(i,a:) = F§1>(i,2) - P1{X2 = 0} + F5”(i,:) . (1 — P:{X2 = 0}) (4.18) (note that the parameter t that indicates time is dropped to reflect asymptotic quan- tities). But K Pr{X. =0}=ZP1{S=J°,X2 =0} =ZGl(j,0) (4.19) .i i=1 58 Thus, H(i,:c) = [F§1)(:,:)— F(1)(z 2)] [2(a) (j,0 +F,“)(z',x) (4.20) j-l which is true for 0 S :c < BI, and for all i 6 L. Next consider BR. Pr{S=i,X2$a:} = Pr{S=i,ngx/X1=0}-PI{X1=O} +PI‘{S=Z, ngx/X1>0}-Pr{X1>0} Thus, forOSx(.-,0). [1— 2: Hum] ~ (4.23) '=1 Substituting G1(i,0) from (4.23) in (4.20) and evaluating at :c = 0, we have H030) = FJWLO) + [F.5"(z'.0) - Fl"(z',0)] f: {F100, 0) . + F90, 0) [1 — i H(p, 0)] }] (4.24) X K 217040) j=l p=l p=l This is a set of K linear equation of K unknowns; H (i,0), i E L, and can be easily solved. With H (i, 0) evaluated, G1(i, 0) can be obtained from (4.23), and thereafter, 59 H(i,:r) from (4.20). Also, G; (i,:z:) and G2(i,a:) can be found from (4.21) and (4.22), which completes the solution. 4.6 Performance Statistics Once the steady-state distributions for the content of BN R and BR are determined, it is straightforward to obtain the, throughput and loss probabilities for the various types of traffic. First, the following quantities are computed: Pr{S = i, BNR is full} = 7r,- — H(i, B.) Pr {S = i, BNR is empty} = H(i,0) Pr {5' = i, BR is full} = 7r.- — G2(i, Bz) Pr {5' = i, BR is empty} = Gl(i,0) Pr {5 = 2', X. = T} = G.(.',:r) -— G.(z’,T) The throughput for a given class of cells is the difference between the generation rate for that class and its loss rate. For N RT cells, the generation rate is 25;, A1(i)7r,-, where A1(i) is the arrival rate of NRT traffic when S = 2' (since i here is a global state, A; (i) = Ad(i modulo Nvo)). Loss rate for NRT cells is the positive drift rate into BN R when BN R is full. Therefore, K loss rate for nonreal cells = Z [A1(i) - max{(1 - '7)C, C — A2(i)}] - (7r.- — H(i, 8.)) i=1 where A2(i) is the arrival rate of RT traffic when S’ = i. (Again, this is the same as A... ( j ) where j is the second element in the ith tuple). Let T; denote the throughput for N RT cells, T2H and Tf’ denote the throughput for high and low priority RT cells, respectively. (Note that we will continue to use the letter T to denote the threshold 60 BR). Then, K K T. = zxmim- >3—ma.x{<1-:)C,c—Az(i)})(m~-H(i.Bl))] i=1 i=1 K K = 241(2)}! (i. 81) + 2(a- — H(i,Bl))-max{(1— .00, c — 2.0)} (4.25) i=1 i=1 K K T2H = Ziffim " Z (4510') " max {7C9 C — A10») (7': - G20} 32”] (4-26) i=1 i=1 where A? (i) = {A2(i). Low priority real-time (RL) cells are lost whenever X2 > T in which case all generated cells are lost, or when X; = T which results in a partial loss rate Ag(i) - max {70, C' — A1(i)}. Therefore, the throughput for RL cells is T: = throughput I X2>T +throughput |x,=T K K = {2: 22(2):,- — 2X51!) (7r.- — Gz(i,T))} _ { 2 (0.0, T) — G1(i,T))(A.(i) — max{7C, C — A.(z‘)})}4.27) 5505.2) fluff) In the expression above, 11; — Gg(i, T) is the probability of {X2 > T and S = i}. Also, A20 = (1422(4). Let L1 denote the loss probability for nonreal cells, L5! and L5’ denote the loss probability for high and low priority real cells, respectively. Then, T1 L = 1 — 4.28 1 2:1 7M1“) ( ) L” 1 T2” (4 29) 2 £1 7r,-,\¥(i) . LL — 1 — TZL (4 30) 2 — £1 MW) . In conventional fluid analysis, the distribution for the waiting time of a cell is readily obtained from the distribution for the buffer content. However, in the model consid- 61 ered, this is not trivial since the service rate for a given class of cells is not constant. For NRT cells, the service rate at state i E L is C1(i) = max{(1— 7)C, C — A2(i)} Similarly, the service rate for high and low priority real cells is C2(i) = max {7C, C — A1(i)} which, for both cases, is a function of the state i. An approximate expression for the waiting time distribution of cells can be obtained using average values of C1 and C2 given by _ K __ K C} = 2 01(2)”; and C2 = ZCz(i)7l’g (4.31) i=1 i=1 Let W1, W2”, and W2L denote the waiting time for a cell belonging to NRT, RH, and RL traffic types, respectively. Then, K mm. s t} z Ti}: A.(2)H(.’,F:It) for 0 g t s 13,/“CT (4.32) 1 i=1 —— CT K . Pr{Wl = 31/01} s — [1— [110,130] (4.33) T1 i=1 For high priority real-time cells, £1,235; Ag’(i)G.(i,C—§t) for 0 S t S T/Cz Pr{W.” s t} z $.25; 22(4) (G.(z',T) — G.(z‘,T)), for t = 17?. 5:132:2'1 /\£{(Z)G2(Z,—CT2—t), for 776 < t < 82/52 H — E K . Pr{W2 = B./C.} z T7 1 — Z G.(z,B.) (4.34) 2 {:1 Similar expressions can be obtained for low priority real-time cells. 62 4.7 Numerical Investigations 4.7 .1 Computational Considerations Numerical results were obtained for the analysis in the previous sections using a C pro- gram supported by Matlab library functions. Solutions for the eigenvalue / eigenvector sets were based on the decomposition technique developed in [66]. In this technique, an aggregate traffic that consists of several independent and separable rate-modulated input processes arriving at a buffer system is analyzed by decomposing the system into smaller subsystems to be treated separately. The final solution is then obtained by superposing the individual results. This approach considerably reduces the number of required computations. The other major numerical problem which we encountered is the numerical instability of the mathematical system. Such a problem is known to exist in fluid approximation of finite buffers [67]. The eigenvalues associated with such buffer systems can take positive as well as negative values. When solving for the constants {1139(2)}, the exponentiation of positive and negative terms produces a badly-scaled matrix whose values can be close to the precision of the machine. Typically, researchers have dealt with such problem by using the complementary in- finite buffer distribution as an approximation to the actual finite buffer case, since the former case does not produce positive eigenvalues. In our case, however, positive eigenvalues cannot be avoided because of the finite threshold (T). We used several scaling methods to condition the matrices involved. Row as well as column scaling were required using block diagonal matrices to obtain acceptable results. 4.7 .2 Numerical Results and Simulations Numerical examples based on the previous fluid analysis were used to study the effect of various parameters on the performance of NTCD / MB. Additionally, simulation experiments were conducted and their results compared to the analytical results. 63 In these simulations, the traffic consists of voice and data sources with voice sources. generating RH and RL cells. Each source in the simulation experiments behaves as an ON / OFF stream in which the duration of an ON period has a truncated exponential distribution to provide an integer number of time slots. A time slot corresponds to the transmission time of a cell (with respect to the input line rate), or equivalently the cell interarrival time during a burst. During an active period of a stream, cells arrive one at a time at the beginning of a slot. OFF periods in the simulation model are identical to those of the fluid model. To provide a fractional guaranteed bandwidth (equivalent to 7C, and (1 — 7)C in the analysis), a cyclic service discipline is implemented in the simulation model in which the server alternates between the two buffers forming cycles of service. Each cycle consists of a maximum of 0 slots for BR followed by a maximum of 3 slots for BNR such that 7 = 31—3 with smallest possible integer-valued a and fl (e.g., if 'y = 0.4, then a = 2, fl = 3). The service discipline is work-conserving. Buffers used in the simulations are of a finite size, whereas the numerical results for the analysis were mostly obtained assuming infinite buffers to avoid numerical instability and machine precision overflow (note, however, that BR still uses a finite threshold). It should be noted that because of the several differences between the simulation setup and the assumptions in the analytical approach (namely, the use of finite versus infinite buffers, the truncation of ON periods in the simulations, the separation of time scales in the fluid approach, and the server arbitration), the results obtained from the two approaches are not expected to be identical. However, for most of the cases both approaches gave sufficiently close results, and in all cases they indicated the same performance trends. The parameters used in the following experiments are normalized with respect to time and data units. The average length of ON state for a voice source was chosen as the time unit (i.e., p3 = ), which corresponds to 352 msec. Based on this time unit, 64 it is assumed that r3 = 1.85 (or 650 msec), r51 = 4 and p51 = 2. As noted, a data source is more bursty than a voice source. The size of a cell (i.e., 53 bytes) is used as the data unit. In Figure 4.4, the effect of the size of BNR on the loss probability of _ NRT cells is shown for two levels of N RT offered load: p, = 98% (heavy load), and p, = 64% (light load). Here, p, g 717/ (1 — 7)C. These results were obtained from the analytical model for finite and infinite buffers using N.) = 3, N... = 6, 82 = 100, T = 50, 'y = 0.67, and 5 = 0.2. As noted, the infinite buffer approximation provides a lower bound on the finite buffer performance. 10: T l I f l j ,0-2' — analysis: finite buffer 1‘ E ----- analysisflnfinitebufler .3» u 10 f 1 1 ................ 1 _4 ........ s”: =92: 3 .h l 310 g " i .i 2 10.2 1E 1057? =64% ': 106: 1 10.9 l 1 l— l l .1 0 50 100 150 200 250 300 350 Nonreal Buffer Size. 81, (in cells) Figure 4.4: Loss probability of NRT cells versus the size of BNR. The complementary buffer distribution for the content of BR (i.e., Pr{Xg > 2}) is shown in Figure 4.5 as a function of a: for different values of T. Notice that Pr{Xg > x}, which is based on infinite buffers, approximates the loss probability of RH cells. The confluence of drifts at the threshold level is the reason for the discontinuity of Pr{Xz > 1:} at a: = T. 65 10° 1 a“: i i A : 5 gm“ - E a: E Z ‘3 E E a, i i 10“5 g g 10“ i l l l I J l l l l 0 1O 20 30 '40 7O 80 90 100 x(irI cells) Figure 4.5: Complementary buffer distribution for BR. The effect of T on the loss probability for RL cells is shown in Figure 4.6 for different values of 7 and using N... = 3, N... = 8, B; = 200, 32 = 100, and f = 0.2. Results in this figure were obtained using the analytical model with finite buffers. Note that the parameter 7 is a key factor is determining the tradeoff between the performance for NRT and RT traffic. This parameter should be determined according to the desired QoS requirements. At larger values of 7, the value of T has more impact on the loss probability of RL cells. For the same experiment, the average waiting times of RH cells are shown in Figure 4.7. At lower values of 7, the value of T has more effect on the delay performance. Compared to the previous figure, at smaller values of 7 the waiting time of RH cells is the significant factor in determining T, while at large 7, it is the loss probability of RL cells that determines T. In Figure 4.8 the fluid approach with infinite buffers was used along with simula- tions to obtain the loss probability of RL cells and the average waiting time of RH 66 1o _.—. I j T I —I I I ....................................... Y—:O.4 4 10.3r ~~~~~ ~.‘.‘-~ n-T [ ‘.‘-‘ ~ ...... 7:05 10" l'\_ ‘ ‘ T ‘ ~ ...... .. a "x 310‘“ - ._ - a \- Q ‘- 2 r ‘-\ E £ '\ \ 7:07 10 - x 4 3 "-4 '\_\ l 10-7r \ \x ‘ L "~.\ ] 10* - ’ \‘x. ] 10.9 l I; J I L A l 20 30 4O 50 60 7O 80 90 10( ThreshoidTGnoells) Figure 4.6: Loss probability for RL cells versus threshold. 0.14]- _ 0.12” ./-. 0.1- [,1 ’ _ 3 1:0.4-’ , ’ ’ ._ ......... 3008- ,., ,.- . g .I' a .,-’ 3 ,/ §0.m_ I‘l." d O _I' E I" 0.04*' " 7:0.5 0.02- _________________ .-._._._._._.-. ........... ._._. ............ - 7:0.7 0..---____-__.___-._._____-_-__-_-_1 20 30 40 50 60 70 80 90 10C ThresholdT(inc9|ls) Figure 4.7: Average waiting time for RH cells versus threshold. 67 cells. The results were obtained for different values of T and using N. = 5, N... = 10, 31 = 200, B; = 80, and E = 0.2. Note that the performance predicted by simulations is slightly worse than that obtained from the analysis. For the same experiment, the probability that the waiting time of a real-time cell exceeds a fixed value t = 0.2841 time units (100 msec) is shown in Figure 4.9 as a function of T. Again, the analytical results indicate a slightly better performance than the one demonstrated via simula- tions. The discrepancy between the two approaches, however, is minor. The figure also shows that Pr{WzH > t} > Pr{Wf’ > t} which is an intuitive result. The dotted line in the figure indicates the value of T below which the waiting time of an RH or an RL cell will be less than t, with probability one. The effect of the load ratio of RT traffic (6) on the performance is illustrated in Figures 4.10 and 4.11. Three values of T were used: 20, 40, and 60. Figure 4.10 shows that the loss probability of RL cells increases with the load ratio. This is indicated by the analytical (with infinite buffer) and simulation results. The same trend can be seen in Figure 4.11 where the average waiting time of a RH cell is shown to increase with g (only analytical results are shown here). The implication of Figures 4.10 and 4.11 is that a threshold-based cell discarding mechanism such as NTCD is most effective when 5 is small, i.e., when the high priority cells constitute a relatively small fraction of the traffic. 4.8 A Note on Fluid Models for Video Traffic In previous sections we used the fluid approach to analyze the performance of NTCD/ MB under voice and data streams. The analysis can be extended to include any type of traffic, as long as this traffic can be adequately characterized by a MMFF process. In this section, we describe how the previous analysis of NTCD / MB can be extended to include fluid models for video traffic. These models, which were proposed 68 O .5 O F I I I I I I I — RL loss probability: analysis + RL loss probability: simulations - - RH avg. waiting time: analysis 0 RH avg. waiting time: simulations v V I—VYW J .5 O r‘ 0 O L .s O I Loss Probability, Waiting Time (in normalized time units) (a 1. 10 20 30 40 50 60 70 80 Threshold, T (in cells) _a C Figure 4.8: Loss probability for RL and average waiting time for RH versus threshold. 10 I ‘I I . fir I I Tr ‘I r — Pr{wz (high) > 0: analysis l . E a: PM (high) >1}: simulations ' - - Pr{W2(low)>t}:analysis + Pr{w2 (low) >1}: simulations C d ' v Waiting Time (In nonnallzed time units) 0 1 0'2 L I I i I 4 I I I 10 20 30 4O 50 60 70 80 Threshold. T (In cells) Figure 4.9: Probability that the waiting time for RT cells exceeds t = 0.2841. 69 1o , 'I I I I I T f I I g 1 4 — 1:20, analysis. 0 T=20. simlations . — - 1:40. analysis. +T=40, simulations 1 ~- - - T=60, analysis, ' T=60. simulations 104k 1 2 vi g ’ i g 1 L 1 i 104: 1 i 1 . I l 10.3 L 1 I I _1 l 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Real-Time Load Ratio. § Figure 4.10: Loss probability for RL cells versus RT load ratio. 0.08 f I I I I I I r .I O O I o O 3 s 3 I I I \ \ l .0 j " ———------———_—--—--—- P O 81 1 Average Waiting Time (in time units) 0 ii I I i ' i p 3 I I J I I l O 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Real-Time Load Ratio.§ Figure 4.11: Average waiting time for a RH cell versus RT load ratio. 70 in [52] and [62], are applicable only to video streams generated by video-phones, and which are compressed based on the conditional replenishment compression algorithm (similar to differential PCM coding). Maglaris et al. [52] analyzed video streams generated by video-phones and de- veloped two traffic models for these streams. One of these models, which we adopt in this section, is a fluid model. In this model, the aggregate bit rate of Nvd video sources is quantized into a number of discrete levels, as shown in Figure 4.12. ‘ Bit Rate Model MA 4 -- Actual .i 2A ., A - 4» Time Figure 4.12: Aggregate arrival rate from Nvd video sources. The quantized aggregate bit rate constitutes a Markov chain. Transitions between states follow the birth-death transition diagram shown in Figure 4.13. At state i, the total arrival rate is Audi) = Ai, i 6 £04 2 {0,1, . . . , M}, where A is the quantization step (difference between two successive levels) and M is the number of quantization levels. Transitions occur between adjacent states only (i.e., arrival rate increases gradually). A transition from state i to state i + 1 occurs at an average rate of (M — 1)r,,d. Likewise, the average transition rate from state i to state i — 1 is ipvd. The process has more tendency to go to a lower level at high rates, and to a higher level at low rates. Let the generator matrix and the equilibrium probability vector be denoted by de and H04, respectively. The expressions for the two quantities are 71 similar to the ones for Q1 and H1. The values for rm; and [hid are found by matching the mean, standard deviation, and the autocorrelation function in both the model and the empirical data. In [52] the values .of rvd, pm; and A were given in terms of Nvd and M. It was noted that for large M the results are insensitive to the particular choice of M. A value of M = 20Nvd was recommended, as it agreed with results from another simulation model. Mr“, (M- Dr 21'“, (M1) "w Figure 4.13: Transition diagram for the fluid model of video traffic. Consider the structure of N TCD / MB that was shown in Figure 4.2. In addition to voice and data streams, video streams are also incorporated within RT traffic. Similar to voice streams, video streams consist of RH and RL cells. The aggregate video traffic is modeled as an (M + 1)-state MMF F. Independence of voice and video sources allows us to describe both traffic types as one (N90 + 1)(M + 1)—state MMFF process whose state 5'" (t), at time t, represents a 2-tuple integer which consists of the state of voice traffic, and the state of video traffic. |l(> 5*(t) e C" {0,1,...,K*} = {(132) : 1'64... j E£vd} . (4.35) =2 {(0,0),(0,1),...,(0,M),(1,0),...,(1,M),...,(N,,O,M)} where K " = (N90 + 1)(M + 1) — 1. It is important here to note the lexicographic ordering of the indices in (4.35). A general treatment of large systems which are composed of several separable subsystems is found in [66]. Two processes are separa- ble if they are independent and are, individually, modulated by a reversible Markov 72 process. Using results from [66], the combined generator matrix for real traffic is the K " x K "‘ matrix Q‘ = Qua e de (4'36) The equilibrium probability vector for the process that characterizes RT traffic can be expressed as 11*. = II,» ® Hm, (4.37) In the above, “GB” and “®” indicate the Kronecker sum and Kronecker product, respectively. The total arrival rate for real-time traffic at state i is given by /\2(z') = Ava (ifl-J) + Ami (i modulo M) (4.38) = am, lfij + A (i modulo M) (4.39) The function lfJ indicates the integer part of the division. Without loss of generality, we assume that (12 75 nM for any integer n, so that the arrival rates at two different states in C“ are always distinct. The load ratio .5 which was defined for voice traffic applies as well for video traffic, so that if = A§(i)/)\2(z’). The combined total arrival rate of NRT traffic and RT traffic (which now consists of voice and video streams) can be described by a global K -state MMFF process (K = (N4 + 1)(Nvo +1)(M + 1)) whose state at time t is S'(t) é (Sd(t),S'*(t)) E .C, where [I 2 {(i,j) : i: 0,1,...,Nd, j = O,1,...,K"'}. The set of pairs in .C are ordered lexicographically. We say S(t) = (2', j) = k where k = 1,2, . . . , K, to mean that the integer It represents the k’th ordered pair in .C. The global generator matrix Q and the stationary probability vector H for the global arrival process are [66]: = 6246962“ (440) n = mean" =[7r1 «2 MT (4.41) 73 Once the aggregate traffic is described as a MMFF process, the analysis of N TCD / MB discussed in previous sections can be applied in a straightforward manner. The underlying assumption in the analysis developed in this chapter is that a traffic stream can be adequately characterized by a fluid model. While such an as- sumption is quite acceptable in the cases of data and voice streams, it is unlikely that this assumption is appropriate for every compressed video stream. The fluid models proposed in [52] and [62] are applicable only to certain types of video (i.e., video-phones) and based on certain compression schemes (i.e., the conditional re- plenishment scheme). In fact, it is quite improbable that a single traffic model can adequately characterize all sorts of compressed video streams due to two reasons. First, different types of video are quite different with regard to their scene dynamics (e.g., video-phones depict much less scene activity than video movies, which in turn depict less activity than commercial advertisements). Second, the existence of vari- ous compression algorithms result in traffic streams with different patterns, i.e., the same (uncompressed) video source can be compressed in different ways, resulting in different traffic patterns. Fortunately, a new standard for video compression has emerged and is expected to receive a wide distribution. This standard is known as Moving-Pictures Expert Group (MPEG) [26, 27] (after the name of the ISO committee which was responsible for its development). In order to investigate the performance of NTCD / MB under MPEG-coded video traffic, models for MPEG streams must first be developed. This is the focus of the next chapter. Chapter 5 Characterization of MPEG-Coded Video Streams 5.1 Introduction The largest proportion of the bandwidth in B—ISDN / ATM networks will be used to transport video streams. This is due to the introduction of many new video/ multimedia services and also to the large amount of bandwidth needed to trans- port real-time digital video. The huge link capacity provided by optical fibers can be quickly saturated by few video streams transmitted in their digital format. Hence, compression of digital video is the only means to transport real-time full-motion video over B-ISDN / ATM networks. By means of compression, the number of simultane- ously transported video streams over a single link can be increased to more than one order of magnitude. The basic concept in compression is to reduce the size of video frames by taking advantage of the inherent information redundancy (spatial as well as temporal) that exists in video data. A video stream (before compression) consists of a sequence of frames (i.e., images) that are displayed successively at a constant rate (e.g., 30 frames/sec in the NTSC standard) to produce motion picture . Most 74 75 often successive frames exhibit a large amount of visual similarities. This fact is used by many compression schemes to encode the differences between frames only. Other types of compression can also be used such as discrete cosine transform (DCT), mo— tion prediction, and interpolation. The size of a compressed video frame varies from one frame to another depending on the scene activity and the type of compression. As a result, the output of a video compressor is a variable bit rate (VBR) stream. Unlike conventional data networks, ATM networks provide efficient support for VBR traffic. Since this research is concerned with the design and analysis of the N TCD / MB mechanism under diverse types of traffic, we would like to study the performance of NTCD / MB under compressed video traffic. Such a study, however, requires the availability of empirical video data to be used in trace-driven simulations, or traffic models to characterize the actual video streams. Obtaining empirical data is a dificult problem due to the amount of storage which would be required to store a digitized movie before compression (a 2—hour movie with a moderate level of activity would require in the order of few hundreds of gigabytes). Deve10ping a traffic model for compressed video is also a challenging problem, due to both the difficulty in obtaining empirical data, and the complexity of the traffic patterns of compressed video streams. While a number of traffic models have been proposed to characterize compressed video, these models are valid only for a particular type of video (e.g., video-phone, video-teleconferencing) based on a particular compression technique. Hence, none of the existing models are considered to be universal for any compressed video stream. We focus on the modeling and characterization of video streams that are com- pressed based on the Moving Picture Expert Group (MPEG) compression technique. MPEG is a new compression standard which has recently gained a considerable at- tention. The first draft for the MPEG standard was accomplished in 1991 [26]. This draft defines the compressed bit stream for video and audio within a bandwidth of 76 1.5 Mbits/s. A more recent draft (known as MPEG-2) [27] defines the compression sequence at the rate of 5 Mbits/s. MPEG-2 has just been accepted as the basis for the HDTV standard in the United States [1]. The standardization and widespread acceptance of MPEG are the main reasons for choosing it among other compression techniques to be the focus of our research. In addition to these merits, MPEG involves several modes of compression, some of which are the basis of other (non-standard) compression algorithms. Thus, a traffic model for an MPEG stream would be applica- ble, as well, to video streams that are compressed using other compression algorithms (for example, JPEG which is a still-image compression algorithm is already being incorporated in MPEG). Several traffic models have been proposed to characterize compressed video streams [52, 62, 21, 54, 24, 61,63, 46, 74, 53, 6, 7, 15]. The parameters of these mod- els were obtained by matching certain statistical characteristics of an actual video sequence to their counterparts in the studied model. Particular emphasis was on matching the correlation structure of the bits-per—frame sequence, since correlations are known to have a great impact on the queueing performance of a statistical multi- plexer [65]. Correlations arise naturally in video traffic and their patterns are largely determined by the type of video (e.g., video-phone, motion-picture, teleconferencing) as well as by the compression algorithm used. In [52] the authors proposed two traf- fic models for the frame size sequence of a video—phone stream compressed using a conditional replenishment algorithm. The first model is a first-order autoregressive process, while the second is a fluid model. A more elaborate model based on an ARMA process was proposed in [21]. Skelly et al. [63] introduced a histogram-based traffic model using a quasi-static approximation. In [46] the authors used the TES approach developed in [54] to model a video stream that was generated using DCT coding, but with no differential or motion compensation. Heyman et al. [24] analyzed the VBR trace for a 30-minute long video—teleconferencing sequence and suggested 77 that the number of cells per frame approximately follows a gamma distribution. A sophisticated autoregressive model was proposed in [61], which consists of the sum of two AR(I) processes and a Markov chain. More recently, some researchers in— vestigated the appropriateness of fractional ARIMA processes to capture long-range dependency in the autocorrelation function (acf) of the VBR stream [17]. We see this last approach quite promising to model MPEG-compressed streams. However, the video sequence used in [17] was obtained using a DOT-based scheme that does not exploit the various compression modes employed in the MPEG algorithm. An empirical study of the characteristics of several short sequences of MPEG-compressed video was reported in [58]. No traffic models were provided in that study. Our objectives in this chapter are twofold. First, we describe the characteristics of an MPEG-coded video movie based on empirical data. Second, we propose two traffic models for MPEG streams. A video movie exhibits more scene dynamics and is, there- fore, more difficult to analyze than other types of video such as video-conferencing and video—phones. With regard to the first goal, we describe an experimental setup which was used to capture, digitize, and compress a long portion of a video movie. The frame size sequence of the compressed movie was analyzed. Empirical statistics of this sequence were obtained and subsequently used in developing tra.flic models. Such a sequence (which we refer to as the VBR sequence) was also used in trace-driven simulations described in Chapter 5. 5.2 Overview of the MPEG Standard This section provides a brief overview of the MPEG standard. The description is related to the first draft of MPEG, known as MPEG-I [26]. Subsequent drafts (e.g., MPEG-II) have slight differences which will not be discussed here. Most of the material in this section is paraphrased from [47]. Further details can be found in [26] 78 and [27]. In response to the need for standardization of video compression techniques, the International Organization for Standards (ISO) undertook an effort to develop a stan- dard for video and associated audio on digital storage medium which include CD- ROM, tape drives, and writable optical drives, as well as telecommunication channels such as ISDNs, and local area networks. This effort resulted in the MPEG standard, named after the ISO group that was responsible for its development. The MPEG activities cover more than video compression, since the compression of the associated audio and the issue of audio-visual synchronization cannot be worked independently of the video compression. MPEG-Video is addressing the compression of video signals at about 1.5 Mbits. MPEG-Audio is addressing the compression of a digital audio signal at the rates of 64, 128, and 192 Kbits/s. MPEG-System is addressing the issue of synchronization and multiplexing of multiple compressed streams. Our focus is on MPEG-Video compression. During the standardization phase, the MPEG com- mittee took into consideration the related activities of other standard organizations. As a result, the MPEG standard incorporated many of the good features of other compression standards. 5.2.1 Features of the MPEG Compression Algorithm Since the ISO/MPEG committee consists of various segments of the information processing industry, a representation of video on digital storage media has to support many applications. This is expressed by saying that the MPEG standard is a generic standard. It is generic in the sense that it is independent of a particular application. This does not mean that the standard ignores the requirements of the applications. A generic standard possesses certain features that make it somewhat universal. Some of the important features of the MPEG compression standard that were identified to meet the needs of applications are: 79 0 Random Access. This feature is essential for video on a storage medium whether or not the medium is a random access medium such as a CD, or a sequential medium such as a magnetic tape. Random access implies the existence of access points (i.e., segments of information coded only with reference to themselves). 0 Fast Forward/Reverse Searches. Depending on the application, it should be possible to scan a compressed bit stream and, using the appropriate access points, display selected pictures to obtain a fast forward or reverse effect. 0 Reverse Playback. Some interactive applications require the video signal to play in reverse. This feature should be possible with slight additional cost in memory (at the expense of slightly less quality of video when the signal is played back). 0 Coding/Decoding Delay. Since video quality and coding/ decoding delay represent a trade-off to a cer— tain extent, the MPEG algorithm is required to perform well over the range of acceptable, delays. The MPEG compression algorithm relies on two basic techniques: block-based motion compensation for the reduction of the temporal redundancy and DCT—based (discrete cosine transform) compression for the reduction of the spatial redundancy. Motion compensation techniques are applied with both causal (i.e., predictive) and noncausal (i.e., interpolative) coding. 5.2.2 Temporal Redundancy Reduction To achieve significant bit-rate reduction, temporal redundancy is exploited by gen- erating three types of compressed frames (i.e., images): Intra—coded (I), Predictive 80 (P), and Bidirectional (B) frames. I frames provide access points for random access, with moderate compression. An I frame is encoded independently of other frames based on DCT coding. A P frame is encoded with reference to a past I or P frame, and is used as a reference point for the next P frame. A B frame is an interpolated frame that requires both a past and a future reference frames (I or P), and it results in the highest amount of compression. B frames are never used as reference frames. From the point of view of the encoder, a stream of frames could look like the pattern shown in Figure 5.1—a. Since B frames require noncausal encoding, the transmission sequence has a different pattern than the encoding sequence, as shown in part (b) of thefigure. (a)EncodedSequence IIBIBIPIBIBIPIBIBIIIBIBIPIBIBIPI 1 2 3 4 5 6 7 8 9 1011 12 13 14 15 16 (b) Transmitted Sequence I P B|B|P|B|B|I|B|B|P|B|B|P|B|B 2 3 7 56108 9131112161415 1 4 Figure 5.1: A sequence of MPEG frames. At the encoder side (part (a) of the figure), the sequence of frames are generated according to a predetermined pattern which we refer to as the compression pattern. This pattern is repeated periodically until the whole stream is compressed. The pattern defines the numbers and types of P and B frames between successive I frames. In Figure 5.1, the pattern is IBBPBBPBB which continues to be repeated until the end of the video stream. We will refer to the length of this pattern as the compression period. The transmitted sequence (part (b) of Figure 5.1) is a permutation of the] ordering of the original sequence. If we only consider the types of the frames (and 81 not their time order), except for the first few frames, the encoded and transmitted sequences look alike. Such an observation will be used later when discussing the autocorrelation function of the transmitted sequence. 5.2.3 Spatial Redundancy Reduction Both still-image and prediction error signals have a very high spatial redundancy. Still-image refers to I frames and portions of P and B frames that are intra-coded. Prediction error refers to the difference between the predicted frames (produced us- ing motion estimation techniques) and the actual frames. Because of the block—based nature of motion compensation process, block-based spatial redundancy reduction techniques are used. These techniques include transform coding and vector quantiza- tion coding. Similar to J PEG (Joint Photographic Experts Group) and CCITT H.261 standards, the MPEG standard was based on DCT transform. Intra—frame coding with DCT involves three stages: computation of the transform coefficients; quan- tization of these coefficients; and performing run-length encoding on the quantized coefficients. 5.3 The Experimental Setup In order to provide a meaningful statistical study of an MPEG-coded stream, a long sequence of actual video is needed. We used the the experimental setup described below to capture, digitize, and compress a 23-minutes long video sequence [42]. The sequence was taken from the entertainment movie The Wizard of Oz, and was digi- tized and encoded using a public domain software MPEG encoder developed by the Berkeley Plateau Research Group. A two-stage approach was used to obtain the VBR trace (i.e., the sequence of bits per frame in the compressed stream). In the first stage, video frames were digitized 82 and stored on magnetic tape. A computer program was written to capture and digitize video frames. The program ran on a workstation connected to the laser disk player (see Figure 5.2). Using a Sun Video card installed in the workstation, the program received analog frames and digitized them one at a time. It then sent control signals to the laser player to position the head at the next frame and repeat the process. Frames were converted to 4:1:1 YUV format (the input format for MPEG encoders) and were written to hard disk. After accumulating some number of frames (180 frames), these frames were moved from the hard disk to magnetic tape. The process continued until the entire stream was stored on tape. A pseudo-code for the program that was used to obtain the digitized frames is shown in Figure 5.3. Analog Video Laser Disc Ta Player / Spare-10 ———S pe Control Line Frame-Grabber (SunVideo Card) Figure 5.2: A schematic diagram of the experimental setup. In the second stage, the frames were read from tape and compressed using the Berkeley MPEG encoder. The VBR trace was extracted during the encoding process. The compression pattern used to encode the examined video stream is shown in Figure 5.4. In this pattern, the compression period is 15, while the distance between successive P frames within the compression period is 3. There is no particular reason for choosing such a pattern except that it is one of the commonly used patterns (empirically, this pattern is found to provide good compromise between complexity and the amount of compression). In fact, the MPEG standard does not specify the compression pattern to be used, which makes the compression pattern a user- 83 E’rocedure: Main] begin position tape fori = 1 to Last.Set call Digitize(i) store digitized frames on tape end for end [Procedure Digitizej begin open a serial port configure video card (link to XIL Lib.) position player head ( random mode ) start player while < 180 frames are captured grab a frame (using XIL functions) convert frame to YUV format write frame to hard disk position player head (sequential mode) end while stop player end Figure 5.3: Pseudo-code for the program used in digitizing video frames. I’I’ I'I’ I'I’ if if ----- Compression Pattern (length- - 15 frames) Figure 5.4: Compression pattern used to generate the empirical data. 84 dependent parameter. 5.4 Empirical Statistics 5.4.1 Frame-Size Measurements Based on the previous setup, 41760 video frames were compressed and their sizes were recorded. At 30 frames/ sec, this represents about 23 minutes of real-time full-motion video. Portions of the frame size sequence are plotted in Figures 5.5 and 5.6. In both figures, the larger frame sizes (which are depicted by the lightly shaded areas) correspond to I frames. The darker parts of the figures correspond'to P and B frames which are smaller in size than I frames. Short-range variations in the VBR sequence are shown in Figure 5.7. Sample statistics for the size of an arbitrary frame and also for the sizes of individual I, P, and B frames are given in Table 5.1. 350 If I f I I I I I I 300- - 250*: 1 N 8 r 1 _s 01 C J Frame Size (in Kbits) § 50 0 200 400 600 800 1000 1200 1400 1600 1800 2000 Framelndex Figure 5.5: Frame size sequence (frames 1 to 2000). Frame Size (In Kbits) 85 350 r r r f r if m I r 250* '1 N 8 I 1 -L 01 o Frame Size (in Kbits) é 50 i , ‘ i V 1 l l I l l 0 l I l 1 2000 2200 2400 2600 2800 3000 200 3400 3600 3800 4000 Frame Index Figure 5.6: Frame size sequence (frames 2001 to 4000). 350 u r 300T .1 250- - 200- .. 150[- a 100[' 7 “11111111111111 1111 ‘ 1111 AAA/11 19100 1:50 1500 1550 Frame Index Figure 5.7: Frame size sequence (frames 1401 to 1550). 86 Sample Statistic All Frames I Frames P Frames B Frames Number 41760 2784 11136 27840 Mean (in Kbits) 41.7 197.1 58.0 19.6 Standard Deviation (in Kbits) 51.7 63.8 37.3 5.7 Maximum (in Kbits) 343.1 343.1 284.6 60.0 Minimum (in Kbits) 0.56 36.2 0.56 0.57 Table 5.1: Summary statistic for the frame size sequence. From the table, we find that the size of an I frame is, on the average, ten times that of a B frame. Additionally, the size of a P frame is about three times that of a B frame. The ratio of the sample standard deviation to the sample mean is an indication of the relative variation of the size of a frame. Using Table 5.1 to compute this ratio, it appears that P frames have the largest relative variation in their sizes followed by I frames, and finally B frames. The frame size histogram is depicted in Figure 5.8. It has the general shape of a Pareto or a Pearson type V pdf. We will not, however, attempt to fit a theoretical pdf to this histogram, because such a pdf would not differentiate among the three types of frames. Notice that the values in Figure 5.8 are given in cells/frame, since video bits must be converted into cells when entering the network. If the size of a frame at the output of the encoder is X bits, then this frame is packetized into [X / (8 :1: 48)] cells (i.e., a frame contains an integer number of cells). It is apparent that the type of a frame is an important factor in determining the size of that frame. Hence, we will be interested in studying the frame size statistics of individual types of frames. For this purpose, we divide the complete VBR trace into three subsequences, each of which corresponds to the size of same-type frames. Sample paths from these subsequences are depicted in Figures 5.9—5.11. 87 0.035 I W I —r I I WI I 0.03 ' O a i Relative Frequence O '2 0| 0.01 - I 0.005 “4+ hl.‘ I L o 100 200 300 400 500 600 700 800 900 Frame Size (in cells) Figure 5.8: Frame size histogram. m. ‘i 250.- 3.5 § 5.200 1 V J g .1 (0 E150 a i 100 o0200400600800100012001400160018002000 lFramelndex Figure 5.9: Sample path from I -frames subsequence. 88 ‘80 fl T I I T I d I d I L _s N O 3 O O Frame Size (in Kbits) 8 0o 500 1000 1500 2000 2500 3000 3500 4000 PFramelndex Figure 5.10: Sample path from P—frames subsequence. 8 Frame Size (in Kbits) 8 8 010002000300040005000600070008000900010000 BFramelndex Figure 5.11: Sample path from B—frames subsequence. 89 5.4.2 The Correlation Structure Correlations in video data arise as a consequence of visual similarities between con- secutive images (or parts of images) in a video stream. Although compression results in reducing the amount of correlations in video, the VBR sequence of a compressed stream maintains a considerable amount of correlations. This is due to the periodic fashion in which a given compression technique is used. For example, consider two consecutive frames that correspond to two] semi-similar images. Applying DCT to these frames (one at a time) will result in two compressed frames with almost similar sizes (i.e., highly correlated frame sizes). Two types of correlations can be identified in compressed video streams: intra- frame and inter-frame correlations. Intra-frame correlations arise when intra-frame compression (e.g., DCT) is involved and the VBR sequence is studied at a smaller level than a frame (e.g., a slice level) [46]. Inter-frame correlations are observed when the VBR stream is studied at the frame level, as in the case of our study. In several previous studies of video traffic, researchers observed that the acf for the frame size sequence of the compressed stream had a negative-exponential shape [52, 23, 24, 46]. A different shape for this function should be expected in MPEG- coded streams because of the existence of three different types of frames in MPEG. These frames are generated periodically according to the compression pattern. This results in persistent periodicities in the inter-frame acf . The sample acf for the frame size sequence of our video stream was computed using the following estimate: 1:1" Xg—Y X; —7 p(k)=($)(z“ [ H +’° 1) (5.1) N — k where X,- is the size of the ith frame, N = 41760, 7 and 02 are, respectively, the sample mean and variance. This function is depicted in Figure 5.12. Although the VBR sequence is being studied at a frame level, the correlation C .2 2 LL .5 , 3 EIlllllllll s s 2 _0.4,. .................. ...................................... ...................................... .1 ~05" .................. ........................................ ..................................... .1 4.8-14 ....................................... ...................................... q _1 I I I I I I I I J 0 10 20 3O 40 50 60 70 80 90 100 Lag (in frames) Figure 5.12: Autocorrelation function for the frame size of the VBR sequence. structure for the sequence is quite complicated and it depicts strong and pseudo- periodic behavior. Two apparent periodic components are observed in Figure 5.12: one at lags of 15 and its multiples, and the other component is at lags of 3 and its multiples. The first component is due to the periodic nature of the compression pattern which is being repeated every 15 frames. The second periodic component results from the correlations between P frames (the distance between two successive P frames within the compression pattern is 3). Both components are bounded by exponentially decaying envelops with large time constants (i.e., slowly decaying). This behavior can be better illustrated by computing the acf for the individual I frames (similarly, the P and B frames) as shown in Figures 5.13-5.15. Experimental Autocorrelation Function Experimental Autocorrelation Function _oz. ............................ _ .......... . .......... _ .......... , .......... _ .......... , .......... . ........ _ O 6.. ........ -. ......... - .......... - .......... ........ - .......... - .......... - .......... - .......... . ........ _ . . . . . . . . . . . . . . . . . . . . . . a . - . . "8- ............................ 1 .......... ' .......... ' .......... - .......... ' .......... ' .................. d . . . . . . . . . . . . . . . . . . . . . - . . 1 1 . . . . . . . - . u a - . o e i n - . - . . . . . 1 . . . . . - . . s . . - . . . . . . . __02 _ ................. , ............................ , ......... , ............................ . ......... _ ..... .. . . - . . . . . . . . . 4 . . . . . . . . . . 1 . . . . . . . u . . . . . . . . . . . . . . . . . . . . . - 4 i . . 1 . - ................................................................................................ - . . u . . . . . . . - . u - . . . . . . . . e . . . . 4 . . 06.. ........ ' ......... ' ......... ' ......... - ......... ' ......... ......... ' ......... - ..... _‘ . . . . ........................................................................ .1 . . . "1") 11111 ------ -------- - _, 4 1 1 1 1 1 1 1 _L 0 1o 20 30 4o 50 60 70 so 90 100 Lag (in l- Frames) Figure 5.13: Correlations in the I-frames subsequence. .5 .1 .._1 d —( 0102030405060708090100 Lag (in P-frames) Figure 5.14: Correlations in the P-frames subsequence. 0.8 0.6 ,4 [[1 ll 1 i ....... 2 .......... ......... ,1 0.2 ~ Experimental Autocorrelation Function 4,2- ........ ........ .......... g .......... ......... ......... .......... .......... ......... -0.4' ................................................................................................ .. .116- ........ .......... .......... .......... ......... ......... .......... .......... ......... g1 .01. ........ ......... .......... .......... ......... ......... .......... ........ ......... _, ; . g 1 1 1 1 1 . L 0102030405060706090100 Lag (in B—frames) Figure 5.15: Correlations in the B—frames subsequence. 5.5 Proposed Traffic Models for MPEG Streams Typically, a traffic model is used to analyze the queueing behavior of a buffer system. The complexity of compressed video streams precludes such an analytical study. Ex- cept for few simple models that were used in the analysis of simple queues (e.g., the fluid model by Maglaris et. al [52] for a FIFO infinite queue), models for compressed video have been used to generate synthetic traffic streams for simulation studies. Synthetic streams are needed in situations where empirical data are not available to conduct trace-driven simulations. The empirical data (i.e., frame size sequence) described in the previous section were used to derive two source models for an MPEG-coded video stream. Since these data belong to a video movie, the proposed models are particularly suitable to characterize the frame size sequence of a compressed video movie. The models can be extended to other types of video (e.g., video teleconferencing) by adjusting their 93 parameters to match certain statistics of the empirical data. For the purposes of this research, we will only be concerned with video streams from movies. 5.5.1 First Model 5.5.1.1 Model Description Driven by the need for a simple parsimonious traffic model, we propose a model that is based on the compression pattern and the first two moments for the size of individual I, P, and B frames [38, 43]. In this model, a traffic stream consists of a sequence of frames that are generated at a constant rate (e.g., 30 frames per second). Frames are of 3 types: I, P, and B. Frame types are determined according to a given compression pattern (hence, the compression pattern must be known apriori). The first frame in a stream can be of any type. Specifically, the type of the first frame is obtained by randomly selecting a location in the compression pattern, and then assigning the frame type in that location to the first frame. Once the type of the first frame (and its location within the compression pattern) is determined, the types and locations of the remaining frames are found easily. For example, in the compression pattern of Figure 5.4, the first frame in a stream can be in any of the 15 locations in the compression pattern (with equal probabilities = 1/15). Suppose that the location of the first frame was randomly decided as the 4th frame in the compression pattern. Then, the first frame is a P frame. The subsequent 11 frames in the stream are of the respective types: BBPBBPBBPBB. The compression pattern is then used again, and the next 15 frames have their types exactly as the ones in the compression pattern, and so on. To model the size of a frame of each type, the three subsequences in Figures 5.9 - 5.11 were used. Recall that each subsequence represents the frame size trace for frames having the same type. The empirical histograms for the three subsequences 94 are shown in Figures 5.16—5.18 (values in these histograms were normalized so that the total area under the histogram is one). Each histogram was fitted to three continuous pdfs: gamma, Weibull, and lognormal, as shown in Figures 5.9 - 5.11. Although the actual frame size is an integer number of cells, we used continuous distributions to simplify the fitting process. This should have a very minor effect on the accuracy of the fitting. When sampling from these distributions, the random samples are truncated to the closest (larger) integer to maintain a whole number of cells in a frame (this is being used in the simulation experiments of an ATM multiplexer for MPEG sources that are generated according to the model). The true parameters for the candidate distributions are substituted by their maximum-likelihood estimates (MLE). These estimates were computed according to the formulae in [4, page 345] for gamma and Weibull densities, and [45, page 337] for a lognormal density. .3 10 3x I I T I I I I? I 1 7 '1 1 - -—Gamma 2.51 [1 ----Lognormal J I“ , -- Weibull _’ ”IT. ‘1 T .1 I '\ N _ _ I [I '\ ix 2' I l ' k K \ ‘ Relative Frequence in ‘11 m \ ‘.fi \ —l I j s e V 0.5 O 100 200 300 400 500 600 lFrameSizeGncells) Figure 5.16: Histogram and fitting pdfs for the size of an I frame. 95 7X10.a 1 T I l T l 1 7 — 3mm J 6 - - Lognormal - - Weibull 5 l 8 §4 - LL 0 as ~ '5 m N 0 _ ‘ 1 o 100 200 300 400 500 600 700 800 900 1000 PFrameSizeancells) , Figure 5.17: Histogram and fitting pdfs for the size of a P frame. 0.05 T I fi I I—— fl I fir I 2 l G) s a Relatlve Frequence O O O 'o .0 ' 9 ' .0 a: s E s Q 2 e Q d 0.005 , l |., lll‘} “"ll l l l o 2040 60 80100120140160180200 B Frame Size (in cells) Figure 5.18: Histogram and fitting pdfs for the size of a B frame. 96 5.5.1.2 flame Size Distribution From Figure 5.16 it is observed that none of the candidate pdfs provides an ex- cellent fit to the frame size histogram for I frames. The multi-mode structure of the empirical histogram requires a more complicated fitting distribution than the exam- ined ones. In order to maintain the simplicity of the model, we restricted our selection process to the three candidate pdfs. Any of these functions can be equally used. We chose a lognormal pdf as the frame size distribution for I frames. As shown in Fig- ures 5.17 and 5.18, among the three candidate pdfs a lognormal pdf also provides the best fit to the frame size histograms for P and B frames. The match is best in the case of P frames. For B frames, the empirical distribution is more deterministic than any of the examined functions. We chose a lognormal pdf as the basis of our model. Hence, the number of cells in a frame is assumed to follow a lognormal distribution. The parameters for this distribution vary from one type of frames to another. The lognormal pdf for a frame of type T (where T E {1, P, 8}) has the following form: __ _ 2 l 2 exp [W] , x > 0 2;;2707. ”T fT($) = (5.2) 0, otherwise This function f1 is parameterized by a shape parameter CT > O, and scale param— eter pr 6 (—oo, 00). The. mean and variance for a lognormally distributed random \rariable are, respectively: m7 = exp {p1 + 0'31/2} (5.3) 127 = exp {2pT + 0%} (exp {0%} — 1) (5.4) In our model, we substituted the MLE of p7 and GT for their true values. These estimates are given in Table 5.2 for each frame type. .97 Frame Type MLE for the lognormal fit (T) FIT 5'! I 5.1968 0.2016 P 3.7380 0.5961 B 2.8687 0.2675 Table 5.2: Maximum likelihood estimates for the parameters of the lognormal fits. In the following, we derive an expression for the frame size distribution for an arbitrary frame. Consider an MPEG stream which is generated according to the proposed model. The frame size sequence for this stream is a discrete-time random process {Xn : n = 1,2, . . .} where X, is the number of cells in the nth frame. Our objective is to derive the distribution of X“. Since lognormal pdfs are being used in the model, the derived distribution of Xn will be a continuous function, and thus a continuous version of the actual discrete function. Let .S'n be a discrete random variable which describes the location of the nth frame within the compression pattern. The state space for 5,1 is 95 = {1,2, . . . , C}, where C is the compression period (C = 15 for our empirical data). The variable 5,. indicates the type of the frame. Based on the compression pattern in Figure 5.4: if 3,, = 1, then the nth frame is an I frame; if .97, = 4, 7,10,13, then the nth frame is a P frame; otherwise, the nth frame is a B frame. According to the model, given 57, = 2' , Xn ~ lognormal distribution with pa- rameters that depend on i. For i = 1,.. . , 15, define F.(a:) é Pr [Xn S 93/37, = 2']. Then, 171(3) , if i = 1 F.(:c) = Fp(z), ifz' = 4,7,10,13 (5-5) F 3(2) , otherwise Notice that E-(x) does not depend on n since the model assumes that the sizes of same-type frames are iid. It is easy to see that {Sn} constitutes a Markov chain with the following transition 98 probability matrix: 0 1 0 0 0 0 0 0 O 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 P = s s 5 (5.6) d where P = [p.,-] 2 Pr [5,. = j/S.._1 = i]. The Markov chain {Sn} is irreducible and homogeneous. All the states are positive recurrent with mean recurrence time equals to 15. Thus, there is a unique stationary distribution H such that 117’ = II. Let H = [7r1 7r2 11:15]. Then, 7r.- = l/mean recurrence time = 1/15 for all i. The probability distribution function for X, is given in the following proposition. Proposition 1 If 31 ~ II, then the random process {Xn} is first-order stationary. In this case, the pdf for Xn is given by: f(:v) = 515(f1(rc)+ we) + 1013(2)) (5.7) Moreover, the mean and variance of Xn are given by: m 2 E[X,,] = I15 [m1 + 4m + mm] (5.8) v 2 E [(Xn — m2] = -11—5 (v; + m? + 4(2),. + mi) +10(v3 + mfg» — m2 (5.9) where the quantities on the right hand sides of (5.7)- (5.9) were given in (5.2), {5.3), and (5.4). Proof: It is clear that if 51 ~ II, then the Markov chain {Sn} is stationary. Let 99 F (1:, n) g Pr [Xn S 1:] (for now, we maintain the time dependency). Then, F(a:,n) = :qun g z, 3.. = i] (5.10) = :13: [Xn g 32/5,. = i] Pr [3,. = i] (5.11) = '35:“an 3 93/5,, = 2'] (5.12) = 115;,(x)+4rp(x)+1org(x)) (5.13) Taking the derivative of F(:r,n) with respect to :c yields (5.7). Notice that the ex- pression for F (2:, n) does not contain n, i.e., {Xn} is first-order stationary. From (5.7) it is easy to compute m and v. D Using the MLE for m- and 07» (T = I, P, B) given in Table 5.2, f (2:) was computed according to (5.7). and is plotted in Figure 5.19. By comparing Figures 5.8 and 5.19, it is observed that the frame size distribution based on the model is very similar to the actual distribution. This gives strong credibility in the model. 0.025 I I I fir I j WI r ....- ] 0.015 * 0.01 - J Probability Density Function. {(x) 0.005 F ,1 01002003004005006007008009001000 x(FrameSizeinoells) Figure 5.19: The pdf for the size of an arbitrary frame based on first model. 100 5.5.1.3 Autocorrelation Function When studying the characteristics of compressed video, traffic modelers often try to develop a model in which the acf for frame sizes is similar to the empirical acf. This is important because of the impact of traffic correlations on the queueing performance. In this section, we derive the acf for our model and show its similarity to the empirical one. First, we show that the random process {Xn} is second-order stationary (i.e., the joint distribution of the random variables Xn and Xn+i¢ does not depend on n). Let H x“ x" +1: (2:, y) g Pr [X7, 3 x, Xn...’c S y]. In the following proposition, we provide the expression for H x" X“ +,,,(:t:,y) and show that this expression does not depend on n. First, define , . 1, ifj=((i+k—1)mod15)+1 pg) 2 Pr [3...”c = J/Sn = z] = (5.14) 0, otherwise Proposition 2 If 5'1 ~ II, then the random process {Xn} is second-order stationary, and the joint cumulative distribution function is given by: 15 lS-k‘ HXan+k($ay) = 113' ( Z E($)E+k’(y) + Z Fz‘($)E'+k°-15(y)) (5-15) i=1 i=15-k‘+l where k“ = ((i — 1) mod 15) + 1, and F,-(:c) is given in {5.5) V i and 2:. Proof: HXan+k($a3/) = Pr [Xn S 2:, Xn+k S y] 15 15 22131.an S 3:, Xn+k S y, 5,, = i, Sn“; =j] i=1 j=l ZZPIIXMI: S y, Sn“. =j/Xn S 2:, 3n = i]'Pr[Xn S 3:, 5n = i] J BUt PI‘ [Xn-Hc _<_ ya Sn-Hc :j/Xn S 1:9 Sn : 2] = PI‘ [Xvi-He S y, Sn+k =j/Sn = i] 101 (since 5,. contains all the necessary information). Thus, HXan+k($1 y) = EZPI [Xn+k S y, Sn-l-k = j/Sn = i] ' Pr [Xn S. CU, Sn = i] i i ZERPHXMLI. S y, Sn“; =j/Sn = i] - Prpffl S z/S'n = i]?'l',' = 11322131” an+k_ < y/5n+k — JaS = 2'] Pijk Pr [Xn S 3/5n = i] = 115:2:Pr[Xn+k_ < y/Sn+k— — j] p,J-)- Pr [Xn S z/Sn = i] = ELI—522m (y)F.-(:z: ()pff) (5.16) which is the same as (5.15). Notice that the expression for H x" x” ,H (x,y) does not contain the index n, i.e., the process {Xn} is second-order stationary. D To derive the acf for {Xn}, let p(k) denote the autocorrelation at lag k. Then, e C k pas): ( ) (5.17) where v is the variance (given in (5.9)) and C (k) is the covariance at lag k C(k) 2 E [(X..+,. — m)(X,. — m)] = E [Xan+k] — m2 (5.18) The following proposition provides the expression for C (k) Proposition 3 The covariance at lag k is given by 2 C(k)=1—15-th(,-)m,-— (1-1—5 2mg) , for k _>_ 1 (5.19) 5i=l i-l where m,- 2 E[Xn/Sn =j] forj = 1,...,15, and h(i) é (i+k— 1) mod 15+ 1. Proof: first notice that m,- E {m1,mp,m3} forj = 1,...,15. Consider 102 E [Xan+k] = E[X1X1+k] (because of stationarity) for k 2 1. E[X1X,+,.] = [0 Pr [X1X1+k>u]du 0° 15 f0 ZPr[X1X1+k > u/51 = i] - Fr [31 = i] du i=1 15 = ZW{E[X1X1+k/Sl =2] i=1 1 15 = —ZE [X1X1+k/Sl = i] (5.20) 15 i=1 To determine E[X1X1+k/Sl = i], observe that the two events [XI/51 = i] and [X 1+1. / S; = i] are independent (i.e., conditionally independent). Thus, f(x1x.+./sl=e)($, y) = furl/s: =i)($)f(x1+~/sl=i)(y) (5-21) Equation (5.20) becomes: 1 15 E[X1X1+k] = 13§_j13[X1/31 =i]E[X1+k/Sl =i] i=1 1 15 '2 Bimimhm (5.22) i=1 and the assertion is proved. Cl Using (5.19) and (5.17), the autocorrelation function for the frame size sequence based on the model was computed and is shown in Figure 5.20. A comparison between Figures 5.12 and 5.20 reveals that the model reproduces the general shape of the empirical acf. This fact gives strong credibility in the model. However, the values for the correlations based on the model are smaller than their empirical counterparts. This should be expected since the model only captures correlations induced by the periodicity and deterministic nature of the compression pattern (this type of correlations is not found in compression algorithms other than MPEG). Correlations between frames of the same type are not captured (in the model, the sizes of same-type frames are iid with a common lognormal distribution. The parameters of this distribution vary from one frame type to another). 1 I T I ”T I l v r u ,8. ......... ........... ........... ...... ........... ........... ........... .......... i 0.6“ ............................................. ] ............................................. _ ,4- ......... .......... .......... .................... .......... _ . ‘ H] H ‘ °|l|||||l||llllllllllllllllllflllllIlllflllll|||||||||l||||l| oretlcal Autocorrelatlon Functlon _021. ................................................................................................ . 4.4]. ................................................................................................ .. .2 .- _O.6.. ............................................................................................... _. _o_8_ ......... ........... ........... .......... .......... ........... .......... _1 I I J J I I ]_ I I 0 1O 20 3O 40 50 60 70 80 90 Leg (in Frames) Figure 5.20: Autocorrelation function for the frame size sequence based on first model. A sample path from the frame size sequence of a synthetic stream is shown in Figure 5.21. Observe that the model does not capture the effect of scene changes that were seen in the empirical trace (Figure 5.5 and 5.6). The empirical histogram and acf for the trace of the synthetic stream are shown in Figures 5.22 and 5.23, respectively. Both figures are very similar to the ones derived theoretically. 5.5.2 Second Model 5.5.2.1 Motivation The model proposed in the previous section captures the frame size histogram as well as the general form of the acf of the empirical data. It does not, however, incorporate the scene dynamics. From Figures 5.5 and 5.6, it is observed that the video stream consists of several segments such that the sizes of I frames in each 104 12m 1 T I I l T I I I 1000*: 1 . eoo- . g 8 E. g 600- - (D 2 IL 400 ~ 200 01002003004005006007008009001000 Framelndex Figure 5.21: Frame size sequence for a synthetic stream based on the first model. 0.025 I j 1 I WI I fl 0.02 - - 0.015 a 0.01 r - Relatlve Frequency 0.005 . ; _‘n #1 l 0 200 400 600 800 1000 1200 1400 1600 Frame Size (in cells) Figure 5.22: Frame size histogram for a synthetic stream based on the first model. d 1 fi fi .0 .° .0 A a m I I I O l . J I I o to Experlmental Autocorrelation Functlon O '02 : E -o.4 i 3 -o.e -o.s E _1 g 1 I I l I o 20 40 so so 100 120 Lag (In Frames) Figure 5.23: Empirical acf for the frame size sequence of a synthetic stream generated using first model. segment are close in value. By watching the movie and simultaneously observing the changes in the frame size sequence, we concluded that each of these segments corresponds to a part of the movie with no abrupt view shifts. Each of these segments is being referred to as a scene. Note that only an abrupt view shift accounts for the beginning of a new scene. Camera panning and zooming are not considered as scene boundaries. In this section, we develop a second model for an MPEG video stream, which is based on capturing the scene dynamics. 5.5.2.2 Scene Length Distribution To model the length of a scene (in seconds or in successive frames), one must first obtain a set of empirical data that represent the lengths of actual scenes in the movie. This can be done by watching the movie and measuring the duration of each scene. A disadvantage of this approach is that it requires the availability of the actual movie which must be watched in slow motion to accurately measure scene durations. 106 Moreover, it is sometimes dificult to visually determine whether a given view shift should be counted as the start of a scene (e.g., when the camera is moving fast but still in a continuous manner). We developed another approach for computing scene durations, which only requires the availability of the VBR trace. This approach, to be presented shortly, was validated by comparing its outcome to the one obtained through visual inspection. For more than 95% of the scenes, both outcomes coincide. In this heuristic approach, we use the fact that a ‘sufficient’ change in the size of two consecutive I frames is a strong indication of the start of a new scene. Thus, one can use the frame size subsequence of I frames to obtain the scene length data. We assume that the minimum length of a scene is one second (i.e., two consecutive I frames). Let {X1(n) : n = 1,2, ...} be the I frames subsequence. Suppose that the current scene is the ith scene that started with the kth I frame. The (n + k + 1)th I frame of the sequence indicates the start ‘of the (i + 1)th scene if |X1(n + 1: +1) — X1(n + k)| T1 (239:: XrUl) /n and |X1(n+k+2)—X1(n+k)| T2 (232:: X100) /n where T1 and T2 are two thresholds. Based on the above approach, the frame size histogram for the scene length (in I frames) is shown in Figure 5.24 using T1 = 0.05 and T2 = 0.1. An exponential fit for this histogram is also shown in the figure. Since the scene length is a discrete quantity (measured in successive I frames), we assume that it follows a geometric distribution (the discrete version of an exponential distribution) with mean = 10.5 I frames. A quantile-quantile plot for the empirical and geometric distributions is shown in Figure 5.25. We also tested the hypothesis of independence between scene lengths based on the runs—up test [45]. At a 95% level of confidence, the hypothesis of independence cannot be rejected. P ..s .0 8 ‘udfi' p 8 I 0.07 p 8 0.05 0.04 Probability Density 0.03 0.02 0.01 107 I I I «if 3.4m- 1 m 1o 20* so 40 so so 70 so 90 Scene Length (in successive I frames) Figure 5.24: Scene length histogram. 8 ages. Geometric Quantiles i! Quantile Points — Ideal Fit 3! L l I J I L I I 51015202530354045 Observed Quantiles Figure 5.25: Q—Q plot for the scene—length distribution. 108 5.5.2.3 Frame Size Distribution Average size of an I frame in a scene. The model assumes that an MPEG stream consists of several scenes. A scene is being recognized by the overall level of the frame size sequence. We saw in the previous section that this overall level can be identified by the average size of an I frame taken over all I frames within a scene (this average is given in the denominator of the left-hand sides of (5.23) and (5.23)). This average, which we denote by Iavg( j) for the jth scene, is itself a random Variable that varies from one scene to another. Hence, we are interested in obtaining a suitable approximation to the distribution of Iavg- We assume that {Iavg( j) : j = 1,2, . . .} is a sequence of iid random variables. Using the empirical values of Iavg( j ) (j = 1, 2, . . .), the histogram in Figure 5.26 was constructed. Compared to the frame size histogram of I frames (see Figure 5.16), the frame size histogram of [avg depicts a more regular shape. In Figure 5.26, three pdfs are fitted to the histogram (using the MLE for the parameters of these pdfs). We adopt a lognormal distribution to characterize the average size of I frames in a scene. The MLE values for the lognormal fit in Figure 5.26 are: in = 6.0188 and (‘71 = 0.4556. Sizes of I frames within a scene. Given the average size of I frames in a scene, we would like to characterize the small variations in the sizes of I frames within that scene. Let n 1( j) be the number of I frames in the jth scene (n 1( j ) is geometrically distributed for all j). Denote the size of the kth I in the jth scene by X1(k,j), where k = 1,...,n1(j). Let A1(k, j) = X1(k, j) — Iavg( j) which represents the deviation of the size of the kth I frame in the jth scene from the average size of I frames in that scene. Our objective is to model the sequence {A1(k, j) : k = 1, . . . , n 1( j )} The difficulty is modeling such a sequence is that for a given j, n1(j) is very small (n1( j) = 10.5 on the average). To overcome this problem, we assume that the stochastic behavior of {A1(k, j )} 109 -3 Modified l-Frame Size Distribution 25x10 — Gamma 2 _ -- - - Lognorrnal q ' ----- Weibull .I- E " o1.5b ! 3 I s ,- ‘t _, a ! % 1 - .I a: i ' 0.5 . . “I . _I .-". ., 0 100 200 300 400 500 600 Frame Size (in cells) Figure 5.26: Histogram and fitted pdfs for the average size of I frames in a scene. is independent of j, i.e., {A1(k,j)} is invariant with respect to j. Thus, a longer sequence can be constructed by successively concatenating the sequences {A 1(k, j )} for j = 1, 2,. . .. This results in the following sequence: {A;(n) : n =1,2,...}é {{A1(k,j) : k =1,2,... ,n1(j)} : j = 1,2,...} (5.23) It should be expected that the process of concatenation will result in slight errors at the boundaries of the concatenated sequences. This error is of a minor effect on the modeling of A1(k, j). Intuitively, a time series model is a good candidate to characterize the sequence {A}(n)}. This sequence is shown in Figure 5.27. Its empirical acf is depicted in Figure 5.28 (the bold-font vertical lines). The shape of the acf suggests some form of an autoregressive fit. We believe that an autoregressive of order two (AR(2)) model is appropriate to characterize 110 150- .4 I I 50 Deviation from the mean (in cells) -1oop - -150 l I I J_ L I L I I O 200 400 600 800 1000 1200 1400 1600 1800 2000 I-Frame index Figure 5.27: The sequence {A}(n)}. 0.81 ........ ......... ......... ......... ......... ......... ......... ......... ......... ..... _. 0.6- 0.41;...“ ......... g ......... g ......... g ......... ......... g ......... g ......... g ......... g. ..... _ . . ‘ g n u a o n n a . . . . . . . . . . . D o I ............................................................... ‘ --------- I --------------- d 0.2 s, . . . . . . . . . . . . . . . . . . . . . . . . . . )- .................................... , .............................................. . ............... _ I . Autocorrelation Function o ....Ji . I: .' ...—i... ......i i ...:l. M: J _O4-......._ ......... j ......... 1 ......... j ......... ......... : ......... ; ......... ; ......... ; ...... .1 I 06.........: ......... 1 ......... : ......... i ......... ......... : ......... ' ......... ' ......... ' ...... q -— , . . . 8.. ................. . ......... - ......... . ............................ . ......... . ......... . ............... _, _1 i i i i i i i i '1 i 0 5 10 ' 15 20 25 30 35 40 45 50 Lag (in successive l frames) Figure 5.28: The acf for the sequence {A}(n)} and for an AR(2) model. 1 I r r r I r 1 I r 0.8” ........ ......... .......... .......... .......... .......... .......... ........ .......... ........ ., 0.6---~ ......... .......... .......... .......... .......... .......... ...... .......... ........ 1 g L E i 2' 2 : 2 E 2 2 30.4 ........ ......... :. ......... .......... .......... .......... .......... .......... ::........., ........ —| § 0.2.. ............................ .. 2 I - - - é . . g 0 l 1 | I 1 1 n- 5 I v a: ; 2 34.2.. ........ ; .......................................................... ............................ _, .g : g-OAL' ................................................................... ............................ _. I” : -0.6"' .................................................................... ............................ .., -0.8" ..................................................................... ............................ 1 _1 i i g 'L . . m 'L . 0 2 4 6 8 10 12 14 16 18 20 Coefficientlndex Figure 5.29: Partial autocorrelation function for the sequence {A}(n)}. {A;(n)}. The acf for an AR(2) fit is also shown in Figure 5.28. The empirical partial autocorrelation function (pacf) was computed and is depicted in Figure 5.29. For a general autoregressive process, the pacf provides a means of determining the number of the autoregressive coefficients. It is clear from the pacf in Figure 5.29 that the sequence {A}(n)} entails two strong autoregressive components (at lag 1 and 2). Thus, the following AR(2) model will be used to characterize {A}(n)}: A}(n) = alA';(n - 1) + agA;(n —- 2) + €(n) (5.24) where {s(n)} is a sequence of iid random variables whose marginal distribution is often taken as a normal distribution with mean zero and variance 03. Since A}(n) has the same marginal distribution as e(n), this distribution is found empirically from the histogram of A;(n), which is depicted in Figure 5.30. A normal fit is also depicted (based on MLE parameters), which provides sufficient support to assume a normal 112 distribution for 5(n). 0.m5 I W I T I F 0.02 r- - Q .. ' k a g 0.015 - -‘ - o _l A] a V l a , . :5 I l 3:5 I. '\ normal iii 4 i 0.01 - .I- ”l -\ I _ r- . II .‘ .I ‘\ I [- ‘\ 0.005 ~ .- .\ ] .\ \ .‘. O __._ D 4_ A -150 -100 0 50 100 150 200 Deviation from the mean (in cells) ‘ Figure 5.30: Histogram for the sequence {A}(n)}. In order to estimate a1 and a2 in ( 5.24), we used Yule-Walker equations [5]: -l a‘ — 1 p1 ”1 (525) a; Pl 1 P2 where pk is the autocorrelation value for {A}(n)} at lag k. Yule-Walker estimates for al and oz can be obtained by using the empirical values for p1 and p; in (5.25). Accordingly, a. 0.5300 = (5.26) it; 0.1512 The empirical sequence {A;(n)} was fitted to an AR(2) model with the above values for al and a2. A histogram for the residuals is shown in Figure 5.31 along with a normal fit. The acf for the residuals (Figure 5.32) clearly confirms the independence 113 of the residuals (lack of correlation implies independence under the assumption of normality). An estimate for of can be obtained from the sample variance of the residuals, and was found to be 83 = 392.04. 0.035 I I I W T I I 0.03 ' e . 0.025 ~ _ - 2' E 8 0.02 " I i " \ s i r a . “’ 0.015 - i l. - 3 I \ O. , \ .’ F Fl. normal fit 0.01 ' .I \ _ .’ i u, ‘- 0.005 ‘ ‘.\ .. '\ \- O .I_ _L__ . 7 , J _1_ -200 -150 -100 -50 0 50 100 1 50 200 Residuals in AR(2) Component (in cells) Figure 5.31: Histogram of the residuals in an AR(2) fitted model. Sizes of P and B frames. As in the first model, the size of a P or a B frame is assumed to follow a lognormal distribution (with parameters that depend on the type of the frame). The fitting lognormal distributions for both types of frames were shown in Figures 5.17 and 5.18. However, after sampling the size of a P (similarly a B) frame from a lognormal distribution, this size is adjusted to incorporate the overall level of the current scene. For example, if the P frame to be generated is in the jth scene, then the size of this frame is adjusted by multiplying it by the factor I“, (j) /Ia,,g, where I“, is the average of [avg (j) over all j (Tm, = 432 cells for our data). In essence, this multiplying factor reflects the level of the jth scene compared to the overall level of the movie. The 1 I T l r r i r r T T 0'8] ............................................ ' .................................................... _] 0.6’ ................................................................................................ _] 0.4.. ............................................................................................... _l c .9 ‘2 . 3 0.2 .............................................................................................. - U- . C . . . : .9 O l' 1 ' 'J L. -' A. ’ 4L ' :1 'J1 a in dirt? ' ' r Tfi'ri'H' ‘I' r' I 34,2, ................................................................................................ .. S < 4.4... ............................................................................................... q _o.6.........: ....................................................................................... '] _0...8_.....f ........................................................................................ .l _, i . . . . i J i A. i 0 5 1O 15 20 25 30 35 40 45 50 Lag (in successive l Frames) Figure 5.32: Autocorrelation function for the residuals in the AR(2) fit. same procedure was used with B frames as well. The algorithm in Figure 5.33 can be used to generate a synthetic MPEG stream based on the present model. Notice that the computer-generated values for the frame sizes are truncated so that they do not exceed their maximum empirical values. In the cases when such maximum values are not known, some upper theoretical bounds could be used instead. 5.6 Queueing Performance under MPEG Streams In the study of computer networks, traffic models are mainly used to evaluate the queueing performance in the network buffers. Hence, the most important criterion for testing the appropriateness of a given traffic model should be the degree of similarity between the queueing performance under the examined model and that obtain under 115 Initialization: set Scene_ma:c := number of scenes X 2 frame size (in cells) T 2 frame type (T e {1, P, 3}) Loop: for j = 1 to Scene-ma:c do . compute the length of scene j: n 1( j ) ~ Geometric compute Iavg( j) ~ lognormal(i21, (“71) compute c g Ia.,9( j) /Ia,,g for i = 1 to n1(j) do fork=1tol5do T = type of kth frame in the compression pattern if T = I, then X = Iavg(j) + A}(i), where A';(i) = 81A;(i - 1) + agAfli — 2) + e(i) end if if T = P, then X = cY where Y ~ lognorma-KfiP, 5P) end if if T = B, then X = cY where Y ~ lognormal(fie, 63) end if end for end for end for Figure 5.33: Generating a synthetic stream based on the second model. the actual traffic. Other criteria such as the similarity in the acf structure and the marginal distribution are still useful in the preliminary stages of model development. However, in many cases the queueing performance under a traffic model may be no— ticeably different from the queueing performance of a real source, despite a relatively similar first and second order statistical properties. To verify the appropriateness of our models, we report in this [section the results from simulation experiments of an ATM multiplexer for MPEG streams. In addi- tion to testing the models, the simulation results are used to study the actual (i.e., 116 trace-driven) multiplexing performance for. MPEG streams (this is important since we have no previous reference to the actual queueing performance under MPEG traf- fic streams). The multiplexer (Figure 5.34) is modeled as a finite capacity queueing system with buffer size B (in cells) and one server with service rate C. A FIFO ser- vice discipline is assumed. The input to the multiplexer consists of N MPEG-coded video streams. Two types of simulation experiments were conducted. The first type is trace-driven (i.e., using the actual VBR trace). The second type of experiments was based on synthetic streams generated according to the proposed models. In either case, a video source consists of 41760 frames. Cells in each frame are evenly dis- tributed. All generated streams were based on the compression pattern of Figure 5.4. First, we consider the performance using the empirical frame size trace. Hnnri H'rinnii \ .... win . ----- lnrnnnri rl/ MO km>l 8°ch [ rlnnnli 11 F] Figure 5.34: A multiplexer for MPEG streams. Source] H" 5.6.1 Trace-Driven Simulations In the following experiments, traffic streams based on the empirical trace were used to drive simulations. Since only one trace is available, an approach due to Heyman et al. 117 [24] was used to generate multiple streams from the empirical trace. In this approach, the'video sequence is assumed to be homogeneous in some sense. The VBR trace is arranged as a circular list by connecting its ends. To generate a traffic stream, the first frame in that stream is randomly selected from the circular list. The remaining 41759 frames are selected sequentially following the first frame. This process is similar to a random shift with rotation in sequential lists. The procedure is repeated for each multiplexed stream. A drawback of this method is that it ignores possible cross- correlations among different streams (these correlations result from using one trace to obtain all the streams). For our purposes, this method was used only to study the multiplexing of MPEG streams, and not to validate the traffic models. To reduce the effect of synchronization among sources, the starting times for the video streams were selected randomly from a uniform pdf (over a frame period). The service rate for the multiplexer was adjusted to obtain a desired level of utilization U which is defined by the ratio of the aggregate arrival rate from all multiplexed sources to the service rate. Figure 5.35 depicts the average cell loss rate, Paw, Versus the buffer size, B, using different numbers of multiplexed sources: N = 1 (no multiplexing) and N = 10. The results are shown using two levels of utilization: U = 60% and U = 80%. Observe that PM for N = 1 is surprisingly large under relatively light load (U = 60%) and large buffer size (B = 600). This is true despite the fact that each stream is smoothed by spacing cells in each frame. Another important observation is the improvement in the cell loss performance when video streams are multiplexed. For N = 10, Pm,g is the average cell loss rate of the ten sources. Not all sources experience this rate. The maximum (Pmaz) and minimum (Pm-n) loss rates among the ten sources are shown in Table 5.3, for U = 60% and U = 80% and several values of B. The average cell loss rate versus the link utilization is shown in Figure 5.36 using different N and B = 150. It is evident that the loss rate drops significantly when N 118 13400 . l T l I r l ' & i 1 16-01 {_- & - '7] ’ i t 1 le-OZ '; "..‘EL 1 8 b ....... B... e s -------- ..., . 3 1e-03 _- -- -, g . G """""" a - Q U . le—04 :- 1 le-05 F- 1 le-06 L m r l J L 100 200 300 400 500 600 Buffer Size (in cells) Figure 5.35: Average cell loss rate versus buffer size in trace-driven simulations. Buffer U = 60% U = 80% ' Size P avg P max P min P avg P max P min 100 6.99E—4 1.05E-3 3.98E—4 2.29E—2 5.64E—2 7.04E—3 200 1.62E—4 3.14E—4 8.81E-5 7.83E—3 1.66E—2 4.04E—3 300 3.04E-5 6.30E—5 1.63E—5 3.85E—3 6.86E-3 1.24E—3 400 5.80E—6 1.30E—5 2.20E—6 2.05E—3 4.18E—3 8.59E—4 500 1.80E—6 5.05E—6 2.20E—7" 8.32E—4 2.6OE—3 6.05E—4 600 0" 0* 0" 5.47E-4 9.11E—3 2.62E—4 (:1: loss rates are less accurate due to small or zero number of lost cells) Table 5.3: Average, maximum, and minimum cell loss rates. 119 increases at a fixed U. Note that for certain values of U and N no cell losses were observed. 164-00 l I I T I TT T I le-Ol .- -. le-02 .- -. s l - m le-03 r ‘- 3 r 1 3 l . = 1e-04 :- -: as r ‘ le-OS F' 1 " 'l le-06 .- .1 16.07 I. I J I J I I I J ‘ 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 l Utilization (U) Figure 5.36: Average cell loss rate versus utilization. The figure clearly indicates that a considerable gain can be obtained by multi- plexing VBR video streams. We define the following quantity which will be referred to as the multiplexing gain: n x Utilization at N = 1 and PM, = p A G” (n) — Utilization at N = n and Pavg = P (5.27) For a given PM, and N, the utilization can be obtained graphically from Fig- ure 5.36. Accordingly, Gp(n) was found for various n and for P,mg = 10‘2 and PM, = 10'3 as shown in Table 5.4. 120 n Gp(n) p = 10"2 p = 10“3 1 1 l 10 4.1 3.4 100 31.1 21.4 Table 5.4: Multiplexing gain at different loss rates. 5.6.2 Queueing Performance Based on Proposed Models In this section, we evaluate the appropriateness of the two proposed traffic models from the queueing performance perspective. A FIFO queue with finite capacity B is assumed. Input traffic consists of only one stream. Three cases are considered. In the first case, the stream is the empirical trace. In the two other cases, the stream is generated according to the first and second traffic models, respectively. In each of the following experiments, a traffic stream consists of 41760 frames, generated at the rate of 30 frames/ sec. The service rate is adjusted to obtain a given level of utilization. When the traffic stream is generated based on one of the two models, each simulation experiment is repeated 5 times with different random sequence. The 90 percent confidence interval are computed based on the five independent runs. When the empirical trace is used, only a single run is used in each experiment (no random numbers are used in this case). The cell loss rate versus buffer size is shown in Figure 5.37 using two levels of utilization: U = 40% and U = 60%. The short vertical lines along the the cell loss curves for the first and second models indicate the 90% confidence intervals based on five replications (using the t distribution with 4 degrees of freedom). For a small buffer size, the performance based on either traffic model is very close to that based on the empirical trace. This is true for both levels of utilization. Intuitively, the difference in queueing behavior becomes smaller as the traffic intensity is increased (at U = 80% the queueing behavior for the trace and the model-based streams were almost identical). However, as the size of the buffer increases, results from the two 121 models start to deviate from the results based on the empirical trace. At U = 40%, the trace-based cell loss rate decreases more rapidly than the loss rate according to any of the models. The first model seems slightly more accurate than the second model in terms of reproducing the cell loss rate of the empirical trace. Notice that the second model has relatively large confidence intervals, meaning that it would require a larger number of independent replications to obtain reliable results than would be required in the first model. 10 ,_ f I T r I F ' —Trace l - - FirstModel , ----- SeoondModel , 10-1‘: 1 .2 E i 5 _ , g . e o. t ..l 10*,- 1 t 1 10.3 JL 1 l i l 0 100 200 300 400 ‘ 500 600 Buffer Size (in cells) Figure 5.37: Average cell loss rate versus buffer size. Figure 5.38 depicts the relationship between the average queue length q and the buffer size (B). When U = 40%, the increase in q as a function of B for a model- based stream (using either model) is similar to that of the trace. When U = 60%, the second model provides closer results to trace-based results than the second model. 122 1m 1 I I I r 90“ -—Trace - —- FirstModel 80" ----- SecondModel ‘ 1'? as 70- ~ 0 S a °°r 1 5 _l O 50]' .1 8 3 O 40— - 8: £2 20' Ill 10~ ~ 0 I 1* I I l 0 100 200 300 400 500 600 Buffer Size (in cells) Figure 5.38: Mean queue length versus buffer size. In all cases, we observed that the queueing results based on the second model upper bounded the trace-based results. Between the two models, we decided to use the second model to characterize the video traffic component in the study of NTCD / MB. Our choice is justified by the need to provide statistical performance guarantees in NTCD / MB and the fact that the second model produces conservative performance results compared to the actual (i.e., trace-based) results. Hence, guaranteeing the QoS requirements of traffic streams generated by the second model will consequently guarantee the QoS requirements of the actual video streams. Chapter 6 The Performance of NTCD / MB under Multimedia Traffic 6.1 Introduction In this chapter, we use the various results obtained in previous chapters to demon- strate the performance of the NTCD / MB mechanism under multimedia traffic. For our purposes, “multimedia traffic” refers to the combination of several independent types of traffic, including data, voice, and video streams. Therefore, a multimedia source in which voice and video bits, for example, are intermixed within a single stream is not included in the current study, mainly due to the lack of data regarding the format of such a source. Nevertheless, the applicability of NTCD / MB extends as well to this type of streams. The main goal of this chapter is to describe how buffers and bandwidth resources under NTCD / MB can be efficiently allocated to various traffic streams, while, simul- taneously, guaranteeing the sets of QoS requirements associated with these streams. In theory, this is a constrained optimization problem whose exact analytical solution is not tractable. This is due to the difficulty in analyzing the queueing behavior un- 123 124 der video traffic streams that are generated according to the models developed in the previous chapter. Even for a simple FCFS (First Come First Serve) queue, analytical results under video traffic models are not tractable. In the case of data and voice streams, analytical queueing results can be obtained using the fluid approach, as de- scribed in Chapter 4. Consequently, we used both analytic and simulation approaches to study the queueing performance of the N TCD / MB mechanism under data, voice, and video streams. In addition, we provide near-optimal allocation of bandwidth and buffer resources for such streams given that their QoS requirements are satisfied. Although particular sets of QoS requirements will be assumed throughout the study, the same treatment can be similarly applied to any given sets of QoS requirements. 6.2 Input Traffic and Associated (208 Require- ments We assume that the overall traffic is composed of three types: data, voice, and video. Each type consists of several independent streams that are generated according to the models below. A set of QoS requirements is associated with each type of traffic. The input streams arrive at a buffer system that implements an NTCD / MB mechanism. The number and sizes of the buffers used in N TCD / MB are generally determined according to the QoS requirements of the traffic. Streams that are admitted to the same buffer are statistically multiplexed. In the following, subscripts 1, 2, and 3 will be used, respectively, to refer to quantities associated with data, voice, and video traffic types. Data traffic consists of N1 data sources. Each source is characterized by alternating ON / OFF periods. A fluid representation is used to model a data source. It is assumed that the durations of ON periods (similarly, OFF periods) constitute a sequence of iid random variables which are exponentially distributed. To provide a realistic 125 description of a data source, we assume that the mean duration for an OFF period is four times the mean duration of an ON period (i.e., 7'82? = 47812?)- On the average, a data source transmits 200 ATM cells during an ON period (this corresponds to slightly more than 10K bytes). These cells arrive at a constant rate A1 = 100 Kbits/ sec. Data streams require the following cell loss rate to be guaranteed (with no requirements on cell delay): QoS requirements for data traffic: cell loss rate 61 S 10'3 Voice traffic consists of N2 streams which, similar to data streams, have the ON / OFF behavior. Again, each voice stream is modeled using the fluid approxima- tion. In this case, however, the mean duration of an OFF period is chosen to be about 1.85 times the mean duration of an ON period. This choice is made in compliance with previous measurements taken for adaptive differential pulse code modulation (ADPCM) voice sources with silent detectors [22]. In these measurements, it was found that the mean durations of ON and OFF periods in a voice stream are, respec- tively, 352 msec and 650 msec. As will be shown in the next section, the ratio of the OFF to ON mean durations plays a significant role in determining the appropriate buffer size needed to achieve a given cell loss rate. During ON periods, voice cells arrive at a rate of A2 = 32 Kbits/ sec (which is the standard rate for an ADPCM voice stream). Since voice traffic is delay-sensitive, it has a delay requirement. We assume that voice cells have a maximum queueing delay requirement in addition to a cell loss requirement: . . cell loss rate £2 5 10‘4 QoS requirements for vorce traffic: maximum queueing delay (12 5 D2 where two values for D2 will be used: 352 msec and 35.2 msec. Video traffic consists of N3 streams. A stream is represented by the second traffic model that we developed in Chapter 5. Recall that in this model assumes three frame 126 types that are generated in a deterministic fashion based on the compression pattern of Figure 5.4. Frames are generated at a rate of 30 frames / sec. Cells within a frame are evenly distributed. The algorithm in Figure 5.33 was used to generate each video stream. To reduce the effect of synchronization among different streams, the type of the first frame in each stream is obtained by randomly selecting the location of the first frame from the 15 locations in the compression pattern, and then assigning the type of the frame in the selected location to the first frame. Thereafter, the types of the remaining frames are taken sequentially according to the compression pattern. In addition, we assume that the starting instant for each stream is random with a continuous uniform distribution over a period of 1 / 30 second. With respect to their role in reconstructing the video signal at the receiver, MPEG frames vary in their relative significance depending on the type of the frame. Specif- ically, I frames are more important than P and B frames since I frames are used as reference points to P and B frames. Thus, if an I frame (or part of it) is lost, all P and B frames between this I frame and the next I frame cannot be properly decoded at the receiver. To protect I frames from excessive cell losses, two classes of loss priority are assigned to video cells, with cells in I frames having higher priority over cells in P and B frames [37]. An NTCD mechanism is required to realize the two classes of priority. Notice that in our study priority classes are assigned on a frame basis. A different approach to priority assignment in an MPEG stream was used in [58] where priorities were assigned on a macroblock basis, with possibly high and low priority cells in every frame. Clearly, this latter approach does not take into consideration the different levels of importance associated with different types of frames. We assume the following QoS requirements for video traffic: cell loss rate for I cells 69) S 10'4 Q03 requirements for video traffic: cell loss rate for P and B cells 6&2) S 10'2 maximum queueing delay d3 3 D3 127 Two values for D3 were used: 33 msec and 10 msec. In order to guarantee the aforementioned QoS requirements for data, voice, and video traffic streams, an NTCD/ MB mechanism of the form shown in Figure 6.1 is needed. Following the general design methodology that was outlined in the last section of Chapter 2, three buffers would be used to support three levels of delay performance. Each buffer accommodates cells of one of the three traffic types. The total service rate (i.e., link capacity) is divided among the three buffers such that each buffer is guaranteed a fraction of the total capacity. These fractional capacities are the quantities C1, C2, and 03 in Figure 6.1, with C = C1 + 02 + C3. The service discipline is work—conserving, so that if one buffer is empty at some time, the residual capacity is given to the following buffer (in a cyclic fashion). Effectively, the perceived service rate in each buffer can be higher than the guaranteed service rate (which is being indicated by the “2” signs in the figure). Our major concern for the remaining sections of this chapter is: (1) determine the appropriate values for the fractional capacities, (2) dimension the sizes of the three buffers, and (3) appropriately partition the space in Buffer 3, such that the QoS requirements for the three types of traffic are satisfied. 6.3 Efficient Allocation of Buffers and Bandwidth The buffer system shown in Figure 6.1 contains dependencies among the contents of the three buffers. For a given set of QoS requirements, finding the optimal sizes of the buffers and the right amounts of bandwidth to be allocated to each buffer can be analytically done under the fluid assumption. This was shown in Chapter 4 for two buffers, and can be extended in a straightforward manner to any number of buffers, under the assumption that each traffic stream is characterized by a fluid model. However, for the type of video being considered here, the fluid representation 128 Data Traffic ———> Buffer 1 ‘ 2 01 Voice Traffic __> Buffer 2 — Video Traffic —>5 (high +low) __> Buffer 3 l T Figure 6.1: Structure of N TCD / MB for data, voice, and video streams. is not appropriate. The two models which were proposed in Chapter 5 can accurately characterize MPEG streams. Unfortunately, queueing analysis under such models is not tractable. In order to dimension the underlying system (using the second video model in characterizing MPEG video streams), we resorted to a two-stage approach. In the first stage, we considered a non-work-conserving service discipline. This allowed us to consider each buffer independent of the other two buffers. We then optimized the size and allocated bandwidth for each buffer (given the QoS requirements associated with input traffic to that buffer). This was done analytically for Buffers 1 and 2 (using fluid analysis), and via simulations for Buffer 3. In the second stage, we used simulations to study the performance of the complete system assuming a work-conserving discipline, and using the buffers sizes and bandwidth computed from the first stage. Intuitively, the performance observed in the second stage is expected to be better than the desired QoS requirements (which were guaranteed under a non-work-conserving assumption). Depending on the difference in performance between the first stage and second stages, we further reduced the size of buffers or, equivalently, the amount of bandwidth so 129 that the observed performance approaches the desired QoS requirements. The first stage is described next. 6.3.1 Bufl'er-Bandwidth Tradeoff for Data Traffic Consider Buffer 1 which accommodates cells from N1 data streams. The total band- width capacity allocated to these streams is CI. The offered load is given by: (1) (fl) AINI U1 ___ TONI-TOP? Ci (6.1) It is clear that U1 is inversely proportional to the amount of bandwidth per source (Cl /N1). For a fixed number of multiplexed streams, the cell loss rate depends on the buffer size and the allocated bandwidth per source. Hence, for a given loss rate, a tradeoff exists between the size of the buffer and the bandwidth allocated for each source. The cell loss rate for data traffic can be estimated analytically from the complementary buffer distribution computed using the fluid approach (see Chapter 4). This is shown in Figures 6.2 and 6.3 for N1 = 1 and N1 = 10, respectively. For a given N1, the cell loss probability can be reduced by increasing the buffer size (Bl) or by decreasing the offered load (i.e., increasing Cl/Nl). When U1 is reduced below a certain level, say Uf, the amount of bandwidth that is allocated for each source exceeds the peak rate of the source. In this case, buffering becomes unnecessary. The value of U; is given by: (1) ., U: = 0” = 20% (6.2) avg}. Figures 6.2 and 6.3 can be used to compute the possible sets of (buffer size, offered load) pairs that result in loss rate of 10'3; the QoS requirement for data sources. Such a buffer-bandwidth tradeoff is shown in Figure 6.4 for N = 1, 10 and 20. Notice 10 1o" 3 i. a i. 3 L _s 0 Approximate Cell Loss Probability 10 1 0‘7 L 4 1 4m 1 O 500 1000 1500 2000 2500 3000 3500 Buffer Size (In cells) Figure 6.2: Loss probability versus buffer size for data traffic with N1 = 1. 10 1 -1 i 10 1, e104? 1: a = : a : I g1o"- 1 i . . $10 a o . , a -5 g 10 1 2 5 O- . . 2’10-6 1 1o": 1 10“. l l l L I L ‘ 0 500 1000 1500 2000 2500 3000 3500 Buffer Size (h cells) Figure 6.3: Loss probability versus buffer size for data traffic with N1 = 10. 131 that the Y-axis in this figure indicates the buffer size per source, while the X-axis indicates the offered load, or equivalently, the inverse of bandwidth per source. Any point on each of the three curves will result in a loss rate of 10‘3. The choice of a particular buffer-bandwidth pair should be dictated by the available amount of buffer and bandwidth resources as well as their associated costs. Notice that the larger the number of multiplexed streams the smaller are the required amounts of buffer space and bandwidth. A considerable amount of buffers is needed when N; = 1 Multiplexing significantly reduces the required amount of buffer space per source. This reduction is particularly obvious when going from N1 = 1 to N1 = 10. 10 W r T T r 3 N=1 g10 EL - £102 in E B E 1 5 10 E S 10° l 10.1 J L 1 l l l l l 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7 0.75 Figure 6.4: Buffer-bandwidth tradeoff for data traffic. 6.3.2 Buffer-Bandwidth Tradeofl‘ for Voice Traffic Similar to data traffic, the cells loss rate for voice traffic can be computed analytically using the fluid approach. The relationship between the loss rate and the buffer size 132 can be approximated by the complementary distribution for the content of Buffer 2, as shown in Figures 6.5 and 6.6 for N2 = 1 and N2 = 10, respectively. 0 N=1 1o ‘ 1 I —r r I T I I T \_ F ‘ ~ ~ ‘ i \ .‘- ‘ ‘ ~ ~ - 1 -1‘ \ ",\.\ ‘ T \ 1O \ ' .\. ‘ ‘ s ‘ -: \ \ ~ ‘ \ § 3 ‘ \-\ F ‘ ~ - U2=90% ( .3: -2 \\ D‘ \ f ‘ ~ - i B10 \ \‘\ ~ ‘ ‘1: 3 \ '\ : e \ 'x. . a. 4 \ -. \_ .. \ £10 \\ '\‘ U2=8096 ? .J \ \.\ E E \ ' ‘ O _4 \ ‘ \ . 210 \ \. i g \ \_U2=70% : 7 \ \'\ I 2 _5 ‘ ‘-_U2=60% ' 4 $10 ‘ , ‘ i \ I \ . -e \ 10 ‘\U2=I50% - U2=40% \ . .4 1o" 050100150200250300350400450500 BuiferSize(incells) Figure 6.5: Loss probability versus buffer size for voice traffic with N2 = 1. For voice traffic the maximum offered load that guarantees a zero loss rate without any buffering is given by: U“ 7'82, 352 msec 2 — 7.512, + 7522.}, — 352 msec + 650 msec z 35% (6.3) By comparing Figures 6.5 and 6.5 to Figures 6.2 and 6.3, it can be observed that at a given offered load the loss rate for data traffic is much higher than that of voice traffic. This is because of the larger burstiness of a data stream, which can be measured by the ratio of the peak to mean arrival rates (or equivalently, the inverse of Uf). The optimal amount of resources which guarantees £2 for voice streams is shown __s E a 8 2 8 2 O 5.0 . 1 o 02=40% _ 1042 l L i 1 mm 0 100 200 300 400 500 600 Butler Size (in eels) Figure 6.6: Loss probability versus buffer size for voice traffic with N2 = 10. in Figure 6.7 (the solid curves) for N2 = 1, 10 and 20. Again, any point on each of the three solid curves will guarantee 62. Clearly, increasing N2 reduces the required amount of buffers and bandwidth per source. In addition to the loss requirement, voice cells require a maximum delay of d; _<_ D2. For U; > 35%, the maximum delay is determined by U2 and the buffer size (82): £2“, if U2 > 35% d2 = (6.4) 0, if U2 S 35% But (2) (fl?) A2N2 U2 = ON+ OFF (6.5) 02 134 Thus, the buffer-bandwidth tradeoff that guarantees d2 g D; is: (0.32M) ($31]? 5 D2 . (6-6) Using 0.352 sec as the time unit and an ATM cell as the data unit, the buffer— bandwidth tradeoff curves that guarantee the delay requirement are shown by the dotted lines in Figure 6.7, for D2 = 0.1 and D2 = 1 time units (notice that each curve is valid for any N2). For a given number of voice sources, the buffer-bandwidth operating region should be on the segment of the solid curve associated with N2, and which lies below the dotted delay curve (to guarantee the delay requirement). Required Number of Butlers/Source .2 1 o l l l l l L l l l 0.4 0.45 0.5 0.55 0.6 0 65 0.7 0.75 0.8 0.85 0.9 Offered Load Figure 6.7: Buffer-bandwidth tradeoff for voice traffic. 135 6.3.3 Buffer-Bandwidth Tradeoff for Video Traffic In the case of video traffic, obtaining the buffer-bandwidth tradeoff is more dificult than the previous two cases. First, we can only rely on simulations to obtain the relationships between cell loss rates and the amount of resources. Second and more importantly, the dimensioning problem involves, in addition to the buffer size, the threshold (T) which partitions the buffer pool into two portions: one that accom- modates all types of cells (i.e., I, P, and B) and the other is exclusive to the high priority cells (i.e., I cells). Our goal in this section is to describe how the buffer size Ba, the threshold value T, and the offered video load U3 can be optimized to provide the requested QoS requirements (£531), £532), and (Is). The results to be described below were obtained using N3 = 10. The same treatment can be carried for any number of video streams. To obtain the buffer—bandwidth tradeoff curves, consider first the interaction be- tween B3 and T at a given offered load. In theory, increasing T at a fixed B3 should result in decreasing 65,2) and increasing cg) (since less fraction of the total buffer space is exclusively reserved for I cells). On the other hand, fixing T and increasing B3 (1) 3 should clearly decrease c and, less obviously, increase 6&2). This is true because an increase in B3 means higher probability of admitting I cells to the buffer, which in turn will adversely affect the loss rate for low priority cells. However, if 69) and 6552) are orders of magnitude different, then the impact of increasing 3;; (at fixed T) on 632) is negligible. We verified our intuition by conducting several experiments in which B3 was varied at some fixed T. The output of these experiments is shown in Figure 6.8 using U = 40% and U = 80%, and different values of T. The above observation allows us to decompose the dimensioning problem into three stages. In the first stage, T is optimized to satisfy the a?) S 10‘2 requirement using an arbitrary large buffer size. Given the optimum T from the first stage, say T", the buffer size (83) is optimized in the second stage to satisfy the 69) S 10‘4 136 _3 U3=40% —1 U3=80% 1o . s r j 1 1o . a r ‘ ’ l b xT=20 1 i W l % T=40 ’ 0 ( E ‘ , .8 +T=80 , N , J “- s 3 * a x——x-——x - '3 O » o____._e__—.o . 2 .2 §1O4r 3" m if 1 g a .n 3 e-—e——o 3 9 s O. Q. a +———1-———+ 8 3 3 tram T2200 r OT=300 10.5 l I l l 10.2 l I I L 0 50 100 150 200 100 200 300 400 500 BulierSizeanoells) BuilerSlze(hoells) Figure 6.8: Loss probability for low priority (P and B) cells versus buffer size. -1 10 T r 4 I l l g i s 19. a. a 3 35 g i 0. E i -3 i 1 1° o 1000 1500 Tonoeils) Figure 6.9: Loss probability for low priority (P and B) cells versus threshold. 137 requirement. Finally, an additional buffer-bandwidth relationship is drawn to satisfy the delay requirement d3 S D3. Figure 6.9 depicts the cell loss rate for low priority cells (P and B) versus T using arbitrary large values for Ba and at different offered loads. Each experiment was replicated 10 times, each time using a different seed for the random number generator. The 95% confidence intervals are shown by the short vertical lines in the graph. The values for 83 which were used are: 200, 500, 600, 1000, and 1500 cells, at the corresponding offered loads: U3 = 0.6, 0.7, 0.8, and 0.9. Clearly, increasing U3 requires a drastic increase in T to maintain a cell loss rate in the range of 104. For video traffic, the maximum offered load which guarantees a zero loss rate at B3 = 0 is given by: _ average arrival rate of a stream _ 109.5 cells/frame U3 — _ 894 cells/frame = 12.2% (6.7) peak arrival rate of a stream Once T" is computed, we can now dimension the size of the buffer to satisfy 6&1). Using T = T" at different U3, simulations were conducted in which 83 was varied. Figure 6.10 depicts the loss rate for high priority cells (6:9)) versus Ba when T = T". In 6&2) was constantly observed to be around 104, as expected. all of these simulations, From Figure 6.10 the minimum value for B3, say 8;, that satisfies cg) S 10‘4 can be computed. These values are given in Table 6.1. U3 T; B; 40% 1 3 50% 3 7 60% 118 195 70% 404 487 80% 625 760 90% 1100 1230 Table 6.1: Optimal values for T3 and 83 that guarantee the QoS requirements. To satisfy the delay requirement d3 S D3, a similar buffer-bandwidth relationship 138 T=T 1 l 2 a 1 o . 3 1 u: .9 I .2 5‘ 3 .3 9 a. .1 : U3=60°k l 10“ l J l l l l 0 200 400 600 800 1000 1200 1400 Butler Size (ln cells) Figure 6.10: Loss probability for high priority (I) cells versus buffer size at T = T‘. to the data and voice cases can be obtained as follows: 1 B3 (1095) (N3) U3 _ D3, for U3 > U3 (6.8) Using (6.8) and the results in Table 6.1, the buffer-bandwidth tradeoff curves for video traffic can be obtained as shown in Figure 6.11. 6.3.4 Performance under a Work-Conserving Discipline In the previous sections, buffer and bandwidth resources in the N TCD / MB mech- anism were optimized to provide the given set of QoS requirements. However, to maintain tractable results, the optimization was carried under the assumption of non-work-conserving service discipline. From a practical point of view, it is often de- sirable to use a work-conserving discipline when cells are output from multiple buffers. 139 N 8 J .J 180 _ + buffer/source 4 a! threshold/source 160 l- / .1 $140 ' D3: 33 msec - Q g 120 r - s 1 '51 i- .l - 15 00 03: 10 msec .’ 3 / .’ / - 2 °°r 3 as“, .5 60.. l.’. - 0' ,- Q - . ‘5 401- ’x' J I" 20 " ‘l' .. ”IX 0 - "' - 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Offered Load Figure 6.11: Buffer-bandwidth tradeoff for video traffic. Intuitively, a work-conserving discipline should enhance the overall performance, or equivalently, maintain the same performance in a non-work-conserving discipline but using less amount of resources. Unfortunately, resource optimization in the under- lying 3-buffer system is not analytically tractable in the case of a work-conserving discipline. To provide efficient resource allocation for such a buffer system, we start with the optimal values for buffers and bandwidth in the non-work-conserving ver- sion. These values will serve as upper bounds to the optimal amount of resources in the work-conserving case. We then evaluate the performance using these values. If the performance is considerably better than the required QoS requirements, the values for buffer sizes and allocated bandwidth can be reduced until the performance is closer to the requested QoS requirements. In the following, we illustrate the above procedure by an example. Let N1 = N2 = N3 = 10 sources. Assume the same QoS requirements as before 140 with Dg = 352 msec and D3 = 33 msec. Suppose that the target offered loads for each type of traffic are: U1 = 50%, Ug = 60%, and U3 = 70%. From these values, we can compute the service rates C1, Cg, and C3 using, for example, ( 6.1). Accordingly, C1 = 943, Cg = 443, and C3 = 46928 (all in cells/ sec). The total link capacity is C = 01 + Cg + C3 = 48314 cells/ sec. Clearly, the amount of bandwidth to be allo- cated for video traffic is much larger than the bandwidth allocated for data or voice traffic. The large difference in the allocated bandwidth makes the gains from a work- conserving discipline vary from one traffic to another. For data and voice streams, a work-conserving discipline will drastically improve the queueing performance (com- pared to a non-work-conserving discipline). The reason is that when no video cells are in Buffer 3, a huge residual bandwidth (C3) will be used to switch voice and data cells in the other two buffers. Video traffic, on the other hand, will experience only a slightly better performance when the relatively small amounts of bandwidth (01 and Cg) are added to the service rate of Buffer 3. Typically, the N TCD / MB mechanism is implemented using a weighted round- robin discipline. This requires that the total service rate be transformed into an integer number of data units (q) per service cycle, and that the service rates guar- anteed to individual buffers be also some integers of data units, say ql, qg, and q3 (with q = q1 + qg + q3). In theory, these integer quantities can be the same as the above values for C, C1, Cg, and C3. However, this results in large blocking times at a given buffer when the server is busy switching cells from another buffer. Moreover, large counters would be needed to keep track of the cell counts. To reduce the block- ing times, it is better to slightly adjust the service rates so that the q.-s are kept as small as possible. We adjust the service rates to become: C1 = 1000, Cg = 500, and C3 = 47000 cells / sec. Based on these rates, a service cycle may consist of serving a 141 maximum of 100 cells (i.e., q = 100) from the three buffers such that: q1 = 2 cells qg = 1 cells qg, = 97 cells The adjusted service rates correspond to U1 = 0.47, Ug = 0.53, and U3 = 0.68. At these loads, the optimal buffer sizes (and the optimal T for the third buffer) under a non-conserving discipline can be obtained from the tradeoff curves in Figures 6.4, 6.7, and 6.11, and were found to be: 81 z 500 cells Bg z 50 cells B3 2"» 480 cells T x 380 cells Note, however, that these values are not necessarily optimal under a work- conserving discipline. Simulations of the (work-conserving) NTCD / MB mechanism were conducted used the above values for the buffers and the threshold. The above values for q, q], qg, and q3 were assumed. From 20 replications, the cell loss rates for the various types of cells were found to be as follows (confidence intervals are indicated as well): a = 01:0 ' (6.10) :5,” = 8.36 x 10-5 i 3.4 x 10"5 (6.11) .53) = 1.09 x10‘2 i 3.2 x 10-3 (6.12) 142 It is clear that the requested (203 are being satisfied (the delay requirements are being met by the choice of the buffer sizes). Moreover, the cell loss rates for data and voice streams are much smaller than needed, whereas the loss rates for video streams are, as expected, within the range of the requested QoS. Since it is sufficient to only provide the requested (203, we may further reduce the sizes of the data and voice buffers until their associated cell loss rates are in the ranges of the requested QoS. Simulations were used in which the values for BI and Bg were varied with 83 and T kept constant at their previous values. The results are summarized in Figure 6.12. L Cell Loss Rate 3 *E 3/ ___..L. I 0 5 1O 15 Buffer Size (in eels) 10 Figure 6.12: Cell loss rates versus buffer sizes for data and voice traffic. From this figure, we found the minimum values for B1 and Bg that guarantee the requested QoS requirements to be: B; m 12 cells B; m 8 cells 143 which are considerably less than the values obtained based on a non-conserving service discipline. Chapter 7 Summary and Future Research 7 .1 Summary In this thesis we introduced a new buffer management scheme for multimedia traflic in ATM networks. This scheme, referred to as NTCD / MB, is designed to support multiple grades of service that are often required in a heterogeneous multimedia traffic environment. N TCD / MB combines the use of loss and delay priority of the incoming traffic to support several sets of QoS requirements. It exhibits a simple cell admission and scheduling disciplines, which makes the mechanism easy to implement in hardware. Moreover, the mechanism provides guaranteed performance to several types of traflic while eficiently utilizing the available resources. We propose the use of NTCD / MB for buffer management at ATM switching and multiplexing nodes. We outlined the general structure of the NTCD / MB mechanism and evaluated its performance under various traffic scenarios. Preliminary investigation of the per- formance of N TCD / MB was carried via simulations assuming data and voice traffic streams. The MMPP model was used to characterize each type of traffic. Different cases were considered to demonstrate the flexibility of the NTCD / MB mechanism to adapt to various traffic mixes and different sets of performance requirements. 144 145 A complete analysis of the queueing performance of the NTCD / MB was provided using the fluid representation for the input streams. This analytical study was con- ducted for a particular structure of the NTCD / MB mechanism that consists of two buffers and a threshold. However, the same procedure can be applied to the analysis of any structure of the NTCD / MB mechanism. From this analysis, we obtained expres- sions for the steady-state probability distribution for the content of each buffer, the cell loss rate, the throughput, and an approximate waiting time distribution for each traffic type. Our approach can be used to analyze any dependent system of buffers in which the input traffic can be conveniently characterized by separable Markov- modulated fluid processes. Numerical results based on the analysis were supported by similar ones obtained via simulations. The fluid approximation is known to be particularly appropriate for data and voice streams. It can also be used to characterize compressed video streams that are generated by certain types of video encoders. Recent advances in video coding resulted in compression encoders that generate very complicated traffic patterns. Such patterns can not be adequately approximated by fluid models. Motivated by the desire to evaluate the performance of N TOD / MB under MPEG-compressed video streams (possibly along with other data and voice streams), we studied the characteristics of MPEG-compressed movies. Two models were developed to characterize an MPEG stream. The first model is based on the compression pattern and the distributions of the bit rates from the three types of MPEG frames. Bit rate variations due to scene changes are additionally incorporated in the second model. The two models capture several statistical properties of the empirical video data. More importantly, the queueing performance under synthetic streams generated by either model was , shown to be very close to the trace-driven performance. It was observed that the queueing performance under the second model is always slightly more conservative compared to the trace-driven performance. Since the main idea behind NTCD / MB 146 is to guarantee the performance, the second model was chosen to characterize video streams in the subsequent studies. Through a proof-of-concept study, we described (in Chapter 6) how to efficiently allocate buffer and bandwidth resources in the N TCD / MB mechanism. In that study, we combined our previous analytical and simulation results to compute the optimal buffer-bandwidth pairs that guarantee a set of requested QoS requirements under a non-work-conserving service discipline. Buffer—bandwidth tradeoff curves were es- tablished for the three examined types of traffic: data, voice, and video (MPEG- compressed). These curves were then used to provide conservative estimates for the optimal amounts of resources under a work-conserving discipline, which were subse- quently computed via simulations. 7 .2 Future Research 7 .2.1 Generalizing the Proposed Video Models The traffic models developed in Chapter 5 were based on one trace of empirical data and also using a particular compression pattern. This is due to the excessive amount of time that is required to capture and compress video frames (it took six weeks to digitize and store the frames and three weeks to compress them). Parameters of both models were obtained by matching certain statistics of the model to their correspondents in the empirical trace. Hence, these parameters are specific to the examined video trace, i.e., a different movie is expected to result in different values for these parameters. Moreover, using a different compression pattern to generate an MPEG steam may also result in different values for the model parameters. Our objective is to develop a procedure to estimate the parameters of each model to fit a given movie. Only few information about the movie should be needed to estimate the values for the parameters of either model. Such information could include 147 the compression pattern, the dimensions of the frame, and the “level of dynamics” of the movie. This last requirement implies that movies should be classified into a small number of classes based on their level of scene activity. Movies belonging to a given class and that have the same compression pattern and image dimensions will probably result in similar values for model parameters. Clearly, to achieve our goal, we need to consider a large number of movies to be individually compressed according to various compression patterns. 7 .2.2 Analyzing the Queueing Performance of MPEG Streams The queueing performance for MPEG streams was obtained in this thesis via simula- tions. For cell loss rates below 10'6, simulations become computationally impractical. Analytical results, if tractable, provide a very efficient and inexpensive means of ob- taining very small loss rate performance. Unfortunately, exact queueing analysis does not seem possible for any of the proposed models. Instead, approximate bounding approaches are more promising for analysis purposes. We intend to further explore this possibility. One may, for example, assume that MPEG frames of a certain type (I, P, or B) have the size of the largest frame of their type. The three maximum sizes may be provided apriorz' or estimated. Accordingly, a video stream is approximately described by the three maxima and the compression pattern. This characterization has more potential for queueing analysis than a more accurate characterization that is provided by any of the proposed models. Bibliography [1] T. G. Alliance. The U.S. HDTV standard: the Grand Alliance (special report on digital TV). IEEE Spectrum, pages 36—45, Apr. 1995. [2] D. Anick, D. Mitra, and M. M. Sondhi. Stochastic theory of a data-handling system with multiple sources. Bell System Technical Journal, 61(8):1871—1894, Oct. 1982. [3] J. J. Bae and T. Suda. Survey of trafic control schemes and protocols in ATM networks. Proceedings of the IEEE, 79(2):1871-1894, Feb. 1991. [4] J. Banks and J. S. Carson. Discrete-Event System Simulation. Prentice-Hall, Inc., first edition, 1984. [5] G. E. P. Box and G. M. Jenkins. Time Series Analysis: Forcasting and Control. Holden-Day, Inc., 1976. (Revised Edition). [6] A. W. Bragg and W. Chou. Analytic models and characteristics of video traffic in high speed networks. In Proceedings of International Workshop on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MAS- COTS ’94), pages 68-73, Durhan, North Carolina, Jan. 31 — Feb. 2 1994. [7] S. K. Chan and A. L. Garcia. Analysis of cell inter-arrival from VBR video codecs. In Proc. of IEEE INF OCOM ’94, volume 1, pages 350—357, 1994. [8] T. M. Chen, J. Walrand, and D. G. Messerschmitt. Dynamic priority protocols for packet voice. IEEE Journal on Selected Areas in Communications, 7(7), June 1989. [9] R. Chipalkatti, J. F. Kurose, and D. Towsley. Scheduling policies for real-time and nonreal-time traffic in a statistical multiplexer. In Proceedings of IEEE INF OCOM ’89, pages 774—783, 1989. [10] M. De Prycker. Evolution from ISDN to BISDN: a logical step towards ATM. Computer Communications, 12(3):141—146, 1989. [11] S. Dravida and K. Sriram. End-to-end performance models for variable bit rate voice over tandem links in packet networks. In Proc. of IEEE INF OCOM ’89, pages 1089—1095, 1989. 148 149 [12] A. I. Elwalid and D. Mitra. Fluid models for the analysis and design of sta tistical multiplexing with loss priorities on multiple classes of bursty trafic. In Proceedings of IEEE INF OCOM ’92, pages 3c.4.1—3c.4.11, 1992. [13] A. I. Elwalid, D. Mitra, and T. E. Stern. Statistical multiplexing of Markov modulated sources: Theory and computational algorithms. In Proceedings of 13th International Teletrafi‘ic Congress (ITC), June 1992. [14] W. Fischer and K. Meier-Hellstern. The markov-modulated poisson process (MMPP) cookbook. Performance Evaluation, 1(18):149—171, 1993. [15] V. S. Frost and B. Melamed. Traffic modeling for telecommunications networks. IEEE Communications Magazine, 32(3):70—81, Mar. 1994. [16] J. Garcia and O. Casals. Priorities in ATM networks. In Proc. of NATO Work- shop on Architecture and Performance issues of high capacity local and metropoli- tan networks, June 1990. [17] M. W. Garrett and W. Willinger. Analysis, modeling, and generation of self- similar VBR video traffic. Computer Communication Review (SIGCOMM’94 Conference Proceedings), pages 269—280, Sept. 1994. [18] M. Ghanbari. Two-layer coding of video signals for VBR networks. IEEE Journal on Selected Areas in Communications, 7(5):77l—781, June 1989. [19] D. J. Goodman. Embedded DPCM for variable bit rate transmission. IEEE Transaction on Communications, 28:1040—1046, July 1980. [20] A. Gravey and G. Hebuterne. Analysis of a priority queue with delay and/or loss sensitive customers. In Proc. of I TC Broadband Seminar, Oct. 1990. [21] R. Grunenfelder, J. P. Cosmos, S. Manthorpe, and A. Odinma-Okafor. Charac- terization of video codecs as autoregressive moving average processes and related queueing system performance. IEEE Journal on Selected Areas in Communica- tions, 9(3):284—293, Apr. 1991. [22] H. Heffes and D. M. Lucantoni. A Markov modulated characterization of packe- tized voice and data traffic and related statistical multiplexer performance. IEEE Journal on Selected Areas in Communications, SAC-4(6):856—868, Sept. 1986. [23] D. P. Heyman and T. V. Lakshman. Source models for VBR broadcast-video traffic. In Proc. of IEEE INF OCOM ’94, volume 2, pages 664—671, 1994. [24] D. P. Heyman, A. Tabatabai, and T. V. Lakshman. Statistical analysis and simulation study of video teleconferencing traffic in ATM networks. IEEE Trans. on Circuits and Systems for Video Technology, 2(1):49-59, Mar. 1992. [25] T. Hou and A. Wong. Queueing analysis for ATM switching of mixed continuous- bit-rate and bursty traffic. In Proc. of IEEE INF 000M ’90, pages 660—667, 1990. 150 [26] ISO / MPEG. ISO CD11172—2: Coding of moving pictures and associated audio for digital storage media at up to about 1.5 mbits/s, Nov. 1991. [27] ISO / MPEG II. ISO CD11172—2: Coding of moving pictures and associated audio, Dec. 1992. [28] D. L. J agerman and B. Melamed. The transition and autocorrelation structure of TES processes part I: General theory. Stochastic Models, 8(2):193—219, 1992. [29] D. L. ’Jagerman and B. Melamed. The transition and autocorrelation structure of TES processes part II: Special cases. Stochastic Models, 8(3):499-527, 1992. [30] R. Jain and S. Routhier. Packet train — measurements and a new model for computer network traffic. IEEE Journal on Selected Areas in Communications, Sept.1986. [31] N. S. Jayant and S. W. Christensen. Effects of packet losses in waveform coded speech and improvements due to an odd-even sample-interpolation procedure. IEEE Transaction on Communications, 29:101—109, Feb. 1981. [32] F. Kishino, K. Manabe, Y. Hayashih, and H. Yasuda. Variable bit-rate coding of video signals for ATM networks. IEEE Journal on Selected Areas in Commu- nications, 7(5):801—806, June 1989. [33] L. Kosten. Stochastic theory of data-handling systems with groups of multi- ple sources. Performance of Computer-Communication Systems, pages 321-331, 1984. [34] H. Kroner. Comparative performance study of space priority mechanisms for ATM channels. In Proc. of IEEE INF OCOM ’90, pages 1136—1143, 1990. [35] H. Kroner, G. Hebuterne, P. Boyer, and A. Gravey. Priority management in ATM switching nodes. IEEE Journal on Selected Areas in Communications, 9(3):418—427, Apr. 1991. [36] M. Krunz and H. Hughes. Analysis of a Markov-modulated fluid flow model for multimedia traffic with loss and delay priorities. Journal of High Speed Networks, 3(3):309—329, 1994. 103 Press. [37] M. Krunz and H. Hughes. A performance study of loss priorities for MPEG video traffic. In in Proc. of IEEE ICC ’95 Conference, June 1995. [38] M. Krunz and H. Hughes. A traffic model for MPEG-coded VBR streams. In Proc. of the ACM SIGMETRICS/PERFORMANCE ’95 Conference, pages 47- 55, May 1995. [39] M. Krunz, H. Hughes, and P. Yegani. Congestion control in ATM networks using multiple buffers and priority mechanisms. In Proc. of the Summer Computer Simulations Conference, pages 566—571, Boston, MA, July 1993. 151 [40] M. Krunz, H. Hughes, and P. Yegani. Traffic control in ATM switching using multiple buffers and nested threshold cell discarding. In Proc. of 2’nd Int. Conf. on Computer Communications and Networks (IC3N), pages 121—127, San Diego, California, June 1993. [41] M. Krunz, H. Hughes, and P. Yegani. Design and analysis of a buffer management scheme for multimedia traffic with loss and delay priorities. In Proc. of the IEEE CLOBE'COM ’94, pages 1560-1564, San Francisco, CA, Nov. 1994. [42] M. Krunz, R. Sass, and H. Hughes. Statistical characteristics and multiplexing of MPEG streams. In Proc. of the IEEE INFOCOM ’95 Conference, pages 455-462, Boston, Apr. 1995. [43] M. Krunz, R. Sass, and H. Hughes. A study of VBR MPEG-coded video traf- fic and associated multiplexing performance. Computer Systems Science and Engineering Journal, 1995. CRL Publishing Ltd. (in press). [44] J. Kurose. Open issues and challenges in providing quality of service guarantees in high—speed networks. Computer Communication Review, ACM/SIGCOMM, 23(1):6-15, Jan. 1993. [45] A. M. Law and W. D. Kelton. Simulation Modeling and Analysis. McGraw-Hill, Inc., second edition, 1991. [46] A. A. Lazar, G. Pacifici, and D. E. Pendarakis. Modeling video sources for real-time scheduling. Technical Report 324—93-03, Columbia University, De- partment of Electrical Engineering and Center for Telecommunications Research, Apr. 1993. [47] D. Le Gall. MPEG: A video compression standard for multimedia applications. Communications of the ACM, 34(4):47-58, Apr. 1991. [48] W. E. Leland, M. S. Taqqu, W. Willinger, and D. V. Wilson. On the self- sirnilar nature of Ethernet traffic (extended version). IEEE/A CM Transactions on Networking, 2(1):1-15, Feb. 1994. [49] Y. Lim and J. Kobza. Analysis of a delay-dependent priority discipline in a multiclass traffic packet switching node. In Proc. of IEEE INF 000M ’88, pages 9A.4.1—9A.4.1.10, 1988. [50] A. Y.-M. Lin and J. A. Silvester. Priority queueing strategies and buffer allo- cation protocols for traffic control at an ATM integrated broadband switching system. IEEE Journal on Selected Areas in Communications, 9(9):1524—1536, Dec. 1991. [51] M. L. Luhanga. A fluid approximation model of an integrated packet voice and data multiplexer. In Proc. of IEEE INF OCOM ’88, pages 7A.4.1-7A.4.6, 1988. 152 [52] B. Maglaris et al. Performance models of statistical multiplexing in packet video communications. IEEE Journal on Selected Areas in Communications, 36(7):834—844, July 1988. [53] N. M. Marafih, Y.-Q. Zhang, and R. L. Pickholtz. Modeling and queueing anal- ysis of variable-bit-rate coded video sources in ATM networks. IEEE Trans. on Circuits and Systems for Video Technology, 4(2):121—128, Apr. 1994. [54] B. Melamed. TES: A class of methods for generating autocorrelated uniform variates. ORSA Journal on Computing, 3(4):317—329, 1991. [55] S. E. Minzer. Broadband ISDN and Asynchronous Transfer Mode (ATM). IEEE Communications Magazine, 27(9):]7-24, Sept. 1989. [56] D. Mitra. Stochastic theory of a fluid model of producers and consumers coupled by a buffer. Advances in Applied Probability, 20:646-676, 1988. [57] R. W. Muise, T. J. Scheonfeld, and G. H. Zimmerman. Experiments with wide- band packet technology. In Proc. of International Zurich Seminar on Digital Communications, Mar. 1986. (paper D4). [58] P. Pancha and M. El Zarki. MPEG coding for variable bit rate video transmis- sion. IEEE Communications Magazine, 32(5):54—66, May 1994. [59] D. W. Petr, L. A. DaSliva, Jr., and V. S. Frost. Priority discarding of speech in integrated packet networks. IEEE Journal on Selected Areas in Communications, 7(5):644-659, June 1989. [60] D. W. Petr and V. S. Frost. Nested threshold cell discard for ATM overload control: optimization under cell loss constraints. In Proc. of IEEE INF OCOM ’91, pages 12A.4.1—12A.4.1.10, Bal Harbour, 1991. [61] G. Ramamurthy and B. Sengupta. Modeling and analysis of a variable bit rate video multiplexer. In Proc. of IEEE INF OCOM ’92, volume 2, pages 817-827, 1992. [62] P. Sen, B. Maglaris, N.-E. Rikli, and D. Anastassiou. Models for packet switching of variable-bit-rate video sources. IEEE Journal on Selected Areas in Commu- nications, 7(5):865-869, June 1989. [63] P. Skelly, M. Schwartz, and S. Dixit. A histogram-based model for video traf- fic behavior in an ATM multiplexer. IEEE/A CM Transactions on Networking, 1(4):446—459, Aug. 1993. [64] K. Sohraby. On the theory of general ON-OFF sources with applications in high-speed networks. In Proceedings of IEEE INF OCOM ’93, pages 401—410, 1993. 153 [65] K. Sriram and W. Whitt. Characterizing superposition arrival processes in packet multiplexers for voice and data. IEEE Journal on Selected Areas in Communi- cations, SAC—4(6):833—846, Sept. 1986. [66] T. E. Stern and A. I. Elwalid. Analysis of separable Markov-modulated rate mod- els for information-handling systems. Advances in Applied Probability, 23:105- 139, 1991. [67] R. C. F. Tucker. Accurate method for analysis of a packet-speech multiplexer with limited delay. IEEE Transaction on Communications, 36(4):479—483, Apr. 1988. [68] J. S. Turner and L. F. Wyatt. A packet network architecture for integrated services. In Proceedings of IEEE GLOBECOM ’83, pages 2.1.1—6, 1983. [69] D. Verma, H. Zhang, and D. Ferrari. Guaranteeing delay jitter bounds in packet- switched networks. In Proc. of T riComm ’92, Apr. 1991. (Chapel Hill, NC). [70] G. Woodruff and R. Kositpaiboon. Multimedia traffic management principles for guaranteed ATM network performance. IEEE Journal on Selected Areas in Communications, 8(3):437—446, Apr. 1990. [71] V. Yau and K. Pawlikowski. ATM buffer overflow control: A Nested Threshold Cell Discarding with Suspended Execution. In Proc. of Australian Broadband Switching and Services Symp., Melbourne, July 1992. [72] P. Yegani. Performance models for ATM switching of mixed continuous bit rate and bursty traffic with threshold based discarding. In Proc. of IEEE ICC ’92, pages 1621—1627, June 1992. [73] P. Yegani, M. Krunz, and H. Hughes. Congestion control schemes in prioritized ATM networks. In Proc. of IEEE ICC ’94, pages 1169-1173, May 1994. [74] F. Yegengolu, B. Jabbari, and Y.-Q. Zhang. Motion-classified autoregressive modeling of variable bit rate video. IEEE Trans. on Circuits and Systems for Video Technology, 3(2):42—53, Feb. 1993. [75] N. Yin, S.-Q. Li, and T. E. Stern. Congestion control for packet voice by selective packet discarding. In Proc. of IEEE GLOBECOM ’87, pages 45.31—45.34, 1987. [76] N. Yin, S.-Q. Li, and T. E. Stern. Data performance in an integrated packet voice/ data system using voice congestion control. In Proc. of IEEE GLOBECOM ’88, pages 16.4.1—16.4.5, 1988. [77] N. Yin, T. E. Stern, and S.-Q. Li. Performance analysis of a priority-oriented packet voice system. In Proc. of IEEE INF OCOM ’87, pages 856-863, 1987. [78] J. Zhang. Performance study of Markov modulated fluid flow models with pri- ority traffic. In Proc. of IEEE INF OCOM ’93, pages 1a.2.1-1a.2.8, 1993. HICHIGQN RT \\\\\\\\lllllllll\\\\\\l\\\l]\l]\l2\\l 3129301