In an integrated services network, resources are shared by multiple traffic classes. Service classes that deliver quality-of-service (QoS) to applications have priority over others that do not. In such a multi-service network, routing decisions for high priority QoS traffic will affect what resources are available for lower priority traffic: poor route selection can result in congestion for, or even starvation of, lower priority traffic. Whereas many studies have focused on routing algorithms that optimize the network throughput for individual service classes, little effort has been devoted to routing algorithms that address inter-class resource sharing. In this paper, we propose a routing algorithm that allows dynamic sharing of link resources among multiple traffic classes. The algorithm is based on the concept of "virtual residual bandwidth", which is derived from the link residual bandwidth by taking the congestion condition of low priority traffic into account. By using the virtual residual bandwidth in the link cost function for QoS sessions, we discourage QoS sessions from using links that are heavily loaded with low priority traffic. Our approach is simple in the sense that besides changing the link cost function, no other changes to the routing algorithms for individual service classes are required. An extensive simulation study shows that when the traffic load is unevenly distributed, significant performance improvements can be achieved for low priority traffic without sacrificing performance for high priority traffic. The result demonstrates that QoS routing is important even when the QoS traffic load is light and call blocking is not an issue.

Transmission of multimedia streams imposes a minimum-bandwidth requirement on the path being used to ensure end-to-end Quality-of-Service (QoS) guarantees. While any shortest-path algorithm can be used to select a feasible path, additional constraints that limit resource consumption and balance the network load are needed to achieve efficient resource utilization. We present a systematic evaluation of four routing algorithms that offer different tradeoffs between limiting the path hop count and balancing the network load. Our evaluation considers not only the call blocking rate but also the fairness to requests for different bandwidths, robustness to inaccurate routing information, and sensitivity to the routing information update frequency. It evaluates not only the performance of these algorithms for the sessions with bandwidth guarantees, but also their impact on the lower priority best-effort sessions. Our results show that a routing algorithm that gives preference to limiting the hop count performs better when the network load is heavy, while an algorithm that gives preference to balancing the network load performs slightly better when the network load is light. We also show that the performance of using pre-computed paths with a few discrete bandwidth requests is comparable to that of computing paths on-demand, which implies feasibility of class-based routing. We observe that the routing information update interval can be set reasonably large to reduce routing overhead without sacrificing the overall performance, although an increased number of sessions can be misrouted.

Rate based congestion control has been considered desirable, both to deal with the high bandwidth-delay products of today's high speed networks, and to match the needs of emerging multimedia applications. Explicit rate control achieves low loss because sources transmit smoothly at a rate adjusted through feedback to be within the capacity of the resources in the network. However, large feedback delays, presence of higher priority traffic, and varying transient situations make it difficult to ensure feasibility (i.e., keep the aggregate arrival rate below the bottleneck resource's capacity) while also maintaining high resource utilization. These conditions along with the "fast start" desired by data applications often result in substantial queue buildups.We describe a scheme that manages the queue buildup at a switch even under the most aggressive patterns of sources, in the context of the Explicit Rate option for the Available Bit Rate (ABR) congestion control scheme. A switch observes the buildup of its queue, and uses it to reduce the portion of the link capacity allocated to sources bottlenecked at that link. We use the concept of a "virtual" queue, which tracks the amount of queue that has been "reduced", but has not yet taken effect at the switch. We take advantage of the natural timing of "resource management" (RM) cells transmitted by sources. The scheme is elegant in that it is simple, and we show that it reduces the queue buildup, in some cases, by more than two orders of magnitude and the queue size remains around a desired target. It maintains max-min fairness even when the queue is being drained. The scheme is scalable, and is as responsive as can be expected: within the constraints of the feedback delay. Finally, no changes are needed to the ATM Forum defined source/destination policies.

We study how to improve the throughput of high-bandwidth traffic such as large file transfers in a network where resources are fairly shared among connections. While it is possible to devise priority or reservation-based schemes that give high-bandwidth traffic preferential treatment at the expense of other connections, we focus on the use of routing algorithms that improve resource allocation while maintaining max-min fair share semantics. In our approach, routing is closely coupled with congestion control in the sense that congestion information, such as the rates allocated to existing connections, is used by the routing algorithm. To reduce the amount of routing information that must be distributed, an abstraction of the congestion information is introduced. Using an extensive set of simulation, we identify a link-cost or cost metric for "shortest-path" routing that performs uniformly better than the minimal-hop routing and shortest-widest path routing algorithms. To further improve throughput without reducing the fair share of single-path connections, we propose a novel prioritized multi-path routing algorithm in which low priority paths share the bandwidth left unused by higher priority paths. This leads to a conservative extension of max-min fairness called prioritized multi-level max-min fairness. Simulation results confirm the advantages of our multi-path routing algorithm.

Switched LANs are become more widely used because they can provide a higher bandwidth than LANs based on shared media. Examples of packet switched LANs include HIPPI, and switched FDDI and Ethernet. A number of studies have evaluated the performance of HIPPI networks, making simplifying assumptions about both the network and the traffic load. In this paper we present the results of a simulation study of circuit-switched LANs such as HIPPI using more realistic models for the system and the traffic. We observe changes in throughput as high as a factor of ten when we change the system and traffic parameters. We also show how packet scheduling can be used to improve performance in some cases.>