blank.gif (43 bytes)

Church Of The
Swimming Elephant

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

Up: 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

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.

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

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


Protect yourself from cyberstalkers, identity thieves, and those who would snoop on you.
Stop spam from invading your inbox without losing the mail you want. We give you more control over your e-mail than any other service.
Block popups, ads, and malicious scripts while you surf the net through our anonymous proxies.
Participate in Usenet, host your web files, easily send anonymous messages, and more, much more.
All private, all encrypted, all secure, all in an easy to use service, and all for only $5.95 a month!

Service Details

Have you gone to church today?
All pages ©1999, 2000, 2001, 2002, 2003 Church of the Swimming Elephant unless otherwise stated
Church of the Swimming Elephant©1999, 2000, 2001, 2002, 2003 is a wholly owned subsidiary of Packetderm, LLC.

Packetderm, LLC
210 Park Ave #308
Worcester, MA 01609