Network Working Group                                         J. Moy
    Internet Draft                                         Proteon, Inc.
                                                              April 1992


                     Proposed modifications to RFC 1247



    Status of this Memo

    This memo documents proposed modifications to the OSPF protocol. It
    is the intent that these modifications be folded into the OSPF
    specification, resulting in an update to RFC 1247. OSPF is a
    standards track protocol, and is presently at Draft Standard status.
    The modifications proposed herein are backward-compatible, and will
    not outdate any current OSPF implementations.

    Abstract

    The proposed modification to OSPF fall into three general
    categories, as listed below:

    o   Bugfixes. There is a problem with certain anomalous virtual
        links configurations wherein permanent routing loops can form.
        This memo describes a modification to the OSPF routing table
        calculation that fixes the problem. Only area border routers
        attaching to non-backbone transit areas (which by definition
        contain virtual links) are affected.

    o   Responses to changes in the IP architecture. Since the IP TOS
        field is being redefined to be one bit larger (the extra bit
        being assigned to monetary cost), the list of TOS encodings in
        Section 12.3 of RFC 1247 must be enhanced. The encoding for the
        previously defined TOS types will not change.

    o   Incremental optimizations. Several small changes fall into this
        category. One example is for the OSPF specification to mention
        that, other than default, it is not necessary to summarize
        information into OSPF stub areas (although this may be at the
        expense of optimal inter-area routing).










    [Moy]                                                       [Page 1]

    Internet Draft           OSPF modifications               April 1992


    1.  A problem with virtual links

    OSPF allows an Autonomous System to be organized into separate
    pieces, called Areas. This might be done for several reasons: it can
    lessen the amount of resources consumed by the routing protocol
    itself (both in terms of network bandwidth, router CPU and memory),
    and it provides an additional level of routing protection. When
    splitting an AS into areas, there is always a special area called
    the backbone (which uses Area ID 0.0.0.0). It is the responsibility
    of the backbone area to distribute routing information to and from
    the other areas. When OSPF routing information, and in fact IP data
    traffic, flows from one non-backbone area to another, it must
    transit the backbone. In this way, the area configuration looks like
    a hub and spoke topology, with the backbone area being the hub.

    In order to support this functionality, the backbone must remain
    connected. However, so that arbitrary area configurations can be
    supported, OSPF introduces the idea of virtual links. By configuring
    virtual links through non-backbone areas, the backbone is extended
    and connectivity is maintained. The areas containing these virtual
    links are called "transit areas". They are the only areas in an
    OSPF, besides the backbone, that can forward data traffic which
    neither originates nor terminates in the area itself.

    Transit areas pose a special problem when forwarding data traffic.
    This is because as transit data traffic goes from a border router
    into the interior of the transit area, it goes from a router having
    global knowledge to one having only local knowledge (and one that
    has no knowledge of the virtual link's existence). In other words,
    there is an information disparity between the border routers and the
    transit area's interior. Realizing this, RFC 1247 attempted to deal
    with this by recalculating the first hop of a packet as it enters
    the transit area (see Section 16.3, "Resolving virtual next hops",
    of [1]).  However, this ends up being inadequate for certain virtual
    link configurations, one of which is shown in Figure 1.

    Figure 1 shows the last configuration tested in the Interop pre-
    staging held in October 1992 in Boxborough, MA. The backbone area
    was configured as three physically separate pieces: networks
    128.8.0.0, 12.0.0.0 and the serial line joining routers RT4 and RT5.
    The middle network, 6.0.0.0, was configured as Area 1. In order to
    reconnect the backbone, two virtual links were configured, one
    between Routers RT2 and RT6 and the other between routers RT6 and
    RT4, making Area 1 into a transit area.

    The problem then occurred when attempting to forward packets to
    router RT5. In the backbone Dijkstra, RT2 calculated the next hop as
    being Router RT6, and then uses the calculation in Section 16.3 of



    [Moy]                                                       [Page 2]

    Internet Draft           OSPF modifications               April 1992



                               +-----+
                               | RT1 |
                               +-----+
                                  |           128.8.0.0
          --------------------------------------------------
               |               |
            +-----+         +-----+            |18.0.0.0
            | RT2 |         | RT3 |------------|      +-----+
            +-----+         +-----+            |------| RT4 |
               |     6.0.0.0   |               |      +-----+
          ---------------------------                    |
               |               |                         |
            +-----+         +-----+                   +-----+
            | RT6 |         | RT7 |                   | RT5 |
            +-----+         +-----+                   +-----+
               |     12.0.0.0
          ---------------------------
               |               |
            +-----+         +-----+
            | RT8 |         | RT9 |
            +-----+         +-----+

                     Figure 1: A problem configuration

    [1] to adjust the next hop to the better choice RT3. Unfortunately,
    RT3's backbone Dijkstra calculated the next hop (correctly) as RT2
    (!), and did not invoke the Section 16.3 calculation since it is not
    a virtual link endpoint. This led to a tight routing loop between
    RT2 and RT3.

    It is interesting to note that the problem could have been avoided
    by the configuration of an additional virtual link between RT3 and
    RT4.  But in general what is needed is an additional routing table
    calculation in all of the transit area's border routers. This
    calculation, which will replace Section 16.3 of [1], is presented
    below.

    1.1.  A fix for the virtual link problem

    The general idea of the fix is as follows. First, an area's border
    routers dynamically determine whether the area is contains any
    active virtual links (i.e., whether it is a transit area). Then,
    after calculating the intra-area and inter-area paths in Sections
    16.1 and 16.2 of [1], each border router examines the summary-LSAs
    associated with its connected transit areas to see whether more
    optimal paths using the transit area exist. If so, they override the
    previously discovered routes.



    [Moy]                                                       [Page 3]

    Internet Draft           OSPF modifications               April 1992


    Relating this to figure 1, what would happen when calculating routes
    to RT5 is as follows. All of Area 1's border routers (RT2, RT3, RT4
    and RT6) would dynamically discover that Area 1 is a transit area.
    Using the calculations in Sections 16.1 and 16.2 of [1], RT2
    calculates the next hop to RT5 as RT6, and RT3 calculates it as RT2
    (as before). Then, performing the new (additional) calculation which
    replaces 16.3 of [1], the summary-LSA originated into Area 1 by RT4
    causes the next hops to be overridden by the next hops of RT3 and
    RT4, respectively.

    In more detail, this new mechanism consists of the following
    components:

    o   There will be a new bit in the "router type" field of the
        router-LSA.  This bit (call it the "V" bit) will be set in a
        router X's router-LSA for Area A if and only if router X is the
        endpoint of an active (i.e., configured and up) virtual link
        through Area A. Note that the other bits in the router type
        field indicate whether the router is an area border, AS boundary
        router and/or wild-card multicast receiver (see Section A.2 of
        [1] and Section A.1 of [4]).

    o   Whether Area A is a transit area will be discovered dynamically
        in Area A's Dijkstra calculation (Section 16.1). Area A is a
        transit if and only if one or more router-LSAs having the "V"
        bit set are discovered in Step 2 on page 82 of [1], or if the
        calculating router itself is the endpoint of an active virtual
        link through Area A. Only area border routers need perform this
        calculation, since they are the only ones that perform the
        succeeding calculations.

    o   The calculation in Section 16.3 is replaced by the calculation
        detailed below in "Replacement for Resolving virtual next hops".
        The new calculation, performed only in area border routers,
        examines all connected transit areas, installing any paths that
        are better than those discovered in Sections 16.1 and 16.2 of
        [1].

    o   The calculation in Section 16.5 of [1], "Incremental updates --
        summary links" will be updated as follows. There are two cases:

       -    If the summary-LSA is associated with the backbone, or if
            the router is attached to a single area, the calculation in
            16.2 of [1] is run again for a single routing table entry
            (as before). Then, if the router is attached to one or more
            transit areas, the calculation in Section 16.3's replacement
            must be run again for the single destination.  Finally, if
            the results of these calculations have changed the cost to



    [Moy]                                                       [Page 4]

    Internet Draft           OSPF modifications               April 1992


            an AS boundary router (as would be the case for a type 4
            summary-LSA) or to any forwarding addresses, the AS external
            links will have to be examined by rerunning the calculation
            in Section 16.5.

       -    Otherwise, if the summary-LSA is associated with a transit
            area, the following calculations must be performed. If the
            new summary-LSA specifies a lower cost than the previous
            instance (or if there was no previous instance of the
            summary-LSA) the calculation in the replacement for Section
            16.3 should be rerun for a single routing table entry,
            removing those next hops belonging to the transit area
            before the recalculation commences. As before, if the
            results of this calculation changes the cost to an AS
            boundary router or to any forwarding addresses, the AS
            external links will have to be examined by rerunning the
            calculation in Section 16.5. On the other hand, if the new
            summary-LSA specifies a larger cost than the previous
            instance, the complete routing table calculation must be
            rerun starting with the Dijkstra algorithm specified in
            Section 16.1.

    1.2.  Replacement for Resolving virtual next hops

    The following calculation will be substituted for section 16.3 of
    [1].  The calculation is extremely similar to the calculation in
    Section 16.2 of [1], and is performed in area border routers only:

    Examine in turn all the summary-LSAs associated with transit areas.
    Each such summary-LSA advertises a route to Network N (or in the
    case of a type 4 summary-LSA, router N). It is associated with
    transit area A, and was originated by an area border router BR.

    (1) If the cost advertised by the summary-LSA is LSInfinity, examine
        the next LSA.

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

    (3) Look up the routing table entry for N. If it does not exist, or
        if the route type is other than intra-area or inter-area, or if
        the area associated with the routing table entry is not the
        backbone area, then examine the next LSA. In other words, this
        calculation only updates backbone Dijkstra routes found in
        Section 16.1 of [1] and inter-area routes found in Section 16.2
        of [1].





    [Moy]                                                       [Page 5]

    Internet Draft           OSPF modifications               April 1992


    (4) Look up the routing table entry for the advertising router BR
        associated with the Area A. If it is unreachable, examine the
        next LSA. Otherwise, the cost to destination N is the sum of the
        cost in BR's routing table entry and the cost advertised in the
        LSA. Call this cost IAC.

    (5) If this cost is less than the cost occurring in N's routing
        table entry, overwrite N's list of next hops with those used for
        BR, and set N's routing table cost to IAC. Else, if IAC is the
        same as N's current cost, add BR's list of next hops to N's list
        of next hops. In any case, the area associated with N's routing
        table entry must remain the backbone area. And the path type
        (either intra-area or inter-area), must also remain the same.

    1.3.  Notes on the new Section 16.3

    It is important to note that the new calculation never makes
    unreachable destinations reachable, but instead just potentially
    finds better paths to already reachable destinations. Also, unlike
    the old 16.3, the new calculation installs any better cost found
    into the routing table entry, from which it may be readvertised in
    summary-LSAs to other areas.

    1.4.  Obsoleting LSInfinity in router-LSAs

    As a related change, the metric of LSInfinity can no longer be used
    in router-LSAs to indicate unusable links. This is being done for
    several reasons:

    o   It removes any possible confusion in an OSPF area as to just
        which routers/networks are reachable in the area. For example,
        the above virtual link fix automatically detects the existence
        of virtual links when running the Dijkstra. However, when one-
        directional links are possible, some routers may detect the
        existence of virtual links while others may not. This may defeat
        the proposed fix for the virtual link problem.  For example,
        consider a modification to Figure 1 where RT3 is advertising its
        cost to Network 6 as LSInfinity, and where there is no virtual
        link between RT6 and RT4 but instead a connection through the
        physical backbone. In this case, RT3 would not know about the
        virtual link through Area 1, and a routing loop would again
        result.

    o   It also helps the IP multicast extensions, because one-way
        reachability can lead to places that are reachable via unicast
        but not multicast, or vice versa.





    [Moy]                                                       [Page 6]

    Internet Draft           OSPF modifications               April 1992


    It is believed that no current OSPF implementations are using
    LSInfinity in router-LSAs; its two prior justifications (a way to
    not support TOS before TOS was optional, and for strong TOS
    interpretations) are no longer valid.  LSInfinity will continue to
    mean "unreachable" in summary-LSAs and AS-external-LSAs, as some
    implementations use this as an alternative to the premature aging
    procedure specified in Section 14.1 of [1].

    2.  Other changes

    2.1.  TOS encoding

    Now that an additional IP TOS bit (monetary cost) has been defined
    (see [3]), additional TOS encodings will now be defined in Section
    12.3 of [1].  Note that the encodings of the already existing TOS
    types will not change. The OSPF MIB ([2]) must also be modified in
    the same fashion.

    2.2.  Summarizing routes into transit areas

    Originating summary-LSAs (Section 12.4.3 of [1]). The OSPF
    specification mandates that routes associated with Area A are never
    summarized back into Area A. However, you can further reduce the
    number of summary-LSAs by refusing to summarize into Area A those
    routes having next hops in Area A (this only happens in the presence
    of virtual links). For example, in Figure 1 Router RT6 does not have
    to summarize a route for 128.8.0.0 into Area 1 (if it does, it will
    never be used). This is the logical equivalent of a Distance Vector
    protocol's split horizon logic.

    2.3.  Summarizing routes into stub areas

    While area border routers connected to OSPF stub areas must import
    default summary-LSAs into the stub area, they need not summarize
    other routes into the stub area. The amount of summarization done
    into stub areas can be put under configuration control. The user can
    then make a trade-off between optimal routing and database size.
    This is also a change to Section 12.4.3 of [1].

    3.  References

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

    [2]  Baker, F. and Coltun, R., "OSPF Version 2 Management
         Information Base", RFC 1253, August 1991.

    [3]  Almquist, Philip, "Type of Service in the Internet Protocol
         Suite", Internet Draft, January 1992.



    [Moy]                                                       [Page 7]

    Internet Draft           OSPF modifications               April 1992


    [4]  Moy, J., "Multicast extensions to OSPF", Internet Draft,
         November 1991.

















































    [Moy]                                                       [Page 8]