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