As originally published in IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 44, NO. 2, FEBRUARY 1996
Abstract - Even though asynchronous transfer mode (ATM) seems to be clearly the wave of the future, one performance analysis indicates that the combination of stringent performance requirements (e.g., 10-9 cell blocking probabilities), moderate size buffers, and highly bursty traffic will require that the utilization of the network be quite low. That performance analysis is based on asymptotic decay rates of steady-state distributions used to develop a concept of effective bandwidths for connection admission control. However, we have developed an exact numerical algorithm that shows that the effective-bandwidth approximation can overestimate the target small blocking probabilities by several orders of magnitude when there are many sources that are more bursty than Poisson. The bad news is that the appealing simple connection admission control algorithm using effective bandwidths based solely on tail-probability asymptotic decay rates may actually not be as effective as many have hoped. The good news is that the statistical multiplexing gain on ATM networks may actually be higher than some have feared. For one example, thought to be realistic, our analysis indicates that the network actually can support twice as many sources as predicted by the effective-bandwidth approximation; this discrepancy occurs because for a large number of bursty sources the asymptotic constant in the tail probability exponential asymptote is extremely small. That, in turn, can be explained by the observation that the asymptotic constant decays exponentially in the number of sources when the sources are scaled to keep the total arrival rate fixed. We also show that the effective bandwidth approximation is not always conservative. Specifically, for sources less bursty than Poisson, the asymptotic constant grows exponentially in the number of sources (when they are scaled as above) and the effective-bandwidth approximation can greatly underestimate the target blocking probabilities. Finally, we develop new approximations that work much better than the pure effective-bandwidth approximation.
I. INTRODUCTIONMuch energy is being devoted to studying the promising new asynchronous transfer mode (ATM) technology for supporting multiservice high-speed communication networks-e.g., see Roberts . As indicated in , interest in ATM is stimulated by two factors: First, by new technology making it possible to transmit and switch at very high bandwidths; and, second, by the growing demand for more sophisticated and powerful communication services.
Even though ATM seems to be well on its way to widespread use, a performance analysis based on asymptotic decay rates of steady-state distributions indicates that the combination of stringent performance requirements (e.g., 10-9 cell blocking probabilities), moderate-size buffers, and highly bursty traffic associated with these new services will necessitate operating the networks at very low utilizations. (The basic model represents an ATM switch receiving fixed-size ATM cells from several sources and transmitting them over an output channel in a first-in-first-out fashion; the basic question is: How many sources can be admitted for a fixed buffer size with a specified small cell blocking probability?) The main message of this paper is that ATM networks may be able to achieve higher utilizations than that asymptotic analysis indicates. In other words, there seems to be more potential for statistical multiplexing gain.
The approximation based on asymptotic decay rates of tail probabilities is very appealing because it supports a concept of effective bandwidths. From an engineering perspective, the notion of effective bandwidths is very natural. The idea is to assign each source an effective-bandwidth requirement, and then consider any subset of sources feasible (admissible) if the sum of the required effective bandwidths is less than the total available bandwidth. Thus; a suitable notion of effective bandwidths could go a long way toward solving the connection admission control problem. For instance, once effective bandwidths have been assigned, we can approach engineering and design problems using multirate loss network models, e.g., as in Choudhury et al.  and , and references therein.
A large-deviations asymptotic analysis provides strong support for the simple effective-bandwidth procedure, because it shows that it is asymptotically correct as the buffer size gets large and the tail probabilities get small, and because it provides a basis for assigning actual effective-bandwidth values to different sources (voice, data, video, etc.); e.g., see Hui , Gibbens and Hunt , Guerin et al. , Kelly , Sohraby , , Chang , Whitt , Elwalid and Mitra , Kesidis et al. , Glynn and Whitt , Courcoubetis et al. , and Chang et al. .
The additive nature of effective bandwidths is clearly appropriate if we let the effective bandwidths be either the source peak rates or the source average rates. However, it seems intuitively clear that working with peak rates is far too conservative, while working with average rates is far too optimistic. (We show this later in our examples.) Most of the recent work has been aimed at finding appropriate effective bandwidths in between the peak and average rates.
Unfortunately, however, from the outset, teletraffic engineering experience suggests that there may be a flaw in the effective bandwidth concept because it corresponds to having no traffic smoothing from multiplexing. In particular, it is known that when many separate bursty sources are multiplexed (superposed), the total is less bursty than the components, i.e., there is a basis for more statistical multiplexing gain than with Poisson sources. This is theoretically supported by the classical limit theorem stating that superpositions of arrival processes, suitably scaled, converge to a Poisson process as the number of component arrival processes increases, e.g., see Cinlar . For related performance studies see Heffes and Lucantoni , Sriram and Whitt , and Fendick et at. . In contrast, with the effective-bandwidth approximation, the burstiness of an superposed independent and identically distributed sources is the same as for a single source (e.g., see [45, p. 76]). This implies that the effective-bandwidth approximation will predict greater congestion for any fixed arrival rate than it should.
Nevertheless, there is a case for the effective bandwidths, because previous teletraffic analysis (such as in , , and ) did not focus on extremely small loss probabilities such as 10-9 . Such very small loss probabilities naturally suggest that appropriate asymptotics should provide what we want-and the asymptotic analysis associated with effective bandwidths indicates. no traffic smoothing.
The question, then, is what will actually happen in real systems? Will there be significant traffic smoothing or not? Is the asymptotic analysis supporting effective bandwidths sufficiently accurate or is it not?
These questions have plagued researchers in recent years because the natural models are very difficult to analyze. It is difficult to calculate very small tail probabilities in models with many independent bursty sources, by either exact analytical formulas or by computer simulation.
Our main contribution is a new algorithm for a queueing model that enables us to compute the desired small tail probabilities exactly when there are many bursty sources. From this exact analysis, we find that in some cases the effective-bandwidth approximation is excellent, but in other cases (which we think are realistic) it is not. Thus, we conclude that the notion of effective bandwidths based directly on large deviation asymptotics may not be effective for connection admission control.
©Copyright - All Rights Reserved
DO NOT REPRODUCE WITHOUT WRITTEN PERMISSION BY AUTHOR.