Previous

Content

Next 

5.0.- Path Selection

  

To select a path we have two problems:
  1. The path selection algorithm itself.
     
      The cost of a path is a function of both: the hop count and the available bandwidth. Each interface has associated a metric which indicates the amount of remaining available bandwidth. This metric is combined with the hop count to provide a cost value, whose goal is to pick the path with the minimum number of hops supporting the requested bandwidth. When several paths are available, the path whose availability is maximal is selected. This way the balance load is maximized. Observe that this algorithm has double objetive optimization.
         		  
  2. When the algorithm is actually invoked.
     
      Here two options exist:
    1. On-demand, this means, the computation is triggered for each new request. This option could be computationally expensive.
       
    2. Using some form of pre-computation. This option amortizes the computational cost over multiple requests, but each computation instance is usually more expensive because path to all destination should be recomputed. Also the final accuracy of the selected path may be lower. Another important issue is when this precomputation should take place. Here, again, we have two options:
       
       
      1. Periodic recomputation.
      2. Precomputation after 'N' number of updates have been received.
      		  
    		 
In this document, precomputation is the method selected. Some experiment have been done to compare periodic precomputation for different period values.
Path Computation Algorithm
The algorithm pre-computes for any destination a minimum hop count path with maximum bandwidth. Its complexity is comparable to that of a standard Belman-Ford shortest path algorithm. The BF algorithm, at its h-th iteration, identifies the optimal (i.e., maximal bandwidth) path between a source and a destination, among paths of at most h hops. This bandwidth is the smallest available bandwidth on all lines of the path. Because the BF algorithm progresses by increasing hop count, it essentially provides for free the hop count of a path as a second optimization criteria.  

Specifically, at the h-th (hop count) iteration, the maximum available bandwidth to all destinations on a path of no more than h hops is recorded. After the algorithm terminates, this information provides for all destinations and bandwidth requeriments, the path with the smallest possible number of hops and sufficient bandwidth to accomodate the new request.
Let us denote by b(m;n) the available bandwidth on the link from node m to n. The vertex where the algorithm is being run, the router, is denoted as the source node. The algorithm precomputes path from this source node to all possible destination networks and for all possible bandwidth values. At each iteration (hop count), intermediate results are recorded in a QoS routing table, which has the following structure:
The QoS routing table
  • a K x H matrix, where K is the number of destinations (taken from the current IP routing table of the source host) and H is the maximum allowed number of hops for a path.
     
  • the (n;h) entry is built during the h-th iteration of the algorithm and contains two fields:
     
    1. bw: the maximum available bandwidth on the path (with h hops).
    2. neighbor: the identity of the node adjacent to the source node on that path. It should be a router and not a network, except when the network is just the destination node.
    		  

When the algorithm is first invoked, the QoS routing table is first initialized with all bw fields set to 0 and neighbor fields cleared.
The first column is next treated (which corresponds to one-hop paths). Its values are modified as follows:
 
  1. The bw field is set to the value of the available bandwidth on the direct edge from the source.
  2. The neighbor field is set to the identity of the neighbor of the computing router, i.e., the next router on the selected path.
  
Afterward, the algorithm iterates for at most H iterations; the value of H could be implicit, i.e., the diameter of the network or, it can be set explicitly thereby limiting path lenghts to at most H hops. In this case, H must be assigned a value larger than the length of the minimum hop-count path to any node in the graph.
  At iteration h, column h-1 values are copied into column h. Also, the algorithm keeps a list of nodes that changed their bw value in the previous iteration (h-1). The algorithm then looks at each link (n;m) where n is a node whose bw value changed in the previous iteration, and checks the maximal available bandwidth on an (at most) h-hop path to node m whose final hop is that link. This amounts to taking the minimum between the bw field in entry (n; h-1) and the link metric value b(n;m) kept in the topology database.
If this value is higher than the present value of the bw field in entry (m;h), then a better (larger bw value) path has been found for destination m with at most h hops. The bw in entry (m;h) is updated. In the case of hop-by-hop routing, the neighbor field of entry (m;h) is set to the same value as in entry (n;h-1). This records the identity of the first hop (next hop from the source) on the best path identified thus far for destination m and with h (or less) hops.
It should be noted that it is assumed that some entity is responsible for determining the "available bandwidth" on the network, e.g., a subnet bandwidth manager. The specification and operation of such an entuty is beyond the scope of this document.
The algorithm has to deal also with accomodating zero-hop edges in the context of the path selection. Zero-hop edges are needed to represent multiaccess networks, for example, when three routers A, B, and C are connected over an Ethernet network N. In this case, one edge from the network to any of the three routers must have zero "cost", so that it should not be counted twice.
The issue of equal cost, i.e., same hop count and available bandwidth, is not detailed above, but it should be also taken into account. It only requires that the neighbor field be expanded to record the list of next (previous) hops, when multiple equal cost paths are present.
Stub Networks
The path selection algorithm is run on a graph consisting only of routers and transit networks, but not stub networks. A second processing must be run to account for stub networks. Specifically, after the QoS routing table is built, all router vertices are again considered. For each router, stub networks whose links appear in the router's link advertisement will be processed to determine QoS routes available to them.
Each entry in the row corresponding to stub network S has its bw(S) field initialized to zero and its neighbor set to null. When a stub network S is found in the link advertisement of router V, the value bw(S,h) is updated as follows:
  bw(S,h) = max( bw(S,h); min( bw(V,h), b(V,S) ) )  
where bw(V,h) is the bandwidth available on an h hop path to V, and b(V,S) is the advertised available bandwidth on the link from V to S. This expression states that the bandwidth of a h hop path to stub netowrk S is updated using a path through router V, only if the minimum of the bandwidth of the h hop path to V and the bandwidth on the link between V and S, is larger then the current value.
Extracting forwarding information from the QoS Routing Table
When the QoS paths are precomputed, the forwarding information for a flow with given destination and bandwidth requirement is extracted from the newly constructed QoS Routing Table.
Specifically, assume a new request to destination d with bandwidth requirement B is received. The index of destination d identifies the row in the QoS Routing Table that needs to be checked. The search then proceeds by increasing index (hop) count until an entry is found containing a bw value equal or larger than B. This entry point identifies the next hop that has to be selected.
If the path computation algorithm stores multiple equal cost paths, then some degree of load balancing can be achieved. A next hop from the list of equivalent next hops can be chosen in a round robin manner, or randomly with a probability that is weighted by the actual available bandwidth on the local interface.
This explanation holds for hop-by-hop implicit routing. The case of explicit routing is discussed later.
   

Previous

Content

Next