Qingming Ma

Quality-of-Service Routing in Integrated Services Networks Degree Type: Ph.D. in Computer Science
Advisor(s): Peter Steenkiste
Graduated: May 1998

Abstract:

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 guarantees. 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.

Thesis Committee:
Peter Steenkiste (Chair)
Garth Gibson
Allan Fisher
Hui Zhang
Lixia Zhang (UCLA)

James Morris, Head, Computer Science Department
Raj Reddy Dean, School of Computer Science

Keywords:
Integrated services networks, quality-of-service, routing resource management, congestion control, max-min fair share, resource reservation, service disiplines, algorithms