Quality-of-Service Routing in Integrated Services Networks

摘要

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