The Link-State (LS) Routing Algorithms

The Link-State (LS) Routing Algorithms

Remember that in a link-state algorithm, the network topology and all link costs are known, that is, available as input to the LS algorithm. In fact this is accomplished by having each node broadcast link-state packets to all other nodes in the network, with each link-state packet including the identities and costs of its attached links. In fact (for instance, with the Internet's OSPF routing protocol, discussed in "Routing in the Internet") this is often accomplished by a link-state broadcast algorithm [Perlman 1999]. We'll cover broadcast algorithms in "Broadcast and Multicast Routing". The result of the nodes broadcast is that all nodes have the same and complete view of the network. Each node can then run the LS algorithm and compute the same set of least-cost paths as every other node.  (corrected and changed)

The link-state routing algorithm we present below is known as Dijkstra's algorithm, named after its inventor. A closely related algorithm is Prim's algorithm; see [Cormen 2001] for a general discussion of graph algorithms. Dijkstra's algorithm computes the least-cost path from one node (the source, which we will refer to as u) to all other nodes in the network. Dijkstra's algorithm is iterative and has the property that after the kth iteration of the algorithm, the least-cost paths are known to k destination nodes, and among the least-cost paths to all destination nodes, these k paths will have the k smallest costs. Let us describe the following notation:

●  D(v): cost of the least-cost path from the source node to destination v as of this iteration of the algorithm.
●  p(v): previous node (neighbor of v) along the current least-cost path from the source to v.
●  N' : subset of nodes; v is in N' if the least-cost path from the source to v is definitively known.

The global routing algorithm comprises an initialization step followed by a loop, The number of times the loop is carried out is equal to the number of nodes in the network. Upon termination, the algorithm will have calculated the shortest paths from the source node u to every other node in the network.

 Link-State (LS) Algorithm for Source Node u

As an example, let's look at the network in "Routing Algorithms" Figure 1 and compute the least-cost paths from u to all possible destinations. A tabular summary of the algorithm's computation is illustrated in Table 1, where each line in the table gives the values of the algorithm's variables at the end of the iteration. Let's look at the few first steps in detail.

●  In the initialization step, the currently known least-cost paths from u to its directly attached neighbors, v, x, and w, are initialized to 2, 1, and 5, respectively. Note in particular that the cost to w is set to 5 (even though we will soon see that a lesser-cost path does indeed exist) since this is the cost of the direct (one hop) link from u to w. The costs to y and z are set to infinity because they are not directly connected to u.

●  In the first iteration, we look among those nodes not yet added to the set N' and find that node with the least cost as of the end of the previous iteration. That node is x, with a cost of I, and thus x is added to the set N'. Line 12 of the LS algorithm is then performed to update D(v) for all nodes v, yielding the results shown in the second line (Step 1) in Table 1. The cost of the path to v is unchanged. The cost of the path to w (which was 5 at the end of the initialization) through node x is found to have a cost of 4.  Thus this lower-cost path is selected and w's predecessor along the shortest path from u is set to x. Likewise, the cost to y (through x) is computed to be 2, and the table is updated accordingly.

●  In the second iteration, nodes v and y are found to have the least-cost paths (2), and we break the tie randomly and add y to the set N' so that N' now includes u, x, and y. The cost to the remaining nodes not yet in N', that is, nodes v, w, and z,

Running the link-state algorithm on the network

are updated via line 12 of the LS algorithm, yielding the results shown in the third row in the Table 1.

●  And so on. . . .

When the LS algorithm terminates, we have, for each node, its predecessor along the least-cost path from the source node. For each predecessor, we also have its predecessor, and so in this way we can construct the entire path from the source to all destinations. The forwarding table in a node, say node u, can then be constructed from this information by storing, for each destination, the next-hop node on the least-cost path from u to the destination. Figure 1 illustrates the resulting least-cost paths and forwarding table in u for the network in "Routing Algorithms" Figure 1.

What is the computational complexity of this algorithm? That is, given n nodes (not counting the source), how much computation must be done in the worst case to find the least-cost paths from the source to all destinations? In the first iteration, we need to search through all n nodes to determine the node, w, not in N' that has the minimum cost, In the second iteration, we need to check n - 1 nodes to determine the minimum cost; in the third iteration n - 2 nodes, and so on. On the whole, the total number of nodes we need to search through over all the iterations is n(n + 1)/2, and therefore we say that the preceding implementation of the LS algorithm worst-case complexity of order n squared: O(n2). (A more complicated implementation of this algorithm, using a data structure known as a heap, can find the minimum in line 9 in logarithmic rather than linear time, hence reducing the complexity.)

Before completing our discussion of the LS algorithm, let us look at a pathology that can arise. Figure 2 shows a simple network topology where link costs are equal to the load carried on the link, for instance, reflecting the delay that would be experienced. In this example, link costs are not symmetric; that is, c(u,v) equals c(v,u) only if the load carried on both directions on the link (u,v) is the same. In this example, node z originates a unit of traffic destined for w, node x also originates a

Least costs paths and forwarding table for nodule u

unit of traffic destined for w, and node y injects an amount of traffic equal to e, also destined for w. The initial routing is illustrated in Figure 2(a) with the link costs corresponding to the amount of traffic carried.

When the LS algorithm is next run, node y determines (based on the link costs illustrated in Figure 2(a)) that the clockwise path to w has a cost of 1, while the counterclockwise path to w (which it had been using) has a cost of 1 + e. Hence y's least-cost path to w is now clockwise. Likewise, x determines that its new least-cost path to w is also clockwise, resulting in costs illustrated in Figure 2(b).  When the LS algorithm is run next, nodes x, y, and z all detect a zero-cost path to w in the counterclockwise direction, and all route their traffic to the counterclockwise routes. The next time the LS algorithm is run, x, y and z all then route their traffic to the clockwise routes.

What can be done to prevent such oscillations (which can occur in any algorithm, not just an LS algorithm, that uses a congestion or delay-based link metric)? One solution would be to mandate that link costs not depend on the amount of traffic carried - an unacceptable solution since one goal of routing is to avoid highly congested (for instance, high-delay) links. Another solution is to ensure that not all routers run the LS algorithm at the same time. This seems a more reasonable solution, since we would hope that even if routers ran the LS algorithm with the same periodicity, the execution instance of the algorithm would not be the same at each node. Interestingly, researchers have found that routers in the Internet can self-synchronize among themselves [Floyd Synchronization 1994]. That is, even though they in the beginning carry out the algorithm with the same period but at different instants of time, the algorithm execution instance can finally become, and remain, synchronized at the routers. One way to avoid such self-synchronization is for each router to randomize the time it sends out a link advertisement.

Having studied the LS algorithm, let's look at the other most important routing algorithm that is used in practice today - the distance-vector routing algorithm.

Oscillations with congestion-sensitive routing

Tags

nodes, broadcast algorithms, loop, ls algorithm, routers

Copy Right

The contents available on this website are copyrighted by TechPlus unless otherwise indicated. All rights are reserved by TechPlus, and content may not be reproduced, published, or transferred in any form or by any means, except with the prior written permission of TechPlus.