16. Calculation of the Routing Table

Summary-LSAs are originated by the area border routers. Each summary-LSA in Area A is considered in turn. Remember that the destination described by a summary-LSA is either a network (Type 3 summary-LSAs) or an AS boundary router (Type 4 summary-LSAs). For each summary-LSA:

(1) If the cost specified by the LSA is LSInfinity, or if the LSA's LS age is equal to MaxAge, then examine the the next LSA.

(2) If the LSA was originated by the calculating router itself, examine the next LSA.

(3) If it is a Type 3 summary-LSA, and the collection of destinations described by the summary-LSA equals one of the router's configured area address ranges (see Section 3.5), and the particular area address range is active, then the summary-LSA should be ignored. "Active" means that there are one or more reachable (by intra-area paths) networks contained in the area range.

(4) Else, call the destination described by the LSA N (for Type 3 summary-LSAs, N's address is obtained by masking the LSA's Link State ID with the network/subnet mask contained in the body of the LSA), and the area border originating the LSA BR. Look up the routing table entry for BR having Area A as its associated area. If no such entry exists for router BR (i.e., BR is unreachable in Area A), do nothing with this LSA and consider the next in the list. Else, this LSA describes an inter-area path to destination N, whose cost is the distance to BR plus the cost specified in the LSA. Call the cost of this inter-area path IAC.

(5) Next, look up the routing table entry for the destination N. (If N is an AS boundary router, look up the "router" routing table entry associated with Area A). If no entry exists for N or if the entry's path type is "type 1 external" or "type 2 external", then install the inter-area path to N, with associated area Area A, cost IAC, next hop equal to the list of next hops to router BR, and Advertising router equal to BR.

(6) Else, if the paths present in the table are intra-area paths, do nothing with the LSA (intra-area paths are always preferred).

(7) Else, the paths present in the routing table are also inter-area paths. Install the new path through BR if it is cheaper, overriding the paths in the routing table. Otherwise, if the new path is the same cost, add it to the list of paths that appear in the routing table entry.

16.3. Examining transit areas' summary-LSAs

This step is only performed by area border routers attached to one or more non-backbone areas that are capable of carrying transit traffic (i.e., "transit areas", or those areas whose TransitCapability parameter has been set to TRUE in Step 2 of the Dijkstra algorithm (see Section 16.1).

The purpose of the calculation below is to examine the transit areas to see whether they provide any better (shorter) paths than the paths previously calculated in Sections 16.1 and 16.2. Any paths found that are better than or equal to previously discovered paths are installed in the routing table.

The calculation also determines the actual next hop(s) for those destinations whose next hop was calculated as a virtual link in Sections 16.1 and 16.2. After completion of the calculation below, any paths calculated in Sections 16.1 and 16.2 that still have unresolved virtual next hops should be discarded.

The calculation proceeds as follows. All the transit areas' summary-LSAs are examined in turn. Each such summary-LSA describes a route through a transit area Area A to a Network N (N's address is obtained by masking the LSA's Link State ID with the network/subnet mask contained in the body of the LSA) or in the case of a Type 4 summary-LSA, to an AS boundary router N. Suppose also that the summary-LSA was originated by an area border router BR.

(1) If the cost advertised by the summary-LSA is LSInfinity, or if the LSA's LS age is equal to MaxAge, then examine the next LSA.

(2) If the summary-LSA was originated by the calculating router itself, examine the next LSA.

(3) Look up the routing table entry for N. (If N is an AS boundary router, look up the "router" routing table entry associated with the backbone area). If it does not exist, or if the route type is other than intra-area or inter-area, or if the area associated with the routing table entry is not the backbone area, then examine the next LSA. In other words, this calculation only updates backbone intra-area routes found in Section 16.1 and inter-area routes found in Section 16.2.

(4) Look up the routing table entry for the advertising router BR associated with the Area A. If it is unreachable, examine the next LSA. Otherwise, the cost to destination N is the sum of the cost in BR's Area A routing table entry and the cost advertised in the LSA. Call this cost IAC.

(5) If this cost is less than the cost occurring in N's routing table entry, overwrite N's list of next hops with those used for BR, and set N's routing table cost to IAC. Else, if IAC is the same as N's current cost, add BR's list of next hops to N's list of next hops. In any case, the area associated with N's routing table entry must remain the backbone area, and the path type (either intra-area or inter-area) must also remain the same.

It is important to note that the above calculation never makes unreachable destinations reachable, but instead just potentially finds better paths to already reachable destinations. The calculation installs any better cost found into the routing table entry, from which it may be readvertised in summary-LSAs to other areas.

As an example of the calculation, consider the Autonomous System pictured in Figure 17. There is a single non-backbone area (Area 1) that physically divides the backbone into two separate pieces. To maintain connectivity of the backbone, a virtual link has been configured between routers RT1 and RT4. On the right side of the figure, Network N1 belongs to the backbone. The dotted lines indicate that there is a much shorter intra-area

........................ . Area 1 (transit) . + . . | . +---+1 1+---+100 | . |RT2|----------|RT4|=========| . 1/+---+********* +---+ | . /******* . | . 1/Virtual . | 1+---+/ Link . Net|work =======|RT1|* . | N1 +---+\ . | . \ . | . \ . | . 1+---+1 1+---+20 | . |RT3|----------|RT5|=========| . +---+ +---+ | . . | ........................ +

Figure 17: Routing through transit areas

backbone path between router RT5 and Network N1 (cost 20) than there is between Router RT4 and Network N1 (cost 100). Both Router RT4 and Router RT5 will inject summary-LSAs for Network N1 into Area 1.

After the shortest-path tree has been calculated for the backbone in Section 16.1, Router RT1 (left end of the virtual link) will have calculated a path through Router RT4 for all data traffic destined for Network N1. However, since Router RT5 is so much closer to Network N1, all routers internal to Area 1 (e.g., Routers RT2 and RT3) will forward their Network N1 traffic towards Router RT5, instead of RT4. And indeed, after examining Area 1's summary-LSAs by the above calculation, Router RT1 will also forward Network N1 traffic towards RT5. Note that in this example the virtual link enables transit data traffic to be forwarded through Area 1, but the actual path the transit data traffic takes does not follow the virtual link. In other words, virtual links allow transit traffic to be forwarded through an area, but do not dictate the precise path that the traffic will take.

16.4. Calculating AS external routes

AS external routes are calculated by examining AS-external-LSAs. Each of the AS-external-LSAs is considered in turn. Most AS- external-LSAs describe routes to specific IP destinations. An AS-external-LSA can also describe a default route for the Autonomous System (Destination ID = DefaultDestination, network/subnet mask = 0x00000000). For each AS-external-LSA:

(1) If the cost specified by the LSA is LSInfinity, or if the LSA's LS age is equal to MaxAge, then examine the next LSA.

(2) If the LSA was originated by the calculating router itself, examine the next LSA.

(3) Call the destination described by the LSA N. N's address is obtained by masking the LSA's Link State ID with the network/subnet mask contained in the body of the LSA. Look up the routing table entries (potentially one per attached area) for the AS boundary router (ASBR) that originated the LSA. If no entries exist for router ASBR (i.e., ASBR is unreachable), do nothing with this LSA and consider the next in the list.

Else, this LSA describes an AS external path to destination N. Examine the forwarding address specified in the AS- external-LSA. This indicates the IP address to which packets for the destination should be forwarded.

If the forwarding address is set to 0.0.0.0, packets should be sent to the ASBR itself. Among the multiple routing table entries for the ASBR, select the preferred entry as follows. If RFC1583Compatibility is set to "disabled", prune the set of routing table entries for the ASBR as described in Section 16.4.1. In any case, among the remaining routing table entries, select the routing table entry with the least cost; when there are multiple least cost routing table entries the entry whose associated area has the largest OSPF Area ID (when considered as an unsigned 32-bit integer) is chosen.

If the forwarding address is non-zero, look up the forwarding address in the routing table.[24] The matching routing table entry must specify an intra-area or inter-area path; if no such path exists, do nothing with the LSA and consider the next in the list.

(4) Let X be the cost specified by the preferred routing table entry for the ASBR/forwarding address, and Y the cost specified in the LSA. X is in terms of the link state metric, and Y is a type 1 or 2 external metric.

(5) Look up the routing table entry for the destination N. If no entry exists for N, install the AS external path to N, with next hop equal to the list of next hops to the forwarding address, and advertising router equal to ASBR. If the external metric type is 1, then the path-type is set to type 1 external and the cost is equal to X+Y. If the external metric type is 2, the path-type is set to type 2 external, the link state component of the route's cost is X, and the type 2 cost is Y.

(6) Compare the AS external path described by the LSA with the existing paths in N's routing table entry, as follows. If the new path is preferred, it replaces the present paths in N's routing table entry. If the new path is of equal preference, it is added to N's routing table entry's list of paths.

(a) Intra-area and inter-area paths are always preferred over AS external paths.

(b) Type 1 external paths are always preferred over type 2 external paths. When all paths are type 2 external paths, the paths with the smallest advertised type 2 metric are always preferred.

(c) If the new AS external path is still indistinguishable from the current paths in the N's routing table entry, and RFC1583Compatibility is set to "disabled", select the preferred paths based on the intra-AS paths to the ASBR/forwarding addresses, as specified in Section 16.4.1.

(d) If the new AS external path is still indistinguishable from the current paths in the N's routing table entry, select the preferred path based on a least cost comparison. Type 1 external paths are compared by looking at the sum of the distance to the forwarding address and the advertised type 1 metric (X+Y). Type 2 external paths advertising equal type 2 metrics are compared by looking at the distance to the forwarding addresses.

16.4.1. External path preferences

When multiple intra-AS paths are available to ASBRs/forwarding addresses, the following rules indicate which paths are preferred. These rules apply when the same ASBR is reachable through multiple areas, or when trying to decide which of several AS-external-LSAs should be preferred. In the former case the paths all terminate at the same ASBR, while in the latter the paths terminate at separate ASBRs/forwarding addresses. In either case, each path is represented by a separate routing table entry as defined in Section 11.

This section only applies when RFC1583Compatibility is set to "disabled".

The path preference rules, stated from highest to lowest preference, are as follows. Note that as a result of these rules, there may still be multiple paths of the highest preference. In this case, the path to use must be determined based on cost, as described in Section 16.4.

o Intra-area paths using non-backbone areas are always the most preferred.

o The other paths, intra-area backbone paths and inter- area paths, are of equal preference.

16.5. Incremental updates -- summary-LSAs

When a new summary-LSA is received, it is not necessary to recalculate the entire routing table. Call the destination

described by the summary-LSA N (N's address is obtained by masking the LSA's Link State ID with the network/subnet mask contained in the body of the LSA), and let Area A be the area to which the LSA belongs. There are then two separate cases:

Case 1: Area A is the backbone and/or the router is not an area border router. In this case, the following calculations must be performed. First, if there is presently an inter-area route to the destination N, N's routing table entry is invalidated, saving the entry's values for later comparisons. Then the calculation in Section 16.2 is run again for the single destination N. In this calculation, all of Area A's summary-LSAs that describe a route to N are examined. In addition, if the router is an area border router attached to one or more transit areas, the calculation in Section 16.3 must be run again for the single destination. If the results of these calculations have changed the cost/path to an AS boundary router (as would be the case for a Type 4 summary-LSA) or to any forwarding addresses, all AS- external-LSAs will have to be reexamined by rerunning the calculation in Section 16.4. Otherwise, if N is now newly unreachable, the calculation in Section 16.4 must be rerun for the single destination N, in case an alternate external route to N exists.

Case 2: Area A is a transit area and the router is an area border router. In this case, the following calculations must be performed. First, if N's routing table entry presently contains one or more inter-area paths that utilize the transit area Area A, these paths should be removed. If this removes all paths from the routing table entry, the entry should be invalidated. The entry's old values should be saved for later comparisons. Next the calculation in Section 16.3 must be run again for the single destination N. If the results of this calculation have caused the cost to N to increase, the complete routing table calculation must be rerun starting with the Dijkstra algorithm specified in Section 16.1. Otherwise, if the cost/path to an AS boundary router (as would be the case for a Type 4 summary-LSA) or to any forwarding addresses has changed, all AS-external-LSAs will

have to be reexamined by rerunning the calculation in Section 16.4. Otherwise, if N is now newly unreachable, the calculation in Section 16.4 must be rerun for the single destination N, in case an alternate external route to N exists.

16.6. Incremental updates -- AS-external-LSAs

When a new AS-external-LSA is received, it is not necessary to recalculate the entire routing table. Call the destination described by the AS-external-LSA N. N's address is obtained by masking the LSA's Link State ID with the network/subnet mask contained in the body of the LSA. If there is already an intra- area or inter-area route to the destination, no recalculation is necessary (internal routes take precedence).

Otherwise, the procedure in Section 16.4 will have to be performed, but only for those AS-external-LSAs whose destination is N. Before this procedure is performed, the present routing table entry for N should be invalidated.

16.7. Events generated as a result of routing table changes

Changes to routing table entries sometimes cause the OSPF area border routers to take additional actions. These routers need to act on the following routing table changes:

o The cost or path type of a routing table entry has changed. If the destination described by this entry is a Network or AS boundary router, and this is not simply a change of AS external routes, new summary-LSAs may have to be generated (potentially one for each attached area, including the backbone). See Section 12.4.3 for more information. If a previously advertised entry has been deleted, or is no longer advertisable to a particular area, the LSA must be flushed from the routing domain by setting its LS age to MaxAge and reflooding (see Section 14.1).

o A routing table entry associated with a configured virtual link has changed. The destination of such a routing table entry is an area border router. The change indicates a modification to the virtual link's cost or viability.

If the entry indicates that the area border router is newly reachable, the corresponding virtual link is now operational. An InterfaceUp event should be generated for the virtual link, which will cause a virtual adjacency to begin to form (see Section 10.3). At this time the virtual link's IP interface address and the virtual neighbor's Neighbor IP address are also calculated.

If the entry indicates that the area border router is no longer reachable, the virtual link and its associated adjacency should be destroyed. This means an InterfaceDown event should be generated for the associated virtual link.

If the cost of the entry has changed, and there is a fully established virtual adjacency, a new router-LSA for the backbone must be originated. This in turn may cause further routing table changes.

16.8. Equal-cost multipath

The OSPF protocol maintains multiple equal-cost routes to all destinations. This can be seen in the steps used above to calculate the routing table, and in the definition of the routing table structure.

Each one of the multiple routes will be of the same type (intra-area, inter-area, type 1 external or type 2 external), cost, and will have the same associated area. However, each route may specify a separate next hop and Advertising router.

There is no requirement that a router running OSPF keep track of all possible equal-cost routes to a destination. An implementation may choose to keep only a fixed number of routes to any given destination. This does not affect any of the algorithms presented in this specification.

Footnotes

[1]The graph's vertices represent either routers, transit networks, or stub networks. Since routers may belong to multiple areas, it is not possible to color the graph's vertices.

[2]It is possible for all of a router's interfaces to be unnumbered point-to-point links. In this case, an IP address must be assigned to the router. This address will then be advertised in the router's router-LSA as a host route.

[3]Note that in these cases both interfaces, the non-virtual and the virtual, would have the same IP address.

[4]Note that no host route is generated for, and no IP packets can be addressed to, interfaces to unnumbered point-to-point networks. This is regardless of such an interface's state.

[5]It is instructive to see what happens when the Designated Router for the network crashes. Call the Designated Router for the network RT1, and the Backup Designated Router RT2. If Router RT1 crashes (or maybe its interface to the network dies), the other routers on the network will detect RT1's absence within RouterDeadInterval seconds. All routers may not detect this at precisely the same time; the routers that detect RT1's absence before RT2 does will, for a time, select RT2 to be both Designated Router and Backup Designated Router. When RT2 detects that RT1 is gone it will move itself to Designated Router. At this time, the remaining router having highest Router Priority will be selected as Backup Designated Router.

[6]On point-to-point networks, the lower level protocols indicate whether the neighbor is up and running. Likewise, existence of the neighbor on virtual links is indicated by the routing table calculation. However, in both these cases, the Hello Protocol is still used. This ensures that communication between the neighbors is bidirectional, and that each of the neighbors has a functioning routing protocol layer.

[7]When the identity of the Designated Router is changing, it may be quite common for a neighbor in this state to send the router a

Database Description packet; this means that there is some momentary disagreement on the Designated Router's identity.

[8]Note that it is possible for a router to resynchronize any of its fully established adjacencies by setting the adjacency's state back to ExStart. This will cause the other end of the adjacency to process a SeqNumberMismatch event, and therefore to also go back to ExStart state.

[9]The address space of IP networks and the address space of OSPF Router IDs may overlap. That is, a network may have an IP address which is identical (when considered as a 32-bit number) to some router's Router ID.

[10]"Discard" entries are necessary to ensure that route summarization at area boundaries will not cause packet looping.

[11]It is assumed that, for two different address ranges matching the destination, one range is more specific than the other. Non- contiguous subnet masks can be configured to violate this assumption. Such subnet mask configurations cannot be handled by the OSPF protocol.

[12]MaxAgeDiff is an architectural constant. It indicates the maximum dispersion of ages, in seconds, that can occur for a single LSA instance as it is flooded throughout the routing domain. If two LSAs differ by more than this, they are assumed to be different instances of the same LSA. This can occur when a router restarts and loses track of the LSA's previous LS sequence number. See Section 13.4 for more details.

[13]When two LSAs have different LS checksums, they are assumed to be separate instances. This can occur when a router restarts, and loses track of the LSA's previous LS sequence number. In the case where the two LSAs have the same LS sequence number, it is not possible to determine which LSA is actually newer. However, if the wrong LSA is accepted as newer, the originating router will simply originate another instance. See Section 13.4 for further details.

[14]There is one instance where a lookup must be done based on partial information. This is during the routing table calculation, when a network-LSA must be found based solely on its Link State ID.

The lookup in this case is still well defined, since no two network-LSAs can have the same Link State ID.

[15]This is the way RFC 1583 specified point-to-point representation. It has three advantages: a) it does not require allocating a subnet to the point-to-point link, b) it tends to bias the routing so that packets destined for the point-to-point interface will actually be received over the interface (which is useful for diagnostic purposes) and c) it allows network bootstrapping of a neighbor, without requiring that the bootstrap program contain an OSPF implementation.

[16]This is the more traditional point-to-point representation used by protocols such as RIP.

[17]This clause covers the case: Inter-area routes are not summarized to the backbone. This is because inter-area routes are always associated with the backbone area.

[18]This clause is only invoked when a non-backbone Area A supports transit data traffic (i.e., has TransitCapability set to TRUE). For example, in the area configuration of Figure 6, Area 2 can support transit traffic due to the configured virtual link between Routers RT10 and RT11. As a result, Router RT11 need only originate a single summary-LSA into Area 2 (having the collapsed destination N9- N11,H1), since all of Router RT11's other eligible routes have next hops belonging to Area 2 itself (and as such only need be advertised by other area border routers; in this case, Routers RT10 and RT7).

[19]By keeping more information in the routing table, it is possible for an implementation to recalculate the shortest path tree for only a single area. In fact, there are incremental algorithms that allow an implementation to recalculate only a portion of a single area's shortest path tree [Ref1]. However, these algorithms are beyond the scope of this specification.

[20]This is how the Link state request list is emptied, which eventually causes the neighbor state to transition to Full. See Section 10.9 for more details.

[21]It should be a relatively rare occurrence for an LSA's LS age to reach MaxAge in this fashion. Usually, the LSA will be replaced by

a more recent instance before it ages out.

[22]Strictly speaking, because of equal-cost multipath, the algorithm does not create a tree. We continue to use the "tree" terminology because that is what occurs most often in the existing literature.

[23]Note that the presence of any link back to V is sufficient; it need not be the matching half of the link under consideration from V to W. This is enough to ensure that, before data traffic flows between a pair of neighboring routers, their link state databases will be synchronized.

[24]When the forwarding address is non-zero, it should point to a router belonging to another Autonomous System. See Section 12.4.4 for more details.

References

[Ref1] McQuillan, J., I. Richer and E. Rosen, "ARPANET Routing Algorithm Improvements", BBN Technical Report 3803, April 1978.

[Ref2] Digital Equipment Corporation, "Information processing systems -- Data communications -- Intermediate System to Intermediate System Intra-Domain Routing Protocol", October 1987.

[Ref3] McQuillan, J., et.al., "The New Routing Algorithm for the ARPANET", IEEE Transactions on Communications, May 1980.

[Ref4] Perlman, R., "Fault-Tolerant Broadcast of Routing Information", Computer Networks, December 1983.

[Ref5] Postel, J., "Internet Protocol", STD 5, RFC 791, September 1981.

[Ref6] McKenzie, A., "ISO Transport Protocol specification ISO DP 8073", RFC 905, April 1984.

[Ref7] Deering, S., "Host extensions for IP multicasting", STD 5, RFC 1112, May 1988.

[Ref8] McCloghrie, K., and M. Rose, "Management Information Base for network management of TCP/IP-based internets: MIB-II", STD 17, RFC 1213, March 1991.

[Ref9] Moy, J., "OSPF Version 2", RFC 1583, March 1994.

[Ref10] Fuller, V., T. Li, J. Yu, and K. Varadhan, "Classless Inter-Domain Routing (CIDR): an Address Assignment and Aggregation Strategy", RFC1519, September 1993.

[Ref11] Reynolds, J., and J. Postel, "Assigned Numbers", STD 2, RFC 1700, October 1994.

[Ref12] Almquist, P., "Type of Service in the Internet Protocol Suite", RFC 1349, July 1992.

[Ref13] Leiner, B., et.al., "The DARPA Internet Protocol Suite", DDN Protocol Handbook, April 1985.

[Ref14] Bradley, T., and C. Brown, "Inverse Address Resolution Protocol", RFC 1293, January 1992.

[Ref15] deSouza, O., and M. Rodrigues, "Guidelines for Running OSPF Over Frame Relay Networks", RFC 1586, March 1994.

[Ref16] Bellovin, S., "Security Problems in the TCP/IP Protocol Suite", ACM Computer Communications Review, Volume 19, Number 2, pp. 32-38, April 1989.

[Ref17] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, April 1992.

[Ref18] Moy, J., "Multicast Extensions to OSPF", RFC 1584, March 1994.

[Ref19] Coltun, R., and V. Fuller, "The OSPF NSSA Option", RFC 1587, March 1994.

[Ref20] Ferguson, D., "The OSPF External Attributes LSA", work in progress.

[Ref21] Moy, J., "Extending OSPF to Support Demand Circuits", RFC 1793, April 1995.

[Ref22] Mogul, J., and S. Deering, "Path MTU Discovery", RFC 1191, November 1990.

[Ref23] Rekhter, Y., and T. Li, "A Border Gateway Protocol 4 (BGP- 4)", RFC 1771, March 1995.

[Ref24] Hinden, R., "Internet Routing Protocol Standardization Criteria", BBN, October 1991.

[Ref25] Moy, J., "OSPF Version 2", RFC 2178, July 1997.

[Ref26] Rosen, E., "Vulnerabilities of Network Control Protocols: An Example", Computer Communication Review, July 1981.