|
CMU-CS-98-138
Computer Science Department
School of Computer Science, Carnegie Mellon University
CMU-CS-98-138
Quality-of-Service Routing in Integrated Services Networks
Qingming Ma
January 1998
Ph.D. Thesis
CMU-CS-98-138.ps
Keywords: Integrated services networks, quality-of-service, routing
resource management, congestion control, max-min fair share, resource
reservation, service disiplines, algorithms
Future integrated services networks will support multiple classes of
service to meet the diverse quality-of-service (QoS) requirements of
applications. To meet these end-to-end QoS requirements, strict resource
constraints may have to be imposed on the paths being used. QoS
routing refers to a set of protocols and algorithms that can select
paths that satisfy such constraints while achieving high network throughput.
QoS routing is challenging because (1) different service classes employ
different resource sharing models, (2) service classes dynamically share
link resources, and (3) selecting paths that meet multiple QoS constraints
is a complex algorithmic problem.
This dissertation show QoS routing in integrated services networks is
both desirable and feasible. To support this claim, this
dissertation develops an integrated QoS routing framework that has two
components. The first component consists of routing algorithms for
individual service classes that support either bandwidth guarantees,
delay guarantees, or high throughput. By exploiting the relationship
between QoS constraints, we develop polynomial routing algorithms for
traffic classes that require stringent end-to-end performance quarantees.
By coupling routing with finer-time scale resource management mechanisms
such as congestion control and scheduling, we develop routing algorithms
that achieve high throughput for best-effort traffic and low blocking
rate for guaranteed traffic. By striking an appropriate balance between
per-flow resource consumption and the distribution of network load, these
algorithms improve resource utilization efficiency and network throughput
under dynamic load conditions.
In a network that supports multiple classes of service, best-effort flows
can experience congestion or even starvation if guaranteed flows are not
routed appropriately. The second component of the proposed QoS routing
framework is an effective inter-class resource sharing mechanism that also
takes into consideration the link load of best-effort traffic while routing
guaranteed flows. This mechanism is simple in the sense that it
influences routing decisions by changing the link costs used for
guaranteed traffic without requiring any change to the routing algorithms
employed for individual service classes. In various scenarios, we observed
significant performance improvements for best-effort traffic without
sacrificing any performance for guaranteed traffic.
168 pages
|