Network Working Group J. Moy
`Request for Comments: 2328 Ascend Communications, Inc.
`STD: 54 April 1998
`Obsoletes: 2178
`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.
`
`Copyright Notice
`
` Copyright (C) The Internet Society (1998). All Rights Reserved.
`
`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 2178 are explained in
` Appendix G. All differences are backward-compatible in nature.
`
`Moy Standards Track [Page 1]
`
`Petitioner RPX Corporation - Ex. 1064, p. 1
`
`

`

`
`RFC 2328 OSPF Version 2 April 1998
`
` Implementations of this memo and of RFCs 2178, 1583, and 1247 will
` interoperate.
`
` Please send comments to ospf@gated.cornell.edu.
`
`Table of Contents
`
` 1 Introduction ........................................... 6
` 1.1 Protocol Overview ...................................... 6
` 1.2 Definitions of commonly used terms ..................... 8
` 1.3 Brief history of link-state routing technology ........ 11
` 1.4 Organization of this document ......................... 12
` 1.5 Acknowledgments ....................................... 12
` 2 The link-state database: organization and calculations 13
` 2.1 Representation of routers and networks ................ 13
` 2.1.1 Representation of non-broadcast networks .............. 15
` 2.1.2 An example link-state database ........................ 18
` 2.2 The shortest-path tree ................................ 21
` 2.3 Use of external routing information ................... 23
` 2.4 Equal-cost multipath .................................. 26
` 3 Splitting the AS into Areas ........................... 26
` 3.1 The backbone of the Autonomous System ................. 27
` 3.2 Inter-area routing .................................... 27
` 3.3 Classification of routers ............................. 28
` 3.4 A sample area configuration ........................... 29
` 3.5 IP subnetting support ................................. 35
` 3.6 Supporting stub areas ................................. 37
` 3.7 Partitions of areas ................................... 38
` 4 Functional Summary .................................... 40
` 4.1 Inter-area routing .................................... 41
` 4.2 AS external routes .................................... 41
` 4.3 Routing protocol packets .............................. 42
` 4.4 Basic implementation requirements ..................... 43
` 4.5 Optional OSPF capabilities ............................ 46
` 5 Protocol data structures .............................. 47
` 6 The Area Data Structure ............................... 49
` 7 Bringing Up Adjacencies ............................... 52
` 7.1 The Hello Protocol .................................... 52
` 7.2 The Synchronization of Databases ...................... 53
` 7.3 The Designated Router ................................. 54
` 7.4 The Backup Designated Router .......................... 56
` 7.5 The graph of adjacencies .............................. 56
`
`Moy Standards Track [Page 2]
`
`Petitioner RPX Corporation - Ex. 1064, p. 2
`
`

`

`
`RFC 2328 OSPF Version 2 April 1998
`
` 8 Protocol Packet Processing ............................ 58
` 8.1 Sending protocol packets .............................. 58
` 8.2 Receiving protocol packets ............................ 61
` 9 The Interface Data Structure .......................... 63
` 9.1 Interface states ...................................... 67
` 9.2 Events causing interface state changes ................ 70
` 9.3 The Interface state machine ........................... 72
` 9.4 Electing the Designated Router ........................ 75
` 9.5 Sending Hello packets ................................. 77
` 9.5.1 Sending Hello packets on NBMA networks ................ 79
` 10 The Neighbor Data Structure ........................... 80
` 10.1 Neighbor states ....................................... 83
` 10.2 Events causing neighbor state changes ................. 87
` 10.3 The Neighbor state machine ............................ 89
` 10.4 Whether to become adjacent ............................ 95
` 10.5 Receiving Hello Packets ............................... 96
` 10.6 Receiving Database Description Packets ................ 99
` 10.7 Receiving Link State Request Packets ................. 102
` 10.8 Sending Database Description Packets ................. 103
` 10.9 Sending Link State Request Packets ................... 104
` 10.10 An Example ........................................... 105
` 11 The Routing Table Structure .......................... 107
` 11.1 Routing table lookup ................................. 111
` 11.2 Sample routing table, without areas .................. 111
` 11.3 Sample routing table, with areas ..................... 112
` 12 Link State Advertisements (LSAs) ..................... 115
` 12.1 The LSA Header ....................................... 116
` 12.1.1 LS age ............................................... 116
` 12.1.2 Options .............................................. 117
` 12.1.3 LS type .............................................. 117
` 12.1.4 Link State ID ........................................ 117
` 12.1.5 Advertising Router ................................... 119
` 12.1.6 LS sequence number ................................... 120
` 12.1.7 LS checksum .......................................... 121
` 12.2 The link state database .............................. 121
` 12.3 Representation of TOS ................................ 122
` 12.4 Originating LSAs ..................................... 123
` 12.4.1 Router-LSAs .......................................... 126
` 12.4.1.1 Describing point-to-point interfaces ................. 130
` 12.4.1.2 Describing broadcast and NBMA interfaces ............. 130
` 12.4.1.3 Describing virtual links ............................. 131
` 12.4.1.4 Describing Point-to-MultiPoint interfaces ............ 131
`
`Moy Standards Track [Page 3]
`
`Petitioner RPX Corporation - Ex. 1064, p. 3
`
`

`

`
`RFC 2328 OSPF Version 2 April 1998
`
` 12.4.1.5 Examples of router-LSAs .............................. 132
` 12.4.2 Network-LSAs ......................................... 133
` 12.4.2.1 Examples of network-LSAs ............................. 134
` 12.4.3 Summary-LSAs ......................................... 135
` 12.4.3.1 Originating summary-LSAs into stub areas ............. 137
` 12.4.3.2 Examples of summary-LSAs ............................. 138
` 12.4.4 AS-external-LSAs ..................................... 139
` 12.4.4.1 Examples of AS-external-LSAs ......................... 140
` 13 The Flooding Procedure ............................... 143
` 13.1 Determining which LSA is newer ....................... 146
` 13.2 Installing LSAs in the database ...................... 147
` 13.3 Next step in the flooding procedure .................. 148
` 13.4 Receiving self-originated LSAs ....................... 151
` 13.5 Sending Link State Acknowledgment packets ............ 152
` 13.6 Retransmitting LSAs .................................. 154
` 13.7 Receiving link state acknowledgments ................. 155
` 14 Aging The Link State Database ........................ 156
` 14.1 Premature aging of LSAs .............................. 157
` 15 Virtual Links ........................................ 158
` 16 Calculation of the routing table ..................... 160
` 16.1 Calculating the shortest-path tree for an area ....... 161
` 16.1.1 The next hop calculation ............................. 167
` 16.2 Calculating the inter-area routes .................... 178
` 16.3 Examining transit areas’ summary-LSAs ................ 170
` 16.4 Calculating AS external routes ....................... 173
` 16.4.1 External path preferences ............................ 175
` 16.5 Incremental updates -- summary-LSAs .................. 175
` 16.6 Incremental updates -- AS-external-LSAs .............. 177
` 16.7 Events generated as a result of routing table changes 177
` 16.8 Equal-cost multipath ................................. 178
` Footnotes ............................................ 179
` References ........................................... 183
` A OSPF data formats .................................... 185
` A.1 Encapsulation of OSPF packets ........................ 185
` A.2 The Options field .................................... 187
` A.3 OSPF Packet Formats .................................. 189
` A.3.1 The OSPF packet header ............................... 190
` A.3.2 The Hello packet ..................................... 193
` A.3.3 The Database Description packet ...................... 195
` A.3.4 The Link State Request packet ........................ 197
` A.3.5 The Link State Update packet ......................... 199
` A.3.6 The Link State Acknowledgment packet ................. 201
`
`Moy Standards Track [Page 4]
`
`Petitioner RPX Corporation - Ex. 1064, p. 4
`
`

`

`
`RFC 2328 OSPF Version 2 April 1998
`
` A.4 LSA formats .......................................... 203
` A.4.1 The LSA header ....................................... 204
` A.4.2 Router-LSAs .......................................... 206
` A.4.3 Network-LSAs ......................................... 210
` A.4.4 Summary-LSAs ......................................... 212
` A.4.5 AS-external-LSAs ..................................... 214
` B Architectural Constants .............................. 217
` C Configurable Constants ............................... 219
` C.1 Global parameters .................................... 219
` C.2 Area parameters ...................................... 220
` C.3 Router interface parameters .......................... 221
` C.4 Virtual link parameters .............................. 224
` C.5 NBMA network parameters .............................. 224
` C.6 Point-to-MultiPoint network parameters ............... 225
` C.7 Host route parameters ................................ 226
` D Authentication ....................................... 227
` D.1 Null authentication .................................. 227
` D.2 Simple password authentication ....................... 228
` D.3 Cryptographic authentication ......................... 228
` D.4 Message generation ................................... 231
` D.4.1 Generating Null authentication ....................... 231
` D.4.2 Generating Simple password authentication ............ 232
` D.4.3 Generating Cryptographic authentication .............. 232
` D.5 Message verification ................................. 234
` D.5.1 Verifying Null authentication ........................ 234
` D.5.2 Verifying Simple password authentication ............. 234
` D.5.3 Verifying Cryptographic authentication ............... 235
` E An algorithm for assigning Link State IDs ............ 236
` F Multiple interfaces to the same network/subnet ....... 239
` G Differences from RFC 2178 ............................ 240
` G.1 Flooding modifications ............................... 240
` G.2 Changes to external path preferences ................. 241
` G.3 Incomplete resolution of virtual next hops ........... 241
` G.4 Routing table lookup ................................. 241
` Security Considerations .............................. 243
` Author’s Address ..................................... 243
` Full Copyright Statement ............................. 244
`
`Moy Standards Track [Page 5]
`
`Petitioner RPX Corporation - Ex. 1064, p. 5
`
`

`

`
`RFC 2328 OSPF Version 2 April 1998
`
`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.
`
`Moy Standards Track [Page 6]
`
`Petitioner RPX Corporation - Ex. 1064, p. 6
`
`

`

`
`RFC 2328 OSPF Version 2 April 1998
`
` 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.
`
`Moy Standards Track [Page 7]
`
`Petitioner RPX Corporation - Ex. 1064, p. 7
`
`

`

`
`RFC 2328 OSPF Version 2 April 1998
`
` 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.
`
` 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.
`
`Moy Standards Track [Page 8]
`
`Petitioner RPX Corporation - Ex. 1064, p. 8
`
`

`

`
`RFC 2328 OSPF Version 2 April 1998
`
` 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.
`
` 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.
`
`Moy Standards Track [Page 9]
`
`Petitioner RPX Corporation - Ex. 1064, p. 9
`
`

`

`
`RFC 2328 OSPF Version 2 April 1998
`
` 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.
`
` 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
`
`Moy Standards Track [Page 10]
`
`Petitioner RPX Corporation - Ex. 1064, p. 10
`
`

`

`
`RFC 2328 OSPF Version 2 April 1998
`
` 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 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.
`
`Moy Standards Track [Page 11]
`
`Petitioner RPX Corporation - Ex. 1064, p. 11
`
`

`

`
`RFC 2328 OSPF Version 2 April 1998
`
` 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.
`
` 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
`
`Moy Standards Track [Page 12]
`
`Petitioner RPX Corporation - Ex. 1064, p. 12
`
`

`

`
`RFC 2328 OSPF Version 2 April 1998
`
` 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.
`
`Moy Standards Track [Page 13]
`
`Petitioner RPX Corporation - Ex. 1064, p. 13
`
`

`

`
`RFC 2328 OSPF Version 2 April 1998
`
` **FROM**
`
` * |RT1|RT2|
`