To accommodate more general shapes of the CTMC with finite-state space [40] are among the simplest correlation functions, Li and Hwang [43,44] propose the extensions to the renewal process model for incorporating application of linear systems analysis using power spectral temporal dependence. The traffic correlation structure representation of traffic. By the Markov property, the probability of transitioning of a resource that is subject to random usage patterns.
These one-step transition link of finite capacity. The elements allowed to queue in a buffer when the channel is busy. In a continuous time Statistical multiplexing gains come at the expense of Markov chain, the transition rates are captured by an a packet loss or delay probability that is considered tolerable for the applications being transported.
The infinitesimal generating matrix QY containing elements performance constraint is typically specified by the qij that represent the transition rate from state Si to acceptable probability of loss for a given buffer size B. In this case, the sum of the rates in In some cases an infinite buffer queue is analyzed for each row is equal to zero.
For the the rate of decay in the autocorrelations of the Markov limiting case of zero buffer size, the probability of loss chain. In the context of modeling traffic arrivals the may be calculated by determining the probability of the transition matrix is supported by a K-state rate vector aggregate input rate exceeding the capacity.
The approaches to performance analysis in the litera- 1. The multiplexing of packet voice with data using two state Markov chains to model the ON and OFF states and the application of 1. With 1. Models 1. The Markov repre- sentation for packet video typically required a large state 1.
As a result, several approximation method- 1. These approximations have been 0 particularly useful in formulating admission control deci- Buffer occupancy x sions for multiservice networks. Figure 1. Brady [57] presented experimental measurements of approximations.
This leads to a discussion of admission the average durations of ON and OFF periods and transition control algorithms with particular focus on the effective rates between these states from a study of telephone con- bandwidth approximations. Voice and Data Multiplexers a function of users, language, and other such factors.
Aver- In the early s integrated services digital networks age length of talk and silence spurts are in the 0. The digital telephone characterizing speech-based applications, although the network with a basic transmission rate of 64 kbps kilobits silence durations are seldom exponentially distributed. Different local user interfaces were standardized states can be significantly different for voice and data to connect end systems such as telephones, data terminals, sources.
The alternating talk spurts and silence durations or local area networks to a common ISDN channel. At any of speech applications exhibit relatively slow transition given time, the traffic generated on this link could be a rates, allowing the data to be multiplexed in the OFF mix of data, voice, and associated signaling and control periods. Data sources exhibit faster transitions between information.
The performance requirements of voice and active and inactive states. A problematic feature in packet data traffic [46] govern the design of the multiplexing voice traffic is its temporal correlation which is induced by system. The buffer overflow probability is a chief concern speech encoders and voice activity detectors [29,30]. As a for data transmission, whereas bounding transmission result of multiplexing with voice in a queue, the departing delay is critical for speech signals [47].
This feature influences the performance of assumed fixed duration time-division multiplexing frames other multiplexers in the transmission path. In this context, the multiplexing features of multiplexed voice and data traffic using a efficiency of voice and data has been analyzed using two-state Markov modulated Poisson process MMPP. Maglaris and discussed. Sriram and Whitt [29] extract the dependence Schwartz [55] describe a variable-frame multiplexer that features of aggregate voice packet arrival process from admits long messages of variable length and single packets a highly variable renewal process model of a single that arrive as a Poisson process.
The Poisson model voice source. The aggregation of multiple independent is assumed to impose a degree of traffic burstiness on voice sources is examined using the index of dispersion the otherwise continuous rate process. The ability to of intervals IDI. The motivation behind this approach adapt frame sizes in response to traffic variations showed is that the limiting value of IDI as number of sources improved performance in terms of bandwidth utilization tend to infinity completely characterizes the effect of the and delays relative to fixed-frame movable-boundary arrival process on the congestion characteristics of a FIFO schemes.
The system requirements for multiplexing data queue in heavy traffic. This work also shows that the during silence periods of speech is presented by Roberge positive dependence in the packet arrival process is a and Adoul [56]. In this work the accurate discrimination major cause of congestion in the multiplexer queue at of speech and data signals is proposed using statistical heavy loads.
Buffer sizes larger than a critical value as pattern classification algorithms based on zero-crossing determined by the characteristic correlation time scale statistics of the quadrature-amplitude-modulated speech will allow a sequence of dependent interarrival times signal. A speech-data transition detector is proposed for to build up the queue, causing congestion. Limiting the detecting switching points in time with accuracy. These pioneering These applications generate bursts of activity separated by studies provided a comprehensive understanding on the random durations of inactive periods.
Speech patterns in efficiency of synchronous and asynchronous approaches for telephone conversations are also characterized by random multiplexing voice and data traffic on a common channel. In this regard, The transport of variable bit rate VBR video finite-state Markov processes were found to be amenable using statistical multiplexing has been examined in in both capturing some of the dependence features and numerous studies.
VBR video is preferred over traditional allowing tractable analysis of the multiplexer queues. Statistical measurements and measurement based models did not multiplexing invariably results in buffering delays and play a prominent role in analysis of multiplexers.
However, losses, which can significantly degrade video quality. To with transition from ISDN to B-ISDN and the recognition minimize the amount of delay and loss, the networking that simple two-state Markov models are inadequate for community has focused on the development of effective broadband sources, more emphasis has been placed on and implementable congestion control schemes, including measurement based analysis of video and data traffic.
To minimize the impact of delay and loss, the discussed next. Video Models and Multiplexers coding algorithms [61,62] for use in combination with the dual-priority transport provided by ATM networks. Although current compres- generally invisible, even to experienced viewers [63].
Figure 2 s segments of low-activity videophone signals. A first depicts a comparison of the temporal variation of mea- order autoregressive AR process was proposed for the sured video frame rates for a low-activity videoconference number of bits in successive video frames of a single source. The signals represent the Markov process. In this model, transitions are limited to number of bits in each encoded video frame as a function neighboring states. The model parameters were selected of the frame index.
The large dispersions about a mean to match the mean and short-term covariance structure rate are evident, as are the sudden transitions in frame in the measurements. The states of the Markov chain a Video frame rate 0 0 Frame index, n b Video frame rate 0 Frame index, n Figure 2. Sample paths of VBR video in videoconferencing and entertainment applications.
A choice of various combinations of the quantization parameter, the 20 levels per source was found adequate for the low- inter-to-intraframe ratio and the priority breakpoint in activity videoconferencing source. Sen et al. The resulting source model is equivalent to on the ratio of peak rate to the standard deviation of the that obtained by superposition of independent ON — OFF frame rates.
Frater et al. Grunenfelder et al. The superposed video process was assumed to different buffer sizes. Krunz and Hughes [78] modeled be wide sense stationary.
The multiplexer was modeled MPEG, with distinct models for each different frame using a general arrival process with independent arrivals type. The selection of an adequate number of states in and deterministic service times. A source model for full the Markov chain model of video such as to adequately motion video was presented by Yegenoglu et al. Reibman [79]. Adequate spectral content in single sources The selection of the coefficients was based on the state is found necessary to understand the scaling aspects of of a discrete-time Markov chain.
The transition and Markov models under multiplexing. Moderate-activity videoconference data and others [77,81]. Ryu and Elwalid [82] show that long- were also modeled by Heyman et al. The rate term correlations do not significantly affect network per- evolution was modeled by a Markov chain with identical formance over a reasonable range of cell losses, buffer transition probabilities in each row. These probabilities sizes, and network operating parameters.
Grossglauser were modeled as a negative binomial distribution. The and Bolot [83] also propose that correlation timescales number of states in the model was of the order of the to be considered in the traffic depend on the operating peak rate scaled by a factor of This ranged from parameters and that full long-range dependence charac- to states. The within state correlations were terization of traffic is unnecessary. The impact of temporal modeled by a discrete AR DAR process that resulted in correlation in the output rate of a VBR video source on a diagonally dominant matrix structure.
This structure the queue response has been examined [43], and it has did not model single-source statistics very well since there been shown that macrolevel correlations can be modeled were no selective transitions between states based on by Markov-chain-based models. Long-range dependence source characteristics. The DAR model failed to capture seen in VBR video has also been examined and the queue- the short-term correlations in the traffic of a single ing results have been compared to those obtained using source.
Lucantoni et al. Results buffer sizes, the short-range correlations obtained using of this model show that burstiness in video data can Markov chain models are sufficient to estimate the buffer be captured more accurately than in the DAR model. Although the MRP was shown to perform better than the The aforementioned studies have determined that DAR model in capturing the burstiness, the MRP still did correlations on many timescales are an inherent feature not match the cell loss probabilities for large buffer sizes.
The sources and concluded that their DAR model proposed for ubiquitous use of multistate Markov models has led to videoconference sources could not be applied as a general work on their performance in queues. The application of model to all sources.
Skelly et al. They determined, on the basis of simulation, that with an increase in the number of multiplexed that a fixed number of eight states were sufficient to model video sources and corresponding increase in the channel the video source.
It was shown role in shaping the temporal and amplitude variation of that typically 15—20 states are required to faithfully model compressed video. Traffic shaping algorithms at policing the queue behavior of moderate to high-activity video systems that enforce constraints on the output rate of sources. When using too few states, the tail probabilities the encoding system also play an important role in of the rate histogram will not be captured, thereby yielding shaping digital video traffic [72—74].
In general, the coder an underestimate of the packet delay or loss probability. The idea that encoders could be The performance analysis of queues driven by large- constrained to generate traffic described by Markov chains dimensional Markovian traffic sources may be approached was explored by Heeke [75] for designing better traffic using exact queueing analysis in discrete time and discrete policing and control algorithms. Pancha and Zarki [76] state space. In the limit of a large number of state probability of the multiplexed source being in state sources operating in the heavy-traffic regime, the discrete i.
For a buffer of finite size, all of the eigenvalues are arrival and departure times may be replaced by a fluid retained and boundary condition at infinity replaced by approximation. This analysis technique is discussed in the the corresponding value at the buffer size.
The aforementioned approach requires the solution of an eigenvalue problem for a matrix whose upper 3. To counter this dimensionality problem, reduced order traffic models Fluid flow models assume that the packet arrival process have been used as approximations.
For two-state ON — OFF at a multiplexer occurs continuously in time and may Markov processes the superposition yields a generator be characterized by continuous random fluctuations in the arrival rate [87]. This approach is applicable when of O N states. Multi-state Markov sources have been the packet sizes are small relative to the link capacity. The number of two-state in multiplexers fed by Markov modulated fluid sources sources selected for this model is often an arbitrarily and served at constant rate.
In this method, the buffer choice. For moderate to high-activity video sources, this occupancy X is assumed to be a continuous valued approximation can be shown to underestimate the packet random variable. The arrival process of each source is delays. A traffic source represented by a single source, and N is the number of sources assumed finite-state Markov chain exhibits temporal autocorrela- identical being multiplexed, the superposition can be tions that decay exponentially in time.
Packets in the buffer the traffic model. High-activity video sources often require are serviced on a first-in first-out basis at a constant K to be in the range of 15—20 states. Figure 3 shows the service rate. The cumulative probability distribution of effect of choosing an inadequate number of states K for the buffer occupancy x in steady state is specified by modeling the H. For a service rate of totic decay rate of the complementary delay distribution C packets per second, the probabilities satisfy the equation approaches that exhibited by the measurements.
Here I is the identity matrix. The Thompson et al. The reduction process involved the solution of Eq. The coefficients ai x are functions of the buffer sizes and small delay or loss probabilities [92].
Effective Bandwidths and Admission Control Network traffic measurements have identified application and system dependent features that influence the traffic characteristics.
Characterization in terms of the mean traffic rate is inadequate because of the large variability in its value over time. As traffic mixes and their One Std. Interval 0. Admission and usage control policies are two proposals in place in ATM networks and the next-generation Internet An admission control process determines if a source requesting connection H.
Influence of number of states K chosen to model video disparate traffic and service characteristics. Multiplexing source. The performance of five classes of admission control algorithms is reviewed by Knightly and Shroff [99]. These classes include scheduling based of all the eigenvectors and eigenvalues of the system. Although most of the from large deviation principles [], and maximum asymptotic representations have considered Markovian variance approaches based on estimating the upper tails sources, there have been some results for traffic modeled of Gaussian process models of traffic [95].
A overview of as stationary Gaussian processes [95] and fractional the EB and its refinements is presented, since it appears Brownian motion [96]. This allows a very usable descriptor into a node served by a link capacity C packets per second. This capacity is referred to ments of each class and available capacity C.
Defining the as the effective bandwidth EB of the multiplexed traffic generated by type i source on a timescale t by a source.
It was shown that the asymptotic where the parameter s is related to the decay rate of G x constant was itself asymptotically exponential in the and captures the multiplexing efficiency of the system.
For traffic sources It is calculated from the specified probability of loss with indices of dispersion greater than Poisson, this or delay bounds [89]. The term on the right is the log parameter decreased exponentially in N, reflecting the moment generating function of the arrival process. The multiplexing gain of the system.
The application of workload can be described over a time t that represents these approximations in designing efficient multiplexing the typical time taken for the buffer to overflow starting systems through admission control is discussed next.
The characterization of a traf- and peak values of Ai [0, t]. Methods for deriving Ei for different traffic Derived in the asymptotic limit of large number of multi- classes are discussed by Chang [].
The aforementioned plexed sources, large buffer sizes and link capacities and model assumes that all the multiplexed sources have small probabilities of delay and loss, effective bandwidths the same quality of service requirements.
If not, all offer a conservative, but computationally feasible model for sources achieve the performance of the most stringent evaluating multiplexing efficiency in theory. The design of source. Kulkarni et al. She is currently an 4. Chandra The multiplexing issues in the early s were concerned received the Eta Kappa Nu Outstanding Electrical with voice and data integration on kbps telephone Engineer Award honorable mention in and the channels. Her tiplexing using moving boundaries between voice and research interests are in the areas of network traffic and data slots, silence detection for insertion of data pack- performance analysis, wireless networks, acoustic and ets, and development of adaptive speech encoders were electromagnetic wave propagation, adaptive estimation the primary concerns in designing efficient multiplexers.
ATM networks were envisioned to integrate and optimize 1. ITU-T, Recommendation i. ATM related paradigms such as traffic characterization, 4. The important open issues at present are robust char- 5.
Clark, S. Shenker, and L. Zhang, Supporting real- time applications in an integrated services packet network: acterization of traffic and the derivation of traffic models Architecture and mechanism, Proc. With pp. On the contrary, traffic measurements 7. Eichler, Implementing integrated and differentiated indicate that deterministic patterns and nonlinearities in services for the Internet with ATM networks: A practical traffic amplitudes are new prevailing features in broad- approach, IEEE Commun.
Large-dimensional stochastic models are 8. Zhang et al. Frost and B. Melamed, Traffic modeling for telecom- Cooper, Introduction to Queueing Theory, 3rd ed. Sriram and W. Whitt, Characterizing superposition Jagerman, B. Melamed, and W.
Willinger, Stochastic arrival processes in packet multiplexers for voice and data, modeling of traffic processes, in J. Dshalalow, ed. Areas Commun. Heffes and D. Lucantoni, A Markov-modulated char- Areas conversations, Nyt Tidsskrift Matematik B 33 English translation in E.
Brockmeyer, H. Halstrom and Eckberg, Jr. Jensen , The life and works of A. Erlang, The processes, 10th Int. Teletraffic Congress, Copenhagen Telephone Company, Copenhagen. Coffman and R. Wood, Interarrival statistics for ed arrival queueing delays based on generalized peaked- time sharing systems, Commun.
ACM 9: — Jackson and C. Stubbs, A study of multi-access Cox and P. Fredericks, Congestion in blocking systems — a simple Fuchs and P. Jackson, Estimates of distributions of approximation technique, Bell Syst.
ACM — Livny, B. Melamed, and A. Tsiolis, The impact of Pawlita, Traffic measurements in data networks, autocorrelation on queueing systems, Manage. Roberts, ed. Jain and S. Norros, J. Roberts, A. Simonian, and J. Virtamo, Schoch and J.
ACM 23 12 : — Murray and P. Roberts and J. Virtamo, The superposition of Mag. Tobagi, Modeling and measurement techniques in packet communication networks, Proc. IEEE — Anick, D. Mitra, and M. Sondhi, Stochastic theory of a Paxson and S. Cinlar, Introduction to Stochastic Processes, Prentice- — Hall, Englewood Cliffs, NJ, Caceres, P.
Danzig, S. Jamin, and D. Mitzel, Character- Meier-Hellstern, P. Wirth, Y. Yan, and D. Hoe- Fischer and K. Jensen and V. Iversen, eds. Li and C.
Hwang, Queue response to input cor- Publishers, , pp. The burstiness b is defined as the bit rate produced by the N sources: peak to mean bit rate ratio i. We will represent the cell length in bits by The expansion factor gives us a measure of the ncell. Furthermore, unless otherwise specified, we excess bandwidth relative to the average that will express the burst average length L and the must be assigned to the incoming traffic in order multiplexer buffer size K in number of cells.
For single type bursty traffic sources, a peak 2. Some traffic sources are neither strictly bursty with active periods alternated with silence peri- ods , nor continuous bit rate. One example is 4. Although video could be Several models were proposed in the literature transmitted at continuous rate, a differential, VBR for the analysis of bursty traffic.
For a survey of changes on a frame by frame basis between a models and their references see [10]. Other results minimum and a maximum bit rate. In Section 5 we present the analysis of the For bursty traffic, R is a function of: the multiplexing of a video-phone source traffic. Recently, Gallassi et al. Bandwidth assignment problem independent of the particular value of the peak bit rate Bp.
In this paper, we show that R depends We formulate the bandwidth assignment prob- on L and K only through their ratio. Solution approach assigned to this mix of traffic in order to satisfy a given Grade of Service GOS requirement. For a given bandwidth allocation, number of The mixt of the N distinct type sources is identical bursty sources, and buffer size, the cell represented by the tuple nl, n Thus, our algorithm searches for the appropriate value of bandwidth using a logarith- mic interpolation method in the range N.
Both 10 20 30 4O numerical algorithms are of complexity O N3. N Since the interpolation converges in a number of Fig.
To this end, we first validate the ana- lytic model by comparison with simulation for 4. Buffer size is 50 cells obtained much faster. Since the assumptions on rts delay. The value which the model is based remain valid as P de- chosen for P was much higher than typical in- creases, we can assume that the model will be dustry requirements.
This choice was dictated by accurate also for much smaller values of P. Thus, simulation run-time constraints.
These results cannot be obtained by simulation, because of excessive run-time. As expected, the higher the burstiness, the larger the multiplex effect i. The buffer size N Fig. Simulation vs. Figures 3 - 5 show the effect of the decrease in be quite small, because the entire burst can fit into P from 10 -5 to 10 -9 on the expansion factor. We the buffer. When the average burst becomes longer note that R increases as P decreases, as expected.
Thus, the actual burst length is not that Next, we study the sensitivity of R with respect critical anymore. This can be explained by the fact that as IL long as the average burst length of a single source o is shorter than the buffer size, the cell losses will I i : ul 3. In this Markov model, the state corresponds to a 8.
C average variance and autocovariance function of 0 the measured data. Solution approach. We implemented this solution approach to obtain As we mentioned before, we observed that R the cell loss probability for a given buffer size. In other words, if we multiply both traffic, the bandwidth required to achieve a given K and L by the same factor, R remains un- GOS cell loss probability , is determined by using changed.
This property, first observed by Li [11], a logarithmic interpolation method in the range is formally proved in the Appendix. The search ends when ratio between the average burst length of a single the GOS is obtained within a given tolerance. Thus, we do not need to carry out another set of experi- 5. Numerical results ments where L is kept fixed and K is a variable. Finally, in Fig. There- scribed in [12] which is easy to simulate but dif- fore, it is no surprise to find in Fig.
The parameter a is im- a video source during a frame period is stored in a portant in the dimensioning of the buffer size. From their article one can deduct that the parameter. This transfer mode is feasible only 5. Variable-bit-rate traffic analysis for large common buffers. This is because Therefore, if the buffer length is small, no characterization and multiplexing of VBR sources. In this portion of cells would always be lost. The con- tinuous transfer corresponds to the fluid-flow model.
In the uniform N transfer, the packets cells generated in a frame Fig. The agreement is M. C very satisfactory. N Figure 11 shows the sensitivity of R with respect Fig. V B R sources. Comparison of bursty and variable bit rate traffic. That is, the effective bandwidth per source is underestimated, and therefore, if all channel capacity is allocated, 6. Comparison of bursty and variable bit rate traffic the GOS requirement is still not satisfied.
Decina and Toniatti [5] suggest the use of a quasi linear Figure 12 compares the multiplexing effect for approximation with a security coefficient. VBR sources with the multiplexing effect for A pessimistic bandwidth allocation would be to bursty sources of similar burstiness. These sources are com- each subset independently and then we add up the pared with bursty sources with burstiness factor 3 bandwidth requirements. This is obviously an for three distinct burst lengths. This reduction of the with different characteristics.
As a consequence, which is the minimum between the above pessi- approximating the multiplexing behavior of VBR mistic upper-bound and the required bandwidth sources by the behavior of bursty sources with if the total average traffic was generated by the same burstiness would usually be too pessimistic.
However, it can give us a lower bound in the Dziong et al. Figure 13 presents the results obtained by simu- 7. Application: admission control lation of the statistical multiplexing of bursty and VBR sources. The VBR source characteristics were The results obtained in the previous sections described earlier. The bursty sources have bursti- can be used to devise call admission policies. For the analytical readily obtain the maximum number of sources and approximation results, we assume that the x max of type i that can be multiplexed in a chan- number of sources is a continuous variable.
The linear approximation was t0 20 shown to be too optimistic, while the upper bound is too pessimistic. A non-linear approximation 10 proposed elsewhere was shown to produce a good match.
We conclude that more work is required in 0 order to validate the above mentioned approxima- 5 10 15 20 25 30 tion and; to decide if it is adequate as a basis for N2 VBR admission control.
Mixing of bursty and variable bit rate traffic. Further work is necessary in these areas: mod- els for the traffic sources in particular, relaxing the assumption that the active and silence periods in the simulation they can only assume discrete for a bursty source are exponentially distributed ; values.
In Fig. Note that and; better approximations for the allowed num- the upperbound on required bandwidth becomes ber of sources in mixed traffic. More extensive work is required in order to determine whether Dziong's The cell loss probability, and therefore also the approximation is adequate, or a better one must expansion factor, of bursty sources on a multi- be sought. Conclusions As a reviewer pointed out, this property has been previously observed by Li [11].
0コメント