QoS Routing for Best-effort Flows
Pawan Goyal, Gisli Hjalmtyssony · 1999
In packet networks such as Internet, a simple static shortest path routing algorithm is employed. A packet is sent on the shortest path to its destination. If there are multiple shortest paths, the shortest path is chosen arbitrarily. To determine the shortest path each link is assigned a weight and the shortest path is the one with the smallest aggregate weight. The key characteristic of this routing algorithm is that the weights are assigned statically. Hence, route changes occur only when a change in the topology of the network occurs, i.e., a link is deleted or added. This topology driven static shortest path routing may suffice in networks that provide a single best effort service in which there is no guarantee about whether and when a packet will be delivered. However, it may not be adequate in networks that provide Quality of Service (QoS) guarantees to applications such as multimedia conferencing. To observe the inadequacies of static shortest path routing, consider the network shown in Figure 1. Let the network provide bandwidth guarantees to a flow. A flow is a sequence of packets from a source to destination and for our purpose is synonymous with a connection. In the network shown in Figure 1, all flows originating from 1 and destined to 5 will be routed over path 1-2-3-4-5 (assuming each link has identical weight). If large number of flows originating from 1 and terminating at 5 request guaranteed bandwidth, then the links 2-3 and 3-4 may get saturated and flows may be denied their request. This may