William is an independent consultant and president of Comp-Comm Consulting of Brewster, Massachusetts. He is a frequent lecturer on networking topics and the author of over a dozen books on data communications and computer networking. This article is based on material in Bill's latest book, Networking Standards: A Guide to OSI, ISDN, LAN, and MAN Standards (Addison-Wesley, 1993). Bill can be reached at 72500.3562@ compuserve.com.
There is a trend within many organizations toward the use of an increasing number of LANs and other networks joined together in an internet to support distributed processing needs. For relatively simple configurations of LANs, interconnection is usually provided by bridges. For more complex internets, and for ones that include metropolitan-and wide-area networks, the more sophisticated router is used for interconnection.
A major task in an internet is the routing of packets from source to destination through a sequence of networks and bridges or routers. For this purpose, an algorithm is needed to determine a route for each source-destination pair, and a protocol is needed by which the bridges or routers can exchange configuration and traffic information in order to calculate the routes.
For internets based on bridges, routing is usually accomplished with source routing or spanning-tree routing, both of which have been standardized by the IEEE 802 LAN standards group. However, neither of these techniques scale up well to a complex, highly interconnected internet supported by routers.
Three different routing protocols have emerged in recent years to answer the need for dynamic routing that provides load balancing and response to failures.
For internets that use the internet protocol (IP) or the ISO connectionless network protocol, the key function of a router is to make a routing decision to forward network-level protocol-data units, called "datagrams," on their next hop. The information required by a router to perform the routing function is of three types: topology, end-system (ES) reachability, and hop cost. For topology information, a router needs to know about the existence of the other routers and how they are interconnected. We can abstract the topology into a graph consisting of nodes connected by edges. Each node is a router, and each edge is either a point-to-point link or a subnetwork.
The second type of information needed by the router is ES reachability. For each end system, the router needs to know the identity of the subnetwork that contains that ES.
Finally, each hop must be assigned a cost in each direction. The cost associated with each hop, in each direction, is generally referred to as a "routing metric." The routing metrics used in IS-IS are arranged in four levels, with a lower value indicating a more optimum (lower-cost) choice. In order, the routing metrics are:
The hop costs are used as input to the path-calculation routine. Each router maintains an information base containing the topology and hop costs of each hop in the internet. This information is used to perform what is referred to as a "least-cost" routing algorithm, which can be simply stated as:
Given a network of nodes connected by bidirectional links, where each link has a cost associated with it in each direction, define the cost of a path between two nodes as the sum of the costs of the links traversed. For each pair of nodes, find the path with the least cost.
The algorithm used in OSPF, IS-IS, and Integrated IS-IS was originally proposed by Dijkstra. It enables each router to find the least-cost route to every other router. Dijkstra's algorithm can be stated thus: Find the shortest paths from a given source node to all other nodes by developing the paths in order of increasing path length. The algorithm proceeds in stages. By the kth stage, the shortest paths to the k nodes closest to (least cost away from) the source node have been determined; these nodes are in a set M. At the (k + 1) stage, the node not in M that has the shortest path from the source is added to M. As nodes are added to M, their path from the source is defined. The algorithm is formally described in Example 1. Table 1 and Figure 2 show the results of applying this algorithm to Figure 1, using s = 1. Note that at each step, the path to each node plus the total cost of that path is generated. After the final iteration, the least-cost path to each node and the cost of that path has been developed. The same procedure can be used with node 2 as source node, and so on.
Define:
N =set of node in the network
s =source node
M =set of nodes so far incorporated by the algorithm
d[ij] =hop cost from node i to node j; d[ii] =O, and d[ij]= infinity
if the nodes are not directly connected
D[n] =cost of the least-cost path from node s to node n that is
currently known to the algorithm
The algorithm has three steps; steps 2 and 3 are repeated until M=N:
1. Initialize:
M = {s} (set of nodes incorporated is only the source node)
D[n] =d[sn] for n not equal s (initial path costs to neighboring nodes
are simply the hop costs)
2. Find the neighboring node not in M that has the least-cost path from
node s and incorporate that node into M:
min
Find w epsi s M such that D[w]= D[j]
j epsi s M
Add w to M
3. Update least-cost paths:
D[n]=min[D[n], D[w]+d[w,n]]for all nepsiM
If the latter term is the minimum, the path from s to n is now the
path from s to w, concatenated with the hop from w to n.
Iteration M D[2] Path D[3] Path D[4] Path D[5] Path D[6] Path
-------------------------------------------------------------------------
1 {1} 2 1-2 5 1-3 1 1-4 infinity -- infinity --
2 {1,4} 2 1-2 4 1-4-3 1 1-4 2 1-4-5 infinity --
3 {1,2,4} 2 1-2 4 1-4-3 1 1-4 2 1-4-5 infinity --
4 {1,2,4,5} 2 1-2 3 1-4-5-3 1 1-4 2 1-4-5 4 1-4-5-6
5 {1,2,3,4,5} 2 1-2 3 1-4-5-3 1 1-4 2 1-4-5 4 1-4-5-6
6 {1,2,3,4,5,6 2 1-2 3 1-4-5-3 1 1-4 2 1-4-5 4 1-4-5-6
Dijkstra's algorithm is known to converge under static conditions of topology and hop costs. If the hop costs change over time, the algorithm will attempt to catch up with these changes. However, if the hop cost depends on traffic, which in turn depends on the routes chosen, then a feedback condition exists, and instabilities may result.
The validity of the algorithm will, of course, depend on the validity of the information used as input. The routing information may change over time. A router or subnetwork failure can alter the topology, and some of the costs, especially delay, are variable. Thus, some sort of information-exchange discipline is needed to govern the frequency with which routers exchange routing information. This is the purpose of all three routing protocols, and all three use essentially the same strategy for distributing information. The general strategy has the following elements:
Since the point of distributing LSPs is to enable each router to build up a picture of the topology of its area or domain, how can a router know to whom and how to deliver the LSPs? There appears to be a circular dilemma: A router needs to know the topology in order to directly address its LSPs to each other router, yet the router learns the topology from LSPs. The way out of this dilemma is flooding: The LSP is sent by the source router to every one of its neighbor routers. At each router, an incoming LSP is retransmitted on all outgoing links except for the link that it arrived from. Eventually, all routers will receive a copy of the LSP.
Flooding solves the delivery problem, but raises some new problems:
Next, consider the problem of obsolescence. Each LSP includes a parameter called "remaining lifetime." This parameter is set to some default maximum value by the source router. The parameter is decremented each time it is retransmitted by a router. Once a router stores an LSP in its database, it periodically decrements the lifetime parameter until it reaches 0. If the sequence number of an LSP reaches 0 (no new LSP from the same source arrives in time), the LSP is purged from the database.
Finally, a router can determine which of two LSPs from the same source is the more recent on the basis of the sequence number. When a router is initialized, it issues its first LSP with a sequence number of 1 and increments the sequence number for each subsequent LSP it creates. With a 32-bit sequence number, it is unlikely that all of the sequence numbers will be used up. However, if a router reaches the maximum sequence number (2{32}-1), the routing function at the router is disabled for a period sufficient to ensure that all of the prior LSPs issued by this router have expired. The router then begins again with a sequence number of 1.
The routing discipline can actually be more complex than that just described. All of the routing protocols we have been describing are designed to work in a multilevel, hierarchical routing environment. We will describe the environment designed for OSI configurations; the one for TCP/IP configurations is similar.
In an OSI configuration, an internet can be divided into a number of routing domains. A domain is a large-scale portion of an internet, generally organized along geographical or organizational lines. For example, all of the local area networks at a site, such as a military base or campus, could be linked by ISs to form a routing domain. This complex might be linked through a wide area network to other routing domains. Domains can be further subdivided into areas. This hierarchical approach has a number of advantages:
The information required by an IS to perform the routing function depends on its role. For topology information, a level-1 IS only needs to know the existence of the other level-1 ISs in its area and at least one level-2 IS in its area, plus the way in which these ISs are interconnected. Similarly, a level-2 IS needs only know the identity of the other level-2 ISs in its routing domain and how they are interconnected. In either case, we can abstract the topology into a graph consisting of nodes connected by edges. Each node is an IS, and each edge is either a point-to-point link or a subnetwork.
The second type of information needed by the IS is ES reachability. In the case of a level-1 IS, it needs to know, for each ES in its area, the identity of the subnetwork that contains that ES. In the case of a level-2 IS, it needs to know, for each ES, the area that contains that ES and a level-2 IS in that area.
Finally, for either level-1 or level-2 routing, each hop must be assigned a cost in each direction. In the case of level-1 routing, a hop is a subnetwork or point-to-point link connecting ISs. For level-2 routing, a hop is a point-to-point link between level-2 ISs.
Copyright © 1993, Dr. Dobb's Journal