tech-invite   World Map     

3GPP     Specs     Glossaries     Architecture     IMS     UICC       IETF     RFCs     Groups     SIP     ABNFs       Search

RFC 2178

 
 
 

OSPF Version 2

Part 6 of 8, p. 137 to 167
Prev RFC Part       Next RFC Part

 


prevText      Top      Up      ToC       Page 137 
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-LSA originated by a certain router).  This
   access is performed by the lookup function discussed in Section 12.2.
   The lookup process may return an LSA whose LS age is equal to MaxAge.
   Such an LSA 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.

Top      Up      ToC       Page 138 
   (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-LSAs.  If the router is attached to multiple areas
       (i.e., it is an area border router), only backbone summary-LSAs
       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-LSAs 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-LSAs.  The locations of the AS
       boundary routers (which originate the AS-external-LSAs) have
       been determined in steps 2-4.

   Steps 2-5 are explained in further detail below.

   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-LSAs (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

   This calculation yields the set of intra-area routes associated with
   an area (called hereafter Area A).  A router calculates the
   shortest-path tree using itself as the root.[22] The formation of the
   shortest path tree is done here in two stages.  In the first stage,
   only links between routers and transit networks are considered.
   Using the Dijkstra algorithm, a tree is formed from this subset of
   the link state database.  In the second stage, leaves are added to
   the tree by considering the links to stub networks.

Top      Up      ToC       Page 139 
   The procedure will be explained using the graph terminology that was
   introduced in Section 2.  The area's link state database is
   represented as a directed graph.  The graph's vertices are routers,
   transit networks and stub networks.  The first stage of the procedure
   concerns only the transit vertices (routers and transit networks) and
   their connecting links.  Throughout the shortest path calculation,
   the following data is also associated with each transit vertex:


   Vertex (node) ID
       A 32-bit number uniquely identifying the vertex.  For router
       vertices this is the router's OSPF Router ID.  For network
       vertices, this is the IP address of the network's Designated
       Router.

   An LSA
       Each transit vertex has an associated LSA.  For router
       vertices, this is a router-LSA.  For transit networks, this
       is a network-LSA (which is actually originated by the
       network's Designated Router).  In any case, the LSA's Link
       State ID is always equal to the above Vertex ID.

   List of next hops
       The list of next hops for the current set of shortest paths
       from the root to this vertex.  There can be multiple
       shortest paths due to the equal-cost multipath capability.
       Each next hop indicates the outgoing router interface to use
       when forwarding traffic to the destination.  On broadcast,
       Point-to-MultiPoint and NBMA networks, the next hop also
       includes the IP address of the next router (if any) in the
       path towards the destination.

   Distance from root
       The link state cost of the current set of shortest paths
       from the root to the vertex.  The link state cost of a path
       is calculated as the sum of the costs of the path's
       constituent links (as advertised in router-LSAs and
       network-LSAs).  One path is said to be "shorter" than
       another if it has a smaller link state cost.


   The first stage of the procedure (i.e., the Dijkstra algorithm) can
   now be summarized as follows. At each iteration of the algorithm,
   there is a list of candidate vertices.  Paths from the root to these
   vertices have been found, but not necessarily the shortest ones.
   However, the paths to the candidate vertex that is closest to the
   root are guaranteed to be shortest; this vertex is added to the
   shortest-path tree, removed from the candidate list, and its adjacent

Top      Up      ToC       Page 140 
   vertices are examined for possible addition to/modification of the
   candidate list.  The algorithm then iterates again.  It terminates
   when the candidate list becomes empty.

   The following steps describe the algorithm in detail.  Remember that
   we are computing the shortest path tree for Area A.  All references
   to link state database lookup below are from Area A's database.

   (1) Initialize the algorithm's data structures.  Clear the list
       of candidate vertices.  Initialize the shortest-path tree to
       only the root (which is the router doing the calculation).
       Set Area A's TransitCapability to FALSE.

   (2) Call the vertex just added to the tree vertex V.  Examine
       the LSA associated with vertex V.  This is a lookup in the
       Area A's link state database based on the Vertex ID.  If
       this is a router-LSA, and bit V of the router-LSA (see
       Section A.4.2) is set, set Area A's TransitCapability to
       TRUE.  In any case, each link described by the LSA gives the
       cost to an adjacent vertex.  For each described link, (say
       it joins vertex V to vertex W):

       (a) If this is a link to a stub network, examine the next
           link in V's LSA.  Links to stub networks will be
           considered in the second stage of the shortest path
           calculation.

       (b) Otherwise, W is a transit vertex (router or transit
           network).  Look up the vertex W's LSA (router-LSA or
           network-LSA) in Area A's link state database.  If the
           LSA does not exist, or its LS age is equal to MaxAge, or
           it does not have a link back to vertex V, examine the
           next link in V's LSA.[23]

       (c) If vertex W is already on the shortest-path tree,
           examine the next link in the LSA.

       (d) Calculate the link state cost D of the resulting path
           from the root to vertex W.  D is equal to the sum of the
           link state cost of the (already calculated) shortest
           path to vertex V and the advertised cost of the link
           between vertices V and W.  If D is:

           o   Greater than the value that already appears for
               vertex W on the candidate list, then examine the
               next link.

Top      Up      ToC       Page 141 
           o   Equal to the value that appears for vertex W on the
               candidate list, calculate the set of next hops that
               result from using the advertised link.  Input to
               this calculation is the destination (W), and its
               parent (V).  This calculation is shown in Section
               16.1.1.  This set of hops should be added to the
               next hop values that appear for W on the candidate
               list.

           o   Less than the value that appears for vertex W on the
               candidate list, or if W does not yet appear on the
               candidate list, then set the entry for W on the
               candidate list to indicate a distance of D from the
               root.  Also calculate the list of next hops that
               result from using the advertised link, setting the
               next hop values for W accordingly.  The next hop
               calculation is described in Section 16.1.1; it takes
               as input the destination (W) and its parent (V).

   (3) If at this step the candidate list is empty, the shortest-
       path tree (of transit vertices) has been completely built
       and this stage of the procedure terminates.  Otherwise,
       choose the vertex belonging to the candidate list that is
       closest to the root, and add it to the shortest-path tree
       (removing it from the candidate list in the process). Note
       that when there is a choice of vertices closest to the root,
       network vertices must be chosen before router vertices in
       order to necessarily find all equal-cost paths. This is
       consistent with the tie-breakers that were introduced in the
       modified Dijkstra algorithm used by OSPF's Multicast routing
       extensions (MOSPF).

   (4) Possibly modify the routing table.  For those routing table
       entries modified, the associated area will be set to Area A,
       the path type will be set to intra-area, and the cost will
       be set to the newly discovered shortest path's calculated
       distance.

       If the newly added vertex is an area border router or AS
       boundary router, a routing table entry is added whose
       destination type is "router".  The Options field found in
       the associated router-LSA is copied into the routing table
       entry's Optional capabilities field. Call the newly added
       vertex Router X.  If Router X is the endpoint of one of the
       calculating router's virtual links, and the virtual link
       uses Area A as Transit area:  the virtual link is declared
       up, the IP address of the virtual interface is set to the IP
       address of the outgoing interface calculated above for

Top      Up      ToC       Page 142 
       Router X, and the virtual neighbor's IP address is set to
       Router X's interface address (contained in Router X's
       router-LSA) that points back to the root of the shortest-
       path tree; equivalently, this is the interface that points
       back to Router X's parent vertex on the shortest-path tree
       (similar to the calculation in Section 16.1.1).

       If the newly added vertex is a transit network, the routing
       table entry for the network is located.  The entry's
       Destination ID is the IP network number, which can be
       obtained by masking the Vertex ID (Link State ID) with its
       associated subnet mask (found in the body of the associated
       network-LSA).  If the routing table entry already exists
       (i.e., there is already an intra-area route to the
       destination installed in the routing table), multiple
       vertices have mapped to the same IP network.  For example,
       this can occur when a new Designated Router is being
       established.  In this case, the current routing table entry
       should be overwritten if and only if the newly found path is
       just as short and the current routing table entry's Link
       State Origin has a smaller Link State ID than the newly
       added vertex' LSA.

       If there is no routing table entry for the network (the
       usual case), a routing table entry for the IP network should
       be added.  The routing table entry's Link State Origin
       should be set to the newly added vertex' LSA.

   (5) Iterate the algorithm by returning to Step 2.

   The stub networks are added to the tree in the procedure's second
   stage.  In this stage, all router vertices are again examined.  Those
   that have been determined to be unreachable in the above first phase
   are discarded.  For each reachable router vertex (call it V), the
   associated router-LSA is found in the link state database.  Each stub
   network link appearing in the LSA is then examined, and the following
   steps are executed:


   (1) Calculate the distance D of stub network from the root.  D
       is equal to the distance from the root to the router vertex
       (calculated in stage 1), plus the stub network link's
       advertised cost.  Compare this distance to the current best
       cost to the stub network.  This is done by looking up the
       stub network's current routing table entry.  If the
       calculated distance D is larger, go on to examine the next
       stub network link in the LSA.

Top      Up      ToC       Page 143 
   (2) If this step is reached, the stub network's routing table
       entry must be updated.  Calculate the set of next hops that
       would result from using the stub network link.  This
       calculation is shown in Section 16.1.1; input to this
       calculation is the destination (the stub network) and the
       parent vertex (the router vertex).  If the distance D is the
       same as the current routing table cost, simply add this set
       of next hops to the routing table entry's list of next hops.
       In this case, the routing table already has a Link State
       Origin.  If this Link State Origin is a router-LSA whose
       Link State ID is smaller than V's Router ID, reset the Link
       State Origin to V's router-LSA.

       Otherwise D is smaller than the routing table cost.
       Overwrite the current routing table entry by setting the
       routing table entry's cost to D, and by setting the entry's
       list of next hops to the newly calculated set.  Set the
       routing table entry's Link State Origin to V's router-LSA.
       Then go on to examine the next stub network link.

   For all routing table entries added/modified in the second stage, the
   associated area will be set to Area A and the path type will be set to
   intra-area.  When the list of reachable router-LSAs is exhausted, the
   second stage is completed.  At this time, all intra-area routes
   associated with Area A have been determined.

   The specification does not require that the above two stage method be
   used to calculate the shortest path tree.  However, if another
   algorithm is used, an identical tree must be produced.  For this
   reason, it is important to note that links between transit vertices
   must be bidirectional in order to be included in the above tree.  It
   should also be mentioned that more efficient algorithms exist for
   calculating the tree; for example, the incremental SPF algorithm
   described in [Ref1].

Top      Up      ToC       Page 144 
16.1.1.  The next hop calculation

   This section explains how to calculate the current set of next hops
   to use for a destination.  Each next hop consists of the outgoing
   interface to use in forwarding packets to the destination together
   with the IP address of the next hop router (if any).  The next hop
   calculation is invoked each time a shorter path to the destination is
   discovered.  This can happen in either stage of the shortest-path
   tree calculation (see Section 16.1).  In stage 1 of the shortest-path
   tree calculation a shorter path is found as the destination is added
   to the candidate list, or when the destination's entry on the
   candidate list is modified (Step 2d of Stage 1).  In stage 2 a
   shorter path is discovered each time the destination's routing table
   entry is modified (Step 2 of Stage 2).

   The set of next hops to use for the destination may be recalculated
   several times during the shortest-path tree calculation, as shorter
   and shorter paths are discovered.  In the end, the destination's
   routing table entry will always reflect the next hops resulting from
   the absolute shortest path(s).

   Input to the next hop calculation is a) the destination and b) its
   parent in the current shortest path between the root (the calculating
   router) and the destination.  The parent is always a transit vertex
   (i.e., always a router or a transit network).

   If there is at least one intervening router in the current shortest
   path between the destination and the root, the destination simply
   inherits the set of next hops from the parent.  Otherwise, there are
   two cases.  In the first case, the parent vertex is the root (the
   calculating router itself).  This means that the destination is
   either a directly connected network or directly connected router.
   The outgoing interface in this case is simply the OSPF interface
   connecting to the destination network/router. If the destination is a
   router which connects to the calculating router via a Point-to-
   MultiPoint network, the destination's next hop IP address(es) can be
   determined by examining the destination's router-LSA: each link
   pointing back to the calculating router and having a Link Data field
   belonging to the Point-to-MultiPoint network provides an IP address
   of the next hop router. If the destination is a directly connected
   network, or a router which connects to the calculating router via a
   point-to-point interface, no next hop IP address is required. If the
   destination is a router connected to the calculating router via a
   virtual link, the setting of the next hop should be deferred until
   the calculation in Section 16.3.

Top      Up      ToC       Page 145 
   In the second case, the parent vertex is a network that directly
   connects the calculating router to the destination router.  The list
   of next hops is then determined by examining the destination's
   router-LSA.  For each link in the router-LSA that points back to the
   parent network, the link's Link Data field provides the IP address of
   a next hop router.  The outgoing interface to use can then be derived
   from the next hop IP address (or it can be inherited from the parent
   network).

16.2.  Calculating the inter-area routes

   The inter-area routes are calculated by examining summary-LSAs.  If
   the router has active attachments to multiple areas, only backbone
   summary-LSAs are examined.  Routers attached to a single area examine
   that area's summary-LSAs.  In either case, the summary-LSAs examined
   below are all part of a single area's link state database (call it
   Area A).

   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

Top      Up      ToC       Page 146 
       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 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.

Top      Up      ToC       Page 147 
   (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.

Top      Up      ToC       Page 148 
                      . 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

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

Top      Up      ToC       Page 149 
   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.

Top      Up      ToC       Page 150 
       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.

Top      Up      ToC       Page 151 
       (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   Otherwise, intra-area backbone paths are preferred.

    o   Inter-area paths are the least preferred.

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:

Top      Up      ToC       Page 152 
   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).

Top      Up      ToC       Page 153 
   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.

Top      Up      ToC       Page 154 
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 specifies 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.

Top      Up      ToC       Page 155 
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.

Top      Up      ToC       Page 156 
   [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.

Top      Up      ToC       Page 157 
   [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.

Top      Up      ToC       Page 158 
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,
           USC/Information Sciences Institute, September 1981.

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

   [Ref7]  Deering, S., "Host extensions for IP multicasting", STD 5,
           RFC 1112, Stanford University, 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, Hughes LAN Systems, Performance Systems
           International, March 1991.

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

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

   [Ref11] Reynolds, J., and J. Postel, "Assigned Numbers", STD 2, RFC
           1700, USC/Information Sciences Institute, 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.

Top      Up      ToC       Page 159 
   [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, Proteon,
           Inc., March 1994.

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

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

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

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

   [Ref23] Rekhter, Y. and T. Li, "A Border Gateway Protocol 4 (BGP-
           4)", RFC 1771, T.J. Watson Research Center, IBM Corp., cisco
           Systems, March 1995.

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

Top      Up      ToC       Page 160 
A. OSPF data formats

   This appendix describes the format of OSPF protocol packets and OSPF
   LSAs.  The OSPF protocol runs directly over the IP network layer.
   Before any data formats are described, the details of the OSPF
   encapsulation are explained.

   Next the OSPF Options field is described.  This field describes
   various capabilities that may or may not be supported by pieces of
   the OSPF routing domain. The OSPF Options field is contained in OSPF
   Hello packets, Database Description packets and in OSPF LSAs.

   OSPF packet formats are detailed in Section A.3.  A description of
   OSPF LSAs appears in Section A.4.

A.1 Encapsulation of OSPF packets

   OSPF runs directly over the Internet Protocol's network layer.  OSPF
   packets are therefore encapsulated solely by IP and local data-link
   headers.

   OSPF does not define a way to fragment its protocol packets, and
   depends on IP fragmentation when transmitting packets larger than the
   network MTU. If necessary, the length of OSPF packets can be up to
   65,535 bytes (including the IP header). The OSPF packet types that
   are likely to be large (Database Description Packets, Link State
   Request, Link State Update, and Link State Acknowledgment packets)
   can usually be split into several separate protocol packets, without
   loss of functionality.  This is recommended; IP fragmentation should
   be avoided whenever possible. Using this reasoning, an attempt should
   be made to limit the sizes of OSPF packets sent over virtual links to
   576 bytes unless Path MTU Discovery is being performed (see [Ref22]).

   The other important features of OSPF's IP encapsulation are:

   o  Use of IP multicast.  Some OSPF messages are multicast, when
      sent over broadcast networks.  Two distinct IP multicast addresses
      are used.  Packets sent to these multicast addresses should never
      be forwarded; they are meant to travel a single hop only.  To
      ensure that these packets will not travel multiple hops, their IP
      TTL must be set to 1.

Top      Up      ToC       Page 161 
   AllSPFRouters
      This multicast address has been assigned the value 224.0.0.5. All
      routers running OSPF should be prepared to receive packets sent to
      this address.  Hello packets are always sent to this destination.
      Also, certain OSPF protocol packets are sent to this address
      during the flooding procedure.

   AllDRouters
      This multicast address has been assigned the value 224.0.0.6. Both
      the Designated Router and Backup Designated Router must be
      prepared to receive packets destined to this address.  Certain
      OSPF protocol packets are sent to this address during the flooding
      procedure.

   o   OSPF is IP protocol number 89.  This number has been registered
       with the Network Information Center.  IP protocol number
       assignments are documented in [Ref11].

   o   All OSPF routing protocol packets are sent using the normal
       service TOS value of binary 0000 defined in [Ref12].

   o   Routing protocol packets are sent with IP precedence set to
       Internetwork Control.  OSPF protocol packets should be given
       precedence over regular IP data traffic, in both sending and
       receiving.  Setting the IP precedence field in the IP header to
       Internetwork Control [Ref5] may help implement this objective.

Top      Up      ToC       Page 162 
A.2 The Options field

   The OSPF Options field is present in OSPF Hello packets, Database
   Description packets and all LSAs.  The Options field enables OSPF
   routers to support (or not support) optional capabilities, and to
   communicate their capability level to other OSPF routers.  Through
   this mechanism routers of differing capabilities can be mixed within
   an OSPF routing domain.

   When used in Hello packets, the Options field allows a router to
   reject a neighbor because of a capability mismatch.  Alternatively,
   when capabilities are exchanged in Database Description packets a
   router can choose not to forward certain LSAs to a neighbor because
   of its reduced functionality.  Lastly, listing capabilities in LSAs
   allows routers to forward traffic around reduced functionality
   routers, by excluding them from parts of the routing table
   calculation.

   Five bits of the OSPF Options field have been assigned, although only
   one (the E-bit) is described completely by this memo. Each bit is
   described briefly below. Routers should reset (i.e. clear)
   unrecognized bits in the Options field when sending Hello packets or
   Database Description packets and when originating LSAs. Conversely,
   routers encountering unrecognized Option bits in received Hello
   Packets, Database Description packets or LSAs should ignore the
   capability and process the packet/LSA normally.

               +------------------------------------+
               | * | * | DC | EA | N/P | MC | E | * |
               +------------------------------------+

                           The Options field

   E-bit
      This bit describes the way AS-external-LSAs are flooded, as
      described in Sections 3.6, 9.5, 10.8 and 12.1.2 of this memo.

   MC-bit
      This bit describes whether IP multicast datagrams are forwarded
      according to the specifications in [Ref18].

   N/P-bit
      This bit describes the handling of Type-7 LSAs, as specified in
      [Ref19].

   EA-bit
      This bit describes the router's willingness to receive and
      forward External-Attributes-LSAs, as specified in [Ref20].

Top      Up      ToC       Page 163 
   DC-bit
      This bit describes the router's handling of demand circuits, as
      specified in [Ref21].

A.3 OSPF Packet Formats

   There are five distinct OSPF packet types. All OSPF packet types
   begin with a standard 24 byte header.  This header is described
   first.  Each packet type is then described in a succeeding section.
   In these sections each packet's division into fields is displayed,
   and then the field definitions are enumerated.

   All OSPF packet types (other than the OSPF Hello packets) deal with
   lists of LSAs.  For example, Link State Update packets implement the
   flooding of LSAs throughout the OSPF routing domain.  Because of
   this, OSPF protocol packets cannot be parsed unless the format of
   LSAs is also understood.  The format of LSAs is described in Section
   A.4.

   The receive processing of OSPF packets is detailed in Section 8.2.
   The sending of OSPF packets is explained in Section 8.1.

Top      Up      ToC       Page 164 
A.3.1 The OSPF packet header

   Every OSPF packet starts with a standard 24 byte header.  This header
   contains all the information necessary to determine whether the
   packet should be accepted for further processing.  This determination
   is described in Section 8.2 of the specification.

        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |   Version #   |     Type      |         Packet length         |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                          Router ID                            |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                           Area ID                             |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |           Checksum            |             AuType            |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                       Authentication                          |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                       Authentication                          |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


   Version #
      The OSPF version number.  This specification documents version 2
      of the protocol.

   Type
      The OSPF packet types are as follows. See Sections A.3.2 through
      A.3.6 for details.

                  Type   Description
                  ________________________________
                  1      Hello
                  2      Database Description
                  3      Link State Request
                  4      Link State Update
                  5      Link State Acknowledgment


   Packet length
      The length of the OSPF protocol packet in bytes.  This length
      includes the standard OSPF header.

   Router ID
      The Router ID of the packet's source.

Top      Up      ToC       Page 165 
   Area ID
      A 32 bit number identifying the area that this packet belongs
      to.  All OSPF packets are associated with a single area.  Most
      travel a single hop only.  Packets travelling over a virtual
      link are labelled with the backbone Area ID of 0.0.0.0.

   Checksum
      The standard IP checksum of the entire contents of the packet,
      starting with the OSPF packet header but excluding the 64-bit
      authentication field.  This checksum is calculated as the 16-bit
      one's complement of the one's complement sum of all the 16-bit
      words in the packet, excepting the authentication field.  If the
      packet's length is not an integral number of 16-bit words, the
      packet is padded with a byte of zero before checksumming.  The
      checksum is considered to be part of the packet authentication
      procedure; for some authentication types the checksum
      calculation is omitted.

   AuType
      Identifies the authentication procedure to be used for the
      packet.  Authentication is discussed in Appendix D of the
      specification.  Consult Appendix D for a list of the currently
      defined authentication types.

   Authentication
      A 64-bit field for use by the authentication scheme. See
      Appendix D for details.

Top      Up      ToC       Page 166 
A.3.2 The Hello packet

   Hello packets are OSPF packet type 1.  These packets are sent
   periodically on all interfaces (including virtual links) in order to
   establish and maintain neighbor relationships.  In addition, Hello
   Packets are multicast on those physical networks having a multicast
   or broadcast capability, enabling dynamic discovery of neighboring
   routers.

   All routers connected to a common network must agree on certain
   parameters (Network mask, HelloInterval and RouterDeadInterval).
   These parameters are included in Hello packets, so that differences
   can inhibit the forming of neighbor relationships. A detailed
   explanation of the receive processing for Hello packets is presented
   in Section 10.5.  The sending of Hello packets is covered in Section
   9.5.


        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |   Version #   |       1       |         Packet length         |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                          Router ID                            |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                           Area ID                             |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |           Checksum            |             AuType            |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                       Authentication                          |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                       Authentication                          |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                        Network Mask                           |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |         HelloInterval         |    Options    |    Rtr Pri    |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                     RouterDeadInterval                        |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                      Designated Router                        |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                   Backup Designated Router                    |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                          Neighbor                             |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                              ...                              |

Top      Up      ToC       Page 167 
   Network mask
      The network mask associated with this interface.  For example,
      if the interface is to a class B network whose third byte is
      used for subnetting, the network mask is 0xffffff00.

   Options
      The optional capabilities supported by the router, as documented
      in Section A.2.

   HelloInterval
      The number of seconds between this router's Hello packets.

   Rtr Pri
      This router's Router Priority.  Used in (Backup) Designated
      Router election.  If set to 0, the router will be ineligible to
      become (Backup) Designated Router.

   RouterDeadInterval
      The number of seconds before declaring a silent router down.

   Designated Router
      The identity of the Designated Router for this network, in the
      view of the sending router.  The Designated Router is identified
      here by its IP interface address on the network.  Set to 0.0.0.0
      if there is no Designated Router.

   Backup Designated Router
      The identity of the Backup Designated Router for this network,
      in the view of the sending router.  The Backup Designated Router
      is identified here by its IP interface address on the network.
      Set to 0.0.0.0 if there is no Backup Designated Router.

   Neighbor
      The Router IDs of each router from whom valid Hello packets have
      been seen recently on the network.  Recently means in the last
      RouterDeadInterval seconds.


Next RFC Part