Tech-invite3GPPspaceIETFspace
959493929190898887868584838281807978777675747372717069686766656463626160595857565554535251504948474645444342414039383736353433323130292827262524232221201918171615141312111009080706050403020100
in Index   Prev   Next

RFC 1583

OSPF Version 2

Pages: 216
Obsoletes:  1247
Obsoleted by:  2178
Part 7 of 9 – Pages 152 to 176
First   Prev   Next

ToP   noToC   RFC1583 - Page 152   prevText
    16.3.  Examining transit areas' summary links

        This step is only performed by area border routers attached to
        one or more transit areas. Transit areas are those areas
        supporting one or more virtual links; their TransitCapability
        parameter has been set to TRUE in Step 2 of the Dijkstra
        algorithm (see Section 16.1). They are the only non-backbone
        areas that can carry data traffic that neither originates nor
        terminates in the area itself.

        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 link advertisements are examined in turn.  Each such
        summary link advertisement describes a route through a transit
        area Area A to a Network N (N's address is obtained by masking
        the advertisement's Link State ID with the network/subnet mask
        contained in the body of the advertisement) or in the case of a
        Type 4 summary link advertisement, to an AS boundary router N.
        Suppose also that the summary link advertisement was originated
        by an area border router BR.

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

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

        (3) Look up the routing table entry for N. 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 advertisement.
            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 advertisement. 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 advertisement. Call this cost
            IAC.
ToP   noToC   RFC1583 - Page 153
        (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. Also,
        unlike Section 16.3 of [RFC 1247], the above calculation
        installs any better cost found into the routing table entry,
        from which it may be readvertised in summary link advertisements
        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
ToP   noToC   RFC1583 - Page 154
        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 link
        advertisements 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 link advertisements by the above
        calculation, Router RT1 will also forward Network N1 traffic
        towards RT5. Note that in this example the virtual link enables
        Network N1 traffic to be forwarded through the transit area Area
        1, but the actual path the 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 link
        advertisements.  Each of the AS external link advertisements is
        considered in turn.  Most AS external link advertisements
        describe routes to specific IP destinations.  An AS external
        link advertisement can also describe a default route for the
        Autonomous System (Destination ID = DefaultDestination,
        network/subnet mask = 0x00000000).  For each AS external link
        advertisement:


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

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

        (3) Call the destination described by the advertisement N.  N's
            address is obtained by masking the advertisement's Link
            State ID with the network/subnet mask contained in the body
            of the advertisement.  Look up the routing table entry for
            the AS boundary router (ASBR) that originated the
            advertisement. If no entry exists for router ASBR (i.e.,
            ASBR is unreachable), do nothing with this advertisement and
            consider the next in the list.
ToP   noToC   RFC1583 - Page 155
            Else, this advertisement describes an AS external path to
            destination N.  Examine the forwarding address specified in
            the AS external link advertisement.  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.  Otherwise, look
            up the forwarding address in the routing table.[23] An
            intra-area or inter-area path must exist to the forwarding
            address.  If no such path exists, do nothing with the
            advertisement and consider the next in the list.

            Call the routing table distance to the forwarding address X
            (when the forwarding address is set to 0.0.0.0, this is the
            distance to the ASBR itself), and the cost specified in the
            advertisement Y.  X is in terms of the link state metric,
            and Y is a type 1 or 2 external metric.

        (4) Next, 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.

        (5) Else, if the paths present in the table are not type 1 or
            type 2 external paths, do nothing (AS external paths have
            the lowest priority).

        (6) Otherwise, compare the cost of this new AS external path to
            the ones present in the table.  Type 1 external paths are
            always shorter than type 2 external paths.  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 are compared by looking at the
            advertised type 2 metrics, and then if necessary, the
            distance to the forwarding addresses.

            If the new path is shorter, it replaces the present paths in
            the routing table entry.  If the new path is the same cost,
            it is added to the routing table entry's list of paths.
ToP   noToC   RFC1583 - Page 156
    16.5.  Incremental updates -- summary link advertisements

        When a new summary link advertisement is received, it is not
        necessary to recalculate the entire routing table.  Call the
        destination described by the summary link advertisement N (N's
        address is obtained by masking the advertisement's Link State ID
        with the network/subnet mask contained in the body of the
        advertisement), and let Area A be the area to which the
        advertisement 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
            link advertisements 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 link advertisement) or to any forwarding addresses,
            all AS external link advertisements 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 link advertisement)
            or to any forwarding addresses has changed, all AS external
            link advertisements will have to be reexamined by rerunning
ToP   noToC   RFC1583 - Page 157
            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 link advertisements

        When a new AS external link advertisement is received, it is not
        necessary to recalculate the entire routing table.  Call the
        destination described by the AS external link advertisement N.
        N's address is obtained by masking the advertisement's Link
        State ID with the network/subnet mask contained in the body of
        the advertisement. 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 link advertisements
        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 link advertisements 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 advertisement 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 (via TOS 0), the corresponding virtual link is now
ToP   noToC   RFC1583 - Page 158
            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 (via TOS 0), 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 links
            advertisement 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 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.


    16.9.  Building the non-zero-TOS portion of the routing table

        The OSPF protocol can calculate a different set of routes for
        each IP TOS (see Section 2.4).  Support for TOS-based routing is
        optional.  TOS-capable and non-TOS-capable routers can be mixed
        in an OSPF routing domain.  Routers not supporting TOS calculate
        only the TOS 0 route to each destination.  These routes are then
        used to forward all data traffic, regardless of the TOS
        indications in the data packet's IP header.  A router that does
        not support TOS indicates this fact to the other OSPF routers by
        clearing the T-bit in the Options field of its router links
ToP   noToC   RFC1583 - Page 159
        advertisement.

        The above sections detailing the routing table calculations
        handle the TOS 0 case only.  In general, for routers supporting
        TOS-based routing, each piece of the routing table calculation
        must be rerun separately for the non-zero TOS values.  When
        calculating routes for TOS X, only TOS X metrics can be used.
        Any link state advertisement may specify a separate cost for
        each TOS (a cost for TOS 0 must always be specified).  The
        encoding of TOS in OSPF link state advertisements is described
        in Section 12.3.

        An advertisement can specify that it is restricted to TOS 0
        (i.e., non-zero TOS is not handled) by clearing the T-bit in the
        link state advertisement's Option field.  Such advertisements
        are not used when calculating routes for non-zero TOS.  For this
        reason, it is possible that a destination is unreachable for
        some non-zero TOS.  In this case, the TOS 0 path is used when
        forwarding packets (see Section 11.1).

        The following lists the modifications needed when running the
        routing table calculation for a non-zero TOS value (called TOS
        X).  In general, routers and advertisements that do not support
        TOS are omitted from the calculation.


        Calculating the shortest-path tree (Section  16.1).
            Routers that do not support TOS-based routing should be
            omitted from the shortest-path tree calculation.  These
            routers are identified as those having the T-bit reset in
            the Options field of their router links advertisements.
            Such routers should never be added to the Dijktra
            algorithm's candidate list, nor should their router links
            advertisements be examined when adding the stub networks to
            the tree.  In particular, if the T-bit is reset in the
            calculating router's own router links advertisement, it does
            not run the shortest-path tree calculation for non-zero TOS
            values.

        Calculating the inter-area routes (Section  16.2).
            Inter-area paths are the concatenation of a path to an area
            border router with a summary link.  When calculating TOS X
            routes, both path components must also specify TOS X.  In
            other words, only TOS X paths to the area border router are
            examined, and the area border router must be advertising a
            TOS X route to the destination.  Note that this means that
            summary link advertisements having the T-bit reset in their
            Options field are not considered.
ToP   noToC   RFC1583 - Page 160
        Examining transit areas' summary links (Section 16.3).
            This calculation again considers the concatenation of a path
            to an area border router with a summary link.  As with
            inter-area routes, only TOS X paths to the area border
            router are examined, and the area border router must be
            advertising a TOS X route to the destination.

        Calculating AS external routes (Section 16.4).
            This calculation considers the concatenation of a path to a
            forwarding address with an AS external link.  Only TOS X
            paths to the forwarding address are examined, and the AS
            boundary router must be advertising a TOS X route to the
            destination.  Note that this means that AS external link
            advertisements having the T-bit reset in their Options field
            are not considered.

            In addition, the advertising AS boundary router must also be
            reachable for its advertisements to be considered (see
            Section 16.4).  However, if the advertising router and the
            forwarding address are not one in the same, the advertising
            router need only be reachable via TOS 0.
ToP   noToC   RFC1583 - Page 161
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 links advertisement 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
ToP   noToC   RFC1583 - Page 162
    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]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.

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

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

    [13]There is one instance where a lookup must be done based on
    partial information.  This is during the routing table calculation,
    when a network links advertisement must be found based solely on its
    Link State ID.  The lookup in this case is still well defined, since
    no two network links advertisements can have the same Link State ID.

    [14]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.

    [15]This clause is only invoked when Area A is a Transit area
    supporting one or more virtual links. For example, in the area
    configuration of Figure 6, Router RT11 need only originate a single
    summary link having the (collapsed) destination N9-N11,H1 into its
    connected Transit area Area 2, since all of its other eligible
    routes have next hops belonging to Area 2 (and as such only need be
    advertised by other area border routers; in this case, Routers RT10
ToP   noToC   RFC1583 - Page 163
    and RT7).

    [16]By keeping more information in the routing table, it is possible
    for an implementation to recalculate the shortest path tree only for
    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 [BBN].  However, these algorithms are beyond the
    scope of this specification.

    [17]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.

    [18]It should be a relatively rare occurrence for an advertisement's
    LS age to reach MaxAge in this fashion.  Usually, the advertisement
    will be replaced by a more recent instance before it ages out.

    [19]Only the TOS 0 routes are important here because all OSPF
    protocol packets are sent with TOS = 0.  See Appendix A.

    [20]It may be the case that paths to certain destinations do not
    vary based on TOS.  For these destinations, the routing calculation
    need not be repeated for each TOS value.  In addition, there need
    only be a single routing table entry for these destinations (instead
    of a separate entry for each TOS value).

    [21]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.

    [22]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.

    [23]When the forwarding address is non-zero, it should point to a
    router belonging to another Autonomous System.  See Section 12.4.5
    for more details.
ToP   noToC   RFC1583 - Page 164
References

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

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

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

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

    [RFC 791]       Postel, J., "Internet Protocol", STD 5, RFC 791,
                    USC/Information Sciences Institute, September 1981.

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

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

    [RFC 1213]      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.

    [RFC 1247]      Moy, J., "OSPF Version 2", RFC 1247, Proteon, Inc.,
                    July 1991.

    [RFC 1519]      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.

    [RFC 1340]      Reynolds, J., and J. Postel, "Assigned Numbers", STD
                    2, RFC 1340, USC/Information Sciences Institute,
                    July 1992.

    [RFC 1349]      Almquist, P., "Type of Service in the Internet
                    Protocol Suite", RFC 1349, July 1992.
ToP   noToC   RFC1583 - Page 165
    [RS-85-153]     Leiner, B., et.al., "The DARPA Internet Protocol
                    Suite", DDN Protocol Handbook, April 1985.
ToP   noToC   RFC1583 - Page 166
A. OSPF data formats

    This appendix describes the format of OSPF protocol packets and OSPF
    link state advertisements.  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 link state
    advertisements.

    OSPF packet formats are detailed in Section A.3.  A description of
    OSPF link state advertisements 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.  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 packets sent over virtual links to 576
    bytes.  However, if necessary, the length of OSPF packets can be up
    to 65,535 bytes (including the IP header).

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

    o   Use of IP multicast.  Some OSPF messages are multicast, when
        sent over multi-access 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.

        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
ToP   noToC   RFC1583 - Page 167
            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 [RFC 1340].

    o   Routing protocol packets are sent with IP TOS of 0.  The OSPF
        protocol supports TOS-based routing.  Routes to any particular
        destination may vary based on TOS.  However, all OSPF routing
        protocol packets are sent using the normal service TOS value of
        binary 0000 defined in [RFC 1349].

    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 [RFC 791] may help implement this
        objective.
ToP   noToC   RFC1583 - Page 168
A.2 The Options field

    The OSPF Options field is present in OSPF Hello packets, Database
    Description packets and all link state advertisements.  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 link state advertisements
    to a neighbor because of its reduced functionality.  Lastly, listing
    capabilities in link state advertisements allows routers to route
    traffic around reduced functionality routers, by excluding them from
    parts of the routing table calculation.

    Two capabilities are currently defined.  For each capability, the
    effect of the capability's appearance (or lack of appearance) in
    Hello packets, Database Description packets and link state
    advertisements is specified below.  For example, the
    ExternalRoutingCapability (below called the E-bit) has meaning only
    in OSPF Hello Packets.  Routers should reset (i.e.  clear) the
    unassigned part of the capability field when sending Hello packets
    or Database Description packets and when originating link state
    advertisements.

    Additional capabilities may be assigned in the future.  Routers
    encountering unrecognized capabilities in received Hello Packets,
    Database Description packets or link state advertisements should
    ignore the capability and process the packet/advertisement normally.

                               +-+-+-+-+-+-+-+-+
                               | | | | | | |E|T|
                               +-+-+-+-+-+-+-+-+

                             The Options field


    T-bit
        This describes the router's TOS capability.  If the T-bit is
        reset, then the router supports only a single TOS (TOS 0).  Such
        a router is also said to be incapable of TOS-routing, and
        elsewhere in this document referred to as a TOS-0-only router.
        The absence of the T-bit in a router links advertisement causes
        the router to be skipped when building a non-zero TOS shortest-
        path tree (see Section 16.9).  In other words, routers incapable
ToP   noToC   RFC1583 - Page 169
        of TOS routing will be avoided as much as possible when
        forwarding data traffic requesting a non-zero TOS.  The absence
        of the T-bit in a summary link advertisement or an AS external
        link advertisement indicates that the advertisement is
        describing a TOS 0 route only (and not routes for non-zero TOS).

    E-bit
        This bit reflects the associated area's
        ExternalRoutingCapability.  AS external link advertisements are
        not flooded into/through OSPF stub areas (see Section 3.6).  The
        E-bit ensures that all members of a stub area agree on that
        area's configuration.  The E-bit is meaningful only in OSPF
        Hello packets.  When the E-bit is reset in the Hello packet sent
        out a particular interface, it means that the router will
        neither send nor receive AS external link state advertisements
        on that interface (in other words, the interface connects to a
        stub area).  Two routers will not become neighbors unless they
        agree on the state of the E-bit.
ToP   noToC   RFC1583 - Page 170
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 link state advertisements.  For example, Link State Update
    packets implement the flooding of advertisements throughout the OSPF
    routing domain.  Because of this, OSPF protocol packets cannot be
    parsed unless the format of link state advertisements is also
    understood.  The format of Link state advertisements 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   noToC   RFC1583 - Page 171
A.3.1 The OSPF packet header

    Every OSPF packet starts with a common 24 byte header.  This header
    contains all the necessary information 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.  The format of each of
        these packet types is described in a succeeding section.



                          Type   Description
                          ________________________________
                          1      Hello
                          2      Database Description
                          3      Link State Request
                          4      Link State Update
                          5      Link State Acknowledgment
ToP   noToC   RFC1583 - Page 172
    Packet length
        The length of the protocol packet in bytes.  This length
        includes the standard OSPF header.

    Router ID
        The Router ID of the packet's source.  In OSPF, the source and
        destination of a routing protocol packet are the two ends of an
        (potential) adjacency.

    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.

    AuType
        Identifies the authentication scheme 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.
ToP   noToC   RFC1583 - Page 173
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   noToC   RFC1583 - Page 174
    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 advertising 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 advertising 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.
ToP   noToC   RFC1583 - Page 175
A.3.3 The Database Description packet

    Database Description packets are OSPF packet type 2.  These packets
    are exchanged when an adjacency is being initialized.  They describe
    the contents of the topological database.  Multiple packets may be
    used to describe the database.  For this purpose a poll-response
    procedure is used.  One of the routers is designated to be master,
    the other a slave.  The master sends Database Description packets
    (polls) which are acknowledged by Database Description packets sent
    by the slave (responses).  The responses are linked to the polls via
    the packets' DD sequence numbers.


        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 #   |       2       |         Packet length         |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                          Router ID                            |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                           Area ID                             |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |           Checksum            |             AuType            |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                       Authentication                          |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                       Authentication                          |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |       0       |       0       |    Options    |0|0|0|0|0|I|M|MS
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                     DD sequence number                        |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                                                               |
       +-                                                             -+
       |                             A                                 |
       +-                 Link State Advertisement                    -+
       |                           Header                              |
       +-                                                             -+
       |                                                               |
       +-                                                             -+
       |                                                               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                              ...                              |


    The format of the Database Description packet is very similar to
    both the Link State Request and Link State Acknowledgment packets.
    The main part of all three is a list of items, each item describing
ToP   noToC   RFC1583 - Page 176
    a piece of the topological database.  The sending of Database
    Description Packets is documented in Section 10.8.  The reception of
    Database Description packets is documented in Section 10.6.

    0   These fields are reserved.  They must be 0.

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

    I-bit
        The Init bit.  When set to 1, this packet is the first in the
        sequence of Database Description Packets.

    M-bit
        The More bit.  When set to 1, it indicates that more Database
        Description Packets are to follow.

    MS-bit
        The Master/Slave bit.  When set to 1, it indicates that the
        router is the master during the Database Exchange process.
        Otherwise, the router is the slave.

    DD sequence number
        Used to sequence the collection of Database Description Packets.
        The initial value (indicated by the Init bit being set) should
        be unique.  The DD sequence number then increments until the
        complete database description has been sent.


    The rest of the packet consists of a (possibly partial) list of the
    topological database's pieces.  Each link state advertisement in the
    database is described by its link state advertisement header.  The
    link state advertisement header is documented in Section A.4.1.  It
    contains all the information required to uniquely identify both the
    advertisement and the advertisement's current instance.


(next page on part 8)

Next Section