tech-invite   World Map     

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

RFC 2328

 
 
 

OSPF Version 2

Part 5 of 8, p. 107 to 135
Prev RFC Part       Next RFC Part

 


prevText      Top      Up      ToC       Page 107 
11.  The Routing Table Structure

    The routing table data structure contains all the information
    necessary to forward an IP data packet toward its destination.  Each
    routing table entry describes the collection of best paths to a
    particular destination.  When forwarding an IP data packet, the
    routing table entry providing the best match for the packet's IP
    destination is located.  The matching routing table entry then
    provides the next hop towards the packet's destination.  OSPF also
    provides for the existence of a default route (Destination ID =
    DefaultDestination, Address Mask =  0x00000000).  When the default
    route exists, it matches all IP destinations (although any other
    matching entry is a better match).  Finding the routing table entry
    that best matches an IP destination is further described in Section
    11.1.

    There is a single routing table in each router.  Two sample routing
    tables are described in Sections 11.2 and 11.3.  The building of the
    routing table is discussed in Section 16.

Top      Up      ToC       Page 108 
    The rest of this section defines the fields found in a routing table
    entry.  The first set of fields describes the routing table entry's
    destination.


    Destination Type
        Destination type is either "network" or "router". Only network
        entries are actually used when forwarding IP data traffic.
        Router routing table entries are used solely as intermediate
        steps in the routing table build process.

        A network is a range of IP addresses, to which IP data traffic
        may be forwarded.  This includes IP networks (class A, B, or C),
        IP subnets, IP supernets and single IP hosts.  The default route
        also falls into this category.

        Router entries are kept for area border routers and AS boundary
        routers.  Routing table entries for area border routers are used
        when calculating the inter-area routes (see Section 16.2), and
        when maintaining configured virtual links (see Section 15).
        Routing table entries for AS boundary routers are used when
        calculating the AS external routes (see Section 16.4).

    Destination ID
        The destination's identifier or name.  This depends on the
        Destination Type.  For networks, the identifier is their
        associated IP address.  For routers, the identifier is the OSPF
        Router ID.[9]

    Address Mask
        Only defined for networks.  The network's IP address together
        with its address mask defines a range of IP addresses.  For IP
        subnets, the address mask is referred to as the subnet mask.
        For host routes, the mask is "all ones" (0xffffffff).

    Optional Capabilities
        When the destination is a router this field indicates the
        optional OSPF capabilities supported by the destination router.
        The only optional capability defined by this specification is
        the ability to process AS-external-LSAs.  For a further
        discussion of OSPF's optional capabilities, see Section 4.5.

Top      Up      ToC       Page 109 
    The set of paths to use for a destination may vary based on the OSPF
    area to which the paths belong.  This means that there may be
    multiple routing table entries for the same destination, depending
    on the values of the next field.


    Area
        This field indicates the area whose link state information has
        led to the routing table entry's collection of paths.  This is
        called the entry's associated area.  For sets of AS external
        paths, this field is not defined.  For destinations of type
        "router", there may be separate sets of paths (and therefore
        separate routing table entries) associated with each of several
        areas. For example, this will happen when two area border
        routers share multiple areas in common.  For destinations of
        type "network", only the set of paths associated with the best
        area (the one providing the preferred route) is kept.


    The rest of the routing table entry describes the set of paths to
    the destination.  The following fields pertain to the set of paths
    as a whole.  In other words, each one of the paths contained in a
    routing table entry is of the same path-type and cost (see below).


    Path-type
        There are four possible types of paths used to route traffic to
        the destination, listed here in decreasing order of preference:
        intra-area, inter-area, type 1 external or type 2 external.
        Intra-area paths indicate destinations belonging to one of the
        router's attached areas.  Inter-area paths are paths to
        destinations in other OSPF areas.  These are discovered through
        the examination of received summary-LSAs.  AS external paths are
        paths to destinations external to the AS.  These are detected
        through the examination of received AS-external-LSAs.

    Cost
        The link state cost of the path to the destination.  For all
        paths except type 2 external paths this describes the entire
        path's cost.  For Type 2 external paths, this field describes
        the cost of the portion of the path internal to the AS.  This

Top      Up      ToC       Page 110 
        cost is calculated as the sum of the costs of the path's
        constituent links.

    Type 2 cost
        Only valid for type 2 external paths.  For these paths, this
        field indicates the cost of the path's external portion.  This
        cost has been advertised by an AS boundary router, and is the
        most significant part of the total path cost.  For example, a
        type 2 external path with type 2 cost of 5 is always preferred
        over a path with type 2 cost of 10, regardless of the cost of
        the two paths' internal components.

    Link State Origin
        Valid only for intra-area paths, this field indicates the LSA
        (router-LSA or network-LSA) that directly references the
        destination.  For example, if the destination is a transit
        network, this is the transit network's network-LSA.  If the
        destination is a stub network, this is the router-LSA for the
        attached router.  The LSA is discovered during the shortest-path
        tree calculation (see Section 16.1).  Multiple LSAs may
        reference the destination, however a tie-breaking scheme always
        reduces the choice to a single LSA. The Link State Origin field
        is not used by the OSPF protocol, but it is used by the routing
        table calculation in OSPF's Multicast routing extensions
        (MOSPF).

    When multiple paths of equal path-type and cost exist to a
    destination (called elsewhere "equal-cost" paths), they are stored
    in a single routing table entry.  Each one of the "equal-cost" paths
    is distinguished by the following fields:

    Next hop
        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.

    Advertising router
        Valid only for inter-area and AS external paths.  This field
        indicates the Router ID of the router advertising the summary-
        LSA or AS-external-LSA that led to this path.

Top      Up      ToC       Page 111 
    11.1.  Routing table lookup

        When an IP data packet is received, an OSPF router finds the
        routing table entry that best matches the packet's destination.
        This routing table entry then provides the outgoing interface
        and next hop router to use in forwarding the packet. This
        section describes the process of finding the best matching
        routing table entry.

        Before the lookup begins, "discard" routing table entries should
        be inserted into the routing table for each of the router's
        active area address ranges (see Section 3.5).  (An area range is
        considered "active" if the range contains one or more networks
        reachable by intra-area paths.) The destination of a "discard"
        entry is the set of addresses described by its associated active
        area address range, and the path type of each "discard" entry is
        set to "inter-area".[10]

        Several routing table entries may match the destination address.
        In this case, the "best match" is the routing table entry that
        provides the most specific (longest) match. Another way of
        saying this is to choose the entry that specifies the narrowest
        range of IP addresses.[11] For example, the entry for the
        address/mask pair of (128.185.1.0, 0xffffff00) is more specific
        than an entry for the pair (128.185.0.0, 0xffff0000). The
        default route is the least specific match, since it matches all
        destinations. (Note that for any single routing table entry,
        multiple paths may be possible. In these cases, the calculations
        in Sections 16.1, 16.2, and 16.4 always yield the paths having
        the most preferential path-type, as described in Section 11).

        If there is no matching routing table entry, or the best match
        routing table entry is one of the above "discard" routing table
        entries, then the packet's IP destination is considered
        unreachable. Instead of being forwarded, the packet should then
        be discarded and an ICMP destination unreachable message should
        be returned to the packet's source.

    11.2.  Sample routing table, without areas

        Consider the Autonomous System pictured in Figure 2.  No OSPF
        areas have been configured.  A single metric is shown per

Top      Up      ToC       Page 112 
        outbound interface.  The calculation of Router RT6's routing
        table proceeds as described in Section 2.2.  The resulting
        routing table is shown in Table 12.  Destination types are
        abbreviated: Network as "N", Router as "R".

        There are no instances of multiple equal-cost shortest paths in
        this example.  Also, since there are no areas, there are no
        inter-area paths.

        Routers RT5 and RT7 are AS boundary routers.  Intra-area routes
        have been calculated to Routers RT5 and RT7.  This allows
        external routes to be calculated to the destinations advertised
        by RT5 and RT7 (i.e., Networks N12, N13, N14 and N15).  It is
        assumed all AS-external-LSAs originated by RT5 and RT7 are
        advertising type 1 external metrics.  This results in type 1
        external paths being calculated to destinations N12-N15.



    11.3.  Sample routing table, with areas

        Consider the previous example, this time split into OSPF areas.
        An OSPF area configuration is pictured in Figure 6.  Router
        RT4's routing table will be described for this area
        configuration.  Router RT4 has a connection to Area 1 and a
        backbone connection.  This causes Router RT4 to view the AS as
        the concatenation of the two graphs shown in Figures 7 and 8.
        The resulting routing table is displayed in Table 13.

        Again, Routers RT5 and RT7 are AS boundary routers.  Routers
        RT3, RT4, RT7, RT10 and RT11 are area border routers.  Note that
        there are two routing entries for the area border router RT3,
        since it has two areas in common with RT4 (Area 1 and the
        backbone).

        Backbone paths have been calculated to all area border routers.
        These are used when determining the inter-area routes.  Note
        that all of the inter-area routes are associated with the
        backbone; this is always the case when the calculating router is
        itself an area border router.  Routing information is condensed
        at area boundaries.  In this example, we assume that Area 3 has
        been defined so that networks N9-N11 and the host route to H1

Top      Up      ToC       Page 113 
      Type   Dest   Area   Path  Type    Cost   Next     Adv.
                                                Hop(s)   Router(s)
      ____________________________________________________________
      N      N1     0      intra-area    10     RT3      *
      N      N2     0      intra-area    10     RT3      *
      N      N3     0      intra-area    7      RT3      *
      N      N4     0      intra-area    8      RT3      *
      N      Ib     0      intra-area    7      *        *
      N      Ia     0      intra-area    12     RT10     *
      N      N6     0      intra-area    8      RT10     *
      N      N7     0      intra-area    12     RT10     *
      N      N8     0      intra-area    10     RT10     *
      N      N9     0      intra-area    11     RT10     *
      N      N10    0      intra-area    13     RT10     *
      N      N11    0      intra-area    14     RT10     *
      N      H1     0      intra-area    21     RT10     *
      R      RT5    0      intra-area    6      RT5      *
      R      RT7    0      intra-area    8      RT10     *
      ____________________________________________________________
      N      N12    *      type 1 ext.   10     RT10     RT7
      N      N13    *      type 1 ext.   14     RT5      RT5
      N      N14    *      type 1 ext.   14     RT5      RT5
      N      N15    *      type 1 ext.   17     RT10     RT7


               Table 12: The routing table for Router RT6
                         (no configured areas).

        are all condensed to a single route when advertised into the
        backbone (by Router RT11).  Note that the cost of this route is
        the maximum of the set of costs to its individual components.

        There is a virtual link configured between Routers RT10 and
        RT11.  Without this configured virtual link, RT11 would be
        unable to advertise a route for networks N9-N11 and Host H1 into
        the backbone, and there would not be an entry for these networks
        in Router RT4's routing table.

        In this example there are two equal-cost paths to Network N12.
        However, they both use the same next hop (Router RT5).

Top      Up      ToC       Page 114 
        Router RT4's routing table would improve (i.e., some of the
        paths in the routing table would become shorter) if an
        additional virtual link were configured between Router RT4 and
        Router RT3.  The new virtual link would itself be associated
        with the first entry for area border router RT3 in Table 13 (an
        intra-area path through Area 1).  This would yield a cost of 1
        for the virtual link.  The routing table entries changes that
        would be caused by the addition of this virtual link are shown


   Type   Dest        Area   Path  Type    Cost   Next      Adv.
                                                  Hops(s)   Router(s)
   __________________________________________________________________
   N      N1          1      intra-area    4      RT1       *
   N      N2          1      intra-area    4      RT2       *
   N      N3          1      intra-area    1      *         *
   N      N4          1      intra-area    3      RT3       *
   R      RT3         1      intra-area    1      *         *
   __________________________________________________________________
   N      Ib          0      intra-area    22     RT5       *
   N      Ia          0      intra-area    27     RT5       *
   R      RT3         0      intra-area    21     RT5       *
   R      RT5         0      intra-area    8      *         *
   R      RT7         0      intra-area    14     RT5       *
   R      RT10        0      intra-area    22     RT5       *
   R      RT11        0      intra-area    25     RT5       *
   __________________________________________________________________
   N      N6          0      inter-area    15     RT5       RT7
   N      N7          0      inter-area    19     RT5       RT7
   N      N8          0      inter-area    18     RT5       RT7
   N      N9-N11,H1   0      inter-area    36     RT5       RT11
   __________________________________________________________________
   N      N12         *      type 1 ext.   16     RT5       RT5,RT7
   N      N13         *      type 1 ext.   16     RT5       RT5
   N      N14         *      type 1 ext.   16     RT5       RT5
   N      N15         *      type 1 ext.   23     RT5       RT7


                  Table 13: Router RT4's routing table
                       in the presence of areas.

Top      Up      ToC       Page 115 
        in Table 14.



12.  Link State Advertisements (LSAs)

    Each router in the Autonomous System originates one or more link
    state advertisements (LSAs).  This memo defines five distinct types
    of LSAs, which are described in Section 4.3.  The collection of LSAs
    forms the link-state database.  Each separate type of LSA has a
    separate function.  Router-LSAs and network-LSAs describe how an
    area's routers and networks are interconnected.  Summary-LSAs
    provide a way of condensing an area's routing information.  AS-
    external-LSAs provide a way of transparently advertising
    externally-derived routing information throughout the Autonomous
    System.

    Each LSA begins with a standard 20-byte header.  This LSA header is
    discussed below.







    Type   Dest        Area   Path  Type   Cost   Next     Adv.
                                                  Hop(s)   Router(s)
    ________________________________________________________________
    N      Ib          0      intra-area   16     RT3      *
    N      Ia          0      intra-area   21     RT3      *
    R      RT3         0      intra-area   1      *        *
    R      RT10        0      intra-area   16     RT3      *
    R      RT11        0      intra-area   19     RT3      *
    ________________________________________________________________
    N      N9-N11,H1   0      inter-area   30     RT3      RT11


                  Table 14: Changes resulting from an
                        additional virtual link.

Top      Up      ToC       Page 116 
    12.1.  The LSA Header

        The LSA header contains the LS type, Link State ID and
        Advertising Router fields.  The combination of these three
        fields uniquely identifies the LSA.

        There may be several instances of an LSA present in the
        Autonomous System, all at the same time.  It must then be
        determined which instance is more recent.  This determination is
        made by examining the LS sequence, LS checksum and LS age
        fields.  These fields are also contained in the 20-byte LSA
        header.

        Several of the OSPF packet types list LSAs.  When the instance
        is not important, an LSA is referred to by its LS type, Link
        State ID and Advertising Router (see Link State Request
        Packets).  Otherwise, the LS sequence number, LS age and LS
        checksum fields must also be referenced.

        A detailed explanation of the fields contained in the LSA header
        follows.


        12.1.1.  LS age

            This field is the age of the LSA in seconds.  It should be
            processed as an unsigned 16-bit integer.  It is set to 0
            when the LSA is originated.  It must be incremented by
            InfTransDelay on every hop of the flooding procedure.  LSAs
            are also aged as they are held in each router's database.

            The age of an LSA is never incremented past MaxAge.  LSAs
            having age MaxAge are not used in the routing table
            calculation.  When an LSA's age first reaches MaxAge, it is
            reflooded.  An LSA of age MaxAge is finally flushed from the
            database when it is no longer needed to ensure database
            synchronization.  For more information on the aging of LSAs,
            consult Section 14.

            The LS age field is examined when a router receives two
            instances of an LSA, both having identical LS sequence
            numbers and LS checksums.  An instance of age MaxAge is then

Top      Up      ToC       Page 117 
            always accepted as most recent; this allows old LSAs to be
            flushed quickly from the routing domain.  Otherwise, if the
            ages differ by more than MaxAgeDiff, the instance having the
            smaller age is accepted as most recent.[12] See Section 13.1
            for more details.


        12.1.2.  Options

            The Options field in the LSA header indicates which optional
            capabilities are associated with the LSA.  OSPF's optional
            capabilities are described in Section 4.5.  One optional
            capability is defined by this specification, represented by
            the E-bit found in the Options field.  The unrecognized bits
            in the Options field should be set to zero.

            The E-bit represents OSPF's ExternalRoutingCapability.  This
            bit should be set in all LSAs associated with the backbone,
            and all LSAs associated with non-stub areas (see Section
            3.6).  It should also be set in all AS-external-LSAs.  It
            should be reset in all router-LSAs, network-LSAs and
            summary-LSAs associated with a stub area.  For all LSAs, the
            setting of the E-bit is for informational purposes only; it
            does not affect the routing table calculation.


        12.1.3.  LS type

            The LS type field dictates the format and function of the
            LSA.  LSAs of different types have different names (e.g.,
            router-LSAs or network-LSAs).  All LSA types defined by this
            memo, except the AS-external-LSAs (LS type = 5), are flooded
            throughout a single area only.  AS-external-LSAs are flooded
            throughout the entire Autonomous System, excepting stub
            areas (see Section 3.6).  Each separate LSA type is briefly
            described below in Table 15.

        12.1.4.  Link State ID

            This field identifies the piece of the routing domain that
            is being described by the LSA.  Depending on the LSA's LS
            type, the Link State ID takes on the values listed in Table

Top      Up      ToC       Page 118 
            LS Type   LSA description
            ________________________________________________
            1         These are the router-LSAs.
                      They describe the collected
                       states of the router's
                      interfaces. For more information,
                      consult Section 12.4.1.
            ________________________________________________
            2         These are the network-LSAs.
                      They describe the set of routers
                      attached to the network. For
                      more information, consult
                      Section 12.4.2.
            ________________________________________________
            3 or 4    These are the summary-LSAs.
                      They describe inter-area routes,
                      and enable the condensation of
                      routing information at area
                      borders. Originated by area border
                      routers, the Type 3 summary-LSAs
                      describe routes to networks while the
                      Type 4 summary-LSAs describe routes to
                      AS boundary routers.
            ________________________________________________
            5         These are the AS-external-LSAs.
                      Originated by AS boundary routers,
                      they describe routes
                      to destinations external to the
                      Autonomous System. A default route for
                      the Autonomous System can also be
                      described by an AS-external-LSA.


            Table 15: OSPF link state advertisements (LSAs).

            16.


            Actually, for Type 3 summary-LSAs (LS type = 3) and AS-
            external-LSAs (LS type = 5), the Link State ID may

Top      Up      ToC       Page 119 
            LS Type   Link State ID
            _______________________________________________
            1         The originating router's Router ID.
            2         The IP interface address of the
                      network's Designated Router.
            3         The destination network's IP address.
            4         The Router ID of the described AS
                      boundary router.
            5         The destination network's IP address.


                   Table 16: The LSA's Link State ID.

            additionally have one or more of the destination network's
            "host" bits set. For example, when originating an AS-
            external-LSA for the network 10.0.0.0 with mask of
            255.0.0.0, the Link State ID can be set to anything in the
            range 10.0.0.0 through 10.255.255.255 inclusive (although
            10.0.0.0 should be used whenever possible). The freedom to
            set certain host bits allows a router to originate separate
            LSAs for two networks having the same address but different
            masks. See Appendix E for details.

            When the LSA is describing a network (LS type = 2, 3 or 5),
            the network's IP address is easily derived by masking the
            Link State ID with the network/subnet mask contained in the
            body of the LSA.  When the LSA is describing a router (LS
            type = 1 or 4), the Link State ID is always the described
            router's OSPF Router ID.

            When an AS-external-LSA (LS Type = 5) is describing a
            default route, its Link State ID is set to
            DefaultDestination (0.0.0.0).


        12.1.5.  Advertising Router

            This field specifies the OSPF Router ID of the LSA's
            originator.  For router-LSAs, this field is identical to the
            Link State ID field.  Network-LSAs are originated by the

Top      Up      ToC       Page 120 
            network's Designated Router.  Summary-LSAs originated by
            area border routers.  AS-external-LSAs are originated by AS
            boundary routers.


        12.1.6.  LS sequence number

            The sequence number field is a signed 32-bit integer.  It is
            used to detect old and duplicate LSAs.  The space of
            sequence numbers is linearly ordered.  The larger the
            sequence number (when compared as signed 32-bit integers)
            the more recent the LSA.  To describe to sequence number
            space more precisely, let N refer in the discussion below to
            the constant 2**31.

            The sequence number -N (0x80000000) is reserved (and
            unused).  This leaves -N + 1 (0x80000001) as the smallest
            (and therefore oldest) sequence number; this sequence number
            is referred to as the constant InitialSequenceNumber. A
            router uses InitialSequenceNumber the first time it
            originates any LSA.  Afterwards, the LSA's sequence number
            is incremented each time the router originates a new
            instance of the LSA.  When an attempt is made to increment
            the sequence number past the maximum value of N - 1
            (0x7fffffff; also referred to as MaxSequenceNumber), the
            current instance of the LSA must first be flushed from the
            routing domain.  This is done by prematurely aging the LSA
            (see Section 14.1) and reflooding it.  As soon as this flood
            has been acknowledged by all adjacent neighbors, a new
            instance can be originated with sequence number of
            InitialSequenceNumber.

            The router may be forced to promote the sequence number of
            one of its LSAs when a more recent instance of the LSA is
            unexpectedly received during the flooding process.  This
            should be a rare event.  This may indicate that an out-of-
            date LSA, originated by the router itself before its last
            restart/reload, still exists in the Autonomous System.  For
            more information see Section 13.4.

Top      Up      ToC       Page 121 
        12.1.7.  LS checksum

            This field is the checksum of the complete contents of the
            LSA, excepting the LS age field.  The LS age field is
            excepted so that an LSA's age can be incremented without
            updating the checksum.  The checksum used is the same that
            is used for ISO connectionless datagrams; it is commonly
            referred to as the Fletcher checksum.  It is documented in
            Annex B of [Ref6].  The LSA header also contains the length
            of the LSA in bytes; subtracting the size of the LS age
            field (two bytes) yields the amount of data to checksum.

            The checksum is used to detect data corruption of an LSA.
            This corruption can occur while an LSA is being flooded, or
            while it is being held in a router's memory.  The LS
            checksum field cannot take on the value of zero; the
            occurrence of such a value should be considered a checksum
            failure.  In other words, calculation of the checksum is not
            optional.

            The checksum of an LSA is verified in two cases:  a) when it
            is received in a Link State Update Packet and b) at times
            during the aging of the link state database.  The detection
            of a checksum failure leads to separate actions in each
            case.  See Sections 13 and 14 for more details.

            Whenever the LS sequence number field indicates that two
            instances of an LSA are the same, the LS checksum field is
            examined.  If there is a difference, the instance with the
            larger LS checksum is considered to be most recent.[13] See
            Section 13.1 for more details.


    12.2.  The link state database

        A router has a separate link state database for every area to
        which it belongs. All routers belonging to the same area have
        identical link state databases for the area.

        The databases for each individual area are always dealt with
        separately.  The shortest path calculation is performed
        separately for each area (see Section 16).  Components of the

Top      Up      ToC       Page 122 
        area link-state database are flooded throughout the area only.
        Finally, when an adjacency (belonging to Area A) is being
        brought up, only the database for Area A is synchronized between
        the two routers.

        The area database is composed of router-LSAs, network-LSAs and
        summary-LSAs (all listed in the area data structure).  In
        addition, external routes (AS-external-LSAs) are included in all
        non-stub area databases (see Section 3.6).

        An implementation of OSPF must be able to access individual
        pieces of an area database.  This lookup function is based on an
        LSA's LS type, Link State ID and Advertising Router.[14] There
        will be a single instance (the most up-to-date) of each LSA in
        the database.  The database lookup function is invoked during
        the LSA flooding procedure (Section 13) and the routing table
        calculation (Section 16).  In addition, using this lookup
        function the router can determine whether it has itself ever
        originated a particular LSA, and if so, with what LS sequence
        number.

        An LSA is added to a router's database when either a) it is
        received during the flooding process (Section 13) or b) it is
        originated by the router itself (Section 12.4).  An LSA is
        deleted from a router's database when either a) it has been
        overwritten by a newer instance during the flooding process
        (Section 13) or b) the router originates a newer instance of one
        of its self-originated LSAs (Section 12.4) or c) the LSA ages
        out and is flushed from the routing domain (Section 14).
        Whenever an LSA is deleted from the database it must also be
        removed from all neighbors' Link state retransmission lists (see
        Section 10).


    12.3.  Representation of TOS

        For backward compatibility with previous versions of the OSPF
        specification ([Ref9]), TOS-specific information can be included
        in router-LSAs, summary-LSAs and AS-external-LSAs.  The encoding
        of TOS in OSPF LSAs is specified in Table 17. That table relates
        the OSPF encoding to the IP packet header's TOS field (defined
        in [Ref12]).  The OSPF encoding is expressed as a decimal

Top      Up      ToC       Page 123 
        integer, and the IP packet header's TOS field is expressed in
        the binary TOS values used in [Ref12].



                    OSPF encoding   RFC 1349 TOS values
                    ___________________________________________
                    0               0000 normal service
                    2               0001 minimize monetary cost
                    4               0010 maximize reliability
                    6               0011
                    8               0100 maximize throughput
                    10              0101
                    12              0110
                    14              0111
                    16              1000 minimize delay
                    18              1001
                    20              1010
                    22              1011
                    24              1100
                    26              1101
                    28              1110
                    30              1111


                        Table 17: Representing TOS in OSPF.


    12.4.  Originating LSAs

        Into any given OSPF area, a router will originate several LSAs.
        Each router originates a router-LSA.  If the router is also the
        Designated Router for any of the area's networks, it will
        originate network-LSAs for those networks.

        Area border routers originate a single summary-LSA for each
        known inter-area destination.  AS boundary routers originate a
        single AS-external-LSA for each known AS external destination.
        Destinations are advertised one at a time so that the change in
        any single route can be flooded without reflooding the entire
        collection of routes.  During the flooding procedure, many LSAs
        can be carried by a single Link State Update packet.

Top      Up      ToC       Page 124 
        As an example, consider Router RT4 in Figure 6.  It is an area
        border router, having a connection to Area 1 and the backbone.
        Router RT4 originates 5 distinct LSAs into the backbone (one
        router-LSA, and one summary-LSA for each of the networks N1-N4).
        Router RT4 will also originate 8 distinct LSAs into Area 1 (one
        router-LSA and seven summary-LSAs as pictured in Figure 7).  If
        RT4 has been selected as Designated Router for Network N3, it
        will also originate a network-LSA for N3 into Area 1.

        In this same figure, Router RT5 will be originating 3 distinct
        AS-external-LSAs (one for each of the networks N12-N14).  These
        will be flooded throughout the entire AS, assuming that none of
        the areas have been configured as stubs.  However, if area 3 has
        been configured as a stub area, the AS-external-LSAs for
        networks N12-N14 will not be flooded into area 3 (see Section
        3.6).  Instead, Router RT11 would originate a default summary-
        LSA that would be flooded throughout area 3 (see Section
        12.4.3).  This instructs all of area 3's internal routers to
        send their AS external traffic to RT11.

        Whenever a new instance of an LSA is originated, its LS sequence
        number is incremented, its LS age is set to 0, its LS checksum
        is calculated, and the LSA is added to the link state database
        and flooded out the appropriate interfaces.  See Section 13.2
        for details concerning the installation of the LSA into the link
        state database.  See Section 13.3 for details concerning the
        flooding of newly originated LSAs.


        The ten events that can cause a new instance of an LSA to be
        originated are:


        (1) The LS age field of one of the router's self-originated LSAs
            reaches the value LSRefreshTime. In this case, a new
            instance of the LSA is originated, even though the contents
            of the LSA (apart from the LSA header) will be the same.
            This guarantees periodic originations of all LSAs.  This
            periodic updating of LSAs adds robustness to the link state
            algorithm.  LSAs that solely describe unreachable
            destinations should not be refreshed, but should instead be
            flushed from the routing domain (see Section 14.1).

Top      Up      ToC       Page 125 
        When whatever is being described by an LSA changes, a new LSA is
        originated.  However, two instances of the same LSA may not be
        originated within the time period MinLSInterval.  This may
        require that the generation of the next instance be delayed by
        up to MinLSInterval.  The following events may cause the
        contents of an LSA to change.  These events should cause new
        originations if and only if the contents of the new LSA would be
        different:


        (2) An interface's state changes (see Section 9.1).  This may
            mean that it is necessary to produce a new instance of the
            router-LSA.

        (3) An attached network's Designated Router changes.  A new
            router-LSA should be originated.  Also, if the router itself
            is now the Designated Router, a new network-LSA should be
            produced.  If the router itself is no longer the Designated
            Router, any network-LSA that it might have originated for
            the network should be flushed from the routing domain (see
            Section 14.1).

        (4) One of the neighboring routers changes to/from the FULL
            state.  This may mean that it is necessary to produce a new
            instance of the router-LSA.  Also, if the router is itself
            the Designated Router for the attached network, a new
            network-LSA should be produced.


        The next four events concern area border routers only:


        (5) An intra-area route has been added/deleted/modified in the
            routing table.  This may cause a new instance of a summary-
            LSA (for this route) to be originated in each attached area
            (possibly including the backbone).

        (6) An inter-area route has been added/deleted/modified in the
            routing table.  This may cause a new instance of a summary-
            LSA (for this route) to be originated in each attached area
            (but NEVER for the backbone).

Top      Up      ToC       Page 126 
        (7) The router becomes newly attached to an area.  The router
            must then originate summary-LSAs into the newly attached
            area for all pertinent intra-area and inter-area routes in
            the router's routing table.  See Section 12.4.3 for more
            details.

        (8) When the state of one of the router's configured virtual
            links changes, it may be necessary to originate a new
            router-LSA into the virtual link's Transit area (see the
            discussion of the router-LSA's bit V in Section 12.4.1), as
            well as originating a new router-LSA into the backbone.


        The last two events concern AS boundary routers (and former AS
        boundary routers) only:


        (9) An external route gained through direct experience with an
            external routing protocol (like BGP) changes.  This will
            cause an AS boundary router to originate a new instance of
            an AS-external-LSA.

        (10)
            A router ceases to be an AS boundary router, perhaps after
            restarting. In this situation the router should flush all
            AS-external-LSAs that it had previously originated.  These
            LSAs can be flushed via the premature aging procedure
            specified in Section 14.1.


        The construction of each type of LSA is explained in detail
        below.  In general, these sections describe the contents of the
        LSA body (i.e., the part coming after the 20-byte LSA header).
        For information concerning the building of the LSA header, see
        Section 12.1.

        12.4.1.  Router-LSAs

            A router originates a router-LSA for each area that it
            belongs to.  Such an LSA describes the collected states of
            the router's links to the area.  The LSA is flooded
            throughout the particular area, and no further.

Top      Up      ToC       Page 127 
                  ....................................
                  . 192.1.2                   Area 1 .
                  .     +                            .
                  .     |                            .
                  .     | 3+---+1                    .
                  .  N1 |--|RT1|-----+               .
                  .     |  +---+      \              .
                  .     |              \  _______N3  .
                  .     +               \/       \   .  1+---+
                  .                     * 192.1.1 *------|RT4|
                  .     +               /\_______/   .   +---+
                  .     |              /     |       .
                  .     | 3+---+1     /      |       .
                  .  N2 |--|RT2|-----+      1|       .
                  .     |  +---+           +---+8    .         6+---+
                  .     |                  |RT3|----------------|RT6|
                  .     +                  +---+     .          +---+
                  . 192.1.3                  |2      .   18.10.0.6|7
                  .                          |       .            |
                  .                   +------------+ .
                  .                     192.1.4 (N4) .
                  ....................................


                    Figure 15: Area 1 with IP addresses shown

            The format of a router-LSA is shown in Appendix A (Section
            A.4.2).  The first 20 bytes of the LSA consist of the
            generic LSA header that was discussed in Section 12.1.
            router-LSAs have LS type = 1.

            A router also indicates whether it is an area border router,
            or an AS boundary router, by setting the appropriate bits
            (bit B and bit E, respectively) in its router-LSAs. This
            enables paths to those types of routers to be saved in the
            routing table, for later processing of summary-LSAs and AS-
            external-LSAs.  Bit B should be set whenever the router is
            actively attached to two or more areas, even if the router
            is not currently attached to the OSPF backbone area.  Bit E
            should never be set in a router-LSA for a stub area (stub
            areas cannot contain AS boundary routers).

Top      Up      ToC       Page 128 
            In addition, the router sets bit V in its router-LSA for
            Area A if and only if the router is the endpoint of one or
            more fully adjacent virtual links having Area A as their
            Transit area. The setting of bit V enables other routers in
            Area A to discover whether the area supports transit traffic
            (see TransitCapability in Section 6).

            The router-LSA then describes the router's working
            connections (i.e., interfaces or links) to the area.  Each
            link is typed according to the kind of attached network.
            Each link is also labelled with its Link ID.  This Link ID
            gives a name to the entity that is on the other end of the
            link.  Table 18 summarizes the values used for the Type and
            Link ID fields.



                   Link type   Description       Link ID
                   __________________________________________________
                   1           Point-to-point    Neighbor Router ID
                               link
                   2           Link to transit   Interface address of
                               network           Designated Router
                   3           Link to stub      IP network number
                               network
                   4           Virtual link      Neighbor Router ID


                           Table 18: Link descriptions in the
                                      router-LSA.


            In addition, the Link Data field is specified for each link.
            This field gives 32 bits of extra information for the link.
            For links to transit networks, numbered point-to-point links
            and virtual links, this field specifies the IP interface
            address of the associated router interface (this is needed
            by the routing table calculation, see Section 16.1.1).  For
            links to stub networks, this field specifies the stub
            network's IP address mask.  For unnumbered point-to-point
            links, the Link Data field should be set to the unnumbered
            interface's MIB-II [Ref8] ifIndex value.

Top      Up      ToC       Page 129 
            Finally, the cost of using the link for output is specified.
            The output cost of a link is configurable.  With the
            exception of links to stub networks, the output cost must
            always be non-zero.

            To further describe the process of building the list of link
            descriptions, suppose a router wishes to build a router-LSA
            for Area A.  The router examines its collection of interface
            data structures.  For each interface, the following steps
            are taken:


            o   If the attached network does not belong to Area A, no
                links are added to the LSA, and the next interface
                should be examined.

            o   If the state of the interface is Down, no links are
                added.

            o   If the state of the interface is Loopback, add a Type 3
                link (stub network) as long as this is not an interface
                to an unnumbered point-to-point network.  The Link ID
                should be set to the IP interface address, the Link Data
                set to the mask 0xffffffff (indicating a host route),
                and the cost set to 0.

            o   Otherwise, the link descriptions added to the router-LSA
                depend on the OSPF interface type. Link descriptions
                used for point-to-point interfaces are specified in
                Section 12.4.1.1, for virtual links in Section 12.4.1.2,
                for broadcast and NBMA interfaces in 12.4.1.3, and for
                Point-to-MultiPoint interfaces in 12.4.1.4.

            After consideration of all the router interfaces, host links
            are added to the router-LSA by examining the list of
            attached hosts belonging to Area A.  A host route is
            represented as a Type 3 link (stub network) whose Link ID is
            the host's IP address, Link Data is the mask of all ones
            (0xffffffff), and cost the host's configured cost (see
            Section C.7).

Top      Up      ToC       Page 130 
            12.4.1.1.  Describing point-to-point interfaces

                For point-to-point interfaces, one or more link
                descriptions are added to the router-LSA as follows:

                o   If the neighboring router is fully adjacent, add a
                    Type 1 link (point-to-point). The Link ID should be
                    set to the Router ID of the neighboring router. For
                    numbered point-to-point networks, the Link Data
                    should specify the IP interface address. For
                    unnumbered point-to-point networks, the Link Data
                    field should specify the interface's MIB-II [Ref8]
                    ifIndex value. The cost should be set to the output
                    cost of the point-to-point interface.

                o   In addition, as long as the state of the interface
                    is "Point-to-Point" (and regardless of the
                    neighboring router state), a Type 3 link (stub
                    network) should be added. There are two forms that
                    this stub link can take:

                    Option 1
                        Assuming that the neighboring router's IP
                        address is known, set the Link ID of the Type 3
                        link to the neighbor's IP address, the Link Data
                        to the mask 0xffffffff (indicating a host
                        route), and the cost to the interface's
                        configured output cost.[15]

                    Option 2
                        If a subnet has been assigned to the point-to-
                        point link, set the Link ID of the Type 3 link
                        to the subnet's IP address, the Link Data to the
                        subnet's mask, and the cost to the interface's
                        configured output cost.[16]


            12.4.1.2.  Describing broadcast and NBMA interfaces

                For operational broadcast and NBMA interfaces, a single
                link description is added to the router-LSA as follows:

Top      Up      ToC       Page 131 
                o   If the state of the interface is Waiting, add a Type
                    3 link (stub network) with Link ID set to the IP
                    network number of the attached network, Link Data
                    set to the attached network's address mask, and cost
                    equal to the interface's configured output cost.

                o   Else, there has been a Designated Router elected for
                    the attached network.  If the router is fully
                    adjacent to the Designated Router, or if the router
                    itself is Designated Router and is fully adjacent to
                    at least one other router, add a single Type 2 link
                    (transit network) with Link ID set to the IP
                    interface address of the attached network's
                    Designated Router (which may be the router itself),
                    Link Data set to the router's own IP interface
                    address, and cost equal to the interface's
                    configured output cost.  Otherwise, add a link as if
                    the interface state were Waiting (see above).


            12.4.1.3.  Describing virtual links

                For virtual links, a link description is added to the
                router-LSA only when the virtual neighbor is fully
                adjacent. In this case, add a Type 4 link (virtual link)
                with Link ID set to the Router ID of the virtual
                neighbor, Link Data set to the IP interface address
                associated with the virtual link and cost set to the
                cost calculated for the virtual link during the routing
                table calculation (see Section 15).


            12.4.1.4.  Describing Point-to-MultiPoint interfaces

                For operational Point-to-MultiPoint interfaces, one or
                more link descriptions are added to the router-LSA as
                follows:

                o   A single Type 3 link (stub network) is added with
                    Link ID set to the router's own IP interface
                    address, Link Data set to the mask 0xffffffff
                    (indicating a host route), and cost set to 0.

Top      Up      ToC       Page 132 
                o   For each fully adjacent neighbor associated with the
                    interface, add an additional Type 1 link (point-to-
                    point) with Link ID set to the Router ID of the
                    neighboring router, Link Data set to the IP
                    interface address and cost equal to the interface's
                    configured output cost.


            12.4.1.5.  Examples of router-LSAs

                Consider the router-LSAs generated by Router RT3, as
                pictured in Figure 6.  The area containing Router RT3
                (Area 1) has been redrawn, with actual network
                addresses, in Figure 15.  Assume that the last byte of
                all of RT3's interface addresses is 3, giving it the
                interface addresses 192.1.1.3 and 192.1.4.3, and that
                the other routers have similar addressing schemes.  In
                addition, assume that all links are functional, and that
                Router IDs are assigned as the smallest IP interface
                address.

                RT3 originates two router-LSAs, one for Area 1 and one
                for the backbone.  Assume that Router RT4 has been
                selected as the Designated router for network 192.1.1.0.
                RT3's router-LSA for Area 1 is then shown below.  It
                indicates that RT3 has two connections to Area 1, the
                first a link to the transit network 192.1.1.0 and the
                second a link to the stub network 192.1.4.0.  Note that
                the transit network is identified by the IP interface of
                its Designated Router (i.e., the Link ID = 192.1.1.4
                which is the Designated Router RT4's IP interface to
                192.1.1.0).  Note also that RT3 has indicated that it is
                an area border router.

        ; RT3's router-LSA for Area 1

        LS age = 0                     ;always true on origination
        Options = (E-bit)              ;
        LS type = 1                    ;indicates router-LSA
        Link State ID = 192.1.1.3      ;RT3's Router ID
        Advertising Router = 192.1.1.3 ;RT3's Router ID
        bit E = 0                      ;not an AS boundary router

Top      Up      ToC       Page 133 
        bit B = 1                      ;area border router
        #links = 2
               Link ID = 192.1.1.4     ;IP address of Desig. Rtr.
               Link Data = 192.1.1.3   ;RT3's IP interface to net
               Type = 2                ;connects to transit network
               # TOS metrics = 0
               metric = 1

               Link ID = 192.1.4.0     ;IP Network number
               Link Data = 0xffffff00  ;Network mask
               Type = 3                ;connects to stub network
               # TOS metrics = 0
               metric = 2

                    Next RT3's router-LSA for the backbone is shown.  It
                    indicates that RT3 has a single attachment to the
                    backbone.  This attachment is via an unnumbered
                    point-to-point link to Router RT6.  RT3 has again
                    indicated that it is an area border router.

        ; RT3's router-LSA for the backbone

        LS age = 0                     ;always true on origination
        Options = (E-bit)              ;
        LS type = 1                    ;indicates router-LSA
        Link State ID = 192.1.1.3      ;RT3's router ID
        Advertising Router = 192.1.1.3 ;RT3's router ID
        bit E = 0                      ;not an AS boundary router
        bit B = 1                      ;area border router
        #links = 1
               Link ID = 18.10.0.6     ;Neighbor's Router ID
               Link Data = 0.0.0.3     ;MIB-II ifIndex of P-P link
               Type = 1                ;connects to router
               # TOS metrics = 0
               metric = 8

        12.4.2.  Network-LSAs

            A network-LSA is generated for every transit broadcast or
            NBMA network.  (A transit network is a network having two or
            more attached routers).  The network-LSA describes all the
            routers that are attached to the network.

Top      Up      ToC       Page 134 
            The Designated Router for the network originates the LSA.
            The Designated Router originates the LSA only if it is fully
            adjacent to at least one other router on the network.  The
            network-LSA is flooded throughout the area that contains the
            transit network, and no further.  The network-LSA lists
            those routers that are fully adjacent to the Designated
            Router; each fully adjacent router is identified by its OSPF
            Router ID.  The Designated Router includes itself in this
            list.

            The Link State ID for a network-LSA is the IP interface
            address of the Designated Router.  This value, masked by the
            network's address mask (which is also contained in the
            network-LSA) yields the network's IP address.

            A router that has formerly been the Designated Router for a
            network, but is no longer, should flush the network-LSA that
            it had previously originated.  This LSA is no longer used in
            the routing table calculation.  It is flushed by prematurely
            incrementing the LSA's age to MaxAge and reflooding (see
            Section 14.1). In addition, in those rare cases where a
            router's Router ID has changed, any network-LSAs that were
            originated with the router's previous Router ID must be
            flushed. Since the router may have no idea what it's
            previous Router ID might have been, these network-LSAs are
            indicated by having their Link State ID equal to one of the
            router's IP interface addresses and their Advertising Router
            equal to some value other than the router's current Router
            ID (see Section 13.4 for more details).


            12.4.2.1.  Examples of network-LSAs

                Again consider the area configuration in Figure 6.
                Network-LSAs are originated for Network N3 in Area 1,
                Networks N6 and N8 in Area 2, and Network N9 in Area 3.
                Assuming that Router RT4 has been selected as the
                Designated Router for Network N3, the following
                network-LSA is generated by RT4 on behalf of Network N3
                (see Figure 15 for the address assignments):

        ; Network-LSA for Network N3

Top      Up      ToC       Page 135 
        LS age = 0                     ;always true on origination
        Options = (E-bit)              ;
        LS type = 2                    ;indicates network-LSA
        Link State ID = 192.1.1.4      ;IP address of Desig. Rtr.
        Advertising Router = 192.1.1.4 ;RT4's Router ID
        Network Mask = 0xffffff00
               Attached Router = 192.1.1.4    ;Router ID
               Attached Router = 192.1.1.1    ;Router ID
               Attached Router = 192.1.1.2    ;Router ID
               Attached Router = 192.1.1.3    ;Router ID



(page 135 continued on part 6)

Next RFC Part