draft-ietf-ospf-vers2-02.txt   rfc2328.txt 
Network Working Group J. Moy Network Working Group J. Moy
Internet Draft Ascend Communications, Inc. Request for Comments: 2328 Ascend Communications, Inc.
Expiration Date: July 1998 January 1998 STD: 54 April 1998
File name: draft-ietf-ospf-vers2-02.txt Obsoletes: 2178
Category: Standards Track
OSPF Version 2 OSPF Version 2
Status of this Memo Status of this Memo
This document is an Internet-Draft. Internet-Drafts are working This document specifies an Internet standards track protocol for the
documents of the Internet Engineering Task Force (IETF), its areas, Internet community, and requests discussion and suggestions for
and its working groups. Note that other groups may also distribute improvements. Please refer to the current edition of the "Internet
working documents as Internet-Drafts. Official Protocol Standards" (STD 1) for the standardization state
and status of this protocol. Distribution of this memo is
unlimited.
Internet-Drafts are draft documents valid for a maximum of six Copyright Notice
months and may be updated, replaced, or obsoleted by other documents
at any time. It is inappropriate to use Internet- Drafts as
reference material or to cite them other than as "work in progress".
To learn the current status of any Internet-Draft, please check the Copyright (C) The Internet Society (1998). All Rights Reserved.
"1id-abstracts.txt" listing contained in the Internet- Drafts Shadow
Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
ftp.isi.edu (US West Coast).
Abstract Abstract
This memo documents version 2 of the OSPF protocol. OSPF is a 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 link-state routing protocol. It is designed to be run internal to a
single Autonomous System. Each OSPF router maintains an identical single Autonomous System. Each OSPF router maintains an identical
database describing the Autonomous System's topology. From this database describing the Autonomous System's topology. From this
database, a routing table is calculated by constructing a shortest- database, a routing table is calculated by constructing a shortest-
path tree. path tree.
OSPF recalculates routes quickly in the face of topological changes, OSPF recalculates routes quickly in the face of topological changes,
utilizing a minimum of routing protocol traffic. OSPF provides utilizing a minimum of routing protocol traffic. OSPF provides
support for equal-cost multipath. An area routing capability is support for equal-cost multipath. An area routing capability is
provided, enabling an additional level of routing protection and a provided, enabling an additional level of routing protection and a
reduction in routing protocol traffic. In addition, all OSPF reduction in routing protocol traffic. In addition, all OSPF
routing protocol exchanges are authenticated. routing protocol exchanges are authenticated.
The differences between this memo and RFC 2178 are explained in The differences between this memo and RFC 2178 are explained in
Appendix G. All differences are backward-compatible in nature. Appendix G. All differences are backward-compatible in nature.
Implementations of this memo and of RFCs 2178, 1583, and 1247 will
Implementations of this memo and of RFCs 2178, 1583, and 1247 will
interoperate. interoperate.
Please send comments to ospf@gated.cornell.edu. Please send comments to ospf@gated.cornell.edu.
Table of Contents Table of Contents
1 Introduction ........................................... 7 1 Introduction ........................................... 6
1.1 Protocol Overview ...................................... 7 1.1 Protocol Overview ...................................... 6
1.2 Definitions of commonly used terms ..................... 8 1.2 Definitions of commonly used terms ..................... 8
1.3 Brief history of link-state routing technology ........ 11 1.3 Brief history of link-state routing technology ........ 11
1.4 Organization of this document ......................... 12 1.4 Organization of this document ......................... 12
1.5 Acknowledgments ....................................... 13 1.5 Acknowledgments ....................................... 12
2 The link-state database: organization and calculations 13 2 The link-state database: organization and calculations 13
2.1 Representation of routers and networks ................ 13 2.1 Representation of routers and networks ................ 13
2.1.1 Representation of non-broadcast networks .............. 15 2.1.1 Representation of non-broadcast networks .............. 15
2.1.2 An example link-state database ........................ 16 2.1.2 An example link-state database ........................ 18
2.2 The shortest-path tree ................................ 20 2.2 The shortest-path tree ................................ 21
2.3 Use of external routing information ................... 22 2.3 Use of external routing information ................... 23
2.4 Equal-cost multipath .................................. 24 2.4 Equal-cost multipath .................................. 26
3 Splitting the AS into Areas ........................... 25 3 Splitting the AS into Areas ........................... 26
3.1 The backbone of the Autonomous System ................. 25 3.1 The backbone of the Autonomous System ................. 27
3.2 Inter-area routing .................................... 26 3.2 Inter-area routing .................................... 27
3.3 Classification of routers ............................. 26 3.3 Classification of routers ............................. 28
3.4 A sample area configuration ........................... 27 3.4 A sample area configuration ........................... 29
3.5 IP subnetting support ................................. 33 3.5 IP subnetting support ................................. 35
3.6 Supporting stub areas ................................. 34 3.6 Supporting stub areas ................................. 37
3.7 Partitions of areas ................................... 35 3.7 Partitions of areas ................................... 38
4 Functional Summary .................................... 37 4 Functional Summary .................................... 40
4.1 Inter-area routing .................................... 37 4.1 Inter-area routing .................................... 41
4.2 AS external routes .................................... 38 4.2 AS external routes .................................... 41
4.3 Routing protocol packets .............................. 38 4.3 Routing protocol packets .............................. 42
4.4 Basic implementation requirements ..................... 41 4.4 Basic implementation requirements ..................... 43
4.5 Optional OSPF capabilities ............................ 42 4.5 Optional OSPF capabilities ............................ 46
5 Protocol data structures .............................. 43 5 Protocol data structures .............................. 47
6 The Area Data Structure ............................... 46 6 The Area Data Structure ............................... 49
7 Bringing Up Adjacencies ............................... 47 7 Bringing Up Adjacencies ............................... 52
7.1 The Hello Protocol .................................... 48 7.1 The Hello Protocol .................................... 52
7.2 The Synchronization of Databases ...................... 48 7.2 The Synchronization of Databases ...................... 53
7.3 The Designated Router ................................. 49 7.3 The Designated Router ................................. 54
7.4 The Backup Designated Router .......................... 51 7.4 The Backup Designated Router .......................... 56
7.5 The graph of adjacencies .............................. 51 7.5 The graph of adjacencies .............................. 56
8 Protocol Packet Processing ............................ 53 8 Protocol Packet Processing ............................ 58
8.1 Sending protocol packets .............................. 53 8.1 Sending protocol packets .............................. 58
8.2 Receiving protocol packets ............................ 55 8.2 Receiving protocol packets ............................ 61
9 The Interface Data Structure .......................... 57 9 The Interface Data Structure .......................... 63
9.1 Interface states ...................................... 60 9.1 Interface states ...................................... 67
9.2 Events causing interface state changes ................ 63 9.2 Events causing interface state changes ................ 70
9.3 The Interface state machine ........................... 65 9.3 The Interface state machine ........................... 72
9.4 Electing the Designated Router ........................ 67 9.4 Electing the Designated Router ........................ 75
9.5 Sending Hello packets ................................. 70 9.5 Sending Hello packets ................................. 77
9.5.1 Sending Hello packets on NBMA networks ................ 71 9.5.1 Sending Hello packets on NBMA networks ................ 79
10 The Neighbor Data Structure ........................... 72 10 The Neighbor Data Structure ........................... 80
10.1 Neighbor states ....................................... 74 10.1 Neighbor states ....................................... 83
10.2 Events causing neighbor state changes ................. 78 10.2 Events causing neighbor state changes ................. 87
10.3 The Neighbor state machine ............................ 80 10.3 The Neighbor state machine ............................ 89
10.4 Whether to become adjacent ............................ 85 10.4 Whether to become adjacent ............................ 95
10.5 Receiving Hello Packets ............................... 86 10.5 Receiving Hello Packets ............................... 96
10.6 Receiving Database Description Packets ................ 88 10.6 Receiving Database Description Packets ................ 99
10.7 Receiving Link State Request Packets .................. 92 10.7 Receiving Link State Request Packets ................. 102
10.8 Sending Database Description Packets .................. 92 10.8 Sending Database Description Packets ................. 103
10.9 Sending Link State Request Packets .................... 93 10.9 Sending Link State Request Packets ................... 104
10.10 An Example ............................................ 94 10.10 An Example ........................................... 105
11 The Routing Table Structure ........................... 96 11 The Routing Table Structure .......................... 107
11.1 Routing table lookup .................................. 99 11.1 Routing table lookup ................................. 111
11.2 Sample routing table, without areas .................. 100 11.2 Sample routing table, without areas .................. 111
11.3 Sample routing table, with areas ..................... 100 11.3 Sample routing table, with areas ..................... 112
12 Link State Advertisements (LSAs) ..................... 102 12 Link State Advertisements (LSAs) ..................... 115
12.1 The LSA Header ....................................... 103 12.1 The LSA Header ....................................... 116
12.1.1 LS age ............................................... 104 12.1.1 LS age ............................................... 116
12.1.2 Options .............................................. 104 12.1.2 Options .............................................. 117
12.1.3 LS type .............................................. 105 12.1.3 LS type .............................................. 117
12.1.4 Link State ID ........................................ 106 12.1.4 Link State ID ........................................ 117
12.1.5 Advertising Router ................................... 107 12.1.5 Advertising Router ................................... 119
12.1.6 LS sequence number ................................... 107 12.1.6 LS sequence number ................................... 120
12.1.7 LS checksum .......................................... 108 12.1.7 LS checksum .......................................... 121
12.2 The link state database .............................. 108 12.2 The link state database .............................. 121
12.3 Representation of TOS ................................ 109 12.3 Representation of TOS ................................ 122
12.4 Originating LSAs ..................................... 110 12.4 Originating LSAs ..................................... 123
12.4.1 Router-LSAs .......................................... 113 12.4.1 Router-LSAs .......................................... 126
12.4.1.1 Describing point-to-point interfaces ................. 116 12.4.1.1 Describing point-to-point interfaces ................. 130
12.4.1.2 Describing broadcast and NBMA interfaces ............. 117 12.4.1.2 Describing broadcast and NBMA interfaces ............. 130
12.4.1.3 Describing virtual links ............................. 117 12.4.1.3 Describing virtual links ............................. 131
12.4.1.4 Describing Point-to-MultiPoint interfaces ............ 118 12.4.1.4 Describing Point-to-MultiPoint interfaces ............ 131
12.4.1.5 Examples of router-LSAs .............................. 118 12.4.1.5 Examples of router-LSAs .............................. 132
12.4.2 Network-LSAs ......................................... 119 12.4.2 Network-LSAs ......................................... 133
12.4.2.1 Examples of network-LSAs ............................. 120 12.4.2.1 Examples of network-LSAs ............................. 134
12.4.3 Summary-LSAs ......................................... 121 12.4.3 Summary-LSAs ......................................... 135
12.4.3.1 Originating summary-LSAs into stub areas ............. 123 12.4.3.1 Originating summary-LSAs into stub areas ............. 137
12.4.3.2 Examples of summary-LSAs ............................. 124 12.4.3.2 Examples of summary-LSAs ............................. 138
12.4.4 AS-external-LSAs ..................................... 124 12.4.4 AS-external-LSAs ..................................... 139
12.4.4.1 Examples of AS-external-LSAs ......................... 125 12.4.4.1 Examples of AS-external-LSAs ......................... 140
13 The Flooding Procedure ............................... 127 13 The Flooding Procedure ............................... 143
13.1 Determining which LSA is newer ....................... 130 13.1 Determining which LSA is newer ....................... 146
13.2 Installing LSAs in the database ...................... 131 13.2 Installing LSAs in the database ...................... 147
13.3 Next step in the flooding procedure .................. 132 13.3 Next step in the flooding procedure .................. 148
13.4 Receiving self-originated LSAs ....................... 135 13.4 Receiving self-originated LSAs ....................... 151
13.5 Sending Link State Acknowledgment packets ............ 135 13.5 Sending Link State Acknowledgment packets ............ 152
13.6 Retransmitting LSAs .................................. 138 13.6 Retransmitting LSAs .................................. 154
13.7 Receiving link state acknowledgments ................. 138 13.7 Receiving link state acknowledgments ................. 155
14 Aging The Link State Database ........................ 139 14 Aging The Link State Database ........................ 156
14.1 Premature aging of LSAs .............................. 140 14.1 Premature aging of LSAs .............................. 157
15 Virtual Links ........................................ 140 15 Virtual Links ........................................ 158
16 Calculation of the routing table ..................... 142 16 Calculation of the routing table ..................... 160
16.1 Calculating the shortest-path tree for an area ....... 143 16.1 Calculating the shortest-path tree for an area ....... 161
16.1.1 The next hop calculation ............................. 149 16.1.1 The next hop calculation ............................. 167
16.2 Calculating the inter-area routes .................... 150 16.2 Calculating the inter-area routes .................... 178
16.3 Examining transit areas' summary-LSAs ................ 151 16.3 Examining transit areas' summary-LSAs ................ 170
16.4 Calculating AS external routes ....................... 154 16.4 Calculating AS external routes ....................... 173
16.4.1 External path preferences ............................ 156 16.4.1 External path preferences ............................ 175
16.5 Incremental updates -- summary-LSAs .................. 156 16.5 Incremental updates -- summary-LSAs .................. 175
16.6 Incremental updates -- AS-external-LSAs .............. 157 16.6 Incremental updates -- AS-external-LSAs .............. 177
16.7 Events generated as a result of routing table changes 158 16.7 Events generated as a result of routing table changes 177
16.8 Equal-cost multipath ................................. 159 16.8 Equal-cost multipath ................................. 178
Footnotes ............................................ 160 Footnotes ............................................ 179
References ........................................... 163 References ........................................... 183
A OSPF data formats .................................... 165 A OSPF data formats .................................... 185
A.1 Encapsulation of OSPF packets ........................ 165 A.1 Encapsulation of OSPF packets ........................ 185
A.2 The Options field .................................... 167 A.2 The Options field .................................... 187
A.3 OSPF Packet Formats .................................. 169 A.3 OSPF Packet Formats .................................. 189
A.3.1 The OSPF packet header ............................... 170 A.3.1 The OSPF packet header ............................... 190
A.3.2 The Hello packet ..................................... 172 A.3.2 The Hello packet ..................................... 193
A.3.3 The Database Description packet ...................... 174 A.3.3 The Database Description packet ...................... 195
A.3.4 The Link State Request packet ........................ 176 A.3.4 The Link State Request packet ........................ 197
A.3.5 The Link State Update packet ......................... 178 A.3.5 The Link State Update packet ......................... 199
A.3.6 The Link State Acknowledgment packet ................. 180 A.3.6 The Link State Acknowledgment packet ................. 201
A.4 LSA formats .......................................... 182 A.4 LSA formats .......................................... 203
A.4.1 The LSA header ....................................... 183 A.4.1 The LSA header ....................................... 204
A.4.2 Router-LSAs .......................................... 185 A.4.2 Router-LSAs .......................................... 206
A.4.3 Network-LSAs ......................................... 188 A.4.3 Network-LSAs ......................................... 210
A.4.4 Summary-LSAs ......................................... 189 A.4.4 Summary-LSAs ......................................... 212
A.4.5 AS-external-LSAs ..................................... 191 A.4.5 AS-external-LSAs ..................................... 214
B Architectural Constants .............................. 193 B Architectural Constants .............................. 217
C Configurable Constants ............................... 195 C Configurable Constants ............................... 219
C.1 Global parameters .................................... 195 C.1 Global parameters .................................... 219
C.2 Area parameters ...................................... 196 C.2 Area parameters ...................................... 220
C.3 Router interface parameters .......................... 197 C.3 Router interface parameters .......................... 221
C.4 Virtual link parameters .............................. 199 C.4 Virtual link parameters .............................. 224
C.5 NBMA network parameters .............................. 200 C.5 NBMA network parameters .............................. 224
C.6 Point-to-MultiPoint network parameters ............... 200 C.6 Point-to-MultiPoint network parameters ............... 225
C.7 Host route parameters ................................ 201 C.7 Host route parameters ................................ 226
D Authentication ....................................... 202 D Authentication ....................................... 227
D.1 Null authentication .................................. 202 D.1 Null authentication .................................. 227
D.2 Simple password authentication ....................... 202 D.2 Simple password authentication ....................... 228
D.3 Cryptographic authentication ......................... 203 D.3 Cryptographic authentication ......................... 228
D.4 Message generation ................................... 205 D.4 Message generation ................................... 231
D.4.1 Generating Null authentication ....................... 206 D.4.1 Generating Null authentication ....................... 231
D.4.2 Generating Simple password authentication ............ 206 D.4.2 Generating Simple password authentication ............ 232
D.4.3 Generating Cryptographic authentication .............. 206 D.4.3 Generating Cryptographic authentication .............. 232
D.5 Message verification ................................. 208 D.5 Message verification ................................. 234
D.5.1 Verifying Null authentication ........................ 208 D.5.1 Verifying Null authentication ........................ 234
D.5.2 Verifying Simple password authentication ............. 208 D.5.2 Verifying Simple password authentication ............. 234
D.5.3 Verifying Cryptographic authentication ............... 208 D.5.3 Verifying Cryptographic authentication ............... 235
E An algorithm for assigning Link State IDs ............ 210 E An algorithm for assigning Link State IDs ............ 236
F Multiple interfaces to the same network/subnet ....... 212 F Multiple interfaces to the same network/subnet ....... 239
G Differences from RFC 2178 ............................ 213 G Differences from RFC 2178 ............................ 240
G.1 Flooding modifications ............................... 213 G.1 Flooding modifications ............................... 240
G.2 Changes to external path preferences ................. 213 G.2 Changes to external path preferences ................. 241
G.3 Incomplete resolution of virtual next hops ........... 214 G.3 Incomplete resolution of virtual next hops ........... 241
G.4 Routing table lookup ................................. 214 G.4 Routing table lookup ................................. 241
Security Considerations .............................. 215 Security Considerations .............................. 243
Author's Address ..................................... 215 Author's Address ..................................... 243
Full Copyright Statement ............................. 244
1. Introduction 1. Introduction
This document is a specification of the Open Shortest Path First This document is a specification of the Open Shortest Path First
(OSPF) TCP/IP internet routing protocol. OSPF is classified as an (OSPF) TCP/IP internet routing protocol. OSPF is classified as an
Interior Gateway Protocol (IGP). This means that it distributes Interior Gateway Protocol (IGP). This means that it distributes
routing information between routers belonging to a single Autonomous routing information between routers belonging to a single Autonomous
System. The OSPF protocol is based on link-state or SPF technology. System. The OSPF protocol is based on link-state or SPF technology.
This is a departure from the Bellman-Ford base used by traditional This is a departure from the Bellman-Ford base used by traditional
TCP/IP internet routing protocols. TCP/IP internet routing protocols.
The OSPF protocol was developed by the OSPF working group of the The OSPF protocol was developed by the OSPF working group of the
Internet Engineering Task Force. It has been designed expressly for Internet Engineering Task Force. It has been designed expressly for
the TCP/IP internet environment, including explicit support for CIDR the TCP/IP internet environment, including explicit support for CIDR
and the tagging of externally-derived routing information. OSPF and the tagging of externally-derived routing information. OSPF
also provides for the authentication of routing updates, and also provides for the authentication of routing updates, and
utilizes IP multicast when sending/receiving the updates. In utilizes IP multicast when sending/receiving the updates. In
addition, much work has been done to produce a protocol that addition, much work has been done to produce a protocol that
responds quickly to topology changes, yet involves small amounts of responds quickly to topology changes, yet involves small amounts of
routing protocol traffic. routing protocol traffic.
1.1. Protocol overview 1.1. Protocol overview
OSPF routes IP packets based solely on the destination IP OSPF routes IP packets based solely on the destination IP
address found in the IP packet header. IP packets are routed address found in the IP packet header. IP packets are routed
"as is" -- they are not encapsulated in any further protocol "as is" -- they are not encapsulated in any further protocol
headers as they transit the Autonomous System. OSPF is a headers as they transit the Autonomous System. OSPF is a
dynamic routing protocol. It quickly detects topological dynamic routing protocol. It quickly detects topological
changes in the AS (such as router interface failures) and changes in the AS (such as router interface failures) and
calculates new loop-free routes after a period of convergence. calculates new loop-free routes after a period of convergence.
This period of convergence is short and involves a minimum of This period of convergence is short and involves a minimum of
routing traffic. routing traffic.
In a link-state routing protocol, each router maintains a In a link-state routing protocol, each router maintains a
database describing the Autonomous System's topology. This database describing the Autonomous System's topology. This
database is referred to as the link-state database. Each database is referred to as the link-state database. Each
participating router has an identical database. Each individual participating router has an identical database. Each individual
piece of this database is a particular router's local state piece of this database is a particular router's local state
(e.g., the router's usable interfaces and reachable neighbors). (e.g., the router's usable interfaces and reachable neighbors).
The router distributes its local state throughout the Autonomous The router distributes its local state throughout the Autonomous
System by flooding. System by flooding.
All routers run the exact same algorithm, in parallel. From the All routers run the exact same algorithm, in parallel. From the
link-state database, each router constructs a tree of shortest link-state database, each router constructs a tree of shortest
paths with itself as root. This shortest-path tree gives the paths with itself as root. This shortest-path tree gives the
route to each destination in the Autonomous System. Externally route to each destination in the Autonomous System. Externally
derived routing information appears on the tree as leaves. derived routing information appears on the tree as leaves.
When several equal-cost routes to a destination exist, traffic When several equal-cost routes to a destination exist, traffic
is distributed equally among them. The cost of a route is is distributed equally among them. The cost of a route is
described by a single dimensionless metric. described by a single dimensionless metric.
OSPF allows sets of networks to be grouped together. Such a OSPF allows sets of networks to be grouped together. Such a
grouping is called an area. The topology of an area is hidden grouping is called an area. The topology of an area is hidden
from the rest of the Autonomous System. This information hiding from the rest of the Autonomous System. This information hiding
enables a significant reduction in routing traffic. Also, enables a significant reduction in routing traffic. Also,
routing within the area is determined only by the area's own routing within the area is determined only by the area's own
topology, lending the area protection from bad routing data. An topology, lending the area protection from bad routing data. An
area is a generalization of an IP subnetted network. area is a generalization of an IP subnetted network.
OSPF enables the flexible configuration of IP subnets. Each OSPF enables the flexible configuration of IP subnets. Each
route distributed by OSPF has a destination and mask. Two route distributed by OSPF has a destination and mask. Two
different subnets of the same IP network number may have different subnets of the same IP network number may have
different sizes (i.e., different masks). This is commonly different sizes (i.e., different masks). This is commonly
referred to as variable length subnetting. A packet is routed referred to as variable length subnetting. A packet is routed
to the best (i.e., longest or most specific) match. Host routes to the best (i.e., longest or most specific) match. Host routes
are considered to be subnets whose masks are "all ones" are considered to be subnets whose masks are "all ones"
(0xffffffff). (0xffffffff).
All OSPF protocol exchanges are authenticated. This means that All OSPF protocol exchanges are authenticated. This means that
only trusted routers can participate in the Autonomous System's only trusted routers can participate in the Autonomous System's
routing. A variety of authentication schemes can be used; in routing. A variety of authentication schemes can be used; in
fact, separate authentication schemes can be configured for each fact, separate authentication schemes can be configured for each
IP subnet. IP subnet.
Externally derived routing data (e.g., routes learned from an Externally derived routing data (e.g., routes learned from an
Exterior Gateway Protocol such as BGP; see [Ref23]) is Exterior Gateway Protocol such as BGP; see [Ref23]) is
advertised throughout the Autonomous System. This externally advertised throughout the Autonomous System. This externally
derived data is kept separate from the OSPF protocol's link derived data is kept separate from the OSPF protocol's link
state data. Each external route can also be tagged by the state data. Each external route can also be tagged by the
advertising router, enabling the passing of additional advertising router, enabling the passing of additional
information between routers on the boundary of the Autonomous information between routers on the boundary of the Autonomous
System. System.
1.2. Definitions of commonly used terms 1.2. Definitions of commonly used terms
This section provides definitions for terms that have a specific This section provides definitions for terms that have a specific
meaning to the OSPF protocol and that are used throughout the meaning to the OSPF protocol and that are used throughout the
text. The reader unfamiliar with the Internet Protocol Suite is text. The reader unfamiliar with the Internet Protocol Suite is
referred to [Ref13] for an introduction to IP. referred to [Ref13] for an introduction to IP.
Router Router
A level three Internet Protocol packet switch. Formerly A level three Internet Protocol packet switch. Formerly
called a gateway in much of the IP literature. called a gateway in much of the IP literature.
Autonomous System Autonomous System
A group of routers exchanging routing information via a A group of routers exchanging routing information via a
common routing protocol. Abbreviated as AS. common routing protocol. Abbreviated as AS.
Interior Gateway Protocol Interior Gateway Protocol
The routing protocol spoken by the routers belonging to an The routing protocol spoken by the routers belonging to an
Autonomous system. Abbreviated as IGP. Each Autonomous Autonomous system. Abbreviated as IGP. Each Autonomous
System has a single IGP. Separate Autonomous Systems may be System has a single IGP. Separate Autonomous Systems may be
running different IGPs. running different IGPs.
Router ID Router ID
A 32-bit number assigned to each router running the OSPF A 32-bit number assigned to each router running the OSPF
protocol. This number uniquely identifies the router within protocol. This number uniquely identifies the router within
an Autonomous System. an Autonomous System.
Network Network
In this memo, an IP network/subnet/supernet. It is possible In this memo, an IP network/subnet/supernet. It is possible
for one physical network to be assigned multiple IP for one physical network to be assigned multiple IP
network/subnet numbers. We consider these to be separate network/subnet numbers. We consider these to be separate
networks. Point-to-point physical networks are an exception networks. Point-to-point physical networks are an exception
- they are considered a single network no matter how many - they are considered a single network no matter how many
(if any at all) IP network/subnet numbers are assigned to (if any at all) IP network/subnet numbers are assigned to
them. them.
Network mask Network mask
A 32-bit number indicating the range of IP addresses A 32-bit number indicating the range of IP addresses
residing on a single IP network/subnet/supernet. This residing on a single IP network/subnet/supernet. This
specification displays network masks as hexadecimal numbers. 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 For example, the network mask for a class C IP network is
A network that joins a single pair of routers. A 56Kb displayed as 0xffffff00. Such a mask is often displayed
serial line is an example of a point-to-point network. elsewhere in the literature as 255.255.255.0.
Broadcast networks Point-to-point networks
Networks supporting many (more than two) attached routers, A network that joins a single pair of routers. A 56Kb
together with the capability to address a single physical serial line is an example of a point-to-point network.
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 Broadcast networks
Networks supporting many (more than two) routers, but having Networks supporting many (more than two) attached routers,
no broadcast capability. Neighboring routers are maintained together with the capability to address a single physical
on these nets using OSPF's Hello Protocol. However, due to message to all of the attached routers (broadcast).
the lack of broadcast capability, some configuration Neighboring routers are discovered dynamically on these nets
information may be necessary to aid in the discovery of using OSPF's Hello Protocol. The Hello Protocol itself
neighbors. On non-broadcast networks, OSPF protocol packets takes advantage of the broadcast capability. The OSPF
that are normally multicast need to be sent to each protocol makes further use of multicast capabilities, if
neighboring router, in turn. An X.25 Public Data Network they exist. Each pair of routers on a broadcast network is
(PDN) is an example of a non-broadcast network. assumed to be able to communicate directly. An ethernet is
an example of a broadcast network.
OSPF runs in one of two modes over non-broadcast networks. Non-broadcast networks
The first mode, called non-broadcast multi-access or NBMA, Networks supporting many (more than two) routers, but having
simulates the operation of OSPF on a broadcast network. The no broadcast capability. Neighboring routers are maintained
second mode, called Point-to-MultiPoint, treats the non- on these nets using OSPF's Hello Protocol. However, due to
broadcast network as a collection of point-to-point links. the lack of broadcast capability, some configuration
Non-broadcast networks are referred to as NBMA networks or information may be necessary to aid in the discovery of
Point-to-MultiPoint networks, depending on OSPF's mode of neighbors. On non-broadcast networks, OSPF protocol packets
operation over the network. 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.
Interface OSPF runs in one of two modes over non-broadcast networks.
The connection between a router and one of its attached The first mode, called non-broadcast multi-access or NBMA,
networks. An interface has state information associated simulates the operation of OSPF on a broadcast network. The
with it, which is obtained from the underlying lower level second mode, called Point-to-MultiPoint, treats the non-
protocols and the routing protocol itself. An interface to broadcast network as a collection of point-to-point links.
a network has associated with it a single IP address and Non-broadcast networks are referred to as NBMA networks or
mask (unless the network is an unnumbered point-to-point Point-to-MultiPoint networks, depending on OSPF's mode of
network). An interface is sometimes also referred to as a operation over the network.
link.
Neighboring routers Interface
Two routers that have interfaces to a common network. The connection between a router and one of its attached
Neighbor relationships are maintained by, and usually networks. An interface has state information associated
dynamically discovered by, OSPF's Hello Protocol. 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.
Adjacency Neighboring routers
A relationship formed between selected neighboring routers Two routers that have interfaces to a common network.
for the purpose of exchanging routing information. Not Neighbor relationships are maintained by, and usually
every pair of neighboring routers become adjacent. dynamically discovered by, OSPF's Hello Protocol.
Link state advertisement Adjacency
Unit of data describing the local state of a router or A relationship formed between selected neighboring routers
network. For a router, this includes the state of the for the purpose of exchanging routing information. Not
router's interfaces and adjacencies. Each link state every pair of neighboring routers become adjacent.
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 Link state advertisement
The part of the OSPF protocol used to establish and maintain Unit of data describing the local state of a router or
neighbor relationships. On broadcast networks the Hello network. For a router, this includes the state of the
Protocol can also dynamically discover neighboring routers. 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.
Flooding Hello Protocol
The part of the OSPF protocol that distributes and The part of the OSPF protocol used to establish and maintain
synchronizes the link-state database between OSPF routers. neighbor relationships. On broadcast networks the Hello
Protocol can also dynamically discover neighboring routers.
Designated Router Flooding
Each broadcast and NBMA network that has at least two The part of the OSPF protocol that distributes and
attached routers has a Designated Router. The Designated synchronizes the link-state database between OSPF routers.
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 Designated Router
number of adjacencies required on a broadcast or NBMA Each broadcast and NBMA network that has at least two
network. This in turn reduces the amount of routing attached routers has a Designated Router. The Designated
protocol traffic and the size of the link-state database. 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.
Lower-level protocols The Designated Router concept enables a reduction in the
The underlying network access protocols that provide number of adjacencies required on a broadcast or NBMA
services to the Internet Protocol and in turn the OSPF network. This in turn reduces the amount of routing
protocol. Examples of these are the X.25 packet and frame protocol traffic and the size of the link-state database.
levels for X.25 PDNs, and the ethernet data link layer for
ethernets.
1.3. Brief history of link-state routing technology 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.
OSPF is a link state routing protocol. Such protocols are also 1.3. Brief history of link-state routing technology
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 OSPF is a link state routing protocol. Such protocols are also
the ARPANET packet switching network. This protocol is referred to in the literature as SPF-based or distributed-
described in [Ref3]. It has formed the starting point for all database protocols. This section gives a brief description of
other link-state protocols. The homogeneous ARPANET the developments in link-state technology that have influenced
environment, i.e., single-vendor packet switches connected by the OSPF protocol.
synchronous serial lines, simplified the design and
implementation of the original protocol.
Modifications to this protocol were proposed in [Ref4]. These The first link-state routing protocol was developed for use in
modifications dealt with increasing the fault tolerance of the the ARPANET packet switching network. This protocol is
routing protocol through, among other things, adding a checksum described in [Ref3]. It has formed the starting point for all
to the LSAs (thereby detecting database corruption). The paper other link-state protocols. The homogeneous ARPANET
also included means for reducing the routing traffic overhead in environment, i.e., single-vendor packet switches connected by
a link-state protocol. This was accomplished by introducing synchronous serial lines, simplified the design and
mechanisms which enabled the interval between LSA originations implementation of the original protocol.
to be increased by an order of magnitude.
A link-state algorithm has also been proposed for use as an ISO Modifications to this protocol were proposed in [Ref4]. These
IS-IS routing protocol. This protocol is described in [Ref2]. modifications dealt with increasing the fault tolerance of the
The protocol includes methods for data and routing traffic routing protocol through, among other things, adding a checksum
reduction when operating over broadcast networks. This is to the LSAs (thereby detecting database corruption). The paper
accomplished by election of a Designated Router for each also included means for reducing the routing traffic overhead in
broadcast network, which then originates an LSA for the network. 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.
The OSPF Working Group of the IETF has extended this work in A link-state algorithm has also been proposed for use as an ISO
developing the OSPF protocol. The Designated Router concept has IS-IS routing protocol. This protocol is described in [Ref2].
been greatly enhanced to further reduce the amount of routing The protocol includes methods for data and routing traffic
traffic required. Multicast capabilities are utilized for reduction when operating over broadcast networks. This is
additional routing bandwidth reduction. An area routing scheme accomplished by election of a Designated Router for each
has been developed enabling information broadcast network, which then originates an LSA for the network.
hiding/protection/reduction. Finally, the algorithms have been
tailored for efficient operation in TCP/IP internets. 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 1.4. Organization of this document
The first three sections of this specification give a general The first three sections of this specification give a general
overview of the protocol's capabilities and functions. Sections overview of the protocol's capabilities and functions. Sections
4-16 explain the protocol's mechanisms in detail. Packet 4-16 explain the protocol's mechanisms in detail. Packet
formats, protocol constants and configuration items are formats, protocol constants and configuration items are
specified in the appendices. specified in the appendices.
Labels such as HelloInterval encountered in the text refer to Labels such as HelloInterval encountered in the text refer to
protocol constants. They may or may not be configurable. protocol constants. They may or may not be configurable.
Architectural constants are summarized in Appendix B. Architectural constants are summarized in Appendix B.
Configurable constants are summarized in Appendix C. Configurable constants are summarized in Appendix C.
The detailed specification of the protocol is presented in terms The detailed specification of the protocol is presented in terms
of data structures. This is done in order to make the of data structures. This is done in order to make the
explanation more precise. Implementations of the protocol are explanation more precise. Implementations of the protocol are
required to support the functionality described, but need not required to support the functionality described, but need not
use the precise data structures that appear in this memo. use the precise data structures that appear in this memo.
1.5. Acknowledgments 1.5. Acknowledgments
The author would like to thank Ran Atkinson, Fred Baker, Jeffrey The author would like to thank Ran Atkinson, Fred Baker, Jeffrey
Burgan, Rob Coltun, Dino Farinacci, Vince Fuller, Phanindra Burgan, Rob Coltun, Dino Farinacci, Vince Fuller, Phanindra
Jujjavarapu, Milo Medin, Tom Pusateri, Kannan Varadhan, Zhaohui Jujjavarapu, Milo Medin, Tom Pusateri, Kannan Varadhan, Zhaohui
Zhang and the rest of the OSPF Working Group for the ideas and Zhang and the rest of the OSPF Working Group for the ideas and
support they have given to this project. support they have given to this project.
The OSPF Point-to-MultiPoint interface is based on work done by The OSPF Point-to-MultiPoint interface is based on work done by
Fred Baker. Fred Baker.
The OSPF Cryptographic Authentication option was developed by The OSPF Cryptographic Authentication option was developed by
Fred Baker and Ran Atkinson. Fred Baker and Ran Atkinson.
2. The Link-state Database: organization and calculations 2. The Link-state Database: organization and calculations
The following subsections describe the organization of OSPF's link- The following subsections describe the organization of OSPF's link-
state database, and the routing calculations that are performed on state database, and the routing calculations that are performed on
the database in order to produce a router's routing table. the database in order to produce a router's routing table.
2.1. Representation of routers and networks 2.1. Representation of routers and networks
The Autonomous System's link-state database describes a directed The Autonomous System's link-state database describes a directed
graph. The vertices of the graph consist of routers and graph. The vertices of the graph consist of routers and
networks. A graph edge connects two routers when they are networks. A graph edge connects two routers when they are
attached via a physical point-to-point network. An edge attached via a physical point-to-point network. An edge
connecting a router to a network indicates that the router has connecting a router to a network indicates that the router has
an interface on the network. Networks can be either transit or an interface on the network. Networks can be either transit or
stub networks. Transit networks are those capable of carrying stub networks. Transit networks are those capable of carrying
data traffic that is neither locally originated nor locally data traffic that is neither locally originated nor locally
destined. A transit network is represented by a graph vertex destined. A transit network is represented by a graph vertex
having both incoming and outgoing edges. A stub network's vertex having both incoming and outgoing edges. A stub network's vertex
has only incoming edges. has only incoming edges.
The neighborhood of each network node in the graph depends on The neighborhood of each network node in the graph depends on
the network's type (point-to-point, broadcast, NBMA or Point- the network's type (point-to-point, broadcast, NBMA or Point-
to-MultiPoint) and the number of routers having an interface to to-MultiPoint) and the number of routers having an interface to
the network. Three cases are depicted in Figure 1a. Rectangles the network. Three cases are depicted in Figure 1a. Rectangles
indicate routers. Circles and oblongs indicate networks. indicate routers. Circles and oblongs indicate networks.
Router names are prefixed with the letters RT and network names Router names are prefixed with the letters RT and network names
with the letter N. Router interface names are prefixed by the with the letter N. Router interface names are prefixed by the
letter I. Lines between routers indicate point-to-point letter I. Lines between routers indicate point-to-point
networks. The left side of the figure shows networks with their networks. The left side of the figure shows networks with their
connected routers, with the resulting graphs shown on the right. connected routers, with the resulting graphs shown on the right.
**FROM** **FROM**
* |RT1|RT2| * |RT1|RT2|
+---+Ia +---+ * ------------ +---+Ia +---+ * ------------
|RT1|------|RT2| T RT1| | X | |RT1|------|RT2| T RT1| | X |
+---+ Ib+---+ O RT2| X | | +---+ Ib+---+ O RT2| X | |
* Ia| | X | * Ia| | X |
* Ib| X | | * Ib| X | |
Physical point-to-point networks Physical point-to-point networks
**FROM** **FROM**
+---+ * +---+ *
|RT7| * |RT7| N3| |RT7| * |RT7| N3|
+---+ T ------------ +---+ T ------------
| O RT7| | | | O RT7| | |
+----------------------+ * N3| X | | +----------------------+ * N3| X | |
N3 * N3 *
Stub networks Stub networks
**FROM** **FROM**
+---+ +---+ +---+ +---+
|RT3| |RT4| |RT3|RT4|RT5|RT6|N2 | |RT3| |RT4| |RT3|RT4|RT5|RT6|N2 |
+---+ +---+ * ------------------------ +---+ +---+ * ------------------------
| N2 | * RT3| | | | | X | | N2 | * RT3| | | | | X |
+----------------------+ T RT4| | | | | X | +----------------------+ T RT4| | | | | X |
| | O RT5| | | | | X | | | O RT5| | | | | X |
+---+ +---+ * RT6| | | | | X | +---+ +---+ * RT6| | | | | X |
|RT5| |RT6| * N2| X | X | X | X | | |RT5| |RT6| * N2| X | X | X | X | |
+---+ +---+ +---+ +---+
Broadcast or NBMA networks Broadcast or NBMA networks
Figure 1a: Network map components Figure 1a: Network map components
Networks and routers are represented by vertices. Networks and routers are represented by vertices.
An edge connects Vertex A to Vertex B iff the An edge connects Vertex A to Vertex B iff the
intersection of Column A and Row B is marked with intersection of Column A and Row B is marked with
an X. an X.
The top of Figure 1a shows two routers connected by a point-to- The top of Figure 1a shows two routers connected by a point-to-
point link. In the resulting link-state database graph, the two point link. In the resulting link-state database graph, the two
router vertices are directly connected by a pair of edges, one router vertices are directly connected by a pair of edges, one
in each direction. Interfaces to point-to-point networks need in each direction. Interfaces to point-to-point networks need
not be assigned IP addresses. When interface addresses are not be assigned IP addresses. When interface addresses are
assigned, they are modelled as stub links, with each router assigned, they are modelled as stub links, with each router
advertising a stub connection to the other router's interface advertising a stub connection to the other router's interface
address. Optionally, an IP subnet can be assigned to the point- address. Optionally, an IP subnet can be assigned to the point-
to-point network. In this case, both routers advertise a stub to-point network. In this case, both routers advertise a stub
link to the IP subnet, instead of advertising each others' IP link to the IP subnet, instead of advertising each others' IP
interface addresses. interface addresses.
The middle of Figure 1a shows a network with only one attached The middle of Figure 1a shows a network with only one attached
router (i.e., a stub network). In this case, the network appears 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 on the end of a stub connection in the link-state database's
graph. graph.
When multiple routers are attached to a broadcast network, the When multiple routers are attached to a broadcast network, the
link-state database graph shows all routers bidirectionally link-state database graph shows all routers bidirectionally
connected to the network vertex. This is pictured at the bottom connected to the network vertex. This is pictured at the bottom
of Figure 1a. of Figure 1a.
Each network (stub or transit) in the graph has an IP address Each network (stub or transit) in the graph has an IP address
and associated network mask. The mask indicates the number of and associated network mask. The mask indicates the number of
nodes on the network. Hosts attached directly to routers nodes on the network. Hosts attached directly to routers
(referred to as host routes) appear on the graph as stub (referred to as host routes) appear on the graph as stub
networks. The network mask for a host route is always networks. The network mask for a host route is always
0xffffffff, which indicates the presence of a single node. 0xffffffff, which indicates the presence of a single node.
2.1.1. Representation of non-broadcast networks 2.1.1. Representation of non-broadcast networks
As mentioned previously, OSPF can run over non-broadcast As mentioned previously, OSPF can run over non-broadcast
networks in one of two modes: NBMA or Point-to-MultiPoint. networks in one of two modes: NBMA or Point-to-MultiPoint.
The choice of mode determines the way that the Hello The choice of mode determines the way that the Hello
protocol and flooding work over the non-broadcast network, protocol and flooding work over the non-broadcast network,
and the way that the network is represented in the link- and the way that the network is represented in the link-
state database. state database.
In NBMA mode, OSPF emulates operation over a broadcast In NBMA mode, OSPF emulates operation over a broadcast
network: a Designated Router is elected for the NBMA network: a Designated Router is elected for the NBMA
network, and the Designated Router originates an LSA for the network, and the Designated Router originates an LSA for the
network. The graph representation for broadcast networks and network. The graph representation for broadcast networks and
NBMA networks is identical. This representation is pictured NBMA networks is identical. This representation is pictured
in the middle of Figure 1a. in the middle of Figure 1a.
NBMA mode is the most efficient way to run OSPF over non- NBMA mode is the most efficient way to run OSPF over non-
broadcast networks, both in terms of link-state database broadcast networks, both in terms of link-state database
size and in terms of the amount of routing protocol traffic. size and in terms of the amount of routing protocol traffic.
However, it has one significant restriction: it requires all However, it has one significant restriction: it requires all
routers attached to the NBMA network to be able to routers attached to the NBMA network to be able to
communicate directly. This restriction may be met on some communicate directly. This restriction may be met on some
non-broadcast networks, such as an ATM subnet utilizing non-broadcast networks, such as an ATM subnet utilizing
SVCs. But it is often not met on other non-broadcast SVCs. But it is often not met on other non-broadcast
networks, such as PVC-only Frame Relay networks. On non- networks, such as PVC-only Frame Relay networks. On non-
broadcast networks where not all routers can communicate broadcast networks where not all routers can communicate
directly you can break the non-broadcast network into directly you can break the non-broadcast network into
logical subnets, with the routers on each subnet being able logical subnets, with the routers on each subnet being able
to communicate directly, and then run each separate subnet to communicate directly, and then run each separate subnet
as an NBMA network (see [Ref15]). This however requires as an NBMA network (see [Ref15]). This however requires
quite a bit of administrative overhead, and is prone to quite a bit of administrative overhead, and is prone to
misconfiguration. It is probably better to run such a non- misconfiguration. It is probably better to run such a non-
broadcast network in Point-to-Multipoint mode. broadcast network in Point-to-Multipoint mode.
In Point-to-MultiPoint mode, OSPF treats all router-to- In Point-to-MultiPoint mode, OSPF treats all router-to-
router connections over the non-broadcast network as if they router connections over the non-broadcast network as if they
were point-to-point links. No Designated Router is elected were point-to-point links. No Designated Router is elected
for the network, nor is there an LSA generated for the for the network, nor is there an LSA generated for the
network. In fact, a vertex for the Point-to-MultiPoint network. In fact, a vertex for the Point-to-MultiPoint
network does not appear in the graph of the link-state network does not appear in the graph of the link-state
database. database.
Figure 1b illustrates the link-state database representation Figure 1b illustrates the link-state database representation
of a Point-to-MultiPoint network. On the left side of the of a Point-to-MultiPoint network. On the left side of the
figure, a Point-to-MultiPoint network is pictured. It is figure, a Point-to-MultiPoint network is pictured. It is
assumed that all routers can communicate directly, except assumed that all routers can communicate directly, except
for routers RT4 and RT5. I3 though I6 indicate the routers' for routers RT4 and RT5. I3 though I6 indicate the routers'
IP interface addresses on the Point-to-MultiPoint network. IP interface addresses on the Point-to-MultiPoint network.
In the graphical representation of the link-state database, In the graphical representation of the link-state database,
routers that can communicate directly over the Point-to- routers that can communicate directly over the Point-to-
MultiPoint network are joined by bidirectional edges, and MultiPoint network are joined by bidirectional edges, and
each router also has a stub connection to its own IP each router also has a stub connection to its own IP
interface address (which is in contrast to the interface address (which is in contrast to the
representation of real point-to-point links; see Figure 1a). representation of real point-to-point links; see Figure 1a).
On some non-broadcast networks, use of Point-to-MultiPoint On some non-broadcast networks, use of Point-to-MultiPoint
mode and data-link protocols such as Inverse ARP (see mode and data-link protocols such as Inverse ARP (see
[Ref14]) will allow autodiscovery of OSPF neighbors even [Ref14]) will allow autodiscovery of OSPF neighbors even
though broadcast support is not available. though broadcast support is not available.
2.1.2. An example link-state database **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 2 shows a sample map of an Autonomous System. The Figure 1b: Network map components
rectangle labelled H1 indicates a host, which has a SLIP Point-to-MultiPoint networks
**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 All routers can communicate directly over N2, except
Point-to-MultiPoint networks routers RT4 and RT5. I3 through I6 indicate IP
interface addresses
All routers can communicate directly over N2, except 2.1.2. An example link-state database
routers RT4 and RT5. I3 through I6 indicate IP
interface addresses
connection to Router RT12. Router RT12 is therefore Figure 2 shows a sample map of an Autonomous System. The
advertising a host route. Lines between routers indicate rectangle labelled H1 indicates a host, which has a SLIP
physical point-to-point networks. The only point-to-point connection to Router RT12. Router RT12 is therefore
network that has been assigned interface addresses is the advertising a host route. Lines between routers indicate
one joining Routers RT6 and RT10. Routers RT5 and RT7 have physical point-to-point networks. The only point-to-point
BGP connections to other Autonomous Systems. A set of BGP- network that has been assigned interface addresses is the
learned routes have been displayed for both of these one joining Routers RT6 and RT10. Routers RT5 and RT7 have
routers. 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 A cost is associated with the output side of each router
interface. This cost is configurable by the system interface. This cost is configurable by the system
administrator. The lower the cost, the more likely the administrator. The lower the cost, the more likely the
interface is to be used to forward data traffic. Costs are interface is to be used to forward data traffic. Costs are
also associated with the externally derived routing data also associated with the externally derived routing data
(e.g., the BGP-learned routes). (e.g., the BGP-learned routes).
The directed graph resulting from the map in Figure 2 is The directed graph resulting from the map in Figure 2 is
depicted in Figure 3. Arcs are labelled with the cost of depicted in Figure 3. Arcs are labelled with the cost of
the corresponding router output interface. Arcs having no the corresponding router output interface. Arcs having no
labelled cost have a cost of 0. Note that arcs leading from labelled cost have a cost of 0. Note that arcs leading from
networks to routers always have cost 0; they are significant networks to routers always have cost 0; they are significant
nonetheless. Note also that the externally derived routing nonetheless. Note also that the externally derived routing
data appears on the graph as stubs. data appears on the graph as stubs.
+ The link-state database is pieced together from LSAs
| 3+---+ N12 N14 generated by the routers. In the associated graphical
N1|--|RT1|\ 1 \ N13 / representation, the neighborhood of each router or transit
| +---+ \ 8\ |8/8 network is represented in a single, separate LSA. Figure 4
+ \ ____ \|/ shows these LSAs graphically. Router RT12 has an interface
/ \ 1+---+8 8+---+6 to two broadcast networks and a SLIP line to a host.
* N3 *---|RT4|------|RT5|--------+ Network N6 is a broadcast network with three attached
\____/ +---+ +---+ | routers. The cost of all links from Network N6 to its
+ / | |7 | attached routers is 0. Note that the LSA for Network N6 is
| 3+---+ / | | | actually generated by one of the network's attached routers:
N2|--|RT2|/1 |1 |6 | the router that has been elected Designated Router for the
| +---+ +---+8 6+---+ | network.
+ |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 +
**FROM** | 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
|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT| Figure 2: A sample Autonomous System
|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 **FROM**
Networks and routers are represented by vertices. |RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|
An edge of cost X connects Vertex A to Vertex B iff |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12|N3|N6|N8|N9|
the intersection of Column A and Row B is marked ----- ---------------------------------------------
with an X. 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| | | | |
The link-state database is pieced together from LSAs Figure 3: The resulting directed graph
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. 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 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.
When no OSPF areas are configured, each router in the Autonomous **FROM** **FROM**
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 |RT12|N9|N10|H1| |RT9|RT11|RT12|N9|
host. However, only the next hop to the destination is used in * -------------------- * ----------------------
the forwarding process. Note also that the best route to any * RT12| | | | | * RT9| | | |0 |
router has also been calculated. For the processing of external T N9|1 | | | | T RT11| | | |0 |
data, we note the next hop and distance to any router O N10|2 | | | | O RT12| | | |0 |
advertising external routes. The resulting routing table for * H1|10 | | | | * N9| | | | |
Router RT6 is pictured in Table 2. Note that there is a * *
separate route for each end of a numbered point-to-point network RT12's router-LSA N9's network-LSA
(in this case, the serial line between Routers RT6 and RT10).
**FROM** **FROM** Figure 4: Individual link state components
|RT12|N9|N10|H1| |RT9|RT11|RT12|N9| Networks and routers are represented by vertices.
* -------------------- * ---------------------- An edge of cost X connects Vertex A to Vertex B iff
* RT12| | | | | * RT9| | | |0 | the intersection of Column A and Row B is marked
T N9|1 | | | | T RT11| | | |0 | with an X.
O N10|2 | | | | O RT12| | | |0 |
* H1|10 | | | | * N9| | | | |
* *
RT12's router-LSA N9's network-LSA
Figure 4: Individual link state components 2.2. The shortest-path tree
Networks and routers are represented by vertices. When no OSPF areas are configured, each router in the Autonomous
An edge of cost X connects Vertex A to Vertex B iff System has an identical link-state database, leading to an
the intersection of Column A and Row B is marked identical graphical representation. A router generates its
with an X. 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.
RT6(origin) The tree gives the entire path to any destination network or
RT5 o------------o-----------o Ib host. However, only the next hop to the destination is used in
/|\ 6 |\ 7 the forwarding process. Note also that the best route to any
8/8|8\ | \ router has also been calculated. For the processing of external
/ | \ 6| \ data, we note the next hop and distance to any router
o | o | \7 advertising external routes. The resulting routing table for
N12 o N14 | \ Router RT6 is pictured in Table 2. Note that there is a
N13 2 | \ separate route for each end of a numbered point-to-point network
N4 o-----o RT3 \ (in this case, the serial line between Routers RT6 and RT10).
/ \ 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 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
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
Edges that are not marked with a cost have a cost of Figure 5: The SPF tree for Router RT6
of zero (these are network-to-router links). Routes
to networks N12-N15 are external information that is Edges that are not marked with a cost have a cost of
considered in Section 2.3 of zero (these are network-to-router links). Routes
Destination Next Hop Distance to networks N12-N15 are external information that is
__________________________________ considered in Section 2.3
N1 RT3 10
N2 RT3 10 Destination Next Hop Distance
N3 RT3 7 __________________________________
N4 RT3 8 N1 RT3 10
Ib * 7 N2 RT3 10
Ia RT10 12 N3 RT3 7
N6 RT10 8 N4 RT3 8
N7 RT10 12 Ib * 7
N8 RT10 10 Ia RT10 12
N9 RT10 11 N6 RT10 8
N10 RT10 13 N7 RT10 12
N11 RT10 14 N8 RT10 10
H1 RT10 21 N9 RT10 11
__________________________________ N10 RT10 13
RT5 RT5 6 N11 RT10 14
RT7 RT10 8 H1 RT10 21
__________________________________
RT5 RT5 6
RT7 RT10 8
Table 2: The portion of Router RT6's routing table listing local Table 2: The portion of Router RT6's routing table listing local
destinations. destinations.
Routes to networks belonging to other AS'es (such as N12) appear this externally derived routing information is considered in the
as dashed lines on the shortest path tree in Figure 5. Use of next section.
this externally derived routing information is considered in the
next section.
2.3. Use of external routing information 2.3. Use of external routing information
After the tree is created the external routing information is After the tree is created the external routing information is
examined. This external routing information may originate from examined. This external routing information may originate from
another routing protocol such as BGP, or be statically another routing protocol such as BGP, or be statically
configured (static routes). Default routes can also be included configured (static routes). Default routes can also be included
as part of the Autonomous System's external routing information. as part of the Autonomous System's external routing information.
External routing information is flooded unaltered throughout the External routing information is flooded unaltered throughout the
AS. In our example, all the routers in the Autonomous System AS. In our example, all the routers in the Autonomous System
know that Router RT7 has two external routes, with metrics 2 and know that Router RT7 has two external routes, with metrics 2 and
9. 9.
OSPF supports two types of external metrics. Type 1 external OSPF supports two types of external metrics. Type 1 external
metrics are expressed in the same units as OSPF interface cost metrics are expressed in the same units as OSPF interface cost
(i.e., in terms of the link state metric). Type 2 external (i.e., in terms of the link state metric). Type 2 external
metrics are an order of magnitude larger; any Type 2 metric is metrics are an order of magnitude larger; any Type 2 metric is
considered greater than the cost of any path internal to the AS. considered greater than the cost of any path internal to the AS.
Use of Type 2 external metrics assumes that routing between Use of Type 2 external metrics assumes that routing between
AS'es is the major cost of routing a packet, and eliminates the AS'es is the major cost of routing a packet, and eliminates the
need for conversion of external costs to internal link state need for conversion of external costs to internal link state
metrics. metrics.
As an example of Type 1 external metric processing, suppose that As an example of Type 1 external metric processing, suppose that
the Routers RT7 and RT5 in Figure 2 are advertising Type 1 the Routers RT7 and RT5 in Figure 2 are advertising Type 1
external metrics. For each advertised external route, the total external metrics. For each advertised external route, the total
cost from Router RT6 is calculated as the sum of the external cost from Router RT6 is calculated as the sum of the external
route's advertised cost and the distance from Router RT6 to the route's advertised cost and the distance from Router RT6 to the
advertising router. When two routers are advertising the same advertising router. When two routers are advertising the same
external destination, RT6 picks the advertising router providing external destination, RT6 picks the advertising router providing
the minimum total cost. RT6 then sets the next hop to the the minimum total cost. RT6 then sets the next hop to the
external destination equal to the next hop that would be used external destination equal to the next hop that would be used
when routing packets to the chosen advertising router. when routing packets to the chosen advertising router.
In Figure 2, both Router RT5 and RT7 are advertising an external In Figure 2, both Router RT5 and RT7 are advertising an external
route to destination Network N12. Router RT7 is preferred since route to destination Network N12. Router RT7 is preferred since
it is advertising N12 at a distance of 10 (8+2) to Router RT6, 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 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 entries that are added to the routing table when external routes
are examined: are examined:
Destination Next Hop Distance Destination Next Hop Distance
__________________________________ __________________________________
N12 RT10 10 N12 RT10 10
N13 RT5 14 N13 RT5 14
N14 RT5 14 N14 RT5 14
N15 RT10 17 N15 RT10 17
Table 3: The portion of Router RT6's routing table Table 3: The portion of Router RT6's routing table
listing external destinations. listing external destinations.
Processing of Type 2 external metrics is simpler. The AS Processing of Type 2 external metrics is simpler. The AS
boundary router advertising the smallest external metric is boundary router advertising the smallest external metric is
chosen, regardless of the internal distance to the AS boundary chosen, regardless of the internal distance to the AS boundary
router. Suppose in our example both Router RT5 and Router RT7 router. Suppose in our example both Router RT5 and Router RT7
were advertising Type 2 external routes. Then all traffic were advertising Type 2 external routes. Then all traffic
destined for Network N12 would be forwarded to Router RT7, since destined for Network N12 would be forwarded to Router RT7, since
2 < 8. When several equal-cost Type 2 routes exist, the 2 < 8. When several equal-cost Type 2 routes exist, the
internal distance to the advertising routers is used to break internal distance to the advertising routers is used to break
the tie. the tie.
Both Type 1 and Type 2 external metrics can be present in the AS 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 at the same time. In that event, Type 1 external metrics always
take precedence. take precedence.
This section has assumed that packets destined for external This section has assumed that packets destined for external
destinations are always routed through the advertising AS destinations are always routed through the advertising AS
boundary router. This is not always desirable. For example, boundary router. This is not always desirable. For example,
suppose in Figure 2 there is an additional router attached to suppose in Figure 2 there is an additional router attached to
Network N6, called Router RTX. Suppose further that RTX does Network N6, called Router RTX. Suppose further that RTX does
not participate in OSPF routing, but does exchange BGP not participate in OSPF routing, but does exchange BGP
information with the AS boundary router RT7. Then, Router RT7 information with the AS boundary router RT7. Then, Router RT7
would end up advertising OSPF external routes for all would end up advertising OSPF external routes for all
destinations that should be routed to RTX. An extra hop will destinations that should be routed to RTX. An extra hop will
sometimes be introduced if packets for these destinations need sometimes be introduced if packets for these destinations need
always be routed first to Router RT7 (the advertising router). always be routed first to Router RT7 (the advertising router).
To deal with this situation, the OSPF protocol allows an AS To deal with this situation, the OSPF protocol allows an AS
boundary router to specify a "forwarding address" in its AS- boundary router to specify a "forwarding address" in its AS-
external-LSAs. In the above example, Router RT7 would specify external-LSAs. In the above example, Router RT7 would specify
RTX's IP address as the "forwarding address" for all those RTX's IP address as the "forwarding address" for all those
destinations whose packets should be routed directly to RTX. destinations whose packets should be routed directly to RTX.
The "forwarding address" has one other application. It enables The "forwarding address" has one other application. It enables
routers in the Autonomous System's interior to function as routers in the Autonomous System's interior to function as
"route servers". For example, in Figure 2 the router RT6 could "route servers". For example, in Figure 2 the router RT6 could
become a route server, gaining external routing information become a route server, gaining external routing information
through a combination of static configuration and external through a combination of static configuration and external
routing protocols. RT6 would then start advertising itself as routing protocols. RT6 would then start advertising itself as
an AS boundary router, and would originate a collection of OSPF an AS boundary router, and would originate a collection of OSPF
AS-external-LSAs. In each AS-external-LSA, Router RT6 would AS-external-LSAs. In each AS-external-LSA, Router RT6 would
specify the correct Autonomous System exit point to use for the specify the correct Autonomous System exit point to use for the
destination through appropriate setting of the LSA's "forwarding destination through appropriate setting of the LSA's "forwarding
address" field. address" field.
2.4. Equal-cost multipath 2.4. Equal-cost multipath
The above discussion has been simplified by considering only a The above discussion has been simplified by considering only a
single route to any destination. In reality, if multiple single route to any destination. In reality, if multiple
equal-cost routes to a destination exist, they are all equal-cost routes to a destination exist, they are all
discovered and used. This requires no conceptual changes to the discovered and used. This requires no conceptual changes to the
algorithm, and its discussion is postponed until we consider the algorithm, and its discussion is postponed until we consider the
tree-building process in more detail. tree-building process in more detail.
With equal cost multipath, a router potentially has several With equal cost multipath, a router potentially has several
available next hops towards any given destination. available next hops towards any given destination.
3. Splitting the AS into Areas 3. Splitting the AS into Areas
OSPF allows collections of contiguous networks and hosts to be OSPF allows collections of contiguous networks and hosts to be
grouped together. Such a group, together with the routers having grouped together. Such a group, together with the routers having
interfaces to any one of the included networks, is called an area. interfaces to any one of the included networks, is called an area.
Each area runs a separate copy of the basic link-state routing Each area runs a separate copy of the basic link-state routing
algorithm. This means that each area has its own link-state algorithm. This means that each area has its own link-state
database and corresponding graph, as explained in the previous database and corresponding graph, as explained in the previous
section. section.
The topology of an area is invisible from the outside of the area. The topology of an area is invisible from the outside of the area.
Conversely, routers internal to a given area know nothing of the Conversely, routers internal to a given area know nothing of the
detailed topology external to the area. This isolation of knowledge detailed topology external to the area. This isolation of knowledge
enables the protocol to effect a marked reduction in routing traffic enables the protocol to effect a marked reduction in routing traffic
as compared to treating the entire Autonomous System as a single as compared to treating the entire Autonomous System as a single
link-state domain. link-state domain.
With the introduction of areas, it is no longer true that all With the introduction of areas, it is no longer true that all
routers in the AS have an identical link-state database. A router routers in the AS have an identical link-state database. A router
actually has a separate link-state database for each area it is actually has a separate link-state database for each area it is
connected to. (Routers connected to multiple areas are called area connected to. (Routers connected to multiple areas are called area
border routers). Two routers belonging to the same area have, for border routers). Two routers belonging to the same area have, for
that area, identical area link-state databases. that area, identical area link-state databases.
Routing in the Autonomous System takes place on two levels, Routing in the Autonomous System takes place on two levels,
depending on whether the source and destination of a packet reside depending on whether the source and destination of a packet reside
in the same area (intra-area routing is used) or different areas in the same area (intra-area routing is used) or different areas
(inter-area routing is used). In intra-area routing, the packet is (inter-area routing is used). In intra-area routing, the packet is
routed solely on information obtained within the area; no routing routed solely on information obtained within the area; no routing
information obtained from outside the area can be used. This information obtained from outside the area can be used. This
protects intra-area routing from the injection of bad routing protects intra-area routing from the injection of bad routing
information. We discuss inter-area routing in Section 3.2. information. We discuss inter-area routing in Section 3.2.
3.1. The backbone of the Autonomous System 3.1. The backbone of the Autonomous System
The OSPF backbone is the special OSPF Area 0 (often written as The OSPF backbone is the special OSPF Area 0 (often written as
Area 0.0.0.0, since OSPF Area ID's are typically formatted as IP Area 0.0.0.0, since OSPF Area ID's are typically formatted as IP
addresses). The OSPF backbone always contains all area border addresses). The OSPF backbone always contains all area border
routers. The backbone is responsible for distributing routing routers. The backbone is responsible for distributing routing
information between non-backbone areas. The backbone must be information between non-backbone areas. The backbone must be
contiguous. However, it need not be physically contiguous; contiguous. However, it need not be physically contiguous;
backbone connectivity can be established/maintained through the backbone connectivity can be established/maintained through the
configuration of virtual links. configuration of virtual links.
Virtual links can be configured between any two backbone routers Virtual links can be configured between any two backbone routers
that have an interface to a common non-backbone area. Virtual that have an interface to a common non-backbone area. Virtual
links belong to the backbone. The protocol treats two routers links belong to the backbone. The protocol treats two routers
joined by a virtual link as if they were connected by an joined by a virtual link as if they were connected by an
unnumbered point-to-point backbone network. On the graph of the unnumbered point-to-point backbone network. On the graph of the
backbone, two such routers are joined by arcs whose costs are backbone, two such routers are joined by arcs whose costs are
the intra-area distances between the two routers. The routing the intra-area distances between the two routers. The routing
protocol traffic that flows along the virtual link uses intra- protocol traffic that flows along the virtual link uses intra-
area routing only. area routing only.
3.2. Inter-area routing 3.2. Inter-area routing
When routing a packet between two non-backbone areas the When routing a packet between two non-backbone areas the
backbone is used. The path that the packet will travel can be backbone is used. The path that the packet will travel can be
broken up into three contiguous pieces: an intra-area path from broken up into three contiguous pieces: an intra-area path from
the source to an area border router, a backbone path between the the source to an area border router, a backbone path between the
source and destination areas, and then another intra-area path source and destination areas, and then another intra-area path
to the destination. The algorithm finds the set of such paths to the destination. The algorithm finds the set of such paths
that have the smallest cost. that have the smallest cost.
Looking at this another way, inter-area routing can be pictured Looking at this another way, inter-area routing can be pictured
as forcing a star configuration on the Autonomous System, with as forcing a star configuration on the Autonomous System, with
the backbone as hub and each of the non-backbone areas as the backbone as hub and each of the non-backbone areas as
spokes. spokes.
The topology of the backbone dictates the backbone paths used The topology of the backbone dictates the backbone paths used
between areas. The topology of the backbone can be enhanced by between areas. The topology of the backbone can be enhanced by
adding virtual links. This gives the system administrator some adding virtual links. This gives the system administrator some
control over the routes taken by inter-area traffic. control over the routes taken by inter-area traffic.
The correct area border router to use as the packet exits the The correct area border router to use as the packet exits the
source area is chosen in exactly the same way routers source area is chosen in exactly the same way routers
advertising external routes are chosen. Each area border router advertising external routes are chosen. Each area border router
in an area summarizes for the area its cost to all networks in an area summarizes for the area its cost to all networks
external to the area. After the SPF tree is calculated for the external to the area. After the SPF tree is calculated for the
area, routes to all inter-area destinations are calculated by area, routes to all inter-area destinations are calculated by
examining the summaries of the area border routers. examining the summaries of the area border routers.
3.3. Classification of routers 3.3. Classification of routers
Before the introduction of areas, the only OSPF routers having a Before the introduction of areas, the only OSPF routers having a
specialized function were those advertising external routing specialized function were those advertising external routing
information, such as Router RT5 in Figure 2. When the AS is information, such as Router RT5 in Figure 2. When the AS is
split into OSPF areas, the routers are further divided according split into OSPF areas, the routers are further divided according
to function into the following four overlapping categories: to function into the following four overlapping categories:
Internal routers Internal routers
A router with all directly connected networks belonging to A router with all directly connected networks belonging to
the same area. These routers run a single copy of the basic the same area. These routers run a single copy of the basic
routing algorithm. routing algorithm.
Area border routers Area border routers
A router that attaches to multiple areas. Area border A router that attaches to multiple areas. Area border
routers run multiple copies of the basic algorithm, one copy routers run multiple copies of the basic algorithm, one copy
for each attached area. Area border routers condense the for each attached area. Area border routers condense the
topological information of their attached areas for topological information of their attached areas for
distribution to the backbone. The backbone in turn distribution to the backbone. The backbone in turn
distributes the information to the other areas. distributes the information to the other areas.
Backbone routers Backbone routers
A router that has an interface to the backbone area. This A router that has an interface to the backbone area. This
includes all routers that interface to more than one area includes all routers that interface to more than one area
(i.e., area border routers). However, backbone routers do (i.e., area border routers). However, backbone routers do
not have to be area border routers. Routers with all not have to be area border routers. Routers with all
interfaces connecting to the backbone area are supported. interfaces connecting to the backbone area are supported.
AS boundary routers AS boundary routers
A router that exchanges routing information with routers A router that exchanges routing information with routers
belonging to other Autonomous Systems. Such a router belonging to other Autonomous Systems. Such a router
advertises AS external routing information throughout the advertises AS external routing information throughout the
Autonomous System. The paths to each AS boundary router are Autonomous System. The paths to each AS boundary router are
known by every router in the AS. This classification is known by every router in the AS. This classification is
completely independent of the previous classifications: AS completely independent of the previous classifications: AS
boundary routers may be internal or area border routers, and boundary routers may be internal or area border routers, and
may or may not participate in the backbone. may or may not participate in the backbone.
3.4. A sample area configuration 3.4. A sample area configuration
Figure 6 shows a sample area configuration. The first area Figure 6 shows a sample area configuration. The first area
consists of networks N1-N4, along with their attached routers consists of networks N1-N4, along with their attached routers
RT1-RT4. The second area consists of networks N6-N8, along with RT1-RT4. The second area consists of networks N6-N8, along with
their attached routers RT7, RT8, RT10 and RT11. The third area their attached routers RT7, RT8, RT10 and RT11. The third area
consists of networks N9-N11 and Host H1, along with their consists of networks N9-N11 and Host H1, along with their
attached routers RT9, RT11 and RT12. The third area has been attached routers RT9, RT11 and RT12. The third area has been
configured so that networks N9-N11 and Host H1 will all be configured so that networks N9-N11 and Host H1 will all be
grouped into a single route, when advertised external to the grouped into a single route, when advertised external to the
area (see Section 3.5 for more details). area (see Section 3.5 for more details).
In Figure 6, Routers RT1, RT2, RT5, RT6, RT8, RT9 and RT12 are In Figure 6, Routers RT1, RT2, RT5, RT6, RT8, RT9 and RT12 are
internal routers. Routers RT3, RT4, RT7, RT10 and RT11 are area internal routers. Routers RT3, RT4, RT7, RT10 and RT11 are area
border routers. Finally, as before, Routers RT5 and RT7 are AS border routers. Finally, as before, Routers RT5 and RT7 are AS
boundary routers. boundary routers.
Figure 7 shows the resulting link-state database for the Area 1. Figure 7 shows the resulting link-state database for the Area 1.
The figure completely describes that area's intra-area routing. The figure completely describes that area's intra-area routing.
It also shows the complete view of the internet for the two
internal routers RT1 and RT2. It is the job of the area border
routers, RT3 and RT4, to advertise into Area 1 the distances to
all destinations external to the area. These are indicated in
Figure 7 by the dashed stub routes. Also, RT3 and RT4 must
advertise into Area 1 the location of the AS boundary routers
RT5 and RT7. Finally, AS-external-LSAs from RT5 and RT7 are
flooded throughout the entire AS, and in particular throughout
Area 1. These LSAs are included in Area 1's database, and yield
routes to Networks N12-N15.
........................... Routers RT3 and RT4 must also summarize Area 1's topology for
. + . ...........................
. | 3+---+ . N12 N14 . + .
. N1|--|RT1|\ 1 . \ N13 / . | 3+---+ . N12 N14
. | +---+ \ . 8\ |8/8 . N1|--|RT1|\ 1 . \ N13 /
. + \ ____ . \|/ . | +---+ \ . 8\ |8/8
. / \ 1+---+8 8+---+6 . + \ ____ . \|/
. * N3 *---|RT4|------|RT5|--------+ . / \ 1+---+8 8+---+6
. \____/ +---+ +---+ | . * N3 *---|RT4|------|RT5|--------+
. + / \ . |7 | . \____/ +---+ +---+ |
. | 3+---+ / \ . | | . + / \ . |7 |
. N2|--|RT2|/1 1\ . |6 | . | 3+---+ / \ . | |
. | +---+ +---+8 6+---+ | . N2|--|RT2|/1 1\ . |6 |
. + |RT3|------|RT6| | . | +---+ +---+8 6+---+ |
. +---+ +---+ | . + |RT3|------|RT6| |
. 2/ . Ia|7 | . +---+ +---+ |
. / . | | . 2/ . Ia|7 |
. +---------+ . | | . / . | |
.Area 1 N4 . | | . +---------+ . | |
........................... | | .Area 1 N4 . | |
.......................... | | ........................... | |
. N11 . | | .......................... | |
. +---------+ . | | . N11 . | |
. | . | | N12 . +---------+ . | |
. |3 . Ib|5 |6 2/ . | . | | N12
. +---+ . +----+ +---+/ . |3 . Ib|5 |6 2/
. |RT9| . .........|RT10|.....|RT7|---N15. . +---+ . +----+ +---+/
. +---+ . . +----+ +---+ 9 . . |RT9| . .........|RT10|.....|RT7|---N15.
. |1 . . + /3 1\ |1 . . +---+ . . +----+ +---+ 9 .
. _|__ . . | / \ __|_ . . |1 . . + /3 1\ |1 .
. / \ 1+----+2 |/ \ / \ . . _|__ . . | / \ __|_ .
. * N9 *------|RT11|----| * N6 * . . / \ 1+----+2 |/ \ / \ .
. \____/ +----+ | \____/ . . * N9 *------|RT11|----| * N6 * .
. | . . | | . . \____/ +----+ | \____/ .
. |1 . . + |1 . . | . . | | .
. +--+ 10+----+ . . N8 +---+ . . |1 . . + |1 .
. |H1|-----|RT12| . . |RT8| . . +--+ 10+----+ . . N8 +---+ .
. +--+SLIP +----+ . . +---+ . . |H1|-----|RT12| . . |RT8| .
. |2 . . |4 . . +--+SLIP +----+ . . +---+ .
. | . . | . . |2 . . |4 .
. +---------+ . . +--------+ . . | . . | .
. N10 . . N7 . . +---------+ . . +--------+ .
. . .Area 2 .
.Area 3 . ................................
..........................
Figure 6: A sample OSPF area configuration . N10 . . N7 .
It also shows the complete view of the internet for the two . . .Area 2 .
internal routers RT1 and RT2. It is the job of the area border .Area 3 . ................................
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 Figure 6: A sample OSPF area configuration
distribution to the backbone. Their backbone LSAs are shown in
Table 4. These summaries show which networks are contained in
Area 1 (i.e., Networks N1-N4), and the distance to these
networks from the routers RT3 and RT4 respectively.
The link-state database for the backbone is shown in Figure 8. distribution to the backbone. Their backbone LSAs are shown in
The set of routers pictured are the backbone routers. Router Table 4. These summaries show which networks are contained in
RT11 is a backbone router because it belongs to two areas. In Area 1 (i.e., Networks N1-N4), and the distance to these
order to make the backbone connected, a virtual link has been networks from the routers RT3 and RT4 respectively.
configured between Routers R10 and R11.
The area border routers RT3, RT4, RT7, RT10 and RT11 condense The link-state database for the backbone is shown in Figure 8.
the routing information of their attached non-backbone areas for The set of routers pictured are the backbone routers. Router
distribution via the backbone; these are the dashed stubs that RT11 is a backbone router because it belongs to two areas. In
appear in Figure 8. Remember that the third area has been order to make the backbone connected, a virtual link has been
configured to condense Networks N9-N11 and Host H1 into a single configured between Routers R10 and R11.
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. The area border routers RT3, RT4, RT7, RT10 and RT11 condense
_____________________________ the routing information of their attached non-backbone areas for
N1 4 4 distribution via the backbone; these are the dashed stubs that
N2 4 4 appear in Figure 8. Remember that the third area has been
N3 1 1 configured to condense Networks N9-N11 and Host H1 into a single
N4 2 3 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.
Table 4: Networks advertised to the backbone Network RT3 adv. RT4 adv.
by Routers RT3 and RT4. _____________________________
N1 4 4
N2 4 4
N3 1 1
N4 2 3
**FROM** Table 4: Networks advertised to the backbone
by Routers RT3 and RT4.
|RT|RT|RT|RT|RT|RT| **FROM**
|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. |RT|RT|RT|RT|RT|RT|
|1 |2 |3 |4 |5 |7 |N3|
----- -------------------
RT1| | | | | | |0 |
RT2| | | | | | |0 |
RT3| | | | | | |0 |
* RT4| | | | | | |0 |
* RT5| | |14|8 | | | |
T RT7| | |20|14| | | |
O N1|3 | | | | | | |
* N2| |3 | | | | | |
* N3|1 |1 |1 |1 | | | |
N4| | |2 | | | | |
Ia,Ib| | |20|27| | | |
N6| | |16|15| | | |
N7| | |20|19| | | |
N8| | |18|18| | | |
N9-N11,H1| | |29|36| | | |
N12| | | | |8 |2 | |
N13| | | | |8 | | |
N14| | | | |8 | | |
N15| | | | | |9 | |
Networks and routers are represented by vertices. Figure 7: Area 1's Database.
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.
**FROM** 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.
|RT|RT|RT|RT|RT|RT|RT **FROM**
|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. |RT|RT|RT|RT|RT|RT|RT
|3 |4 |5 |6 |7 |10|11|
------------------------
RT3| | | |6 | | | |
RT4| | |8 | | | | |
RT5| |8 | |6 |6 | | |
RT6|8 | |7 | | |5 | |
RT7| | |6 | | | | |
* RT10| | | |7 | | |2 |
* RT11| | | | | |3 | |
T N1|4 |4 | | | | | |
O N2|4 |4 | | | | | |
* N3|1 |1 | | | | | |
* N4|2 |3 | | | | | |
Ia| | | | | |5 | |
Ib| | | |7 | | | |
N6| | | | |1 |1 |3 |
N7| | | | |5 |5 |7 |
N8| | | | |4 |3 |2 |
N9-N11,H1| | | | | | |11|
N12| | |8 | |2 | | |
N13| | |8 | | | | |
N14| | |8 | | | | |
N15| | | | |9 | | |
Networks and routers are represented by vertices. Figure 8: The backbone's database.
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 Networks and routers are represented by vertices.
area border routers. Every area border router hears the area An edge of cost X connects Vertex A to Vertex B iff
summaries from all other area border routers. It then forms a the intersection of Column A and Row B is marked
picture of the distance to all networks outside of its area by with an X.
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 The backbone enables the exchange of summary information between
goes as follows: They first calculate the SPF tree for the area border routers. Every area border router hears the area
backbone. This gives the distances to all other area border summaries from all other area border routers. It then forms a
routers. Also noted are the distances to networks (Ia and Ib) picture of the distance to all networks outside of its area by
and AS boundary routers (RT5 and RT7) that belong to the examining the collected LSAs, and adding in the backbone
backbone. This calculation is shown in Table 5. distance to each advertising router.
Next, by looking at the area summaries from these area border Again using Routers RT3 and RT4 as an example, the procedure
routers, RT3 and RT4 can determine the distance to all networks goes as follows: They first calculate the SPF tree for the
outside their area. These distances are then advertised backbone. This gives the distances to all other area border
internally to the area by RT3 and RT4. The advertisements that routers. Also noted are the distances to networks (Ia and Ib)
Router RT3 and RT4 will make into Area 1 are shown in Table 6. and AS boundary routers (RT5 and RT7) that belong to the
Note that Table 6 assumes that an area range has been configured backbone. This calculation is shown in Table 5.
for the backbone which groups Ia and Ib into a single LSA.
The information imported into Area 1 by Routers RT3 and RT4 Next, by looking at the area summaries from these area border
enables an internal router, such as RT1, to choose an area routers, RT3 and RT4 can determine the distance to all networks
border router intelligently. Router RT1 would use RT4 for 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.
dist from dist from The information imported into Area 1 by Routers RT3 and RT4
RT3 RT4 enables an internal router, such as RT1, to choose an area
__________________________________ border router intelligently. Router RT1 would use RT4 for
to RT3 * 21 traffic to Network N6, RT3 for traffic to Network N10, and would
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 dist from dist from
by Routers RT3 and RT4. 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
Destination RT3 adv. RT4 adv. Table 5: Backbone distances calculated
_________________________________ by Routers RT3 and RT4.
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 Destination RT3 adv. RT4 adv.
by Routers RT3 and RT4. _________________________________
Ia,Ib 20 27
N6 16 15
N7 20 19
N8 18 18
N9-N11,H1 29 36
_________________________________
RT5 14 8
RT7 20 14
traffic to Network N6, RT3 for traffic to Network N10, and would Table 6: Destinations advertised into Area 1
load share between the two for traffic to Network N8. by Routers RT3 and RT4.
Router RT1 can also determine in this manner the shortest path load share between the two for traffic to Network N8.
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 Router RT1 can also determine in this manner the shortest path
will cause the backbone to become disconnected. Configuring a to the AS boundary routers RT5 and RT7. Then, by looking at RT5
virtual link between Routers RT7 and RT10 will give the backbone and RT7's AS-external-LSAs, Router RT1 can decide between RT5 or
more connectivity and more resistance to such failures. RT7 when sending to a destination in another Autonomous System
(one of the networks N12-N15).
3.5. IP subnetting support 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.
OSPF attaches an IP address mask to each advertised route. The 3.5. IP subnetting support
mask indicates the range of addresses being described by the
particular route. For example, a summary-LSA for the
destination 128.185.0.0 with a mask of 0xffff0000 actually is
describing a single route to the collection of destinations
128.185.0.0 - 128.185.255.255. Similarly, host routes are
always advertised with a mask of 0xffffffff, indicating the
presence of only a single destination.
Including the mask with each advertised destination enables the OSPF attaches an IP address mask to each advertised route. The
implementation of what is commonly referred to as variable- mask indicates the range of addresses being described by the
length subnetting. This means that a single IP class A, B, or C particular route. For example, a summary-LSA for the
network number can be broken up into many subnets of various destination 128.185.0.0 with a mask of 0xffff0000 actually is
sizes. For example, the network 128.185.0.0 could be broken up describing a single route to the collection of destinations
into 62 variable-sized subnets: 15 subnets of size 4K, 15 128.185.0.0 - 128.185.255.255. Similarly, host routes are
subnets of size 256, and 32 subnets of size 8. Table 7 shows always advertised with a mask of 0xffffffff, indicating the
some of the resulting network addresses together with their presence of only a single destination.
masks.
Network address IP address mask Subnet size Including the mask with each advertised destination enables the
_______________________________________________ implementation of what is commonly referred to as variable-
128.185.16.0 0xfffff000 4K length subnetting. This means that a single IP class A, B, or C
128.185.1.0 0xffffff00 256 network number can be broken up into many subnets of various
128.185.0.8 0xfffffff8 8 sizes. For example, the network 128.185.0.0 could be broken up
into 62 variable-sized subnets: 15 subnets of size 4K, 15
subnets of size 256, and 32 subnets of size 8. Table 7 shows
some of the resulting network addresses together with their
masks.
Table 7: Some sample subnet sizes. Network address IP address mask Subnet size
_______________________________________________
128.185.16.0 0xfffff000 4K
128.185.1.0 0xffffff00 256
128.185.0.8 0xfffffff8 8
There are many possible ways of dividing up a class A, B, and C Table 7: Some sample subnet sizes.
network into variable sized subnets. The precise procedure for
doing so is beyond the scope of this specification. This
specification however establishes the following guideline: When
an IP packet is forwarded, it is always forwarded to the network
that is the best match for the packet's destination. Here best
match is synonymous with the longest or most specific match.
For example, the default route with destination of 0.0.0.0 and
mask 0x00000000 is always a match for every IP destination. Yet
it is always less specific than any other match. Subnet masks
must be assigned so that the best match for any IP destination
is unambiguous.
Attaching an address mask to each route also enables the support There are many possible ways of dividing up a class A, B, and C
of IP supernetting. For example, a single physical network network into variable sized subnets. The precise procedure for
segment could be assigned the [address,mask] pair doing so is beyond the scope of this specification. This
[192.9.4.0,0xfffffc00]. The segment would then be single IP specification however establishes the following guideline: When
network, containing addresses from the four consecutive class C an IP packet is forwarded, it is always forwarded to the network
network numbers 192.9.4.0 through 192.9.7.0. Such addressing is that is the best match for the packet's destination. Here best
now becoming commonplace with the advent of CIDR (see [Ref10]). match is synonymous with the longest or most specific match.
For example, the default route with destination of 0.0.0.0 and
mask 0x00000000 is always a match for every IP destination. Yet
it is always less specific than any other match. Subnet masks
must be assigned so that the best match for any IP destination
is unambiguous.
In order to get better aggregation at area boundaries, area Attaching an address mask to each route also enables the support
address ranges can be employed (see Section C.2 for more of IP supernetting. For example, a single physical network
details). Each address range is defined as an [address,mask] segment could be assigned the [address,mask] pair
pair. Many separate networks may then be contained in a single [192.9.4.0,0xfffffc00]. The segment would then be single IP
address range, just as a subnetted network is composed of many network, containing addresses from the four consecutive class C
separate subnets. Area border routers then summarize the area network numbers 192.9.4.0 through 192.9.7.0. Such addressing is
contents (for distribution to the backbone) by advertising a now becoming commonplace with the advent of CIDR (see [Ref10]).
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 In order to get better aggregation at area boundaries, area
single OSPF area. In that case, a single address range could be address ranges can be employed (see Section C.2 for more
configured: a class A, B, or C network number along with its details). Each address range is defined as an [address,mask]
natural IP mask. Inside the area, any number of variable sized pair. Many separate networks may then be contained in a single
subnets could be defined. However, external to the area a address range, just as a subnetted network is composed of many
single route for the entire subnetted network would be separate subnets. Area border routers then summarize the area
distributed, hiding even the fact that the network is subnetted contents (for distribution to the backbone) by advertising a
at all. The cost of this route is the maximum of the set of single route for each address range. The cost of the route is
costs to the component subnets. 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 3.6. Supporting stub areas
In some Autonomous Systems, the majority of the link-state In some Autonomous Systems, the majority of the link-state
database may consist of AS-external-LSAs. An OSPF AS-external- database may consist of AS-external-LSAs. An OSPF AS-external-
LSA is usually flooded throughout the entire AS. However, OSPF LSA is usually flooded throughout the entire AS. However, OSPF
allows certain areas to be configured as "stub areas". AS- allows certain areas to be configured as "stub areas". AS-
external-LSAs are not flooded into/throughout stub areas; external-LSAs are not flooded into/throughout stub areas;
routing to AS external destinations in these areas is based on a routing to AS external destinations in these areas is based on a
(per-area) default only. This reduces the link-state database (per-area) default only. This reduces the link-state database
size, and therefore the memory requirements, for a stub area's size, and therefore the memory requirements, for a stub area's
internal routers. internal routers.
In order to take advantage of the OSPF stub area support, In order to take advantage of the OSPF stub area support,
default routing must be used in the stub area. This is default routing must be used in the stub area. This is
accomplished as follows. One or more of the stub area's area accomplished as follows. One or more of the stub area's area
border routers must advertise a default route into the stub area border routers must advertise a default route into the stub area
via summary-LSAs. These summary defaults are flooded throughout via summary-LSAs. These summary defaults are flooded throughout
the stub area, but no further. (For this reason these defaults the stub area, but no further. (For this reason these defaults
pertain only to the particular stub area). These summary pertain only to the particular stub area). These summary
default routes will be used for any destination that is not default routes will be used for any destination that is not
explicitly reachable by an intra-area or inter-area path (i.e., explicitly reachable by an intra-area or inter-area path (i.e.,
AS external destinations). AS external destinations).
An area can be configured as a stub when there is a single exit 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 point from the area, or when the choice of exit point need not
be made on a per-external-destination basis. For example, Area be made on a per-external-destination basis. For example, Area
3 in Figure 6 could be configured as a stub area, because all 3 in Figure 6 could be configured as a stub area, because all
external traffic must travel though its single area border external traffic must travel though its single area border
router RT11. If Area 3 were configured as a stub, Router RT11 router RT11. If Area 3 were configured as a stub, Router RT11
would advertise a default route for distribution inside Area 3 would advertise a default route for distribution inside Area 3
(in a summary-LSA), instead of flooding the AS-external-LSAs for (in a summary-LSA), instead of flooding the AS-external-LSAs for
Networks N12-N15 into/throughout the area. Networks N12-N15 into/throughout the area.
The OSPF protocol ensures that all routers belonging to an area The OSPF protocol ensures that all routers belonging to an area
agree on whether the area has been configured as a stub. This agree on whether the area has been configured as a stub. This
guarantees that no confusion will arise in the flooding of AS- guarantees that no confusion will arise in the flooding of AS-
external-LSAs. external-LSAs.
There are a couple of restrictions on the use of stub areas. There are a couple of restrictions on the use of stub areas.
Virtual links cannot be configured through stub areas. In Virtual links cannot be configured through stub areas. In
addition, AS boundary routers cannot be placed internal to stub addition, AS boundary routers cannot be placed internal to stub
areas. areas.
3.7. Partitions of areas 3.7. Partitions of areas
OSPF does not actively attempt to repair area partitions. When OSPF does not actively attempt to repair area partitions. When
an area becomes partitioned, each component simply becomes a an area becomes partitioned, each component simply becomes a
separate area. The backbone then performs routing between the separate area. The backbone then performs routing between the
new areas. Some destinations reachable via intra-area routing new areas. Some destinations reachable via intra-area routing
before the partition will now require inter-area routing. before the partition will now require inter-area routing.
However, in order to maintain full routing after the partition, However, in order to maintain full routing after the partition,
an address range must not be split across multiple components of an address range must not be split across multiple components of
the area partition. Also, the backbone itself must not the area partition. Also, the backbone itself must not
partition. If it does, parts of the Autonomous System will partition. If it does, parts of the Autonomous System will
become unreachable. Backbone partitions can be repaired by become unreachable. Backbone partitions can be repaired by
configuring virtual links (see Section 15). configuring virtual links (see Section 15).
Another way to think about area partitions is to look at the Another way to think about area partitions is to look at the
Autonomous System graph that was introduced in Section 2. Area Autonomous System graph that was introduced in Section 2. Area
IDs can be viewed as colors for the graph's edges.[1] Each edge 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- of the graph connects to a network, or is itself a point-to-
point network. In either case, the edge is colored with the point network. In either case, the edge is colored with the
network's Area ID. network's Area ID.
A group of edges, all having the same color, and interconnected A group of edges, all having the same color, and interconnected
by vertices, represents an area. If the topology of the by vertices, represents an area. If the topology of the
Autonomous System is intact, the graph will have several regions Autonomous System is intact, the graph will have several regions
of color, each color being a distinct Area ID. of color, each color being a distinct Area ID.
When the AS topology changes, one of the areas may become When the AS topology changes, one of the areas may become
partitioned. The graph of the AS will then have multiple partitioned. The graph of the AS will then have multiple
regions of the same color (Area ID). The routing in the regions of the same color (Area ID). The routing in the
Autonomous System will continue to function as long as these Autonomous System will continue to function as long as these
regions of same color are connected by the single backbone regions of same color are connected by the single backbone
region. region.
4. Functional Summary 4. Functional Summary
A separate copy of OSPF's basic routing algorithm runs in each area. A separate copy of OSPF's basic routing algorithm runs in each area.
Routers having interfaces to multiple areas run multiple copies of Routers having interfaces to multiple areas run multiple copies of
the algorithm. A brief summary of the routing algorithm follows. the algorithm. A brief summary of the routing algorithm follows.
When a router starts, it first initializes the routing protocol data When a router starts, it first initializes the routing protocol data
structures. The router then waits for indications from the lower- structures. The router then waits for indications from the lower-
level protocols that its interfaces are functional. level protocols that its interfaces are functional.
A router then uses the OSPF's Hello Protocol to acquire neighbors. A router then uses the OSPF's Hello Protocol to acquire neighbors.
The router sends Hello packets to its neighbors, and in turn The router sends Hello packets to its neighbors, and in turn
receives their Hello packets. On broadcast and point-to-point receives their Hello packets. On broadcast and point-to-point
networks, the router dynamically detects its neighboring routers by networks, the router dynamically detects its neighboring routers by
sending its Hello packets to the multicast address AllSPFRouters. sending its Hello packets to the multicast address AllSPFRouters.
On non-broadcast networks, some configuration information may be On non-broadcast networks, some configuration information may be
necessary in order to discover neighbors. On broadcast and NBMA necessary in order to discover neighbors. On broadcast and NBMA
networks the Hello Protocol also elects a Designated router for the networks the Hello Protocol also elects a Designated router for the
network. network.
The router will attempt to form adjacencies with some of its newly The router will attempt to form adjacencies with some of its newly
acquired neighbors. Link-state databases are synchronized between acquired neighbors. Link-state databases are synchronized between
pairs of adjacent routers. On broadcast and NBMA networks, the pairs of adjacent routers. On broadcast and NBMA networks, the
Designated Router determines which routers should become adjacent. Designated Router determines which routers should become adjacent.
Adjacencies control the distribution of routing information. Adjacencies control the distribution of routing information.
Routing updates are sent and received only on adjacencies. Routing updates are sent and received only on adjacencies.
A router periodically advertises its state, which is also called A router periodically advertises its state, which is also called
link state. Link state is also advertised when a router's state link state. Link state is also advertised when a router's state
changes. A router's adjacencies are reflected in the contents of changes. A router's adjacencies are reflected in the contents of
its LSAs. This relationship between adjacencies and link state its LSAs. This relationship between adjacencies and link state
allows the protocol to detect dead routers in a timely fashion. allows the protocol to detect dead routers in a timely fashion.
LSAs are flooded throughout the area. The flooding algorithm is LSAs are flooded throughout the area. The flooding algorithm is
reliable, ensuring that all routers in an area have exactly the same reliable, ensuring that all routers in an area have exactly the same
link-state database. This database consists of the collection of link-state database. This database consists of the collection of
LSAs originated by each router belonging to the area. From this LSAs originated by each router belonging to the area. From this
database each router calculates a shortest-path tree, with itself as database each router calculates a shortest-path tree, with itself as
root. This shortest-path tree in turn yields a routing table for root. This shortest-path tree in turn yields a routing table for
the protocol. the protocol.
4.1. Inter-area routing 4.1. Inter-area routing
The previous section described the operation of the protocol The previous section described the operation of the protocol
within a single area. For intra-area routing, no other routing within a single area. For intra-area routing, no other routing
information is pertinent. In order to be able to route to information is pertinent. In order to be able to route to
destinations outside of the area, the area border routers inject destinations outside of the area, the area border routers inject
additional routing information into the area. This additional additional routing information into the area. This additional
information is a distillation of the rest of the Autonomous information is a distillation of the rest of the Autonomous
System's topology. System's topology.
This distillation is accomplished as follows: Each area border This distillation is accomplished as follows: Each area border
router is by definition connected to the backbone. Each area router is by definition connected to the backbone. Each area
border router summarizes the topology of its attached non- border router summarizes the topology of its attached non-
backbone areas for transmission on the backbone, and hence to backbone areas for transmission on the backbone, and hence to
all other area border routers. An area border router then has all other area border routers. An area border router then has
complete topological information concerning the backbone, and complete topological information concerning the backbone, and
the area summaries from each of the other area border routers. the area summaries from each of the other area border routers.
From this information, the router calculates paths to all From this information, the router calculates paths to all
inter-area destinations. The router then advertises these paths inter-area destinations. The router then advertises these paths
into its attached areas. This enables the area's internal into its attached areas. This enables the area's internal
routers to pick the best exit router when forwarding traffic routers to pick the best exit router when forwarding traffic
inter-area destinations. inter-area destinations.
4.2. AS external routes 4.2. AS external routes
Routers that have information regarding other Autonomous Systems Routers that have information regarding other Autonomous Systems
can flood this information throughout the AS. This external can flood this information throughout the AS. This external
routing information is distributed verbatim to every routing information is distributed verbatim to every
participating router. There is one exception: external routing participating router. There is one exception: external routing
information is not flooded into "stub" areas (see Section 3.6). information is not flooded into "stub" areas (see Section 3.6).
To utilize external routing information, the path to all routers To utilize external routing information, the path to all routers
advertising external information must be known throughout the AS advertising external information must be known throughout the AS
(excepting the stub areas). For that reason, the locations of (excepting the stub areas). For that reason, the locations of
these AS boundary routers are summarized by the (non-stub) area these AS boundary routers are summarized by the (non-stub) area
border routers. border routers.
4.3. Routing protocol packets 4.3. Routing protocol packets
The OSPF protocol runs directly over IP, using IP protocol 89. The OSPF protocol runs directly over IP, using IP protocol 89.
OSPF does not provide any explicit fragmentation/reassembly OSPF does not provide any explicit fragmentation/reassembly
support. When fragmentation is necessary, IP support. When fragmentation is necessary, IP
fragmentation/reassembly is used. OSPF protocol packets have fragmentation/reassembly is used. OSPF protocol packets have
been designed so that large protocol packets can generally be been designed so that large protocol packets can generally be
split into several smaller protocol packets. This practice is split into several smaller protocol packets. This practice is
recommended; IP fragmentation should be avoided whenever recommended; IP fragmentation should be avoided whenever
possible. possible.
Routing protocol packets should always be sent with the IP TOS Routing protocol packets should always be sent with the IP TOS
field set to 0. If at all possible, routing protocol packets field set to 0. If at all possible, routing protocol packets
should be given preference over regular IP data traffic, both should be given preference over regular IP data traffic, both
when being sent and received. As an aid to accomplishing this, when being sent and received. As an aid to accomplishing this,
OSPF protocol packets should have their IP precedence field set OSPF protocol packets should have their IP precedence field set
to the value Internetwork Control (see [Ref5]). to the value Internetwork Control (see [Ref5]).
All OSPF protocol packets share a common protocol header that is All OSPF protocol packets share a common protocol header that is
described in Appendix A. The OSPF packet types are listed below described in Appendix A. The OSPF packet types are listed below
in Table 8. Their formats are also described in Appendix A. in Table 8. Their formats are also described in Appendix A.
Type Packet name Protocol function Type Packet name Protocol function
__________________________________________________________ __________________________________________________________
1 Hello Discover/maintain neighbors 1 Hello Discover/maintain neighbors
2 Database Description Summarize database contents 2 Database Description Summarize database contents
3 Link State Request Database download 3 Link State Request Database download
4 Link State Update Database update 4 Link State Update Database update
5 Link State Ack Flooding acknowledgment 5 Link State Ack Flooding acknowledgment
Table 8: OSPF packet types. Table 8: OSPF packet types.
OSPF's Hello protocol uses Hello packets to discover and OSPF's Hello protocol uses Hello packets to discover and
maintain neighbor relationships. The Database Description and maintain neighbor relationships. The Database Description and
Link State Request packets are used in the forming of Link State Request packets are used in the forming of
adjacencies. OSPF's reliable update mechanism is implemented by adjacencies. OSPF's reliable update mechanism is implemented by
the Link State Update and Link State Acknowledgment packets. the Link State Update and Link State Acknowledgment packets.
Each Link State Update packet carries a set of new link state Each Link State Update packet carries a set of new link state
advertisements (LSAs) one hop further away from their point of advertisements (LSAs) one hop further away from their point of
origination. A single Link State Update packet may contain the origination. A single Link State Update packet may contain the
LSAs of several routers. Each LSA is tagged with the ID of the LSAs of several routers. Each LSA is tagged with the ID of the
originating router and a checksum of its link state contents. originating router and a checksum of its link state contents.
Each LSA also has a type field; the different types of OSPF LSAs Each LSA also has a type field; the different types of OSPF LSAs
are listed below in Table 9. are listed below in Table 9.
OSPF routing packets (with the exception of Hellos) are sent OSPF routing packets (with the exception of Hellos) are sent
only over adjacencies. This means that all OSPF protocol only over adjacencies. This means that all OSPF protocol
packets travel a single IP hop, except those that are sent over packets travel a single IP hop, except those that are sent over
virtual adjacencies. The IP source address of an OSPF protocol virtual adjacencies. The IP source address of an OSPF protocol
packet is one end of a router adjacency, and the IP destination packet is one end of a router adjacency, and the IP destination
address is either the other end of the adjacency or an IP address is either the other end of the adjacency or an IP
multicast address. multicast address.
LS LSA LSA description 4.4. Basic implementation requirements
type name
________________________________________________________
1 Router-LSAs Originated by all routers.
This LSA describes
the collected states of the
router's interfaces to an
area. Flooded throughout a
single area only.
________________________________________________________
2 Network-LSAs Originated for broadcast
and NBMA networks by
the Designated Router. This
LSA contains the
list of routers connected
to the network. Flooded
throughout a single area only.
________________________________________________________
3,4 Summary-LSAs Originated by area border
routers, and flooded through-
out the LSA's associated
area. Each summary-LSA
describes a route to a
destination outside the area,
yet still inside the AS
(i.e., an inter-area route).
Type 3 summary-LSAs describe
routes to networks. Type 4
summary-LSAs describe
routes to AS boundary routers.
________________________________________________________
5 AS-external-LSAs Originated by AS boundary
routers, and flooded through-
out the AS. Each
AS-external-LSA describes
a route to a destination in
another Autonomous System.
Default routes for the AS can
also be described by
AS-external-LSAs.
Table 9: OSPF link state advertisements (LSAs). An implementation of OSPF requires the following pieces of
system support:
4.4. Basic implementation requirements Timers
Two different kind of timers are required. The first kind,
called "single shot timers", fire once and cause a protocol
event to be processed. The second kind, called "interval
timers", fire at continuous intervals. These are used for
the sending of packets at regular intervals. A good example
of this is the regular broadcast of Hello packets. The
granularity of both kinds of timers is one second.
An implementation of OSPF requires the following pieces of Interval timers should be implemented to avoid drift. In
system support: some router implementations, packet processing can affect
timer execution. When multiple routers are attached to a
single network, all doing broadcasts, this can lead to the
synchronization of routing packets (which should be
avoided). If timers cannot be implemented to avoid drift,
small random amounts should be added to/subtracted from the
interval timer at each firing.
Timers LS LSA LSA description
Two different kind of timers are required. The first kind, type name
called "single shot timers", fire once and cause a protocol ________________________________________________________
event to be processed. The second kind, called "interval 1 Router-LSAs Originated by all routers.
timers", fire at continuous intervals. These are used for This LSA describes
the sending of packets at regular intervals. A good example the collected states of the
of this is the regular broadcast of Hello packets. The router's interfaces to an
granularity of both kinds of timers is one second. area. Flooded throughout a
single area only.
________________________________________________________
2 Network-LSAs Originated for broadcast
and NBMA networks by
the Designated Router. This
LSA contains the
list of routers connected
to the network. Flooded
throughout a single area only.
________________________________________________________
3,4 Summary-LSAs Originated by area border
routers, and flooded through-
out the LSA's associated
area. Each summary-LSA
describes a route to a
destination outside the area,
yet still inside the AS
(i.e., an inter-area route).
Type 3 summary-LSAs describe
routes to networks. Type 4
summary-LSAs describe
routes to AS boundary routers.
________________________________________________________
5 AS-external-LSAs Originated by AS boundary
routers, and flooded through-
out the AS. Each
AS-external-LSA describes
a route to a destination in
another Autonomous System.
Default routes for the AS can
also be described by
AS-external-LSAs.
Interval timers should be implemented to avoid drift. In Table 9: OSPF link state advertisements (LSAs).
some router implementations, packet processing can affect
timer execution. When multiple routers are attached to a
single network, all doing broadcasts, this can lead to the
synchronization of routing packets (which should be
avoided). If timers cannot be implemented to avoid drift,
small random amounts should be added to/subtracted from the
interval timer at each firing.
IP multicast IP multicast
Certain OSPF packets take the form of IP multicast Certain OSPF packets take the form of IP multicast
datagrams. Support for receiving and sending IP multicast datagrams. Support for receiving and sending IP multicast
datagrams, along with the appropriate lower-level protocol datagrams, along with the appropriate lower-level protocol
support, is required. The IP multicast datagrams used by support, is required. The IP multicast datagrams used by
OSPF never travel more than one hop. For this reason, the OSPF never travel more than one hop. For this reason, the
ability to forward IP multicast datagrams is not required. ability to forward IP multicast datagrams is not required.
For information on IP multicast, see [Ref7]. For information on IP multicast, see [Ref7].
Variable-length subnet support Variable-length subnet support
The router's IP protocol support must include the ability to The router's IP protocol support must include the ability to
divide a single IP class A, B, or C network number into many divide a single IP class A, B, or C network number into many
subnets of various sizes. This is commonly called subnets of various sizes. This is commonly called
variable-length subnetting; see Section 3.5 for details. variable-length subnetting; see Section 3.5 for details.
IP supernetting support IP supernetting support
The router's IP protocol support must include the ability to The router's IP protocol support must include the ability to
aggregate contiguous collections of IP class A, B, and C aggregate contiguous collections of IP class A, B, and C
networks into larger quantities called supernets. networks into larger quantities called supernets.
Supernetting has been proposed as one way to improve the Supernetting has been proposed as one way to improve the
scaling of IP routing in the worldwide Internet. For more scaling of IP routing in the worldwide Internet. For more
information on IP supernetting, see [Ref10]. information on IP supernetting, see [Ref10].
Lower-level protocol support Lower-level protocol support
The lower level protocols referred to here are the network The lower level protocols referred to here are the network
access protocols, such as the Ethernet data link layer. access protocols, such as the Ethernet data link layer.
Indications must be passed from these protocols to OSPF as Indications must be passed from these protocols to OSPF as
the network interface goes up and down. For example, on an the network interface goes up and down. For example, on an
ethernet it would be valuable to know when the ethernet ethernet it would be valuable to know when the ethernet
transceiver cable becomes unplugged. transceiver cable becomes unplugged.
Non-broadcast lower-level protocol support Non-broadcast lower-level protocol support
On non-broadcast networks, the OSPF Hello Protocol can be On non-broadcast networks, the OSPF Hello Protocol can be
aided by providing an indication when an attempt is made to aided by providing an indication when an attempt is made to
send a packet to a dead or non-existent router. For send a packet to a dead or non-existent router. For
example, on an X.25 PDN a dead neighboring router may be example, on an X.25 PDN a dead neighboring router may be
indicated by the reception of a X.25 clear with an indicated by the reception of a X.25 clear with an
appropriate cause and diagnostic, and this information would appropriate cause and diagnostic, and this information would
be passed to OSPF. be passed to OSPF.
List manipulation primitives List manipulation primitives
Much of the OSPF functionality is described in terms of its Much of the OSPF functionality is described in terms of its
operation on lists of LSAs. For example, the collection of operation on lists of LSAs. For example, the collection of
LSAs that will be retransmitted to an adjacent router until LSAs that will be retransmitted to an adjacent router until
acknowledged are described as a list. Any particular LSA acknowledged are described as a list. Any particular LSA
may be on many such lists. An OSPF implementation needs to may be on many such lists. An OSPF implementation needs to
be able to manipulate these lists, adding and deleting be able to manipulate these lists, adding and deleting
constituent LSAs as necessary. constituent LSAs as necessary.
Tasking support Tasking support
Certain procedures described in this specification invoke Certain procedures described in this specification invoke
other procedures. At times, these other procedures should other procedures. At times, these other procedures should
be executed in-line, that is, before the current procedure be executed in-line, that is, before the current procedure
is finished. This is indicated in the text by instructions is finished. This is indicated in the text by instructions
to execute a procedure. At other times, the other to execute a procedure. At other times, the other
procedures are to be executed only when the current procedures are to be executed only when the current
procedure has finished. This is indicated by instructions procedure has finished. This is indicated by instructions
to schedule a task. to schedule a task.
4.5. Optional OSPF capabilities 4.5. Optional OSPF capabilities
The OSPF protocol defines several optional capabilities. A The OSPF protocol defines several optional capabilities. A
router indicates the optional capabilities that it supports in router indicates the optional capabilities that it supports in
its OSPF Hello packets, Database Description packets and in its its OSPF Hello packets, Database Description packets and in its
LSAs. This enables routers supporting a mix of optional LSAs. This enables routers supporting a mix of optional
capabilities to coexist in a single Autonomous System. capabilities to coexist in a single Autonomous System.
Some capabilities must be supported by all routers attached to a Some capabilities must be supported by all routers attached to a
specific area. In this case, a router will not accept a specific area. In this case, a router will not accept a
neighbor's Hello Packet unless there is a match in reported neighbor's Hello Packet unless there is a match in reported
capabilities (i.e., a capability mismatch prevents a neighbor capabilities (i.e., a capability mismatch prevents a neighbor
relationship from forming). An example of this is the relationship from forming). An example of this is the
ExternalRoutingCapability (see below). ExternalRoutingCapability (see below).
Other capabilities can be negotiated during the Database Other capabilities can be negotiated during the Database
Exchange process. This is accomplished by specifying the Exchange process. This is accomplished by specifying the
optional capabilities in Database Description packets. A optional capabilities in Database Description packets. A
capability mismatch with a neighbor in this case will result in capability mismatch with a neighbor in this case will result in
only a subset of the link state database being exchanged between only a subset of the link state database being exchanged between
the two neighbors. the two neighbors.
The routing table build process can also be affected by the The routing table build process can also be affected by the
presence/absence of optional capabilities. For example, since presence/absence of optional capabilities. For example, since
the optional capabilities are reported in LSAs, routers the optional capabilities are reported in LSAs, routers
incapable of certain functions can be avoided when building the incapable of certain functions can be avoided when building the
shortest path tree. shortest path tree.
The OSPF optional capabilities defined in this memo are listed The OSPF optional capabilities defined in this memo are listed
below. See Section A.2 for more information. below. See Section A.2 for more information.
ExternalRoutingCapability ExternalRoutingCapability
Entire OSPF areas can be configured as "stubs" (see Section Entire OSPF areas can be configured as "stubs" (see Section
3.6). AS-external-LSAs will not be flooded into stub areas. 3.6). AS-external-LSAs will not be flooded into stub areas.
This capability is represented by the E-bit in the OSPF This capability is represented by the E-bit in the OSPF
Options field (see Section A.2). In order to ensure Options field (see Section A.2). In order to ensure
consistent configuration of stub areas, all routers consistent configuration of stub areas, all routers
interfacing to such an area must have the E-bit clear in interfacing to such an area must have the E-bit clear in
their Hello packets (see Sections 9.5 and 10.5). their Hello packets (see Sections 9.5 and 10.5).
5. Protocol Data Structures 5. Protocol Data Structures
The OSPF protocol is described herein in terms of its operation on The OSPF protocol is described herein in terms of its operation on
various protocol data structures. The following list comprises the various protocol data structures. The following list comprises the
top-level OSPF data structures. Any initialization that needs to be top-level OSPF data structures. Any initialization that needs to be
done is noted. OSPF areas, interfaces and neighbors also have done is noted. OSPF areas, interfaces and neighbors also have
associated data structures that are described later in this associated data structures that are described later in this
specification. specification.
Router ID Router ID
A 32-bit number that uniquely identifies this router in the AS. A 32-bit number that uniquely identifies this router in the AS.
One possible implementation strategy would be to use the One possible implementation strategy would be to use the
smallest IP interface address belonging to the router. If a smallest IP interface address belonging to the router. If a
router's OSPF Router ID is changed, the router's OSPF software router's OSPF Router ID is changed, the router's OSPF software
should be restarted before the new Router ID takes effect. In should be restarted before the new Router ID takes effect. In
this case the router should flush its self-originated LSAs from this case the router should flush its self-originated LSAs from
the routing domain (see Section 14.1) before restarting, or they the routing domain (see Section 14.1) before restarting, or they
will persist for up to MaxAge minutes. will persist for up to MaxAge minutes.
Area structures Area structures
Each one of the areas to which the router is connected has its Each one of the areas to which the router is connected has its
own data structure. This data structure describes the working own data structure. This data structure describes the working
of the basic OSPF algorithm. Remember that each area runs a of the basic OSPF algorithm. Remember that each area runs a
separate copy of the basic OSPF algorithm. separate copy of the basic OSPF algorithm.
Backbone (area) structure Backbone (area) structure
The OSPF backbone area is responsible for the dissemination of The OSPF backbone area is responsible for the dissemination of
inter-area routing information. inter-area routing information.
Virtual links configured Virtual links configured
The virtual links configured with this router as one endpoint. The virtual links configured with this router as one endpoint.
In order to have configured virtual links, the router itself In order to have configured virtual links, the router itself
must be an area border router. Virtual links are identified by must be an area border router. Virtual links are identified by
the Router ID of the other endpoint -- which is another area the Router ID of the other endpoint -- which is another area
border router. These two endpoint routers must be attached to a border router. These two endpoint routers must be attached to a
common area, called the virtual link's Transit area. Virtual common area, called the virtual link's Transit area. Virtual
links are part of the backbone, and behave as if they were links are part of the backbone, and behave as if they were
unnumbered point-to-point networks between the two routers. A unnumbered point-to-point networks between the two routers. A
virtual link uses the intra-area routing of its Transit area to virtual link uses the intra-area routing of its Transit area to
forward packets. Virtual links are brought up and down through forward packets. Virtual links are brought up and down through
the building of the shortest-path trees for the Transit area. the building of the shortest-path trees for the Transit area.
List of external routes List of external routes
These are routes to destinations external to the Autonomous These are routes to destinations external to the Autonomous
System, that have been gained either through direct experience System, that have been gained either through direct experience
with another routing protocol (such as BGP), or through with another routing protocol (such as BGP), or through
configuration information, or through a combination of the two configuration information, or through a combination of the two
(e.g., dynamic external information to be advertised by OSPF (e.g., dynamic external information to be advertised by OSPF
with configured metric). Any router having these external routes with configured metric). Any router having these external routes
is called an AS boundary router. These routes are advertised by is called an AS boundary router. These routes are advertised by
the router into the OSPF routing domain via AS-external-LSAs. the router into the OSPF routing domain via AS-external-LSAs.
List of AS-external-LSAs List of AS-external-LSAs
Part of the link-state database. These have originated from the Part of the link-state database. These have originated from the
AS boundary routers. They comprise routes to destinations AS boundary routers. They comprise routes to destinations
external to the Autonomous System. Note that, if the router is external to the Autonomous System. Note that, if the router is
itself an AS boundary router, some of these AS-external-LSAs itself an AS boundary router, some of these AS-external-LSAs
have been self-originated. 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.
Figure 9 shows the collection of data structures present in a The routing table
typical router. The router pictured is RT10, from the map in Figure Derived from the link-state database. Each entry in the routing
6. Note that Router RT10 has a virtual link configured to Router table is indexed by a destination, and contains the
RT11, with Area 2 as the link's Transit area. This is indicated by destination's cost and a set of paths to use in forwarding
the dashed line in Figure 9. When the virtual link becomes active, packets to the destination. A path is described by its type and
through the building of the shortest path tree for Area 2, it next hop. For more information, see Section 11.
becomes an interface to the backbone (see the two backbone
interfaces depicted in Figure 9).
+----+ Figure 9 shows the collection of data structures present in a
|RT10|------+ typical router. The router pictured is RT10, from the map in Figure
+----+ \+-------------+ 6. Note that Router RT10 has a virtual link configured to Router
/ \ |Routing Table| 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
|Area 2|---+ +---|Backbone| interfaces depicted in Figure 9).
+------+***********+ +--------+
/ \ * / \
/ \ * / \
+---------+ +---------+ +------------+ +------------+
|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
6. The Area Data Structure
The area data structure contains all the information used to run the The area data structure contains all the information used to run the
basic OSPF routing algorithm. Each area maintains its own link-state basic OSPF routing algorithm. Each area maintains its own link-state
database. A network belongs to a single area, and a router interface database. A network belongs to a single area, and a router interface
connects to a single area. Each router adjacency also belongs to a connects to a single area. Each router adjacency also belongs to a
single area. single area.
The OSPF backbone is the special OSPF area responsible for The OSPF backbone is the special OSPF area responsible for
disseminating inter-area routing information. disseminating inter-area routing information.
The area link-state database consists of the collection of router- The area link-state database consists of the collection of router-
LSAs, network-LSAs and summary-LSAs that have originated from the LSAs, network-LSAs and summary-LSAs that have originated from the
area's routers. This information is flooded throughout a single area's routers. This information is flooded throughout a single
area only. The list of AS-external-LSAs (see Section 5) is also area only. The list of AS-external-LSAs (see Section 5) is also
considered to be part of each area's link-state database. considered to be part of each area's link-state database.
Area ID Area ID
A 32-bit number identifying the area. The Area ID of 0.0.0.0 is A 32-bit number identifying the area. The Area ID of 0.0.0.0 is
reserved for the backbone. reserved for the backbone.
List of area address ranges List of area address ranges
In order to aggregate routing information at area boundaries, In order to aggregate routing information at area boundaries,
area address ranges can be employed. Each address range is area address ranges can be employed. Each address range is
specified by an [address,mask] pair and a status indication of specified by an [address,mask] pair and a status indication of
either Advertise or DoNotAdvertise (see Section 12.4.3). either Advertise or DoNotAdvertise (see Section 12.4.3).
+----+
|RT10|------+
+----+ \+-------------+
/ \ |Routing Table|
/ \ +-------------+
/ \
+------+ / \ +--------+
|Area 2|---+ +---|Backbone|
+------+***********+ +--------+
/ \ * / \
/ \ * / \
+---------+ +---------+ +------------+ +------------+
|Interface| |Interface| |Virtual Link| |Interface Ib|
| to N6 | | to N8 | | to RT11 | +------------+
+---------+ +---------+ +------------+ |
/ \ | | |
/ \ | | |
+--------+ +--------+ | +-------------+ +------------+
|Neighbor| |Neighbor| | |Neighbor RT11| |Neighbor RT6|
| RT8 | | RT7 | | +-------------+ +------------+
+--------+ +--------+ |
|
+-------------+
|Neighbor RT11|
+-------------+
Figure 9: Router RT10's Data structures
Associated router interfaces Associated router interfaces
This router's interfaces connecting to the area. A router This router's interfaces connecting to the area. A router
interface belongs to one and only one area (or the backbone). interface belongs to one and only one area (or the backbone).
For the backbone area this list includes all the virtual links. For the backbone area this list includes all the virtual links.
A virtual link is identified by the Router ID of its other A virtual link is identified by the Router ID of its other
endpoint; its cost is the cost of the shortest intra-area path endpoint; its cost is the cost of the shortest intra-area path
through the Transit area that exists between the two routers. through the Transit area that exists between the two routers.
List of router-LSAs List of router-LSAs
A router-LSA is generated by each router in the area. It A router-LSA is generated by each router in the area. It
describes the state of the router's interfaces to the area. describes the state of the router's interfaces to the area.
List of network-LSAs List of network-LSAs
One network-LSA is generated for each transit broadcast and NBMA One network-LSA is generated for each transit broadcast and NBMA
network in the area. A network-LSA describes the set of routers network in the area. A network-LSA describes the set of routers
currently connected to the network. currently connected to the network.
List of summary-LSAs List of summary-LSAs
Summary-LSAs originate from the area's area border routers. Summary-LSAs originate from the area's area border routers.
They describe routes to destinations internal to the Autonomous They describe routes to destinations internal to the Autonomous
System, yet external to the area (i.e., inter-area System, yet external to the area (i.e., inter-area
destinations). destinations).
Shortest-path tree Shortest-path tree
The shortest-path tree for the area, with this router itself as The shortest-path tree for the area, with this router itself as
root. Derived from the collected router-LSAs and network-LSAs root. Derived from the collected router-LSAs and network-LSAs
by the Dijkstra algorithm (see Section 16.1). by the Dijkstra algorithm (see Section 16.1).
TransitCapability TransitCapability
This parameter indicates whether the area can carry data traffic This parameter indicates whether the area can carry data traffic
that neither originates nor terminates in the area itself. This that neither originates nor terminates in the area itself. This
parameter is calculated when the area's shortest-path tree is parameter is calculated when the area's shortest-path tree is
built (see Section 16.1, where TransitCapability is set to TRUE built (see Section 16.1, where TransitCapability is set to TRUE
if and only if there are one or more fully adjacent virtual 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 links using the area as Transit area), and is used as an input
to a subsequent step of the routing table build process (see to a subsequent step of the routing table build process (see
Section 16.3). When an area's TransitCapability is set to TRUE, Section 16.3). When an area's TransitCapability is set to TRUE,
the area is said to be a "transit area". the area is said to be a "transit area".
ExternalRoutingCapability ExternalRoutingCapability
Whether AS-external-LSAs will be flooded into/throughout the Whether AS-external-LSAs will be flooded into/throughout the
area. This is a configurable parameter. If AS-external-LSAs area. This is a configurable parameter. If AS-external-LSAs
are excluded from the area, the area is called a "stub". Within are excluded from the area, the area is called a "stub". Within
stub areas, routing to AS external destinations will be based stub areas, routing to AS external destinations will be based
solely on a default summary route. The backbone cannot be solely on a default summary route. The backbone cannot be
configured as a stub area. Also, virtual links cannot be configured as a stub area. Also, virtual links cannot be
configured through stub areas. For more information, see configured through stub areas. For more information, see
Section 3.6. Section 3.6.
StubDefaultCost StubDefaultCost
If the area has been configured as a stub area, and the router If the area has been configured as a stub area, and the router
itself is an area border router, then the StubDefaultCost itself is an area border router, then the StubDefaultCost
indicates the cost of the default summary-LSA that the router indicates the cost of the default summary-LSA that the router
should advertise into the area. See Section 12.4.3 for more should advertise into the area. See Section 12.4.3 for more
information. information.
Unless otherwise specified, the remaining sections of this document Unless otherwise specified, the remaining sections of this document
refer to the operation of the OSPF protocol within a single area. refer to the operation of the OSPF protocol within a single area.
7. Bringing Up Adjacencies 7. Bringing Up Adjacencies
OSPF creates adjacencies between neighboring routers for the purpose OSPF creates adjacencies between neighboring routers for the purpose
of exchanging routing information. Not every two neighboring of exchanging routing information. Not every two neighboring
routers will become adjacent. This section covers the generalities routers will become adjacent. This section covers the generalities
involved in creating adjacencies. For further details consult involved in creating adjacencies. For further details consult
Section 10. Section 10.
7.1. The Hello Protocol 7.1. The Hello Protocol
The Hello Protocol is responsible for establishing and The Hello Protocol is responsible for establishing and
maintaining neighbor relationships. It also ensures that maintaining neighbor relationships. It also ensures that
communication between neighbors is bidirectional. Hello packets communication between neighbors is bidirectional. Hello packets
are sent periodically out all router interfaces. Bidirectional are sent periodically out all router interfaces. Bidirectional
communication is indicated when the router sees itself listed in communication is indicated when the router sees itself listed in
the neighbor's Hello Packet. On broadcast and NBMA networks, the neighbor's Hello Packet. On broadcast and NBMA networks,
the Hello Protocol elects a Designated Router for the network. the Hello Protocol elects a Designated Router for the network.
The Hello Protocol works differently on broadcast networks, NBMA The Hello Protocol works differently on broadcast networks, NBMA
networks and Point-to-MultiPoint networks. On broadcast networks and Point-to-MultiPoint networks. On broadcast
networks, each router advertises itself by periodically networks, each router advertises itself by periodically
multicasting Hello Packets. This allows neighbors to be multicasting Hello Packets. This allows neighbors to be
discovered dynamically. These Hello Packets contain the discovered dynamically. These Hello Packets contain the
router's view of the Designated Router's identity, and the list router's view of the Designated Router's identity, and the list
of routers whose Hello Packets have been seen recently. of routers whose Hello Packets have been seen recently.
On NBMA networks some configuration information may be necessary On NBMA networks some configuration information may be necessary
for the operation of the Hello Protocol. Each router that may for the operation of the Hello Protocol. Each router that may
potentially become Designated Router has a list of all other potentially become Designated Router has a list of all other
routers attached to the network. A router, having Designated routers attached to the network. A router, having Designated
Router potential, sends Hello Packets to all other potential Router potential, sends Hello Packets to all other potential
Designated Routers when its interface to the NBMA network first Designated Routers when its interface to the NBMA network first
becomes operational. This is an attempt to find the Designated becomes operational. This is an attempt to find the Designated
Router for the network. If the router itself is elected Router for the network. If the router itself is elected
Designated Router, it begins sending Hello Packets to all other Designated Router, it begins sending Hello Packets to all other
routers attached to the network. routers attached to the network.
On Point-to-MultiPoint networks, a router sends Hello Packets to On Point-to-MultiPoint networks, a router sends Hello Packets to
all neighbors with which it can communicate directly. These all neighbors with which it can communicate directly. These
neighbors may be discovered dynamically through a protocol such neighbors may be discovered dynamically through a protocol such
as Inverse ARP (see [Ref14]), or they may be configured. as Inverse ARP (see [Ref14]), or they may be configured.
After a neighbor has been discovered, bidirectional After a neighbor has been discovered, bidirectional
communication ensured, and (if on a broadcast or NBMA network) a communication ensured, and (if on a broadcast or NBMA network) a
Designated Router elected, a decision is made regarding whether Designated Router elected, a decision is made regarding whether
or not an adjacency should be formed with the neighbor (see or not an adjacency should be formed with the neighbor (see
Section 10.4). If an adjacency is to be formed, the first step Section 10.4). If an adjacency is to be formed, the first step
is to synchronize the neighbors' link-state databases. This is is to synchronize the neighbors' link-state databases. This is
covered in the next section. covered in the next section.
7.2. The Synchronization of Databases 7.2. The Synchronization of Databases
In a link-state routing algorithm, it is very important for all In a link-state routing algorithm, it is very important for all
routers' link-state databases to stay synchronized. OSPF routers' link-state databases to stay synchronized. OSPF
simplifies this by requiring only adjacent routers to remain simplifies this by requiring only adjacent routers to remain
synchronized. The synchronization process begins as soon as the synchronized. The synchronization process begins as soon as the
routers attempt to bring up the adjacency. Each router routers attempt to bring up the adjacency. Each router
describes its database by sending a sequence of Database describes its database by sending a sequence of Database
Description packets to its neighbor. Each Database Description Description packets to its neighbor. Each Database Description
Packet describes a set of LSAs belonging to the router's Packet describes a set of LSAs belonging to the router's
database. When the neighbor sees an LSA that is more recent database. When the neighbor sees an LSA that is more recent
than its own database copy, it makes a note that this newer LSA than its own database copy, it makes a note that this newer LSA
should be requested. should be requested.
This sending and receiving of Database Description packets is This sending and receiving of Database Description packets is
called the "Database Exchange Process". During this process, called the "Database Exchange Process". During this process,
the two routers form a master/slave relationship. Each Database the two routers form a master/slave relationship. Each Database
Description Packet has a sequence number. Database Description Description Packet has a sequence number. Database Description
Packets sent by the master (polls) are acknowledged by the slave Packets sent by the master (polls) are acknowledged by the slave
through echoing of the sequence number. Both polls and their through echoing of the sequence number. Both polls and their
responses contain summaries of link state data. The master is responses contain summaries of link state data. The master is
the only one allowed to retransmit Database Description Packets. the only one allowed to retransmit Database Description Packets.
It does so only at fixed intervals, the length of which is the It does so only at fixed intervals, the length of which is the
configured per-interface constant RxmtInterval. configured per-interface constant RxmtInterval.
Each Database Description contains an indication that there are Each Database Description contains an indication that there are
more packets to follow --- the M-bit. The Database Exchange more packets to follow --- the M-bit. The Database Exchange
Process is over when a router has received and sent Database Process is over when a router has received and sent Database
Description Packets with the M-bit off. Description Packets with the M-bit off.
During and after the Database Exchange Process, each router has During and after the Database Exchange Process, each router has
a list of those LSAs for which the neighbor has more up-to-date a list of those LSAs for which the neighbor has more up-to-date
instances. These LSAs are requested in Link State Request instances. These LSAs are requested in Link State Request
Packets. Link State Request packets that are not satisfied are Packets. Link State Request packets that are not satisfied are
retransmitted at fixed intervals of time RxmtInterval. When the retransmitted at fixed intervals of time RxmtInterval. When the
Database Description Process has completed and all Link State Database Description Process has completed and all Link State
Requests have been satisfied, the databases are deemed Requests have been satisfied, the databases are deemed
synchronized and the routers are marked fully adjacent. At this synchronized and the routers are marked fully adjacent. At this
time the adjacency is fully functional and is advertised in the time the adjacency is fully functional and is advertised in the
two routers' router-LSAs. two routers' router-LSAs.
The adjacency is used by the flooding procedure as soon as the The adjacency is used by the flooding procedure as soon as the
Database Exchange Process begins. This simplifies database Database Exchange Process begins. This simplifies database
synchronization, and guarantees that it finishes in a synchronization, and guarantees that it finishes in a
predictable period of time. predictable period of time.
7.3. The Designated Router 7.3. The Designated Router
Every broadcast and NBMA network has a Designated Router. The Every broadcast and NBMA network has a Designated Router. The
Designated Router performs two main functions for the routing Designated Router performs two main functions for the routing
protocol: protocol:
o The Designated Router originates a network-LSA on behalf of o The Designated Router originates a network-LSA on behalf of
the network. This LSA lists the set of routers (including the network. This LSA lists the set of routers (including
the Designated Router itself) currently attached to the the Designated Router itself) currently attached to the
network. The Link State ID for this LSA (see Section network. The Link State ID for this LSA (see Section
12.1.4) is the IP interface address of the Designated 12.1.4) is the IP interface address of the Designated
Router. The IP network number can then be obtained by using Router. The IP network number can then be obtained by using
the network's subnet/network mask. the network's subnet/network mask.
o The Designated Router becomes adjacent to all other routers o The Designated Router becomes adjacent to all other routers
on the network. Since the link state databases are on the network. Since the link state databases are
synchronized across adjacencies (through adjacency bring-up synchronized across adjacencies (through adjacency bring-up
and then the flooding procedure), the Designated Router and then the flooding procedure), the Designated Router
plays a central part in the synchronization process. plays a central part in the synchronization process.
The Designated Router is elected by the Hello Protocol. A The Designated Router is elected by the Hello Protocol. A
router's Hello Packet contains its Router Priority, which is router's Hello Packet contains its Router Priority, which is
configurable on a per-interface basis. In general, when a configurable on a per-interface basis. In general, when a
router's interface to a network first becomes functional, it router's interface to a network first becomes functional, it
checks to see whether there is currently a Designated Router for checks to see whether there is currently a Designated Router for
the network. If there is, it accepts that Designated Router, the network. If there is, it accepts that Designated Router,
regardless of its Router Priority. (This makes it harder to regardless of its Router Priority. (This makes it harder to
predict the identity of the Designated Router, but ensures that predict the identity of the Designated Router, but ensures that
the Designated Router changes less often. See below.) the Designated Router changes less often. See below.)
Otherwise, the router itself becomes Designated Router if it has Otherwise, the router itself becomes Designated Router if it has
the highest Router Priority on the network. A more detailed the highest Router Priority on the network. A more detailed
(and more accurate) description of Designated Router election is (and more accurate) description of Designated Router election is
presented in Section 9.4. presented in Section 9.4.
The Designated Router is the endpoint of many adjacencies. In The Designated Router is the endpoint of many adjacencies. In
order to optimize the flooding procedure on broadcast networks, order to optimize the flooding procedure on broadcast networks,
the Designated Router multicasts its Link State Update Packets the Designated Router multicasts its Link State Update Packets
to the address AllSPFRouters, rather than sending separate to the address AllSPFRouters, rather than sending separate
packets over each adjacency. packets over each adjacency.
Section 2 of this document discusses the directed graph Section 2 of this document discusses the directed graph
representation of an area. Router nodes are labelled with their representation of an area. Router nodes are labelled with their
Router ID. Transit network nodes are actually labelled with the Router ID. Transit network nodes are actually labelled with the
IP address of their Designated Router. It follows that when the IP address of their Designated Router. It follows that when the
Designated Router changes, it appears as if the network node on Designated Router changes, it appears as if the network node on
the graph is replaced by an entirely new node. This will cause the graph is replaced by an entirely new node. This will cause
the network and all its attached routers to originate new LSAs. the network and all its attached routers to originate new LSAs.
Until the link-state databases again converge, some temporary Until the link-state databases again converge, some temporary
loss of connectivity may result. This may result in ICMP loss of connectivity may result. This may result in ICMP
unreachable messages being sent in response to data traffic. unreachable messages being sent in response to data traffic.
For that reason, the Designated Router should change only For that reason, the Designated Router should change only
infrequently. Router Priorities should be configured so that infrequently. Router Priorities should be configured so that
the most dependable router on a network eventually becomes the most dependable router on a network eventually becomes
Designated Router. Designated Router.
7.4. The Backup Designated Router 7.4. The Backup Designated Router
In order to make the transition to a new Designated Router In order to make the transition to a new Designated Router
smoother, there is a Backup Designated Router for each broadcast smoother, there is a Backup Designated Router for each broadcast
and NBMA network. The Backup Designated Router is also adjacent and NBMA network. The Backup Designated Router is also adjacent
to all routers on the network, and becomes Designated Router to all routers on the network, and becomes Designated Router
when the previous Designated Router fails. If there were no when the previous Designated Router fails. If there were no
Backup Designated Router, when a new Designated Router became Backup Designated Router, when a new Designated Router became
necessary, new adjacencies would have to be formed between the necessary, new adjacencies would have to be formed between the
new Designated Router and all other routers attached to the new Designated Router and all other routers attached to the
network. Part of the adjacency forming process is the network. Part of the adjacency forming process is the
synchronizing of link-state databases, which can potentially synchronizing of link-state databases, which can potentially
take quite a long time. During this time, the network would not take quite a long time. During this time, the network would not
be available for transit data traffic. The Backup Designated be available for transit data traffic. The Backup Designated
obviates the need to form these adjacencies, since they already obviates the need to form these adjacencies, since they already
exist. This means the period of disruption in transit traffic exist. This means the period of disruption in transit traffic
lasts only as long as it takes to flood the new LSAs (which lasts only as long as it takes to flood the new LSAs (which
announce the new Designated Router). announce the new Designated Router).
The Backup Designated Router does not generate a network-LSA for The Backup Designated Router does not generate a network-LSA for
the network. (If it did, the transition to a new Designated the network. (If it did, the transition to a new Designated
Router would be even faster. However, this is a tradeoff Router would be even faster. However, this is a tradeoff
between database size and speed of convergence when the between database size and speed of convergence when the
Designated Router disappears.) Designated Router disappears.)
The Backup Designated Router is also elected by the Hello The Backup Designated Router is also elected by the Hello
Protocol. Each Hello Packet has a field that specifies the Protocol. Each Hello Packet has a field that specifies the
Backup Designated Router for the network. Backup Designated Router for the network.
In some steps of the flooding procedure, the Backup Designated In some steps of the flooding procedure, the Backup Designated
Router plays a passive role, letting the Designated Router do Router plays a passive role, letting the Designated Router do
more of the work. This cuts down on the amount of local routing more of the work. This cuts down on the amount of local routing
traffic. See Section 13.3 for more information. traffic. See Section 13.3 for more information.
7.5. The graph of adjacencies 7.5. The graph of adjacencies
An adjacency is bound to the network that the two routers have An adjacency is bound to the network that the two routers have
in common. If two routers have multiple networks in common, in common. If two routers have multiple networks in common,
they may have multiple adjacencies between them. they may have multiple adjacencies between them.
One can picture the collection of adjacencies on a network as One can picture the collection of adjacencies on a network as
forming an undirected graph. The vertices consist of routers, forming an undirected graph. The vertices consist of routers,
with an edge joining two routers if they are adjacent. The with an edge joining two routers if they are adjacent. The
graph of adjacencies describes the flow of routing protocol graph of adjacencies describes the flow of routing protocol
packets, and in particular Link State Update Packets, through packets, and in particular Link State Update Packets, through
the Autonomous System. the Autonomous System.
Two graphs are possible, depending on whether a Designated Two graphs are possible, depending on whether a Designated
Router is elected for the network. On physical point-to-point Router is elected for the network. On physical point-to-point
networks, Point-to-MultiPoint networks and virtual links, networks, Point-to-MultiPoint networks and virtual links,
neighboring routers become adjacent whenever they can neighboring routers become adjacent whenever they can
communicate directly. In contrast, on broadcast and NBMA communicate directly. In contrast, on broadcast and NBMA
networks only the Designated Router and the Backup Designated networks only the Designated Router and the Backup Designated
Router become adjacent to all other routers attached to the Router become adjacent to all other routers attached to the
network. network.
These graphs are shown in Figure 10. It is assumed that Router +---+ +---+
RT7 has become the Designated Router, and Router RT3 the Backup |RT1|------------|RT2| o---------------o
Designated Router, for the Network N2. The Backup Designated +---+ N1 +---+ RT1 RT2
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.
+---+ +---+ RT7
|RT1|------------|RT2| o---------------o o---------+
+---+ N1 +---+ RT1 RT2 +---+ +---+ +---+ /|\ |
|RT7| |RT3| |RT4| / | \ |
+---+ +---+ +---+ / | \ |
| | | / | \ |
+-----------------------+ RT5o RT6o oRT4 |
| | N2 * * * |
+---+ +---+ * * * |
|RT5| |RT6| * * * |
+---+ +---+ *** |
o---------+
RT3
RT7 Figure 10: The graph of adjacencies
o---------+
+---+ +---+ +---+ /|\ | These graphs are shown in Figure 10. It is assumed that Router
|RT7| |RT3| |RT4| / | \ | 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
+-----------------------+ RT5o RT6o oRT4 | than the Designated Router (see Section 13.3). This is the
| | N2 * * * | reason for the dashed lines connecting the Backup Designated
+---+ +---+ * * * | Router RT3.
|RT5| |RT6| * * * |
+---+ +---+ *** |
o---------+
RT3
Figure 10: The graph of adjacencies
8. Protocol Packet Processing 8. Protocol Packet Processing
This section discusses the general processing of OSPF routing This section discusses the general processing of OSPF routing
protocol packets. It is very important that the router link-state protocol packets. It is very important that the router link-state
databases remain synchronized. For this reason, routing protocol databases remain synchronized. For this reason, routing protocol
packets should get preferential treatment over ordinary data packets should get preferential treatment over ordinary data
packets, both in sending and receiving. packets, both in sending and receiving.
Routing protocol packets are sent along adjacencies only (with the Routing protocol packets are sent along adjacencies only (with the
exception of Hello packets, which are used to discover the exception of Hello packets, which are used to discover the
adjacencies). This means that all routing protocol packets travel a adjacencies). This means that all routing protocol packets travel a
single IP hop, except those sent over virtual links. single IP hop, except those sent over virtual links.
All routing protocol packets begin with a standard header. The All routing protocol packets begin with a standard header. The
sections below provide details on how to fill in and verify this sections below provide details on how to fill in and verify this
standard header. Then, for each packet type, the section giving standard header. Then, for each packet type, the section giving
more details on that particular packet type's processing is listed. more details on that particular packet type's processing is listed.
8.1. Sending protocol packets 8.1. Sending protocol packets
When a router sends a routing protocol packet, it fills in the When a router sends a routing protocol packet, it fills in the
fields of the standard OSPF packet header as follows. For more fields of the standard OSPF packet header as follows. For more
details on the header format consult Section A.3.1: details on the header format consult Section A.3.1:
Version # Version #
Set to 2, the version number of the protocol as documented Set to 2, the version number of the protocol as documented
in this specification. in this specification.
Packet type Packet type
The type of OSPF packet, such as Link state Update or Hello The type of OSPF packet, such as Link state Update or Hello
Packet. Packet.
Packet length Packet length
The length of the entire OSPF packet in bytes, including the The length of the entire OSPF packet in bytes, including the
standard OSPF packet header. standard OSPF packet header.
Router ID Router ID
The identity of the router itself (who is originating the The identity of the router itself (who is originating the
packet). packet).
Area ID Area ID
The OSPF area that the packet is being sent into. The OSPF area that the packet is being sent into.
Checksum Checksum
The standard IP 16-bit one's complement checksum of the The standard IP 16-bit one's complement checksum of the
entire OSPF packet, excluding the 64-bit authentication entire OSPF packet, excluding the 64-bit authentication
field. This checksum is calculated as part of the field. This checksum is calculated as part of the
appropriate authentication procedure; for some OSPF appropriate authentication procedure; for some OSPF
authentication types, the checksum calculation is omitted. authentication types, the checksum calculation is omitted.
See Section D.4 for details. See Section D.4 for details.
AuType and Authentication AuType and Authentication
Each OSPF packet exchange is authenticated. Authentication Each OSPF packet exchange is authenticated. Authentication
types are assigned by the protocol and are documented in types are assigned by the protocol and are documented in
Appendix D. A different authentication procedure can be Appendix D. A different authentication procedure can be
used for each IP network/subnet. Autype indicates the type used for each IP network/subnet. Autype indicates the type
of authentication procedure in use. The 64-bit of authentication procedure in use. The 64-bit
authentication field is then for use by the chosen authentication field is then for use by the chosen
authentication procedure. This procedure should be the last authentication procedure. This procedure should be the last
called when forming the packet to be sent. See Section D.4 called when forming the packet to be sent. See Section D.4
for details. for details.
The IP destination address for the packet is selected as The IP destination address for the packet is selected as
follows. On physical point-to-point networks, the IP follows. On physical point-to-point networks, the IP
destination is always set to the address AllSPFRouters. On all destination is always set to the address AllSPFRouters. On all
other network types (including virtual links), the majority of other network types (including virtual links), the majority of
OSPF packets are sent as unicasts, i.e., sent directly to the OSPF packets are sent as unicasts, i.e., sent directly to the
other end of the adjacency. In this case, the IP destination is other end of the adjacency. In this case, the IP destination is
just the Neighbor IP address associated with the other end of just the Neighbor IP address associated with the other end of
the adjacency (see Section 10). The only packets not sent as the adjacency (see Section 10). The only packets not sent as
unicasts are on broadcast networks; on these networks Hello unicasts are on broadcast networks; on these networks Hello
packets are sent to the multicast destination AllSPFRouters, the packets are sent to the multicast destination AllSPFRouters, the
Designated Router and its Backup send both Link State Update Designated Router and its Backup send both Link State Update
Packets and Link State Acknowledgment Packets to the multicast Packets and Link State Acknowledgment Packets to the multicast
address AllSPFRouters, while all other routers send both their address AllSPFRouters, while all other routers send both their
Link State Update and Link State Acknowledgment Packets to the Link State Update and Link State Acknowledgment Packets to the
multicast address AllDRouters. multicast address AllDRouters.
Retransmissions of Link State Update packets are ALWAYS sent Retransmissions of Link State Update packets are ALWAYS sent
directly to the neighbor. On multi-access networks, this means directly to the neighbor. On multi-access networks, this means
that retransmissions should be sent to the neighbor's IP that retransmissions should be sent to the neighbor's IP
address. address.
The IP source address should be set to the IP address of the The IP source address should be set to the IP address of the
sending interface. Interfaces to unnumbered point-to-point sending interface. Interfaces to unnumbered point-to-point
networks have no associated IP address. On these interfaces, networks have no associated IP address. On these interfaces,
the IP source should be set to any of the other IP addresses the IP source should be set to any of the other IP addresses
belonging to the router. For this reason, there must be at belonging to the router. For this reason, there must be at
least one IP address assigned to the router.[2] Note that, for least one IP address assigned to the router.[2] Note that, for
most purposes, virtual links act precisely the same as most purposes, virtual links act precisely the same as
unnumbered point-to-point networks. However, each virtual link unnumbered point-to-point networks. However, each virtual link
does have an IP interface address (discovered during the routing does have an IP interface address (discovered during the routing
table build process) which is used as the IP source when sending table build process) which is used as the IP source when sending
packets over the virtual link. packets over the virtual link.
For more information on the format of specific OSPF packet For more information on the format of specific OSPF packet
types, consult the sections listed in Table 10. types, consult the sections listed in Table 10.
Type Packet name detailed section (transmit) Type Packet name detailed section (transmit)
_________________________________________________________ _________________________________________________________
1 Hello Section 9.5 1 Hello Section 9.5
2 Database description Section 10.8 2 Database description Section 10.8
3 Link state request Section 10.9 3 Link state request Section 10.9
4 Link state update Section 13.3 4 Link state update Section 13.3
5 Link state ack Section 13.5 5 Link state ack Section 13.5
Table 10: Sections describing OSPF protocol packet transmission. Table 10: Sections describing OSPF protocol packet transmission.
8.2. Receiving protocol packets 8.2. Receiving protocol packets
Whenever a protocol packet is received by the router it is Whenever a protocol packet is received by the router it is
marked with the interface it was received on. For routers that marked with the interface it was received on. For routers that
have virtual links configured, it may not be immediately obvious have virtual links configured, it may not be immediately obvious
which interface to associate the packet with. For example, which interface to associate the packet with. For example,
consider the Router RT11 depicted in Figure 6. If RT11 receives consider the Router RT11 depicted in Figure 6. If RT11 receives
an OSPF protocol packet on its interface to Network N8, it may an OSPF protocol packet on its interface to Network N8, it may
want to associate the packet with the interface to Area 2, or want to associate the packet with the interface to Area 2, or
with the virtual link to Router RT10 (which is part of the with the virtual link to Router RT10 (which is part of the
backbone). In the following, we assume that the packet is backbone). In the following, we assume that the packet is
initially associated with the non-virtual link.[3] initially associated with the non-virtual link.[3]
In order for the packet to be accepted at the IP level, it must In order for the packet to be accepted at the IP level, it must
pass a number of tests, even before the packet is passed to OSPF pass a number of tests, even before the packet is passed to OSPF
for processing: for processing:
o The IP checksum must be correct. o The IP checksum must be correct.
o The packet's IP destination address must be the IP address o The packet's IP destination address must be the IP address
of the receiving interface, or one of the IP multicast of the receiving interface, or one of the IP multicast
addresses AllSPFRouters or AllDRouters. addresses AllSPFRouters or AllDRouters.
o The IP protocol specified must be OSPF (89). o The IP protocol specified must be OSPF (89).
o Locally originated packets should not be passed on to OSPF. o Locally originated packets should not be passed on to OSPF.
That is, the source IP address should be examined to make That is, the source IP address should be examined to make
sure this is not a multicast packet that the router itself sure this is not a multicast packet that the router itself
generated. generated.
Next, the OSPF packet header is verified. The fields specified Next, the OSPF packet header is verified. The fields specified
in the header must match those configured for the receiving in the header must match those configured for the receiving
interface. If they do not, the packet should be discarded: interface. If they do not, the packet should be discarded:
o The version number field must specify protocol version 2. o The version number field must specify protocol version 2.
o The Area ID found in the OSPF header must be verified. If o The Area ID found in the OSPF header must be verified. If
both of the following cases fail, the packet should be both of the following cases fail, the packet should be
discarded. The Area ID specified in the header must either: discarded. The Area ID specified in the header must either:
(1) Match the Area ID of the receiving interface. In this (1) Match the Area ID of the receiving interface. In this
case, the packet has been sent over a single hop. case, the packet has been sent over a single hop.
Therefore, the packet's IP source address is required to Therefore, the packet's IP source address is required to
be on the same network as the receiving interface. This be on the same network as the receiving interface. This
can be verified by comparing the packet's IP source can be verified by comparing the packet's IP source
address to the interface's IP address, after masking address to the interface's IP address, after masking
both addresses with the interface mask. This comparison both addresses with the interface mask. This comparison
should not be performed on point-to-point networks. On should not be performed on point-to-point networks. On
point-to-point networks, the interface addresses of each point-to-point networks, the interface addresses of each
end of the link are assigned independently, if they are end of the link are assigned independently, if they are
assigned at all. assigned at all.
(2) Indicate the backbone. In this case, the packet has (2) Indicate the backbone. In this case, the packet has
been sent over a virtual link. The receiving router been sent over a virtual link. The receiving router
must be an area border router, and the Router ID must be an area border router, and the Router ID
specified in the packet (the source router) must be the specified in the packet (the source router) must be the
other end of a configured virtual link. The receiving other end of a configured virtual link. The receiving
interface must also attach to the virtual link's interface must also attach to the virtual link's
configured Transit area. If all of these checks configured Transit area. If all of these checks
succeed, the packet is accepted and is from now on succeed, the packet is accepted and is from now on
associated with the virtual link (and the backbone associated with the virtual link (and the backbone
area). area).
o Packets whose IP destination is AllDRouters should only be o Packets whose IP destination is AllDRouters should only be
accepted if the state of the receiving interface is DR or accepted if the state of the receiving interface is DR or
Backup (see Section 9.1). Backup (see Section 9.1).
o The AuType specified in the packet must match the AuType o The AuType specified in the packet must match the AuType
specified for the associated area. specified for the associated area.
o The packet must be authenticated. The authentication o The packet must be authenticated. The authentication
procedure is indicated by the setting of AuType (see procedure is indicated by the setting of AuType (see
Appendix D). The authentication procedure may use one or Appendix D). The authentication procedure may use one or
more Authentication keys, which can be configured on a per- more Authentication keys, which can be configured on a per-
interface basis. The authentication procedure may also interface basis. The authentication procedure may also
verify the checksum field in the OSPF packet header (which, verify the checksum field in the OSPF packet header (which,
when used, is set to the standard IP 16-bit one's complement when used, is set to the standard IP 16-bit one's complement
checksum of the OSPF packet's contents after excluding the checksum of the OSPF packet's contents after excluding the
64-bit authentication field). If the authentication 64-bit authentication field). If the authentication
procedure fails, the packet should be discarded. procedure fails, the packet should be discarded.
If the packet type is Hello, it should then be further processed If the packet type is Hello, it should then be further processed
by the Hello Protocol (see Section 10.5). All other packet by the Hello Protocol (see Section 10.5). All other packet
types are sent/received only on adjacencies. This means that types are sent/received only on adjacencies. This means that
the packet must have been sent by one of the router's active the packet must have been sent by one of the router's active
neighbors. If the receiving interface connects to a broadcast neighbors. If the receiving interface connects to a broadcast
network, Point-to-MultiPoint network or NBMA network the sender network, Point-to-MultiPoint network or NBMA network the sender
is identified by the IP source address found in the packet's IP is identified by the IP source address found in the packet's IP
header. If the receiving interface connects to a point-to-point header. If the receiving interface connects to a point-to-point
network or a virtual link, the sender is identified by the network or a virtual link, the sender is identified by the
Router ID (source router) found in the packet's OSPF header. Router ID (source router) found in the packet's OSPF header.
The data structure associated with the receiving interface The data structure associated with the receiving interface
contains the list of active neighbors. Packets not matching any contains the list of active neighbors. Packets not matching any
active neighbor are discarded. active neighbor are discarded.
At this point all received protocol packets are associated with At this point all received protocol packets are associated with
an active neighbor. For the further input processing of an active neighbor. For the further input processing of
specific packet types, consult the sections listed in Table 11. specific packet types, consult the sections listed in Table 11.
Type Packet name detailed section (receive) Type Packet name detailed section (receive)
________________________________________________________ ________________________________________________________
1 Hello Section 10.5 1 Hello Section 10.5
2 Database description Section 10.6 2 Database description Section 10.6
3 Link state request Section 10.7 3 Link state request Section 10.7
4 Link state update Section 13 4 Link state update Section 13
5 Link state ack Section 13.7 5 Link state ack Section 13.7
Table 11: Sections describing OSPF protocol packet reception. Table 11: Sections describing OSPF protocol packet reception.
9. The Interface Data Structure 9. The Interface Data Structure
An OSPF interface is the connection between a router and a network. An OSPF interface is the connection between a router and a network.
We assume a single OSPF interface to each attached network/subnet, We assume a single OSPF interface to each attached network/subnet,
although supporting multiple interfaces on a single network is although supporting multiple interfaces on a single network is
considered in Appendix F. Each interface structure has at most one considered in Appendix F. Each interface structure has at most one
IP interface address. IP interface address.
An OSPF interface can be considered to belong to the area that An OSPF interface can be considered to belong to the area that
contains the attached network. All routing protocol packets contains the attached network. All routing protocol packets
originated by the router over this interface are labelled with the originated by the router over this interface are labelled with the
interface's Area ID. One or more router adjacencies may develop interface's Area ID. One or more router adjacencies may develop
over an interface. A router's LSAs reflect the state of its over an interface. A router's LSAs reflect the state of its
interfaces and their associated adjacencies. interfaces and their associated adjacencies.
The following data items are associated with an interface. Note The following data items are associated with an interface. Note
that a number of these items are actually configuration for the that a number of these items are actually configuration for the
attached network; such items must be the same for all routers attached network; such items must be the same for all routers
connected to the network. connected to the network.
Type Type
The OSPF interface type is either point-to-point, broadcast, The OSPF interface type is either point-to-point, broadcast,
NBMA, Point-to-MultiPoint or virtual link. NBMA, Point-to-MultiPoint or virtual link.
State State
The functional level of an interface. State determines whether The functional level of an interface. State determines whether
or not full adjacencies are allowed to form over the interface. or not full adjacencies are allowed to form over the interface.
State is also reflected in the router's LSAs. State is also reflected in the router's LSAs.
IP interface address IP interface address
The IP address associated with the interface. This appears as The IP address associated with the interface. This appears as
the IP source address in all routing protocol packets originated the IP source address in all routing protocol packets originated
over this interface. Interfaces to unnumbered point-to-point over this interface. Interfaces to unnumbered point-to-point
networks do not have an associated IP address. networks do not have an associated IP address.
IP interface mask IP interface mask
Also referred to as the subnet mask, this indicates the portion Also referred to as the subnet mask, this indicates the portion
of the IP interface address that identifies the attached of the IP interface address that identifies the attached
network. Masking the IP interface address with the IP interface network. Masking the IP interface address with the IP interface
mask yields the IP network number of the attached network. On mask yields the IP network number of the attached network. On
point-to-point networks and virtual links, the IP interface mask point-to-point networks and virtual links, the IP interface mask
is not defined. On these networks, the link itself is not is not defined. On these networks, the link itself is not
assigned an IP network number, and so the addresses of each side assigned an IP network number, and so the addresses of each side
of the link are assigned independently, if they are assigned at of the link are assigned independently, if they are assigned at
all. all.
Area ID Area ID
The Area ID of the area to which the attached network belongs. The Area ID of the area to which the attached network belongs.
All routing protocol packets originating from the interface are All routing protocol packets originating from the interface are
labelled with this Area ID. labelled with this Area ID.
HelloInterval HelloInterval
The length of time, in seconds, between the Hello packets that The length of time, in seconds, between the Hello packets that
the router sends on the interface. Advertised in Hello packets the router sends on the interface. Advertised in Hello packets
sent out this interface. sent out this interface.
RouterDeadInterval RouterDeadInterval
The number of seconds before the router's neighbors will declare The number of seconds before the router's neighbors will declare
it down, when they stop hearing the router's Hello Packets. it down, when they stop hearing the router's Hello Packets.
Advertised in Hello packets sent out this interface. Advertised in Hello packets sent out this interface.
InfTransDelay InfTransDelay
The estimated number of seconds it takes to transmit a Link The estimated number of seconds it takes to transmit a Link
State Update Packet over this interface. LSAs contained in the State Update Packet over this interface. LSAs contained in the
Link State Update packet will have their age incremented by this Link State Update packet will have their age incremented by this
amount before transmission. This value should take into account amount before transmission. This value should take into account
transmission and propagation delays; it must be greater than transmission and propagation delays; it must be greater than
zero. zero.
Router Priority Router Priority
An 8-bit unsigned integer. When two routers attached to a An 8-bit unsigned integer. When two routers attached to a
network both attempt to become Designated Router, the one with network both attempt to become Designated Router, the one with
the highest Router Priority takes precedence. A router whose the highest Router Priority takes precedence. A router whose
Router Priority is set to 0 is ineligible to become Designated Router Priority is set to 0 is ineligible to become Designated
Router on the attached network. Advertised in Hello packets Router on the attached network. Advertised in Hello packets
sent out this interface. sent out this interface.
Hello Timer Hello Timer
An interval timer that causes the interface to send a Hello An interval timer that causes the interface to send a Hello
packet. This timer fires every HelloInterval seconds. Note packet. This timer fires every HelloInterval seconds. Note
that on non-broadcast networks a separate Hello packet is sent that on non-broadcast networks a separate Hello packet is sent
to each qualified neighbor. to each qualified neighbor.
Wait Timer Wait Timer
A single shot timer that causes the interface to exit the A single shot timer that causes the interface to exit the
Waiting state, and as a consequence select a Designated Router Waiting state, and as a consequence select a Designated Router
on the network. The length of the timer is RouterDeadInterval on the network. The length of the timer is RouterDeadInterval
seconds. seconds.
List of neighboring routers List of neighboring routers
The other routers attached to this network. This list is formed The other routers attached to this network. This list is formed
by the Hello Protocol. Adjacencies will be formed to some of by the Hello Protocol. Adjacencies will be formed to some of
these neighbors. The set of adjacent neighbors can be these neighbors. The set of adjacent neighbors can be
determined by an examination of all of the neighbors' states. determined by an examination of all of the neighbors' states.
Designated Router Designated Router
The Designated Router selected for the attached network. The The Designated Router selected for the attached network. The
Designated Router is selected on all broadcast and NBMA networks Designated Router is selected on all broadcast and NBMA networks
by the Hello Protocol. Two pieces of identification are kept by the Hello Protocol. Two pieces of identification are kept
for the Designated Router: its Router ID and its IP interface for the Designated Router: its Router ID and its IP interface
address on the network. The Designated Router advertises link address on the network. The Designated Router advertises link
state for the network; this network-LSA is labelled with the state for the network; this network-LSA is labelled with the
Designated Router's IP address. The Designated Router is Designated Router's IP address. The Designated Router is
initialized to 0.0.0.0, which indicates the lack of a Designated initialized to 0.0.0.0, which indicates the lack of a Designated
Router. Router.
Backup Designated Router Backup Designated Router
The Backup Designated Router is also selected on all broadcast The Backup Designated Router is also selected on all broadcast
and NBMA networks by the Hello Protocol. All routers on the and NBMA networks by the Hello Protocol. All routers on the
attached network become adjacent to both the Designated Router attached network become adjacent to both the Designated Router
and the Backup Designated Router. The Backup Designated Router and the Backup Designated Router. The Backup Designated Router
becomes Designated Router when the current Designated Router becomes Designated Router when the current Designated Router
fails. The Backup Designated Router is initialized to 0.0.0.0, fails. The Backup Designated Router is initialized to 0.0.0.0,
indicating the lack of a Backup Designated Router. indicating the lack of a Backup Designated Router.
Interface output cost(s) Interface output cost(s)
The cost of sending a data packet on the interface, expressed in The cost of sending a data packet on the interface, expressed in
the link state metric. This is advertised as the link cost for the link state metric. This is advertised as the link cost for
this interface in the router-LSA. The cost of an interface must this interface in the router-LSA. The cost of an interface must
be greater than zero. be greater than zero.
RxmtInterval RxmtInterval
The number of seconds between LSA retransmissions, for The number of seconds between LSA retransmissions, for
adjacencies belonging to this interface. Also used when adjacencies belonging to this interface. Also used when
retransmitting Database Description and Link State Request retransmitting Database Description and Link State Request
Packets. Packets.
AuType AuType
The type of authentication used on the attached network/subnet. The type of authentication used on the attached network/subnet.
Authentication types are defined in Appendix D. All OSPF packet Authentication types are defined in Appendix D. All OSPF packet
exchanges are authenticated. Different authentication schemes exchanges are authenticated. Different authentication schemes
may be used on different networks/subnets. may be used on different networks/subnets.
Authentication key Authentication key
This configured data allows the authentication procedure to This configured data allows the authentication procedure to
generate and/or verify OSPF protocol packets. The generate and/or verify OSPF protocol packets. The
Authentication key can be configured on a per-interface basis. Authentication key can be configured on a per-interface basis.
For example, if the AuType indicates simple password, the For example, if the AuType indicates simple password, the
Authentication key would be a 64-bit clear password which is Authentication key would be a 64-bit clear password which is
inserted into the OSPF packet header. If instead Autype inserted into the OSPF packet header. If instead Autype
indicates Cryptographic authentication, then the Authentication indicates Cryptographic authentication, then the Authentication
key is a shared secret which enables the generation/verification key is a shared secret which enables the generation/verification
of message digests which are appended to the OSPF protocol of message digests which are appended to the OSPF protocol
packets. When Cryptographic authentication is used, multiple packets. When Cryptographic authentication is used, multiple
simultaneous keys are supported in order to achieve smooth key simultaneous keys are supported in order to achieve smooth key
transition (see Section D.3). transition (see Section D.3).
9.1. Interface states 9.1. Interface states
The various states that router interfaces may attain is The various states that router interfaces may attain is
documented in this section. The states are listed in order of documented in this section. The states are listed in order of
progressing functionality. For example, the inoperative state progressing functionality. For example, the inoperative state
is listed first, followed by a list of intermediate states is listed first, followed by a list of intermediate states
before the final, fully functional state is achieved. The before the final, fully functional state is achieved. The
specification makes use of this ordering by sometimes making specification makes use of this ordering by sometimes making
references such as "those interfaces in state greater than X". references such as "those interfaces in state greater than X".
Figure 11 shows the graph of interface state changes. The arcs Figure 11 shows the graph of interface state changes. The arcs
of the graph are labelled with the event causing the state of the graph are labelled with the event causing the state
change. These events are documented in Section 9.2. The change. These events are documented in Section 9.2. The
interface state machine is described in more detail in Section interface state machine is described in more detail in Section
9.3. 9.3.
Down Down
This is the initial interface state. In this state, the This is the initial interface state. In this state, the
lower-level protocols have indicated that the interface is lower-level protocols have indicated that the interface is
unusable. No protocol traffic at all will be sent or unusable. No protocol traffic at all will be sent or
received on such a interface. In this state, interface received on such a interface. In this state, interface
parameters should be set to their initial values. All parameters should be set to their initial values. All
interface timers should be disabled, and there should be no
adjacencies associated with the interface.
+----+ UnloopInd +--------+ Loopback
|Down|<--------------|Loopback| In this state, the router's interface to the network is
+----+ +--------+ +----+ UnloopInd +--------+
| |Down|<--------------|Loopback|
|InterfaceUp +----+ +--------+
+-------+ | +--------------+ |
|Waiting|<-+-------------->|Point-to-point| |InterfaceUp
+-------+ +--------------+ +-------+ | +--------------+
| |Waiting|<-+-------------->|Point-to-point|
WaitTimer|BackupSeen +-------+ +--------------+
| |
| WaitTimer|BackupSeen
| NeighborChange |
+------+ +-+<---------------- +-------+ |
|Backup|<----------|?|----------------->|DROther| | NeighborChange
+------+---------->+-+<-----+ +-------+ +------+ +-+<---------------- +-------+
Neighbor | | |Backup|<----------|?|----------------->|DROther|
Change | |Neighbor +------+---------->+-+<-----+ +-------+
| |Change Neighbor | |
| +--+ Change | |Neighbor
+---->|DR| | |Change
+--+ | +--+
+---->|DR|
+--+
Figure 11: Interface State changes Figure 11: Interface State changes
In addition to the state transitions pictured, In addition to the state transitions pictured,
Event InterfaceDown always forces Down State, and Event InterfaceDown always forces Down State, and
Event LoopInd always forces Loopback State Event LoopInd always forces Loopback State
interface timers should be disabled, and there should be no
adjacencies associated with the interface.
Loopback looped back. The interface may be looped back in hardware
In this state, the router's interface to the network is or software. The interface will be unavailable for regular
looped back. The interface may be looped back in hardware data traffic. However, it may still be desirable to gain
or software. The interface will be unavailable for regular information on the quality of this interface, either through
data traffic. However, it may still be desirable to gain sending ICMP pings to the interface or through something
information on the quality of this interface, either through like a bit error test. For this reason, IP packets may
sending ICMP pings to the interface or through something still be addressed to an interface in Loopback state. To
like a bit error test. For this reason, IP packets may facilitate this, such interfaces are advertised in router-
still be addressed to an interface in Loopback state. To LSAs as single host routes, whose destination is the IP
facilitate this, such interfaces are advertised in router- interface address.[4]
LSAs as single host routes, whose destination is the IP
interface address.[4]
Waiting Waiting
In this state, the router is trying to determine the In this state, the router is trying to determine the
identity of the (Backup) Designated Router for the network. identity of the (Backup) Designated Router for the network.
To do this, the router monitors the Hello Packets it To do this, the router monitors the Hello Packets it
receives. The router is not allowed to elect a Backup receives. The router is not allowed to elect a Backup
Designated Router nor a Designated Router until it Designated Router nor a Designated Router until it
transitions out of Waiting state. This prevents unnecessary transitions out of Waiting state. This prevents unnecessary
changes of (Backup) Designated Router. changes of (Backup) Designated Router.
Point-to-point Point-to-point
In this state, the interface is operational, and connects In this state, the interface is operational, and connects
either to a physical point-to-point network or to a virtual either to a physical point-to-point network or to a virtual
link. Upon entering this state, the router attempts to form link. Upon entering this state, the router attempts to form
an adjacency with the neighboring router. Hello Packets are an adjacency with the neighboring router. Hello Packets are
sent to the neighbor every HelloInterval seconds. sent to the neighbor every HelloInterval seconds.
DR Other DR Other
The interface is to a broadcast or NBMA network on which The interface is to a broadcast or NBMA network on which
another router has been selected to be the Designated another router has been selected to be the Designated
Router. In this state, the router itself has not been Router. In this state, the router itself has not been
selected Backup Designated Router either. The router forms selected Backup Designated Router either. The router forms
adjacencies to both the Designated Router and the Backup adjacencies to both the Designated Router and the Backup
Designated Router (if they exist). Designated Router (if they exist).
Backup Backup
In this state, the router itself is the Backup Designated In this state, the router itself is the Backup Designated
Router on the attached network. It will be promoted to Router on the attached network. It will be promoted to
Designated Router when the present Designated Router fails. Designated Router when the present Designated Router fails.
The router establishes adjacencies to all other routers The router establishes adjacencies to all other routers
attached to the network. The Backup Designated Router attached to the network. The Backup Designated Router
performs slightly different functions during the Flooding performs slightly different functions during the Flooding
Procedure, as compared to the Designated Router (see Section Procedure, as compared to the Designated Router (see Section
13.3). See Section 7.4 for more details on the functions 13.3). See Section 7.4 for more details on the functions
performed by the Backup Designated Router. performed by the Backup Designated Router.
DR In this state, this router itself is the Designated Router DR In this state, this router itself is the Designated Router
on the attached network. Adjacencies are established to all on the attached network. Adjacencies are established to all
other routers attached to the network. The router must also other routers attached to the network. The router must also
originate a network-LSA for the network node. The network- originate a network-LSA for the network node. The network-
LSA will contain links to all routers (including the LSA will contain links to all routers (including the
Designated Router itself) attached to the network. See Designated Router itself) attached to the network. See
Section 7.3 for more details on the functions performed by Section 7.3 for more details on the functions performed by
the Designated Router. the Designated Router.
9.2. Events causing interface state changes 9.2. Events causing interface state changes
State changes can be effected by a number of events. These State changes can be effected by a number of events. These
events are pictured as the labelled arcs in Figure 11. The events are pictured as the labelled arcs in Figure 11. The
label definitions are listed below. For a detailed explanation label definitions are listed below. For a detailed explanation
of the effect of these events on OSPF protocol operation, of the effect of these events on OSPF protocol operation,
consult Section 9.3. consult Section 9.3.
InterfaceUp InterfaceUp
Lower-level protocols have indicated that the network Lower-level protocols have indicated that the network
interface is operational. This enables the interface to interface is operational. This enables the interface to
transition out of Down state. On virtual links, the transition out of Down state. On virtual links, the
interface operational indication is actually a result of the interface operational indication is actually a result of the
shortest path calculation (see Section 16.7). shortest path calculation (see Section 16.7).
WaitTimer WaitTimer
The Wait Timer has fired, indicating the end of the waiting The Wait Timer has fired, indicating the end of the waiting
period that is required before electing a (Backup) period that is required before electing a (Backup)
Designated Router. Designated Router.
BackupSeen BackupSeen
The router has detected the existence or non-existence of a The router has detected the existence or non-existence of a
Backup Designated Router for the network. This is done in Backup Designated Router for the network. This is done in
one of two ways. First, an Hello Packet may be received one of two ways. First, an Hello Packet may be received
from a neighbor claiming to be itself the Backup Designated from a neighbor claiming to be itself the Backup Designated
Router. Alternatively, an Hello Packet may be received from Router. Alternatively, an Hello Packet may be received from
a neighbor claiming to be itself the Designated Router, and a neighbor claiming to be itself the Designated Router, and
indicating that there is no Backup Designated Router. In indicating that there is no Backup Designated Router. In
either case there must be bidirectional communication with either case there must be bidirectional communication with
the neighbor, i.e., the router must also appear in the the neighbor, i.e., the router must also appear in the
neighbor's Hello Packet. This event signals an end to the neighbor's Hello Packet. This event signals an end to the
Waiting state. Waiting state.
NeighborChange NeighborChange
There has been a change in the set of bidirectional There has been a change in the set of bidirectional
neighbors associated with the interface. The (Backup) neighbors associated with the interface. The (Backup)
Designated Router needs to be recalculated. The following Designated Router needs to be recalculated. The following
neighbor changes lead to the NeighborChange event. For an neighbor changes lead to the NeighborChange event. For an
explanation of neighbor states, see Section 10.1. explanation of neighbor states, see Section 10.1.
o Bidirectional communication has been established to a o Bidirectional communication has been established to a
neighbor. In other words, the state of the neighbor has neighbor. In other words, the state of the neighbor has
transitioned to 2-Way or higher. transitioned to 2-Way or higher.
o There is no longer bidirectional communication with a o There is no longer bidirectional communication with a
neighbor. In other words, the state of the neighbor has neighbor. In other words, the state of the neighbor has
transitioned to Init or lower. transitioned to Init or lower.
o One of the bidirectional neighbors is newly declaring o One of the bidirectional neighbors is newly declaring
itself as either Designated Router or Backup Designated itself as either Designated Router or Backup Designated
Router. This is detected through examination of that Router. This is detected through examination of that
neighbor's Hello Packets. neighbor's Hello Packets.
o One of the bidirectional neighbors is no longer o One of the bidirectional neighbors is no longer
declaring itself as Designated Router, or is no longer declaring itself as Designated Router, or is no longer
declaring itself as Backup Designated Router. This is declaring itself as Backup Designated Router. This is
again detected through examination of that neighbor's again detected through examination of that neighbor's
Hello Packets. Hello Packets.
o The advertised Router Priority for a bidirectional o The advertised Router Priority for a bidirectional
neighbor has changed. This is again detected through neighbor has changed. This is again detected through
examination of that neighbor's Hello Packets. examination of that neighbor's Hello Packets.
LoopInd LoopInd
An indication has been received that the interface is now An indication has been received that the interface is now
looped back to itself. This indication can be received looped back to itself. This indication can be received
either from network management or from the lower level either from network management or from the lower level
protocols. protocols.
UnloopInd UnloopInd
An indication has been received that the interface is no An indication has been received that the interface is no
longer looped back. As with the LoopInd event, this longer looped back. As with the LoopInd event, this
indication can be received either from network management or indication can be received either from network management or
from the lower level protocols. from the lower level protocols.
InterfaceDown InterfaceDown
Lower-level protocols indicate that this interface is no Lower-level protocols indicate that this interface is no
longer functional. No matter what the current interface longer functional. No matter what the current interface
state is, the new interface state will be Down. state is, the new interface state will be Down.
9.3. The Interface state machine 9.3. The Interface state machine
A detailed description of the interface state changes follows. A detailed description of the interface state changes follows.
Each state change is invoked by an event (Section 9.2). This Each state change is invoked by an event (Section 9.2). This
event may produce different effects, depending on the current event may produce different effects, depending on the current
state of the interface. For this reason, the state machine state of the interface. For this reason, the state machine
below is organized by current interface state and received below is organized by current interface state and received
event. Each entry in the state machine describes the resulting event. Each entry in the state machine describes the resulting
new interface state and the required set of additional actions. new interface state and the required set of additional actions.
When an interface's state changes, it may be necessary to When an interface's state changes, it may be necessary to
originate a new router-LSA. See Section 12.4 for more details. originate a new router-LSA. See Section 12.4 for more details.
Some of the required actions below involve generating events for Some of the required actions below involve generating events for
the neighbor state machine. For example, when an interface the neighbor state machine. For example, when an interface
becomes inoperative, all neighbor connections associated with becomes inoperative, all neighbor connections associated with
the interface must be destroyed. For more information on the the interface must be destroyed. For more information on the
neighbor state machine, see Section 10.3. neighbor state machine, see Section 10.3.
State(s): Down State(s): Down
Event: InterfaceUp Event: InterfaceUp
New state: Depends upon action routine New state: Depends upon action routine
Action: Start the interval Hello Timer, enabling the Action: Start the interval Hello Timer, enabling the
periodic sending of Hello packets out the interface. periodic sending of Hello packets out the interface.
If the attached network is a physical point-to-point If the attached network is a physical point-to-point
network, Point-to-MultiPoint network or virtual network, Point-to-MultiPoint network or virtual
link, the interface state transitions to Point-to- link, the interface state transitions to Point-to-
Point. Else, if the router is not eligible to Point. Else, if the router is not eligible to
become Designated Router the interface state become Designated Router the interface state
transitions to DR Other. transitions to DR Other.
Otherwise, the attached network is a broadcast or Otherwise, the attached network is a broadcast or
NBMA network and the router is eligible to become NBMA network and the router is eligible to become
Designated Router. In this case, in an attempt to Designated Router. In this case, in an attempt to
discover the attached network's Designated Router discover the attached network's Designated Router
the interface state is set to Waiting and the single the interface state is set to Waiting and the single
shot Wait Timer is started. Additionally, if the shot Wait Timer is started. Additionally, if the
network is an NBMA network examine the configured network is an NBMA network examine the configured
list of neighbors for this interface and generate list of neighbors for this interface and generate
the neighbor event Start for each neighbor that is the neighbor event Start for each neighbor that is
also eligible to become Designated Router. also eligible to become Designated Router.
State(s): Waiting State(s): Waiting
Event: BackupSeen Event: BackupSeen
New state: Depends upon action routine. New state: Depends upon action routine.
Action: Calculate the attached network's Backup Designated Action: Calculate the attached network's Backup Designated
Router and Designated Router, as shown in Section Router and Designated Router, as shown in Section
9.4. As a result of this calculation, the new state 9.4. As a result of this calculation, the new state
of the interface will be either DR Other, Backup or of the interface will be either DR Other, Backup or
DR. DR.
State(s): Waiting State(s): Waiting
Event: WaitTimer Event: WaitTimer
New state: Depends upon action routine. New state: Depends upon action routine.
Action: Calculate the attached network's Backup Designated Action: Calculate the attached network's Backup Designated
Router and Designated Router, as shown in Section Router and Designated Router, as shown in Section
9.4. As a result of this calculation, the new state 9.4. As a result of this calculation, the new state
of the interface will be either DR Other, Backup or of the interface will be either DR Other, Backup or
DR. DR.
State(s): DR Other, Backup or DR State(s): DR Other, Backup or DR
Event: NeighborChange Event: NeighborChange
New state: Depends upon action routine. New state: Depends upon action routine.
Action: Recalculate the attached network's Backup Designated Action: Recalculate the attached network's Backup Designated
Router and Designated Router, as shown in Section Router and Designated Router, as shown in Section
9.4. As a result of this calculation, the new state 9.4. As a result of this calculation, the new state
of the interface will be either DR Other, Backup or of the interface will be either DR Other, Backup or
DR. DR.
State(s): Any State State(s): Any State
Event: InterfaceDown Event: InterfaceDown
New state: Down New state: Down
Action: All interface variables are reset, and interface Action: All interface variables are reset, and interface
timers disabled. Also, all neighbor connections timers disabled. Also, all neighbor connections
associated with the interface are destroyed. This associated with the interface are destroyed. This
is done by generating the event KillNbr on all is done by generating the event KillNbr on all
associated neighbors (see Section 10.2). associated neighbors (see Section 10.2).
State(s): Any State State(s): Any State
Event: LoopInd Event: LoopInd
New state: Loopback New state: Loopback
Action: Since this interface is no longer connected to the Action: Since this interface is no longer connected to the
attached network the actions associated with the attached network the actions associated with the
above InterfaceDown event are executed. above InterfaceDown event are executed.
State(s): Loopback State(s): Loopback
Event: UnloopInd Event: UnloopInd
New state: Down New state: Down
Action: No actions are necessary. For example, the Action: No actions are necessary. For example, the
interface variables have already been reset upon interface variables have already been reset upon
entering the Loopback state. Note that reception of entering the Loopback state. Note that reception of
an InterfaceUp event is necessary before the an InterfaceUp event is necessary before the
interface again becomes fully functional. interface again becomes fully functional.
9.4. Electing the Designated Router 9.4. Electing the Designated Router
This section describes the algorithm used for calculating a This section describes the algorithm used for calculating a
network's Designated Router and Backup Designated Router. This network's Designated Router and Backup Designated Router. This
algorithm is invoked by the Interface state machine. The algorithm is invoked by the Interface state machine. The
initial time a router runs the election algorithm for a network, initial time a router runs the election algorithm for a network,
the network's Designated Router and Backup Designated Router are the network's Designated Router and Backup Designated Router are
initialized to 0.0.0.0. This indicates the lack of both a initialized to 0.0.0.0. This indicates the lack of both a
Designated Router and a Backup Designated Router. Designated Router and a Backup Designated Router.
The Designated Router election algorithm proceeds as follows: The Designated Router election algorithm proceeds as follows:
Call the router doing the calculation Router X. The list of Call the router doing the calculation Router X. The list of
neighbors attached to the network and having established neighbors attached to the network and having established
bidirectional communication with Router X is examined. This bidirectional communication with Router X is examined. This
list is precisely the collection of Router X's neighbors (on list is precisely the collection of Router X's neighbors (on
this network) whose state is greater than or equal to 2-Way (see this network) whose state is greater than or equal to 2-Way (see
Section 10.1). Router X itself is also considered to be on the Section 10.1). Router X itself is also considered to be on the
list. Discard all routers from the list that are ineligible to list. Discard all routers from the list that are ineligible to
become Designated Router. (Routers having Router Priority of 0 become Designated Router. (Routers having Router Priority of 0
are ineligible to become Designated Router.) The following are ineligible to become Designated Router.) The following
steps are then executed, considering only those routers that steps are then executed, considering only those routers that
remain on the list: remain on the list:
(1) Note the current values for the network's Designated Router (1) Note the current values for the network's Designated Router
and Backup Designated Router. This is used later for and Backup Designated Router. This is used later for
comparison purposes. comparison purposes.
(2) Calculate the new Backup Designated Router for the network (2) Calculate the new Backup Designated Router for the network
as follows. Only those routers on the list that have not as follows. Only those routers on the list that have not
declared themselves to be Designated Router are eligible to declared themselves to be Designated Router are eligible to
become Backup Designated Router. If one or more of these become Backup Designated Router. If one or more of these
routers have declared themselves Backup Designated Router routers have declared themselves Backup Designated Router
(i.e., they are currently listing themselves as Backup (i.e., they are currently listing themselves as Backup
Designated Router, but not as Designated Router, in their Designated Router, but not as Designated Router, in their
Hello Packets) the one having highest Router Priority is Hello Packets) the one having highest Router Priority is
declared to be Backup Designated Router. In case of a tie, declared to be Backup Designated Router. In case of a tie,
the one having the highest Router ID is chosen. If no the one having the highest Router ID is chosen. If no
routers have declared themselves Backup Designated Router, routers have declared themselves Backup Designated Router,
choose the router having highest Router Priority, (again choose the router having highest Router Priority, (again
excluding those routers who have declared themselves excluding those routers who have declared themselves
Designated Router), and again use the Router ID to break Designated Router), and again use the Router ID to break
ties. ties.
(3) Calculate the new Designated Router for the network as (3) Calculate the new Designated Router for the network as
follows. If one or more of the routers have declared follows. If one or more of the routers have declared
themselves Designated Router (i.e., they are currently themselves Designated Router (i.e., they are currently
listing themselves as Designated Router in their Hello listing themselves as Designated Router in their Hello
Packets) the one having highest Router Priority is declared Packets) the one having highest Router Priority is declared
to be Designated Router. In case of a tie, the one having to be Designated Router. In case of a tie, the one having
the highest Router ID is chosen. If no routers have the highest Router ID is chosen. If no routers have
declared themselves Designated Router, assign the Designated declared themselves Designated Router, assign the Designated
Router to be the same as the newly elected Backup Designated Router to be the same as the newly elected Backup Designated
Router. Router.
(4) If Router X is now newly the Designated Router or newly the (4) If Router X is now newly the Designated Router or newly the
Backup Designated Router, or is now no longer the Designated Backup Designated Router, or is now no longer the Designated
Router or no longer the Backup Designated Router, repeat Router or no longer the Backup Designated Router, repeat
steps 2 and 3, and then proceed to step 5. For example, if steps 2 and 3, and then proceed to step 5. For example, if
Router X is now the Designated Router, when step 2 is Router X is now the Designated Router, when step 2 is
repeated X will no longer be eligible for Backup Designated repeated X will no longer be eligible for Backup Designated
Router election. Among other things, this will ensure that Router election. Among other things, this will ensure that
no router will declare itself both Backup Designated Router no router will declare itself both Backup Designated Router
and Designated Router.[5] and Designated Router.[5]
(5) As a result of these calculations, the router itself may now (5) As a result of these calculations, the router itself may now
be Designated Router or Backup Designated Router. See be Designated Router or Backup Designated Router. See
Sections 7.3 and 7.4 for the additional duties this would Sections 7.3 and 7.4 for the additional duties this would
entail. The router's interface state should be set entail. The router's interface state should be set
accordingly. If the router itself is now Designated Router, accordingly. If the router itself is now Designated Router,
the new interface state is DR. If the router itself is now the new interface state is DR. If the router itself is now
Backup Designated Router, the new interface state is Backup. Backup Designated Router, the new interface state is Backup.
Otherwise, the new interface state is DR Other. Otherwise, the new interface state is DR Other.
(6) If the attached network is an NBMA network, and the router (6) If the attached network is an NBMA network, and the router
itself has just become either Designated Router or Backup itself has just become either Designated Router or Backup
Designated Router, it must start sending Hello Packets to Designated Router, it must start sending Hello Packets to
those neighbors that are not eligible to become Designated those neighbors that are not eligible to become Designated
Router (see Section 9.5.1). This is done by invoking the Router (see Section 9.5.1). This is done by invoking the
neighbor event Start for each neighbor having a Router neighbor event Start for each neighbor having a Router
Priority of 0. Priority of 0.
(7) If the above calculations have caused the identity of either (7) If the above calculations have caused the identity of either
the Designated Router or Backup Designated Router to change, the Designated Router or Backup Designated Router to change,
the set of adjacencies associated with this interface will the set of adjacencies associated with this interface will
need to be modified. Some adjacencies may need to be need to be modified. Some adjacencies may need to be
formed, and others may need to be broken. To accomplish formed, and others may need to be broken. To accomplish
this, invoke the event AdjOK? on all neighbors whose state this, invoke the event AdjOK? on all neighbors whose state
is at least 2-Way. This will cause their eligibility for is at least 2-Way. This will cause their eligibility for
adjacency to be reexamined (see Sections 10.3 and 10.4). adjacency to be reexamined (see Sections 10.3 and 10.4).
The reason behind the election algorithm's complexity is the The reason behind the election algorithm's complexity is the
desire for an orderly transition from Backup Designated Router desire for an orderly transition from Backup Designated Router
to Designated Router, when the current Designated Router fails. to Designated Router, when the current Designated Router fails.
This orderly transition is ensured through the introduction of This orderly transition is ensured through the introduction of
hysteresis: no new Backup Designated Router can be chosen until hysteresis: no new Backup Designated Router can be chosen until
the old Backup accepts its new Designated Router the old Backup accepts its new Designated Router
responsibilities. responsibilities.
The above procedure may elect the same router to be both The above procedure may elect the same router to be both
Designated Router and Backup Designated Router, although that Designated Router and Backup Designated Router, although that
router will never be the calculating router (Router X) itself. router will never be the calculating router (Router X) itself.
The elected Designated Router may not be the router having the The elected Designated Router may not be the router having the
highest Router Priority, nor will the Backup Designated Router highest Router Priority, nor will the Backup Designated Router
necessarily have the second highest Router Priority. If Router necessarily have the second highest Router Priority. If Router
X is not itself eligible to become Designated Router, it is X is not itself eligible to become Designated Router, it is
possible that neither a Backup Designated Router nor a possible that neither a Backup Designated Router nor a
Designated Router will be selected in the above procedure. Note Designated Router will be selected in the above procedure. Note
also that if Router X is the only attached router that is also that if Router X is the only attached router that is
eligible to become Designated Router, it will select itself as eligible to become Designated Router, it will select itself as
Designated Router and there will be no Backup Designated Router Designated Router and there will be no Backup Designated Router
for the network. for the network.
9.5. Sending Hello packets 9.5. Sending Hello packets
Hello packets are sent out each functioning router interface. Hello packets are sent out each functioning router interface.
They are used to discover and maintain neighbor They are used to discover and maintain neighbor
relationships.[6] On broadcast and NBMA networks, Hello Packets relationships.[6] On broadcast and NBMA networks, Hello Packets
are also used to elect the Designated Router and Backup are also used to elect the Designated Router and Backup
Designated Router. Designated Router.
The format of an Hello packet is detailed in Section A.3.2. The The format of an Hello packet is detailed in Section A.3.2. The
Hello Packet contains the router's Router Priority (used in Hello Packet contains the router's Router Priority (used in
choosing the Designated Router), and the interval between Hello choosing the Designated Router), and the interval between Hello
Packets sent out the interface (HelloInterval). The Hello Packets sent out the interface (HelloInterval). The Hello
Packet also indicates how often a neighbor must be heard from to Packet also indicates how often a neighbor must be heard from to
remain active (RouterDeadInterval). Both HelloInterval and remain active (RouterDeadInterval). Both HelloInterval and
RouterDeadInterval must be the same for all routers attached to RouterDeadInterval must be the same for all routers attached to
a common network. The Hello packet also contains the IP address a common network. The Hello packet also contains the IP address
mask of the attached network (Network Mask). On unnumbered mask of the attached network (Network Mask). On unnumbered
point-to-point networks and on virtual links this field should point-to-point networks and on virtual links this field should
be set to 0.0.0.0. be set to 0.0.0.0.
The Hello packet's Options field describes the router's optional The Hello packet's Options field describes the router's optional
OSPF capabilities. One optional capability is defined in this OSPF capabilities. One optional capability is defined in this
specification (see Sections 4.5 and A.2). The E-bit of the specification (see Sections 4.5 and A.2). The E-bit of the
Options field should be set if and only if the attached area is Options field should be set if and only if the attached area is
capable of processing AS-external-LSAs (i.e., it is not a stub capable of processing AS-external-LSAs (i.e., it is not a stub
area). If the E-bit is set incorrectly the neighboring routers area). If the E-bit is set incorrectly the neighboring routers
will refuse to accept the Hello Packet (see Section 10.5). will refuse to accept the Hello Packet (see Section 10.5).
Unrecognized bits in the Hello Packet's Options field should be Unrecognized bits in the Hello Packet's Options field should be
set to zero. set to zero.
In order to ensure two-way communication between adjacent In order to ensure two-way communication between adjacent
routers, the Hello packet contains the list of all routers on routers, the Hello packet contains the list of all routers on
the network from which Hello Packets have been seen recently. the network from which Hello Packets have been seen recently.
The Hello packet also contains the router's current choice for The Hello packet also contains the router's current choice for
Designated Router and Backup Designated Router. A value of Designated Router and Backup Designated Router. A value of
0.0.0.0 in these fields means that one has not yet been 0.0.0.0 in these fields means that one has not yet been
selected. selected.
On broadcast networks and physical point-to-point networks, On broadcast networks and physical point-to-point networks,
Hello packets are sent every HelloInterval seconds to the IP Hello packets are sent every HelloInterval seconds to the IP
multicast address AllSPFRouters. On virtual links, Hello multicast address AllSPFRouters. On virtual links, Hello
packets are sent as unicasts (addressed directly to the other packets are sent as unicasts (addressed directly to the other
end of the virtual link) every HelloInterval seconds. On Point- end of the virtual link) every HelloInterval seconds. On Point-
to-MultiPoint networks, separate Hello packets are sent to each to-MultiPoint networks, separate Hello packets are sent to each
attached neighbor every HelloInterval seconds. Sending of Hello attached neighbor every HelloInterval seconds. Sending of Hello
packets on NBMA networks is covered in the next section. packets on NBMA networks is covered in the next section.
9.5.1. Sending Hello packets on NBMA networks 9.5.1. Sending Hello packets on NBMA networks
Static configuration information may be necessary in order Static configuration information may be necessary in order
for the Hello Protocol to function on non-broadcast networks for the Hello Protocol to function on non-broadcast networks
(see Sections C.5 and C.6). On NBMA networks, every (see Sections C.5 and C.6). On NBMA networks, every
attached router which is eligible to become Designated attached router which is eligible to become Designated
Router becomes aware of all of its neighbors on the network Router becomes aware of all of its neighbors on the network
(either through configuration or by some unspecified (either through configuration or by some unspecified
mechanism). Each neighbor is labelled with the neighbor's mechanism). Each neighbor is labelled with the neighbor's
Designated Router eligibility. Designated Router eligibility.
The interface state must be at least Waiting for any Hello The interface state must be at least Waiting for any Hello
Packets to be sent out the NBMA interface. Hello Packets Packets to be sent out the NBMA interface. Hello Packets
are then sent directly (as unicasts) to some subset of a are then sent directly (as unicasts) to some subset of a
router's neighbors. Sometimes an Hello Packet is sent router's neighbors. Sometimes an Hello Packet is sent
periodically on a timer; at other times it is sent as a periodically on a timer; at other times it is sent as a
response to a received Hello Packet. A router's hello- response to a received Hello Packet. A router's hello-
sending behavior varies depending on whether the router sending behavior varies depending on whether the router
itself is eligible to become Designated Router. itself is eligible to become Designated Router.
If the router is eligible to become Designated Router, it If the router is eligible to become Designated Router, it
must periodically send Hello Packets to all neighbors that must periodically send Hello Packets to all neighbors that
are also eligible. In addition, if the router is itself the are also eligible. In addition, if the router is itself the
Designated Router or Backup Designated Router, it must also Designated Router or Backup Designated Router, it must also
send periodic Hello Packets to all other neighbors. This send periodic Hello Packets to all other neighbors. This
means that any two eligible routers are always exchanging means that any two eligible routers are always exchanging
Hello Packets, which is necessary for the correct operation Hello Packets, which is necessary for the correct operation
of the Designated Router election algorithm. To minimize of the Designated Router election algorithm. To minimize
the number of Hello Packets sent, the number of eligible the number of Hello Packets sent, the number of eligible
routers on an NBMA network should be kept small. routers on an NBMA network should be kept small.
If the router is not eligible to become Designated Router, If the router is not eligible to become Designated Router,
it must periodically send Hello Packets to both the it must periodically send Hello Packets to both the
Designated Router and the Backup Designated Router (if they Designated Router and the Backup Designated Router (if they
exist). It must also send an Hello Packet in reply to an exist). It must also send an Hello Packet in reply to an
Hello Packet received from any eligible neighbor (other than Hello Packet received from any eligible neighbor (other than
the current Designated Router and Backup Designated Router). the current Designated Router and Backup Designated Router).
This is needed to establish an initial bidirectional This is needed to establish an initial bidirectional
relationship with any potential Designated Router. relationship with any potential Designated Router.
When sending Hello packets periodically to any neighbor, the When sending Hello packets periodically to any neighbor, the
interval between Hello Packets is determined by the interval between Hello Packets is determined by the
neighbor's state. If the neighbor is in state Down, Hello neighbor's state. If the neighbor is in state Down, Hello
Packets are sent every PollInterval seconds. Otherwise, Packets are sent every PollInterval seconds. Otherwise,
Hello Packets are sent every HelloInterval seconds. Hello Packets are sent every HelloInterval seconds.
10. The Neighbor Data Structure 10. The Neighbor Data Structure
An OSPF router converses with its neighboring routers. Each An OSPF router converses with its neighboring routers. Each
separate conversation is described by a "neighbor data structure". separate conversation is described by a "neighbor data structure".
Each conversation is bound to a particular OSPF router interface, Each conversation is bound to a particular OSPF router interface,
and is identified either by the neighboring router's OSPF Router ID and is identified either by the neighboring router's OSPF Router ID
or by its Neighbor IP address (see below). Thus if the OSPF router or by its Neighbor IP address (see below). Thus if the OSPF router
and another router have multiple attached networks in common, and another router have multiple attached networks in common,
multiple conversations ensue, each described by a unique neighbor multiple conversations ensue, each described by a unique neighbor
data structure. Each separate conversation is loosely referred to data structure. Each separate conversation is loosely referred to
in the text as being a separate "neighbor". in the text as being a separate "neighbor".
The neighbor data structure contains all information pertinent to The neighbor data structure contains all information pertinent to
the forming or formed adjacency between the two neighbors. the forming or formed adjacency between the two neighbors.
(However, remember that not all neighbors become adjacent.) An (However, remember that not all neighbors become adjacent.) An
adjacency can be viewed as a highly developed conversation between adjacency can be viewed as a highly developed conversation between
two routers. two routers.
State State
The functional level of the neighbor conversation. This is The functional level of the neighbor conversation. This is
described in more detail in Section 10.1. described in more detail in Section 10.1.
Inactivity Timer Inactivity Timer
A single shot timer whose firing indicates that no Hello Packet A single shot timer whose firing indicates that no Hello Packet
has been seen from this neighbor recently. The length of the has been seen from this neighbor recently. The length of the
timer is RouterDeadInterval seconds. timer is RouterDeadInterval seconds.
Master/Slave Master/Slave
When the two neighbors are exchanging databases, they form a When the two neighbors are exchanging databases, they form a
master/slave relationship. The master sends the first Database master/slave relationship. The master sends the first Database
Description Packet, and is the only part that is allowed to Description Packet, and is the only part that is allowed to
retransmit. The slave can only respond to the master's Database retransmit. The slave can only respond to the master's Database
Description Packets. The master/slave relationship is Description Packets. The master/slave relationship is
negotiated in state ExStart. negotiated in state ExStart.
DD Sequence Number DD Sequence Number
The DD Sequence number of the Database Description packet that The DD Sequence number of the Database Description packet that
is currently being sent to the neighbor. is currently being sent to the neighbor.
Last received Database Description packet Last received Database Description packet
The initialize(I), more (M) and master(MS) bits, Options field, The initialize(I), more (M) and master(MS) bits, Options field,
and DD sequence number contained in the last Database and DD sequence number contained in the last Database
Description packet received from the neighbor. Used to determine Description packet received from the neighbor. Used to determine
whether the next Database Description packet received from the whether the next Database Description packet received from the
neighbor is a duplicate. neighbor is a duplicate.
Neighbor ID Neighbor ID
The OSPF Router ID of the neighboring router. The Neighbor ID The OSPF Router ID of the neighboring router. The Neighbor ID
is learned when Hello packets are received from the neighbor, or is learned when Hello packets are received from the neighbor, or
is configured if this is a virtual adjacency (see Section C.4). is configured if this is a virtual adjacency (see Section C.4).
Neighbor Priority Neighbor Priority
The Router Priority of the neighboring router. Contained in the The Router Priority of the neighboring router. Contained in the
neighbor's Hello packets, this item is used when selecting the neighbor's Hello packets, this item is used when selecting the
Designated Router for the attached network. Designated Router for the attached network.
Neighbor IP address Neighbor IP address
The IP address of the neighboring router's interface to the The IP address of the neighboring router's interface to the
attached network. Used as the Destination IP address when attached network. Used as the Destination IP address when
protocol packets are sent as unicasts along this adjacency. protocol packets are sent as unicasts along this adjacency.
Also used in router-LSAs as the Link ID for the attached network Also used in router-LSAs as the Link ID for the attached network
if the neighboring router is selected to be Designated Router if the neighboring router is selected to be Designated Router
(see Section 12.4.1). The Neighbor IP address is learned when (see Section 12.4.1). The Neighbor IP address is learned when
Hello packets are received from the neighbor. For virtual Hello packets are received from the neighbor. For virtual
links, the Neighbor IP address is learned during the routing links, the Neighbor IP address is learned during the routing
table build process (see Section 15). table build process (see Section 15).
Neighbor Options Neighbor Options
The optional OSPF capabilities supported by the neighbor. The optional OSPF capabilities supported by the neighbor.
Learned during the Database Exchange process (see Section 10.6). Learned during the Database Exchange process (see Section 10.6).
The neighbor's optional OSPF capabilities are also listed in its The neighbor's optional OSPF capabilities are also listed in its
Hello packets. This enables received Hello Packets to be Hello packets. This enables received Hello Packets to be
rejected (i.e., neighbor relationships will not even start to rejected (i.e., neighbor relationships will not even start to
form) if there is a mismatch in certain crucial OSPF form) if there is a mismatch in certain crucial OSPF
capabilities (see Section 10.5). The optional OSPF capabilities capabilities (see Section 10.5). The optional OSPF capabilities
are documented in Section 4.5. are documented in Section 4.5.
Neighbor's Designated Router Neighbor's Designated Router
The neighbor's idea of the Designated Router. If this is the The neighbor's idea of the Designated Router. If this is the
neighbor itself, this is important in the local calculation of neighbor itself, this is important in the local calculation of
the Designated Router. Defined only on broadcast and NBMA the Designated Router. Defined only on broadcast and NBMA
networks. networks.
Neighbor's Backup Designated Router Neighbor's Backup Designated Router
The neighbor's idea of the Backup Designated Router. If this is The neighbor's idea of the Backup Designated Router. If this is
the neighbor itself, this is important in the local calculation the neighbor itself, this is important in the local calculation
of the Backup Designated Router. Defined only on broadcast and of the Backup Designated Router. Defined only on broadcast and
NBMA networks. NBMA networks.
The next set of variables are lists of LSAs. These lists describe The next set of variables are lists of LSAs. These lists describe
subsets of the area link-state database. This memo defines five subsets of the area link-state database. This memo defines five
distinct types of LSAs, all of which may be present in an area distinct types of LSAs, all of which may be present in an area
link-state database: router-LSAs, network-LSAs, and Type 3 and 4 link-state database: router-LSAs, network-LSAs, and Type 3 and 4
summary-LSAs (all stored in the area data structure), and AS- summary-LSAs (all stored in the area data structure), and AS-
external-LSAs (stored in the global data structure). external-LSAs (stored in the global data structure).
Link state retransmission list Link state retransmission list
The list of LSAs that have been flooded but not acknowledged on The list of LSAs that have been flooded but not acknowledged on
this adjacency. These will be retransmitted at intervals until this adjacency. These will be retransmitted at intervals until
they are acknowledged, or until the adjacency is destroyed. they are acknowledged, or until the adjacency is destroyed.
Database summary list Database summary list
The complete list of LSAs that make up the area link-state The complete list of LSAs that make up the area link-state
database, at the moment the neighbor goes into Database Exchange database, at the moment the neighbor goes into Database Exchange
state. This list is sent to the neighbor in Database state. This list is sent to the neighbor in Database
Description packets. Description packets.
Link state request list Link state request list
The list of LSAs that need to be received from this neighbor in The list of LSAs that need to be received from this neighbor in
order to synchronize the two neighbors' link-state databases. order to synchronize the two neighbors' link-state databases.
This list is created as Database Description packets are This list is created as Database Description packets are
received, and is then sent to the neighbor in Link State Request received, and is then sent to the neighbor in Link State Request
packets. The list is depleted as appropriate Link State Update packets. The list is depleted as appropriate Link State Update
packets are received. packets are received.
10.1. Neighbor states 10.1. Neighbor states
The state of a neighbor (really, the state of a conversation The state of a neighbor (really, the state of a conversation
being held with a neighboring router) is documented in the being held with a neighboring router) is documented in the
following sections. The states are listed in order of following sections. The states are listed in order of
progressing functionality. For example, the inoperative state progressing functionality. For example, the inoperative state
is listed first, followed by a list of intermediate states is listed first, followed by a list of intermediate states
before the final, fully functional state is achieved. The before the final, fully functional state is achieved. The
specification makes use of this ordering by sometimes making specification makes use of this ordering by sometimes making
references such as "those neighbors/adjacencies in state greater references such as "those neighbors/adjacencies in state greater
than X". Figures 12 and 13 show the graph of neighbor state than X". Figures 12 and 13 show the graph of neighbor state
changes. The arcs of the graphs are labelled with the event changes. The arcs of the graphs are labelled with the event
causing the state change. The neighbor events are documented in causing the state change. The neighbor events are documented in
Section 10.2. Section 10.2.
The graph in Figure 12 shows the state changes effected by the The graph in Figure 12 shows the state changes effected by the
Hello Protocol. The Hello Protocol is responsible for neighbor Hello Protocol. The Hello Protocol is responsible for neighbor
acquisition and maintenance, and for ensuring two way acquisition and maintenance, and for ensuring two way
communication between neighbors. communication between neighbors.
The graph in Figure 13 shows the forming of an adjacency. Not The graph in Figure 13 shows the forming of an adjacency. Not
every two neighboring routers become adjacent (see Section every two neighboring routers become adjacent (see Section
10.4). The adjacency starts to form when the neighbor is in 10.4). The adjacency starts to form when the neighbor is in
state ExStart. After the two routers discover their state ExStart. After the two routers discover their
+----+ master/slave status, the state transitions to Exchange. At this
|Down| point the neighbor starts to be used in the flooding procedure,
+----+ and the two neighboring routers begin synchronizing their
|\ databases. When this synchronization is finished, the neighbor
| \Start is in state Full and we say that the two routers are fully
| \ +-------+ adjacent. At this point the adjacency is listed in LSAs.
Hello | +---->|Attempt|
Received | +-------+
| |
+----+<-+ |HelloReceived
|Init|<---------------+
+----+<--------+
| |
|2-Way |1-Way
|Received |Received
| |
+-------+ | +-----+
|ExStart|<--------+------->|2-Way|
+-------+ +-----+
Figure 12: Neighbor state changes (Hello Protocol) For a more detailed description of neighbor state changes,
together with the additional actions involved in each change,
see Section 10.3.
In addition to the state transitions pictured, Down
Event KillNbr always forces Down State, This is the initial state of a neighbor conversation. It
Event InactivityTimer always forces Down State, indicates that there has been no recent information received
Event LLDown always forces Down State from the neighbor. On NBMA networks, Hello packets may
+-------+ still be sent to "Down" neighbors, although at a reduced
|ExStart| frequency (see Section 9.5.1).
+-------+
|
NegotiationDone|
+->+--------+
|Exchange|
+--+--------+
|
Exchange|
Done |
+----+ | +-------+
|Full|<---------+----->|Loading|
+----+<-+ +-------+
| LoadingDone |
+------------------+
Figure 13: Neighbor state changes (Database Exchange) +----+
|Down|
+----+
|\
| \Start
| \ +-------+
Hello | +---->|Attempt|
Received | +-------+
| |
+----+<-+ |HelloReceived
|Init|<---------------+
+----+<--------+
| |
|2-Way |1-Way
|Received |Received
| |
+-------+ | +-----+
|ExStart|<--------+------->|2-Way|
+-------+ +-----+
In addition to the state transitions pictured, Figure 12: Neighbor state changes (Hello Protocol)
Event SeqNumberMismatch forces ExStart state,
Event BadLSReq forces ExStart state,
Event 1-Way forces Init state,
Event KillNbr always forces Down State,
Event InactivityTimer always forces Down State,
Event LLDown always forces Down State,
Event AdjOK? leads to adjacency forming/breaking
master/slave status, the state transitions to Exchange. At this In addition to the state transitions pictured,
point the neighbor starts to be used in the flooding procedure, Event KillNbr always forces Down State,
and the two neighboring routers begin synchronizing their Event InactivityTimer always forces Down State,
databases. When this synchronization is finished, the neighbor Event LLDown always forces Down State
is in state Full and we say that the two routers are fully +-------+
adjacent. At this point the adjacency is listed in LSAs. |ExStart|
+-------+
|
NegotiationDone|
+->+--------+
|Exchange|
+--+--------+
|
Exchange|
Done |
+----+ | +-------+
|Full|<---------+----->|Loading|
+----+<-+ +-------+
| LoadingDone |
+------------------+
For a more detailed description of neighbor state changes, Figure 13: Neighbor state changes (Database Exchange)
together with the additional actions involved in each change,
see Section 10.3.
Down In addition to the state transitions pictured,
This is the initial state of a neighbor conversation. It Event SeqNumberMismatch forces ExStart state,
indicates that there has been no recent information received Event BadLSReq forces ExStart state,
from the neighbor. On NBMA networks, Hello packets may Event 1-Way forces Init state,
still be sent to "Down" neighbors, although at a reduced Event KillNbr always forces Down State,
frequency (see Section 9.5.1). Event InactivityTimer always forces Down State,
Event LLDown always forces Down State,
Event AdjOK? leads to adjacency forming/breaking
Attempt Attempt
This state is only valid for neighbors attached to NBMA This state is only valid for neighbors attached to NBMA
networks. It indicates that no recent information has been networks. It indicates that no recent information has been
received from the neighbor, but that a more concerted effort received from the neighbor, but that a more concerted effort
should be made to contact the neighbor. This is done by should be made to contact the neighbor. This is done by
sending the neighbor Hello packets at intervals of sending the neighbor Hello packets at intervals of
HelloInterval (see Section 9.5.1). HelloInterval (see Section 9.5.1).
Init Init
In this state, an Hello packet has recently been seen from In this state, an Hello packet has recently been seen from
the neighbor. However, bidirectional communication has not the neighbor. However, bidirectional communication has not
yet been established with the neighbor (i.e., the router yet been established with the neighbor (i.e., the router
itself did not appear in the neighbor's Hello packet). All itself did not appear in the neighbor's Hello packet). All
neighbors in this state (or higher) are listed in the Hello neighbors in this state (or higher) are listed in the Hello
packets sent from the associated interface. packets sent from the associated interface.
2-Way 2-Way
In this state, communication between the two routers is In this state, communication between the two routers is
bidirectional. This has been assured by the operation of bidirectional. This has been assured by the operation of
the Hello Protocol. This is the most advanced state short the Hello Protocol. This is the most advanced state short
of beginning adjacency establishment. The (Backup) of beginning adjacency establishment. The (Backup)
Designated Router is selected from the set of neighbors in Designated Router is selected from the set of neighbors in
state 2-Way or greater. state 2-Way or greater.
ExStart ExStart
This is the first step in creating an adjacency between the This is the first step in creating an adjacency between the
two neighboring routers. The goal of this step is to decide two neighboring routers. The goal of this step is to decide
which router is the master, and to decide upon the initial which router is the master, and to decide upon the initial
DD sequence number. Neighbor conversations in this state or DD sequence number. Neighbor conversations in this state or
greater are called adjacencies. greater are called adjacencies.
Exchange Exchange
In this state the router is describing its entire link state In this state the router is describing its entire link state
database by sending Database Description packets to the database by sending Database Description packets to the
neighbor. Each Database Description Packet has a DD neighbor. Each Database Description Packet has a DD
sequence number, and is explicitly acknowledged. Only one sequence number, and is explicitly acknowledged. Only one
Database Description Packet is allowed outstanding at any Database Description Packet is allowed outstanding at any
one time. In this state, Link State Request Packets may one time. In this state, Link State Request Packets may
also be sent asking for the neighbor's more recent LSAs. also be sent asking for the neighbor's more recent LSAs.
All adjacencies in Exchange state or greater are used by the All adjacencies in Exchange state or greater are used by the
flooding procedure. In fact, these adjacencies are fully flooding procedure. In fact, these adjacencies are fully
capable of transmitting and receiving all types of OSPF capable of transmitting and receiving all types of OSPF
routing protocol packets. routing protocol packets.
Loading Loading
In this state, Link State Request packets are sent to the In this state, Link State Request packets are sent to the
neighbor asking for the more recent LSAs that have been neighbor asking for the more recent LSAs that have been
discovered (but not yet received) in the Exchange state. discovered (but not yet received) in the Exchange state.
Full Full
In this state, the neighboring routers are fully adjacent. In this state, the neighboring routers are fully adjacent.
These adjacencies will now appear in router-LSAs and These adjacencies will now appear in router-LSAs and
network-LSAs. network-LSAs.
10.2. Events causing neighbor state changes 10.2. Events causing neighbor state changes
State changes can be effected by a number of events. These State changes can be effected by a number of events. These
events are shown in the labels of the arcs in Figures 12 and 13. events are shown in the labels of the arcs in Figures 12 and 13.
The label definitions are as follows: The label definitions are as follows:
HelloReceived HelloReceived
An Hello packet has been received from the neighbor. An Hello packet has been received from the neighbor.
Start Start
This is an indication that Hello Packets should now be sent This is an indication that Hello Packets should now be sent
to the neighbor at intervals of HelloInterval seconds. This to the neighbor at intervals of HelloInterval seconds. This
event is generated only for neighbors associated with NBMA event is generated only for neighbors associated with NBMA
networks. networks.
2-WayReceived 2-WayReceived
Bidirectional communication has been realized between the Bidirectional communication has been realized between the
two neighboring routers. This is indicated by the router two neighboring routers. This is indicated by the router
seeing itself in the neighbor's Hello packet. seeing itself in the neighbor's Hello packet.
NegotiationDone NegotiationDone
The Master/Slave relationship has been negotiated, and DD The Master/Slave relationship has been negotiated, and DD
sequence numbers have been exchanged. This signals the sequence numbers have been exchanged. This signals the
start of the sending/receiving of Database Description start of the sending/receiving of Database Description
packets. For more information on the generation of this packets. For more information on the generation of this
event, consult Section 10.8. event, consult Section 10.8.
ExchangeDone ExchangeDone
Both routers have successfully transmitted a full sequence Both routers have successfully transmitted a full sequence
of Database Description packets. Each router now knows what of Database Description packets. Each router now knows what
parts of its link state database are out of date. For more parts of its link state database are out of date. For more
information on the generation of this event, consult Section information on the generation of this event, consult Section
10.8. 10.8.
BadLSReq BadLSReq
A Link State Request has been received for an LSA not A Link State Request has been received for an LSA not
contained in the database. This indicates an error in the contained in the database. This indicates an error in the
Database Exchange process. Database Exchange process.
Loading Done Loading Done
Link State Updates have been received for all out-of-date Link State Updates have been received for all out-of-date
portions of the database. This is indicated by the Link portions of the database. This is indicated by the Link
state request list becoming empty after the Database state request list becoming empty after the Database
Exchange process has completed. Exchange process has completed.
AdjOK? AdjOK?
A decision must be made as to whether an adjacency should be A decision must be made as to whether an adjacency should be
established/maintained with the neighbor. This event will established/maintained with the neighbor. This event will
start some adjacencies forming, and destroy others. start some adjacencies forming, and destroy others.
The following events cause well developed neighbors to revert to The following events cause well developed neighbors to revert to
lesser states. Unlike the above events, these events may occur lesser states. Unlike the above events, these events may occur
when the neighbor conversation is in any of a number of states. when the neighbor conversation is in any of a number of states.
SeqNumberMismatch SeqNumberMismatch
A Database Description packet has been received that either A Database Description packet has been received that either
a) has an unexpected DD sequence number, b) unexpectedly has a) has an unexpected DD sequence number, b) unexpectedly has
the Init bit set or c) has an Options field differing from the Init bit set or c) has an Options field differing from
the last Options field received in a Database Description the last Options field received in a Database Description
packet. Any of these conditions indicate that some error packet. Any of these conditions indicate that some error
has occurred during adjacency establishment. has occurred during adjacency establishment.
1-Way 1-Way
An Hello packet has been received from the neighbor, in An Hello packet has been received from the neighbor, in
which the router is not mentioned. This indicates that which the router is not mentioned. This indicates that
communication with the neighbor is not bidirectional. communication with the neighbor is not bidirectional.
KillNbr KillNbr
This is an indication that all communication with the This is an indication that all communication with the
neighbor is now impossible, forcing the neighbor to neighbor is now impossible, forcing the neighbor to
revert to Down state. revert to Down state.
InactivityTimer InactivityTimer
The inactivity Timer has fired. This means that no Hello The inactivity Timer has fired. This means that no Hello
packets have been seen recently from the neighbor. The packets have been seen recently from the neighbor. The
neighbor reverts to Down state. neighbor reverts to Down state.
LLDown LLDown
This is an indication from the lower level protocols that This is an indication from the lower level protocols that
the neighbor is now unreachable. For example, on an X.25 the neighbor is now unreachable. For example, on an X.25
network this could be indicated by an X.25 clear indication network this could be indicated by an X.25 clear indication
with appropriate cause and diagnostic fields. This event with appropriate cause and diagnostic fields. This event
forces the neighbor into Down state. forces the neighbor into Down state.
10.3. The Neighbor state machine 10.3. The Neighbor state machine
A detailed description of the neighbor state changes follows. A detailed description of the neighbor state changes follows.
Each state change is invoked by an event (Section 10.2). This Each state change is invoked by an event (Section 10.2). This
event may produce different effects, depending on the current event may produce different effects, depending on the current
state of the neighbor. For this reason, the state machine below state of the neighbor. For this reason, the state machine below
is organized by current neighbor state and received event. Each is organized by current neighbor state and received event. Each
entry in the state machine describes the resulting new neighbor entry in the state machine describes the resulting new neighbor
state and the required set of additional actions. state and the required set of additional actions.
When a neighbor's state changes, it may be necessary to rerun When a neighbor's state changes, it may be necessary to rerun
the Designated Router election algorithm. This is determined by the Designated Router election algorithm. This is determined by
whether the interface NeighborChange event is generated (see whether the interface NeighborChange event is generated (see
Section 9.2). Also, if the Interface is in DR state (the router Section 9.2). Also, if the Interface is in DR state (the router
is itself Designated Router), changes in neighbor state may is itself Designated Router), changes in neighbor state may
cause a new network-LSA to be originated (see Section 12.4). cause a new network-LSA to be originated (see Section 12.4).
When the neighbor state machine needs to invoke the interface When the neighbor state machine needs to invoke the interface
state machine, it should be done as a scheduled task (see state machine, it should be done as a scheduled task (see
Section 4.4). This simplifies things, by ensuring that neither Section 4.4). This simplifies things, by ensuring that neither
state machine will be executed recursively. state machine will be executed recursively.
State(s): Down State(s): Down
Event: Start Event: Start
New state: Attempt New state: Attempt
Action: Send an Hello Packet to the neighbor (this neighbor Action: Send an Hello Packet to the neighbor (this neighbor
is always associated with an NBMA network) and start is always associated with an NBMA network) and start
the Inactivity Timer for the neighbor. The timer's the Inactivity Timer for the neighbor. The timer's
later firing would indicate that communication with later firing would indicate that communication with
the neighbor was not attained. the neighbor was not attained.
State(s): Attempt State(s): Attempt
Event: HelloReceived
Event: HelloReceived New state: Init
New state: Init Action: Restart the Inactivity Timer for the neighbor, since
the neighbor has now been heard from.
Action: Restart the Inactivity Timer for the neighbor, since State(s): Down
the neighbor has now been heard from.
State(s): Down Event: HelloReceived
Event: HelloReceived
New state: Init New state: Init
Action: Start the Inactivity Timer for the neighbor. The Action: Start the Inactivity Timer for the neighbor. The
timer's later firing would indicate that the timer's later firing would indicate that the
neighbor is dead. neighbor is dead.
State(s): Init or greater State(s): Init or greater
Event: HelloReceived Event: HelloReceived
New state: No state change. New state: No state change.
Action: Restart the Inactivity Timer for the neighbor, since Action: Restart the Inactivity Timer for the neighbor, since
the neighbor has again been heard from. the neighbor has again been heard from.
State(s): Init State(s): Init
Event: 2-WayReceived Event: 2-WayReceived
New state: Depends upon action routine. New state: Depends upon action routine.
Action: Determine whether an adjacency should be established Action: Determine whether an adjacency should be established
with the neighbor (see Section 10.4). If not, the with the neighbor (see Section 10.4). If not, the
new neighbor state is 2-Way. new neighbor state is 2-Way.
Otherwise (an adjacency should be established) the Otherwise (an adjacency should be established) the
neighbor state transitions to ExStart. Upon neighbor state transitions to ExStart. Upon
entering this state, the router increments the DD entering this state, the router increments the DD
sequence number in the neighbor data structure. If sequence number in the neighbor data structure. If
this is the first time that an adjacency has been this is the first time that an adjacency has been
attempted, the DD sequence number should be assigned attempted, the DD sequence number should be assigned
some unique value (like the time of day clock). It some unique value (like the time of day clock). It
then declares itself master (sets the master/slave then declares itself master (sets the master/slave
bit to master), and starts sending Database bit to master), and starts sending Database
Description Packets, with the initialize (I), more Description Packets, with the initialize (I), more
(M) and master (MS) bits set. This Database (M) and master (MS) bits set. This Database
Description Packet should be otherwise empty. This Description Packet should be otherwise empty. This
Database Description Packet should be retransmitted Database Description Packet should be retransmitted
at intervals of RxmtInterval until the next state is at intervals of RxmtInterval until the next state is
entered (see Section 10.8). entered (see Section 10.8).
State(s): ExStart State(s): ExStart
Event: NegotiationDone
New state: Exchange Event: NegotiationDone
Action: The router must list the contents of its entire area New state: Exchange
link state database in the neighbor Database summary
list. The area link state database consists of the
router-LSAs, network-LSAs and summary-LSAs contained
in the area structure, along with the AS-external-
LSAs contained in the global structure. AS-
external-LSAs are omitted from a virtual neighbor's
Database summary list. AS-external-LSAs are omitted
from the Database summary list if the area has been
configured as a stub (see Section 3.6). LSAs whose
age is equal to MaxAge are instead added to the
neighbor's Link state retransmission list. A
summary of the Database summary list will be sent to
the neighbor in Database Description packets. Each
Database Description Packet has a DD sequence
number, and is explicitly acknowledged. Only one
Database Description Packet is allowed outstanding
at any one time. For more detail on the sending and
receiving of Database Description packets, see
Sections 10.8 and 10.6.
State(s): Exchange Action: The router must list the contents of its entire area
link state database in the neighbor Database summary
list. The area link state database consists of the
router-LSAs, network-LSAs and summary-LSAs contained
in the area structure, along with the AS-external-
LSAs contained in the global structure. AS-
external-LSAs are omitted from a virtual neighbor's
Database summary list. AS-external-LSAs are omitted
from the Database summary list if the area has been
configured as a stub (see Section 3.6). LSAs whose
age is equal to MaxAge are instead added to the
neighbor's Link state retransmission list. A
summary of the Database summary list will be sent to
the neighbor in Database Description packets. Each
Database Description Packet has a DD sequence
number, and is explicitly acknowledged. Only one
Database Description Packet is allowed outstanding
at any one time. For more detail on the sending and
receiving of Database Description packets, see
Sections 10.8 and 10.6.
Event: ExchangeDone State(s): Exchange
New state: Depends upon action routine. Event: ExchangeDone
Action: If the neighbor Link state request list is empty, New state: Depends upon action routine.
the new neighbor state is Full. No other action is
required. This is an adjacency's final state.
Otherwise, the new neighbor state is Loading. Start Action: If the neighbor Link state request list is empty,
(or continue) sending Link State Request packets to the new neighbor state is Full. No other action is
the neighbor (see Section 10.9). These are requests required. This is an adjacency's final state.
for the neighbor's more recent LSAs (which were
discovered but not yet received in the Exchange
state). These LSAs are listed in the Link state
request list associated with the neighbor.
State(s): Loading Otherwise, the new neighbor state is Loading. Start
Event: Loading Done (or continue) sending Link State Request packets to
the neighbor (see Section 10.9). These are requests
for the neighbor's more recent LSAs (which were
discovered but not yet received in the Exchange
state). These LSAs are listed in the Link state
request list associated with the neighbor.
New state: Full State(s): Loading
Action: No action required. This is an adjacency's final Event: Loading Done
state.
State(s): 2-Way New state: Full
Event: AdjOK? Action: No action required. This is an adjacency's final
state.
New state: Depends upon action routine. State(s): 2-Way
Action: Determine whether an adjacency should be formed with Event: AdjOK?
the neighboring router (see Section 10.4). If not,
the neighbor state remains at 2-Way. Otherwise,
transition the neighbor state to ExStart and perform
the actions associated with the above state machine
entry for state Init and event 2-WayReceived.
State(s): ExStart or greater New state: Depends upon action routine.
Event: AdjOK? Action: Determine whether an adjacency should be formed with
the neighboring router (see Section 10.4). If not,
the neighbor state remains at 2-Way. Otherwise,
transition the neighbor state to ExStart and perform
the actions associated with the above state machine
entry for state Init and event 2-WayReceived.
New state: Depends upon action routine. State(s): ExStart or greater
Action: Determine whether the neighboring router should Event: AdjOK?
still be adjacent. If yes, there is no state change
and no further action is necessary.
Otherwise, the (possibly partially formed) adjacency New state: Depends upon action routine.
must be destroyed. The neighbor state transitions
to 2-Way. The Link state retransmission list,
Database summary list and Link state request list
are cleared of LSAs.
State(s): Exchange or greater Action: Determine whether the neighboring router should
still be adjacent. If yes, there is no state change
and no further action is necessary.
Event: SeqNumberMismatch Otherwise, the (possibly partially formed) adjacency
must be destroyed. The neighbor state transitions
to 2-Way. The Link state retransmission list,
Database summary list and Link state request list
are cleared of LSAs.
New state: ExStart State(s): Exchange or greater
Action: The (possibly partially formed) adjacency is torn Event: SeqNumberMismatch
down, and then an attempt is made at
reestablishment. The neighbor state first
transitions to ExStart. The Link state
retransmission list, Database summary list and Link
state request list are cleared of LSAs. Then the
router increments the DD sequence number in the
neighbor data structure, declares itself master
(sets the master/slave bit to master), and starts
sending Database Description Packets, with the
initialize (I), more (M) and master (MS) bits set.
This Database Description Packet should be otherwise
empty (see Section 10.8).
State(s): Exchange or greater New state: ExStart
Event: BadLSReq Action: The (possibly partially formed) adjacency is torn
down, and then an attempt is made at
reestablishment. The neighbor state first
transitions to ExStart. The Link state
retransmission list, Database summary list and Link
state request list are cleared of LSAs. Then the
router increments the DD sequence number in the