Tech-invite3GPPspaceIETFspace
959493929190898887868584838281807978777675747372717069686766656463626160595857565554535251504948474645444342414039383736353433323130292827262524232221201918171615141312111009080706050403020100
in Index   Prev   Next

RFC 2328

OSPF Version 2

Pages: 244
Internet Standard: 54
Errata
Obsoletes:  2178
Updated by:  57096549684568607474804293559454
Part 2 of 8 – Pages 26 to 52
First   Prev   Next

Top   ToC   RFC2328 - Page 26   prevText
3.  Splitting the AS into Areas

    OSPF allows collections of contiguous networks and hosts to be
    grouped together.  Such a group, together with the routers having
    interfaces to any one of the included networks, is called an area.
    Each area runs a separate copy of the basic link-state routing
    algorithm.  This means that each area has its own link-state
    database and corresponding graph, as explained in the previous
    section.

    The topology of an area is invisible from the outside of the area.
    Conversely, routers internal to a given area know nothing of the
    detailed topology external to the area.  This isolation of knowledge
    enables the protocol to effect a marked reduction in routing traffic
    as compared to treating the entire Autonomous System as a single
    link-state domain.

    With the introduction of areas, it is no longer true that all
    routers in the AS have an identical link-state database.  A router
    actually has a separate link-state database for each area it is
    connected to.  (Routers connected to multiple areas are called area
    border routers).  Two routers belonging to the same area have, for
    that area, identical area link-state databases.

    Routing in the Autonomous System takes place on two levels,
    depending on whether the source and destination of a packet reside
    in the same area (intra-area routing is used) or different areas
    (inter-area routing is used).  In intra-area routing, the packet is
    routed solely on information obtained within the area; no routing
Top   ToC   RFC2328 - Page 27
    information obtained from outside the area can be used.  This
    protects intra-area routing from the injection of bad routing
    information.  We discuss inter-area routing in Section 3.2.


    3.1.  The backbone of the Autonomous System

        The OSPF backbone is the special OSPF Area 0 (often written as
        Area 0.0.0.0, since OSPF Area ID's are typically formatted as IP
        addresses). The OSPF backbone always contains all area border
        routers. The backbone is responsible for distributing routing
        information between non-backbone areas. The backbone must be
        contiguous. However, it need not be physically contiguous;
        backbone connectivity can be established/maintained through the
        configuration of virtual links.

        Virtual links can be configured between any two backbone routers
        that have an interface to a common non-backbone area.  Virtual
        links belong to the backbone.  The protocol treats two routers
        joined by a virtual link as if they were connected by an
        unnumbered point-to-point backbone network.  On the graph of the
        backbone, two such routers are joined by arcs whose costs are
        the intra-area distances between the two routers.  The routing
        protocol traffic that flows along the virtual link uses intra-
        area routing only.


    3.2.  Inter-area routing

        When routing a packet between two non-backbone areas the
        backbone is used.  The path that the packet will travel can be
        broken up into three contiguous pieces: an intra-area path from
        the source to an area border router, a backbone path between the
        source and destination areas, and then another intra-area path
        to the destination.  The algorithm finds the set of such paths
        that have the smallest cost.

        Looking at this another way, inter-area routing can be pictured
        as forcing a star configuration on the Autonomous System, with
        the backbone as hub and each of the non-backbone areas as
        spokes.
Top   ToC   RFC2328 - Page 28
        The topology of the backbone dictates the backbone paths used
        between areas.  The topology of the backbone can be enhanced by
        adding virtual links.  This gives the system administrator some
        control over the routes taken by inter-area traffic.

        The correct area border router to use as the packet exits the
        source area is chosen in exactly the same way routers
        advertising external routes are chosen.  Each area border router
        in an area summarizes for the area its cost to all networks
        external to the area.  After the SPF tree is calculated for the
        area, routes to all inter-area destinations are calculated by
        examining the summaries of the area border routers.


    3.3.  Classification of routers

        Before the introduction of areas, the only OSPF routers having a
        specialized function were those advertising external routing
        information, such as Router RT5 in Figure 2.  When the AS is
        split into OSPF areas, the routers are further divided according
        to function into the following four overlapping categories:


        Internal routers
            A router with all directly connected networks belonging to
            the same area. These routers run a single copy of the basic
            routing algorithm.

        Area border routers
            A router that attaches to multiple areas.  Area border
            routers run multiple copies of the basic algorithm, one copy
            for each attached area. Area border routers condense the
            topological information of their attached areas for
            distribution to the backbone.  The backbone in turn
            distributes the information to the other areas.

        Backbone routers
            A router that has an interface to the backbone area.  This
            includes all routers that interface to more than one area
            (i.e., area border routers).  However, backbone routers do
            not have to be area border routers.  Routers with all
            interfaces connecting to the backbone area are supported.
Top   ToC   RFC2328 - Page 29
        AS boundary routers
            A router that exchanges routing information with routers
            belonging to other Autonomous Systems.  Such a router
            advertises AS external routing information throughout the
            Autonomous System.  The paths to each AS boundary router are
            known by every router in the AS.  This classification is
            completely independent of the previous classifications: AS
            boundary routers may be internal or area border routers, and
            may or may not participate in the backbone.


    3.4.  A sample area configuration

        Figure 6 shows a sample area configuration.  The first area
        consists of networks N1-N4, along with their attached routers
        RT1-RT4.  The second area consists of networks N6-N8, along with
        their attached routers RT7, RT8, RT10 and RT11.  The third area
        consists of networks N9-N11 and Host H1, along with their
        attached routers RT9, RT11 and RT12.  The third area has been
        configured so that networks N9-N11 and Host H1 will all be
        grouped into a single route, when advertised external to the
        area (see Section 3.5 for more details).

        In Figure 6, Routers RT1, RT2, RT5, RT6, RT8, RT9 and RT12 are
        internal routers.  Routers RT3, RT4, RT7, RT10 and RT11 are area
        border routers.  Finally, as before, Routers RT5 and RT7 are AS
        boundary routers.

        Figure 7 shows the resulting link-state database for the Area 1.
        The figure completely describes that area's intra-area routing.
        It also shows the complete view of the internet for the two
        internal routers RT1 and RT2.  It is the job of the area border
        routers, RT3 and RT4, to advertise into Area 1 the distances to
        all destinations external to the area.  These are indicated in
        Figure 7 by the dashed stub routes.  Also, RT3 and RT4 must
        advertise into Area 1 the location of the AS boundary routers
        RT5 and RT7.  Finally, AS-external-LSAs from RT5 and RT7 are
        flooded throughout the entire AS, and in particular throughout
        Area 1.  These LSAs are included in Area 1's database, and yield
        routes to Networks N12-N15.

        Routers RT3 and RT4 must also summarize Area 1's topology for
Top   ToC   RFC2328 - Page 30
             ...........................
             .   +                     .
             .   | 3+---+              .      N12      N14
             . N1|--|RT1|\ 1           .        \ N13 /
             .   |  +---+ \            .        8\ |8/8
             .   +         \ ____      .          \|/
             .              /    \   1+---+8    8+---+6
             .             *  N3  *---|RT4|------|RT5|--------+
             .              \____/    +---+      +---+        |
             .    +         /      \   .           |7         |
             .    | 3+---+ /        \  .           |          |
             .  N2|--|RT2|/1        1\ .           |6         |
             .    |  +---+            +---+8    6+---+        |
             .    +                   |RT3|------|RT6|        |
             .                        +---+      +---+        |
             .                      2/ .         Ia|7         |
             .                      /  .           |          |
             .             +---------+ .           |          |
             .Area 1           N4      .           |          |
             ...........................           |          |
          ..........................               |          |
          .            N11         .               |          |
          .        +---------+     .               |          |
          .             |          .               |          |    N12
          .             |3         .             Ib|5         |6 2/
          .           +---+        .             +----+     +---+/
          .           |RT9|        .    .........|RT10|.....|RT7|---N15.
          .           +---+        .    .        +----+     +---+ 9    .
          .             |1         .    .    +  /3    1\      |1       .
          .            _|__        .    .    | /        \   __|_       .
          .           /    \      1+----+2   |/          \ /    \      .
          .          *  N9  *------|RT11|----|            *  N6  *     .
          .           \____/       +----+    |             \____/      .
          .             |          .    .    |                |        .
          .             |1         .    .    +                |1       .
          .  +--+   10+----+       .    .   N8              +---+      .
          .  |H1|-----|RT12|       .    .                   |RT8|      .
          .  +--+SLIP +----+       .    .                   +---+      .
          .             |2         .    .                     |4       .
          .             |          .    .                     |        .
          .        +---------+     .    .                 +--------+   .
Top   ToC   RFC2328 - Page 31
          .            N10         .    .                     N7       .
          .                        .    .Area 2                        .
          .Area 3                  .    ................................
          ..........................

                    Figure 6: A sample OSPF area configuration

        distribution to the backbone.  Their backbone LSAs are shown in
        Table 4.  These summaries show which networks are contained in
        Area 1 (i.e., Networks N1-N4), and the distance to these
        networks from the routers RT3 and RT4 respectively.


        The link-state database for the backbone is shown in Figure 8.
        The set of routers pictured are the backbone routers.  Router
        RT11 is a backbone router because it belongs to two areas.  In
        order to make the backbone connected, a virtual link has been
        configured between Routers R10 and R11.

        The area border routers RT3, RT4, RT7, RT10 and RT11 condense
        the routing information of their attached non-backbone areas for
        distribution via the backbone; these are the dashed stubs that
        appear in Figure 8.  Remember that the third area has been
        configured to condense Networks N9-N11 and Host H1 into a single
        route.  This yields a single dashed line for networks N9-N11 and
        Host H1 in Figure 8.  Routers RT5 and RT7 are AS boundary
        routers; their externally derived information also appears on
        the graph in Figure 8 as stubs.



                     Network   RT3 adv.   RT4 adv.
                     _____________________________
                     N1        4          4
                     N2        4          4
                     N3        1          1
                     N4        2          3

              Table 4: Networks advertised to the backbone
                        by Routers RT3 and RT4.
Top   ToC   RFC2328 - Page 32
                               **FROM**

                          |RT|RT|RT|RT|RT|RT|
                          |1 |2 |3 |4 |5 |7 |N3|
                       ----- -------------------
                       RT1|  |  |  |  |  |  |0 |
                       RT2|  |  |  |  |  |  |0 |
                       RT3|  |  |  |  |  |  |0 |
                   *   RT4|  |  |  |  |  |  |0 |
                   *   RT5|  |  |14|8 |  |  |  |
                   T   RT7|  |  |20|14|  |  |  |
                   O    N1|3 |  |  |  |  |  |  |
                   *    N2|  |3 |  |  |  |  |  |
                   *    N3|1 |1 |1 |1 |  |  |  |
                        N4|  |  |2 |  |  |  |  |
                     Ia,Ib|  |  |20|27|  |  |  |
                        N6|  |  |16|15|  |  |  |
                        N7|  |  |20|19|  |  |  |
                        N8|  |  |18|18|  |  |  |
                 N9-N11,H1|  |  |29|36|  |  |  |
                       N12|  |  |  |  |8 |2 |  |
                       N13|  |  |  |  |8 |  |  |
                       N14|  |  |  |  |8 |  |  |
                       N15|  |  |  |  |  |9 |  |

                      Figure 7: Area 1's Database.

              Networks and routers are represented by vertices.
              An edge of cost X connects Vertex A to Vertex B iff
              the intersection of Column A and Row B is marked
                               with an X.
Top   ToC   RFC2328 - Page 33
                                  **FROM**

                            |RT|RT|RT|RT|RT|RT|RT
                            |3 |4 |5 |6 |7 |10|11|
                         ------------------------
                         RT3|  |  |  |6 |  |  |  |
                         RT4|  |  |8 |  |  |  |  |
                         RT5|  |8 |  |6 |6 |  |  |
                         RT6|8 |  |7 |  |  |5 |  |
                         RT7|  |  |6 |  |  |  |  |
                     *  RT10|  |  |  |7 |  |  |2 |
                     *  RT11|  |  |  |  |  |3 |  |
                     T    N1|4 |4 |  |  |  |  |  |
                     O    N2|4 |4 |  |  |  |  |  |
                     *    N3|1 |1 |  |  |  |  |  |
                     *    N4|2 |3 |  |  |  |  |  |
                          Ia|  |  |  |  |  |5 |  |
                          Ib|  |  |  |7 |  |  |  |
                          N6|  |  |  |  |1 |1 |3 |
                          N7|  |  |  |  |5 |5 |7 |
                          N8|  |  |  |  |4 |3 |2 |
                   N9-N11,H1|  |  |  |  |  |  |11|
                         N12|  |  |8 |  |2 |  |  |
                         N13|  |  |8 |  |  |  |  |
                         N14|  |  |8 |  |  |  |  |
                         N15|  |  |  |  |9 |  |  |


                     Figure 8: The backbone's database.

              Networks and routers are represented by vertices.
              An edge of cost X connects Vertex A to Vertex B iff
              the intersection of Column A and Row B is marked
                                 with an X.

        The backbone enables the exchange of summary information between
        area border routers.  Every area border router hears the area
        summaries from all other area border routers.  It then forms a
        picture of the distance to all networks outside of its area by
        examining the collected LSAs, and adding in the backbone
        distance to each advertising router.
Top   ToC   RFC2328 - Page 34
        Again using Routers RT3 and RT4 as an example, the procedure
        goes as follows: They first calculate the SPF tree for the
        backbone.  This gives the distances to all other area border
        routers.  Also noted are the distances to networks (Ia and Ib)
        and AS boundary routers (RT5 and RT7) that belong to the
        backbone.  This calculation is shown in Table 5.


        Next, by looking at the area summaries from these area border
        routers, RT3 and RT4 can determine the distance to all networks
        outside their area.  These distances are then advertised
        internally to the area by RT3 and RT4.  The advertisements that
        Router RT3 and RT4 will make into Area 1 are shown in Table 6.
        Note that Table 6 assumes that an area range has been configured
        for the backbone which groups Ia and Ib into a single LSA.


        The information imported into Area 1 by Routers RT3 and RT4
        enables an internal router, such as RT1, to choose an area
        border router intelligently.  Router RT1 would use RT4 for
        traffic to Network N6, RT3 for traffic to Network N10, and would


                              dist  from   dist  from
                              RT3          RT4
                   __________________________________
                   to  RT3    *            21
                   to  RT4    22           *
                   to  RT7    20           14
                   to  RT10   15           22
                   to  RT11   18           25
                   __________________________________
                   to  Ia     20           27
                   to  Ib     15           22
                   __________________________________
                   to  RT5    14           8
                   to  RT7    20           14

                 Table 5: Backbone distances calculated
                        by Routers RT3 and RT4.
Top   ToC   RFC2328 - Page 35
                   Destination   RT3 adv.   RT4 adv.
                   _________________________________
                   Ia,Ib         20         27
                   N6            16         15
                   N7            20         19
                   N8            18         18
                   N9-N11,H1     29         36
                   _________________________________
                   RT5           14         8
                   RT7           20         14

              Table 6: Destinations advertised into Area 1
                        by Routers RT3 and RT4.

        load share between the two for traffic to Network N8.

        Router RT1 can also determine in this manner the shortest path
        to the AS boundary routers RT5 and RT7.  Then, by looking at RT5
        and RT7's AS-external-LSAs, Router RT1 can decide between RT5 or
        RT7 when sending to a destination in another Autonomous System
        (one of the networks N12-N15).

        Note that a failure of the line between Routers RT6 and RT10
        will cause the backbone to become disconnected.  Configuring a
        virtual link between Routers RT7 and RT10 will give the backbone
        more connectivity and more resistance to such failures.


    3.5.  IP subnetting support

        OSPF attaches an IP address mask to each advertised route.  The
        mask indicates the range of addresses being described by the
        particular route.  For example, a summary-LSA for the
        destination 128.185.0.0 with a mask of 0xffff0000 actually is
        describing a single route to the collection of destinations
        128.185.0.0 - 128.185.255.255.  Similarly, host routes are
        always advertised with a mask of 0xffffffff, indicating the
        presence of only a single destination.
Top   ToC   RFC2328 - Page 36
        Including the mask with each advertised destination enables the
        implementation of what is commonly referred to as variable-
        length subnetting.  This means that a single IP class A, B, or C
        network number can be broken up into many subnets of various
        sizes.  For example, the network 128.185.0.0 could be broken up
        into 62 variable-sized subnets: 15 subnets of size 4K, 15
        subnets of size 256, and 32 subnets of size 8.  Table 7 shows
        some of the resulting network addresses together with their
        masks.



                  Network address   IP address mask   Subnet size
                  _______________________________________________
                  128.185.16.0      0xfffff000        4K
                  128.185.1.0       0xffffff00        256
                  128.185.0.8       0xfffffff8        8


                         Table 7: Some sample subnet sizes.


        There are many possible ways of dividing up a class A, B, and C
        network into variable sized subnets.  The precise procedure for
        doing so is beyond the scope of this specification.  This
        specification however establishes the following guideline: When
        an IP packet is forwarded, it is always forwarded to the network
        that is the best match for the packet's destination.  Here best
        match is synonymous with the longest or most specific match.
        For example, the default route with destination of 0.0.0.0 and
        mask 0x00000000 is always a match for every IP destination.  Yet
        it is always less specific than any other match.  Subnet masks
        must be assigned so that the best match for any IP destination
        is unambiguous.

        Attaching an address mask to each route also enables the support
        of IP supernetting. For example, a single physical network
        segment could be assigned the [address,mask] pair
        [192.9.4.0,0xfffffc00]. The segment would then be single IP
        network, containing addresses from the four consecutive class C
        network numbers 192.9.4.0 through 192.9.7.0. Such addressing is
        now becoming commonplace with the advent of CIDR (see [Ref10]).
Top   ToC   RFC2328 - Page 37
        In order to get better aggregation at area boundaries, area
        address ranges can be employed (see Section C.2 for more
        details).  Each address range is defined as an [address,mask]
        pair.  Many separate networks may then be contained in a single
        address range, just as a subnetted network is composed of many
        separate subnets.  Area border routers then summarize the area
        contents (for distribution to the backbone) by advertising a
        single route for each address range.  The cost of the route is
        the maximum cost to any of the networks falling in the specified
        range.

        For example, an IP subnetted network might be configured as a
        single OSPF area.  In that case, a single address range could be
        configured:  a class A, B, or C network number along with its
        natural IP mask.  Inside the area, any number of variable sized
        subnets could be defined.  However, external to the area a
        single route for the entire subnetted network would be
        distributed, hiding even the fact that the network is subnetted
        at all.  The cost of this route is the maximum of the set of
        costs to the component subnets.


    3.6.  Supporting stub areas

        In some Autonomous Systems, the majority of the link-state
        database may consist of AS-external-LSAs.  An OSPF AS-external-
        LSA is usually flooded throughout the entire AS.  However, OSPF
        allows certain areas to be configured as "stub areas".  AS-
        external-LSAs are not flooded into/throughout stub areas;
        routing to AS external destinations in these areas is based on a
        (per-area) default only.  This reduces the link-state database
        size, and therefore the memory requirements, for a stub area's
        internal routers.

        In order to take advantage of the OSPF stub area support,
        default routing must be used in the stub area.  This is
        accomplished as follows.  One or more of the stub area's area
        border routers must advertise a default route into the stub area
        via summary-LSAs.  These summary defaults are flooded throughout
        the stub area, but no further.  (For this reason these defaults
        pertain only to the particular stub area).  These summary
        default routes will be used for any destination that is not
Top   ToC   RFC2328 - Page 38
        explicitly reachable by an intra-area or inter-area path (i.e.,
        AS external destinations).

        An area can be configured as a stub when there is a single exit
        point from the area, or when the choice of exit point need not
        be made on a per-external-destination basis.  For example, Area
        3 in Figure 6 could be configured as a stub area, because all
        external traffic must travel though its single area border
        router RT11.  If Area 3 were configured as a stub, Router RT11
        would advertise a default route for distribution inside Area 3
        (in a summary-LSA), instead of flooding the AS-external-LSAs for
        Networks N12-N15 into/throughout the area.

        The OSPF protocol ensures that all routers belonging to an area
        agree on whether the area has been configured as a stub.  This
        guarantees that no confusion will arise in the flooding of AS-
        external-LSAs.

        There are a couple of restrictions on the use of stub areas.
        Virtual links cannot be configured through stub areas.  In
        addition, AS boundary routers cannot be placed internal to stub
        areas.


    3.7.  Partitions of areas

        OSPF does not actively attempt to repair area partitions.  When
        an area becomes partitioned, each component simply becomes a
        separate area.  The backbone then performs routing between the
        new areas.  Some destinations reachable via intra-area routing
        before the partition will now require inter-area routing.

        However, in order to maintain full routing after the partition,
        an address range must not be split across multiple components of
        the area partition. Also, the backbone itself must not
        partition.  If it does, parts of the Autonomous System will
        become unreachable.  Backbone partitions can be repaired by
        configuring virtual links (see Section 15).

        Another way to think about area partitions is to look at the
        Autonomous System graph that was introduced in Section 2.  Area
        IDs can be viewed as colors for the graph's edges.[1] Each edge
Top   ToC   RFC2328 - Page 39
        of the graph connects to a network, or is itself a point-to-
        point network.  In either case, the edge is colored with the
        network's Area ID.

        A group of edges, all having the same color, and interconnected
        by vertices, represents an area.  If the topology of the
        Autonomous System is intact, the graph will have several regions
        of color, each color being a distinct Area ID.

        When the AS topology changes, one of the areas may become
        partitioned.  The graph of the AS will then have multiple
        regions of the same color (Area ID).  The routing in the
        Autonomous System will continue to function as long as these
        regions of same color are connected by the single backbone
        region.
Top   ToC   RFC2328 - Page 40
4.  Functional Summary

    A separate copy of OSPF's basic routing algorithm runs in each area.
    Routers having interfaces to multiple areas run multiple copies of
    the algorithm.  A brief summary of the routing algorithm follows.

    When a router starts, it first initializes the routing protocol data
    structures.  The router then waits for indications from the lower-
    level protocols that its interfaces are functional.

    A router then uses the OSPF's Hello Protocol to acquire neighbors.
    The router sends Hello packets to its neighbors, and in turn
    receives their Hello packets.  On broadcast and point-to-point
    networks, the router dynamically detects its neighboring routers by
    sending its Hello packets to the multicast address AllSPFRouters.
    On non-broadcast networks, some configuration information may be
    necessary in order to discover neighbors.  On broadcast and NBMA
    networks the Hello Protocol also elects a Designated router for the
    network.

    The router will attempt to form adjacencies with some of its newly
    acquired neighbors.  Link-state databases are synchronized between
    pairs of adjacent routers.  On broadcast and NBMA networks, the
    Designated Router determines which routers should become adjacent.

    Adjacencies control the distribution of routing information.
    Routing updates are sent and received only on adjacencies.

    A router periodically advertises its state, which is also called
    link state.  Link state is also advertised when a router's state
    changes.  A router's adjacencies are reflected in the contents of
    its LSAs.  This relationship between adjacencies and link state
    allows the protocol to detect dead routers in a timely fashion.

    LSAs are flooded throughout the area.  The flooding algorithm is
    reliable, ensuring that all routers in an area have exactly the same
    link-state database.  This database consists of the collection of
    LSAs originated by each router belonging to the area.  From this
    database each router calculates a shortest-path tree, with itself as
    root.  This shortest-path tree in turn yields a routing table for
    the protocol.
Top   ToC   RFC2328 - Page 41
    4.1.  Inter-area routing

        The previous section described the operation of the protocol
        within a single area.  For intra-area routing, no other routing
        information is pertinent.  In order to be able to route to
        destinations outside of the area, the area border routers inject
        additional routing information into the area.  This additional
        information is a distillation of the rest of the Autonomous
        System's topology.

        This distillation is accomplished as follows: Each area border
        router is by definition connected to the backbone.  Each area
        border router summarizes the topology of its attached non-
        backbone areas for transmission on the backbone, and hence to
        all other area border routers.  An area border router then has
        complete topological information concerning the backbone, and
        the area summaries from each of the other area border routers.
        From this information, the router calculates paths to all
        inter-area destinations.  The router then advertises these paths
        into its attached areas.  This enables the area's internal
        routers to pick the best exit router when forwarding traffic
        inter-area destinations.


    4.2.  AS external routes

        Routers that have information regarding other Autonomous Systems
        can flood this information throughout the AS.  This external
        routing information is distributed verbatim to every
        participating router.  There is one exception: external routing
        information is not flooded into "stub" areas (see Section 3.6).

        To utilize external routing information, the path to all routers
        advertising external information must be known throughout the AS
        (excepting the stub areas).  For that reason, the locations of
        these AS boundary routers are summarized by the (non-stub) area
        border routers.
Top   ToC   RFC2328 - Page 42
    4.3.  Routing protocol packets

        The OSPF protocol runs directly over IP, using IP protocol 89.
        OSPF does not provide any explicit fragmentation/reassembly
        support.  When fragmentation is necessary, IP
        fragmentation/reassembly is used.  OSPF protocol packets have
        been designed so that large protocol packets can generally be
        split into several smaller protocol packets.  This practice is
        recommended; IP fragmentation should be avoided whenever
        possible.

        Routing protocol packets should always be sent with the IP TOS
        field set to 0.  If at all possible, routing protocol packets
        should be given preference over regular IP data traffic, both
        when being sent and received.  As an aid to accomplishing this,
        OSPF protocol packets should have their IP precedence field set
        to the value Internetwork Control (see [Ref5]).

        All OSPF protocol packets share a common protocol header that is
        described in Appendix A.  The OSPF packet types are listed below
        in Table 8.  Their formats are also described in Appendix A.



             Type   Packet  name           Protocol  function
             __________________________________________________________
             1      Hello                  Discover/maintain  neighbors
             2      Database Description   Summarize database contents
             3      Link State Request     Database download
             4      Link State Update      Database update
             5      Link State Ack         Flooding acknowledgment


                            Table 8: OSPF packet types.


        OSPF's Hello protocol uses Hello packets to discover and
        maintain neighbor relationships.  The Database Description and
        Link State Request packets are used in the forming of
        adjacencies.  OSPF's reliable update mechanism is implemented by
        the Link State Update and Link State Acknowledgment packets.
Top   ToC   RFC2328 - Page 43
        Each Link State Update packet carries a set of new link state
        advertisements (LSAs) one hop further away from their point of
        origination.  A single Link State Update packet may contain the
        LSAs of several routers.  Each LSA is tagged with the ID of the
        originating router and a checksum of its link state contents.
        Each LSA also has a type field; the different types of OSPF LSAs
        are listed below in Table 9.

        OSPF routing packets (with the exception of Hellos) are sent
        only over adjacencies.  This means that all OSPF protocol
        packets travel a single IP hop, except those that are sent over
        virtual adjacencies.  The IP source address of an OSPF protocol
        packet is one end of a router adjacency, and the IP destination
        address is either the other end of the adjacency or an IP
        multicast address.


    4.4.  Basic implementation requirements

        An implementation of OSPF requires the following pieces of
        system support:


        Timers
            Two different kind of timers are required.  The first kind,
            called "single shot timers", fire once and cause a protocol
            event to be processed.  The second kind, called "interval
            timers", fire at continuous intervals.  These are used for
            the sending of packets at regular intervals.  A good example
            of this is the regular broadcast of Hello packets. The
            granularity of both kinds of timers is one second.

            Interval timers should be implemented to avoid drift.  In
            some router implementations, packet processing can affect
            timer execution.  When multiple routers are attached to a
            single network, all doing broadcasts, this can lead to the
            synchronization of routing packets (which should be
            avoided).  If timers cannot be implemented to avoid drift,
            small random amounts should be added to/subtracted from the
            interval timer at each firing.
Top   ToC   RFC2328 - Page 44
        LS     LSA                LSA description
        type   name
        ________________________________________________________
        1      Router-LSAs        Originated by all routers.
                                  This LSA describes
                                  the collected states of the
                                  router's interfaces to an
                                  area. Flooded throughout a
                                  single area only.
        ________________________________________________________
        2      Network-LSAs       Originated for broadcast
                                  and NBMA networks by
                                  the Designated Router. This
                                  LSA contains the
                                  list of routers connected
                                  to the network. Flooded
                                  throughout a single area only.
        ________________________________________________________
        3,4    Summary-LSAs       Originated by area border
                                  routers, and flooded through-
                                  out the LSA's associated
                                  area. Each summary-LSA
                                  describes a route to a
                                  destination outside the area,
                                  yet still inside the AS
                                  (i.e., an inter-area route).
                                  Type 3 summary-LSAs describe
                                  routes to networks. Type 4
                                  summary-LSAs describe
                                  routes to AS boundary routers.
        ________________________________________________________
        5      AS-external-LSAs   Originated by AS boundary
                                  routers, and flooded through-
                                  out the AS. Each
                                  AS-external-LSA describes
                                  a route to a destination in
                                  another Autonomous System.
                                  Default routes for the AS can
                                  also be described by
                                  AS-external-LSAs.
Top   ToC   RFC2328 - Page 45
            Table 9: OSPF link state advertisements (LSAs).



        IP multicast
            Certain OSPF packets take the form of IP multicast
            datagrams.  Support for receiving and sending IP multicast
            datagrams, along with the appropriate lower-level protocol
            support, is required.  The IP multicast datagrams used by
            OSPF never travel more than one hop. For this reason, the
            ability to forward IP multicast datagrams is not required.
            For information on IP multicast, see [Ref7].

        Variable-length subnet support
            The router's IP protocol support must include the ability to
            divide a single IP class A, B, or C network number into many
            subnets of various sizes.  This is commonly called
            variable-length subnetting; see Section 3.5 for details.

        IP supernetting support
            The router's IP protocol support must include the ability to
            aggregate contiguous collections of IP class A, B, and C
            networks into larger quantities called supernets.
            Supernetting has been proposed as one way to improve the
            scaling of IP routing in the worldwide Internet. For more
            information on IP supernetting, see [Ref10].

        Lower-level protocol support
            The lower level protocols referred to here are the network
            access protocols, such as the Ethernet data link layer.
            Indications must be passed from these protocols to OSPF as
            the network interface goes up and down.  For example, on an
            ethernet it would be valuable to know when the ethernet
            transceiver cable becomes unplugged.

        Non-broadcast lower-level protocol support
            On non-broadcast networks, the OSPF Hello Protocol can be
            aided by providing an indication when an attempt is made to
            send a packet to a dead or non-existent router.  For
            example, on an X.25 PDN a dead neighboring router may be
Top   ToC   RFC2328 - Page 46
            indicated by the reception of a X.25 clear with an
            appropriate cause and diagnostic, and this information would
            be passed to OSPF.

        List manipulation primitives
            Much of the OSPF functionality is described in terms of its
            operation on lists of LSAs.  For example, the collection of
            LSAs that will be retransmitted to an adjacent router until
            acknowledged are described as a list.  Any particular LSA
            may be on many such lists.  An OSPF implementation needs to
            be able to manipulate these lists, adding and deleting
            constituent LSAs as necessary.

        Tasking support
            Certain procedures described in this specification invoke
            other procedures.  At times, these other procedures should
            be executed in-line, that is, before the current procedure
            is finished.  This is indicated in the text by instructions
            to execute a procedure.  At other times, the other
            procedures are to be executed only when the current
            procedure has finished.  This is indicated by instructions
            to schedule a task.


    4.5.  Optional OSPF capabilities

        The OSPF protocol defines several optional capabilities.  A
        router indicates the optional capabilities that it supports in
        its OSPF Hello packets, Database Description packets and in its
        LSAs.  This enables routers supporting a mix of optional
        capabilities to coexist in a single Autonomous System.

        Some capabilities must be supported by all routers attached to a
        specific area.  In this case, a router will not accept a
        neighbor's Hello Packet unless there is a match in reported
        capabilities (i.e., a capability mismatch prevents a neighbor
        relationship from forming).  An example of this is the
        ExternalRoutingCapability (see below).

        Other capabilities can be negotiated during the Database
        Exchange process.  This is accomplished by specifying the
        optional capabilities in Database Description packets.  A
Top   ToC   RFC2328 - Page 47
        capability mismatch with a neighbor in this case will result in
        only a subset of the link state database being exchanged between
        the two neighbors.

        The routing table build process can also be affected by the
        presence/absence of optional capabilities.  For example, since
        the optional capabilities are reported in LSAs, routers
        incapable of certain functions can be avoided when building the
        shortest path tree.

        The OSPF optional capabilities defined in this memo are listed
        below.  See Section A.2 for more information.


        ExternalRoutingCapability
            Entire OSPF areas can be configured as "stubs" (see Section
            3.6).  AS-external-LSAs will not be flooded into stub areas.
            This capability is represented by the E-bit in the OSPF
            Options field (see Section A.2).  In order to ensure
            consistent configuration of stub areas, all routers
            interfacing to such an area must have the E-bit clear in
            their Hello packets (see Sections 9.5 and 10.5).


5.  Protocol Data Structures

    The OSPF protocol is described herein in terms of its operation on
    various protocol data structures.  The following list comprises the
    top-level OSPF data structures.  Any initialization that needs to be
    done is noted.  OSPF areas, interfaces and neighbors also have
    associated data structures that are described later in this
    specification.

    Router ID
        A 32-bit number that uniquely identifies this router in the AS.
        One possible implementation strategy would be to use the
        smallest IP interface address belonging to the router. If a
        router's OSPF Router ID is changed, the router's OSPF software
        should be restarted before the new Router ID takes effect.  In
        this case the router should flush its self-originated LSAs from
        the routing domain (see Section 14.1) before restarting, or they
        will persist for up to MaxAge minutes.
Top   ToC   RFC2328 - Page 48
    Area structures
        Each one of the areas to which the router is connected has its
        own data structure.  This data structure describes the working
        of the basic OSPF algorithm.  Remember that each area runs a
        separate copy of the basic OSPF algorithm.

    Backbone (area) structure
        The OSPF backbone area is responsible for the dissemination of
        inter-area routing information.

    Virtual links configured
        The virtual links configured with this router as one endpoint.
        In order to have configured virtual links, the router itself
        must be an area border router.  Virtual links are identified by
        the Router ID of the other endpoint -- which is another area
        border router.  These two endpoint routers must be attached to a
        common area, called the virtual link's Transit area.  Virtual
        links are part of the backbone, and behave as if they were
        unnumbered point-to-point networks between the two routers.  A
        virtual link uses the intra-area routing of its Transit area to
        forward packets.  Virtual links are brought up and down through
        the building of the shortest-path trees for the Transit area.

    List of external routes
        These are routes to destinations external to the Autonomous
        System, that have been gained either through direct experience
        with another routing protocol (such as BGP), or through
        configuration information, or through a combination of the two
        (e.g., dynamic external information to be advertised by OSPF
        with configured metric). Any router having these external routes
        is called an AS boundary router.  These routes are advertised by
        the router into the OSPF routing domain via AS-external-LSAs.

    List of AS-external-LSAs
        Part of the link-state database.  These have originated from the
        AS boundary routers.  They comprise routes to destinations
        external to the Autonomous System.  Note that, if the router is
        itself an AS boundary router, some of these AS-external-LSAs
        have been self-originated.
Top   ToC   RFC2328 - Page 49
    The routing table
        Derived from the link-state database.  Each entry in the routing
        table is indexed by a destination, and contains the
        destination's cost and a set of paths to use in forwarding
        packets to the destination. A path is described by its type and
        next hop.  For more information, see Section 11.

    Figure 9 shows the collection of data structures present in a
    typical router.  The router pictured is RT10, from the map in Figure
    6.  Note that Router RT10 has a virtual link configured to Router
    RT11, with Area 2 as the link's Transit area.  This is indicated by
    the dashed line in Figure 9.  When the virtual link becomes active,
    through the building of the shortest path tree for Area 2, it
    becomes an interface to the backbone (see the two backbone
    interfaces depicted in Figure 9).

6.  The Area Data Structure

    The area data structure contains all the information used to run the
    basic OSPF routing algorithm. Each area maintains its own link-state
    database. A network belongs to a single area, and a router interface
    connects to a single area. Each router adjacency also belongs to a
    single area.

    The OSPF backbone is the special OSPF area responsible for
    disseminating inter-area routing information.

    The area link-state database consists of the collection of router-
    LSAs, network-LSAs and summary-LSAs that have originated from the
    area's routers.  This information is flooded throughout a single
    area only.  The list of AS-external-LSAs (see Section 5) is also
    considered to be part of each area's link-state database.

    Area ID
        A 32-bit number identifying the area. The Area ID of 0.0.0.0 is
        reserved for the backbone.

    List of area address ranges
        In order to aggregate routing information at area boundaries,
        area address ranges can be employed. Each address range is
        specified by an [address,mask] pair and a status indication of
        either Advertise or DoNotAdvertise (see Section 12.4.3).
Top   ToC   RFC2328 - Page 50
                              +----+
                              |RT10|------+
                              +----+       \+-------------+
                             /      \       |Routing Table|
                            /        \      +-------------+
                           /          \
              +------+    /            \    +--------+
              |Area 2|---+              +---|Backbone|
              +------+***********+          +--------+
             /        \           *        /          \
            /          \           *      /            \
       +---------+  +---------+    +------------+       +------------+
       |Interface|  |Interface|    |Virtual Link|       |Interface Ib|
       |  to N6  |  |  to N8  |    |   to RT11  |       +------------+
       +---------+  +---------+    +------------+             |
           /  \           |               |                   |
          /    \          |               |                   |
   +--------+ +--------+  |        +-------------+      +------------+
   |Neighbor| |Neighbor|  |        |Neighbor RT11|      |Neighbor RT6|
   |  RT8   | |  RT7   |  |        +-------------+      +------------+
   +--------+ +--------+  |
                          |
                     +-------------+
                     |Neighbor RT11|
                     +-------------+


                Figure 9: Router RT10's Data structures

    Associated router interfaces
        This router's interfaces connecting to the area.  A router
        interface belongs to one and only one area (or the backbone).
        For the backbone area this list includes all the virtual links.
        A virtual link is identified by the Router ID of its other
        endpoint; its cost is the cost of the shortest intra-area path
        through the Transit area that exists between the two routers.
Top   ToC   RFC2328 - Page 51
    List of router-LSAs
        A router-LSA is generated by each router in the area.  It
        describes the state of the router's interfaces to the area.

    List of network-LSAs
        One network-LSA is generated for each transit broadcast and NBMA
        network in the area.  A network-LSA describes the set of routers
        currently connected to the network.

    List of summary-LSAs
        Summary-LSAs originate from the area's area border routers.
        They describe routes to destinations internal to the Autonomous
        System, yet external to the area (i.e., inter-area
        destinations).

    Shortest-path tree
        The shortest-path tree for the area, with this router itself as
        root.  Derived from the collected router-LSAs and network-LSAs
        by the Dijkstra algorithm (see Section 16.1).

    TransitCapability
        This parameter indicates whether the area can carry data traffic
        that neither originates nor terminates in the area itself. This
        parameter is calculated when the area's shortest-path tree is
        built (see Section 16.1, where TransitCapability is set to TRUE
        if and only if there are one or more fully adjacent virtual
        links using the area as Transit area), and is used as an input
        to a subsequent step of the routing table build process (see
        Section 16.3). When an area's TransitCapability is set to TRUE,
        the area is said to be a "transit area".

    ExternalRoutingCapability
        Whether AS-external-LSAs will be flooded into/throughout the
        area.  This is a configurable parameter.  If AS-external-LSAs
        are excluded from the area, the area is called a "stub". Within
        stub areas, routing to AS external destinations will be based
        solely on a default summary route.  The backbone cannot be
        configured as a stub area.  Also, virtual links cannot be
        configured through stub areas.  For more information, see
        Section 3.6.
Top   ToC   RFC2328 - Page 52
    StubDefaultCost
        If the area has been configured as a stub area, and the router
        itself is an area border router, then the StubDefaultCost
        indicates the cost of the default summary-LSA that the router
        should advertise into the area. See Section 12.4.3 for more
        information.


    Unless otherwise specified, the remaining sections of this document
    refer to the operation of the OSPF protocol within a single area.




(page 52 continued on part 3)

Next Section