Connected: An Internet Encyclopedia
RFC 1583 - 16. Calculation Of The Routing Table

Top: Connected: An Internet Encyclopedia
Up: Requests For Comments
Up: RFC 1583
Prev: 15. Virtual Links
Next: 16.1. Calculating the shortest-path tree for an area

### 16. Calculation Of The Routing Table

This section details the OSPF routing table calculation. Using its attached areas' link state databases as input, a router runs the following algorithm, building its routing table step by step. At each step, the router must access individual pieces of the link state databases (e.g., a router links advertisement originated by a certain router). This access is performed by the lookup function discussed in Section 12.2. The lookup process may return a link state advertisement whose LS age is equal to MaxAge. Such an advertisement should not be used in the routing table calculation, and is treated just as if the lookup process had failed.

The OSPF routing table's organization is explained in Section 11. Two examples of the routing table build process are presented in Sections 11.2 and 11.3. This process can be broken into the following steps:

1. The present routing table is invalidated. The routing table is built again from scratch. The old routing table is saved so that changes in routing table entries can be identified.

2. The intra-area routes are calculated by building the shortest- path tree for each attached area. In particular, all routing table entries whose Destination Type is "area border router" are calculated in this step. This step is described in two parts. At first the tree is constructed by only considering those links between routers and transit networks. Then the stub networks are incorporated into the tree. During the area's shortest-path tree calculation, the area's TransitCapability is also calculated for later use in Step 4.

3. The inter-area routes are calculated, through examination of summary link advertisements. If the router is attached to multiple areas (i.e., it is an area border router), only backbone summary link advertisements are examined.

4. In area border routers connecting to one or more transit areas (i.e, non-backbone areas whose TransitCapability is found to be TRUE), the transit areas' summary link advertisements are examined to see whether better paths exist using the transit areas than were found in Steps 2-3 above.

5. Routes to external destinations are calculated, through examination of AS external link advertisements. The locations of the AS boundary routers (which originate the AS external link advertisements) have been determined in steps 2-4.

Steps 2-5 are explained in further detail below. The explanations describe the calculations for TOS 0 only. It may also be necessary to perform each step (separately) for each of the non-zero TOS values.[20] For more information concerning the building of non-zero TOS routes see Section 16.9.

Changes made to routing table entries as a result of these calculations can cause the OSPF protocol to take further actions. For example, a change to an intra-area route will cause an area border router to originate new summary link advertisements (see Section 12.4). See Section 16.7 for a complete list of the OSPF protocol actions resulting from routing table changes.

16.1. Calculating the shortest-path tree for an area

16.1.1. The next hop calculation

16.2. Calculating the inter-area routes
16.3. Examining transit areas' summary links
16.4. Calculating AS external routes
16.5. Incremental updates -- summary link advertisements
16.6. Incremental updates -- AS external link advertisements
16.7. Events generated as a result of routing table changes
16.8. Equal-cost multipath
16.9. Building the non-zero-TOS portion of the routing table

Next: 16.1. Calculating the shortest-path tree for an area

Connected: An Internet Encyclopedia
RFC 1583 - 16. Calculation Of The Routing Table