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
