tech-invite   World Map     

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

RFC 2178


Pages: 211
Top     in Index     Prev     Next
 

OSPF Version 2

Part 1 of 8, p. 1 to 22
None       Next RFC Part

Obsoleted by:    2328
Obsoletes:    1583


Top       ToC       Page 1 
Network Working Group                                             J. Moy
Request for Comments: 2178                  Cascade Communications Corp.
Obsoletes: 1583                                                July 1997
Category: Standards Track


                             OSPF Version 2

Status of this Memo

   This document specifies an Internet standards track protocol for the
   Internet community, and requests discussion and suggestions for
   improvements.  Please refer to the current edition of the "Internet
   Official Protocol Standards" (STD 1) for the standardization state
   and status of this protocol.  Distribution of this memo is unlimited.

Abstract

   This memo documents version 2 of the OSPF protocol. OSPF is a link-
   state routing protocol.  It is designed to be run internal to a
   single Autonomous System.  Each OSPF router maintains an identical
   database describing the Autonomous System's topology.  From this
   database, a routing table is calculated by constructing a shortest-
   path tree.

   OSPF recalculates routes quickly in the face of topological changes,
   utilizing a minimum of routing protocol traffic.  OSPF provides
   support for equal-cost multipath.  An area routing capability is
   provided, enabling an additional level of routing protection and a
   reduction in routing protocol traffic.  In addition, all OSPF routing
   protocol exchanges are authenticated.

   The differences between this memo and RFC 1583 are explained in
   Appendix G. All differences are backward-compatible in nature.
   Implementations of this memo and of RFC 1583 will interoperate.

   Please send comments to ospf@gated.cornell.edu.

Table of Contents

    1        Introduction ........................................... 5
    1.1      Protocol Overview ...................................... 5
    1.2      Definitions of commonly used terms ..................... 6
    1.3      Brief history of link-state routing technology ........  9
    1.4      Organization of this document ......................... 10
    1.5      Acknowledgments ....................................... 11
    2        The link-state database: organization and calculations  11
    2.1      Representation of routers and networks ................ 11

Top      ToC       Page 2 
    2.1.1    Representation of non-broadcast networks .............. 13
    2.1.2    An example link-state database ........................ 14
    2.2      The shortest-path tree ................................ 18
    2.3      Use of external routing information ................... 20
    2.4      Equal-cost multipath .................................. 22
    3        Splitting the AS into Areas ........................... 22
    3.1      The backbone of the Autonomous System ................. 23
    3.2      Inter-area routing .................................... 23
    3.3      Classification of routers ............................. 24
    3.4      A sample area configuration ........................... 25
    3.5      IP subnetting support ................................. 31
    3.6      Supporting stub areas ................................. 32
    3.7      Partitions of areas ................................... 33
    4        Functional Summary .................................... 34
    4.1      Inter-area routing .................................... 35
    4.2      AS external routes .................................... 35
    4.3      Routing protocol packets .............................. 35
    4.4      Basic implementation requirements ..................... 38
    4.5      Optional OSPF capabilities ............................ 39
    5        Protocol data structures .............................. 40
    6        The Area Data Structure ............................... 42
    7        Bringing Up Adjacencies ............................... 44
    7.1      The Hello Protocol .................................... 44
    7.2      The Synchronization of Databases ...................... 45
    7.3      The Designated Router ................................. 46
    7.4      The Backup Designated Router .......................... 47
    7.5      The graph of adjacencies .............................. 48
    8        Protocol Packet Processing ............................ 49
    8.1      Sending protocol packets .............................. 49
    8.2      Receiving protocol packets ............................ 51
    9        The Interface Data Structure .......................... 54
    9.1      Interface states ...................................... 57
    9.2      Events causing interface state changes ................ 59
    9.3      The Interface state machine ........................... 61
    9.4      Electing the Designated Router ........................ 64
    9.5      Sending Hello packets ................................. 66
    9.5.1    Sending Hello packets on NBMA networks ................ 67
    10       The Neighbor Data Structure ........................... 68
    10.1     Neighbor states ....................................... 70
    10.2     Events causing neighbor state changes ................. 75
    10.3     The Neighbor state machine ............................ 76
    10.4     Whether tocome adjacent    ............................ 82
    10.5     Receiving Hello Packets ............................... 83
    10.6     Receiving Database Description Packets ................ 85
    10.7     Receiving Link State Request Packets .................. 88
    10.8     Sending Database Description Packets .................. 89
    10.9     Sending Link State Request Packets .................... 90
    10.10    An Example ............................................ 91

Top      ToC       Page 3 
    11       The Routing Table Structure ........................... 93
    11.1     Routing table lookup .................................. 96
    11.2     Sample routing table, without areas ................... 97
    11.3     Sample routing table, with areas ...................... 97
    12       Link State Advertisements (LSAs) ......................100
    12.1     The LSA Header ........................................100
    12.1.1   LS age ............................................... 101
    12.1.2   Options .............................................. 101
    12.1.3   LS type .............................................. 102
    12.1.4   Link State ID ........................................ 102
    12.1.5   Advertising Router ................................... 104
    12.1.6   LS sequence number ................................... 104
    12.1.7   LS checksum .......................................... 105
    12.2     The link state database .............................. 105
    12.3     Representation of TOS ................................ 106
    12.4     Originating LSAs ..................................... 107
    12.4.1   Router-LSAs .......................................... 110
    12.4.1.1 Describing point-to-point interfaces ................. 112
    12.4.1.2 Describing broadcast and NBMA interfaces ............. 113
    12.4.1.3 Describing virtual links ............................. 113
    12.4.1.4 Describing Point-to-MultiPoint interfaces ............ 114
    12.4.1.5 Examples of router-LSAs .............................. 114
    12.4.2   Network-LSAs ......................................... 116
    12.4.2.1 Examples of network-LSAs ............................. 116
    12.4.3   Summary-LSAs ......................................... 117
    12.4.3.1 Originating summary-LSAs into stub areas ............. 119
    12.4.3.2 Examples of summary-LSAs ............................. 119
    12.4.4   AS-external-LSAs ..................................... 120
    12.4.4.1 Examples of AS-external-LSAs ......................... 121
    13       The Flooding Procedure ............................... 122
    13.1     Determining which LSA is newer ....................... 126
    13.2     Installing LSAs in the database ...................... 127
    13.3     Next step in the flooding procedure .................. 128
    13.4     Receiving self-originated LSAs ....................... 130
    13.5     Sending Link State Acknowledgment packets ............ 131
    13.6     Retransmitting LSAs .................................. 133
    13.7     Receiving link state acknowledgments ................. 134
    14       Aging The Link State Database ........................ 134
    14.1     Premature aging of LSAs .............................. 135
    15       Virtual Links ........................................ 135
    16       Calculation of the routing table ..................... 137
    16.1     Calculating the shortest-path tree for an area ....... 138
    16.1.1   The next hop calculation ............................. 144
    16.2     Calculating the inter-area routes .................... 145
    16.3     Examining transit areas' summary-LSAs ................ 146
    16.4     Calculating AS external routes ....................... 149
    16.4.1   External path preferences ............................ 151
    16.5     Incremental updates -- summary-LSAs .................. 151

Top      ToC       Page 4 
    16.6     Incremental updates -- AS-external-LSAs .............. 152
    16.7     Events generated as a result of routing table changes  153
    16.8     Equal-cost multipath ................................. 154
             Footnotes ............................................ 155
             References ........................................... 158
    A.       OSPF data formats .................................... 160
    A.1      Encapsulation of OSPF packets ........................ 160
    A.2      The Options field .................................... 162
    A.3      OSPF Packet Formats .................................. 163
    A.3.1    The OSPF packet header ............................... 164
    A.3.2    The Hello packet ..................................... 166
    A.3.3    The Database Description packet ...................... 168
    A.3.4    The Link State Request packet ........................ 170
    A.3.5    The Link State Update packet ......................... 171
    A.3.6    The Link State Acknowledgment packet ................. 172
    A.4      LSA formats .......................................... 173
    A.4.1    The LSA header ....................................... 174
    A.4.2    Router-LSAs .......................................... 176
    A.4.3    Network-LSAs ......................................... 179
    A.4.4    Summary-LSAs ......................................... 180
    A.4.5    AS-external-LSAs ..................................... 182
    B.       Architectural Constants .............................. 184
    C.       Configurable Constants ............................... 186
    C.1      Global parameters .................................... 186
    C.2      Area parameters ...................................... 187
    C.3      Router interface parameters .......................... 188
    C.4      Virtual link parameters .............................. 190
    C.5      NBMA network parameters .............................. 191
    C.6      Point-to-MultiPoint network parameters ............... 191
    C.7      Host route parameters ................................ 192
    D.       Authentication ....................................... 193
    D.1      Null authentication .................................. 193
    D.2      Simple password authentication ....................... 193
    D.3      Cryptographic authentication ......................... 194
    D.4      Message generation ................................... 196
    D.4.1    Generating Null authentication ....................... 196
    D.4.2    Generating Simple password authentication ............ 197
    D.4.3    Generating Cryptographic authentication .............. 197
    D.5      Message verification ................................. 198
    D.5.1    Verifying Null authentication ........................ 199
    D.5.2    Verifying Simple password authentication ............. 199
    D.5.3    Verifying Cryptographic authentication ............... 199
    E.       An algorithm for assigning Link State IDs ............ 201
    F.       Multiple interfaces to the same network/subnet ....... 203
    G.       Differences from RFC 1583 ............................ 204
    G.1      Enhancements to OSPF authentication .................. 204
    G.2      Addition of Point-to-MultiPoint interface ............ 204
    G.3      Support for overlapping area ranges .................. 205

Top      ToC       Page 5 
    G.4      A modification to the flooding algorithm ............. 206
    G.5      Introduction of the MinLSArrival constant ............ 206
    G.6      Optionally advertising point-to-point links as subnets 207
    G.7      Advertising same external route from multiple areas .. 207
    G.8      Retransmission of initial Database Description packets 209
    G.9      Detecting interface MTU mismatches ................... 209
    G.10     Deleting the TOS routing option ...................... 209
             Security Considerations .............................. 210
             Author's Address ..................................... 211

1.  Introduction

   This document is a specification of the Open Shortest Path First
   (OSPF) TCP/IP internet routing protocol.  OSPF is classified as an
   Interior Gateway Protocol (IGP).  This means that it distributes
   routing information between routers belonging to a single Autonomous
   System.  The OSPF protocol is based on link-state or SPF technology.
   This is a departure from the Bellman-Ford base used by traditional
   TCP/IP internet routing protocols.

   The OSPF protocol was developed by the OSPF working group of the
   Internet Engineering Task Force.  It has been designed expressly for
   the TCP/IP internet environment, including explicit support for CIDR
   and the tagging of externally-derived routing information. OSPF also
   provides for the authentication of routing updates, and utilizes IP
   multicast when sending/receiving the updates.  In addition, much work
   has been done to produce a protocol that responds quickly to topology
   changes, yet involves small amounts of routing protocol traffic.

1.1.  Protocol overview

   OSPF routes IP packets based solely on the destination IP address
   found in the IP packet header. IP packets are routed "as is" -- they
   are not encapsulated in any further protocol headers as they transit
   the Autonomous System. OSPF is a dynamic routing protocol.  It
   quickly detects topological changes in the AS (such as router
   interface failures) and calculates new loop-free routes after a
   period of convergence.  This period of convergence is short and
   involves a minimum of routing traffic.

   In a link-state routing protocol, each router maintains a database
   describing the Autonomous System's topology.  This database is
   referred to as the link-state database. Each participating router has
   an identical database.  Each individual piece of this database is a
   particular router's local state (e.g., the router's usable interfaces
   and reachable neighbors).  The router distributes its local state
   throughout the Autonomous System by flooding.

Top      ToC       Page 6 
   All routers run the exact same algorithm, in parallel. From the
   link-state database, each router constructs a tree of shortest paths
   with itself as root.  This shortest-path tree gives the route to each
   destination in the Autonomous System.  Externally derived routing
   information appears on the tree as leaves.

   When several equal-cost routes to a destination exist, traffic is
   distributed equally among them.  The cost of a route is described by
   a single dimensionless metric.

   OSPF allows sets of networks to be grouped together.  Such a grouping
   is called an area.  The topology of an area is hidden from the rest
   of the Autonomous System.  This information hiding enables a
   significant reduction in routing traffic.  Also, routing within the
   area is determined only by the area's own topology, lending the area
   protection from bad routing data.  An area is a generalization of an
   IP subnetted network.

   OSPF enables the flexible configuration of IP subnets.  Each route
   distributed by OSPF has a destination and mask.  Two different
   subnets of the same IP network number may have different sizes (i.e.,
   different masks).  This is commonly referred to as variable length
   subnetting.  A packet is routed to the best (i.e., longest or most
   specific) match.  Host routes are considered to be subnets whose
   masks are "all ones" (0xffffffff).

   All OSPF protocol exchanges are authenticated.  This means that only
   trusted routers can participate in the Autonomous System's routing.
   A variety of authentication schemes can be used; in fact, separate
   authentication schemes can be configured for each IP subnet.

   Externally derived routing data (e.g., routes learned from an
   Exterior Gateway Protocol such as BGP; see [Ref23]) is advertised
   throughout the Autonomous System.  This externally derived data is
   kept separate from the OSPF protocol's link state data.  Each
   external route can also be tagged by the advertising router, enabling
   the passing of additional information between routers on the boundary
   of the Autonomous System.

1.2.  Definitions of commonly used terms

   This section provides definitions for terms that have a specific
   meaning to the OSPF protocol and that are used throughout the text.
   The reader unfamiliar with the Internet Protocol Suite is referred to
   [Ref13] for an introduction to IP.

Top      ToC       Page 7 
   Router
      A level three Internet Protocol packet switch.  Formerly called a
      gateway in much of the IP literature.

   Autonomous System
      A group of routers exchanging routing information via a common
      routing protocol.  Abbreviated as AS.

   Interior Gateway Protocol
      The routing protocol spoken by the routers belonging to an
      Autonomous system. Abbreviated as IGP.  Each Autonomous System has
      a single IGP.  Separate Autonomous Systems may be running
      different IGPs.

   Router ID
      A 32-bit number assigned to each router running the OSPF protocol.
      This number uniquely identifies the router within an Autonomous
      System.

   Network
      In this memo, an IP network/subnet/supernet.  It is possible for
      one physical network to be assigned multiple IP network/subnet
      numbers.  We consider these to be separate networks.  Point-to-
      point physical networks are an exception - they are considered a
      single network no matter how many (if any at all) IP
      network/subnet numbers are assigned to them.

   Network mask
      A 32-bit number indicating the range of IP addresses residing on a
      single IP network/subnet/supernet.  This specification displays
      network masks as hexadecimal numbers.  For example, the network
      mask for a class C IP network is displayed as 0xffffff00.  Such a
      mask is often displayed elsewhere in the literature as
      255.255.255.0.

   Point-to-point networks
      A network that joins a single pair of routers.  A 56Kb serial line
      is an example of a point-to-point network.

Top      ToC       Page 8 
   Broadcast networks
      Networks supporting many (more than two) attached routers,
      together with the capability to address a single physical message
      to all of the attached routers (broadcast).  Neighboring routers
      are discovered dynamically on these nets using OSPF's Hello
      Protocol.  The Hello Protocol itself takes advantage of the
      broadcast capability.  The OSPF protocol makes further use of
      multicast capabilities, if they exist.  Each pair of routers on a
      broadcast network is assumed to be able to communicate directly.
      An ethernet is an example of a broadcast network.

   Non-broadcast networks
      Networks supporting many (more than two) routers, but having no
      broadcast capability.  Neighboring routers are maintained on these
      nets using OSPF's Hello Protocol. However, due to the lack of
      broadcast capability, some configuration information may be
      necessary to aid in the discovery of neighbors. On non-broadcast
      networks, OSPF protocol packets that are normally multicast need
      to be sent to each neighboring router, in turn. An X.25 Public
      Data Network (PDN) is an example of a non-broadcast network.

      OSPF runs in one of two modes over non-broadcast networks.  The
      first mode, called non-broadcast multi-access or NBMA, simulates
      the operation of OSPF on a broadcast network. The second mode,
      called Point-to-MultiPoint, treats the non-broadcast network as a
      collection of point-to-point links.  Non-broadcast networks are
      referred to as NBMA networks or Point-to-MultiPoint networks,
      depending on OSPF's mode of operation over the network.

   Interface
      The connection between a router and one of its attached networks.
      An interface has state information associated with it, which is
      obtained from the underlying lower level protocols and the routing
      protocol itself.  An interface to a network has associated with it
      a single IP address and mask (unless the network is an unnumbered
      point-to-point network).  An interface is sometimes also referred
      to as a link.

   Neighboring routers
      Two routers that have interfaces to a common network.  Neighbor
      relationships are maintained by, and usually dynamically
      discovered by, OSPF's Hello Protocol.

   Adjacency
      A relationship formed between selected neighboring routers for the
      purpose of exchanging routing information.  Not every pair of
      neighboring routers become adjacent.

Top      ToC       Page 9 
   Link state advertisement
      Unit of data describing the local state of a router or network.
      For a router, this includes the state of the router's interfaces
      and adjacencies.  Each link state advertisement is flooded
      throughout the routing domain. The collected link state
      advertisements of all routers and networks forms the protocol's
      link state database.  Throughout this memo, link state
      advertisement is abbreviated as LSA.

   Hello Protocol
      The part of the OSPF protocol used to establish and maintain
      neighbor relationships.  On broadcast networks the Hello Protocol
      can also dynamically discover neighboring routers.

   Flooding
      The part of the OSPF protocol that distributes and synchronizes
      the link-state database between OSPF routers.

   Designated Router
      Each broadcast and NBMA network that has at least two attached
      routers has a Designated Router.  The Designated Router generates
      an LSA for the network and has other special responsibilities in
      the running of the protocol.  The Designated Router is elected by
      the Hello Protocol.

      The Designated Router concept enables a reduction in the number of
      adjacencies required on a broadcast or NBMA network.  This in turn
      reduces the amount of routing protocol traffic and the size of the
      link-state database.

   Lower-level protocols
      The underlying network access protocols that provide services to
      the Internet Protocol and in turn the OSPF protocol.  Examples of
      these are the X.25 packet and frame levels for X.25 PDNs, and the
      ethernet data link layer for ethernets.

1.3.  Brief history of link-state routing technology

   OSPF is a link state routing protocol.  Such protocols are also
   referred to in the literature as SPF-based or distributed-database
   protocols.  This section gives a brief description of the
   developments in link-state technology that have influenced the OSPF
   protocol.

   The first link-state routing protocol was developed for use in the
   ARPANET packet switching network.  This protocol is described in
   [Ref3].  It has formed the starting point for all other link-state
   protocols.  The homogeneous ARPANET environment, i.e., single-vendor

Top      ToC       Page 10 
   packet switches connected by synchronous serial lines, simplified the
   design and implementation of the original protocol.

   Modifications to this protocol were proposed in [Ref4].  These
   modifications dealt with increasing the fault tolerance of the
   routing protocol through, among other things, adding a checksum to
   the LSAs (thereby detecting database corruption).  The paper also
   included means for reducing the routing traffic overhead in a link-
   state protocol.  This was accomplished by introducing mechanisms
   which enabled the interval between LSA originations to be increased
   by an order of magnitude.

   A link-state algorithm has also been proposed for use as an ISO IS-IS
   routing protocol.  This protocol is described in [Ref2].  The
   protocol includes methods for data and routing traffic reduction when
   operating over broadcast networks.  This is accomplished by election
   of a Designated Router for each broadcast network, which then
   originates an LSA for the network.

   The OSPF Working Group of the IETF has extended this work in
   developing the OSPF protocol.  The Designated Router concept has been
   greatly enhanced to further reduce the amount of routing traffic
   required.  Multicast capabilities are utilized for additional routing
   bandwidth reduction.  An area routing scheme has been developed
   enabling information hiding/protection/reduction.  Finally, the
   algorithms have been tailored for efficient operation in TCP/IP
   internets.

1.4.  Organization of this document

   The first three sections of this specification give a general
   overview of the protocol's capabilities and functions.  Sections 4-16
   explain the protocol's mechanisms in detail.  Packet formats,
   protocol constants and configuration items are specified in the
   appendices.

   Labels such as HelloInterval encountered in the text refer to
   protocol constants.  They may or may not be configurable.
   Architectural constants are summarized in Appendix B.  Configurable
   constants are summarized in Appendix C.

   The detailed specification of the protocol is presented in terms of
   data structures.  This is done in order to make the explanation more
   precise.  Implementations of the protocol are required to support the
   functionality described, but need not use the precise data structures
   that appear in this memo.

Top      ToC       Page 11 
1.5.  Acknowledgments

   The author would like to thank Ran Atkinson, Fred Baker, Jeffrey
   Burgan, Rob Coltun, Dino Farinacci, Vince Fuller, Phanindra
   Jujjavarapu, Milo Medin, Tom Pusateri, Kannan Varadhan, Zhaohui Zhang
   and the rest of the OSPF Working Group for the ideas and support they
   have given to this project.

   The OSPF Point-to-MultiPoint interface is based on work done by Fred
   Baker.

   The OSPF Cryptographic Authentication option was developed by Fred
   Baker and Ran Atkinson.

2.  The Link-state Database: organization and calculations

   The following subsections describe the organization of OSPF's link-
   state database, and the routing calculations that are performed on
   the database in order to produce a router's routing table.

2.1.  Representation of routers and networks

   The Autonomous System's link-state database describes a directed
   graph.  The vertices of the graph consist of routers and networks.  A
   graph edge connects two routers when they are attached via a physical
   point-to-point network.  An edge connecting a router to a network
   indicates that the router has an interface on the network. Networks
   can be either transit or stub networks. Transit networks are those
   capable of carrying data traffic that is neither locally originated
   nor locally destined. A transit network is represented by a graph
   vertex having both incoming and outgoing edges. A stub network's
   vertex has only incoming edges.

   The neighborhood of each network node in the graph depends on the
   network's type (point-to-point, broadcast, NBMA or Point-to-
   MultiPoint) and the number of routers having an interface to the
   network.  Three cases are depicted in Figure 1a.  Rectangles indicate
   routers.  Circles and oblongs indicate networks.  Router names are
   prefixed with the letters RT and network names with the letter N.
   Router interface names are prefixed by the letter I.  Lines between
   routers indicate point-to-point networks.  The left side of the
   figure shows networks with their connected routers, with the
   resulting graphs shown on the right.

Top      ToC       Page 12 
                                                  **FROM**

                                           *      |RT1|RT2|
                +---+Ia    +---+           *   ------------
                |RT1|------|RT2|           T   RT1|   | X |
                +---+    Ib+---+           O   RT2| X |   |
                                           *    Ia|   | X |
                                           *    Ib| X |   |

                    Physical point-to-point networks

                                                  **FROM**
                      +---+                *
                      |RT7|                *      |RT7| N3|
                      +---+                T   ------------
                        |                  O   RT7|   |   |
            +----------------------+       *    N3| X |   |
                       N3                  *

                             Stub networks

                +---+      +---+
                |RT3|      |RT4|              |RT3|RT4|RT5|RT6|N2 |
                +---+      +---+        *  ------------------------
                  |    N2    |          *  RT3|   |   |   |   | X |
            +----------------------+    T  RT4|   |   |   |   | X |
                  |          |          O  RT5|   |   |   |   | X |
                +---+      +---+        *  RT6|   |   |   |   | X |
                |RT5|      |RT6|        *   N2| X | X | X | X |   |
                +---+      +---+

                       Broadcast or NBMA networks

                   Figure 1a: Network map components

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

   The top of Figure 1a shows two routers connected by a point-to-point
   link. In the resulting link-state database graph, the two router
   vertices are directly connected by a pair of edges, one in each
   direction. Interfaces to point-to-point networks need not be assigned
   IP addresses.  When interface addresses are assigned, they are
   modelled as stub links, with each router advertising a stub
   connection to the other router's interface address. Optionally, an IP

Top      ToC       Page 13 
   subnet can be assigned to the point-to-point network. In this case,
   both routers advertise a stub link to the IP subnet, instead of
   advertising each others' IP interface addresses.

   The middle of Figure 1a shows a network with only one attached router
   (i.e., a stub network). In this case, the network appears on the end
   of a stub connection in the link-state database's graph.

   When multiple routers are attached to a broadcast network, the link-
   state database graph shows all routers bidirectionally connected to
   the network vertex. This is pictured at the bottom of Figure 1a.

   Each network (stub or transit) in the graph has an IP address and
   associated network mask.  The mask indicates the number of nodes on
   the network.  Hosts attached directly to routers (referred to as host
   routes) appear on the graph as stub networks.  The network mask for a
   host route is always 0xffffffff, which indicates the presence of a
   single node.

2.1.1. Representation of non-broadcast networks

   As mentioned previously, OSPF can run over non-broadcast networks in
   one of two modes: NBMA or Point-to-MultiPoint.  The choice of mode
   determines the way that the Hello protocol and flooding work over the
   non-broadcast network, and the way that the network is represented in
   the link-state database.

   In NBMA mode, OSPF emulates operation over a broadcast network: a
   Designated Router is elected for the NBMA network, and the Designated
   Router originates an LSA for the network. The graph representation
   for broadcast networks and NBMA networks is identical. This
   representation is pictured in the middle of Figure 1a.

   NBMA mode is the most efficient way to run OSPF over non-broadcast
   networks, both in terms of link-state database size and in terms of
   the amount of routing protocol traffic.  However, it has one
   significant restriction: it requires all routers attached to the NBMA
   network to be able to communicate directly. This restriction may be
   met on some non-broadcast networks, such as an ATM subnet utilizing
   SVCs. But it is often not met on other non-broadcast networks, such
   as PVC-only Frame Relay networks. On non-broadcast networks where not
   all routers can communicate directly you can break the non-broadcast
   network into logical subnets, with the routers on each subnet being
   able to communicate directly, and then run each separate subnet as an
   NBMA network (see [Ref15]). This however requires quite a bit of
   administrative overhead, and is prone to misconfiguration. It is
   probably better to run such a non-broadcast network in Point-to-
   Multipoint mode.

Top      ToC       Page 14 
   In Point-to-MultiPoint mode, OSPF treats all router-to-router
   connections over the non-broadcast network as if they were point-to-
   point links. No Designated Router is elected for the network, nor is
   there an LSA generated for the network. In fact, a vertex for the
   Point-to-MultiPoint network does not appear in the graph of the
   link-state database.

   Figure 1b illustrates the link-state database representation of a
   Point-to-MultiPoint network. On the left side of the figure, a
   Point-to-MultiPoint network is pictured. It is assumed that all
   routers can communicate directly, except for routers RT4 and RT5. I3
   though I6 indicate the routers' IP interface addresses on the Point-
   to-MultiPoint network.  In the graphical representation of the link-
   state database, routers that can communicate directly over the
   Point-to-MultiPoint network are joined by bidirectional edges, and
   each router also has a stub connection to its own IP interface
   address (which is in contrast to the representation of real point-
   to-point links; see Figure 1a).

   On some non-broadcast networks, use of Point-to-MultiPoint mode and
   data-link protocols such as Inverse ARP (see [Ref14]) will allow
   autodiscovery of OSPF neighbors even though broadcast support is not
   available.

2.1.2.  An example link-state database

   Figure 2 shows a sample map of an Autonomous System.  The rectangle
   labelled H1 indicates a host, which has a SLIP connection to Router
   RT12. Router RT12 is therefore advertising a host route.  Lines
   between routers indicate physical point-to-point networks.  The only
   point-to-point network that has been assigned interface addresses is
   the one joining Routers RT6 and RT10.  Routers RT5 and RT7 have BGP
   connections to other Autonomous Systems.  A set of BGP-learned routes
   have been displayed for both of these routers.

   A cost is associated with the output side of each router interface.
   This cost is configurable by the system administrator.  The lower the
   cost,the more likely the interface is to be used to forward data
   traffic.  Costs are also associated with the externally derived
   routing data (e.g., the BGP-learned routes).

   The directed graph resulting from the map in Figure 2 is depicted in
   Figure 3.  Arcs are labelled with the cost of the corresponding
   router output interface. Arcs having no labelled cost have a cost of
   0.  Note that arcs leading from networks to routers always have cost
   0; they are significant nonetheless.  Note also that the externally
   derived routing data appears on the graph as stubs.

Top      ToC       Page 15 
                                                  **FROM**
                +---+      +---+
                |RT3|      |RT4|              |RT3|RT4|RT5|RT6|
                +---+      +---+        *  --------------------
                I3|    N2    |I4        *  RT3|   | X | X | X |
            +----------------------+    T  RT4| X |   |   | X |
                I5|          |I6        O  RT5| X |   |   | X |
                +---+      +---+        *  RT6| X | X | X |   |
                |RT5|      |RT6|        *   I3| X |   |   |   |
                +---+      +---+            I4|   | X |   |   |
                                            I5|   |   | X |   |
                                            I6|   |   |   | X |


                   Figure 1b: Network map components
                      Point-to-MultiPoint networks

          All routers can communicate directly over N2, except
             routers RT4 and RT5. I3 through I6 indicate IP
                          interface addresses

Top      ToC       Page 16 
                 +
                 | 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         |
                                |                  |          |
                           +---------+             |          |
                               N4                  |          |
                                                   |          |
                                                   |          |
                       N11                         |          |
                   +---------+                     |          |
                        |                          |          |    N12
                        |3                         |          |6 2/
                      +---+                        |        +---+/
                      |RT9|                        |        |RT7|---N15
                      +---+                        |        +---+ 9
                        |1                   +     |          |1
                       _|__                  |   Ib|5       __|_
                      /    \      1+----+2   |  3+----+1   /    \
                     *  N9  *------|RT11|----|---|RT10|---*  N6  *
                      \____/       +----+    |   +----+    \____/
                        |                    |                |
                        |1                   +                |1
             +--+   10+----+                N8              +---+
             |H1|-----|RT12|                                |RT8|
             +--+SLIP +----+                                +---+
                        |2                                    |4
                        |                                     |
                   +---------+                            +--------+
                       N10                                    N7

                  Figure 2: A sample Autonomous System

Top      ToC       Page 17 
                                **FROM**

                 |RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|
                 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12|N3|N6|N8|N9|
              ----- ---------------------------------------------
              RT1|  |  |  |  |  |  |  |  |  |  |  |  |0 |  |  |  |
              RT2|  |  |  |  |  |  |  |  |  |  |  |  |0 |  |  |  |
              RT3|  |  |  |  |  |6 |  |  |  |  |  |  |0 |  |  |  |
              RT4|  |  |  |  |8 |  |  |  |  |  |  |  |0 |  |  |  |
              RT5|  |  |  |8 |  |6 |6 |  |  |  |  |  |  |  |  |  |
              RT6|  |  |8 |  |7 |  |  |  |  |5 |  |  |  |  |  |  |
              RT7|  |  |  |  |6 |  |  |  |  |  |  |  |  |0 |  |  |
          *   RT8|  |  |  |  |  |  |  |  |  |  |  |  |  |0 |  |  |
          *   RT9|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |0 |
          T  RT10|  |  |  |  |  |7 |  |  |  |  |  |  |  |0 |0 |  |
          O  RT11|  |  |  |  |  |  |  |  |  |  |  |  |  |  |0 |0 |
          *  RT12|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |0 |
          *    N1|3 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
               N2|  |3 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
               N3|1 |1 |1 |1 |  |  |  |  |  |  |  |  |  |  |  |  |
               N4|  |  |2 |  |  |  |  |  |  |  |  |  |  |  |  |  |
               N6|  |  |  |  |  |  |1 |1 |  |1 |  |  |  |  |  |  |
               N7|  |  |  |  |  |  |  |4 |  |  |  |  |  |  |  |  |
               N8|  |  |  |  |  |  |  |  |  |3 |2 |  |  |  |  |  |
               N9|  |  |  |  |  |  |  |  |1 |  |1 |1 |  |  |  |  |
              N10|  |  |  |  |  |  |  |  |  |  |  |2 |  |  |  |  |
              N11|  |  |  |  |  |  |  |  |3 |  |  |  |  |  |  |  |
              N12|  |  |  |  |8 |  |2 |  |  |  |  |  |  |  |  |  |
              N13|  |  |  |  |8 |  |  |  |  |  |  |  |  |  |  |  |
              N14|  |  |  |  |8 |  |  |  |  |  |  |  |  |  |  |  |
              N15|  |  |  |  |  |  |9 |  |  |  |  |  |  |  |  |  |
               H1|  |  |  |  |  |  |  |  |  |  |  |10|  |  |  |  |


                 Figure 3: The resulting directed graph

           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 link-state database is pieced together from LSAs generated by the
   routers.  In the associated graphical representation, the
   neighborhood of each router or transit network is represented in a
   single, separate LSA.  Figure 4 shows these LSAs graphically. Router
   RT12 has an interface to two broadcast networks and a SLIP line to a
   host.  Network N6 is a broadcast network with three attached routers.
   The cost of all links from Network N6 to its attached routers is 0.

Top      ToC       Page 18 
   Note that the LSA for Network N6 is actually generated by one of the
   network's attached routers: the router that has been elected
   Designated Router for the network.

2.2.  The shortest-path tree

   When no OSPF areas are configured, each router in the Autonomous
   System has an identical link-state database, leading to an identical
   graphical representation.  A router generates its routing table from
   this graph by calculating a tree of shortest paths with the router
   itself as root.  Obviously, the shortest- path tree depends on the
   router doing the calculation.  The shortest-path tree for Router RT6
   in our example is depicted in Figure 5.

   The tree gives the entire path to any destination network or host.
   However, only the next hop to the destination is used in the
   forwarding process.   Note also that the best route to any router has
   also been calculated.  For the processing of external data, we note
   the next hop and distance to any router advertising external routes.
   The resulting routing table for Router RT6 is pictured in Table 2.
   Note that there is a separate route for each end of a numbered
   point-to-point network (in this case, the serial line between Routers
   RT6 and RT10).


                     **FROM**                       **FROM**

                  |RT12|N9|N10|H1|                 |RT9|RT11|RT12|N9|
           *  --------------------          *  ----------------------
           *  RT12|    |  |   |  |          *   RT9|   |    |    |0 |
           T    N9|1   |  |   |  |          T  RT11|   |    |    |0 |
           O   N10|2   |  |   |  |          O  RT12|   |    |    |0 |
           *    H1|10  |  |   |  |          *    N9|   |    |    |  |
           *                                *
                RT12's router-LSA              N9's network-LSA

               Figure 4: Individual link state components

           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       Page 19 
                                RT6(origin)
                    RT5 o------------o-----------o Ib
                       /|\    6      |\     7
                     8/8|8\          | \
                     /  |  \        6|  \
                    o   |   o        |   \7
                   N12  o  N14       |    \
                       N13        2  |     \
                            N4 o-----o RT3  \
                                    /        \    5
                                  1/     RT10 o-------o Ia
                                  /           |\
                       RT4 o-----o N3        3| \1
                                /|            |  \ N6     RT7
                               / |         N8 o   o---------o
                              /  |            |   |        /|
                         RT2 o   o RT1        |   |      2/ |9
                            /    |            |   |RT8   /  |
                           /3    |3      RT11 o   o     o   o
                          /      |            |   |    N12 N15
                      N2 o       o N1        1|   |4
                                              |   |
                                           N9 o   o N7
                                             /|
                                            / |
                        N11      RT9       /  |RT12
                         o--------o-------o   o--------o H1
                             3                |   10
                                              |2
                                              |
                                              o N10


                 Figure 5: The SPF tree for Router RT6

  Edges that are not marked with a cost have a cost of of zero (these
 are network-to-router links). Routes to networks N12-N15 are external
             information that is considered in Section 2.3

Top      ToC       Page 20 
           Destination   Next  Hop   Distance
           __________________________________
           N1            RT3         10
           N2            RT3         10
           N3            RT3         7
           N4            RT3         8
           Ib            *           7
           Ia            RT10        12
           N6            RT10        8
           N7            RT10        12
           N8            RT10        10
           N9            RT10        11
           N10           RT10        13
           N11           RT10        14
           H1            RT10        21
           __________________________________
           RT5           RT5         6
           RT7           RT10        8

    Table 2: The portion of Router RT6's routing table listing local
                             destinations.

   Routes to networks belonging to other AS'es (such as N12) appear as
   dashed lines on the shortest path tree in Figure 5.  Use of this
   externally derived routing information is considered in the next
   section.

2.3.  Use of external routing information

   After the tree is created the external routing information is
   examined.  This external routing information may originate from
   another routing protocol such as BGP, or be statically configured
   (static routes).  Default routes can also be included as part of the
   Autonomous System's external routing information.

   External routing information is flooded unaltered throughout the AS.
   In our example, all the routers in the Autonomous System know that
   Router RT7 has two external routes, with metrics 2 and 9.

   OSPF supports two types of external metrics.  Type 1 external metrics
   are expressed in the same units as OSPF interface cost (i.e., in
   terms of the link state metric).  Type 2 external metrics are an
   order of magnitude larger; any Type 2 metric is considered greater
   than the cost of any path internal to the AS.  Use of Type 2 external
   metrics assumes that routing between AS'es is the major cost of
   routing a packet, and eliminates the need for conversion of external
   costs to internal link state metrics.

Top      ToC       Page 21 
   As an example of Type 1 external metric processing, suppose that the
   Routers RT7 and RT5 in Figure 2 are advertising Type 1 external
   metrics.  For each advertised external route, the total cost from
   Router RT6 is calculated as the sum of the external route's
   advertised cost and the distance from Router RT6 to the advertising
   router.  When two routers are advertising the same external
   destination, RT6 picks the advertising router providing the minimum
   total cost. RT6 then sets the next hop to the external destination
   equal to the next hop that would be used when routing packets to the
   chosen advertising router.

   In Figure 2, both Router RT5 and RT7 are advertising an external
   route to destination Network N12.  Router RT7 is preferred since it
   is advertising N12 at a distance of 10 (8+2) to Router RT6, which is
   better than Router RT5's 14 (6+8).  Table 3 shows the entries that
   are added to the routing table when external routes are examined:



                 Destination   Next  Hop   Distance
                 __________________________________
                 N12           RT10        10
                 N13           RT5         14
                 N14           RT5         14
                 N15           RT10        17


          Table 3: The portion of Router RT6's routing table
                     listing external destinations.

   Processing of Type 2 external metrics is simpler.  The AS boundary
   router advertising the smallest external metric is chosen, regardless
   of the internal distance to the AS boundary router.  Suppose in our
   example both Router RT5 and Router RT7 were advertising Type 2
   external routes.  Then all traffic destined for Network N12 would be
   forwarded to Router RT7, since 2 < 8. When several equal-cost Type 2
   routes exist, the internal distance to the advertising routers is
   used to break the tie.

   Both Type 1 and Type 2 external metrics can be present in the AS at
   the same time.  In that event, Type 1 external metrics always take
   precedence.

   This section has assumed that packets destined for external
   destinations are always routed through the advertising AS boundary
   router.  This is not always desirable.  For example, suppose in
   Figure 2 there is an additional router attached to Network N6, called
   Router RTX. Suppose further that RTX does not participate in OSPF

Top      ToC       Page 22 
   routing, but does exchange BGP information with the AS boundary
   router RT7.  Then, Router RT7 would end up advertising OSPF external
   routes for all destinations that should be routed to RTX.  An extra
   hop will sometimes be introduced if packets for these destinations
   need always be routed first to Router RT7 (the advertising router).

   To deal with this situation, the OSPF protocol allows an AS boundary
   router to specify a "forwarding address" in its AS- external-LSAs. In
   the above example, Router RT7 would specify RTX's IP address as the
   "forwarding address" for all those destinations whose packets should
   be routed directly to RTX.

   The "forwarding address" has one other application.  It enables
   routers in the Autonomous System's interior to function as "route
   servers".  For example, in Figure 2 the router RT6 could become a
   route server, gaining external routing information through a
   combination of static configuration and external routing protocols.
   RT6 would then start advertising itself as an AS boundary router, and
   would originate a collection of OSPF AS-external-LSAs.  In each AS-
   external-LSA, Router RT6 would specify the correct Autonomous System
   exit point to use for the destination through appropriate setting of
   the LSA's "forwarding address" field.

2.4.  Equal-cost multipath

   The above discussion has been simplified by considering only a single
   route to any destination.  In reality, if multiple equal-cost routes
   to a destination exist, they are all discovered and used.  This
   requires no conceptual changes to the algorithm, and its discussion
   is postponed until we consider the tree-building process in more
   detail.

   With equal cost multipath, a router potentially has several available
   next hops towards any given destination.



(page 22 continued on part 2)

Next RFC Part