Tech-invite3GPPspaceIETF RFCsSIP
in Index   Prev   Next

RFC 2178

OSPF Version 2

Pages: 211
Obsoletes:  1583
Obsoleted by:  2328
Part 2 of 8 – Pages 22 to 49
First   Prev   Next

ToP   noToC   RFC2178 - Page 22   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
ToP   noToC   RFC2178 - Page 23
   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 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, 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.
ToP   noToC   RFC2178 - Page 24
   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.

   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

   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   noToC   RFC2178 - Page 25
   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.
ToP   noToC   RFC2178 - Page 26
             .   +                     .
             .   | 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       .
          .             |          .    .                     |        .
          .        +---------+     .    .                 +--------+   .
          .            N10         .    .                     N7       .
          .                        .    .Area 2                        .
          .Area 3                  .    ................................

               Figure 6: A sample OSPF area configuration
ToP   noToC   RFC2178 - Page 27
   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
   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   noToC   RFC2178 - Page 28
                          |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   noToC   RFC2178 - Page 29

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

   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.
ToP   noToC   RFC2178 - Page 30
   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 load share between the two
   for traffic to Network N8.

                              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.

                   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.
ToP   noToC   RFC2178 - Page 31
   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
   with a mask of 0xffff0000 actually is describing a single route to
   the collection of destinations -
   Similarly, host routes are always advertised with a mask of
   0xffffffff, indicating the presence of only a single destination.

   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 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
              0xfffff000        4K
               0xffffff00        256
               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
ToP   noToC   RFC2178 - Page 32
   route with destination of 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 [,0xfffffc00]. The
   segment would then be single IP network, containing addresses from
   the four consecutive class C network numbers through Such addressing is now becoming commonplace with the
   advent of CIDR (see [Ref10]).

   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
ToP   noToC   RFC2178 - Page 33
   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 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 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.
ToP   noToC   RFC2178 - Page 34
   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.

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
ToP   noToC   RFC2178 - Page 35
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

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
ToP   noToC   RFC2178 - Page 36
   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.

   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.
ToP   noToC   RFC2178 - Page 37
        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

            Table 9: OSPF link state advertisements (LSAs).
ToP   noToC   RFC2178 - Page 38
4.4.  Basic implementation requirements

   An implementation of OSPF requires the following pieces of system

      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

   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

   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
ToP   noToC   RFC2178 - Page 39
   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

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

   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).
ToP   noToC   RFC2178 - Page 40
   Other capabilities can be negotiated during the Database Exchange
   process.  This is accomplished by specifying the optional
   capabilities in Database Description packets.  A 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

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

      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

   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.

   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.
ToP   noToC   RFC2178 - Page 41
   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.

   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.
ToP   noToC   RFC2178 - Page 42
   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).

                              +----+       \+-------------+
                             /      \       |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

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.
ToP   noToC   RFC2178 - Page 43
   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 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).

   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.

   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).
ToP   noToC   RFC2178 - Page 44
      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".

      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.

      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

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

7.  Bringing Up Adjacencies

   OSPF creates adjacencies between neighboring routers for the purpose
   of exchanging routing information. Not every two neighboring routers
   will become adjacent.  This section covers the generalities involved
   in creating adjacencies.  For further details consult Section 10.

7.1.  The Hello Protocol

   The Hello Protocol is responsible for establishing and maintaining
   neighbor relationships.  It also ensures that communication between
   neighbors is bidirectional.  Hello packets are sent periodically out
   all router interfaces.  Bidirectional communication is indicated when
   the router sees itself listed in the neighbor's Hello Packet.  On
   broadcast and NBMA networks, the Hello Protocol elects a Designated
   Router for the network.
ToP   noToC   RFC2178 - Page 45
   The Hello Protocol works differently on broadcast networks, NBMA
   networks and Point-to-MultiPoint networks.  On broadcast networks,
   each router advertises itself by periodically multicasting Hello
   Packets.  This allows neighbors to be discovered dynamically.  These
   Hello Packets contain the router's view of the Designated Router's
   identity, and the list of routers whose Hello Packets have been seen

   On NBMA networks some configuration information may be necessary for
   the operation of the Hello Protocol.  Each router that may
   potentially become Designated Router has a list of all other routers
   attached to the network.  A router, having Designated Router
   potential, sends Hello Packets to all other potential Designated
   Routers when its interface to the NBMA network first becomes
   operational.  This is an attempt to find the Designated Router for
   the network.  If the router itself is elected Designated Router, it
   begins sending Hello Packets to all other routers attached to the

   On Point-to-MultiPoint networks, a router sends Hello Packets to all
   neighbors with which it can communicate directly. These neighbors may
   be discovered dynamically through a protocol such as Inverse ARP (see
   [Ref14]), or they may be configured.

   After a neighbor has been discovered, bidirectional communication
   ensured, and (if on a broadcast or NBMA network) a Designated Router
   elected, a decision is made regarding whether or not an adjacency
   should be formed with the neighbor (see Section 10.4). If an
   adjacency is to be formed, the first step is to synchronize the
   neighbors' link-state databases.  This is covered in the next

7.2.  The Synchronization of Databases

   In a link-state routing algorithm, it is very important for all
   routers' link-state databases to stay synchronized.  OSPF simplifies
   this by requiring only adjacent routers to remain synchronized.  The
   synchronization process begins as soon as the routers attempt to
   bring up the adjacency.  Each router describes its database by
   sending a sequence of Database Description packets to its neighbor.
   Each Database Description Packet describes a set of LSAs belonging to
   the router's database.  When the neighbor sees an LSA that is more
   recent than its own database copy, it makes a note that this newer
   LSA should be requested.

   This sending and receiving of Database Description packets is called
   the "Database Exchange Process".  During this process, the two
   routers form a master/slave relationship.  Each Database Description
ToP   noToC   RFC2178 - Page 46
   Packet has a sequence number.  Database Description Packets sent by
   the master (polls) are acknowledged by the slave through echoing of
   the sequence number.  Both polls and their responses contain
   summaries of link state data.  The master is the only one allowed to
   retransmit Database Description Packets.  It does so only at fixed
   intervals, the length of which is the configured per-interface
   constant RxmtInterval.

   Each Database Description contains an indication that there are more
   packets to follow --- the M-bit.  The Database Exchange Process is
   over when a router has received and sent Database Description Packets
   with the M-bit off.

   During and after the Database Exchange Process, each router has a
   list of those LSAs for which the neighbor has more up-to-date
   instances.  These LSAs are requested in Link State Request Packets.
   Link State Request packets that are not satisfied are retransmitted
   at fixed intervals of time RxmtInterval.  When the Database
   Description Process has completed and all Link State Requests have
   been satisfied, the databases are deemed synchronized and the routers
   are marked fully adjacent.  At this time the adjacency is fully
   functional and is advertised in the two routers' router-LSAs.

   The adjacency is used by the flooding procedure as soon as the
   Database Exchange Process begins.  This simplifies database
   synchronization, and guarantees that it finishes in a predictable
   period of time.

7.3.  The Designated Router

   Every broadcast and NBMA network has a Designated Router.  The
   Designated Router performs two main functions for the routing

   o   The Designated Router originates a network-LSA on behalf of
       the network.  This LSA lists the set of routers (including
       the Designated Router itself) currently attached to the
       network.  The Link State ID for this LSA (see Section
       12.1.4) is the IP interface address of the Designated
       Router.  The IP network number can then be obtained by using
       the network's subnet/network mask.

   o   The Designated Router becomes adjacent to all other routers
       on the network.  Since the link state databases are
       synchronized across adjacencies (through adjacency bring-up
       and then the flooding procedure), the Designated Router
       plays a central part in the synchronization process.
ToP   noToC   RFC2178 - Page 47
   The Designated Router is elected by the Hello Protocol.  A router's
   Hello Packet contains its Router Priority, which is configurable on a
   per-interface basis.  In general, when a router's interface to a
   network first becomes functional, it checks to see whether there is
   currently a Designated Router for the network.  If there is, it
   accepts that Designated Router, regardless of its Router Priority.
   (This makes it harder to predict the identity of the Designated
   Router, but ensures that the Designated Router changes less often.
   See below.)  Otherwise, the router itself becomes Designated Router
   if it has the highest Router Priority on the network.  A more
   detailed (and more accurate) description of Designated Router
   election is presented in Section 9.4.

   The Designated Router is the endpoint of many adjacencies.  In order
   to optimize the flooding procedure on broadcast networks, the
   Designated Router multicasts its Link State Update Packets to the
   address AllSPFRouters, rather than sending separate packets over each

   Section 2 of this document discusses the directed graph
   representation of an area.  Router nodes are labelled with their
   Router ID.  Transit network nodes are actually labelled with the IP
   address of their Designated Router.  It follows that when the
   Designated Router changes, it appears as if the network node on the
   graph is replaced by an entirely new node.  This will cause the
   network and all its attached routers to originate new LSAs.  Until
   the link-state databases again converge, some temporary loss of
   connectivity may result.  This may result in ICMP unreachable
   messages being sent in response to data traffic.  For that reason,
   the Designated Router should change only infrequently.  Router
   Priorities should be configured so that the most dependable router on
   a network eventually becomes Designated Router.

7.4.  The Backup Designated Router

   In order to make the transition to a new Designated Router smoother,
   there is a Backup Designated Router for each broadcast and NBMA
   network.  The Backup Designated Router is also adjacent to all
   routers on the network, and becomes Designated Router when the
   previous Designated Router fails.  If there were no Backup Designated
   Router, when a new Designated Router became necessary, new
   adjacencies would have to be formed between the new Designated Router
   and all other routers attached to the network.  Part of the adjacency
   forming process is the synchronizing of link-state databases, which
   can potentially take quite a long time.  During this time, the
   network would not be available for transit data traffic.  The Backup
   Designated obviates the need to form these adjacencies, since they
   already exist.  This means the period of disruption in transit
ToP   noToC   RFC2178 - Page 48
   traffic lasts only as long as it takes to flood the new LSAs (which
   announce the new Designated Router).

   The Backup Designated Router does not generate a network-LSA for the
   network.  (If it did, the transition to a new Designated Router would
   be even faster.  However, this is a tradeoff between database size
   and speed of convergence when the Designated Router disappears.)

   The Backup Designated Router is also elected by the Hello Protocol.
   Each Hello Packet has a field that specifies the Backup Designated
   Router for the network.

   In some steps of the flooding procedure, the Backup Designated Router
   plays a passive role, letting the Designated Router do more of the
   work.  This cuts down on the amount of local routing traffic.  See
   Section 13.3 for more information.

7.5.  The graph of adjacencies

   An adjacency is bound to the network that the two routers have in
   common.  If two routers have multiple networks in common, they may
   have multiple adjacencies between them.

   One can picture the collection of adjacencies on a network as forming
   an undirected graph.  The vertices consist of routers, with an edge
   joining two routers if they are adjacent.  The graph of adjacencies
   describes the flow of routing protocol packets, and in particular
   Link State Update Packets, through the Autonomous System.

   Two graphs are possible, depending on whether a Designated Router is
   elected for the network.  On physical point-to-point networks,
   Point-to-MultiPoint networks and virtual links, neighboring routers
   become adjacent whenever they can communicate directly.  In contrast,
   on broadcast and NBMA networks only the Designated Router and the
   Backup Designated Router become adjacent to all other routers
   attached to the network.

   These graphs are shown in Figure 10.  It is assumed that Router RT7
   has become the Designated Router, and Router RT3 the Backup
   Designated Router, for the Network N2.  The Backup Designated Router
   performs a lesser function during the flooding procedure than the
   Designated Router (see Section 13.3).  This is the reason for the
   dashed lines connecting the Backup Designated Router RT3.
ToP   noToC   RFC2178 - Page 49
          +---+            +---+
          |RT1|------------|RT2|            o---------------o
          +---+    N1      +---+           RT1             RT2

            +---+   +---+   +---+                /|\        |
            |RT7|   |RT3|   |RT4|               / | \       |
            +---+   +---+   +---+              /  |  \      |
              |       |       |               /   |   \     |
         +-----------------------+        RT5o RT6o    oRT4 |
                  |       |     N2            *   *   *     |
                +---+   +---+                  *  *  *      |
                |RT5|   |RT6|                   * * *       |
                +---+   +---+                    ***        |

                  Figure 10: The graph of adjacencies

(page 49 continued on part 3)

Next Section