ERCIM News No.37 - April 1999
ERCIM News No.37 - April 1999
Resource Allocation in Integrated-Services Networks
by Sem Borst
Service providers race to develop next-generation communication networks, integrating a wide variety of services, such as voice, video, and data, onto a common infrastructure. There are major obstacles to overcome, however, since different services not only have drastically different traffic characteristics, but also extremely diverse quality-of-service requirements. Performance evaluation research at CWI focuses on models and techniques from queueing theory for evaluating the relevant quality-of-service measures, such as delay performance. Important issues in integrated networks which have received particular attention include the impact of long-ailed traffic characteristics and the interaction between best-effort and real-ime services.
World-wide, the use of communication services is experiencing revolutionary growth. The growth is fueled not only by the expansion of conventional telephone services, but also the advance of data communications, the spectacular development of the Internet, and the proliferation of wireless communications. Driven by these demands, service providers rush to enhance their networks. A major trend is the integration of voice and data services.
Eventually, this is expected to result in the consolidation of a wide variety of services onto a common platform. While offering potential synergies, however, the integration of heterogeneous service classes also involves several fundamental problems. First of all, different services may have radically different traffic characteristics. To characterize traffic processes, it is convenient to adopt a three-level hierarchy. The lowest level of granularity is the packet level. Packets are typically generated in bursty patterns occurring at a moderate rate, defining the burst level. Finally, at the connection level, connections are established and terminated.
Different service classes may also have extremely diverse quality-of-service requirements. Important measures are the amount of packet delay incurred during transmission, and the fraction of packet loss caused by buffer overflow. Voice traffic is rather sensitive to delay but can sustain some packet loss, whereas data traffic can tolerate some amount of delay but is quite vulnerable to packet loss.
The heterogeneity in quality-of-service requirements and traffic characteristics requires sophisticated allocation mechanisms to regulate the usage of network resources. The main resource allocation instruments include admission control, routing, scheduling, and flow control.
The design of efficient resource allocation algorithms requires techniques for evaluating the relevant quality-of-service measures, eg, delay performance, cell loss, call blocking. CWI has traditionally focused on techniques from queueing theory, which is concerned with the study of congestion phenomena in stochastic service systems. The basic queueing model consists of a group of servers, where customers arrive who require some kind of service. In the context of communication networks, the server usually represents a transmission link, or a buffer or port on a switch. The customers typically correspond to transmitted packets, bursts, or offered calls, in accordance with the three-level hierarchy described above.
Real-ime traffic is traffic which is extremely sensitive to delay, such as voice and video-conferencing. In contrast, best-effort traffic is tolerant of some amount of delay, as long as the average capacity received over somewhat longer intervals is sufficient, file transfers being a typical example. Usually real-ime traffic is given some form of priority over best-effort traffic in packet scheduling. The best-effort traffic thus receives the capacity left-over by the real-ime traffic. That remaining capacity may drastically fluctuate over time because of the bursty patterns in packet flows described earlier. The available capacity is then shared among the best-effort connections in certain fixed proportions. This motivated a detailed investigation at CWI of (discriminatory) processor-sharing models with time-varying service capacity. The results show that the average transmission time of best-effort files is asymptotically linear in the size of the files, which is commonly viewed as a desirable fairness property.
A second major research topic at CWI concerns the occurrence of long-ailed traffic characteristics. Measurements have provided increasing evidence that packet traffic exhibits long-range dependence and self-similarity over a wide range of time scales. Queueing models with long-ailed input traffic offer a useful approach to evaluating the impact of long-range dependence and self-similarity on network performance. It was shown for example that if the input traffic is long-ailed, then so are the buffer content and the delay (buffer content even ‘one degree worse’). In integrated networks, where the transmission capacity is shared by several traffic streams, even a single long-ailed traffic stream may cause the buffer content to be long-ailed, unless the link rate is larger than the peak rate of that long-ailed connection plus the mean rate of the other flows. These results have important implications for admission control. Recently, the research has focused on the issue how scheduling algorithms may be used to neutralize the negative effects from long-ailed traffic phenomena. It was found that if traffic is not processed in order of arrival, but in processor-sharing fashion, then the tail behavior of the delay is no longer any worse than that of the input traffic.
Please contact:
Sem Borst - CWI
Tel: +31 20 592 4205
E-mail: Sem.Borst@cwi.nl