draft-ietf-ospf-version2-05.txt   draft-ietf-ospf-version2-06.txt 
Network Working Group J. Moy Network Working Group J. Moy
Internet Draft Cascade Internet Draft Cascade
Expiration Date: December 1995 June 1995 Expiration Date: May 1996 November 1995
File name: draft-ietf-ospf-version2-05.txt File name: draft-ietf-ospf-version2-06.txt
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 is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas, documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts. working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other documents months and may be updated, replaced, or obsoleted by other documents
at any time. It is inappropriate to use Internet- Drafts as at any time. It is inappropriate to use Internet- Drafts as
reference material or to cite them other than as "work in progress". reference material or to cite them other than as "work in progress".
To learn the current status of any Internet-Draft, please check the To learn the current status of any Internet-Draft, please check the
"1id-abstracts.txt" listing contained in the Internet- Drafts Shadow "1id-abstracts.txt" listing contained in the Internet- Drafts Shadow
Directories on ds.internic.net (US East Coast), nic.nordu.net Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
(Europe), ftp.isi.edu (US West Coast), or munnari.oz.au (Pacific munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
Rim). ftp.isi.edu (US West Coast).
Abstract Abstract
This memo documents version 2 of the OSPF protocol. OSPF is a This memo documents version 2 of the OSPF protocol. OSPF is a
link-state routing protocol. It is designed to be run internal to a link-state routing protocol. It is designed to be run internal to a
single Autonomous System. Each OSPF router maintains an identical single Autonomous System. Each OSPF router maintains an identical
database describing the Autonomous System's topology. From this database describing the Autonomous System's topology. From this
database, a routing table is calculated by constructing a shortest- database, a routing table is calculated by constructing a shortest-
path tree. path tree.
OSPF recalculates routes quickly in the face of topological changes, OSPF recalculates routes quickly in the face of topological changes,
utilizing a minimum of routing protocol traffic. OSPF provides utilizing a minimum of routing protocol traffic. OSPF provides
support for equal-cost multipath. Separate routes can be calculated support for equal-cost multipath. Separate routes can be calculated
for each IP Type of Service. 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 reduction in routing protocol traffic. In addition, all OSPF
routing protocol exchanges are authenticated. routing protocol exchanges are authenticated.
The differences between the current OSPF specification (RFC 1583) The differences between this memo and RFC 1583 are explained in
and this memo are explained in Appendix F. All differences are Appendix F. All differences are backward-compatible in nature.
backward-compatible in nature. Implementations of RFC 1583 and of Implementations of this memo and of RFC 1583 will interoperate.
this memo 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 ........................................... 7
1.1 Protocol Overview ...................................... 7 1.1 Protocol Overview ...................................... 7
1.2 Definitions of commonly used terms ..................... 8 1.2 Definitions of commonly used terms ..................... 8
1.3 Brief history of link-state routing technology ........ 11 1.3 Brief history of link-state routing technology ........ 11
1.4 Organization of this document ......................... 12 1.4 Organization of this document ......................... 12
1.5 Acknowledgments ....................................... 13 1.5 Acknowledgments ....................................... 13
2 The link-state database: organization and calculations 13 2 The link-state database: organization and calculations 13
2.1 Representation of routers and networks ................ 13 2.1 Representation of routers and networks ................ 13
2.1.1 Representation of non-broadcast networks .............. 15 2.1.1 Representation of non-broadcast networks .............. 15
2.1.2 An example link-state database ........................ 16 2.1.2 An example link-state database ........................ 16
2.2 The shortest-path tree ................................ 20 2.2 The shortest-path tree ................................ 20
2.3 Use of external routing information ................... 22 2.3 Use of external routing information ................... 22
2.4 Equal-cost multipath .................................. 24 2.4 Equal-cost multipath .................................. 24
2.5 TOS-based routing ..................................... 24 2.5 TOS-based routing ..................................... 25
3 Splitting the AS into Areas ........................... 25 3 Splitting the AS into Areas ........................... 25
3.1 The backbone of the Autonomous System ................. 26 3.1 The backbone of the Autonomous System ................. 26
3.2 Inter-area routing .................................... 26 3.2 Inter-area routing .................................... 27
3.3 Classification of routers ............................. 27 3.3 Classification of routers ............................. 27
3.4 A sample area configuration ........................... 28 3.4 A sample area configuration ........................... 28
3.5 IP subnetting support ................................. 34 3.5 IP subnetting support ................................. 34
3.6 Supporting stub areas ................................. 35 3.6 Supporting stub areas ................................. 35
3.7 Partitions of areas ................................... 36 3.7 Partitions of areas ................................... 36
4 Functional Summary .................................... 38 4 Functional Summary .................................... 38
4.1 Inter-area routing .................................... 38 4.1 Inter-area routing .................................... 38
4.2 AS external routes .................................... 39 4.2 AS external routes .................................... 39
4.3 Routing protocol packets .............................. 39 4.3 Routing protocol packets .............................. 39
4.4 Basic implementation requirements ..................... 42 4.4 Basic implementation requirements ..................... 42
4.5 Optional OSPF capabilities ............................ 43 4.5 Optional OSPF capabilities ............................ 43
5 Protocol data structures .............................. 45 5 Protocol data structures .............................. 44
6 The Area Data Structure ............................... 46 6 The Area Data Structure ............................... 46
7 Bringing Up Adjacencies ............................... 49 7 Bringing Up Adjacencies ............................... 49
7.1 The Hello Protocol .................................... 49 7.1 The Hello Protocol .................................... 49
7.2 The Synchronization of Databases ...................... 50 7.2 The Synchronization of Databases ...................... 50
7.3 The Designated Router ................................. 51 7.3 The Designated Router ................................. 51
7.4 The Backup Designated Router .......................... 52 7.4 The Backup Designated Router .......................... 52
7.5 The graph of adjacencies .............................. 53 7.5 The graph of adjacencies .............................. 53
8 Protocol Packet Processing ............................ 54 8 Protocol Packet Processing ............................ 53
8.1 Sending protocol packets .............................. 54 8.1 Sending protocol packets .............................. 54
8.2 Receiving protocol packets ............................ 56 8.2 Receiving protocol packets ............................ 56
9 The Interface Data Structure .......................... 59 9 The Interface Data Structure .......................... 59
9.1 Interface states ...................................... 62 9.1 Interface states ...................................... 62
9.2 Events causing interface state changes ................ 64 9.2 Events causing interface state changes ................ 64
9.3 The Interface state machine ........................... 66 9.3 The Interface state machine ........................... 66
9.4 Electing the Designated Router ........................ 69 9.4 Electing the Designated Router ........................ 68
9.5 Sending Hello packets ................................. 71 9.5 Sending Hello packets ................................. 71
9.5.1 Sending Hello packets on NBMA networks ................ 72 9.5.1 Sending Hello packets on NBMA networks ................ 72
10 The Neighbor Data Structure ........................... 73 10 The Neighbor Data Structure ........................... 73
10.1 Neighbor states ....................................... 76 10.1 Neighbor states ....................................... 75
10.2 Events causing neighbor state changes ................. 79 10.2 Events causing neighbor state changes ................. 79
10.3 The Neighbor state machine ............................ 81 10.3 The Neighbor state machine ............................ 80
10.4 Whether to become adjacent ............................ 87 10.4 Whether to become adjacent ............................ 86
10.5 Receiving Hello Packets ............................... 87 10.5 Receiving Hello Packets ............................... 87
10.6 Receiving Database Description Packets ................ 90 10.6 Receiving Database Description Packets ................ 89
10.7 Receiving Link State Request Packets .................. 93 10.7 Receiving Link State Request Packets .................. 92
10.8 Sending Database Description Packets .................. 93 10.8 Sending Database Description Packets .................. 92
10.9 Sending Link State Request Packets .................... 94 10.9 Sending Link State Request Packets .................... 94
10.10 An Example ............................................ 95 10.10 An Example ............................................ 94
11 The Routing Table Structure ........................... 97 11 The Routing Table Structure ........................... 96
11.1 Routing table lookup ................................. 100 11.1 Routing table lookup .................................. 99
11.2 Sample routing table, without areas .................. 101 11.2 Sample routing table, without areas .................. 101
11.3 Sample routing table, with areas ..................... 102 11.3 Sample routing table, with areas ..................... 101
12 Link State Advertisements ............................ 104 12 Link State Advertisements (LSAs) ..................... 104
12.1 The Link State Advertisement Header .................. 105 12.1 The LSA Header ....................................... 104
12.1.1 LS age ............................................... 106 12.1.1 LS age ............................................... 105
12.1.2 Options .............................................. 106 12.1.2 Options .............................................. 105
12.1.3 LS type .............................................. 107 12.1.3 LS type .............................................. 106
12.1.4 Link State ID ........................................ 107 12.1.4 Link State ID ........................................ 106
12.1.5 Advertising Router ................................... 109 12.1.5 Advertising Router ................................... 108
12.1.6 LS sequence number ................................... 109 12.1.6 LS sequence number ................................... 108
12.1.7 LS checksum .......................................... 110 12.1.7 LS checksum .......................................... 109
12.2 The link state database .............................. 111 12.2 The link state database .............................. 110
12.3 Representation of TOS ................................ 112 12.3 Representation of TOS ................................ 111
12.4 Originating link state advertisements ................ 113 12.4 Originating LSAs ..................................... 112
12.4.1 Router links ......................................... 116 12.4.1 Router-LSAs .......................................... 115
12.4.1.1 Describing point-to-point interfaces ................. 119 12.4.1.1 Describing point-to-point interfaces ................. 117
12.4.1.2 Describing broadcast and NBMA interfaces ............. 120 12.4.1.2 Describing broadcast and NBMA interfaces ............. 118
12.4.1.3 Describing virtual links ............................. 121 12.4.1.3 Describing virtual links ............................. 119
12.4.1.4 Describing Point-to-MultiPoint interfaces ............ 121 12.4.1.4 Describing Point-to-MultiPoint interfaces ............ 119
12.4.1.5 Examples of router-LSAs .............................. 121 12.4.1.5 Examples of router-LSAs .............................. 119
12.4.2 Network links ........................................ 124 12.4.2 Network-LSAs ......................................... 122
12.4.2.1 Examples of network-LSAs ............................. 124 12.4.2.1 Examples of network-LSAs ............................. 122
12.4.3 Summary links ........................................ 125 12.4.3 Summary-LSAs ......................................... 123
12.4.3.1 Originating summary links into stub areas ............ 128 12.4.3.1 Originating summary-LSAs into stub areas ............. 125
12.4.3.2 Examples of summary-LSAs ............................. 128 12.4.3.2 Examples of summary-LSAs ............................. 126
12.4.4 AS external links .................................... 129 12.4.4 AS-external-LSAs ..................................... 127
12.4.4.1 Examples of AS-external-LSAs ......................... 130 12.4.4.1 Examples of AS-external-LSAs ......................... 128
13 The Flooding Procedure ............................... 133 13 The Flooding Procedure ............................... 130
13.1 Determining which link state is newer ................ 136 13.1 Determining which LSA is newer ....................... 133
13.2 Installing link state advertisements in the database . 136 13.2 Installing LSAs in the database ...................... 134
13.3 Next step in the flooding procedure .................. 138 13.3 Next step in the flooding procedure .................. 135
13.4 Receiving self-originated link state ................. 140 13.4 Receiving self-originated LSAs ....................... 137
13.5 Sending Link State Acknowledgment packets ............ 141 13.5 Sending Link State Acknowledgment packets ............ 138
13.6 Retransmitting link state advertisements ............. 144 13.6 Retransmitting LSAs .................................. 139
13.7 Receiving link state acknowledgments ................. 144 13.7 Receiving link state acknowledgments ................. 141
14 Aging The Link State Database ........................ 145 14 Aging The Link State Database ........................ 142
14.1 Premature aging of advertisements .................... 145 14.1 Premature aging of LSAs .............................. 142
15 Virtual Links ........................................ 146 15 Virtual Links ........................................ 143
16 Calculation of the routing table ..................... 148 16 Calculation of the routing table ..................... 145
16.1 Calculating the shortest-path tree for an area ....... 150 16.1 Calculating the shortest-path tree for an area ....... 146
16.1.1 The next hop calculation ............................. 155 16.1.1 The next hop calculation ............................. 152
16.2 Calculating the inter-area routes .................... 156 16.2 Calculating the inter-area routes .................... 153
16.3 Examining transit areas' summary links ............... 158 16.3 Examining transit areas' summary-LSAs ................ 154
16.4 Calculating AS external routes ....................... 160 16.4 Calculating AS external routes ....................... 157
16.5 Incremental updates -- summary link advertisements ... 162 16.5 Incremental updates -- summary-LSAs .................. 158
16.6 Incremental updates -- AS external link advertisements 163 16.6 Incremental updates -- AS-external-LSAs .............. 159
16.7 Events generated as a result of routing table changes 163 16.7 Events generated as a result of routing table changes 160
16.8 Equal-cost multipath ................................. 164 16.8 Equal-cost multipath ................................. 160
16.9 Building the non-zero-TOS portion of the routing table 164 16.9 Building the non-zero-TOS portion of the routing table 161
Footnotes ............................................ 167 Footnotes ............................................ 163
References ........................................... 171 References ........................................... 167
A OSPF data formats .................................... 173 A OSPF data formats .................................... 169
A.1 Encapsulation of OSPF packets ........................ 173 A.1 Encapsulation of OSPF packets ........................ 169
A.2 The Options field .................................... 175 A.2 The Options field .................................... 171
A.3 OSPF Packet Formats .................................. 177 A.3 OSPF Packet Formats .................................. 173
A.3.1 The OSPF packet header ............................... 178 A.3.1 The OSPF packet header ............................... 174
A.3.2 The Hello packet ..................................... 180 A.3.2 The Hello packet ..................................... 176
A.3.3 The Database Description packet ...................... 182 A.3.3 The Database Description packet ...................... 178
A.3.4 The Link State Request packet ........................ 184 A.3.4 The Link State Request packet ........................ 180
A.3.5 The Link State Update packet ......................... 186 A.3.5 The Link State Update packet ......................... 182
A.3.6 The Link State Acknowledgment packet ................. 188 A.3.6 The Link State Acknowledgment packet ................. 184
A.4 Link state advertisement formats ..................... 190 A.4 LSA formats .......................................... 186
A.4.1 The Link State Advertisement header .................. 191 A.4.1 The LSA header ....................................... 187
A.4.2 Router links advertisements .......................... 193 A.4.2 Router-LSAs .......................................... 189
A.4.3 Network links advertisements ......................... 197 A.4.3 Network-LSAs ......................................... 193
A.4.4 Summary link advertisements .......................... 199 A.4.4 Summary-LSAs ......................................... 194
A.4.5 AS external link advertisements ...................... 201 A.4.5 AS-external-LSAs ..................................... 296
B Architectural Constants .............................. 203 B Architectural Constants .............................. 198
C Configurable Constants ............................... 205 C Configurable Constants ............................... 200
C.1 Global parameters .................................... 205 C.1 Global parameters .................................... 200
C.2 Area parameters ...................................... 205 C.2 Area parameters ...................................... 200
C.3 Router interface parameters .......................... 207 C.3 Router interface parameters .......................... 202
C.4 Virtual link parameters .............................. 209 C.4 Virtual link parameters .............................. 204
C.5 NBMA network parameters .............................. 210 C.5 NBMA network parameters .............................. 204
C.6 Point-to-Point network parameters .................... 210 C.6 Point-to-MultiPoint network parameters ............... 205
C.7 Host route parameters ................................ 211 C.7 Host route parameters ................................ 205
D Authentication ....................................... 212 D Authentication ....................................... 207
D.1 Null authentication .................................. 212 D.1 Null authentication .................................. 207
D.2 Simple password authentication ....................... 212 D.2 Simple password authentication ....................... 207
D.3 Cryptographic authentication ......................... 213 D.3 Cryptographic authentication ......................... 208
D.4 Message generation ................................... 215 D.4 Message generation ................................... 210
D.4.1 Generating Null authentication ....................... 215 D.4.1 Generating Null authentication ....................... 210
D.4.2 Generating Simple password authentication ............ 216 D.4.2 Generating Simple password authentication ............ 211
D.4.3 Generating Cryptographic authentication .............. 216 D.4.3 Generating Cryptographic authentication .............. 211
D.5 Message verification ................................. 217 D.5 Message verification ................................. 212
D.5.1 Verifying Null authentication ........................ 218 D.5.1 Verifying Null authentication ........................ 213
D.5.2 Verifying Simple password authentication ............. 218 D.5.2 Verifying Simple password authentication ............. 213
D.5.3 Verifying Cryptographic authentication ............... 218 D.5.3 Verifying Cryptographic authentication ............... 213
E An algorithm for assigning Link State IDs ............ 220 E An algorithm for assigning Link State IDs ............ 215
F Differences from RFC 1583 ............................ 222 F Differences from RFC 1583 ............................ 217
F.1 Enhancements to OSPF authentication .................. 222 F.1 Enhancements to OSPF authentication .................. 217
F.2 Addition of Point-to-MultiPoint interface ............ 222 F.2 Addition of Point-to-MultiPoint interface ............ 217
F.3 Support for overlapping area ranges .................. 223 F.3 Support for overlapping area ranges .................. 218
F.4 A modification to the flooding algorithm ............. 224 F.4 A modification to the flooding algorithm ............. 219
F.5 Introduction of the MinLSArrival constant ............ 224 F.5 Introduction of the MinLSArrival constant ............ 219
F.6 Optionally advertising point-to-point links as subnets 225 F.6 Optionally advertising point-to-point links as subnets 220
Security Considerations .............................. 226 Security Considerations .............................. 221
Author's Address ..................................... 226 Author's Address ..................................... 221
1. Introduction 1. Introduction
This document is a specification of the Open Shortest Path First This document is a specification of the Open Shortest Path First
(OSPF) TCP/IP internet routing protocol. OSPF is classified as an (OSPF) TCP/IP internet routing protocol. OSPF is classified as an
Interior Gateway Protocol (IGP). This means that it distributes Interior Gateway Protocol (IGP). This means that it distributes
routing information between routers belonging to a single Autonomous routing information between routers belonging to a single Autonomous
System. The OSPF protocol is based on link-state or SPF technology. System. The OSPF protocol is based on link-state or SPF technology.
This is a departure from the Bellman-Ford base used by traditional This is a departure from the Bellman-Ford base used by traditional
TCP/IP internet routing protocols. TCP/IP internet routing protocols.
skipping to change at page 8, line 32 skipping to change at page 8, line 32
to the best (i.e., longest or most specific) match. Host routes to the best (i.e., longest or most specific) match. Host routes
are considered to be subnets whose masks are "all ones" are considered to be subnets whose masks are "all ones"
(0xffffffff). (0xffffffff).
All OSPF protocol exchanges are authenticated. This means that All OSPF protocol exchanges are authenticated. This means that
only trusted routers can participate in the Autonomous System's only trusted routers can participate in the Autonomous System's
routing. A variety of authentication schemes can be used; in routing. A variety of authentication schemes can be used; in
fact, separate authentication schemes can be configured for each fact, separate authentication schemes can be configured for each
IP subnet. IP subnet.
Externally derived routing data (e.g., routes learned from the Externally derived routing data (e.g., routes learned from an
Exterior Gateway Protocol (EGP)) is advertised throughout the Exterior Gateway Protocol such as BGP; see [Ref23]) is
Autonomous System. This externally derived data is kept advertised throughout the Autonomous System. This externally
separate from the OSPF protocol's link state data. Each derived data is kept separate from the OSPF protocol's link
external route can also be tagged by the advertising router, state data. Each external route can also be tagged by the
enabling the passing of additional information between routers advertising router, enabling the passing of additional
on the boundary of the Autonomous System. information between routers on the boundary of the Autonomous
System.
1.2. Definitions of commonly used terms 1.2. Definitions of commonly used terms
This section provides definitions for terms that have a specific This section provides definitions for terms that have a specific
meaning to the OSPF protocol and that are used throughout the meaning to the OSPF protocol and that are used throughout the
text. The reader unfamiliar with the Internet Protocol Suite is text. The reader unfamiliar with the Internet Protocol Suite is
referred to [13] for an introduction to IP. referred to [Ref13] for an introduction to IP.
Router Router
A level three Internet Protocol packet switch. Formerly A level three Internet Protocol packet switch. Formerly
called a gateway in much of the IP literature. called a gateway in much of the IP literature.
Autonomous System Autonomous System
A group of routers exchanging routing information via a A group of routers exchanging routing information via a
common routing protocol. Abbreviated as AS. common routing protocol. Abbreviated as AS.
Interior Gateway Protocol Interior Gateway Protocol
skipping to change at page 11, line 18 skipping to change at page 11, line 18
neighbor relationships. On broadcast networks the Hello neighbor relationships. On broadcast networks the Hello
Protocol can also dynamically discover neighboring routers. Protocol can also dynamically discover neighboring routers.
Flooding Flooding
The part of the OSPF protocol that distributes and The part of the OSPF protocol that distributes and
synchronizes the link-state database between OSPF routers. synchronizes the link-state database between OSPF routers.
Designated Router Designated Router
Each broadcast and NBMA network that has at least two Each broadcast and NBMA network that has at least two
attached routers has a Designated Router. The Designated attached routers has a Designated Router. The Designated
Router generates a link state advertisement for the network Router generates an LSA for the network and has other
and has other special responsibilities in the running of the special responsibilities in the running of the protocol.
protocol. The Designated Router is elected by the Hello The Designated Router is elected by the Hello Protocol.
Protocol.
The Designated Router concept enables a reduction in the The Designated Router concept enables a reduction in the
number of adjacencies required on a broadcast or NBMA number of adjacencies required on a broadcast or NBMA
network. This in turn reduces the amount of routing network. This in turn reduces the amount of routing
protocol traffic and the size of the link-state database. protocol traffic and the size of the link-state database.
Lower-level protocols Lower-level protocols
The underlying network access protocols that provide The underlying network access protocols that provide
services to the Internet Protocol and in turn the OSPF services to the Internet Protocol and in turn the OSPF
protocol. Examples of these are the X.25 packet and frame protocol. Examples of these are the X.25 packet and frame
skipping to change at page 11, line 45 skipping to change at page 11, line 44
1.3. Brief history of link-state routing technology 1.3. Brief history of link-state routing technology
OSPF is a link state routing protocol. Such protocols are also OSPF is a link state routing protocol. Such protocols are also
referred to in the literature as SPF-based or distributed- referred to in the literature as SPF-based or distributed-
database protocols. This section gives a brief description of database protocols. This section gives a brief description of
the developments in link-state technology that have influenced the developments in link-state technology that have influenced
the OSPF protocol. the OSPF protocol.
The first link-state routing protocol was developed for use in The first link-state routing protocol was developed for use in
the ARPANET packet switching network. This protocol is the ARPANET packet switching network. This protocol is
described in [3]. It has formed the starting point for all described in [Ref3]. It has formed the starting point for all
other link-state protocols. The homogeneous ARPANET other link-state protocols. The homogeneous ARPANET
environment, i.e., single-vendor packet switches connected by environment, i.e., single-vendor packet switches connected by
synchronous serial lines, simplified the design and synchronous serial lines, simplified the design and
implementation of the original protocol. implementation of the original protocol.
Modifications to this protocol were proposed in [4]. These Modifications to this protocol were proposed in [Ref4]. These
modifications dealt with increasing the fault tolerance of the modifications dealt with increasing the fault tolerance of the
routing protocol through, among other things, adding a checksum routing protocol through, among other things, adding a checksum
to the link state advertisements (thereby detecting database to the LSAs (thereby detecting database corruption). The paper
corruption). The paper also included means for reducing the also included means for reducing the routing traffic overhead in
routing traffic overhead in a link-state protocol. This was a link-state protocol. This was accomplished by introducing
accomplished by introducing mechanisms which enabled the mechanisms which enabled the interval between LSA originations
interval between link state advertisement originations to be to be increased by an order of magnitude.
increased by an order of magnitude.
A link-state algorithm has also been proposed for use as an ISO A link-state algorithm has also been proposed for use as an ISO
IS-IS routing protocol. This protocol is described in [2]. The IS-IS routing protocol. This protocol is described in [Ref2].
protocol includes methods for data and routing traffic reduction The protocol includes methods for data and routing traffic
when operating over broadcast networks. This is accomplished by reduction when operating over broadcast networks. This is
election of a Designated Router for each broadcast network, accomplished by election of a Designated Router for each
which then originates a link state advertisement for the broadcast network, which then originates an LSA for the network.
network.
The OSPF Working Group of the IETF has extended this work in The OSPF Working Group of the IETF has extended this work in
developing the OSPF protocol. The Designated Router concept has developing the OSPF protocol. The Designated Router concept has
been greatly enhanced to further reduce the amount of routing been greatly enhanced to further reduce the amount of routing
traffic required. Multicast capabilities are utilized for traffic required. Multicast capabilities are utilized for
additional routing bandwidth reduction. An area routing scheme additional routing bandwidth reduction. An area routing scheme
has been developed enabling information has been developed enabling information
hiding/protection/reduction. Finally, the algorithms have been hiding/protection/reduction. Finally, the algorithms have been
tailored for efficient operation in TCP/IP internets. tailored for efficient operation in TCP/IP internets.
skipping to change at page 15, line 45 skipping to change at page 15, line 45
As mentioned previously, OSPF can run over non-broadcast As mentioned previously, OSPF can run over non-broadcast
networks in one of two modes: NBMA or Point-to-MultiPoint. networks in one of two modes: NBMA or Point-to-MultiPoint.
The choice of mode determines the way that the Hello The choice of mode determines the way that the Hello
protocol and flooding work over the non-broadcast network, protocol and flooding work over the non-broadcast network,
and the way that the network is represented in the link- and the way that the network is represented in the link-
state database. state database.
In NBMA mode, OSPF emulates operation over a broadcast In NBMA mode, OSPF emulates operation over a broadcast
network: a Designated Router is elected for the NBMA network: a Designated Router is elected for the NBMA
network, and the Designated Router originates a link-state network, and the Designated Router originates an LSA for the
advertisement for the network. The graph representation for network. The graph representation for broadcast networks and
broadcast networks and NBMA networks is identical. This NBMA networks is identical. This representation is pictured
representation is pictured in the middle of Figure 1a. in the middle of Figure 1a.
NBMA mode is the most efficient way to run OSPF over non- NBMA mode is the most efficient way to run OSPF over non-
broadcast networks, both in terms of link-state database broadcast networks, both in terms of link-state database
size and in terms of the amount of routing protocol traffic. size and in terms of the amount of routing protocol traffic.
However, it has one significant restriction: it requires all However, it has one significant restriction: it requires all
routers attached to the NBMA network to be able to routers attached to the NBMA network to be able to
communicate directly. This restriction may be met on some communicate directly. This restriction may be met on some
non-broadcast networks, such as an ATM subnet utilizing non-broadcast networks, such as an ATM subnet utilizing
SVCs. But it is often not met on other non-broadcast SVCs. But it is often not met on other non-broadcast
networks, such as PVC-only Frame Relay networks. On non- networks, such as PVC-only Frame Relay networks. On non-
broadcast networks where not all routers can communicate broadcast networks where not all routers can communicate
directly you can break the non-broadcast network into directly you can break the non-broadcast network into
logical subnets, with the routers on each subnet being able logical subnets, with the routers on each subnet being able
to communicate directly, and then run each separate subnet to communicate directly, and then run each separate subnet
as an NBMA network (see [15]). This however requires quite a as an NBMA network (see [Ref15]). This however requires
bit of administrative overhead, and is prone to quite a bit of administrative overhead, and is prone to
misconfiguration. It is probably better to run such a non- misconfiguration. It is probably better to run such a non-
broadcast network in Point-to-Multipoint mode. broadcast network in Point-to-Multipoint mode.
In Point-to-MultiPoint mode, OSPF treats all router-to- In Point-to-MultiPoint mode, OSPF treats all router-to-
router connections over the non-broadcast network as if they router connections over the non-broadcast network as if they
were point-to-point links. No Designated Router is elected were point-to-point links. No Designated Router is elected
for the network, nor is there a link-state advertisement for the network, nor is there an LSA generated for the
generated for the network. In fact, a vertex for the Point- network. In fact, a vertex for the Point-to-MultiPoint
to-MultiPoint network does not appear in the graph of the network does not appear in the graph of the link-state
link-state database. database.
Figure 1b illustrates the link-state database representation Figure 1b illustrates the link-state database representation
of a Point-to-MultiPoint network. On the left side of the of a Point-to-MultiPoint network. On the left side of the
figure, a Point-to-MultiPoint network is pictured. It is figure, a Point-to-MultiPoint network is pictured. It is
assumed that all routers can communicate directly, except assumed that all routers can communicate directly, except
for routers RT4 and RT5. I3 though I6 indicate the routers' for routers RT4 and RT5. I3 though I6 indicate the routers'
IP interface addresses on the Point-to-MultiPoint network. IP interface addresses on the Point-to-MultiPoint network.
In the graphical representation of the link-state database, In the graphical representation of the link-state database,
routers that can communicate directly over the Point-to- routers that can communicate directly over the Point-to-
MultiPoint network are joined by bidirectional edges, and MultiPoint network are joined by bidirectional edges, and
each router also has a stub connection to its own IP each router also has a stub connection to its own IP
interface address (which is in contrast to the interface address (which is in contrast to the
representation of real point-to-point links; see Figure 1a). representation of real point-to-point links; see Figure 1a).
On some non-broadcast networks, use of Point-to-MultiPoint On some non-broadcast networks, use of Point-to-MultiPoint
mode and data-link protocols such as Inverse ARP (see [14]) mode and data-link protocols such as Inverse ARP (see
will allow autodiscovery of OSPF neighbors even though [Ref14]) will allow autodiscovery of OSPF neighbors even
broadcast support is not available. though broadcast support is not available.
2.1.2. An example link-state database 2.1.2. An example link-state database
Figure 2 shows a sample map of an Autonomous System. The Figure 2 shows a sample map of an Autonomous System. The
rectangle labelled H1 indicates a host, which has a SLIP rectangle labelled H1 indicates a host, which has a SLIP
**FROM** **FROM**
+---+ +---+ +---+ +---+
|RT3| |RT4| |RT3|RT4|RT5|RT6| |RT3| |RT4| |RT3|RT4|RT5|RT6|
+---+ +---+ * -------------------- +---+ +---+ * --------------------
I3| N2 |I4 * RT3| | X | X | X | I3| N2 |I4 * RT3| | X | X | X |
skipping to change at page 17, line 29 skipping to change at page 17, line 29
All routers can communicate directly over N2, except All routers can communicate directly over N2, except
routers RT4 and RT5. I3 through I6 indicate IP routers RT4 and RT5. I3 through I6 indicate IP
interface addresses interface addresses
connection to Router RT12. Router RT12 is therefore connection to Router RT12. Router RT12 is therefore
advertising a host route. Lines between routers indicate advertising a host route. Lines between routers indicate
physical point-to-point networks. The only point-to-point physical point-to-point networks. The only point-to-point
network that has been assigned interface addresses is the network that has been assigned interface addresses is the
one joining Routers RT6 and RT10. Routers RT5 and RT7 have one joining Routers RT6 and RT10. Routers RT5 and RT7 have
EGP connections to other Autonomous Systems. A set of EGP- BGP connections to other Autonomous Systems. A set of BGP-
learned routes have been displayed for both of these learned routes have been displayed for both of these
routers. routers.
A cost is associated with the output side of each router A cost is associated with the output side of each router
interface. This cost is configurable by the system interface. This cost is configurable by the system
administrator. The lower the cost, the more likely the administrator. The lower the cost, the more likely the
interface is to be used to forward data traffic. Costs are interface is to be used to forward data traffic. Costs are
also associated with the externally derived routing data also associated with the externally derived routing data
(e.g., the EGP-learned routes). (e.g., the BGP-learned routes).
The directed graph resulting from the map in Figure 2 is The directed graph resulting from the map in Figure 2 is
depicted in Figure 3. Arcs are labelled with the cost of depicted in Figure 3. Arcs are labelled with the cost of
the corresponding router output interface. Arcs having no the corresponding router output interface. Arcs having no
labelled cost have a cost of 0. Note that arcs leading from labelled cost have a cost of 0. Note that arcs leading from
networks to routers always have cost 0; they are significant networks to routers always have cost 0; they are significant
nonetheless. Note also that the externally derived routing nonetheless. Note also that the externally derived routing
data appears on the graph as stubs. data appears on the graph as stubs.
+ +
skipping to change at page 19, line 44 skipping to change at page 19, line 44
N15| | | | | | |9 | | | | | | | | | | N15| | | | | | |9 | | | | | | | | | |
H1| | | | | | | | | | | |10| | | | | H1| | | | | | | | | | | |10| | | | |
Figure 3: The resulting directed graph Figure 3: The resulting directed graph
Networks and routers are represented by vertices. Networks and routers are represented by vertices.
An edge of cost X connects Vertex A to Vertex B iff An edge of cost X connects Vertex A to Vertex B iff
the intersection of Column A and Row B is marked the intersection of Column A and Row B is marked
with an X. with an X.
The link-state database is pieced together from link state The link-state database is pieced together from LSAs
advertisements generated by the routers. In the associated generated by the routers. In the associated graphical
graphical representation, the neighborhood of each router or representation, the neighborhood of each router or transit
transit network is represented in a single, separate link network is represented in a single, separate LSA. Figure 4
state advertisement. Figure 4 shows these link-state shows these LSAs graphically. Router RT12 has an interface
advertisements graphically. Router RT12 has an interface to to two broadcast networks and a SLIP line to a host.
two broadcast networks and a SLIP line to a host. Network Network N6 is a broadcast network with three attached
N6 is a broadcast network with three attached routers. The routers. The cost of all links from Network N6 to its
cost of all links from Network N6 to its attached routers is attached routers is 0. Note that the LSA for Network N6 is
0. Note that the link state advertisement for Network N6 is
actually generated by one of the network's attached routers: actually generated by one of the network's attached routers:
the router that has been elected Designated Router for the the router that has been elected Designated Router for the
network. network.
2.2. The shortest-path tree 2.2. The shortest-path tree
When no OSPF areas are configured, each router in the Autonomous When no OSPF areas are configured, each router in the Autonomous
System has an identical link-state database, leading to an System has an identical link-state database, leading to an
identical graphical representation. A router generates its identical graphical representation. A router generates its
routing table from this graph by calculating a tree of shortest routing table from this graph by calculating a tree of shortest
skipping to change at page 20, line 41 skipping to change at page 20, line 40
**FROM** **FROM** **FROM** **FROM**
|RT12|N9|N10|H1| |RT9|RT11|RT12|N9| |RT12|N9|N10|H1| |RT9|RT11|RT12|N9|
* -------------------- * ---------------------- * -------------------- * ----------------------
* RT12| | | | | * RT9| | | |0 | * RT12| | | | | * RT9| | | |0 |
T N9|1 | | | | T RT11| | | |0 | T N9|1 | | | | T RT11| | | |0 |
O N10|2 | | | | O RT12| | | |0 | O N10|2 | | | | O RT12| | | |0 |
* H1|10 | | | | * N9| | | | | * H1|10 | | | | * N9| | | | |
* * * *
RT12's router links N9's network links RT12's router-LSA N9's network-LSA
advertisement advertisement
Figure 4: Individual link state components Figure 4: Individual link state components
Networks and routers are represented by vertices. Networks and routers are represented by vertices.
An edge of cost X connects Vertex A to Vertex B iff An edge of cost X connects Vertex A to Vertex B iff
the intersection of Column A and Row B is marked the intersection of Column A and Row B is marked
with an X. with an X.
RT6(origin) RT6(origin)
RT5 o------------o-----------o Ib RT5 o------------o-----------o Ib
skipping to change at page 21, line 43 skipping to change at page 22, line 4
|2 |2
| |
o N10 o N10
Figure 5: The SPF tree for Router RT6 Figure 5: The SPF tree for Router RT6
Edges that are not marked with a cost have a cost of Edges that are not marked with a cost have a cost of
of zero (these are network-to-router links). Routes of zero (these are network-to-router links). Routes
to networks N12-N15 are external information that is to networks N12-N15 are external information that is
considered in Section 2.3 considered in Section 2.3
Routes to networks belonging to other AS'es (such as N12) appear
as dashed lines on the shortest path tree in Figure 5. Use of
this externally derived routing information is considered in the
next section.
Destination Next Hop Distance Destination Next Hop Distance
__________________________________ __________________________________
N1 RT3 10 N1 RT3 10
N2 RT3 10 N2 RT3 10
N3 RT3 7 N3 RT3 7
N4 RT3 8 N4 RT3 8
Ib * 7 Ib * 7
Ia RT10 12 Ia RT10 12
N6 RT10 8 N6 RT10 8
N7 RT10 12 N7 RT10 12
skipping to change at page 22, line 27 skipping to change at page 22, line 26
N10 RT10 13 N10 RT10 13
N11 RT10 14 N11 RT10 14
H1 RT10 21 H1 RT10 21
__________________________________ __________________________________
RT5 RT5 6 RT5 RT5 6
RT7 RT10 8 RT7 RT10 8
Table 2: The portion of Router RT6's routing table listing local Table 2: The portion of Router RT6's routing table listing local
destinations. destinations.
Routes to networks belonging to other AS'es (such as N12) appear
as dashed lines on the shortest path tree in Figure 5. Use of
this externally derived routing information is considered in the
next section.
2.3. Use of external routing information 2.3. Use of external routing information
After the tree is created the external routing information is After the tree is created the external routing information is
examined. This external routing information may originate from examined. This external routing information may originate from
another routing protocol such as EGP, or be statically another routing protocol such as BGP, or be statically
configured (static routes). Default routes can also be included configured (static routes). Default routes can also be included
as part of the Autonomous System's external routing information. as part of the Autonomous System's external routing information.
External routing information is flooded unaltered throughout the External routing information is flooded unaltered throughout the
AS. In our example, all the routers in the Autonomous System AS. In our example, all the routers in the Autonomous System
know that Router RT7 has two external routes, with metrics 2 and know that Router RT7 has two external routes, with metrics 2 and
9. 9.
OSPF supports two types of external metrics. Type 1 external OSPF supports two types of external metrics. Type 1 external
metrics are expressed in the same units as OSPF interface cost metrics are expressed in the same units as OSPF interface cost
skipping to change at page 24, line 7 skipping to change at page 24, line 11
Both Type 1 and Type 2 external metrics can be present in the AS Both Type 1 and Type 2 external metrics can be present in the AS
at the same time. In that event, Type 1 external metrics always at the same time. In that event, Type 1 external metrics always
take precedence. take precedence.
This section has assumed that packets destined for external This section has assumed that packets destined for external
destinations are always routed through the advertising AS destinations are always routed through the advertising AS
boundary router. This is not always desirable. For example, boundary router. This is not always desirable. For example,
suppose in Figure 2 there is an additional router attached to suppose in Figure 2 there is an additional router attached to
Network N6, called Router RTX. Suppose further that RTX does Network N6, called Router RTX. Suppose further that RTX does
not participate in OSPF routing, but does exchange EGP not participate in OSPF routing, but does exchange BGP
information with the AS boundary router RT7. Then, Router RT7 information with the AS boundary router RT7. Then, Router RT7
would end up advertising OSPF external routes for all would end up advertising OSPF external routes for all
destinations that should be routed to RTX. An extra hop will destinations that should be routed to RTX. An extra hop will
sometimes be introduced if packets for these destinations need sometimes be introduced if packets for these destinations need
always be routed first to Router RT7 (the advertising router). always be routed first to Router RT7 (the advertising router).
To deal with this situation, the OSPF protocol allows an AS To deal with this situation, the OSPF protocol allows an AS
boundary router to specify a "forwarding address" in its boundary router to specify a "forwarding address" in its AS-
external advertisements. In the above example, Router RT7 would external-LSAs. In the above example, Router RT7 would specify
specify RTX's IP address as the "forwarding address" for all RTX's IP address as the "forwarding address" for all those
those destinations whose packets should be routed directly to destinations whose packets should be routed directly to RTX.
RTX.
The "forwarding address" has one other application. It enables The "forwarding address" has one other application. It enables
routers in the Autonomous System's interior to function as routers in the Autonomous System's interior to function as
"route servers". For example, in Figure 2 the router RT6 could "route servers". For example, in Figure 2 the router RT6 could
become a route server, gaining external routing information become a route server, gaining external routing information
through a combination of static configuration and external through a combination of static configuration and external
routing protocols. RT6 would then start advertising itself as routing protocols. RT6 would then start advertising itself as
an AS boundary router, and would originate a collection of OSPF an AS boundary router, and would originate a collection of OSPF
external advertisements. In each external advertisement, Router AS-external-LSAs. In each AS-external-LSA, Router RT6 would
RT6 would specify the correct Autonomous System exit point to specify the correct Autonomous System exit point to use for the
use for the destination through appropriate setting of the destination through appropriate setting of the LSA's "forwarding
advertisement's "forwarding address" field. address" field.
2.4. Equal-cost multipath 2.4. Equal-cost multipath
The above discussion has been simplified by considering only a The above discussion has been simplified by considering only a
single route to any destination. In reality, if multiple single route to any destination. In reality, if multiple
equal-cost routes to a destination exist, they are all equal-cost routes to a destination exist, they are all
discovered and used. This requires no conceptual changes to the discovered and used. This requires no conceptual changes to the
algorithm, and its discussion is postponed until we consider the algorithm, and its discussion is postponed until we consider the
tree-building process in more detail. tree-building process in more detail.
skipping to change at page 28, line 44 skipping to change at page 28, line 49
boundary routers. boundary routers.
Figure 7 shows the resulting link-state database for the Area 1. Figure 7 shows the resulting link-state database for the Area 1.
The figure completely describes that area's intra-area routing. The figure completely describes that area's intra-area routing.
It also shows the complete view of the internet for the two 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 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 routers, RT3 and RT4, to advertise into Area 1 the distances to
all destinations external to the area. These are indicated in all destinations external to the area. These are indicated in
Figure 7 by the dashed stub routes. Also, RT3 and RT4 must Figure 7 by the dashed stub routes. Also, RT3 and RT4 must
advertise into Area 1 the location of the AS boundary routers advertise into Area 1 the location of the AS boundary routers
RT5 and RT7. Finally, external advertisements from RT5 and RT7 RT5 and RT7. Finally, AS-external-LSAs from RT5 and RT7 are
are flooded throughout the entire AS, and in particular flooded throughout the entire AS, and in particular throughout
throughout Area 1. These advertisements are included in Area
1's database, and yield routes to Networks N12-N15.
Routers RT3 and RT4 must also summarize Area 1's topology for
distribution to the backbone. Their backbone advertisements are
........................... ...........................
. + . . + .
. | 3+---+ . N12 N14 . | 3+---+ . N12 N14
. N1|--|RT1|\ 1 . \ N13 / . N1|--|RT1|\ 1 . \ N13 /
. | +---+ \ . 8\ |8/8 . | +---+ \ . 8\ |8/8
. + \ ____ . \|/ . + \ ____ . \|/
. / \ 1+---+8 8+---+6 . / \ 1+---+8 8+---+6
. * N3 *---|RT4|------|RT5|--------+ . * N3 *---|RT4|------|RT5|--------+
. \____/ +---+ +---+ | . \____/ +---+ +---+ |
. + / \ . |7 | . + / \ . |7 |
skipping to change at page 30, line 4 skipping to change at page 30, line 4
. +--+SLIP +----+ . . +---+ . . +--+SLIP +----+ . . +---+ .
. |2 . . |4 . . |2 . . |4 .
. | . . | . . | . . | .
. +---------+ . . +--------+ . . +---------+ . . +--------+ .
. N10 . . N7 . . N10 . . N7 .
. . .Area 2 . . . .Area 2 .
.Area 3 . ................................ .Area 3 . ................................
.......................... ..........................
Figure 6: A sample OSPF area configuration Figure 6: A sample OSPF area configuration
shown in Table 4. These summaries show which networks are Area 1. These LSAs are included in Area 1's database, and yield
contained in Area 1 (i.e., Networks N1-N4), and the distance to routes to Networks N12-N15.
these networks from the routers RT3 and RT4 respectively.
Routers RT3 and RT4 must also summarize Area 1's topology for
distribution to the backbone. Their backbone LSAs are shown in
Table 4. These summaries show which networks are contained in
Area 1 (i.e., Networks N1-N4), and the distance to these
networks from the routers RT3 and RT4 respectively.
The link-state database for the backbone is shown in Figure 8. The link-state database for the backbone is shown in Figure 8.
The set of routers pictured are the backbone routers. Router The set of routers pictured are the backbone routers. Router
RT11 is a backbone router because it belongs to two areas. In RT11 is a backbone router because it belongs to two areas. In
order to make the backbone connected, a virtual link has been order to make the backbone connected, a virtual link has been
configured between Routers R10 and R11. configured between Routers R10 and R11.
The area border routers RT3, RT4, RT7, RT10 and RT11 condense The area border routers RT3, RT4, RT7, RT10 and RT11 condense
the routing information of their attached non-backbone areas for the routing information of their attached non-backbone areas for
distribution via the backbone; these are the dashed stubs that distribution via the backbone; these are the dashed stubs that
skipping to change at page 30, line 28 skipping to change at page 30, line 33
configured to condense Networks N9-N11 and Host H1 into a single configured to condense Networks N9-N11 and Host H1 into a single
route. This yields a single dashed line for networks N9-N11 and route. This yields a single dashed line for networks N9-N11 and
Host H1 in Figure 8. Routers RT5 and RT7 are AS boundary Host H1 in Figure 8. Routers RT5 and RT7 are AS boundary
routers; their externally derived information also appears on routers; their externally derived information also appears on
the graph in Figure 8 as stubs. the graph in Figure 8 as stubs.
The backbone enables the exchange of summary information between The backbone enables the exchange of summary information between
area border routers. Every area border router hears the area area border routers. Every area border router hears the area
summaries from all other area border routers. It then forms a summaries from all other area border routers. It then forms a
picture of the distance to all networks outside of its area by picture of the distance to all networks outside of its area by
examining the collected advertisements, and adding in the examining the collected LSAs, and adding in the backbone
backbone distance to each advertising router. distance to each advertising router.
Again using Routers RT3 and RT4 as an example, the procedure Again using Routers RT3 and RT4 as an example, the procedure
goes as follows: They first calculate the SPF tree for the
backbone. This gives the distances to all other area border
routers. Also noted are the distances to networks (Ia and Ib)
and AS boundary routers (RT5 and RT7) that belong to the
backbone. This calculation is shown in Table 5.
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.
skipping to change at page 32, line 39 skipping to change at page 32, line 39
N14| | |8 | | | | | N14| | |8 | | | | |
N15| | | | |9 | | | N15| | | | |9 | | |
Figure 8: The backbone's database. Figure 8: The backbone's database.
Networks and routers are represented by vertices. Networks and routers are represented by vertices.
An edge of cost X connects Vertex A to Vertex B iff An edge of cost X connects Vertex A to Vertex B iff
the intersection of Column A and Row B is marked the intersection of Column A and Row B is marked
with an X. with an X.
goes as follows: They first calculate the SPF tree for the
backbone. This gives the distances to all other area border
routers. Also noted are the distances to networks (Ia and Ib)
and AS boundary routers (RT5 and RT7) that belong to the
backbone. This calculation is shown in Table 5.
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 to the area by RT3 and RT4. The advertisements that internally to the area by RT3 and RT4. The advertisements that
Router RT3 and RT4 will make into Area 1 are shown in Table 6. Router RT3 and RT4 will make into Area 1 are shown in Table 6.
Note that Table 6 assumes that an area range has been configured Note that Table 6 assumes that an area range has been configured
for the backbone which groups Ia and Ib into a single
advertisement.
The information imported into Area 1 by Routers RT3 and RT4
enables an internal router, such as RT1, to choose an area
border router intelligently. Router RT1 would use RT4 for
Area border dist from dist from Area border dist from dist from
router RT3 RT4 router RT3 RT4
______________________________________ ______________________________________
to RT3 * 21 to RT3 * 21
to RT4 22 * to RT4 22 *
to RT7 20 14 to RT7 20 14
to RT10 15 22 to RT10 15 22
to RT11 18 25 to RT11 18 25
______________________________________ ______________________________________
to Ia 20 27 to Ia 20 27
to Ib 15 22 to Ib 15 22
______________________________________ ______________________________________
to RT5 14 8 to RT5 14 8
to RT7 20 14 to RT7 20 14
Table 5: Backbone distances calculated Table 5: Backbone distances calculated
by Routers RT3 and RT4. by Routers RT3 and RT4.
for the backbone which groups Ia and Ib into a single LSA.
The information imported into Area 1 by Routers RT3 and RT4
enables an internal router, such as RT1, to choose an area
border router intelligently. Router RT1 would use RT4 for
traffic to Network N6, RT3 for traffic to Network N10, and would
load share between the two for traffic to Network N8.
Destination RT3 adv. RT4 adv. Destination RT3 adv. RT4 adv.
_________________________________ _________________________________
Ia,Ib 15 22 Ia,Ib 15 22
N6 16 15 N6 16 15
N7 20 19 N7 20 19
N8 18 18 N8 18 18
N9-N11,H1 19 26 N9-N11,H1 19 26
_________________________________ _________________________________
RT5 14 8 RT5 14 8
RT7 20 14 RT7 20 14
Table 6: Destinations advertised into Area 1 Table 6: Destinations advertised into Area 1
by Routers RT3 and RT4. by Routers RT3 and RT4.
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 Router RT1 can also determine in this manner the shortest path
to the AS boundary routers RT5 and RT7. Then, by looking at RT5 to the AS boundary routers RT5 and RT7. Then, by looking at RT5
and RT7's external advertisements, Router RT1 can decide between and RT7's AS-external-LSAs, Router RT1 can decide between RT5 or
RT5 or RT7 when sending to a destination in another Autonomous RT7 when sending to a destination in another Autonomous System
System (one of the networks N12-N15). (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 cause the backbone to become disconnected. Configuring a will cause the backbone to become disconnected. Configuring a
virtual link between Routers RT7 and RT10 will give the backbone virtual link between Routers RT7 and RT10 will give the backbone
more connectivity and more resistance to such failures. more 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 indicates the range of addresses being described by the mask indicates the range of addresses being described by the
particular route. For example, a summary advertisement for the particular route. For example, a summary-LSA for the
destination 128.185.0.0 with a mask of 0xffff0000 actually is destination 128.185.0.0 with a mask of 0xffff0000 actually is
describing a single route to the collection of destinations describing a single route to the collection of destinations
128.185.0.0 - 128.185.255.255. Similarly, host routes are 128.185.0.0 - 128.185.255.255. Similarly, host routes are
always advertised with a mask of 0xffffffff, indicating the always advertised with a mask of 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 subnetting. This means that a single IP class A, B, or C length subnetting. This means that a single IP class A, B, or C
network number can be broken up into many subnets of various network number can be broken up into many subnets of various
skipping to change at page 35, line 12 skipping to change at page 35, line 20
it is always less specific than any other match. Subnet masks it is always less specific than any other match. Subnet masks
must be assigned so that the best match for any IP destination must be assigned so that the best 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 IP supernetting. For example, a single physical network of IP supernetting. For example, a single physical network
segment could be assigned the [address,mask] pair segment could be assigned the [address,mask] pair
[192.9.4.0,0xfffffc00]. The segment would then be single IP [192.9.4.0,0xfffffc00]. The segment would then be single IP
network, containing addresses from the four consecutive class C network, containing addresses from the four consecutive class C
network numbers 192.9.4.0 through 192.9.7.0. Such addressing is network numbers 192.9.4.0 through 192.9.7.0. Such addressing is
now becoming commonplace with the advent of CIDR (see [10]). now becoming commonplace with the 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 ranges can be employed (see Section C.2 for more address ranges can be employed (see Section C.2 for more
details). Each address range is defined as an [address,mask] details). Each address range is defined as an [address,mask]
pair. Many separate networks may then be contained in a single pair. Many separate networks may then be contained in a single
address range, just as a subnetted network is composed of many address range, just as a subnetted network is composed of many
separate subnets. Area border routers then summarize the area separate subnets. Area border routers then summarize the area
contents (for distribution to the backbone) by advertising a contents (for distribution to the backbone) by advertising a
single route for each address range. The cost of the route is single route for each address range. The cost of the route is
the minimum cost to any of the networks falling in the specified the minimum cost to any of the networks falling in the specified
skipping to change at page 35, line 38 skipping to change at page 35, line 46
natural IP mask. Inside the area, any number of variable sized natural IP mask. Inside the area, any number of variable sized
subnets could be defined. However, external to the area a subnets could be defined. However, external to the area a
single route for the entire subnetted network would be single route for the entire subnetted network would be
distributed, hiding even the fact that the network is subnetted distributed, hiding even the fact that the network is subnetted
at all. The cost of this route is the minimum of the set of at all. The cost of this route is the minimum 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 may consist of AS external advertisements. An OSPF AS database may consist of AS-external-LSAs. An OSPF AS-external-
external advertisement is usually flooded throughout the entire LSA is usually flooded throughout the entire AS. However, OSPF
AS. However, OSPF allows certain areas to be configured as allows certain areas to be configured as "stub areas". AS-
"stub areas". AS external advertisements are not flooded external-LSAs are not flooded into/throughout stub areas;
into/throughout stub areas; routing to AS external destinations routing to AS external destinations in these areas is based on a
in these areas is based on a (per-area) default only. This (per-area) default only. This reduces the link-state database
reduces the link-state database size, and therefore the memory size, and therefore the memory requirements, for a stub area's
requirements, for a stub area's internal routers. internal routers.
In order to take advantage of the OSPF stub area support, In order to take advantage of the OSPF stub area support,
default routing must be used in the stub area. This is default routing must be used in the stub area. This is
accomplished as follows. One or more of the stub area's area accomplished as follows. One or more of the stub area's area
border routers must advertise a default route into the stub area border routers must advertise a default route into the stub area
via summary link advertisements. These summary defaults are via summary-LSAs. These summary defaults are flooded throughout
flooded throughout the stub area, but no further. (For this the stub area, but no further. (For this reason these defaults
reason these defaults pertain only to the particular stub area). pertain only to the particular stub area). These summary
These summary default routes will be used for any destination default routes will be used for any destination that is not
that is not explicitly reachable by an intra-area or inter-area explicitly reachable by an intra-area or inter-area path (i.e.,
path (i.e., AS external destinations). AS external destinations).
An area can be configured as a stub when there is a single exit An area can be configured as a stub when there is a single exit
point from the area, or when the choice of exit point need not point from the area, or when the choice of exit point need not
be made on a per-external-destination basis. For example, Area be made on a per-external-destination basis. For example, Area
3 in Figure 6 could be configured as a stub area, because all 3 in Figure 6 could be configured as a stub area, because all
external traffic must travel though its single area border external traffic must travel though its single area border
router RT11. If Area 3 were configured as a stub, Router RT11 router RT11. If Area 3 were configured as a stub, Router RT11
would advertise a default route for distribution inside Area 3 would advertise a default route for distribution inside Area 3
(in a summary link advertisement), instead of flooding the AS (in a summary-LSA), instead of flooding the AS-external-LSAs for
external advertisements for Networks N12-N15 into/throughout the Networks N12-N15 into/throughout the area.
area.
The OSPF protocol ensures that all routers belonging to an area The OSPF protocol ensures that all routers belonging to an area
agree on whether the area has been configured as a stub. This agree on whether the area has been configured as a stub. This
guarantees that no confusion will arise in the flooding of AS guarantees that no confusion will arise in the flooding of AS-
external advertisements. external-LSAs.
There are a couple of restrictions on the use of stub areas. There are a couple of restrictions on the use of stub areas.
Virtual links cannot be configured through stub areas. In Virtual links cannot be configured through stub areas. In
addition, AS boundary routers cannot be placed internal to stub addition, AS boundary routers cannot be placed internal to stub
areas. areas.
3.7. Partitions of areas 3.7. Partitions of areas
OSPF does not actively attempt to repair area partitions. When OSPF does not actively attempt to repair area partitions. When
an area becomes partitioned, each component simply becomes a an area becomes partitioned, each component simply becomes a
skipping to change at page 38, line 36 skipping to change at page 38, line 36
acquired neighbors. Link-state databases are synchronized between acquired neighbors. Link-state databases are synchronized between
pairs of adjacent routers. On broadcast and NBMA networks, the pairs of adjacent routers. On broadcast and NBMA networks, the
Designated Router determines which routers should become adjacent. Designated Router determines which routers should become adjacent.
Adjacencies control the distribution of routing information. Adjacencies control the distribution of routing information.
Routing updates are sent and received only on adjacencies. Routing updates are sent and received only on adjacencies.
A router periodically advertises its state, which is also called A router periodically advertises its state, which is also called
link state. Link state is also advertised when a router's state link state. Link state is also advertised when a router's state
changes. A router's adjacencies are reflected in the contents of changes. A router's adjacencies are reflected in the contents of
its link state advertisements. This relationship between its LSAs. This relationship between adjacencies and link state
adjacencies and link state allows the protocol to detect dead allows the protocol to detect dead routers in a timely fashion.
routers in a timely fashion.
Link state advertisements are flooded throughout the area. The LSAs are flooded throughout the area. The flooding algorithm is
flooding algorithm is reliable, ensuring that all routers in an area reliable, ensuring that all routers in an area have exactly the same
have exactly the same link-state database. This database consists link-state database. This database consists of the collection of
of the collection of link state advertisements originated by each LSAs originated by each router belonging to the area. From this
router belonging to the area. From this database each router database each router calculates a shortest-path tree, with itself as
calculates a shortest-path tree, with itself as root. This root. This shortest-path tree in turn yields a routing table for
shortest-path tree in turn yields a routing table for the protocol. the protocol.
4.1. Inter-area routing 4.1. Inter-area routing
The previous section described the operation of the protocol The previous section described the operation of the protocol
within a single area. For intra-area routing, no other routing within a single area. For intra-area routing, no other routing
information is pertinent. In order to be able to route to information is pertinent. In order to be able to route to
destinations outside of the area, the area border routers inject destinations outside of the area, the area border routers inject
additional routing information into the area. This additional additional routing information into the area. This additional
information is a distillation of the rest of the Autonomous information is a distillation of the rest of the Autonomous
System's topology. System's topology.
skipping to change at page 40, line 7 skipping to change at page 40, line 6
been designed so that large protocol packets can generally be been designed so that large protocol packets can generally be
split into several smaller protocol packets. This practice is split into several smaller protocol packets. This practice is
recommended; IP fragmentation should be avoided whenever recommended; IP fragmentation should be avoided whenever
possible. possible.
Routing protocol packets should always be sent with the IP TOS Routing protocol packets should always be sent with the IP TOS
field set to 0. If at all possible, routing protocol packets field set to 0. If at all possible, routing protocol packets
should be given preference over regular IP data traffic, both should be given preference over regular IP data traffic, both
when being sent and received. As an aid to accomplishing this, when being sent and received. As an aid to accomplishing this,
OSPF protocol packets should have their IP precedence field set OSPF protocol packets should have their IP precedence field set
to the value Internetwork Control (see [5]). to the value Internetwork Control (see [Ref5]).
All OSPF protocol packets share a common protocol header that is All OSPF protocol packets share a common protocol header that is
described in Appendix A. The OSPF packet types are listed below described in Appendix A. The OSPF packet types are listed below
in Table 8. Their formats are also described in Appendix A. in Table 8. Their formats are also described in Appendix A.
Type Packet name Protocol function Type Packet name Protocol function
__________________________________________________________ __________________________________________________________
1 Hello Discover/maintain neighbors 1 Hello Discover/maintain neighbors
2 Database Description Summarize database contents 2 Database Description Summarize database contents
3 Link State Request Database download 3 Link State Request Database download
skipping to change at page 40, line 30 skipping to change at page 40, line 29
Table 8: OSPF packet types. Table 8: OSPF packet types.
OSPF's Hello protocol uses Hello packets to discover and OSPF's Hello protocol uses Hello packets to discover and
maintain neighbor relationships. The Database Description and maintain neighbor relationships. The Database Description and
Link State Request packets are used in the forming of Link State Request packets are used in the forming of
adjacencies. OSPF's reliable update mechanism is implemented by adjacencies. OSPF's reliable update mechanism is implemented by
the Link State Update and Link State Acknowledgment packets. the Link State Update and Link State Acknowledgment packets.
Each Link State Update packet carries a set of new link state Each Link State Update packet carries a set of new link state
advertisements one hop further away from their point of advertisements (LSAs) one hop further away from their point of
origination. A single Link State Update packet may contain the origination. A single Link State Update packet may contain the
link state advertisements of several routers. Each LSAs of several routers. Each LSA is tagged with the ID of the
advertisement is tagged with the ID of the originating router originating router and a checksum of its link state contents.
and a checksum of its link state contents. Each advertisement Each LSA also has a type field; the different types of OSPF LSAs
also has a type field; the different types of OSPF link state are listed below in Table 9.
advertisements are listed below in Table 9.
OSPF routing packets (with the exception of Hellos) are sent OSPF routing packets (with the exception of Hellos) are sent
only over adjacencies. This means that all OSPF protocol only over adjacencies. This means that all OSPF protocol
packets travel a single IP hop, except those that are sent over packets travel a single IP hop, except those that are sent over
virtual adjacencies. The IP source address of an OSPF protocol virtual adjacencies. The IP source address of an OSPF protocol
packet is one end of a router adjacency, and the IP destination packet is one end of a router adjacency, and the IP destination
address is either the other end of the adjacency or an IP address is either the other end of the adjacency or an IP
multicast address. multicast address.
LS Advertisement Advertisement description LS LSA LSA description
type name type name
_________________________________________________________ ________________________________________________________
1 Router links Originated by all routers. 1 Router-LSAs Originated by all routers.
advertisements This advertisement describes This LSA describes
the collected states of the the collected states of the
router's interfaces to an router's interfaces to an
area. Flooded throughout a area. Flooded throughout a
single area only. single area only.
_________________________________________________________ ________________________________________________________
2 Network links Originated for broadcast 2 Network-LSAs Originated for broadcast
advertisements and NBMA networks by and NBMA networks by
the Designated Router. This the Designated Router. This
advertisement contains the LSA contains the
list of routers connected list of routers connected
to the network. Flooded to the network. Flooded
throughout a single area only. throughout a single area only.
_________________________________________________________ ________________________________________________________
3,4 Summary link Originated by area border 3,4 Summary-LSAs Originated by area border
advertisements routers, and flooded through- routers, and flooded through-
out the advertisement's out the LSA's associated
associated area. Each summary area. Each summary-LSA
link advertisement describes describes a route to a
a route to a destination out- destination outside the area,
side the area, yet still inside yet still inside the AS
the AS (i.e., an inter-area (i.e., an inter-area route).
route). Type 3 advertisements Type 3 summary-LSAs describe
describe routes to networks. routes to networks. Type 4
Type 4 advertisements describe summary-LSAs describe
routes to AS boundary routers. routes to AS boundary routers.
_________________________________________________________ ________________________________________________________
5 AS external link Originated by AS boundary 5 AS-external-LSAs Originated by AS boundary
advertisements routers, and flooded through- routers, and flooded through-
out the AS. Each AS external out the AS. Each
link advertisement describes AS-external-LSA describes
a route to a destination in a route to a destination in
another Autonomous System. another Autonomous System.
Default routes for the AS can Default routes for the AS can
also be described by AS also be described by
external link advertisements. AS-external-LSAs.
Table 9: OSPF link state advertisements. Table 9: OSPF link state advertisements (LSAs).
4.4. Basic implementation requirements 4.4. Basic implementation requirements
An implementation of OSPF requires the following pieces of An implementation of OSPF requires the following pieces of
system support: system support:
Timers Timers
Two different kind of timers are required. The first kind, Two different kind of timers are required. The first kind,
called "single shot timers", fire once and cause a protocol called "single shot timers", fire once and cause a protocol
event to be processed. The second kind, called "interval event to be processed. The second kind, called "interval
skipping to change at page 42, line 35 skipping to change at page 42, line 35
small random amounts should be added to/subtracted from the small random amounts should be added to/subtracted from the
interval timer at each firing. interval timer at each firing.
IP multicast IP multicast
Certain OSPF packets take the form of IP multicast Certain OSPF packets take the form of IP multicast
datagrams. Support for receiving and sending IP multicast datagrams. Support for receiving and sending IP multicast
datagrams, along with the appropriate lower-level protocol datagrams, along with the appropriate lower-level protocol
support, is required. The IP multicast datagrams used by support, is required. The IP multicast datagrams used by
OSPF never travel more than one hop. For this reason, the OSPF never travel more than one hop. For this reason, the
ability to forward IP multicast datagrams is not required. ability to forward IP multicast datagrams is not required.
For information on IP multicast, see [7]. For information on IP multicast, see [Ref7].
Variable-length subnet support Variable-length subnet support
The router's IP protocol support must include the ability to The router's IP protocol support must include the ability to
divide a single IP class A, B, or C network number into many divide a single IP class A, B, or C network number into many
subnets of various sizes. This is commonly called subnets of various sizes. This is commonly called
variable-length subnetting; see Section 3.5 for details. variable-length subnetting; see Section 3.5 for details.
IP supernetting support IP supernetting support
The router's IP protocol support must include the ability to The router's IP protocol support must include the ability to
aggregate contiguous collections of IP class A, B, and C aggregate contiguous collections of IP class A, B, and C
networks into larger quantities called supernets. networks into larger quantities called supernets.
Supernetting has been proposed as one way to improve the Supernetting has been proposed as one way to improve the
scaling of IP routing in the worldwide Internet. For more scaling of IP routing in the worldwide Internet. For more
information on IP supernetting, see [10]. information on IP supernetting, see [Ref10].
Lower-level protocol support Lower-level protocol support
The lower level protocols referred to here are the network The lower level protocols referred to here are the network
access protocols, such as the Ethernet data link layer. access protocols, such as the Ethernet data link layer.
Indications must be passed from these protocols to OSPF as Indications must be passed from these protocols to OSPF as
the network interface goes up and down. For example, on an the network interface goes up and down. For example, on an
ethernet it would be valuable to know when the ethernet ethernet it would be valuable to know when the ethernet
transceiver cable becomes unplugged. transceiver cable becomes unplugged.
Non-broadcast lower-level protocol support Non-broadcast lower-level protocol support
On non-broadcast networks, the OSPF Hello Protocol can be On non-broadcast networks, the OSPF Hello Protocol can be
aided by providing an indication when an attempt is made to aided by providing an indication when an attempt is made to
send a packet to a dead or non-existent router. For send a packet to a dead or non-existent router. For
example, on an X.25 PDN a dead neighboring router may be example, on an X.25 PDN a dead neighboring router may be
indicated by the reception of a X.25 clear with an indicated by the reception of a X.25 clear with an
appropriate cause and diagnostic, and this information would appropriate cause and diagnostic, and this information would
be passed to OSPF. be passed to OSPF.
List manipulation primitives List manipulation primitives
Much of the OSPF functionality is described in terms of its Much of the OSPF functionality is described in terms of its
operation on lists of link state advertisements. For operation on lists of LSAs. For example, the collection of
example, the collection of advertisements that will be LSAs that will be retransmitted to an adjacent router until
retransmitted to an adjacent router until acknowledged are acknowledged are described as a list. Any particular LSA
described as a list. Any particular advertisement may be on may be on many such lists. An OSPF implementation needs to
many such lists. An OSPF implementation needs to be able to be able to manipulate these lists, adding and deleting
manipulate these lists, adding and deleting constituent constituent LSAs as necessary.
advertisements as necessary.
Tasking support Tasking support
Certain procedures described in this specification invoke Certain procedures described in this specification invoke
other procedures. At times, these other procedures should other procedures. At times, these other procedures should
be executed in-line, that is, before the current procedure be executed in-line, that is, before the current procedure
is finished. This is indicated in the text by instructions is finished. This is indicated in the text by instructions
to execute a procedure. At other times, the other to execute a procedure. At other times, the other
procedures are to be executed only when the current procedures are to be executed only when the current
procedure has finished. This is indicated by instructions procedure has finished. This is indicated by instructions
to schedule a task. to schedule a task.
4.5. Optional OSPF capabilities 4.5. Optional OSPF capabilities
The OSPF protocol defines several optional capabilities. A The OSPF protocol defines several optional capabilities. A
router indicates the optional capabilities that it supports in router indicates the optional capabilities that it supports in
its OSPF Hello packets, Database Description packets and in its its OSPF Hello packets, Database Description packets and in its
link state advertisements. This enables routers supporting a LSAs. This enables routers supporting a mix of optional
mix of optional capabilities to coexist in a single Autonomous capabilities to coexist in a single Autonomous System.
System.
Some capabilities must be supported by all routers attached to a Some capabilities must be supported by all routers attached to a
specific area. In this case, a router will not accept a specific area. In this case, a router will not accept a
neighbor's Hello Packet unless there is a match in reported neighbor's Hello Packet unless there is a match in reported
capabilities (i.e., a capability mismatch prevents a neighbor capabilities (i.e., a capability mismatch prevents a neighbor
relationship from forming). An example of this is the relationship from forming). An example of this is the
ExternalRoutingCapability (see below). ExternalRoutingCapability (see below).
Other capabilities can be negotiated during the Database Other capabilities can be negotiated during the Database
Exchange process. This is accomplished by specifying the Exchange process. This is accomplished by specifying the
optional capabilities in Database Description packets. A optional capabilities in Database Description packets. A
capability mismatch with a neighbor in this case will result in capability mismatch with a neighbor in this case will result in
only a subset of the link state database being exchanged between only a subset of the link state database being exchanged between
the two neighbors. the two neighbors.
The routing table build process can also be affected by the The routing table build process can also be affected by the
presence/absence of optional capabilities. For example, since presence/absence of optional capabilities. For example, since
the optional capabilities are reported in link state the optional capabilities are reported in LSAs, routers
advertisements, routers incapable of certain functions can be incapable of certain functions can be avoided when building the
avoided when building the shortest path tree. An example of shortest path tree. An example of this is the TOS routing
this is the TOS routing capability (see below). capability (see below).
The OSPF optional capabilities defined in this memo are listed The OSPF optional capabilities defined in this memo are listed
below. See Section A.2 for more information. below. See Section A.2 for more information.
ExternalRoutingCapability ExternalRoutingCapability
Entire OSPF areas can be configured as "stubs" (see Section Entire OSPF areas can be configured as "stubs" (see Section
3.6). AS external advertisements will not be flooded into 3.6). AS-external-LSAs will not be flooded into stub areas.
stub areas. This capability is represented by the E-bit in This capability is represented by the E-bit in the OSPF
the OSPF Options field (see Section A.2). In order to Options field (see Section A.2). In order to ensure
ensure consistent configuration of stub areas, all routers consistent configuration of stub areas, all routers
interfacing to such an area must have the E-bit clear in interfacing to such an area must have the E-bit clear in
their Hello packets (see Sections 9.5 and 10.5). their Hello packets (see Sections 9.5 and 10.5).
TOS capability TOS capability
All OSPF implementations must be able to calculate separate All OSPF implementations must be able to calculate separate
routes based on IP Type of Service. However, to save routes based on IP Type of Service. However, to save
routing table space and processing resources, an OSPF router routing table space and processing resources, an OSPF router
can be configured to ignore TOS when forwarding packets. In can be configured to ignore TOS when forwarding packets. In
this case, the router calculates routes for TOS 0 only. this case, the router calculates routes for TOS 0 only.
This capability is represented by the T-bit in the OSPF This capability is represented by the T-bit in the OSPF
skipping to change at page 45, line 20 skipping to change at page 45, line 14
done is noted. OSPF areas, interfaces and neighbors also have done is noted. OSPF areas, interfaces and neighbors also have
associated data structures that are described later in this associated data structures that are described later in this
specification. specification.
Router ID Router ID
A 32-bit number that uniquely identifies this router in the AS. A 32-bit number that uniquely identifies this router in the AS.
One possible implementation strategy would be to use the One possible implementation strategy would be to use the
smallest IP interface address belonging to the router. If a smallest IP interface address belonging to the router. If a
router's OSPF Router ID is changed, the router's OSPF software router's OSPF Router ID is changed, the router's OSPF software
should be restarted before the new Router ID takes effect. In should be restarted before the new Router ID takes effect. In
this case the router should flush its self-originated link state this case the router should flush its self-originated LSAs from
advertisements from the routing domain (see Section 14.1) before the routing domain (see Section 14.1) before restarting, or they
restarting, or they will persist for up to MaxAge minutes. will persist for up to MaxAge minutes.
Area structures Area structures
Each one of the areas to which the router is connected has its Each one of the areas to which the router is connected has its
own data structure. This data structure describes the working own data structure. This data structure describes the working
of the basic OSPF algorithm. Remember that each area runs a of the basic OSPF algorithm. Remember that each area runs a
separate copy of the basic OSPF algorithm. separate copy of the basic OSPF algorithm.
Backbone (area) structure Backbone (area) structure
The OSPF backbone area is responsible for the dissemination of The OSPF backbone area is responsible for the dissemination of
inter-area routing information. inter-area routing information.
skipping to change at page 45, line 50 skipping to change at page 45, line 44
common area, called the virtual link's Transit area. Virtual common area, called the virtual link's Transit area. Virtual
links are part of the backbone, and behave as if they were links are part of the backbone, and behave as if they were
unnumbered point-to-point networks between the two routers. A unnumbered point-to-point networks between the two routers. A
virtual link uses the intra-area routing of its Transit area to virtual link uses the intra-area routing of its Transit area to
forward packets. Virtual links are brought up and down through forward packets. Virtual links are brought up and down through
the building of the shortest-path trees for the Transit area. the building of the shortest-path trees for the Transit area.
List of external routes List of external routes
These are routes to destinations external to the Autonomous These are routes to destinations external to the Autonomous
System, that have been gained either through direct experience System, that have been gained either through direct experience
with another routing protocol (such as EGP), or through with another routing protocol (such as BGP), or through
configuration information, or through a combination of the two configuration information, or through a combination of the two
(e.g., dynamic external information to be advertised by OSPF (e.g., dynamic external information to be advertised by OSPF
with configured metric). Any router having these external routes with configured metric). Any router having these external routes
is called an AS boundary router. These routes are advertised by is called an AS boundary router. These routes are advertised by
the router into the OSPF routing domain via AS external link the router into the OSPF routing domain via AS-external-LSAs.
advertisements.
List of AS external link advertisements List of AS-external-LSAs
Part of the link-state database. These have originated from the Part of the link-state database. These have originated from the
AS boundary routers. They comprise routes to destinations AS boundary routers. They comprise routes to destinations
external to the Autonomous System. Note that, if the router is external to the Autonomous System. Note that, if the router is
itself an AS boundary router, some of these AS external link itself an AS boundary router, some of these AS-external-LSAs
advertisements have been self-originated. have been self-originated.
The routing table The routing table
Derived from the link-state database. Each entry in the routing Derived from the link-state database. Each entry in the routing
table is indexed by a destination, and contains the table is indexed by a destination, and contains the
destination's cost and a set of paths to use in forwarding destination's cost and a set of paths to use in forwarding
packets to the destination. A path is described by its type and packets to the destination. A path is described by its type and
next hop. For more information, see Section 11. next hop. For more information, see Section 11.
TOS capability TOS capability
This item indicates whether the router will calculate separate This item indicates whether the router will calculate separate
skipping to change at page 46, line 49 skipping to change at page 46, line 44
The area data structure contains all the information used to run the The area data structure contains all the information used to run the
basic OSPF routing algorithm. Each area maintains its own link-state basic OSPF routing algorithm. Each area maintains its own link-state
database. A network belongs to a single area, and a router interface database. A network belongs to a single area, and a router interface
connects to a single area. Each router adjacency also belongs to a connects to a single area. Each router adjacency also belongs to a
single area. single area.
The OSPF backbone is the special OSPF area responsible for The OSPF backbone is the special OSPF area responsible for
disseminating inter-area routing information. disseminating inter-area routing information.
The area link-state database consists of the collection of router The area link-state database consists of the collection of router-
links, network links and summary link advertisements that have 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.
+----+ +----+
|RT10|------+ |RT10|------+
+----+ \+-------------+ +----+ \+-------------+
/ \ |Routing Table| / \ |Routing Table|
/ \ +-------------+ / \ +-------------+
/ \ / \
+------+ / \ +--------+ +------+ / \ +--------+
|Area 2|---+ +---|Backbone| |Area 2|---+ +---|Backbone|
+------+***********+ +--------+ +------+***********+ +--------+
/ \ * / \ / \ * / \
skipping to change at page 47, line 32 skipping to change at page 47, line 33
|Neighbor| |Neighbor| | |Neighbor RT11| |Neighbor RT6| |Neighbor| |Neighbor| | |Neighbor RT11| |Neighbor RT6|
| RT8 | | RT7 | | +-------------+ +------------+ | RT8 | | RT7 | | +-------------+ +------------+
+--------+ +--------+ | +--------+ +--------+ |
| |
+-------------+ +-------------+
|Neighbor RT11| |Neighbor RT11|
+-------------+ +-------------+
Figure 9: Router RT10's Data structures Figure 9: Router RT10's Data structures
originated from the area's routers. This information is flooded
throughout a single area only. The list of AS external link
advertisements (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 address ranges can be employed. Each address range is area address ranges can be employed. Each address range is
specified by an [address,mask] pair and a status indication of specified by an [address,mask] pair and a status indication of
either Advertise or DoNotAdvertise (see Section 12.4.3). either Advertise or DoNotAdvertise (see Section 12.4.3).
Associated router interfaces Associated router interfaces
This router's interfaces connecting to the area. A router This router's interfaces connecting to the area. A router
interface belongs to one and only one area (or the backbone). interface belongs to one and only one area (or the backbone).
For the backbone area this list includes all the virtual links. For the backbone area this list includes all the virtual links.
A virtual link is identified by the Router ID of its other A virtual link is identified by the Router ID of its other
endpoint; its cost is the cost of the shortest intra-area path endpoint; its cost is the cost of the shortest intra-area path
through the Transit area that exists between the two routers. through the Transit area that exists between the two routers.
List of router links advertisements List of router-LSAs
A router links advertisement is generated by each router in the A router-LSA is generated by each router in the area. It
area. It describes the state of the router's interfaces to the describes the state of the router's interfaces to the area.
area.
List of network links advertisements List of network-LSAs
One network links advertisement is generated for each transit One network-LSA is generated for each transit broadcast and NBMA
broadcast and NBMA network in the area. A network links network in the area. A network-LSA describes the set of routers
advertisement describes the set of routers currently connected currently connected to the network.
to the network.
List of summary link advertisements List of summary-LSAs
Summary link advertisements originate from the area's area Summary-LSAs originate from the area's area border routers.
border routers. They describe routes to destinations internal They describe routes to destinations internal to the Autonomous
to the Autonomous System, yet external to the area (i.e., System, yet external to the area (i.e., inter-area
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 links and network links root. Derived from the collected router-LSAs and network-LSAs
advertisements by the Dijkstra algorithm (see Section 16.1). by the Dijkstra algorithm (see Section 16.1).
TransitCapability TransitCapability
Set to TRUE if and only if there are one or more active virtual This parameter indicates whether the area can carry data traffic
links using the area as a Transit area. Equivalently, this that neither originates nor terminates in the area itself. This
parameter indicates whether the area can carry data traffic that
neither originates nor terminates in the area itself. This
parameter is calculated when the area's shortest-path tree is parameter is calculated when the area's shortest-path tree is
built (see Section 16.1, and is used as an input to a subsequent built (see Section 16.1, where TransitCapability is set to TRUE
step of the routing table build process (see Section 16.3). if and only if there are one or more fully adjacent virtual
links using the area as Transit area), and is used as an input
to a subsequent step of the routing table build process (see
Section 16.3). When an area's TransitCapability is set to TRUE,
the area is said to be a "transit area".
ExternalRoutingCapability ExternalRoutingCapability
Whether AS external advertisements will be flooded Whether AS-external-LSAs will be flooded into/throughout the
into/throughout the area. This is a configurable parameter. If area. This is a configurable parameter. If AS-external-LSAs
AS external advertisements are excluded from the area, the area are excluded from the area, the area is called a "stub". Within
is called a "stub". Within stub areas, routing to AS external stub areas, routing to AS external destinations will be based
destinations will be based solely on a default summary route. solely on a default summary route. The backbone cannot be
The backbone cannot be configured as a stub area. Also, virtual configured as a stub area. Also, virtual links cannot be
links cannot be configured through stub areas. For more configured through stub areas. For more information, see
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 link 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. There can be a separate cost
configured for each IP TOS. 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
skipping to change at page 50, line 10 skipping to change at page 50, line 5
Router potential, sends Hello Packets to all other potential Router potential, sends Hello Packets to all other potential
Designated Routers when its interface to the NBMA network first Designated Routers when its interface to the NBMA network first
becomes operational. This is an attempt to find the Designated becomes operational. This is an attempt to find the Designated
Router for the network. If the router itself is elected Router for the network. If the router itself is elected
Designated Router, it begins sending Hello Packets to all other Designated Router, it begins sending Hello Packets to all other
routers attached to the network. routers attached to the network.
On Point-to-MultiPoint networks, a router sends Hello Packets to On Point-to-MultiPoint networks, a router sends Hello Packets to
all neighbors with which it can communicate directly. These all neighbors with which it can communicate directly. These
neighbors may be discovered dynamically through a protocol such neighbors may be discovered dynamically through a protocol such
as Inverse ARP (see [14]), or they may be configured. as Inverse ARP (see [Ref14]), or they may be configured.
After a neighbor has been discovered, bidirectional After a neighbor has been discovered, bidirectional
communication ensured, and (if on a broadcast or NBMA network) a communication ensured, and (if on a broadcast or NBMA network) a
Designated Router elected, a decision is made regarding whether Designated Router elected, a decision is made regarding whether
or not an adjacency should be formed with the neighbor (see or not an adjacency should be formed with the neighbor (see
Section 10.4). If an adjacency is to be formed, the first step Section 10.4). If an adjacency is to be formed, the first step
is to synchronize the neighbors' link-state databases. This is is to synchronize the neighbors' link-state databases. This is
covered in the next section. covered in the next section.
7.2. The Synchronization of Databases 7.2. The Synchronization of Databases
In a link-state routing algorithm, it is very important for all In a link-state routing algorithm, it is very important for all
routers' link-state databases to stay synchronized. OSPF routers' link-state databases to stay synchronized. OSPF
simplifies this by requiring only adjacent routers to remain simplifies this by requiring only adjacent routers to remain
synchronized. The synchronization process begins as soon as the synchronized. The synchronization process begins as soon as the
routers attempt to bring up the adjacency. Each router routers attempt to bring up the adjacency. Each router
describes its database by sending a sequence of Database describes its database by sending a sequence of Database
Description packets to its neighbor. Each Database Description Description packets to its neighbor. Each Database Description
Packet describes a set of link state advertisements belonging to Packet describes a set of LSAs belonging to the router's
the router's database. When the neighbor sees a link state database. When the neighbor sees an LSA that is more recent
advertisement that is more recent than its own database copy, it than its own database copy, it makes a note that this newer LSA
makes a note that this newer advertisement should be requested. should be requested.
This sending and receiving of Database Description packets is This sending and receiving of Database Description packets is
called the "Database Exchange Process". During this process, called the "Database Exchange Process". During this process,
the two routers form a master/slave relationship. Each Database the two routers form a master/slave relationship. Each Database
Description Packet has a sequence number. Database Description Description Packet has a sequence number. Database Description
Packets sent by the master (polls) are acknowledged by the slave Packets sent by the master (polls) are acknowledged by the slave
through echoing of the sequence number. Both polls and their through echoing of the sequence number. Both polls and their
responses contain summaries of link state data. The master is responses contain summaries of link state data. The master is
the only one allowed to retransmit Database Description Packets. the only one allowed to retransmit Database Description Packets.
It does so only at fixed intervals, the length of which is the It does so only at fixed intervals, the length of which is the
configured per-interface constant RxmtInterval. configured per-interface constant RxmtInterval.
Each Database Description contains an indication that there are Each Database Description contains an indication that there are
more packets to follow --- the M-bit. The Database Exchange more packets to follow --- the M-bit. The Database Exchange
Process is over when a router has received and sent Database Process is over when a router has received and sent Database
Description Packets with the M-bit off. Description Packets with the M-bit off.
During and after the Database Exchange Process, each router has During and after the Database Exchange Process, each router has
a list of those link state advertisements for which the neighbor a list of those LSAs for which the neighbor has more up-to-date
has more up-to-date instances. These advertisements are instances. These LSAs are requested in Link State Request
requested in Link State Request Packets. Link State Request Packets. Link State Request packets that are not satisfied are
packets that are not satisfied are retransmitted at fixed retransmitted at fixed intervals of time RxmtInterval. When the
intervals of time RxmtInterval. When the Database Description Database Description Process has completed and all Link State
Process has completed and all Link State Requests have been Requests have been satisfied, the databases are deemed
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' link state two routers' router-LSAs.
advertisements.
The adjacency is used by the flooding procedure as soon as the The adjacency is used by the flooding procedure as soon as the
Database Exchange Process begins. This simplifies database Database Exchange Process begins. This simplifies database
synchronization, and guarantees that it finishes in a synchronization, and guarantees that it finishes in a
predictable period of time. predictable period of time.
7.3. The Designated Router 7.3. The Designated Router
Every broadcast and NBMA network has a Designated Router. The Every broadcast and NBMA network has a Designated Router. The
Designated Router performs two main functions for the routing Designated Router performs two main functions for the routing
protocol: protocol:
o The Designated Router originates a network links o The Designated Router originates a network-LSA on behalf of
advertisement on behalf of the network. This advertisement the network. This LSA lists the set of routers (including
lists the set of routers (including the Designated Router the Designated Router itself) currently attached to the
itself) currently attached to the network. The Link State network. The Link State ID for this LSA (see Section
ID for this advertisement (see Section 12.1.4) is the IP 12.1.4) is the IP interface address of the Designated
interface address of the Designated Router. The IP network Router. The IP network number can then be obtained by using
number can then be obtained by using the network's the network's subnet/network mask.
subnet/network mask.
o The Designated Router becomes adjacent to all other routers o The Designated Router becomes adjacent to all other routers
on the network. Since the link state databases are on the network. Since the link state databases are
synchronized across adjacencies (through adjacency bring-up synchronized across adjacencies (through adjacency bring-up
and then the flooding procedure), the Designated Router and then the flooding procedure), the Designated Router
plays a central part in the synchronization process. plays a central part in the synchronization process.
The Designated Router is elected by the Hello Protocol. A The Designated Router is elected by the Hello Protocol. A
router's Hello Packet contains its Router Priority, which is router's Hello Packet contains its Router Priority, which is
configurable on a per-interface basis. In general, when a configurable on a per-interface basis. In general, when a
skipping to change at page 52, line 21 skipping to change at page 52, line 14
the Designated Router multicasts its Link State Update Packets the Designated Router multicasts its Link State Update Packets
to the address AllSPFRouters, rather than sending separate to the address AllSPFRouters, rather than sending separate
packets over each adjacency. packets over each adjacency.
Section 2 of this document discusses the directed graph Section 2 of this document discusses the directed graph
representation of an area. Router nodes are labelled with their representation of an area. Router nodes are labelled with their
Router ID. Transit network nodes are actually labelled with the Router ID. Transit network nodes are actually labelled with the
IP address of their Designated Router. It follows that when the IP address of their Designated Router. It follows that when the
Designated Router changes, it appears as if the network node on Designated Router changes, it appears as if the network node on
the graph is replaced by an entirely new node. This will cause the graph is replaced by an entirely new node. This will cause
the network and all its attached routers to originate new link the network and all its attached routers to originate new LSAs.
state advertisements. Until the link-state databases again Until the link-state databases again converge, some temporary
converge, some temporary loss of connectivity may result. This loss of connectivity may result. This may result in ICMP
may result in ICMP unreachable messages being sent in response unreachable messages being sent in response to data traffic.
to data traffic. For that reason, the Designated Router should For that reason, the Designated Router should change only
change only infrequently. Router Priorities should be infrequently. Router Priorities should be configured so that
configured so that the most dependable router on a network the most dependable router on a network eventually becomes
eventually becomes Designated Router. Designated Router.
7.4. The Backup Designated Router 7.4. The Backup Designated Router
In order to make the transition to a new Designated Router In order to make the transition to a new Designated Router
smoother, there is a Backup Designated Router for each broadcast smoother, there is a Backup Designated Router for each broadcast
and NBMA network. The Backup Designated Router is also adjacent and NBMA network. The Backup Designated Router is also adjacent
to all routers on the network, and becomes Designated Router to all routers on the network, and becomes Designated Router
when the previous Designated Router fails. If there were no when the previous Designated Router fails. If there were no
Backup Designated Router, when a new Designated Router became Backup Designated Router, when a new Designated Router became
necessary, new adjacencies would have to be formed between the necessary, new adjacencies would have to be formed between the
new Designated Router and all other routers attached to the new Designated Router and all other routers attached to the
network. Part of the adjacency forming process is the network. Part of the adjacency forming process is the
synchronizing of link-state databases, which can potentially synchronizing of link-state databases, which can potentially
take quite a long time. During this time, the network would not take quite a long time. During this time, the network would not
be available for transit data traffic. The Backup Designated be available for transit data traffic. The Backup Designated
obviates the need to form these adjacencies, since they already obviates the need to form these adjacencies, since they already
exist. This means the period of disruption in transit traffic exist. This means the period of disruption in transit traffic
lasts only as long as it takes to flood the new link state lasts only as long as it takes to flood the new LSAs (which
advertisements (which announce the new Designated Router). announce the new Designated Router).
The Backup Designated Router does not generate a network links The Backup Designated Router does not generate a network-LSA for
advertisement for the network. (If it did, the transition to a the network. (If it did, the transition to a new Designated
new Designated Router would be even faster. However, this is a Router would be even faster. However, this is a tradeoff
tradeoff between database size and speed of convergence when the between database size and speed of convergence when the
Designated Router disappears.) Designated Router disappears.)
The Backup Designated Router is also elected by the Hello The Backup Designated Router is also elected by the Hello
Protocol. Each Hello Packet has a field that specifies the Protocol. Each Hello Packet has a field that specifies the
Backup Designated Router for the network. Backup Designated Router for the network.
In some steps of the flooding procedure, the Backup Designated In some steps of the flooding procedure, the Backup Designated
Router plays a passive role, letting the Designated Router do Router plays a passive role, letting the Designated Router do
more of the work. This cuts down on the amount of local routing more of the work. This cuts down on the amount of local routing
traffic. See Section 13.3 for more information. traffic. See Section 13.3 for more information.
skipping to change at page 54, line 5 skipping to change at page 53, line 40
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 has become the Designated Router, and Router RT3 the Backup RT7 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 performs a lesser function during the flooding procedure Router performs a lesser function during the flooding procedure
than the Designated Router (see Section 13.3). This is the than the Designated Router (see Section 13.3). This is the
reason for the dashed lines connecting the Backup Designated reason for the dashed lines connecting the Backup Designated
Router RT3. Router RT3.
8. Protocol Packet Processing
This section discusses the general processing of OSPF routing
protocol packets. It is very important that the router link-state
databases remain synchronized. For this reason, routing protocol
packets should get preferential treatment over ordinary data
packets, both in sending and receiving.
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
+---+ +---+ +---+ +---+
|RT1|------------|RT2| o---------------o |RT1|------------|RT2| o---------------o
+---+ N1 +---+ RT1 RT2 +---+ N1 +---+ RT1 RT2
RT7 RT7
o---------+ o---------+
+---+ +---+ +---+ /|\ | +---+ +---+ +---+ /|\ |
|RT7| |RT3| |RT4| / | \ | |RT7| |RT3| |RT4| / | \ |
+---+ +---+ +---+ / | \ | +---+ +---+ +---+ / | \ |
| | | / | \ | | | | / | \ |
+-----------------------+ RT5o RT6o oRT4 | +-----------------------+ RT5o RT6o oRT4 |
| | N2 * * * | | | N2 * * * |
+---+ +---+ * * * | +---+ +---+ * * * |
|RT5| |RT6| * * * | |RT5| |RT6| * * * |
+---+ +---+ *** | +---+ +---+ *** |
o---------+ o---------+
RT3 RT3
Figure 10: The graph of adjacencies Figure 10: The graph of adjacencies
8. Protocol Packet Processing
This section discusses the general processing of OSPF routing
protocol packets. It is very important that the router link-state
databases remain synchronized. For this reason, routing protocol
packets should get preferential treatment over ordinary data
packets, both in sending and receiving.
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 All routing protocol packets begin with a standard header. The
sections below provide details on how to fill in and verify this sections below provide details on how to fill in and verify this
standard header. Then, for each packet type, the section giving standard header. Then, for each packet type, the section giving
more details on that particular packet type's processing is listed. more details on that particular packet type's processing is listed.
8.1. Sending protocol packets 8.1. Sending protocol packets
When a router sends a routing protocol packet, it fills in the When a router sends a routing protocol packet, it fills in the
skipping to change at page 59, line 27 skipping to change at page 59, line 17
An OSPF interface is the connection between a router and a network. An OSPF interface is the connection between a router and a network.
There is a single OSPF interface structure for each attached There is a single OSPF interface structure for each attached
network; each interface structure has at most one IP interface network; each interface structure has at most one IP interface
address (see below). The support for multiple addresses on a single address (see below). The support for multiple addresses on a single
network is a matter for future consideration. network is a matter for future consideration.
An OSPF interface can be considered to belong to the area that An OSPF interface can be considered to belong to the area that
contains the attached network. All routing protocol packets contains the attached network. All routing protocol packets
originated by the router over this interface are labelled with the originated by the router over this interface are labelled with the
interface's Area ID. One or more router adjacencies may develop interface's Area ID. One or more router adjacencies may develop
over an interface. A router's link state advertisements reflect the over an interface. A router's LSAs reflect the state of its
state of its interfaces and their associated adjacencies. interfaces and their associated adjacencies.
The following data items are associated with an interface. Note The following data items are associated with an interface. Note
that a number of these items are actually configuration for the that a number of these items are actually configuration for the
attached network; such items must be the same for all routers attached network; such items must be the same for all routers
connected to the network. connected to the network.
Type Type
The OSPF interface type is either point-to-point, broadcast, The OSPF interface type is either point-to-point, broadcast,
NBMA, Point-to-MultiPoint or virtual link. NBMA, Point-to-MultiPoint or virtual link.
State State
The functional level of an interface. State determines whether The functional level of an interface. State determines whether
or not full adjacencies are allowed to form over the interface. or not full adjacencies are allowed to form over the interface.
State is also reflected in the router's link state State is also reflected in the router's LSAs.
advertisements.
IP interface address IP interface address
The IP address associated with the interface. This appears as The IP address associated with the interface. This appears as
the IP source address in all routing protocol packets originated the IP source address in all routing protocol packets originated
over this interface. Interfaces to unnumbered point-to-point over this interface. Interfaces to unnumbered point-to-point
networks do not have an associated IP address. networks do not have an associated IP address.
IP interface mask IP interface mask
Also referred to as the subnet mask, this indicates the portion Also referred to as the subnet mask, this indicates the portion
of the IP interface address that identifies the attached of the IP interface address that identifies the attached
skipping to change at page 60, line 35 skipping to change at page 60, line 22
the router sends on the interface. Advertised in Hello packets the router sends on the interface. Advertised in Hello packets
sent out this interface. sent out this interface.
RouterDeadInterval RouterDeadInterval
The number of seconds before the router's neighbors will declare The number of seconds before the router's neighbors will declare
it down, when they stop hearing the router's Hello Packets. it down, when they stop hearing the router's Hello Packets.
Advertised in Hello packets sent out this interface. Advertised in Hello packets sent out this interface.
InfTransDelay InfTransDelay
The estimated number of seconds it takes to transmit a Link The estimated number of seconds it takes to transmit a Link
State Update Packet over this interface. Link state State Update Packet over this interface. LSAs contained in the
advertisements contained in the Link State Update packet will Link State Update packet will have their age incremented by this
have their age incremented by this amount before transmission. amount before transmission. This value should take into account
This value should take into account transmission and propagation transmission and propagation delays; it must be greater than
delays; it must be greater than zero. zero.
Router Priority Router Priority
An 8-bit unsigned integer. When two routers attached to a An 8-bit unsigned integer. When two routers attached to a
network both attempt to become Designated Router, the one with network both attempt to become Designated Router, the one with
the highest Router Priority takes precedence. A router whose the highest Router Priority takes precedence. A router whose
Router Priority is set to 0 is ineligible to become Designated Router Priority is set to 0 is ineligible to become Designated
Router on the attached network. Advertised in Hello packets Router on the attached network. Advertised in Hello packets
sent out this interface. sent out this interface.
Hello Timer Hello Timer
skipping to change at page 61, line 25 skipping to change at page 61, line 11
by the Hello Protocol. Adjacencies will be formed to some of by the Hello Protocol. Adjacencies will be formed to some of
these neighbors. The set of adjacent neighbors can be these neighbors. The set of adjacent neighbors can be
determined by an examination of all of the neighbors' states. determined by an examination of all of the neighbors' states.
Designated Router Designated Router
The Designated Router selected for the attached network. The The Designated Router selected for the attached network. The
Designated Router is selected on all broadcast and NBMA networks Designated Router is selected on all broadcast and NBMA networks
by the Hello Protocol. Two pieces of identification are kept by the Hello Protocol. Two pieces of identification are kept
for the Designated Router: its Router ID and its IP interface for the Designated Router: its Router ID and its IP interface
address on the network. The Designated Router advertises link address on the network. The Designated Router advertises link
state for the network; this network link state advertisement is state for the network; this network-LSA is labelled with the
labelled with the Designated Router's IP address. The Designated Router's IP address. The Designated Router is
Designated Router is initialized to 0.0.0.0, which indicates the initialized to 0.0.0.0, which indicates the lack of a Designated
lack of a Designated Router. Router.
Backup Designated Router Backup Designated Router
The Backup Designated Router is also selected on all broadcast The Backup Designated Router is also selected on all broadcast
and NBMA networks by the Hello Protocol. All routers on the and NBMA networks by the Hello Protocol. All routers on the
attached network become adjacent to both the Designated Router attached network become adjacent to both the Designated Router
and the Backup Designated Router. The Backup Designated Router and the Backup Designated Router. The Backup Designated Router
becomes Designated Router when the current Designated Router becomes Designated Router when the current Designated Router
fails. The Backup Designated Router is initialized to 0.0.0.0, fails. The Backup Designated Router is initialized to 0.0.0.0,
indicating the lack of a Backup Designated Router. indicating the lack of a Backup Designated Router.
Interface output cost(s) Interface output cost(s)
The cost of sending a data packet on the interface, expressed in The cost of sending a data packet on the interface, expressed in
the link state metric. This is advertised as the link cost for the link state metric. This is advertised as the link cost for
this interface in the router links advertisement. There may be this interface in the router-LSA. There may be a separate cost
a separate cost for each IP Type of Service. The cost of an for each IP Type of Service. The cost of an interface must be
interface must be greater than zero. greater than zero.
RxmtInterval RxmtInterval
The number of seconds between link state advertisement The number of seconds between LSA retransmissions, for
retransmissions, for adjacencies belonging to this interface. adjacencies belonging to this interface. Also used when
Also used when retransmitting Database Description and Link retransmitting Database Description and Link State Request
State Request Packets. Packets.
AuType AuType
The type of authentication used on the attached network/subnet. The type of authentication used on the attached network/subnet.
Authentication types are defined in Appendix D. All OSPF packet Authentication types are defined in Appendix D. All OSPF packet
exchanges are authenticated. Different authentication schemes exchanges are authenticated. Different authentication schemes
may be used on different networks/subnets. may be used on different networks/subnets.
Authentication key Authentication key
This configured data allows the authentication procedure to This configured data allows the authentication procedure to
generate and/or verify OSPF protocol packets. The generate and/or verify OSPF protocol packets. The
skipping to change at page 62, line 35 skipping to change at page 62, line 19
9.1. Interface states 9.1. Interface states
The various states that router interfaces may attain is The various states that router interfaces may attain is
documented in this section. The states are listed in order of documented in this section. The states are listed in order of
progressing functionality. For example, the inoperative state progressing functionality. For example, the inoperative state
is listed first, followed by a list of intermediate states is listed first, followed by a list of intermediate states
before the final, fully functional state is achieved. The before the final, fully functional state is achieved. The
specification makes use of this ordering by sometimes making specification makes use of this ordering by sometimes making
references such as "those interfaces in state greater than X". references such as "those interfaces in state greater than X".
Figure 11 shows the graph of interface state changes. The arcs Figure 11 shows the graph of interface state changes. The arcs
of the graph are labelled with the event causing the state
change. These events are documented in Section 9.2. The
interface state machine is described in more detail in Section
9.3.
Down
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 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
In this state, the router's interface to the network is
+----+ UnloopInd +--------+ +----+ UnloopInd +--------+
|Down|<--------------|Loopback| |Down|<--------------|Loopback|
+----+ +--------+ +----+ +--------+
| |
|InterfaceUp |InterfaceUp
+-------+ | +--------------+ +-------+ | +--------------+
|Waiting|<-+-------------->|Point-to-point| |Waiting|<-+-------------->|Point-to-point|
+-------+ +--------------+ +-------+ +--------------+
| |
WaitTimer|BackupSeen WaitTimer|BackupSeen
skipping to change at page 63, line 32 skipping to change at page 63, line 4
| |Change | |Change
| +--+ | +--+
+---->|DR| +---->|DR|
+--+ +--+
Figure 11: Interface State changes Figure 11: Interface State changes
In addition to the state transitions pictured, In addition to the state transitions pictured,
Event InterfaceDown always forces Down State, and Event InterfaceDown always forces Down State, and
Event LoopInd always forces Loopback State Event LoopInd always forces Loopback State
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
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 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
In this state, the router's interface to the network is
looped back. The interface may be looped back in hardware looped back. The interface may be looped back in hardware
or software. The interface will be unavailable for regular or software. The interface will be unavailable for regular
data traffic. However, it may still be desirable to gain data traffic. However, it may still be desirable to gain
information on the quality of this interface, either through information on the quality of this interface, either through
sending ICMP pings to the interface or through something sending ICMP pings to the interface or through something
like a bit error test. For this reason, IP packets may like a bit error test. For this reason, IP packets may
still be addressed to an interface in Loopback state. To still be addressed to an interface in Loopback state. To
facilitate this, such interfaces are advertised in router facilitate this, such interfaces are advertised in router-
links advertisements as single host routes, whose LSAs as single host routes, whose destination is the IP
destination is the IP interface address.[4] interface address.[4]
Waiting Waiting
In this state, the router is trying to determine the In this state, the router is trying to determine the
identity of the (Backup) Designated Router for the network. identity of the (Backup) Designated Router for the network.
To do this, the router monitors the Hello Packets it To do this, the router monitors the Hello Packets it
receives. The router is not allowed to elect a Backup receives. The router is not allowed to elect a Backup
Designated Router nor a Designated Router until it Designated Router nor a Designated Router until it
transitions out of Waiting state. This prevents unnecessary transitions out of Waiting state. This prevents unnecessary
changes of (Backup) Designated Router. changes of (Backup) Designated Router.
skipping to change at page 64, line 36 skipping to change at page 64, line 22
The router establishes adjacencies to all other routers The router establishes adjacencies to all other routers
attached to the network. The Backup Designated Router attached to the network. The Backup Designated Router
performs slightly different functions during the Flooding performs slightly different functions during the Flooding
Procedure, as compared to the Designated Router (see Section Procedure, as compared to the Designated Router (see Section
13.3). See Section 7.4 for more details on the functions 13.3). See Section 7.4 for more details on the functions
performed by the Backup Designated Router. performed by the Backup Designated Router.
DR In this state, this router itself is the Designated Router DR In this state, this router itself is the Designated Router
on the attached network. Adjacencies are established to all on the attached network. Adjacencies are established to all
other routers attached to the network. The router must also other routers attached to the network. The router must also
originate a network links advertisement for the network originate a network-LSA for the network node. The network-
node. The advertisement will contain links to all routers LSA will contain links to all routers (including the
(including the Designated Router itself) attached to the Designated Router itself) attached to the network. See
network. See Section 7.3 for more details on the functions Section 7.3 for more details on the functions performed by
performed by the Designated Router. the Designated Router.
9.2. Events causing interface state changes 9.2. Events causing interface state changes
State changes can be effected by a number of events. These State changes can be effected by a number of events. These
events are pictured as the labelled arcs in Figure 11. The events are pictured as the labelled arcs in Figure 11. The
label definitions are listed below. For a detailed explanation label definitions are listed below. For a detailed explanation
of the effect of these events on OSPF protocol operation, of the effect of these events on OSPF protocol operation,
consult Section 9.3. consult Section 9.3.
InterfaceUp InterfaceUp
skipping to change at page 66, line 39 skipping to change at page 66, line 27
A detailed description of the interface state changes follows. A detailed description of the interface state changes follows.
Each state change is invoked by an event (Section 9.2). This Each state change is invoked by an event (Section 9.2). This
event may produce different effects, depending on the current event may produce different effects, depending on the current
state of the interface. For this reason, the state machine state of the interface. For this reason, the state machine
below is organized by current interface state and received below is organized by current interface state and received
event. Each entry in the state machine describes the resulting event. Each entry in the state machine describes the resulting
new interface state and the required set of additional actions. new interface state and the required set of additional actions.
When an interface's state changes, it may be necessary to When an interface's state changes, it may be necessary to
originate a new router links advertisement. See Section 12.4 originate a new router-LSA. See Section 12.4 for more details.
for more details.
Some of the required actions below involve generating events for Some of the required actions below involve generating events for
the neighbor state machine. For example, when an interface the neighbor state machine. For example, when an interface
becomes inoperative, all neighbor connections associated with becomes inoperative, all neighbor connections associated with
the interface must be destroyed. For more information on the the interface must be destroyed. For more information on the
neighbor state machine, see Section 10.3. neighbor state machine, see Section 10.3.
State(s): Down State(s): Down
Event: InterfaceUp Event: InterfaceUp
New state: Depends upon action routine New state: Depends upon action routine
Action: Start the interval Hello Timer, enabling the Action: Start the interval Hello Timer, enabling the
periodic sending of Hello packets out the interface. periodic sending of Hello packets out the interface.
If the attached network is a physical point-to-point If the attached network is a physical point-to-point
network, Point-to-MultiPoint network or virtual network, Point-to-MultiPoint network or virtual
link, the interface state transitions to Point-to- link, the interface state transitions to Point-to-
Point. Else, if the router is not eligible to Point. Else, if the router is not eligible to
skipping to change at page 71, line 48 skipping to change at page 71, line 37
Packets sent out the interface (HelloInterval). The Hello Packets sent out the interface (HelloInterval). The Hello
Packet also indicates how often a neighbor must be heard from to Packet also indicates how often a neighbor must be heard from to
remain active (RouterDeadInterval). Both HelloInterval and remain active (RouterDeadInterval). Both HelloInterval and
RouterDeadInterval must be the same for all routers attached to RouterDeadInterval must be the same for all routers attached to
a common network. The Hello packet also contains the IP address a common network. The Hello packet also contains the IP address
mask of the attached network (Network Mask). On unnumbered mask of the attached network (Network Mask). On unnumbered
point-to-point networks and on virtual links this field should point-to-point networks and on virtual links this field should
be set to 0.0.0.0. be set to 0.0.0.0.
The Hello packet's Options field describes the router's optional The Hello packet's Options field describes the router's optional
OSPF capabilities. Two optional capabilities area defined in OSPF capabilities. Two optional capabilities are defined in
this specification (see Sections 4.5 and A.2). The T-bit of the this specification (see Sections 4.5 and A.2). The T-bit of the
Options field should be set if the router is capable of Options field should be set if the router is capable of
calculating separate routes for each IP TOS. The E-bit should calculating separate routes for each IP TOS. The E-bit should
be set if and only if the attached area is capable of processing be set if and only if the attached area is capable of processing
AS external advertisements (i.e., it is not a stub area). If AS-external-LSAs (i.e., it is not a stub area). If the E-bit is
the E-bit is set incorrectly the neighboring routers will refuse set incorrectly the neighboring routers will refuse to accept
to accept the Hello Packet (see Section 10.5). Unrecognized bits the Hello Packet (see Section 10.5). Unrecognized bits in the
in the Hello Packet's Options field should be set to zero. 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, the Hello packet contains the list of all routers on routers, the Hello packet contains the list of all routers on
the network from which Hello Packets have been seen recently. the network from which Hello Packets have been seen recently.
The Hello packet also contains the router's current choice for The Hello packet also contains the router's current choice for
Designated Router and Backup Designated Router. A value of Designated Router and Backup Designated Router. A value of
0.0.0.0 in these fields means that one has not yet been 0.0.0.0 in these fields means that one has not yet been
selected. selected.
On broadcast networks and physical point-to-point networks, On broadcast networks and physical point-to-point networks,
skipping to change at page 74, line 40 skipping to change at page 74, line 30
Neighbor Priority Neighbor Priority
The Router Priority of the neighboring router. Contained in the The Router Priority of the neighboring router. Contained in the
neighbor's Hello packets, this item is used when selecting the neighbor's Hello packets, this item is used when selecting the
Designated Router for the attached network. Designated Router for the attached network.
Neighbor IP address Neighbor IP address
The IP address of the neighboring router's interface to the The IP address of the neighboring router's interface to the
attached network. Used as the Destination IP address when attached network. Used as the Destination IP address when
protocol packets are sent as unicasts along this adjacency. protocol packets are sent as unicasts along this adjacency.
Also used in router links advertisements as the Link ID for the Also used in router-LSAs as the Link ID for the attached network
attached network if the neighboring router is selected to be if the neighboring router is selected to be Designated Router
Designated Router (see Section 12.4.1). The Neighbor IP address (see Section 12.4.1). The Neighbor IP address is learned when
is learned when Hello packets are received from the neighbor. Hello packets are received from the neighbor. For virtual
For virtual links, the Neighbor IP address is learned during the links, the Neighbor IP address is learned during the routing
routing table build process (see Section 15). table build process (see Section 15).
Neighbor Options Neighbor Options
The optional OSPF capabilities supported by the neighbor. The optional OSPF capabilities supported by the neighbor.
Learned during the Database Exchange process (see Section 10.6). Learned during the Database Exchange process (see Section 10.6).
The neighbor's optional OSPF capabilities are also listed in its The neighbor's optional OSPF capabilities are also listed in its
Hello packets. This enables received Hello Packets to be Hello packets. This enables received Hello Packets to be
rejected (i.e., neighbor relationships will not even start to rejected (i.e., neighbor relationships will not even start to
form) if there is a mismatch in certain crucial OSPF form) if there is a mismatch in certain crucial OSPF
capabilities (see Section 10.5). The optional OSPF capabilities capabilities (see Section 10.5). The optional OSPF capabilities
are documented in Section 4.5. are documented in Section 4.5.
skipping to change at page 75, line 21 skipping to change at page 75, line 11
neighbor itself, this is important in the local calculation of neighbor itself, this is important in the local calculation of
the Designated Router. Defined only on broadcast and NBMA the Designated Router. Defined only on broadcast and NBMA
networks. networks.
Neighbor's Backup Designated Router Neighbor's Backup Designated Router
The neighbor's idea of the Backup Designated Router. If this is The neighbor's idea of the Backup Designated Router. If this is
the neighbor itself, this is important in the local calculation the neighbor itself, this is important in the local calculation
of the Backup Designated Router. Defined only on broadcast and of the Backup Designated Router. Defined only on broadcast and
NBMA networks. NBMA networks.
The next set of variables are lists of link state advertisements. The next set of variables are lists of LSAs. These lists describe
These lists describe subsets of the area link-state database. This subsets of the area link-state database. This memo defines five
memo defines five distinct types of link state advertisements, all distinct types of LSAs, all of which may be present in an area
of which may be present in an area link-state database: router link-state database: router-LSAs, network-LSAs, and Type 3 and 4
links, network links, and Type 3 and 4 summary links (all stored in summary-LSAs (all stored in the area data structure), and AS-
the area data structure), and AS external links (stored in the external-LSAs (stored in the global data structure).
global data structure).
Link state retransmission list Link state retransmission list
The list of link state advertisements that have been flooded but The list of LSAs that have been flooded but not acknowledged on
not acknowledged on this adjacency. These will be retransmitted this adjacency. These will be retransmitted at intervals until
at intervals until they are acknowledged, or until the adjacency they are acknowledged, or until the adjacency is destroyed.
is destroyed.
Database summary list Database summary list
The complete list of link state advertisements that make up the The complete list of LSAs that make up the area link-state
area link-state database, at the moment the neighbor goes into database, at the moment the neighbor goes into Database Exchange
Database Exchange state. This list is sent to the neighbor in state. This list is sent to the neighbor in Database
Database Description packets. Description packets.
Link state request list Link state request list
The list of link state advertisements that need to be received The list of LSAs that need to be received from this neighbor in
from this neighbor in order to synchronize the two neighbors' order to synchronize the two neighbors' link-state databases.
link-state databases. This list is created as Database This list is created as Database Description packets are
Description packets are received, and is then sent to the received, and is then sent to the neighbor in Link State Request
neighbor in Link State Request packets. The list is depleted as packets. The list is depleted as appropriate Link State Update
appropriate Link State Update packets are received. packets are received.
10.1. Neighbor states 10.1. Neighbor states
The state of a neighbor (really, the state of a conversation The state of a neighbor (really, the state of a conversation
being held with a neighboring router) is documented in the being held with a neighboring router) is documented in the
following sections. The states are listed in order of following sections. The states are listed in order of
progressing functionality. For example, the inoperative state progressing functionality. For example, the inoperative state
is listed first, followed by a list of intermediate states is listed first, followed by a list of intermediate states
before the final, fully functional state is achieved. The before the final, fully functional state is achieved. The
specification makes use of this ordering by sometimes making specification makes use of this ordering by sometimes making
skipping to change at page 76, line 25 skipping to change at page 76, line 11
than X". Figures 12 and 13 show the graph of neighbor state than X". Figures 12 and 13 show the graph of neighbor state
changes. The arcs of the graphs are labelled with the event changes. The arcs of the graphs are labelled with the event
causing the state change. The neighbor events are documented in causing the state change. The neighbor events are documented in
Section 10.2. Section 10.2.
The graph in Figure 12 shows the state changes effected by the The graph in Figure 12 shows the state changes effected by the
Hello Protocol. The Hello Protocol is responsible for neighbor Hello Protocol. The Hello Protocol is responsible for neighbor
acquisition and maintenance, and for ensuring two way acquisition and maintenance, and for ensuring two way
communication between neighbors. communication between neighbors.
The graph in Figure 13 shows the forming of an adjacency. Not
every two neighboring routers become adjacent (see Section
10.4). The adjacency starts to form when the neighbor is in
state ExStart. After the two routers discover their
master/slave status, the state transitions to Exchange. At this
point the neighbor starts to be used in the flooding procedure,
and the two neighboring routers begin synchronizing their
databases. When this synchronization is finished, the neighbor
is in state Full and we say that the two routers are fully
adjacent. At this point the adjacency is listed in LSAs.
For a more detailed description of neighbor state changes,
together with the additional actions involved in each change,
+----+ +----+
|Down| |Down|
+----+ +----+
| | rt | | rt
| +-------+ | +-------+
Hello | +---->|Attempt| Hello | +---->|Attempt|
Received | +-------+ Received | +-------+
| | | |
+----+<-+ |HelloReceived +----+<-+ |HelloReceived
|Init|<---------------+ |Init|<---------------+
skipping to change at page 77, line 32 skipping to change at page 77, line 32
In addition to the state transitions pictured, In addition to the state transitions pictured,
Event SeqNumberMismatch forces ExStart state, Event SeqNumberMismatch forces ExStart state,
Event BadLSReq forces ExStart state, Event BadLSReq forces ExStart state,
Event 1-Way forces Init state, Event 1-Way forces Init state,
Event KillNbr always forces Down State, Event KillNbr always forces Down State,
Event InactivityTimer always forces Down State, Event InactivityTimer always forces Down State,
Event LLDown always forces Down State, Event LLDown always forces Down State,
Event AdjOK? leads to adjacency forming/breaking Event AdjOK? leads to adjacency forming/breaking
The graph in Figure 13 shows the forming of an adjacency. Not
every two neighboring routers become adjacent (see Section
10.4). The adjacency starts to form when the neighbor is in
state ExStart. After the two routers discover their
master/slave status, the state transitions to Exchange. At this
point the neighbor starts to be used in the flooding procedure,
and the two neighboring routers begin synchronizing their
databases. When this synchronization is finished, the neighbor
is in state Full and we say that the two routers are fully
adjacent. At this point the adjacency is listed in link state
advertisements.
For a more detailed description of neighbor state changes,
together with the additional actions involved in each change,
see Section 10.3. see Section 10.3.
Down Down
This is the initial state of a neighbor conversation. It This is the initial state of a neighbor conversation. It
indicates that there has been no recent information received indicates that there has been no recent information received
from the neighbor. On NBMA networks, Hello packets may from the neighbor. On NBMA networks, Hello packets may
still be sent to "Down" neighbors, although at a reduced still be sent to "Down" neighbors, although at a reduced
frequency (see Section 9.5.1). frequency (see Section 9.5.1).
Attempt Attempt
skipping to change at page 78, line 47 skipping to change at page 78, line 35
DD sequence number. Neighbor conversations in this state or DD sequence number. Neighbor conversations in this state or
greater are called adjacencies. greater are called adjacencies.
Exchange Exchange
In this state the router is describing its entire link state In this state the router is describing its entire link state
database by sending Database Description packets to the database by sending Database Description packets to the
neighbor. Each Database Description Packet has a DD neighbor. Each Database Description Packet has a DD
sequence number, and is explicitly acknowledged. Only one sequence number, and is explicitly acknowledged. Only one
Database Description Packet is allowed outstanding at any Database Description Packet is allowed outstanding at any
one time. In this state, Link State Request Packets may one time. In this state, Link State Request Packets may
also be sent asking for the neighbor's more recent also be sent asking for the neighbor's more recent LSAs.
advertisements. All adjacencies in Exchange state or All adjacencies in Exchange state or greater are used by the
greater are used by the flooding procedure. In fact, these flooding procedure. In fact, these adjacencies are fully
adjacencies are fully capable of transmitting and receiving capable of transmitting and receiving all types of OSPF
all types of OSPF routing protocol packets. routing protocol packets.
Loading Loading
In this state, Link State Request packets are sent to the In this state, Link State Request packets are sent to the
neighbor asking for the more recent advertisements that have neighbor asking for the more recent LSAs that have been
been discovered (but not yet received) in the Exchange discovered (but not yet received) in the Exchange state.
state.
Full Full
In this state, the neighboring routers are fully adjacent. In this state, the neighboring routers are fully adjacent.
These adjacencies will now appear in router links and These adjacencies will now appear in router-LSAs and
network links advertisements. network-LSAs.
10.2. Events causing neighbor state changes 10.2. Events causing neighbor state changes
State changes can be effected by a number of events. These State changes can be effected by a number of events. These
events are shown in the labels of the arcs in Figures 12 and 13. events are shown in the labels of the arcs in Figures 12 and 13.
The label definitions are as follows: The label definitions are as follows:
HelloReceived HelloReceived
An Hello packet has been received from the neighbor. An Hello packet has been received from the neighbor.
skipping to change at page 80, line 6 skipping to change at page 79, line 40
event, consult Section 10.8. event, consult Section 10.8.
ExchangeDone ExchangeDone
Both routers have successfully transmitted a full sequence Both routers have successfully transmitted a full sequence
of Database Description packets. Each router now knows what of Database Description packets. Each router now knows what
parts of its link state database are out of date. For more parts of its link state database are out of date. For more
information on the generation of this event, consult Section information on the generation of this event, consult Section
10.8. 10.8.
BadLSReq BadLSReq
A Link State Request has been received for a link state A Link State Request has been received for an LSA not
advertisement not contained in the database. This indicates contained in the database. This indicates an error in the
an error in the Database Exchange process. Database Exchange process.
Loading Done Loading Done
Link State Updates have been received for all out-of-date Link State Updates have been received for all out-of-date
portions of the database. This is indicated by the Link portions of the database. This is indicated by the Link
state request list becoming empty after the Database state request list becoming empty after the Database
Exchange process has completed. Exchange process has completed.
AdjOK? AdjOK?
A decision must be made as to whether an adjacency should be A decision must be made as to whether an adjacency should be
established/maintained with the neighbor. This event will established/maintained with the neighbor. This event will
skipping to change at page 81, line 23 skipping to change at page 81, line 11
state of the neighbor. For this reason, the state machine below state of the neighbor. For this reason, the state machine below
is organized by current neighbor state and received event. Each is organized by current neighbor state and received event. Each
entry in the state machine describes the resulting new neighbor entry in the state machine describes the resulting new neighbor
state and the required set of additional actions. state and the required set of additional actions.
When a neighbor's state changes, it may be necessary to rerun When a neighbor's state changes, it may be necessary to rerun
the Designated Router election algorithm. This is determined by the Designated Router election algorithm. This is determined by
whether the interface NeighborChange event is generated (see whether the interface NeighborChange event is generated (see
Section 9.2). Also, if the Interface is in DR state (the router Section 9.2). Also, if the Interface is in DR state (the router
is itself Designated Router), changes in neighbor state may is itself Designated Router), changes in neighbor state may
cause a new network links advertisement to be originated (see cause a new network-LSA to be originated (see Section 12.4).
Section 12.4).
When the neighbor state machine needs to invoke the interface When the neighbor state machine needs to invoke the interface
state machine, it should be done as a scheduled task (see state machine, it should be done as a scheduled task (see
Section 4.4). This simplifies things, by ensuring that neither Section 4.4). This simplifies things, by ensuring that neither
state machine will be executed recursively. state machine will be executed recursively.
State(s): Down State(s): Down
Event: Start Event: Start
skipping to change at page 83, line 16 skipping to change at page 82, line 49
State(s): ExStart State(s): ExStart
Event: NegotiationDone Event: NegotiationDone
New state: Exchange New state: Exchange
Action: The router must list the contents of its entire area Action: The router must list the contents of its entire area
link state database in the neighbor Database summary link state database in the neighbor Database summary
list. The area link state database consists of the list. The area link state database consists of the
router links, network links and summary links router-LSAs, network-LSAs and summary-LSAs contained
contained in the area structure, along with the AS in the area structure, along with the AS-external-
external links contained in the global structure. LSAs contained in the global structure. AS-
AS external link advertisements are omitted from a external-LSAs are omitted from a virtual neighbor's
virtual neighbor's Database summary list. AS Database summary list. AS-external-LSAs are omitted
external advertisements are omitted from the from the Database summary list if the area has been
Database summary list if the area has been configured as a stub (see Section 3.6). LSAs whose
configured as a stub (see Section 3.6). age is equal to MaxAge are instead added to the
Advertisements whose age is equal to MaxAge are neighbor's Link state retransmission list. A
instead added to the neighbor's Link state summary of the Database summary list will be sent to
retransmission list. A summary of the Database the neighbor in Database Description packets. Each
summary list will be sent to the neighbor in Database Description Packet has a DD sequence
Database Description packets. Each Database number, and is explicitly acknowledged. Only one
Description Packet has a DD sequence number, and is Database Description Packet is allowed outstanding
explicitly acknowledged. Only one Database at any one time. For more detail on the sending and
Description Packet is allowed outstanding at any one receiving of Database Description packets, see
time. For more detail on the sending and receiving Sections 10.8 and 10.6.
of Database Description packets, see Sections 10.8
and 10.6.
State(s): Exchange State(s): Exchange
Event: ExchangeDone Event: ExchangeDone
New state: Depends upon action routine. New state: Depends upon action routine.
Action: If the neighbor Link state request list is empty, Action: If the neighbor Link state request list is empty,
the new neighbor state is Full. No other action is the new neighbor state is Full. No other action is
required. This is an adjacency's final state. required. This is an adjacency's final state.
Otherwise, the new neighbor state is Loading. Start Otherwise, the new neighbor state is Loading. Start
(or continue) sending Link State Request packets to (or continue) sending Link State Request packets to
the neighbor (see Section 10.9). These are requests the neighbor (see Section 10.9). These are requests
for the neighbor's more recent advertisements (which for the neighbor's more recent LSAs (which were
were discovered but not yet received in the Exchange discovered but not yet received in the Exchange
state). These advertisements are listed in the Link state). These LSAs are listed in the Link state
state request list associated with the neighbor. request list associated with the neighbor.
State(s): Loading State(s): Loading
Event: Loading Done Event: Loading Done
New state: Full New state: Full
Action: No action required. This is an adjacency's final Action: No action required. This is an adjacency's final
state. state.
skipping to change at page 84, line 44 skipping to change at page 84, line 29
New state: Depends upon action routine. New state: Depends upon action routine.
Action: Determine whether the neighboring router should Action: Determine whether the neighboring router should
still be adjacent. If yes, there is no state change still be adjacent. If yes, there is no state change
and no further action is necessary. and no further action is necessary.
Otherwise, the (possibly partially formed) adjacency Otherwise, the (possibly partially formed) adjacency
must be destroyed. The neighbor state transitions must be destroyed. The neighbor state transitions
to 2-Way. The Link state retransmission list, to 2-Way. The Link state retransmission list,
Database summary list and Link state request list Database summary list and Link state request list
are cleared of link state advertisements. are cleared of LSAs.
State(s): Exchange or greater State(s): Exchange or greater
Event: SeqNumberMismatch Event: SeqNumberMismatch
New state: ExStart New state: ExStart
Action: The (possibly partially formed) adjacency is torn Action: The (possibly partially formed) adjacency is torn
down, and then an attempt is made at down, and then an attempt is made at
reestablishment. The neighbor state first reestablishment. The neighbor state first
transitions to ExStart. The Link state transitions to ExStart. The Link state
retransmission list, Database summary list and Link retransmission list, Database summary list and Link
state request list are cleared of link state state request list are cleared of LSAs. Then the
advertisements. Then the router increments the DD router increments the DD sequence number for this
sequence number for this neighbor, declares itself neighbor, declares itself master (sets the
master (sets the master/slave bit to master), and master/slave bit to master), and starts sending
starts sending Database Description Packets, with Database Description Packets, with the initialize
the initialize (I), more (M) and master (MS) bits (I), more (M) and master (MS) bits set. This
set. This Database Description Packet should be Database Description Packet should be otherwise
otherwise empty (see Section 10.8). empty (see Section 10.8).
State(s): Exchange or greater State(s): Exchange or greater
Event: BadLSReq Event: BadLSReq
New state: ExStart New state: ExStart
Action: The action for event BadLSReq is exactly the same as Action: The action for event BadLSReq is exactly the same as
for the neighbor event SeqNumberMismatch. The for the neighbor event SeqNumberMismatch. The
(possibly partially formed) adjacency is torn down, (possibly partially formed) adjacency is torn down,
skipping to change at page 85, line 43 skipping to change at page 85, line 26
entry that is invoked when event SeqNumberMismatch entry that is invoked when event SeqNumberMismatch
is generated in state Exchange or greater. is generated in state Exchange or greater.
State(s): Any state State(s): Any state
Event: KillNbr Event: KillNbr
New state: Down New state: Down
Action: The Link state retransmission list, Database summary Action: The Link state retransmission list, Database summary
list and Link state request list are cleared of link list and Link state request list are cleared of
state advertisements. Also, the Inactivity Timer is LSAs. Also, the Inactivity Timer is disabled.
disabled.
State(s): Any state State(s): Any state
Event: LLDown Event: LLDown
New state: Down New state: Down
Action: The Link state retransmission list, Database summary Action: The Link state retransmission list, Database summary
list and Link state request list are cleared of link list and Link state request list are cleared of
state advertisements. Also, the Inactivity Timer is LSAs. Also, the Inactivity Timer is disabled.
disabled.
State(s): Any state State(s): Any state
Event: InactivityTimer Event: InactivityTimer
New state: Down New state: Down
Action: The Link state retransmission list, Database summary Action: The Link state retransmission list, Database summary
list and Link state request list are cleared of link list and Link state request list are cleared of
state advertisements. LSAs.
State(s): 2-Way or greater State(s): 2-Way or greater
Event: 1-WayReceived Event: 1-WayReceived
New state: Init New state: Init
Action: The Link state retransmission list, Database summary Action: The Link state retransmission list, Database summary
list and Link state request list are cleared of link list and Link state request list are cleared of
state advertisements. LSAs.
State(s): 2-Way or greater State(s): 2-Way or greater
Event: 2-WayReceived Event: 2-WayReceived
New state: No state change. New state: No state change.
Action: No action required. Action: No action required.
State(s): Init State(s): Init
skipping to change at page 88, line 14 skipping to change at page 87, line 38
interface. Any mismatch causes processing to stop and the interface. Any mismatch causes processing to stop and the
packet to be dropped. In other words, the above fields are packet to be dropped. In other words, the above fields are
really describing the attached network's configuration. However, really describing the attached network's configuration. However,
there is one exception to the above rule: on point-to-point there is one exception to the above rule: on point-to-point
networks and on virtual links, the Network Mask in the received networks and on virtual links, the Network Mask in the received
Hello Packet should be ignored. Hello Packet should be ignored.
The receiving interface attaches to a single OSPF area (this The receiving interface attaches to a single OSPF area (this
could be the backbone). The setting of the E-bit found in the could be the backbone). The setting of the E-bit found in the
Hello Packet's Options field must match this area's Hello Packet's Options field must match this area's
ExternalRoutingCapability. If AS external advertisements are ExternalRoutingCapability. If AS-external-LSAs are not flooded
not flooded into/throughout the area (i.e, the area is a "stub") into/throughout the area (i.e, the area is a "stub") the E-bit
the E-bit must be clear in received Hello Packets, otherwise the must be clear in received Hello Packets, otherwise the E-bit
E-bit must be set. A mismatch causes processing to stop and the must be set. A mismatch causes processing to stop and the
packet to be dropped. The setting of the rest of the bits in packet to be dropped. The setting of the rest of the bits in
the Hello Packet's Options field should be ignored. the Hello Packet's Options field should be ignored.
At this point, an attempt is made to match the source of the At this point, an attempt is made to match the source of the
Hello Packet to one of the receiving interface's neighbors. If Hello Packet to one of the receiving interface's neighbors. If
the receiving interface connects to a broadcast, Point-to- the receiving interface connects to a broadcast, Point-to-
MultiPoint or NBMA network the source is identified by the IP MultiPoint or NBMA network the source is identified by the IP
source address found in the Hello's IP header. If the receiving source address found in the Hello's IP header. If the receiving
interface connects to a point-to-point link or a virtual link, interface connects to a point-to-point link or a virtual link,
the source is identified by the Router ID found in the Hello's the source is identified by the Router ID found in the Hello's
skipping to change at page 92, line 12 skipping to change at page 91, line 35
(stored in the neighbor structure's Neighbor Options field). (stored in the neighbor structure's Neighbor Options field).
Any other packets received, including the reception of a Any other packets received, including the reception of a
packet with the Initialize(I) bit set, should generate the packet with the Initialize(I) bit set, should generate the
neighbor event SeqNumberMismatch.[8] Duplicates should be neighbor event SeqNumberMismatch.[8] Duplicates should be
discarded by the master. The slave must respond to discarded by the master. The slave must respond to
duplicates by repeating the last Database Description packet duplicates by repeating the last Database Description packet
that it had sent. that it had sent.
When the router accepts a received Database Description Packet When the router accepts a received Database Description Packet
as the next in sequence the packet contents are processed as as the next in sequence the packet contents are processed as
follows. For each link state advertisement listed, the follows. For each LSA listed, the LSA's LS type is checked for
advertisement's LS type is checked for validity. If the LS type validity. If the LS type is unknown (e.g., not one of the LS
is unknown (e.g., not one of the LS types 1-5 defined by this types 1-5 defined by this specification), or if this is an AS-
specification), or if this is a AS external advertisement (LS external-LSA (LS type = 5) and the neighbor is associated with a
type = 5) and the neighbor is associated with a stub area, stub area, generate the neighbor event SeqNumberMismatch and
generate the neighbor event SeqNumberMismatch and stop stop processing the packet. Otherwise, the router looks up the
processing the packet. Otherwise, the router looks up the LSA in its database to see whether it also has an instance of
advertisement in its database to see whether it also has an the LSA. If it does not, or if the database copy is less recent
instance of the link state advertisement. If it does not, or if (see Section 13.1), the LSA is put on the Link state request
the database copy is less recent (see Section 13.1), the link list so that it can be requested (immediately or at some later
state advertisement is put on the Link state request list so time) in Link State Request Packets.
that it can be requested (immediately or at some later time) in
Link State Request Packets.
When the router accepts a received Database Description Packet When the router accepts a received Database Description Packet
as the next in sequence, it also performs the following actions, as the next in sequence, it also performs the following actions,
depending on whether it is master or slave: depending on whether it is master or slave:
Master Master
Increments the DD sequence number. If the router has Increments the DD sequence number. If the router has
already sent its entire sequence of Database Description already sent its entire sequence of Database Description
Packets, and the just accepted packet has the more bit (M) Packets, and the just accepted packet has the more bit (M)
set to 0, the neighbor event ExchangeDone is generated. set to 0, the neighbor event ExchangeDone is generated.
skipping to change at page 93, line 9 skipping to change at page 92, line 26
Database Description Packet in reply. If the received Database Description Packet in reply. If the received
packet has the more bit (M) set to 0, and the packet to be packet has the more bit (M) set to 0, and the packet to be
sent by the slave will also have the M-bit set to 0, the sent by the slave will also have the M-bit set to 0, the
neighbor event ExchangeDone is generated. Note that the neighbor event ExchangeDone is generated. Note that the
slave always generates this event before the master. slave always generates this event before the master.
10.7. Receiving Link State Request Packets 10.7. Receiving Link State Request Packets
This section explains the detailed processing of received Link This section explains the detailed processing of received Link
State Request packets. Received Link State Request Packets State Request packets. Received Link State Request Packets
specify a list of link state advertisements that the neighbor specify a list of LSAs that the neighbor wishes to receive.
wishes to receive. Link State Request Packets should be Link State Request Packets should be accepted when the neighbor
accepted when the neighbor is in states Exchange, Loading, or is in states Exchange, Loading, or Full. In all other states
Full. In all other states Link State Request Packets should be Link State Request Packets should be ignored.
ignored.
Each link state advertisement specified in the Link State Each LSA specified in the Link State Request packet should be
Request packet should be located in the router's database, and located in the router's database, and copied into Link State
copied into Link State Update packets for transmission to the Update packets for transmission to the neighbor. These LSAs
neighbor. These link state advertisements should NOT be placed should NOT be placed on the Link state retransmission list for
on the Link state retransmission list for the neighbor. If a the neighbor. If an LSA cannot be found in the database,
link state advertisement cannot be found in the database,
something has gone wrong with the Database Exchange process, and something has gone wrong with the Database Exchange process, and
neighbor event BadLSReq should be generated. neighbor event BadLSReq should be generated.
10.8. Sending Database Description Packets 10.8. Sending Database Description Packets
This section describes how Database Description Packets are sent This section describes how Database Description Packets are sent
to a neighbor. The router's optional OSPF capabilities (see to a neighbor. The router's optional OSPF capabilities (see
Section 4.5) are transmitted to the neighbor in the Options Section 4.5) are transmitted to the neighbor in the Options
field of the Database Description packet. The router should field of the Database Description packet. The router should
maintain the same set of optional capabilities throughout the maintain the same set of optional capabilities throughout the
skipping to change at page 93, line 48 skipping to change at page 93, line 16
area. The rest of the Options field should be set to zero. area. The rest of the Options field should be set to zero.
The sending of Database Description packets depends on the The sending of Database Description packets depends on the
neighbor's state. In state ExStart the router sends empty neighbor's state. In state ExStart the router sends empty
Database Description packets, with the initialize (I), more (M) Database Description packets, with the initialize (I), more (M)
and master (MS) bits set. These packets are retransmitted every and master (MS) bits set. These packets are retransmitted every
RxmtInterval seconds. RxmtInterval seconds.
In state Exchange the Database Description Packets actually In state Exchange the Database Description Packets actually
contain summaries of the link state information contained in the contain summaries of the link state information contained in the
router's database. Each link state advertisement in the area's router's database. Each LSA in the area's link-state database
link-state database (at the time the neighbor transitions into (at the time the neighbor transitions into Exchange state) is
Exchange state) is listed in the neighbor Database summary list. listed in the neighbor Database summary list. When a new
When a new Database Description Packet is to be sent, the Database Description Packet is to be sent, the packet's DD
packet's DD sequence number is incremented, and the (new) top of sequence number is incremented, and the (new) top of the
the Database summary list is described by the packet. Items are Database summary list is described by the packet. Items are
removed from the Database summary list when the previous packet removed from the Database summary list when the previous packet
is acknowledged. is acknowledged.
In state Exchange, the determination of when to send a Database In state Exchange, the determination of when to send a Database
Description packet depends on whether the router is master or Description packet depends on whether the router is master or
slave: slave:
Master Master
Database Description packets are sent when either a) the Database Description packets are sent when either a) the
slave acknowledges the previous Database Description packet slave acknowledges the previous Database Description packet
skipping to change at page 94, line 38 skipping to change at page 94, line 8
Database Description packet in response to duplicate Database Database Description packet in response to duplicate Database
Description packets received from the master. For this reason Description packets received from the master. For this reason
the slave must wait RouterDeadInterval seconds before freeing the slave must wait RouterDeadInterval seconds before freeing
the last Database Description packet. Reception of a Database the last Database Description packet. Reception of a Database
Description packet from the master after this interval will Description packet from the master after this interval will
generate a SeqNumberMismatch neighbor event. generate a SeqNumberMismatch neighbor event.
10.9. Sending Link State Request Packets 10.9. Sending Link State Request Packets
In neighbor states Exchange or Loading, the Link state request In neighbor states Exchange or Loading, the Link state request
list contains a list of those link state advertisements that list contains a list of those LSAs that need to be obtained from
need to be obtained from the neighbor. To request these the neighbor. To request these LSAs, a router sends the
advertisements, a router sends the neighbor the beginning of the neighbor the beginning of the Link state request list, packaged
Link state request list, packaged in a Link State Request in a Link State Request packet.
packet.
When the neighbor responds to these requests with the proper When the neighbor responds to these requests with the proper
Link State Update packet(s), the Link state request list is Link State Update packet(s), the Link state request list is
truncated and a new Link State Request packet is sent. This truncated and a new Link State Request packet is sent. This
process continues until the Link state request list becomes process continues until the Link state request list becomes
empty. Unsatisfied Link State Request packets are retransmitted empty. Unsatisfied Link State Request packets are retransmitted
at intervals of RxmtInterval. There should be at most one Link at intervals of RxmtInterval. There should be at most one Link
State Request packet outstanding at any one time. State Request packet outstanding at any one time.
When the Link state request list becomes empty, and the neighbor When the Link state request list becomes empty, and the neighbor
skipping to change at page 95, line 38 skipping to change at page 95, line 4
that it has heard Hello Packets from RT1. This in turn causes that it has heard Hello Packets from RT1. This in turn causes
RT1 to go to state ExStart, as it starts to bring up the RT1 to go to state ExStart, as it starts to bring up the
adjacency. adjacency.
RT1 begins by asserting itself as the master. When it sees that RT1 begins by asserting itself as the master. When it sees that
RT2 is indeed the master (because of RT2's higher Router ID), RT2 is indeed the master (because of RT2's higher Router ID),
RT1 transitions to slave state and adopts its neighbor's DD RT1 transitions to slave state and adopts its neighbor's DD
sequence number. Database Description packets are then sequence number. Database Description packets are then
exchanged, with polls coming from the master (RT2) and responses exchanged, with polls coming from the master (RT2) and responses
from the slave (RT1). This sequence of Database Description from the slave (RT1). This sequence of Database Description
Packets ends when both the poll and associated response has the
M-bit off.
In this example, it is assumed that RT2 has a completely up to
date database. In that case, RT2 goes immediately into Full
state. RT1 will go into Full state after updating the necessary
parts of its database. This is done by sending Link State
Request Packets, and receiving Link State Update Packets in
response. Note that, while RT1 has waited until a complete set
of Database Description Packets has been received (from RT2)
before sending any Link State Request Packets, this need not be
the case. RT1 could have interleaved the sending of Link State
Request Packets with the reception of Database Description
+---+ +---+ +---+ +---+
|RT1| |RT2| |RT1| |RT2|
+---+ +---+ +---+ +---+
Down Down Down Down
Hello(DR=0,seen=0) Hello(DR=0,seen=0)
------------------------------> ------------------------------>
Hello (DR=RT2,seen=RT1,...) Init Hello (DR=RT2,seen=RT1,...) Init
<------------------------------ <------------------------------
ExStart D-D (Seq=x,I,M,Master) ExStart D-D (Seq=x,I,M,Master)
skipping to change at page 97, line 4 skipping to change at page 96, line 4
------------------------------> ------------------------------>
LS Update LS Update
<------------------------------ <------------------------------
LS Request LS Request
------------------------------> ------------------------------>
LS Update LS Update
<------------------------------ <------------------------------
Full Full
Figure 14: An adjacency bring-up example Figure 14: An adjacency bring-up example
Packets ends when both the poll and associated response has the
M-bit off.
In this example, it is assumed that RT2 has a completely up to
date database. In that case, RT2 goes immediately into Full
state. RT1 will go into Full state after updating the necessary
parts of its database. This is done by sending Link State
Request Packets, and receiving Link State Update Packets in
response. Note that, while RT1 has waited until a complete set
of Database Description Packets has been received (from RT2)
before sending any Link State Request Packets, this need not be
the case. RT1 could have interleaved the sending of Link State
Request Packets with the reception of Database Description
Packets. Packets.
11. The Routing Table Structure 11. The Routing Table Structure
The routing table data structure contains all the information The routing table data structure contains all the information
necessary to forward an IP data packet toward its destination. Each necessary to forward an IP data packet toward its destination. Each
routing table entry describes the collection of best paths to a routing table entry describes the collection of best paths to a
particular destination. When forwarding an IP data packet, the particular destination. When forwarding an IP data packet, the
routing table entry providing the best match for the packet's IP routing table entry providing the best match for the packet's IP
destination is located. The matching routing table entry then destination is located. The matching routing table entry then
skipping to change at page 97, line 44 skipping to change at page 97, line 13
routing table build process. routing table build process.
Network Network
A range of IP addresses, to which IP data traffic may be A range of IP addresses, to which IP data traffic may be
forwarded. This includes IP networks (class A, B, or C), IP forwarded. This includes IP networks (class A, B, or C), IP
subnets, IP supernets and single IP hosts. The default subnets, IP supernets and single IP hosts. The default
route also falls in this category. route also falls in this category.
Area border router Area border router
Routers that are connected to multiple OSPF areas. Such Routers that are connected to multiple OSPF areas. Such
routers originate summary link advertisements. These routers originate summary-LSAs. These routing table entries
routing table entries are used when calculating the inter- are used when calculating the inter-area routes (see Section
area routes (see Section 16.2). These routing table entries 16.2). These routing table entries may also be associated
may also be associated with configured virtual links. with configured virtual links.
AS boundary router AS boundary router
Routers that originate AS external link advertisements. Routers that originate AS-external-LSAs. These routing
These routing table entries are used when calculating the AS table entries are used when calculating the AS external
external routes (see Section 16.4). routes (see Section 16.4).
Destination ID Destination ID
The destination's identifier or name. This depends on the The destination's identifier or name. This depends on the
Destination Type. For networks, the identifier is their Destination Type. For networks, the identifier is their
associated IP address. For all other types, the identifier is associated IP address. For all other types, the identifier is
the OSPF Router ID.[9] the OSPF Router ID.[9]
Address Mask Address Mask
Only defined for networks. The network's IP address together Only defined for networks. The network's IP address together
with its address mask defines a range of IP addresses. For IP with its address mask defines a range of IP addresses. For IP
subnets, the address mask is referred to as the subnet mask. subnets, the address mask is referred to as the subnet mask.
For host routes, the mask is "all ones" (0xffffffff). For host routes, the mask is "all ones" (0xffffffff).
Optional Capabilities Optional Capabilities
When the destination is a router (either an area border router When the destination is a router (either an area border router
or an AS boundary router) this field indicates the optional OSPF or an AS boundary router) this field indicates the optional OSPF
capabilities supported by the destination router. The two capabilities supported by the destination router. The two
optional capabilities currently defined by this specification optional capabilities currently defined by this specification
are the ability to route based on IP TOS and the ability to are the ability to route based on IP TOS and the ability to
process AS external link advertisements. For a further process AS-external-LSAs. For a further discussion of OSPF's
discussion of OSPF's optional capabilities, see Section 4.5. optional capabilities, see Section 4.5.
The set of paths to use for a destination may vary based on IP Type The set of paths to use for a destination may vary based on IP Type
of Service and the OSPF area to which the paths belong. This means of Service and the OSPF area to which the paths belong. This means
that there may be multiple routing table entries for the same that there may be multiple routing table entries for the same
destination, depending on the values of the next two fields. destination, depending on the values of the next two fields.
Type of Service Type of Service
There can be a separate set of routes for each IP Type of There can be a separate set of routes for each IP Type of
Service. The encoding of TOS in OSPF link state advertisements Service. The encoding of TOS in OSPF LSAs is described in
is described in Section 12.3. Section 12.3.
Area Area
This field indicates the area whose link state information has This field indicates the area whose link state information has
led to the routing table entry's collection of paths. This is led to the routing table entry's collection of paths. This is
called the entry's associated area. For sets of AS external called the entry's associated area. For sets of AS external
paths, this field is not defined. For destinations of type paths, this field is not defined. For destinations of type
"area border router", there may be separate sets of paths (and "area border router", there may be separate sets of paths (and
therefore separate routing table entries) associated with each therefore separate routing table entries) associated with each
of several areas. This will happen when two area border routers of several areas. This will happen when two area border routers
share multiple areas in common. For all other destination share multiple areas in common. For all other destination
skipping to change at page 99, line 18 skipping to change at page 98, line 31
as a whole. In other words, each one of the paths contained in a as a whole. In other words, each one of the paths contained in a
routing table entry is of the same path-type and cost (see below). routing table entry is of the same path-type and cost (see below).
Path-type Path-type
There are four possible types of paths used to route traffic to There are four possible types of paths used to route traffic to
the destination, listed here in order of preference: intra-area, the destination, listed here in order of preference: intra-area,
inter-area, type 1 external or type 2 external. Intra-area inter-area, type 1 external or type 2 external. Intra-area
paths indicate destinations belonging to one of the router's paths indicate destinations belonging to one of the router's
attached areas. Inter-area paths are paths to destinations in attached areas. Inter-area paths are paths to destinations in
other OSPF areas. These are discovered through the examination other OSPF areas. These are discovered through the examination
of received summary link advertisements. AS external paths are of received summary-LSAs. AS external paths are paths to
paths to destinations external to the AS. These are detected destinations external to the AS. These are detected through the
through the examination of received AS external link examination of received AS-external-LSAs.
advertisements.
Cost Cost
The link state cost of the path to the destination. For all The link state cost of the path to the destination. For all
paths except type 2 external paths this describes the entire paths except type 2 external paths this describes the entire
path's cost. For Type 2 external paths, this field describes path's cost. For Type 2 external paths, this field describes
the cost of the portion of the path internal to the AS. This the cost of the portion of the path internal to the AS. This
cost is calculated as the sum of the costs of the path's cost is calculated as the sum of the costs of the path's
constituent links. constituent links.
Type 2 cost Type 2 cost
Only valid for type 2 external paths. For these paths, this Only valid for type 2 external paths. For these paths, this
field indicates the cost of the path's external portion. This field indicates the cost of the path's external portion. This
cost has been advertised by an AS boundary router, and is the cost has been advertised by an AS boundary router, and is the
most significant part of the total path cost. For example, a most significant part of the total path cost. For example, a
type 2 external path with type 2 cost of 5 is always preferred type 2 external path with type 2 cost of 5 is always preferred
over a path with type 2 cost of 10, regardless of the cost of over a path with type 2 cost of 10, regardless of the cost of
the two paths' internal components. the two paths' internal components.
Link State Origin Link State Origin
Valid only for intra-area paths, this field indicates the link Valid only for intra-area paths, this field indicates the LSA
state advertisement (router links or network links) that (router-LSA or network-LSA) that directly references the
directly references the destination. For example, if the destination. For example, if the destination is a transit
destination is a transit network, this is the transit network's network, this is the transit network's network-LSA. If the
network links advertisement. If the destination is a stub destination is a stub network, this is the router-LSA for the
network, this is the router links advertisement for the attached attached router. The LSA is discovered during the shortest-path
router. The advertisement is discovered during the shortest- tree calculation (see Section 16.1). Multiple LSAs may
path tree calculation (see Section 16.1). Multiple reference the destination, however a tie-breaking scheme always
advertisements may reference the destination, however a tie- reduces the choice to a single LSA. The Link State Origin field
breaking scheme always reduces the choice to a single is not used by the OSPF protocol, but it is used by the routing
advertisement. The Link State Origin field is not used by the table calculation in OSPF's Multicast routing extensions
OSPF protocol, but it is used by the routing table calculation (MOSPF).
in OSPF's Multicast routing extensions (MOSPF).
When multiple paths of equal path-type and cost exist to a When multiple paths of equal path-type and cost exist to a
destination (called elsewhere "equal-cost" paths), they are stored destination (called elsewhere "equal-cost" paths), they are stored
in a single routing table entry. Each one of the "equal-cost" paths in a single routing table entry. Each one of the "equal-cost" paths
is distinguished by the following fields: is distinguished by the following fields:
Next hop Next hop
The outgoing router interface to use when forwarding traffic to The outgoing router interface to use when forwarding traffic to
the destination. On broadcast, Point-to-MultiPoint and NBMA the destination. On broadcast, Point-to-MultiPoint and NBMA
networks, the next hop also includes the IP address of the next networks, the next hop also includes the IP address of the next
router (if any) in the path towards the destination. This next router (if any) in the path towards the destination. This next
router will always be one of the adjacent neighbors. router will always be one of the adjacent neighbors.
Advertising router Advertising router
Valid only for inter-area and AS external paths. This field Valid only for inter-area and AS external paths. This field
indicates the Router ID of the router advertising the summary indicates the Router ID of the router advertising the summary-
link or AS external link that led to this path. LSA or AS-external-LSA that led to this path.
11.1. Routing table lookup 11.1. Routing table lookup
When an IP data packet is received, an OSPF router finds the When an IP data packet is received, an OSPF router finds the
routing table entry that best matches the packet's destination. routing table entry that best matches the packet's destination.
This routing table entry then provides the outgoing interface This routing table entry then provides the outgoing interface
and next hop router to use in forwarding the packet. This and next hop router to use in forwarding the packet. This
section describes the process of finding the best matching section describes the process of finding the best matching
routing table entry. The process consists of a number of steps, routing table entry. The process consists of a number of steps,
wherein the collection of routing table entries is progressively wherein the collection of routing table entries is progressively
pruned. In the end, the single routing table entry remaining is pruned. In the end, the single routing table entry remaining is
called the "best match". called the "best match".
Before the lookup begins, "discard" routing table entries should Before the lookup begins, "discard" routing table entries should
be inserted into the routing table for each of the router's be inserted into the routing table for each of the router's
active area address ranges (see Section 3.5). (Remember that an active area address ranges (see Section 3.5). (An area range is
area range is considered "active" if the range contains one or considered "active" if the range contains one or more networks
more networks reachable by intra-area paths.) The destination of reachable by intra-area paths.) The destination of a "discard"
a "discard" entry is the set of addresses described by its entry is the set of addresses described by its associated active
associated active area address range, and the path type of each area address range, and the path type of each "discard" entry is
"discard" entry is set to "inter-area".[10] set to "inter-area".[10]
Note that the steps described below may fail to produce a best Note that the steps described below may fail to produce a best
match routing table entry (i.e., all existing routing table match routing table entry (i.e., all existing routing table
entries are pruned for some reason or another), or the best entries are pruned for some reason or another), or the best
match routing table entry may be one of the above "discard" match routing table entry may be one of the above "discard"
routing table entries. In these cases, the packet's IP routing table entries. In these cases, the packet's IP
destination is considered unreachable. Instead of being destination is considered unreachable. Instead of being
forwarded, the packet should be discarded and an ICMP forwarded, the packet should be discarded and an ICMP
destination unreachable message should be returned to the destination unreachable message should be returned to the
packet's source. packet's source.
skipping to change at page 102, line 17 skipping to change at page 101, line 28
"ASBR". "ASBR".
There are no instances of multiple equal-cost shortest paths in There are no instances of multiple equal-cost shortest paths in
this example. Also, since there are no areas, there are no this example. Also, since there are no areas, there are no
inter-area paths. inter-area paths.
Routers RT5 and RT7 are AS boundary routers. Intra-area routes Routers RT5 and RT7 are AS boundary routers. Intra-area routes
have been calculated to Routers RT5 and RT7. This allows have been calculated to Routers RT5 and RT7. This allows
external routes to be calculated to the destinations advertised external routes to be calculated to the destinations advertised
by RT5 and RT7 (i.e., Networks N12, N13, N14 and N15). It is by RT5 and RT7 (i.e., Networks N12, N13, N14 and N15). It is
assumed all AS external advertisements originated by RT5 and RT7 assumed all AS-external-LSAs originated by RT5 and RT7 are
are advertising type 1 external metrics. This results in type 1 advertising type 1 external metrics. This results in type 1
external paths being calculated to destinations N12-N15. external paths being calculated to destinations N12-N15.
11.3. Sample routing table, with areas 11.3. Sample routing table, with areas
Consider the previous example, this time split into OSPF areas. Consider the previous example, this time split into OSPF areas.
An OSPF area configuration is pictured in Figure 6. Router An OSPF area configuration is pictured in Figure 6. Router
RT4's routing table will be described for this area RT4's routing table will be described for this area
configuration. Router RT4 has a connection to Area 1 and a configuration. Router RT4 has a connection to Area 1 and a
backbone connection. This causes Router RT4 to view the AS as backbone connection. This causes Router RT4 to view the AS as
the concatenation of the two graphs shown in Figures 7 and 8. the concatenation of the two graphs shown in Figures 7 and 8.
The resulting routing table is displayed in Table 13. The resulting routing table is displayed in Table 13.
Again, Routers RT5 and RT7 are AS boundary routers. Routers Again, Routers RT5 and RT7 are AS boundary routers. Routers
RT3, RT4, RT7, RT10 and RT11 are area border routers. Note that RT3, RT4, RT7, RT10 and RT11 are area border routers. Note that
there are two routing table entries (in this case having there are two routing table entries (in this case having
identical paths) for Router RT7, in its dual capacities as an identical paths) for Router RT7, in its dual capacities as an
area border router and an AS boundary router. Note also that area border router and an AS boundary router. Note also that
there are two routing entries for the area border router RT3, there are two routing entries for the area border router RT3,
since it has two areas in common with RT4 (Area 1 and the since it has two areas in common with RT4 (Area 1 and the
backbone).
Backbone paths have been calculated to all area border routers
(BR). These are used when determining the inter-area routes.
Note that all of the inter-area routes are associated with the
backbone; this is always the case when the calculating router is
itself an area border router. Routing information is condensed
at area boundaries. In this example, we assume that Area 3 has
been defined so that networks N9-N11 and the host route to H1
are all condensed to a single route when advertised into the
backbone (by Router RT11). Note that the cost of this route is
the minimum of the set of costs to its individual components.
Type Dest Area Path Type Cost Next Adv. Type Dest Area Path Type Cost Next Adv.
Hop(s) Router(s) Hop(s) Router(s)
____________________________________________________________ ____________________________________________________________
N N1 0 intra-area 10 RT3 * N N1 0 intra-area 10 RT3 *
N N2 0 intra-area 10 RT3 * N N2 0 intra-area 10 RT3 *
N N3 0 intra-area 7 RT3 * N N3 0 intra-area 7 RT3 *
N N4 0 intra-area 8 RT3 * N N4 0 intra-area 8 RT3 *
N Ib 0 intra-area 7 * * N Ib 0 intra-area 7 * *
N Ia 0 intra-area 12 RT10 * N Ia 0 intra-area 12 RT10 *
N N6 0 intra-area 8 RT10 * N N6 0 intra-area 8 RT10 *
skipping to change at page 103, line 32 skipping to change at page 102, line 31
ASBR RT7 0 intra-area 8 RT10 * ASBR RT7 0 intra-area 8 RT10 *
____________________________________________________________ ____________________________________________________________
N N12 * type 1 ext. 10 RT10 RT7 N N12 * type 1 ext. 10 RT10 RT7
N N13 * type 1 ext. 14 RT5 RT5 N N13 * type 1 ext. 14 RT5 RT5
N N14 * type 1 ext. 14 RT5 RT5 N N14 * type 1 ext. 14 RT5 RT5
N N15 * type 1 ext. 17 RT10 RT7 N N15 * type 1 ext. 17 RT10 RT7
Table 12: The routing table for Router RT6 Table 12: The routing table for Router RT6
(no configured areas). (no configured areas).
backbone).
Backbone paths have been calculated to all area border routers
(BR). These are used when determining the inter-area routes.
Note that all of the inter-area routes are associated with the
backbone; this is always the case when the calculating router is
itself an area border router. Routing information is condensed
at area boundaries. In this example, we assume that Area 3 has
been defined so that networks N9-N11 and the host route to H1
are all condensed to a single route when advertised into the
backbone (by Router RT11). Note that the cost of this route is
the minimum of the set of costs to its individual components.
There is a virtual link configured between Routers RT10 and There is a virtual link configured between Routers RT10 and
RT11. Without this configured virtual link, RT11 would be RT11. Without this configured virtual link, RT11 would be
unable to advertise a route for networks N9-N11 and Host H1 into unable to advertise a route for networks N9-N11 and Host H1 into
the backbone, and there would not be an entry for these networks the backbone, and there would not be an entry for these networks
in Router RT4's routing table. in Router RT4's routing table.
In this example there are two equal-cost paths to Network N12. In this example there are two equal-cost paths to Network N12.
However, they both use the same next hop (Router RT5). However, they both use the same next hop (Router RT5).
Router RT4's routing table would improve (i.e., some of the Router RT4's routing table would improve (i.e., some of the
paths in the routing table would become shorter) if an paths in the routing table would become shorter) if an
additional virtual link were configured between Router RT4 and additional virtual link were configured between Router RT4 and
Router RT3. The new virtual link would itself be associated Router RT3. The new virtual link would itself be associated
with the first entry for area border router RT3 in Table 13 (an with the first entry for area border router RT3 in Table 13 (an
intra-area path through Area 1). This would yield a cost of 1 intra-area path through Area 1). This would yield a cost of 1
for the virtual link. The routing table entries changes that for the virtual link. The routing table entries changes that
would be caused by the addition of this virtual link are shown
Type Dest Area Path Type Cost Next Adv. Type Dest Area Path Type Cost Next Adv.
Hops(s) Router(s) Hops(s) Router(s)
__________________________________________________________________ __________________________________________________________________
N N1 1 intra-area 4 RT1 * N N1 1 intra-area 4 RT1 *
N N2 1 intra-area 4 RT2 * N N2 1 intra-area 4 RT2 *
N N3 1 intra-area 1 * * N N3 1 intra-area 1 * *
N N4 1 intra-area 3 RT3 * N N4 1 intra-area 3 RT3 *
BR RT3 1 intra-area 1 * * BR RT3 1 intra-area 1 * *
__________________________________________________________________ __________________________________________________________________
N Ib 0 intra-area 22 RT5 * N Ib 0 intra-area 22 RT5 *
skipping to change at page 104, line 35 skipping to change at page 104, line 5
N N9-N11,H1 0 inter-area 26 RT5 RT11 N N9-N11,H1 0 inter-area 26 RT5 RT11
__________________________________________________________________ __________________________________________________________________
N N12 * type 1 ext. 16 RT5 RT5,RT7 N N12 * type 1 ext. 16 RT5 RT5,RT7
N N13 * type 1 ext. 16 RT5 RT5 N N13 * type 1 ext. 16 RT5 RT5
N N14 * type 1 ext. 16 RT5 RT5 N N14 * type 1 ext. 16 RT5 RT5
N N15 * type 1 ext. 23 RT5 RT7 N N15 * type 1 ext. 23 RT5 RT7
Table 13: Router RT4's routing table Table 13: Router RT4's routing table
in the presence of areas. in the presence of areas.
would be caused by the addition of this virtual link are shown
in Table 14. in Table 14.
12. Link State Advertisements 12. Link State Advertisements (LSAs)
Each router in the Autonomous System originates one or more link Each router in the Autonomous System originates one or more link
state advertisements. This memo defines five distinct types of link state advertisements (LSAs). This memo defines five distinct types
state advertisements, which are described in Section 4.3. The of LSAs, which are described in Section 4.3. The collection of LSAs
collection of link state advertisements forms the link-state forms the link-state database. Each separate type of LSA has a
database. Each separate type of advertisement has a separate separate function. Router-LSAs and network-LSAs describe how an
function. Router links and network links advertisements describe area's routers and networks are interconnected. Summary-LSAs
how an area's routers and networks are interconnected. Summary link provide a way of condensing an area's routing information. AS-
external-LSAs provide a way of transparently advertising
externally-derived routing information throughout the Autonomous
System.
Each LSA begins with a standard 20-byte header. This LSA header is
discussed below.
12.1. The LSA Header
The LSA header contains the LS type, Link State ID and
Advertising Router fields. The combination of these three
fields uniquely identifies the LSA.
There may be several instances of an LSA present in the
Autonomous System, all at the same time. It must then be
determined which instance is more recent. This determination is
Type Dest Area Path Type Cost Next Adv. Type Dest Area Path Type Cost Next Adv.
Hop(s) Router(s) Hop(s) Router(s)
________________________________________________________________ ________________________________________________________________
N Ib 0 intra-area 16 RT3 * N Ib 0 intra-area 16 RT3 *
N Ia 0 intra-area 21 RT3 * N Ia 0 intra-area 21 RT3 *
BR RT3 0 intra-area 1 * * BR RT3 0 intra-area 1 * *
BR RT10 0 intra-area 16 RT3 * BR RT10 0 intra-area 16 RT3 *
BR RT11 0 intra-area 19 RT3 * BR RT11 0 intra-area 19 RT3 *
________________________________________________________________ ________________________________________________________________
N N9-N11,H1 0 inter-area 20 RT3 RT11 N N9-N11,H1 0 inter-area 20 RT3 RT11
Table 14: Changes resulting from an Table 14: Changes resulting from an
additional virtual link. additional virtual link.
advertisements provide a way of condensing an area's routing
information. AS external advertisements provide a way of
transparently advertising externally-derived routing information
throughout the Autonomous System.
Each link state advertisement begins with a standard 20-byte header.
This link state advertisement header is discussed below.
12.1. The Link State Advertisement Header
The link state advertisement header contains the LS type, Link
State ID and Advertising Router fields. The combination of
these three fields uniquely identifies the link state
advertisement.
There may be several instances of an advertisement present in
the Autonomous System, all at the same time. It must then be
determined which instance is more recent. This determination is
made by examining the LS sequence, LS checksum and LS age made by examining the LS sequence, LS checksum and LS age
fields. These fields are also contained in the 20-byte link fields. These fields are also contained in the 20-byte LSA
state advertisement header. header.
Several of the OSPF packet types list link state advertisements. Several of the OSPF packet types list LSAs. When the instance
When the instance is not important, an advertisement is referred is not important, an LSA is referred to by its LS type, Link
to by its LS type, Link State ID and Advertising Router (see State ID and Advertising Router (see Link State Request
Link State Request Packets). Otherwise, the LS sequence number, Packets). Otherwise, the LS sequence number, LS age and LS
LS age and LS checksum fields must also be referenced. checksum fields must also be referenced.
A detailed explanation of the fields contained in the link state A detailed explanation of the fields contained in the LSA header
advertisement header follows. follows.
12.1.1. LS age 12.1.1. LS age
This field is the age of the link state advertisement in This field is the age of the LSA in seconds. It should be
seconds. It should be processed as an unsigned 16-bit processed as an unsigned 16-bit integer. It is set to 0
integer. It is set to 0 when the link state advertisement when the LSA is originated. It must be incremented by
is originated. It must be incremented by InfTransDelay on InfTransDelay on every hop of the flooding procedure. LSAs
every hop of the flooding procedure. Link state are also aged as they are held in each router's database.
advertisements are also aged as they are held in each
router's database.
The age of a link state advertisement is never incremented The age of an LSA is never incremented past MaxAge. LSAs
past MaxAge. Advertisements having age MaxAge are not used having age MaxAge are not used in the routing table
in the routing table calculation. When an advertisement's calculation. When an LSA's age first reaches MaxAge, it is
age first reaches MaxAge, it is reflooded. A link state reflooded. An LSA of age MaxAge is finally flushed from the
advertisement of age MaxAge is finally flushed from the
database when it is no longer needed to ensure database database when it is no longer needed to ensure database
synchronization. For more information on the aging of link synchronization. For more information on the aging of LSAs,
state advertisements, consult Section 14. consult Section 14.
The LS age field is examined when a router receives two The LS age field is examined when a router receives two
instances of a link state advertisement, both having instances of an LSA, both having identical LS sequence
identical LS sequence numbers and LS checksums. An instance numbers and LS checksums. An instance of age MaxAge is then
of age MaxAge is then always accepted as most recent; this always accepted as most recent; this allows old LSAs to be
allows old advertisements to be flushed quickly from the flushed quickly from the routing domain. Otherwise, if the
routing domain. Otherwise, if the ages differ by more than ages differ by more than MaxAgeDiff, the instance having the
MaxAgeDiff, the instance having the smaller age is accepted smaller age is accepted as most recent.[12] See Section 13.1
as most recent.[12] See Section 13.1 for more details. for more details.
12.1.2. Options 12.1.2. Options
The Options field in the link state advertisement header The Options field in the LSA header indicates which optional
indicates which optional capabilities are associated with capabilities are associated with the LSA. OSPF's optional
the advertisement. OSPF's optional capabilities are capabilities are described in Section 4.5. There are
described in Section 4.5. There are currently two optional currently two optional capabilities defined; they are
capabilities defined; they are represented by the T-bit and represented by the T-bit and E-bit found in the Options
E-bit found in the Options field. The rest of the Options field. The rest of the Options field should be set to zero.
field should be set to zero.
The E-bit represents OSPF's ExternalRoutingCapability. This The E-bit represents OSPF's ExternalRoutingCapability. This
bit should be set in all advertisements associated with the bit should be set in all LSAs associated with the backbone,
backbone, and all advertisements associated with non-stub and all LSAs associated with non-stub areas (see Section
areas (see Section 3.6). It should also be set in all AS 3.6). It should also be set in all AS-external-LSAs. It
external link advertisements. It should be reset in all should be reset in all router-LSAs, network-LSAs and
router links, network links and summary link advertisements summary-LSAs associated with a stub area. For all LSAs, the
associated with a stub area. For all link state setting of the E-bit is for informational purposes only; it
advertisements, the setting of the E-bit is for does not affect the routing table calculation.
informational purposes only; it does not affect the routing
table calculation.
The T-bit represents OSPF's TOS routing capability. This The T-bit represents OSPF's TOS routing capability. This
bit should be set in a router links advertisement if and bit should be set in a router-LSA if and only if the router
only if the router is capable of calculating separate routes is capable of calculating separate routes for each IP TOS
for each IP TOS (see Section 2.5). The T-bit should always (see Section 2.5). The T-bit should always be set in
be set in network links advertisements. It should be set in network-LSAs. It should be set in summary-LSAs and AS-
summary link and AS external link advertisements if and only external-LSAs if and only if the LSA describes paths for all
if the advertisement describes paths for all TOS values, TOS values, instead of just the TOS 0 path. Note that, with
instead of just the TOS 0 path. Note that, with the T-bit the T-bit set, there may still be only a single metric in
set, there may still be only a single metric in the the LSA (the TOS 0 metric). This would mean that paths for
advertisement (the TOS 0 metric). This would mean that non-zero TOS exist, but are equivalent to the TOS 0 path.
paths for non-zero TOS exist, but are equivalent to the TOS An LSA's T-bit is examined when calculating the routing
0 path. A link state advertisement's T-bit is examined when table's non-zero TOS paths (see Section 16.9).
calculating the routing table's non-zero TOS paths (see
Section 16.9).
12.1.3. LS type 12.1.3. LS type
The LS type field dictates the format and function of the The LS type field dictates the format and function of the
link state advertisement. Advertisements of different types LSA. LSAs of different types have different names (e.g.,
have different names (e.g., router links or network links). router-LSAs or network-LSAs). All LSA types defined by this
All advertisement types defined by this memo, except the AS memo, except the AS-external-LSAs (LS type = 5), are flooded
external link advertisements (LS type = 5), are flooded throughout a single area only. AS-external-LSAs are flooded
throughout a single area only. AS external link throughout the entire Autonomous System, excepting stub
advertisements are flooded throughout the entire Autonomous areas (see Section 3.6). Each separate LSA type is briefly
System, excepting stub areas (see Section 3.6). Each described below in Table 15.
separate advertisement type is briefly described below in
Table 15.
12.1.4. Link State ID 12.1.4. Link State ID
This field identifies the piece of the routing domain that This field identifies the piece of the routing domain that
is being described by the advertisement. Depending on the is being described by the LSA. Depending on the LSA's LS
advertisement's LS type, the Link State ID takes on the type, the Link State ID takes on the values listed in Table
values listed in Table 16. 16.
Actually, for Type 3 summary link (LS type = 3) Actually, for Type 3 summary-LSAs (LS type = 3) and AS-
advertisements and AS external link (LS type = 5) external-LSAs (LS type = 5), the Link State ID may
advertisements, the Link State ID may additionally have one additionally have one or more of the destination network's
or more of the destination network's "host" bits set. For "host" bits set. For example, when originating an AS-
example, when originating an AS external link for the external-LSA for the network 10.0.0.0 with mask of
network 10.0.0.0 with mask of 255.0.0.0, the Link State ID 255.0.0.0, the Link State ID can be set to anything in the
can be set to anything in the range 10.0.0.0 through LS Type LSA description
10.255.255.255 inclusive (although 10.0.0.0 should be used ________________________________________________
whenever possible). The freedom to set certain host bits 1 These are the router-LSAs.
LS Type Advertisement description They describe the collected
__________________________________________________ states of the router's
1 These are the router links
advertisements. They describe the
collected states of the router's
interfaces. For more information, interfaces. For more information,
consult Section 12.4.1. consult Section 12.4.1.
__________________________________________________ ________________________________________________
2 These are the network links 2 These are the network-LSAs.
advertisements. They describe the set They describe the set of routers
of routers attached to the network. For attached to the network. For
more information, consult more information, consult
Section 12.4.2. Section 12.4.2.
__________________________________________________ ________________________________________________
3 or 4 These are the summary link 3 or 4 These are the summary-LSAs.
advertisements. They describe They describe inter-area routes,
inter-area routes, and enable the and enable the condensation of
condensation of routing information at routing information at area
area borders. Originated by area border borders. Originated by area border
routers, the Type 3 advertisements routers, the Type 3 summary-LSAs
describe routes to networks while the describe routes to networks while the
Type 4 advertisements describe routes to Type 4 summary-LSAs describe routes to
AS boundary routers. AS boundary routers.
__________________________________________________ ________________________________________________
5 These are the AS external link 5 These are the AS-external-LSAs.
advertisements. Originated by AS Originated by AS boundary routers,
boundary routers, they describe routes they describe routes
to destinations external to the to destinations external to the
Autonomous System. A default route for Autonomous System. A default route for
the Autonomous System can also be the Autonomous System can also be
described by an AS external link described by an AS-external-LSA.
advertisement.
Table 15: OSPF link state advertisements. Table 15: OSPF link state advertisements (LSAs).
LS Type Link State ID LS Type Link State ID
_______________________________________________ _______________________________________________
1 The originating router's Router ID. 1 The originating router's Router ID.
2 The IP interface address of the 2 The IP interface address of the
network's Designated Router. network's Designated Router.
3 The destination network's IP address. 3 The destination network's IP address.
4 The Router ID of the described AS 4 The Router ID of the described AS
boundary router. boundary router.
5 The destination network's IP address. 5 The destination network's IP address.
Table 16: The advertisement's Link State ID. Table 16: The LSA's Link State ID.
allows a router to originate separate advertisements for two range 10.0.0.0 through 10.255.255.255 inclusive (although
networks having the same address but different masks. See 10.0.0.0 should be used whenever possible). The freedom to
Appendix E for details. set certain host bits allows a router to originate separate
LSAs for two networks having the same address but different
masks. See Appendix E for details.
When the link state advertisement is describing a network When the LSA is describing a network (LS type = 2, 3 or 5),
(LS type = 2, 3 or 5), the network's IP address is easily the network's IP address is easily derived by masking the
derived by masking the Link State ID with the network/subnet Link State ID with the network/subnet mask contained in the
mask contained in the body of the link state advertisement. body of the LSA. When the LSA is describing a router (LS
When the link state advertisement is describing a router (LS
type = 1 or 4), the Link State ID is always the described type = 1 or 4), the Link State ID is always the described
router's OSPF Router ID. router's OSPF Router ID.
When an AS external advertisement (LS Type = 5) is When an AS-external-LSA (LS Type = 5) is describing a
describing a default route, its Link State ID is set to default route, its Link State ID is set to
DefaultDestination (0.0.0.0). DefaultDestination (0.0.0.0).
12.1.5. Advertising Router 12.1.5. Advertising Router
This field specifies the OSPF Router ID of the This field specifies the OSPF Router ID of the LSA's
advertisement's originator. For router links originator. For router-LSAs, this field is identical to the
advertisements, this field is identical to the Link State ID Link State ID field. Network-LSAs are originated by the
field. Network link advertisements are originated by the network's Designated Router. Summary-LSAs originated by
network's Designated Router. Summary link advertisements area border routers. AS-external-LSAs are originated by AS
are originated by area border routers. AS external link boundary routers.
advertisements are originated by AS boundary routers.
12.1.6. LS sequence number 12.1.6. LS sequence number
The sequence number field is a signed 32-bit integer. It is The sequence number field is a signed 32-bit integer. It is
used to detect old and duplicate link state advertisements. used to detect old and duplicate LSAs. The space of
The space of sequence numbers is linearly ordered. The sequence numbers is linearly ordered. The larger the
larger the sequence number (when compared as signed 32-bit sequence number (when compared as signed 32-bit integers)
integers) the more recent the advertisement. To describe to the more recent the LSA. To describe to sequence number
sequence number space more precisely, let N refer in the space more precisely, let N refer in the discussion below to
discussion below to the constant 2**31. the constant 2**31.
The sequence number -N (0x80000000) is reserved (and The sequence number -N (0x80000000) is reserved (and
unused). This leaves -N + 1 (0x80000001) as the smallest unused). This leaves -N + 1 (0x80000001) as the smallest
(and therefore oldest) sequence number; this sequence number (and therefore oldest) sequence number; this sequence number
is referred to as the constant InitialSequenceNumber. A is referred to as the constant InitialSequenceNumber. A
router uses InitialSequenceNumber the first time it router uses InitialSequenceNumber the first time it
originates any link state advertisement. Afterwards, the originates any LSA. Afterwards, the LSA's sequence number
advertisement's sequence number is incremented each time the is incremented each time the router originates a new
router originates a new instance of the advertisement. When instance of the LSA. When an attempt is made to increment
an attempt is made to increment the sequence number past the the sequence number past the maximum value of N - 1
maximum value of N - 1 (0x7fffffff; also referred to as (0x7fffffff; also referred to as MaxSequenceNumber), the
MaxSequenceNumber), the current instance of the current instance of the LSA must first be flushed from the
advertisement must first be flushed from the routing domain. routing domain. This is done by prematurely aging the LSA
This is done by prematurely aging the advertisement (see (see Section 14.1) and reflooding it. As soon as this flood
Section 14.1) and reflooding it. As soon as this flood has has been acknowledged by all adjacent neighbors, a new
been acknowledged by all adjacent neighbors, a new instance instance can be originated with sequence number of
can be originated with sequence number of
InitialSequenceNumber. InitialSequenceNumber.
The router may be forced to promote the sequence number of The router may be forced to promote the sequence number of
one of its advertisements when a more recent instance of the one of its LSAs when a more recent instance of the LSA is
advertisement is unexpectedly received during the flooding unexpectedly received during the flooding process. This
process. This should be a rare event. This may indicate should be a rare event. This may indicate that an out-of-
that an out-of-date advertisement, originated by the router date LSA, originated by the router itself before its last
itself before its last restart/reload, still exists in the restart/reload, still exists in the Autonomous System. For
Autonomous System. For more information see Section 13.4. more information see Section 13.4.
12.1.7. LS checksum 12.1.7. LS checksum
This field is the checksum of the complete contents of the This field is the checksum of the complete contents of the
advertisement, excepting the LS age field. The LS age field LSA, excepting the LS age field. The LS age field is
is excepted so that an advertisement's age can be excepted so that an LSA's age can be incremented without
incremented without updating the checksum. The checksum updating the checksum. The checksum used is the same that
used is the same that is used for ISO connectionless is used for ISO connectionless datagrams; it is commonly
datagrams; it is commonly referred to as the Fletcher referred to as the Fletcher checksum. It is documented in
checksum. It is documented in Annex B of [6]. The link Annex B of [Ref6]. The LSA header also contains the length
state advertisement header also contains the length of the of the LSA in bytes; subtracting the size of the LS age
advertisement in bytes; subtracting the size of the LS age
field (two bytes) yields the amount of data to checksum. field (two bytes) yields the amount of data to checksum.
The checksum is used to detect data corruption of an The checksum is used to detect data corruption of an LSA.
advertisement. This corruption can occur while an This corruption can occur while an LSA is being flooded, or
advertisement is being flooded, or while it is being held in while it is being held in a router's memory. The LS
a router's memory. The LS checksum field cannot take on the checksum field cannot take on the value of zero; the
value of zero; the occurrence of such a value should be occurrence of such a value should be considered a checksum
considered a checksum failure. In other words, calculation failure. In other words, calculation of the checksum is not
of the checksum is not optional. optional.
The checksum of a link state advertisement is verified in The checksum of an LSA is verified in two cases: a) when it
two cases: a) when it is received in a Link State Update is received in a Link State Update Packet and b) at times
Packet and b) at times during the aging of the link state during the aging of the link state database. The detection
database. The detection of a checksum failure leads to of a checksum failure leads to separate actions in each
separate actions in each case. See Sections 13 and 14 for case. See Sections 13 and 14 for more details.
more details.
Whenever the LS sequence number field indicates that two Whenever the LS sequence number field indicates that two
instances of an advertisement are the same, the LS checksum instances of an LSA are the same, the LS checksum field is
field is examined. If there is a difference, the instance examined. If there is a difference, the instance with the
with the larger LS checksum is considered to be most larger LS checksum is considered to be most recent.[13] See
recent.[13] See Section 13.1 for more details. Section 13.1 for more details.
12.2. The link state database 12.2. The link state database
A router has a separate link state database for every area to A router has a separate link state database for every area to
which it belongs. All routers belonging to the same area have which it belongs. All routers belonging to the same area have
identical link state databases for the area. identical link state databases for the area.
The databases for each individual area are always dealt with The databases for each individual area are always dealt with
separately. The shortest path calculation is performed separately. The shortest path calculation is performed
separately for each area (see Section 16). Components of the separately for each area (see Section 16). Components of the
area link-state database are flooded throughout the area only. area link-state database are flooded throughout the area only.
Finally, when an adjacency (belonging to Area A) is being Finally, when an adjacency (belonging to Area A) is being
brought up, only the database for Area A is synchronized between brought up, only the database for Area A is synchronized between
the two routers. the two routers.
The area database is composed of router links advertisements, The area database is composed of router-LSAs, network-LSAs and
network links advertisements, and summary link advertisements summary-LSAs (all listed in the area data structure). In
(all listed in the area data structure). In addition, external addition, external routes (AS-external-LSAs) are included in all
routes (AS external advertisements) are included in all non-stub non-stub area databases (see Section 3.6).
area databases (see Section 3.6).
An implementation of OSPF must be able to access individual An implementation of OSPF must be able to access individual
pieces of an area database. This lookup function is based on an pieces of an area database. This lookup function is based on an
advertisement's LS type, Link State ID and Advertising LSA's LS type, Link State ID and Advertising Router.[14] There
Router.[14] There will be a single instance (the most up-to- will be a single instance (the most up-to-date) of each LSA in
date) of each link state advertisement in the database. The the database. The database lookup function is invoked during
database lookup function is invoked during the link state the LSA flooding procedure (Section 13) and the routing table
flooding procedure (Section 13) and the routing table
calculation (Section 16). In addition, using this lookup calculation (Section 16). In addition, using this lookup
function the router can determine whether it has itself ever function the router can determine whether it has itself ever
originated a particular link state advertisement, and if so, originated a particular LSA, and if so, with what LS sequence
with what LS sequence number. number.
A link state advertisement is added to a router's database when An LSA is added to a router's database when either a) it is
either a) it is received during the flooding process (Section received during the flooding process (Section 13) or b) it is
13) or b) it is originated by the router itself (Section 12.4). originated by the router itself (Section 12.4). An LSA is
A link state advertisement is deleted from a router's database deleted from a router's database when either a) it has been
when either a) it has been overwritten by a newer instance overwritten by a newer instance during the flooding process
during the flooding process (Section 13) or b) the router (Section 13) or b) the router originates a newer instance of one
originates a newer instance of one of its self-originated of its self-originated LSAs (Section 12.4) or c) the LSA ages
advertisements (Section 12.4) or c) the advertisement ages out out and is flushed from the routing domain (Section 14).
and is flushed from the routing domain (Section 14). Whenever a Whenever an LSA is deleted from the database it must also be
link state advertisement is deleted from the database it must removed from all neighbors' Link state retransmission lists (see
also be removed from all neighbors' Link state retransmission Section 10).
lists (see Section 10).
12.3. Representation of TOS 12.3. Representation of TOS
All OSPF link state advertisements (with the exception of All OSPF LSAs (with the exception of network-LSAs) specify
network links advertisements) specify metrics. In router links metrics. In router-LSAs, the metrics indicate the costs of the
advertisements, the metrics indicate the costs of the described described interfaces. In summary-LSAs and AS-external-LSAs, the
interfaces. In summary link and AS external link metric indicates the cost of the described path. In all of
advertisements, the metric indicates the cost of the described these LSAs, a separate metric can be specified for each IP TOS.
path. In all of these advertisements, a separate metric can be The encoding of TOS in OSPF LSAs is specified in Table 17. That
specified for each IP TOS. The encoding of TOS in OSPF link table relates the OSPF encoding to the IP packet header's TOS
state advertisements is specified in Table 17. That table field (defined in [Ref12]). The OSPF encoding is expressed as a
relates the OSPF encoding to the IP packet header's TOS field decimal integer, and the IP packet header's TOS field is
(defined in [12]). The OSPF encoding is expressed as a decimal expressed in the binary TOS values used in [Ref12].
integer, and the IP packet header's TOS field is expressed in
the binary TOS values used in [12].
OSPF encoding RFC 1349 TOS values OSPF encoding RFC 1349 TOS values
___________________________________________ ___________________________________________
0 0000 normal service 0 0000 normal service
2 0001 minimize monetary cost 2 0001 minimize monetary cost
4 0010 maximize reliability 4 0010 maximize reliability
6 0011 6 0011
8 0100 maximize throughput 8 0100 maximize throughput
10 0101 10 0101
12 0110 12 0110
skipping to change at page 113, line 26 skipping to change at page 111, line 45
18 1001 18 1001
20 1010 20 1010
22 1011 22 1011
24 1100 24 1100
26 1101 26 1101
28 1110 28 1110
30 1111 30 1111
Table 17: Representing TOS in OSPF. Table 17: Representing TOS in OSPF.
Each OSPF link state advertisement must specify the TOS 0 Each OSPF LSA must specify the TOS 0 metric. Other TOS metrics,
metric. Other TOS metrics, if they appear, must appear in order if they appear, must appear in order of increasing TOS encoding.
of increasing TOS encoding. For example, the TOS 8 (maximize
throughput) metric must always appear before the TOS 16
(minimize delay) metric when both are specified. If a metric
for some non-zero TOS is not specified, its cost defaults to the
cost for TOS 0, unless the T-bit is reset in the advertisement's
Options field (see Section 12.1.2 for more details).
12.4. Originating link state advertisements For example, the TOS 8 (maximize throughput) metric must always
appear before the TOS 16 (minimize delay) metric when both are
specified. If a metric for some non-zero TOS is not specified,
its cost defaults to the cost for TOS 0, unless the T-bit is
reset in the LSA's Options field (see Section 12.1.2 for more
details).
Into any given OSPF area, a router will originate several link 12.4. Originating LSAs
state advertisements. Each router originates a router links
advertisement. If the router is also the Designated Router for
any of the area's networks, it will originate network links
advertisements for those networks.
Area border routers originate a single summary link Into any given OSPF area, a router will originate several LSAs.
advertisement for each known inter-area destination. AS Each router originates a router-LSA. If the router is also the
boundary routers originate a single AS external link Designated Router for any of the area's networks, it will
advertisement for each known AS external destination. originate network-LSAs for those networks.
Area border routers originate a single summary-LSA for each
known inter-area destination. AS boundary routers originate a
single AS-external-LSA for each known AS external destination.
Destinations are advertised one at a time so that the change in Destinations are advertised one at a time so that the change in
any single route can be flooded without reflooding the entire any single route can be flooded without reflooding the entire
collection of routes. During the flooding procedure, many link collection of routes. During the flooding procedure, many LSAs
state advertisements can be carried by a single Link State can be carried by a single Link State Update packet.
Update packet.
As an example, consider Router RT4 in Figure 6. It is an area As an example, consider Router RT4 in Figure 6. It is an area
border router, having a connection to Area 1 and the backbone. border router, having a connection to Area 1 and the backbone.
Router RT4 originates 5 distinct link state advertisements into Router RT4 originates 5 distinct LSAs into the backbone (one
the backbone (one router links, and one summary link for each of router-LSA, and one summary-LSA for each of the networks N1-N4).
the networks N1-N4). Router RT4 will also originate 8 distinct Router RT4 will also originate 8 distinct LSAs into Area 1 (one
link state advertisements into Area 1 (one router links and router-LSA and seven summary-LSAs as pictured in Figure 7). If
seven summary link advertisements as pictured in Figure 7). If
RT4 has been selected as Designated Router for Network N3, it RT4 has been selected as Designated Router for Network N3, it
will also originate a network links advertisement for N3 into will also originate a network-LSA for N3 into Area 1.
Area 1.
In this same figure, Router RT5 will be originating 3 distinct In this same figure, Router RT5 will be originating 3 distinct
AS external link advertisements (one for each of the networks AS-external-LSAs (one for each of the networks N12-N14). These
N12-N14). These will be flooded throughout the entire AS, will be flooded throughout the entire AS, assuming that none of
assuming that none of the areas have been configured as stubs. the areas have been configured as stubs. However, if area 3 has
However, if area 3 has been configured as a stub area, the been configured as a stub area, the AS-external-LSAs for
external advertisements for networks N12-N14 will not be flooded networks N12-N14 will not be flooded into area 3 (see Section
into area 3 (see Section 3.6). Instead, Router RT11 would 3.6). Instead, Router RT11 would originate a default summary-
originate a default summary link advertisement that would be LSA that would be flooded throughout area 3 (see Section
flooded throughout area 3 (see Section 12.4.3). This instructs 12.4.3). This instructs all of area 3's internal routers to
all of area 3's internal routers to send their AS external send their AS external traffic to RT11.
traffic to RT11.
Whenever a new instance of a link state advertisement is Whenever a new instance of an LSA is originated, its LS sequence
originated, its LS sequence number is incremented, its LS age is number is incremented, its LS age is set to 0, its LS checksum
set to 0, its LS checksum is calculated, and the advertisement is calculated, and the LSA is added to the link state database
is added to the link state database and flooded out the and flooded out the appropriate interfaces. See Section 13.2
appropriate interfaces. See Section 13.2 for details concerning for details concerning the installation of the LSA into the link
the installation of the advertisement into the link state state database. See Section 13.3 for details concerning the
database. See Section 13.3 for details concerning the flooding flooding of newly originated LSAs.
of newly originated advertisements.
The ten events that can cause a new instance of a link state The ten events that can cause a new instance of an LSA to be
advertisement to be originated are: originated are:
(1) The LS age field of one of the router's self-originated (1) The LS age field of one of the router's self-originated LSAs
advertisements reaches the value LSRefreshTime. In this reaches the value LSRefreshTime. In this case, a new
case, a new instance of the link state advertisement is instance of the LSA is originated, even though the contents
originated, even though the contents of the advertisement of the LSA (apart from the LSA header) will be the same.
(apart from the link state advertisement header) will be the This guarantees periodic originations of all LSAs. This
same. This guarantees periodic originations of all link periodic updating of LSAs adds robustness to the link state
state advertisements. This periodic updating of link state algorithm. LSAs that solely describe unreachable
advertisements adds robustness to the link state algorithm.
Link state advertisements that solely describe unreachable
destinations should not be refreshed, but should instead be destinations should not be refreshed, but should instead be
flushed from the routing domain (see Section 14.1). flushed from the routing domain (see Section 14.1).
When whatever is being described by a link state advertisement When whatever is being described by an LSA changes, a new LSA is
changes, a new advertisement is originated. However, two originated. However, two instances of the same LSA may not be
instances of the same link state advertisement may not be
originated within the time period MinLSInterval. This may originated within the time period MinLSInterval. This may
require that the generation of the next instance be delayed by require that the generation of the next instance be delayed by
up to MinLSInterval. The following events may cause the up to MinLSInterval. The following events may cause the
contents of a link state advertisement to change. These events contents of an LSA to change. These events should cause new
should cause new originations if and only if the contents of the originations if and only if the contents of the new LSA would be
new advertisement would be different: different:
(2) An interface's state changes (see Section 9.1). This may (2) An interface's state changes (see Section 9.1). This may
mean that it is necessary to produce a new instance of the mean that it is necessary to produce a new instance of the
router links advertisement. router-LSA.
(3) An attached network's Designated Router changes. A new (3) An attached network's Designated Router changes. A new
router links advertisement should be originated. Also, if router-LSA should be originated. Also, if the router itself
the router itself is now the Designated Router, a new is now the Designated Router, a new network-LSA should be
network links advertisement should be produced. If the produced. If the router itself is no longer the Designated
router itself is no longer the Designated Router, any Router, any network-LSA that it might have originated for
network links advertisement that it might have originated the network should be flushed from the routing domain (see
for the network should be flushed from the routing domain Section 14.1).
(see Section 14.1).
(4) One of the neighboring routers changes to/from the FULL (4) One of the neighboring routers changes to/from the FULL
state. This may mean that it is necessary to produce a new state. This may mean that it is necessary to produce a new
instance of the router links advertisement. Also, if the instance of the router-LSA. Also, if the router is itself
router is itself the Designated Router for the attached the Designated Router for the attached network, a new
network, a new network links advertisement should be network-LSA should be produced.
produced.
The next four events concern area border routers only: The next four events concern area border routers only:
(5) An intra-area route has been added/deleted/modified in the (5) An intra-area route has been added/deleted/modified in the
routing table. This may cause a new instance of a summary routing table. This may cause a new instance of a summary-
links advertisement (for this route) to be originated in LSA (for this route) to be originated in each attached area
each attached area (possibly including the backbone). (possibly including the backbone).
(6) An inter-area route has been added/deleted/modified in the (6) An inter-area route has been added/deleted/modified in the
routing table. This may cause a new instance of a summary routing table. This may cause a new instance of a summary-
links advertisement (for this route) to be originated in LSA (for this route) to be originated in each attached area
each attached area (but NEVER for the backbone). (but NEVER for the backbone).
(7) The router becomes newly attached to an area. The router (7) The router becomes newly attached to an area. The router
must then originate summary link advertisements into the must then originate summary-LSAs into the newly attached
newly attached area for all pertinent intra-area and inter- area for all pertinent intra-area and inter-area routes in
area routes in the router's routing table. See Section the router's routing table. See Section 12.4.3 for more
12.4.3 for more details. details.
(8) When the state of one of the router's configured virtual (8) When the state of one of the router's configured virtual
links changes, it may be necessary to originate a new router links changes, it may be necessary to originate a new
links advertisement into the virtual link's transit area router-LSA into the virtual link's Transit area (see the
(see the discussion of the router links advertisement's bit discussion of the router-LSA's bit V in Section 12.4.1), as
V in Section 12.4.1), as well as originating a new router well as originating a new router-LSA into the backbone.
links advertisement into the backbone.
The last two events concern AS boundary routers (and former AS The last two events concern AS boundary routers (and former AS
boundary routers) only: boundary routers) only:
(9) An external route gained through direct experience with an (9) An external route gained through direct experience with an
external routing protocol (like EGP) changes. This will external routing protocol (like BGP) changes. This will
cause an AS boundary router to originate a new instance of cause an AS boundary router to originate a new instance of
an AS external link advertisement. an AS-external-LSA.
(10) (10)
A router ceases to be an AS boundary router, perhaps after A router ceases to be an AS boundary router, perhaps after
restarting. In this situation the router should flush all AS restarting. In this situation the router should flush all
external link advertisements that it had previously AS-external-LSAs that it had previously originated. These
originated. These advertisements can be flushed via the LSAs can be flushed via the premature aging procedure
premature aging procedure specified in Section 14.1. specified in Section 14.1.
The construction of each type of link state advertisement is
explained in detail below. In general, these sections describe
the contents of the advertisement body (i.e., the part coming
after the 20-byte advertisement header). For information
concerning the building of the link state advertisement header,
see Section 12.1.
12.4.1. Router links
A router originates a router links advertisement for each The construction of each type of LSA is explained in detail
area that it belongs to. Such an advertisement describes below. In general, these sections describe the contents of the
the collected states of the router's links to the area. The LSA body (i.e., the part coming after the 20-byte LSA header).
advertisement is flooded throughout the particular area, and For information concerning the building of the LSA header, see
no further. Section 12.1.
.................................... ....................................
. 192.1.2 Area 1 . . 192.1.2 Area 1 .
. + . . + .
. | . . | .
. | 3+---+1 . . | 3+---+1 .
. N1 |--|RT1|-----+ . . N1 |--|RT1|-----+ .
. | +---+ . . | +---+ .
. | _______N3 . . | _______N3 .
. + / . 1+---+ . + / . 1+---+
skipping to change at page 117, line 30 skipping to change at page 115, line 30
. | |RT3|----------------|RT6| . | |RT3|----------------|RT6|
. + +---+ . +---+ . + +---+ . +---+
. 192.1.3 |2 . 18.10.0.6|7 . 192.1.3 |2 . 18.10.0.6|7
. | . | . | . |
. +------------+ . . +------------+ .
. 192.1.4 (N4) . . 192.1.4 (N4) .
.................................... ....................................
Figure 15: Area 1 with IP addresses shown Figure 15: Area 1 with IP addresses shown
The format of a router links advertisement is shown in 12.4.1. Router-LSAs
Appendix A (Section A.4.2). The first 20 bytes of the
advertisement consist of the generic link state A router originates a router-LSA for each area that it
advertisement header that was discussed in Section 12.1. belongs to. Such an LSA describes the collected states of
Router links advertisements have LS type = 1. The router the router's links to the area. The LSA is flooded
indicates whether it is willing to calculate separate routes throughout the particular area, and no further.
for each IP TOS by setting (or resetting) the T-bit of the
link state advertisement's Options field. The format of a router-LSA is shown in Appendix A (Section
A.4.2). The first 20 bytes of the LSA consist of the
generic LSA header that was discussed in Section 12.1.
router-LSAs have LS type = 1. The router indicates whether
it is willing to calculate separate routes for each IP TOS
by setting (or resetting) the T-bit of the LSA's Options
field.
A router also indicates whether it is an area border router, A router also indicates whether it is an area border router,
or an AS boundary router, by setting the appropriate bits or an AS boundary router, by setting the appropriate bits
(bit B and bit E, respectively) in its router links (bit B and bit E, respectively) in its router-LSAs. This
advertisements. This enables paths to those types of routers enables paths to those types of routers to be saved in the
to be saved in the routing table, for later processing of routing table, for later processing of summary-LSAs and AS-
summary link advertisements and AS external link external-LSAs. Bit B should be set whenever the router is
advertisements. Bit B should be set whenever the router is
actively attached to two or more areas, even if the router actively attached to two or more areas, even if the router
is not currently attached to the OSPF backbone area. Bit E is not currently attached to the OSPF backbone area. Bit E
should never be set in a router links advertisement for a should never be set in a router-LSA for a stub area (stub
stub area (stub areas cannot contain AS boundary routers). areas cannot contain AS boundary routers).
In addition, the router sets bit V in its router links
advertisement for Area A if and only if it is the endpoint
of an active virtual link using Area A as its Transit area.
This enables the other routers attached to Area A to
discover whether the area currently supports any virtual
links (i.e., is a transit area).
The router links advertisement then describes the router's In addition, the router sets bit V in its router-LSA for
working connections (i.e., interfaces or links) to the area. Area A if and only if the router is the endpoint of one or
Each link is typed according to the kind of attached more fully adjacent virtual links having Area A as their
network. Each link is also labelled with its Link ID. This Transit area. The setting of bit V enables other routers in
Link ID gives a name to the entity that is on the other end Area A to discover whether the area supports transit traffic
of the link. Table 18 summarizes the values used for the (see TransitCapability in Section 6).
Type and Link ID fields.
The router-LSA then describes the router's working
connections (i.e., interfaces or links) to the area. Each
link is typed according to the kind of attached network.
Each link is also labelled with its Link ID. This Link ID
gives a name to the entity that is on the other end of the
link. Table 18 summarizes the values used for the Type and
Link ID fields.
Link type Description Link ID Link type Description Link ID
__________________________________________________ __________________________________________________
1 Point-to-point Neighbor Router ID 1 Point-to-point Neighbor Router ID
link link
2 Link to transit Interface address of 2 Link to transit Interface address of
network Designated Router network Designated Router
3 Link to stub IP network number 3 Link to stub IP network number
network network
4 Virtual link Neighbor Router ID 4 Virtual link Neighbor Router ID
Table 18: Link descriptions in the Table 18: Link descriptions in the
router links advertisement. router-LSA.
In addition, the Link Data field is specified for each link. In addition, the Link Data field is specified for each link.
This field gives 32 bits of extra information for the link. This field gives 32 bits of extra information for the link.
For links to transit networks, numbered point-to-point links For links to transit networks, numbered point-to-point links
and virtual links, this field specifies the IP interface and virtual links, this field specifies the IP interface
address of the associated router interface (this is needed address of the associated router interface (this is needed
by the routing table calculation, see Section 16.1.1). For by the routing table calculation, see Section 16.1.1). For
links to stub networks, this field specifies the stub links to stub networks, this field specifies the stub
network's IP address mask. For unnumbered point-to-point network's IP address mask. For unnumbered point-to-point
links, the Link Data field should be set to the unnumbered links, the Link Data field should be set to the unnumbered
interface's MIB-II [8] ifIndex value. interface's MIB-II [Ref8] ifIndex value.
Finally, the cost of using the link for output (possibly Finally, the cost of using the link for output (possibly
specifying a different cost for each Type of Service) is specifying a different cost for each Type of Service) is
specified. The output cost of a link is configurable. With specified. The output cost of a link is configurable. With
the exception of links to stub networks, the output cost the exception of links to stub networks, the output cost
must always be non-zero. must always be non-zero.
To further describe the process of building the list of link To further describe the process of building the list of link
descriptions, suppose a router wishes to build a router descriptions, suppose a router wishes to build a router-LSA
links advertisement for Area A. The router examines its for Area A. The router examines its collection of interface
collection of interface data structures. For each data structures. For each interface, the following steps
interface, the following steps are taken: are taken:
o If the attached network does not belong to Area A, no o If the attached network does not belong to Area A, no
links are added to the advertisement, and the next links are added to the LSA, and the next interface
interface should be examined. should be examined.
o If the state of the interface is Down, no links are o If the state of the interface is Down, no links are
added. added.
o If the state of the interface is Loopback, add a Type 3 o If the state of the interface is Loopback, add a Type 3
link (stub network) as long as this is not an interface link (stub network) as long as this is not an interface
to an unnumbered point-to-point network. The Link ID to an unnumbered point-to-point network. The Link ID
should be set to the IP interface address, the Link Data should be set to the IP interface address, the Link Data
set to the mask 0xffffffff (indicating a host route), set to the mask 0xffffffff (indicating a host route),
and the cost set to 0. and the cost set to 0.
skipping to change at page 120, line 4 skipping to change at page 118, line 11
For point-to-point interfaces, one or more link For point-to-point interfaces, one or more link
descriptions are added to the router-LSA as follows: descriptions are added to the router-LSA as follows:
o If the neighboring router is fully adjacent, add a o If the neighboring router is fully adjacent, add a
Type 1 link (point-to-point). The Link ID should be Type 1 link (point-to-point). The Link ID should be
set to the Router ID of the neighboring router. For set to the Router ID of the neighboring router. For
numbered point-to-point networks, the Link Data numbered point-to-point networks, the Link Data
should specify the IP interface address. For should specify the IP interface address. For
unnumbered point-to-point networks, the Link Data unnumbered point-to-point networks, the Link Data
field should specify the interface's MIB-II [8] field should specify the interface's MIB-II [Ref8]
ifIndex value. The cost should be set to the output ifIndex value. The cost should be set to the output
cost of the point-to-point interface. cost of the point-to-point interface.
o In addition, as long as the state of the interface o In addition, as long as the state of the interface
is "Point-to-Point" (and regardless of the is "Point-to-Point" (and regardless of the
neighboring router state), a Type 3 link (stub neighboring router state), a Type 3 link (stub
network) should be added. There are two forms that network) should be added. There are two forms that
this stub link can take: this stub link can take:
Option 1 Option 1
skipping to change at page 121, line 9 skipping to change at page 119, line 15
interface address of the attached network's interface address of the attached network's
Designated Router (which may be the router itself), Designated Router (which may be the router itself),
Link Data set to the router's own IP interface Link Data set to the router's own IP interface
address, and cost equal to the interface's address, and cost equal to the interface's
configured output cost. Otherwise, add a link as if configured output cost. Otherwise, add a link as if
the interface state were Waiting (see above). the interface state were Waiting (see above).
12.4.1.3. Describing virtual links 12.4.1.3. Describing virtual links
For virtual links, a link description is added to the For virtual links, a link description is added to the
router-LSA only when the neighboring router is fully router-LSA only when the virtual neighbor is fully
adjacent. In this case, add a Type 4 link (virtual link) adjacent. In this case, add a Type 4 link (virtual link)
with Link ID set to the Router ID of the neighboring with Link ID set to the Router ID of the virtual
router, Link Data set to the IP interface address neighbor, Link Data set to the IP interface address
associated with the virtual link and cost set to the associated with the virtual link and cost set to the
cost calculated for the virtual link during the routing cost calculated for the virtual link during the routing
table calculation (see Section 15). table calculation (see Section 15).
12.4.1.4. Describing Point-to-MultiPoint interfaces 12.4.1.4. Describing Point-to-MultiPoint interfaces
For operational Point-to-MultiPoint interfaces, one or For operational Point-to-MultiPoint interfaces, one or
more link descriptions are added to the router-LSA as more link descriptions are added to the router-LSA as
follows: follows:
skipping to change at page 121, line 37 skipping to change at page 119, line 43
o For each fully adjacent neighbor associated with the o For each fully adjacent neighbor associated with the
interface, add an additional Type 1 link (point-to- interface, add an additional Type 1 link (point-to-
point) with Link ID set to the Router ID of the point) with Link ID set to the Router ID of the
neighboring router, Link Data set to the IP neighboring router, Link Data set to the IP
interface address and cost equal to the interface's interface address and cost equal to the interface's
configured output cost. configured output cost.
12.4.1.5. Examples of router-LSAs 12.4.1.5. Examples of router-LSAs
Consider the router links advertisements generated by Consider the router-LSAs generated by Router RT3, as
Router RT3, as pictured in Figure 6. The area pictured in Figure 6. The area containing Router RT3
containing Router RT3 (Area 1) has been redrawn, with (Area 1) has been redrawn, with actual network
actual network addresses, in Figure 15. Assume that the addresses, in Figure 15. Assume that the last byte of
last byte of all of RT3's interface addresses is 3, all of RT3's interface addresses is 3, giving it the
giving it the interface addresses 192.1.1.3 and interface addresses 192.1.1.3 and 192.1.4.3, and that
192.1.4.3, and that the other routers have similar the other routers have similar addressing schemes. In
addressing schemes. In addition, assume that all links addition, assume that all links are functional, and that
are functional, and that Router IDs are assigned as the Router IDs are assigned as the smallest IP interface
smallest IP interface address. address.
RT3 originates two router links advertisements, one for RT3 originates two router-LSAs, one for Area 1 and one
Area 1 and one for the backbone. Assume that Router RT4 for the backbone. Assume that Router RT4 has been
has been selected as the Designated router for network selected as the Designated router for network 192.1.1.0.
192.1.1.0. RT3's router links advertisement for Area 1 RT3's router-LSA for Area 1 is then shown below. It
is then shown below. It indicates that RT3 has two indicates that RT3 has two connections to Area 1, the
connections to Area 1, the first a link to the transit first a link to the transit network 192.1.1.0 and the
network 192.1.1.0 and the second a link to the stub second a link to the stub network 192.1.4.0. Note that
network 192.1.4.0. Note that the transit network is the transit network is identified by the IP interface of
identified by the IP interface of its Designated Router its Designated Router (i.e., the Link ID = 192.1.1.4
(i.e., the Link ID = 192.1.1.4 which is the Designated which is the Designated Router RT4's IP interface to
Router RT4's IP interface to 192.1.1.0). Note also that 192.1.1.0). Note also that RT3 has indicated that it is
RT3 has indicated that it is capable of calculating capable of calculating separate routes based on IP TOS,
separate routes based on IP TOS, through setting the T- through setting the T-bit in the Options field. It has
bit in the Options field. It has also indicated that it also indicated that it is an area border router.
is an area border router.
; RT3's router links advertisement for Area 1 ; RT3's router-LSA for Area 1
LS age = 0 ;always true on origination LS age = 0 ;always true on origination
Options = (T-bit|E-bit) ;TOS-capable Options = (T-bit|E-bit) ;TOS-capable
LS type = 1 ;indicates router links LS type = 1 ;indicates router-LSA
Link State ID = 192.1.1.3 ;RT3's Router ID Link State ID = 192.1.1.3 ;RT3's Router ID
Advertising Router = 192.1.1.3 ;RT3's Router ID Advertising Router = 192.1.1.3 ;RT3's Router ID
bit E = 0 ;not an AS boundary router bit E = 0 ;not an AS boundary router
bit B = 1 ;area border router bit B = 1 ;area border router
#links = 2 #links = 2
Link ID = 192.1.1.4 ;IP address of Desig. Rtr. Link ID = 192.1.1.4 ;IP address of Desig. Rtr.
Link Data = 192.1.1.3 ;RT3's IP interface to net Link Data = 192.1.1.3 ;RT3's IP interface to net
Type = 2 ;connects to transit network Type = 2 ;connects to transit network
# other metrics = 0 # other metrics = 0
TOS 0 metric = 1 TOS 0 metric = 1
Link ID = 192.1.4.0 ;IP Network number Link ID = 192.1.4.0 ;IP Network number
Link Data = 0xffffff00 ;Network mask Link Data = 0xffffff00 ;Network mask
Type = 3 ;connects to stub network Type = 3 ;connects to stub network
# other metrics = 0 # other metrics = 0
TOS 0 metric = 2 TOS 0 metric = 2
Next RT3's router links advertisement for the backbone Next RT3's router-LSA for the backbone is shown. It
is shown. It indicates that RT3 has a single attachment indicates that RT3 has a single attachment to the
to the backbone. This attachment is via an unnumbered backbone. This attachment is via an unnumbered point-
point-to-point link to Router RT6. RT3 has again to-point link to Router RT6. RT3 has again indicated
indicated that it is TOS-capable, and that it is an area that it is TOS-capable, and that it is an area border
border router. router.
; RT3's router links advertisement for the backbone ; RT3's router-LSA for the backbone
LS age = 0 ;always true on origination LS age = 0 ;always true on origination
Options = (T-bit|E-bit) ;TOS-capable Options = (T-bit|E-bit) ;TOS-capable
LS type = 1 ;indicates router links LS type = 1 ;indicates router-LSA
Link State ID = 192.1.1.3 ;RT3's router ID Link State ID = 192.1.1.3 ;RT3's router ID
Advertising Router = 192.1.1.3 ;RT3's router ID Advertising Router = 192.1.1.3 ;RT3's router ID
bit E = 0 ;not an AS boundary router bit E = 0 ;not an AS boundary router
bit B = 1 ;area border router bit B = 1 ;area border router
#links = 1 #links = 1
Link ID = 18.10.0.6 ;Neighbor's Router ID Link ID = 18.10.0.6 ;Neighbor's Router ID
Link Data = 0.0.0.3 ;MIB-II ifIndex of P-P link Link Data = 0.0.0.3 ;MIB-II ifIndex of P-P link
Type = 1 ;connects to router Type = 1 ;connects to router
# other metrics = 0 # other metrics = 0
TOS 0 metric = 8 TOS 0 metric = 8
Even though Router RT3 has indicated that it is TOS- Even though Router RT3 has indicated that it is TOS-
capable in the above examples, only a single metric (the capable in the above examples, only a single metric (the
TOS 0 metric) has been specified for each interface. TOS 0 metric) has been specified for each interface.
Different metrics can be specified for each TOS. The Different metrics can be specified for each TOS. The
encoding of TOS in OSPF link state advertisements is encoding of TOS in OSPF LSAs is described in Section
described in Section 12.3. 12.3.
As an example, suppose the point-to-point link between As an example, suppose the point-to-point link between
Routers RT3 and RT6 in Figure 15 is a satellite link. Routers RT3 and RT6 in Figure 15 is a satellite link.
The AS administrator may want to encourage the use of The AS administrator may want to encourage the use of
the line for high bandwidth traffic. This would be done the line for high bandwidth traffic. This would be done
by setting the metric artificially low for the by setting the metric artificially low for the
appropriate TOS value. Router RT3 would then originate appropriate TOS value. Router RT3 would then originate
the following router links advertisement for the the following router-LSA for the backbone (TOS 8 =
backbone (TOS 8 = maximize throughput): maximize throughput):
; RT3's router links advertisement for the backbone ; RT3's router-LSA for the backbone
LS age = 0 ;always true on origination LS age = 0 ;always true on origination
Options = (T-bit|E-bit) ;TOS-capable Options = (T-bit|E-bit) ;TOS-capable
LS type = 1 ;indicates router links LS type = 1 ;indicates router-LSA
Link State ID = 192.1.1.3 ;RT3's Router ID Link State ID = 192.1.1.3 ;RT3's Router ID
Advertising Router = 192.1.1.3 Advertising Router = 192.1.1.3
bit E = 0 ;not an AS boundary router bit E = 0 ;not an AS boundary router
bit B = 1 ;area border router bit B = 1 ;area border router
#links = 1 #links = 1
Link ID = 18.10.0.6 ;Neighbor's Router ID Link ID = 18.10.0.6 ;Neighbor's Router ID
Link Data = 0.0.0.3 ;MIB-II ifIndex of P-P link Link Data = 0.0.0.3 ;MIB-II ifIndex of P-P link
Type = 1 ;connects to router Type = 1 ;connects to router
# other metrics = 1 # other metrics = 1
TOS 0 metric = 8 TOS 0 metric = 8
TOS = 8 ;maximize throughput TOS = 8 ;maximize throughput
metric = 1 ;traffic preferred metric = 1 ;traffic preferred
12.4.2. Network links
A network links advertisement is generated for every transit 12.4.2. Network-LSAs
broadcast or NBMA network. (A transit network is a network
having two or more attached routers). The network links
advertisement describes all the routers that are attached to
the network.
The Designated Router for the network originates the A network-LSA is generated for every transit broadcast or
advertisement. The Designated Router originates the NBMA network. (A transit network is a network having two or
advertisement only if it is fully adjacent to at least one more attached routers). The network-LSA describes all the
other router on the network. The network links routers that are attached to the network.
advertisement is flooded throughout the area that contains
the transit network, and no further. The networks links
advertisement lists those routers that are fully adjacent to
the Designated Router; each fully adjacent router is
identified by its OSPF Router ID. The Designated Router
includes itself in this list.
The Link State ID for a network links advertisement is the The Designated Router for the network originates the LSA.
IP interface address of the Designated Router. This value, The Designated Router originates the LSA only if it is fully
masked by the network's address mask (which is also adjacent to at least one other router on the network. The
contained in the network links advertisement) yields the network-LSA is flooded throughout the area that contains the
network's IP address. transit network, and no further. The network-LSA lists
those routers that are fully adjacent to the Designated
Router; each fully adjacent router is identified by its OSPF
Router ID. The Designated Router includes itself in this
list.
The Link State ID for a network-LSA is the IP interface
address of the Designated Router. This value, masked by the
network's address mask (which is also contained in the
network-LSA) yields the network's IP address.
A router that has formerly been the Designated Router for a A router that has formerly been the Designated Router for a
network, but is no longer, should flush the network links network, but is no longer, should flush the network-LSA that
advertisement that it had previously originated. This it had previously originated. This LSA is no longer used in
advertisement is no longer used in the routing table the routing table calculation. It is flushed by prematurely
calculation. It is flushed by prematurely incrementing the incrementing the LSA's age to MaxAge and reflooding (see
advertisement's age to MaxAge and reflooding (see Section Section 14.1). In addition, in those rare cases where a
14.1). In addition, in those rare cases where a router's router's Router ID has changed, any network-LSAs that were
Router ID has changed, any network links advertisements that originated with the router's previous Router ID must be
were originated with the router's previous Router ID must be
flushed. Since the router may have no idea what it's flushed. Since the router may have no idea what it's
previous Router ID might have been, these network links previous Router ID might have been, these network-LSAs are
advertisements are indicated by having their Link State ID indicated by having their Link State ID equal to one of the
equal to one of the router's IP interface addresses and router's IP interface addresses and their Advertising Router
their Advertising Router equal to some value other than the equal to some value other than the router's current Router
router's current Router ID (see Section 13.4 for more ID (see Section 13.4 for more details).
details).
12.4.2.1. Examples of network-LSAs 12.4.2.1. Examples of network-LSAs
Again consider the area configuration in Figure 6. Again consider the area configuration in Figure 6.
Network links advertisements are originated for Network Network-LSAs are originated for Network N3 in Area 1,
N3 in Area 1, Networks N6 and N8 in Area 2, and Network Networks N6 and N8 in Area 2, and Network N9 in Area 3.
N9 in Area 3. Assuming that Router RT4 has been Assuming that Router RT4 has been selected as the
selected as the Designated Router for Network N3, the Designated Router for Network N3, the following
following network links advertisement is generated by network-LSA is generated by RT4 on behalf of Network N3
RT4 on behalf of Network N3 (see Figure 15 for the (see Figure 15 for the address assignments):
address assignments):
; network links advertisement for Network N3 ; Network-LSA for Network N3
LS age = 0 ;always true on origination LS age = 0 ;always true on origination
Options = (T-bit|E-bit) ;TOS-capable Options = (T-bit|E-bit) ;TOS-capable
LS type = 2 ;indicates network links LS type = 2 ;indicates network-LSA
Link State ID = 192.1.1.4 ;IP address of Desig. Rtr. Link State ID = 192.1.1.4 ;IP address of Desig. Rtr.
Advertising Router = 192.1.1.4 ;RT4's Router ID Advertising Router = 192.1.1.4 ;RT4's Router ID
Network Mask = 0xffffff00 Network Mask = 0xffffff00
Attached Router = 192.1.1.4 ;Router ID Attached Router = 192.1.1.4 ;Router ID
Attached Router = 192.1.1.1 ;Router ID Attached Router = 192.1.1.1 ;Router ID
Attached Router = 192.1.1.2 ;Router ID Attached Router = 192.1.1.2 ;Router ID
Attached Router = 192.1.1.3 ;Router ID Attached Router = 192.1.1.3 ;Router ID
12.4.3. Summary links 12.4.3. Summary-LSAs
The destination described by a summary link advertisement is The destination described by a summary-LSA is either an IP
either an IP network, an AS boundary router or a range of IP network, an AS boundary router or a range of IP addresses.
addresses. Summary link advertisements are flooded Summary-LSAs are flooded throughout a single area only. The
throughout a single area only. The destination described is destination described is one that is external to the area,
one that is external to the area, yet still belongs to the yet still belongs to the Autonomous System.
Autonomous System.
Summary link advertisements are originated by area border Summary-LSAs are originated by area border routers. The
routers. The precise summary routes to advertise into an precise summary routes to advertise into an area are
area are determined by examining the routing table structure determined by examining the routing table structure (see
(see Section 11) in accordance with the algorithm described Section 11) in accordance with the algorithm described
below. Note that only intra-area routes are advertised into below. Note that only intra-area routes are advertised into
the backbone, while both intra-area and inter-area routes the backbone, while both intra-area and inter-area routes
are advertised into the other areas. are advertised into the other areas.
To determine which routes to advertise into an attached Area To determine which routes to advertise into an attached Area
A, each routing table entry is processed as follows. A, each routing table entry is processed as follows.
Remember that each routing table entry describes a set of Remember that each routing table entry describes a set of
equal-cost best paths to a particular destination: equal-cost best paths to a particular destination:
o Only Destination Types of network and AS boundary router o Only Destination Types of network and AS boundary router
are advertised in summary link advertisements. If the are advertised in summary-LSAs. If the routing table
routing table entry's Destination Type is area border entry's Destination Type is area border router, examine
router, examine the next routing table entry. the next routing table entry.
o AS external routes are never advertised in summary link o AS external routes are never advertised in summary-LSAs.
advertisements. If the routing table entry has Path- If the routing table entry has Path-type of type 1
type of type 1 external or type 2 external, examine the external or type 2 external, examine the next routing
next routing table entry. table entry.
o Else, if the area associated with this set of paths is o Else, if the area associated with this set of paths is
the Area A itself, do not generate a summary link the Area A itself, do not generate a summary-LSA for the
advertisement for the route.[17] route.[17]
o Else, if the next hops associated with this set of paths o Else, if the next hops associated with this set of paths
belong to Area A itself, do not generate a summary link belong to Area A itself, do not generate a summary-LSA
advertisement for the route.[18] This is the logical for the route.[18] This is the logical equivalent of a
equivalent of a Distance Vector protocol's split horizon Distance Vector protocol's split horizon logic.
logic.
o Else, if the routing table cost equals or exceeds the o Else, if the routing table cost equals or exceeds the
value LSInfinity, a summary link advertisement cannot be value LSInfinity, a summary-LSA cannot be generated for
generated for this route. this route.
o Else, if the destination of this route is an AS boundary o Else, if the destination of this route is an AS boundary
router, generate a Type 4 link state advertisement for router, generate a Type 4 summary-LSA for the
the destination, with Link State ID equal to the AS destination, with Link State ID equal to the AS boundary
boundary router's Router ID and metric equal to the router's Router ID and metric equal to the routing table
routing table entry's cost. These advertisements should entry's cost. These LSAs should not be generated if
not be generated if Area A has been configured as a stub Area A has been configured as a stub area.
area.
o Else, the Destination type is network. If this is an o Else, the Destination type is network. If this is an
inter-area route, generate a Type 3 advertisement for inter-area route, generate a Type 3 summary-LSA for the
the destination, with Link State ID equal to the destination, with Link State ID equal to the network's
network's address (if necessary, the Link State ID can address (if necessary, the Link State ID can also have
also have one or more of the network's host bits set; one or more of the network's host bits set; see Appendix
see Appendix E for details) and metric equal to the E for details) and metric equal to the routing table
routing table cost. cost.
o The one remaining case is an intra-area route to a o The one remaining case is an intra-area route to a
network. This means that the network is contained in network. This means that the network is contained in
one of the router's directly attached areas. In one of the router's directly attached areas. In
general, this information must be condensed before general, this information must be condensed before
appearing in summary link advertisements. Remember that appearing in summary-LSAs. Remember that an area has a
an area has a configured list of address ranges, each configured list of address ranges, each range consisting
range consisting of an [address,mask] pair and a status of an [address,mask] pair and a status indication of
indication of either Advertise or DoNotAdvertise. At either Advertise or DoNotAdvertise. At most a single
most a single Type 3 advertisement is made for each Type 3 summary-LSA is originated for each range. When
range. When the range's status indicates Advertise, a the range's status indicates Advertise, a Type 3
Type 3 advertisement is generated with Link State ID summary-LSA is generated with Link State ID equal to the
equal to the range's address (if necessary, the Link range's address (if necessary, the Link State ID can
State ID can also have one or more of the range's "host" also have one or more of the range's "host" bits set;
bits set; see Appendix E for details) and cost equal to see Appendix E for details) and cost equal to the
the smallest cost of any of the component networks. When smallest cost of any of the component networks. When the
the range's status indicates DoNotAdvertise, the Type 3 range's status indicates DoNotAdvertise, the Type 3
advertisement is suppressed and the component networks summary-LSA is suppressed and the component networks
remain hidden from other areas. remain hidden from other areas.
By default, if a network is not contained in any By default, if a network is not contained in any
explicitly configured address range, a Type 3 explicitly configured address range, a Type 3 summary-
advertisement is generated with Link State ID equal to LSA is generated with Link State ID equal to the
the network's address (if necessary, the Link State ID network's address (if necessary, the Link State ID can
can also have one or more of the network's "host" bits also have one or more of the network's "host" bits set;
set; see Appendix E for details) and metric equal to the see Appendix E for details) and metric equal to the
network's routing table cost. network's routing table cost.
If virtual links are being used to provide/increase If an area is capable of carrying transit traffic (i.e.,
connectivity of the backbone, routing information its TransitCapability is set to TRUE), routing
concerning the backbone networks should not be condensed information concerning backbone networks should not be
before being summarized into the virtual links' Transit condensed before being summarized into the area. Nor
areas. Nor should the advertisement of backbone networks should the advertisement of backbone networks into
into Transit areas be suppressed. In other words, the transit areas be suppressed. In other words, the
backbone's configured ranges should be ignored when backbone's configured ranges should be ignored when
originating summary links into Transit areas. The originating summary-LSAs into transit areas.
existence of virtual links is determined during the
shortest path calculation for the Transit areas (see
Section 16.1).
If a router advertises a summary advertisement for a If a router advertises a summary-LSA for a destination which
destination which then becomes unreachable, the router must then becomes unreachable, the router must then flush the LSA
then flush the advertisement from the routing domain by from the routing domain by setting its age to MaxAge and
setting its age to MaxAge and reflooding (see Section 14.1). reflooding (see Section 14.1). Also, if the destination is
Also, if the destination is still reachable, yet can no still reachable, yet can no longer be advertised according
longer be advertised according to the above procedure (e.g., to the above procedure (e.g., it is now an inter-area route,
it is now an inter-area route, when it used to be an intra- when it used to be an intra-area route associated with some
area route associated with some non-backbone area; it would non-backbone area; it would thus no longer be advertisable
thus no longer be advertisable to the backbone), the to the backbone), the LSA should also be flushed from the
advertisement should also be flushed from the routing routing domain.
domain.
For the destination described by a summary-LSA there may be For the destination described by a summary-LSA there may be
separate sets of paths, and therefore separate routing table separate sets of paths, and therefore separate routing table
entries, for each Type of Service. All these entries must entries, for each Type of Service. All these entries must
be considered when building the summary link advertisement be considered when building the summary-LSA for the
for the destination; a single advertisement must specify the destination; a single LSA must specify the separate costs
separate costs (if they exist) for each TOS. The encoding (if they exist) for each TOS. The encoding of TOS in OSPF
of TOS in OSPF link state advertisements is described in LSAs is described in Section 12.3.
Section 12.3.
Clearing the T-bit in the Options field of a summary link Clearing the T-bit in the Options field of a summary-LSA
advertisement indicates that there is a TOS 0 path to the indicates that there is a TOS 0 path to the destination, but
destination, but no paths for non-zero TOS. This can happen no paths for non-zero TOS. This can happen when non-TOS-
when non-TOS-capable routers exist in the routing domain capable routers exist in the routing domain (see Section
(see Section 2.5). 2.5).
12.4.3.1. Originating summary links into stub areas 12.4.3.1. Originating summary-LSAs into stub areas
The algorithm in Section 12.4.3 is optional when Area A The algorithm in Section 12.4.3 is optional when Area A
is an OSPF stub area. Area border routers connecting to is an OSPF stub area. Area border routers connecting to
a stub area can originate summary link advertisements a stub area can originate summary-LSAs into the area
into the area according to the Section 12.4.3's according to the Section 12.4.3's algorithm, or can
algorithm, or can choose to originate only a subset of choose to originate only a subset of the summary-LSAs,
the advertisements, possibly under configuration possibly under configuration control. The fewer LSAs
control. The fewer advertisements originated, the originated, the smaller the stub area's link state
smaller the stub area's link state database, further database, further reducing the demands on its routers'
reducing the demands on its routers' resources. However, resources. However, omitting LSAs may also lead to sub-
omitting advertisements may also lead to sub-optimal optimal inter-area routing, although routing will
inter-area routing, although routing will continue to continue to function.
function.
As specified in Section 12.4.3, Type 4 link state As specified in Section 12.4.3, Type 4 summary-LSAs
advertisements (ASBR summary links) are never originated (ASBR-summary-LSAs) are never originated into stub
into stub areas. areas.
In a stub area, instead of importing external routes In a stub area, instead of importing external routes
each area border router originates a "default summary each area border router originates a "default summary-
link" into the area. The Link State ID for the default LSA" into the area. The Link State ID for the default
summary link is set to DefaultDestination, and the summary-LSA is set to DefaultDestination, and the metric
metric set to the (per-area) configurable parameter set to the (per-area) configurable parameter
StubDefaultCost. Note that StubDefaultCost need not be StubDefaultCost. Note that StubDefaultCost need not be
configured identically in all of the stub area's area configured identically in all of the stub area's area
border routers. border routers.
12.4.3.2. Examples of summary-LSAs 12.4.3.2. Examples of summary-LSAs
Consider again the area configuration in Figure 6. Consider again the area configuration in Figure 6.
Routers RT3, RT4, RT7, RT10 and RT11 are all area border Routers RT3, RT4, RT7, RT10 and RT11 are all area border
routers, and therefore are originating summary link routers, and therefore are originating summary-LSAs.
advertisements. Consider in particular Router RT4. Its Consider in particular Router RT4. Its routing table
routing table was calculated as the example in Section was calculated as the example in Section 11.3. RT4
11.3. RT4 originates summary link advertisements into originates summary-LSAs into both the backbone and Area
both the backbone and Area 1. Into the backbone, Router 1. Into the backbone, Router RT4 originates separate
RT4 originates separate advertisements for each of the LSAs for each of the networks N1-N4. Into Area 1,
networks N1-N4. Into Area 1, Router RT4 originates Router RT4 originates separate LSAs for networks N6-N8
separate advertisements for networks N6-N8 and the AS and the AS boundary routers RT5,RT7. It also condenses
boundary routers RT5,RT7. It also condenses host routes host routes Ia and Ib into a single summary-LSA.
Ia and Ib into a single summary link advertisement.
Finally, the routes to networks N9,N10,N11 and Host H1 Finally, the routes to networks N9,N10,N11 and Host H1
are advertised by a single summary link advertisement. are advertised by a single summary-LSA. This
This condensation was originally performed by the router condensation was originally performed by the router
RT11. RT11.
These advertisements are illustrated graphically in These LSAs are illustrated graphically in Figures 7 and
Figures 7 and 8. Two of the summary link advertisements 8. Two of the summary-LSAs originated by Router RT4
originated by Router RT4 follow. The actual IP follow. The actual IP addresses for the networks and
addresses for the networks and routers in question have routers in question have been assigned in Figure 15.
been assigned in Figure 15.
; summary link advertisement for Network N1, ; Summary-LSA for Network N1,
; originated by Router RT4 into the backbone ; originated by Router RT4 into the backbone
LS age = 0 ;always true on origination LS age = 0 ;always true on origination
Options = (T-bit|E-bit) ;TOS-capable Options = (T-bit|E-bit) ;TOS-capable
LS type = 3 ;summary link to IP net LS type = 3 ;Type 3 summary-LSA
Link State ID = 192.1.2.0 ;N1's IP network number Link State ID = 192.1.2.0 ;N1's IP network number
Advertising Router = 192.1.1.4 ;RT4's ID Advertising Router = 192.1.1.4 ;RT4's ID
TOS = 0 TOS = 0
metric = 4 metric = 4
; summary link advertisement for AS boundary router RT7 ; Summary-LSA for AS boundary router RT7
; originated by Router RT4 into Area 1 ; originated by Router RT4 into Area 1
LS age = 0 ;always true on origination LS age = 0 ;always true on origination
Options = (T-bit|E-bit) ;TOS-capable Options = (T-bit|E-bit) ;TOS-capable
LS type = 4 ;summary link to ASBR LS type = 4 ;Type 4 summary-LSA
Link State ID = Router RT7's ID Link State ID = Router RT7's ID
Advertising Router = 192.1.1.4 ;RT4's ID Advertising Router = 192.1.1.4 ;RT4's ID
TOS = 0 TOS = 0
metric = 14 metric = 14
12.4.4. AS external links 12.4.4. AS-external-LSAs
AS external link advertisements describe routes to AS-external-LSAs describe routes to destinations external to
destinations external to the Autonomous System. Most AS the Autonomous System. Most AS-external-LSAs describe
external link advertisements describe routes to specific routes to specific external destinations; in these cases the
external destinations; in these cases the advertisement's LSA's Link State ID is set to the destination network's IP
Link State ID is set to the destination network's IP address address (if necessary, the Link State ID can also have one
(if necessary, the Link State ID can also have one or more or more of the network's "host" bits set; see Appendix E for
of the network's "host" bits set; see Appendix E for
details). However, a default route for the Autonomous details). However, a default route for the Autonomous
System can be described in an AS external link advertisement System can be described in an AS-external-LSA by setting the
by setting the advertisement's Link State ID to LSA's Link State ID to DefaultDestination (0.0.0.0). AS-
DefaultDestination (0.0.0.0). AS external link external-LSAs are originated by AS boundary routers. An AS
advertisements are originated by AS boundary routers. An AS boundary router originates a single AS-external-LSA for each
boundary router originates a single AS external link external route that it has learned, either through another
advertisement for each external route that it has learned, routing protocol (such as BGP), or through configuration
either through another routing protocol (such as EGP), or information.
through configuration information.
AS external link advertisements are the only type of link AS-external-LSAs are the only type of LSAs that are flooded
state advertisements that are flooded throughout the entire throughout the entire Autonomous System; all other types of
Autonomous System; all other types of link state LSAs are specific to a single area. However, AS-external-
advertisements are specific to a single area. However, AS LSAs are not flooded into/throughout stub areas (see Section
external link advertisements are not flooded into/throughout 3.6). This enables a reduction in link state database size
stub areas (see Section 3.6). This enables a reduction in for routers internal to stub areas.
link state database size for routers internal to stub areas.
The metric that is advertised for an external route can be The metric that is advertised for an external route can be
one of two types. Type 1 metrics are comparable to the link one of two types. Type 1 metrics are comparable to the link
state metric. Type 2 metrics are assumed to be larger than state metric. Type 2 metrics are assumed to be larger than
the cost of any intra-AS path. As with summary link the cost of any intra-AS path. As with summary-LSAs, if
advertisements, if separate paths exist based on TOS, separate paths exist based on TOS, separate TOS costs can be
separate TOS costs can be included in the AS external link included in the AS-external-LSA The encoding of TOS in OSPF
advertisement. The encoding of TOS in OSPF link state LSAs is described in Section 12.3. If the T-bit of the
advertisements is described in Section 12.3. If the T-bit LSA's Options field is clear, no non-zero TOS paths to the
of the advertisement's Options field is clear, no non-zero destination exist.
TOS paths to the destination exist.
If a router advertises an AS external link advertisement for If a router advertises an AS-external-LSA for a destination
a destination which then becomes unreachable, the router which then becomes unreachable, the router must then flush
must then flush the advertisement from the routing domain by the LSA from the routing domain by setting its age to MaxAge
setting its age to MaxAge and reflooding (see Section 14.1). and reflooding (see Section 14.1).
12.4.4.1. Examples of AS-external-LSAs 12.4.4.1. Examples of AS-external-LSAs
Consider once again the AS pictured in Figure 6. There Consider once again the AS pictured in Figure 6. There
are two AS boundary routers: RT5 and RT7. Router RT5 are two AS boundary routers: RT5 and RT7. Router RT5
originates three external link advertisements, for originates three AS-external-LSAs, for networks N12-N14.
networks N12-N14. Router RT7 originates two external Router RT7 originates two AS-external-LSAs, for networks
link advertisements, for networks N12 and N15. Assume N12 and N15. Assume that RT7 has learned its route to
that RT7 has learned its route to N12 via EGP, and that N12 via BGP, and that it wishes to advertise a Type 2
it wishes to advertise a Type 2 metric to the AS. RT7 metric to the AS. RT7 would then originate the
would then originate the following advertisement for following LSA for N12:
N12:
; AS external link advertisement for Network N12, ; AS-external-LSA for Network N12,
; originated by Router RT7 ; originated by Router RT7
LS age = 0 ;always true on origination LS age = 0 ;always true on origination
Options = (T-bit|E-bit) ;TOS-capable Options = (T-bit|E-bit) ;TOS-capable
LS type = 5 ;indicates AS external link LS type = 5 ;AS-external-LSA
Link State ID = N12's IP network number Link State ID = N12's IP network number
Advertising Router = Router RT7's ID Advertising Router = Router RT7's ID
bit E = 1 ;Type 2 metric bit E = 1 ;Type 2 metric
TOS = 0 TOS = 0
metric = 2 metric = 2
Forwarding address = 0.0.0.0 Forwarding address = 0.0.0.0
In the above example, the forwarding address field has In the above example, the forwarding address field has
been set to 0.0.0.0, indicating that packets for the been set to 0.0.0.0, indicating that packets for the
external destination should be forwarded to the external destination should be forwarded to the
advertising OSPF router (RT7). This is not always advertising OSPF router (RT7). This is not always
desirable. Consider the example pictured in Figure 16. desirable. Consider the example pictured in Figure 16.
There are three OSPF routers (RTA, RTB and RTC) There are three OSPF routers (RTA, RTB and RTC)
connected to a common network. Only one of these connected to a common network. Only one of these
routers, RTA, is exchanging EGP information with the routers, RTA, is exchanging BGP information with the
non-OSPF router RTX. RTA must then originate AS non-OSPF router RTX. RTA must then originate AS-
external link advertisements for those destinations it external-LSAs for those destinations it has learned from
has learned from RTX. By using the AS external link RTX. By using the AS-external-LSA's forwarding address
advertisement's forwarding address field, RTA can field, RTA can specify that packets for these
specify that packets for these destinations be forwarded destinations be forwarded directly to RTX. Without this
directly to RTX. Without this feature, Routers RTB and feature, Routers RTB and RTC would take an extra hop to
RTC would take an extra hop to get to these get to these destinations.
destinations.
Note that when the forwarding address field is non-zero, Note that when the forwarding address field is non-zero,
it should point to a router belonging to another it should point to a router belonging to another
Autonomous System. Autonomous System.
A forwarding address can also be specified for the A forwarding address can also be specified for the
default route. For example, in figure 16 RTA may want default route. For example, in figure 16 RTA may want
to specify that all externally-destined packets should to specify that all externally-destined packets should
by default be forwarded to its EGP peer RTX. The by default be forwarded to its BGP peer RTX. The
resulting AS external link advertisement is pictured resulting AS-external-LSA is pictured below. Note that
below. Note that the Link State ID is set to the Link State ID is set to DefaultDestination.
DefaultDestination.
; Default route, originated by Router RTA ; Default route, originated by Router RTA
; Packets forwarded through RTX ; Packets forwarded through RTX
LS age = 0 ;always true on origination LS age = 0 ;always true on origination
Options = (T-bit|E-bit) ;TOS-capable Options = (T-bit|E-bit) ;TOS-capable
LS type = 5 ;indicates AS external link LS type = 5 ;AS-external-LSA
Link State ID = DefaultDestination ; default route Link State ID = DefaultDestination ; default route
Advertising Router = Router RTA's ID Advertising Router = Router RTA's ID
bit E = 1 ;Type 2 metric bit E = 1 ;Type 2 metric
TOS = 0 TOS = 0
metric = 1 metric = 1
Forwarding address = RTX's IP address Forwarding address = RTX's IP address
In figure 16, suppose instead that both RTA and RTB In figure 16, suppose instead that both RTA and RTB
exchange EGP information with RTX. In this case, RTA exchange BGP information with RTX. In this case, RTA
and RTB would originate the same set of AS external link and RTB would originate the same set of AS-external-
advertisements. These advertisements, if they specify LSAs. These LSAs, if they specify the same metric,
the same metric, would be functionally equivalent since would be functionally equivalent since they would
they would specify the same destination and forwarding specify the same destination and forwarding address
address (RTX). This leads to a clear duplication of (RTX). This leads to a clear duplication of effort. If
effort. If only one of RTA or RTB originated the set of only one of RTA or RTB originated the set of AS-
external advertisements, the routing would remain the external-LSAs, the routing would remain the same, and
same, and the size of the link state database would the size of the link state database would decrease.
decrease. However, it must be unambiguously defined as However, it must be unambiguously defined as to which
to which router originates the advertisements (otherwise router originates the LSAs (otherwise neither may, or
neither may, or the identity of the originator may the identity of the originator may oscillate). The
oscillate). The following rule is thereby established: following rule is thereby established: if two routers,
if two routers, both reachable from one another, both reachable from one another, originate functionally
originate functionally equivalent AS external equivalent AS-external-LSAs (i.e., same destination,
advertisements (i.e., same destination, cost and non- cost and non-zero forwarding address), then the LSA
zero forwarding address), then the advertisement
originated by the router having the highest OSPF Router originated by the router having the highest OSPF Router
ID is used. The router having the lower OSPF Router ID ID is used. The router having the lower OSPF Router ID
can then flush its advertisement. Flushing a link state can then flush its LSA. Flushing an LSA is discussed in
advertisement is discussed in Section 14.1. Section 14.1.
+
|
+---+.....|.EGP
|RTA|-----|.....+---+
+---+ |-----|RTX|
| +---+
+---+ |
|RTB|-----|
+---+ |
|
+---+ |
|RTC|-----|
+---+ |
|
+
Figure 16: Forwarding address example
13. The Flooding Procedure 13. The Flooding Procedure
Link State Update packets provide the mechanism for flooding link Link State Update packets provide the mechanism for flooding LSAs.
state advertisements. A Link State Update packet may contain A Link State Update packet may contain several distinct LSAs, and
several distinct advertisements, and floods each advertisement one floods each LSA one hop further from its point of origination. To
hop further from its point of origination. To make the flooding make the flooding procedure reliable, each LSA must be acknowledged
procedure reliable, each advertisement must be acknowledged
separately. Acknowledgments are transmitted in Link State separately. Acknowledgments are transmitted in Link State
Acknowledgment packets. Many separate acknowledgments can also be Acknowledgment packets. Many separate acknowledgments can also be
grouped together into a single packet. grouped together into a single packet.
The flooding procedure starts when a Link State Update packet has The flooding procedure starts when a Link State Update packet has
been received. Many consistency checks have been made on the been received. Many consistency checks have been made on the
received packet before being handed to the flooding procedure (see received packet before being handed to the flooding procedure (see
Section 8.2). In particular, the Link State Update packet has been Section 8.2). In particular, the Link State Update packet has been
associated with a particular neighbor, and a particular area. If associated with a particular neighbor, and a particular area. If
the neighbor is in a lesser state than Exchange, the packet should the neighbor is in a lesser state than Exchange, the packet should
be dropped without further processing. be dropped without further processing.
All types of link state advertisements, other than AS external link All types of LSAs, other than AS-external-LSAs, are associated with
advertisements, are associated with a specific area. However, link a specific area. However, LSAs do not contain an area field. An
state advertisements do not contain an area field. A link state LSA's area must be deduced from the Link State Update packet header.
advertisement's area must be deduced from the Link State Update
packet header.
For each link state advertisement contained in a Link State Update For each LSA contained in a Link State Update packet, the following
packet, the following steps are taken: steps are taken:
(1) Validate the advertisement's LS checksum. If the checksum turns +
out to be invalid, discard the advertisement and get the next |
one from the Link State Update packet. +---+.....|.BGP
|RTA|-----|.....+---+
+---+ |-----|RTX|
| +---+
+---+ |
|RTB|-----|
+---+ |
|
+---+ |
|RTC|-----|
+---+ |
|
+
(2) Examine the link state advertisement's LS type. If the LS type Figure 16: Forwarding address example
is unknown, discard the advertisement and get the next one from (1) Validate the LSA's LS checksum. If the checksum turns out to be
the Link State Update Packet. This specification defines LS invalid, discard the LSA and get the next one from the Link
types 1-5 (see Section 4.3). State Update packet.
(3) Else if this is an AS external link advertisement (LS type = 5), (2) Examine the LSA's LS type. If the LS type is unknown, discard
and the area has been configured as a stub area, discard the the LSA and get the next one from the Link State Update Packet.
advertisement and get the next one from the Link State Update This specification defines LS types 1-5 (see Section 4.3).
Packet. AS external link advertisements are not flooded
into/throughout stub areas (see Section 3.6).
(4) Else if the advertisement's LS age is equal to MaxAge, and there (3) Else if this is an AS-external-LSA (LS type = 5), and the area
is currently no instance of the advertisement in the router's has been configured as a stub area, discard the LSA and get the
link state database, then take the following actions: next one from the Link State Update Packet. AS-external-LSAs
are not flooded into/throughout stub areas (see Section 3.6).
(a) Acknowledge the receipt of the advertisement by sending a (4) Else if the LSA's LS age is equal to MaxAge, and there is
Link State Acknowledgment packet back to the sending currently no instance of the LSA in the router's link state
neighbor (see Section 13.5). database, then take the following actions:
(a) Acknowledge the receipt of the LSA by sending a Link State
Acknowledgment packet back to the sending neighbor (see
Section 13.5).
(b) Purge all outstanding requests for equal or previous (b) Purge all outstanding requests for equal or previous
instances of the advertisement from the sending neighbor's instances of the LSA from the sending neighbor's Link State
Link State Request list (see Section 10). Request list (see Section 10).
(c) If the sending neighbor is in state Exchange or in state (c) If the sending neighbor is in state Exchange or in state
Loading, then install the MaxAge advertisement in the link Loading, then install the MaxAge LSA in the link state
state database. Otherwise, simply discard the database. Otherwise, simply discard the LSA. In either
advertisement. In either case, examine the next case, examine the next LSA (if any) listed in the Link State
advertisement (if any) listed in the Link State Update Update packet.
packet.
(5) Otherwise, find the instance of this advertisement that is (5) Otherwise, find the instance of this LSA that is currently
currently contained in the router's link state database. If contained in the router's link state database. If there is no
there is no database copy, or the received advertisement is more database copy, or the received LSA is more recent than the
recent than the database copy (see Section 13.1 below for the database copy (see Section 13.1 below for the determination of
determination of which advertisement is more recent) the which LSA is more recent) the following steps must be performed:
following steps must be performed:
(a) If there is already a database copy, and if the database (a) If there is already a database copy, and if the database
copy was installed less than MinLSArrival seconds ago, copy was installed less than MinLSArrival seconds ago,
discard the new advertisement (without acknowledging it) and discard the new LSA (without acknowledging it) and examine
examine the next advertisement (if any) listed in the Link the next LSA (if any) listed in the Link State Update
State Update packet. packet.
(b) Otherwise immediately flood the new advertisement out some (b) Otherwise immediately flood the new LSA out some subset of
subset of the router's interfaces (see Section 13.3). In the router's interfaces (see Section 13.3). In some cases
some cases (e.g., the state of the receiving interface is DR (e.g., the state of the receiving interface is DR and the
and the advertisement was received from a router other than LSA was received from a router other than the Backup DR) the
the Backup DR) the advertisement will be flooded back out LSA will be flooded back out the receiving interface. This
the receiving interface. This occurrence should be noted occurrence should be noted for later use by the
for later use by the acknowledgment process (Section 13.5). acknowledgment process (Section 13.5).
(c) Remove the current database copy from all neighbors' Link (c) Remove the current database copy from all neighbors' Link
state retransmission lists. state retransmission lists.
(d) Install the new advertisement in the link state database (d) Install the new LSA in the link state database (replacing
(replacing the current database copy). This may cause the the current database copy). This may cause the routing
routing table calculation to be scheduled. In addition, table calculation to be scheduled. In addition, timestamp
timestamp the new advertisement with the current time (i.e., the new LSA with the current time (i.e., the time it was
the time it was received). The flooding procedure cannot received). The flooding procedure cannot overwrite the
overwrite the newly installed advertisement until newly installed LSA until MinLSArrival seconds have elapsed.
MinLSArrival seconds have elapsed. The advertisement The LSA installation process is discussed further in Section
installation process is discussed further in Section 13.2. 13.2.
(e) Possibly acknowledge the receipt of the advertisement by (e) Possibly acknowledge the receipt of the LSA by sending a
sending a Link State Acknowledgment packet back out the Link State Acknowledgment packet back out the receiving
receiving interface. This is explained below in Section interface. This is explained below in Section 13.5.
13.5.
(f) If this new link state advertisement indicates that it was (f) If this new LSA indicates that it was originated by the
originated by the receiving router itself (i.e., is receiving router itself (i.e., is considered a self-
considered a self-originated advertisement), the router must originated LSA), the router must take special action, either
take special action, either updating the advertisement or in updating the LSA or in some cases flushing it from the
some cases flushing it from the routing domain. For a routing domain. For a description of how self-originated
description of how self-originated advertisements are LSAs are detected and subsequently handled, see Section
detected and subsequently handled, see Section 13.4. 13.4.
(6) Else, if there is an instance of the advertisement on the (6) Else, if there is an instance of the LSA on the sending
sending neighbor's Link state request list, an error has neighbor's Link state request list, an error has occurred in the
occurred in the Database Exchange process. In this case, Database Exchange process. In this case, restart the Database
restart the Database Exchange process by generating the neighbor Exchange process by generating the neighbor event BadLSReq for
event BadLSReq for the sending neighbor and stop processing the the sending neighbor and stop processing the Link State Update
Link State Update packet. packet.
(7) Else, if the received advertisement is the same instance as the (7) Else, if the received LSA is the same instance as the database
database copy (i.e., neither one is more recent) the following copy (i.e., neither one is more recent) the following two steps
two steps should be performed: should be performed:
(a) If the advertisement is listed in the Link state (a) If the LSA is listed in the Link state retransmission list
retransmission list for the receiving adjacency, the router for the receiving adjacency, the router itself is expecting
itself is expecting an acknowledgment for this an acknowledgment for this LSA. The router should treat the
advertisement. The router should treat the received received LSA as an acknowledgment by removing the LSA from
advertisement as an acknowledgment by removing the the Link state retransmission list. This is termed an
advertisement from the Link state retransmission list. This "implied acknowledgment". Its occurrence should be noted
is termed an "implied acknowledgment". Its occurrence for later use by the acknowledgment process (Section 13.5).
should be noted for later use by the acknowledgment process
(Section 13.5).
(b) Possibly acknowledge the receipt of the advertisement by (b) Possibly acknowledge the receipt of the LSA by sending a
sending a Link State Acknowledgment packet back out the Link State Acknowledgment packet back out the receiving
receiving interface. This is explained below in Section interface. This is explained below in Section 13.5.
13.5.
(8) Else, the database copy is more recent. If the database copy (8) Else, the database copy is more recent. If the database copy
has LS age equal to MaxAge and LS sequence number equal to has LS age equal to MaxAge and LS sequence number equal to
MaxSequenceNumber, simply discard the received LSA without MaxSequenceNumber, simply discard the received LSA without
acknowledging it. (In this case, the LSA's LS sequence number is acknowledging it. (In this case, the LSA's LS sequence number is
wrapping, and the MaxSequenceNumber LSA must be completely wrapping, and the MaxSequenceNumber LSA must be completely
flushed before any new LSA instance can be introduced). flushed before any new LSA instance can be introduced).
Otherwise, send the database copy back to the sending neighbor, Otherwise, send the database copy back to the sending neighbor,
encapsulated within a Link State Update Packet. The Link State encapsulated within a Link State Update Packet. The Link State
Update Packet should be unicast to the neighbor. In so doing, do Update Packet should be unicast to the neighbor. In so doing, do
not put the database copy of the LSA on the neighbor's link not put the database copy of the LSA on the neighbor's link
state retransmission list, and do not acknowledge the received state retransmission list, and do not acknowledge the received
(less recent) LSA instance. (less recent) LSA instance.
13.1. Determining which link state is newer 13.1. Determining which LSA is newer
When a router encounters two instances of a link state When a router encounters two instances of an LSA, it must
advertisement, it must determine which is more recent. This determine which is more recent. This occurred above when
occurred above when comparing a received advertisement to its comparing a received LSA to its database copy. This comparison
database copy. This comparison must also be done during the must also be done during the Database Exchange procedure which
Database Exchange procedure which occurs during adjacency occurs during adjacency bring-up.
bring-up.
A link state advertisement is identified by its LS type, Link An LSA is identified by its LS type, Link State ID and
State ID and Advertising Router. For two instances of the same Advertising Router. For two instances of the same LSA, the LS
advertisement, the LS sequence number, LS age, and LS checksum sequence number, LS age, and LS checksum fields are used to
fields are used to determine which instance is more recent: determine which instance is more recent:
o The advertisement having the newer LS sequence number is o The LSA having the newer LS sequence number is more recent.
more recent. See Section 12.1.6 for an explanation of the See Section 12.1.6 for an explanation of the LS sequence
LS sequence number space. If both instances have the same number space. If both instances have the same LS sequence
LS sequence number, then: number, then:
o If the two instances have different LS checksums, then the o If the two instances have different LS checksums, then the
instance having the larger LS checksum (when considered as a instance having the larger LS checksum (when considered as a
16-bit unsigned integer) is considered more recent. 16-bit unsigned integer) is considered more recent.
o Else, if only one of the instances has its LS age field set o Else, if only one of the instances has its LS age field set
to MaxAge, the instance of age MaxAge is considered to be to MaxAge, the instance of age MaxAge is considered to be
more recent. more recent.
o Else, if the LS age fields of the two instances differ by o Else, if the LS age fields of the two instances differ by
more than MaxAgeDiff, the instance having the smaller more than MaxAgeDiff, the instance having the smaller
(younger) LS age is considered to be more recent. (younger) LS age is considered to be more recent.
o Else, the two instances are considered to be identical. o Else, the two instances are considered to be identical.
13.2. Installing link state advertisements in the database 13.2. Installing LSAs in the database
Installing a new link state advertisement in the database,
either as the result of flooding or a newly self-originated
advertisement, may cause the OSPF routing table structure to be
recalculated. The contents of the new advertisement should be
compared to the old instance, if present. If there is no
difference, there is no need to recalculate the routing table.
When comparing an LSA to its previous instance, the following Installing a new LSA in the database, either as the result of
are all considered to be differences in contents: flooding or a newly self-originated LSA, may cause the OSPF
routing table structure to be recalculated. The contents of the
new LSA should be compared to the old instance, if present. If
there is no difference, there is no need to recalculate the
routing table. When comparing an LSA to its previous instance,
the following are all considered to be differences in contents:
o The LSA's Options field has changed. o The LSA's Options field has changed.
o One of the LSA instances has LS age set to MaxAge, and o One of the LSA instances has LS age set to MaxAge, and
the other does not. the other does not.
o The length field in the LSA header has changed. o The length field in the LSA header has changed.
o The body of the LSA (i.e., anything outside the 20-byte o The body of the LSA (i.e., anything outside the 20-byte
link state header) has changed. Note that this excludes LSA header) has changed. Note that this excludes changes
changes in LS Sequence Number and LS Checksum. in LS Sequence Number and LS Checksum.
If the contents are different, the following pieces of the If the contents are different, the following pieces of the
routing table must be recalculated, depending on the new routing table must be recalculated, depending on the new LSA's
advertisement's LS type field: LS type field:
Router links and network links advertisements Router-LSAs and network-LSAs
The entire routing table must be recalculated, starting with The entire routing table must be recalculated, starting with
the shortest path calculations for each area (not just the the shortest path calculations for each area (not just the
area whose link-state database has changed). The reason area whose link-state database has changed). The reason
that the shortest path calculation cannot be restricted to that the shortest path calculation cannot be restricted to
the single changed area has to do with the fact that AS the single changed area has to do with the fact that AS
boundary routers may belong to multiple areas. A change in boundary routers may belong to multiple areas. A change in
the area currently providing the best route may force the the area currently providing the best route may force the
router to use an intra-area route provided by a different router to use an intra-area route provided by a different
area.[19] area.[19]
Summary link advertisements Summary-LSAs
The best route to the destination described by the summary The best route to the destination described by the summary-
link advertisement must be recalculated (see Section 16.5). LSA must be recalculated (see Section 16.5). If this
If this destination is an AS boundary router, it may also be destination is an AS boundary router, it may also be
necessary to re-examine all the AS external link necessary to re-examine all the AS-external-LSAs.
advertisements.
AS external link advertisements AS-external-LSAs
The best route to the destination described by the AS The best route to the destination described by the AS-
external link advertisement must be recalculated (see external-LSA must be recalculated (see Section 16.6).
Section 16.6).
Also, any old instance of the advertisement must be removed from Also, any old instance of the LSA must be removed from the
the database when the new advertisement is installed. This old database when the new LSA is installed. This old instance must
instance must also be removed from all neighbors' Link state also be removed from all neighbors' Link state retransmission
retransmission lists (see Section 10). lists (see Section 10).
13.3. Next step in the flooding procedure 13.3. Next step in the flooding procedure
When a new (and more recent) advertisement has been received, it When a new (and more recent) LSA has been received, it must be
must be flooded out some set of the router's interfaces. This flooded out some set of the router's interfaces. This section
section describes the second part of flooding procedure (the describes the second part of flooding procedure (the first part
first part being the processing that occurred in Section 13), being the processing that occurred in Section 13), namely,
namely, selecting the outgoing interfaces and adding the selecting the outgoing interfaces and adding the LSA to the
advertisement to the appropriate neighbors' Link state appropriate neighbors' Link state retransmission lists. Also
retransmission lists. Also included in this part of the included in this part of the flooding procedure is the
flooding procedure is the maintenance of the neighbors' Link maintenance of the neighbors' Link state request lists.
state request lists.
This section is equally applicable to the flooding of an This section is equally applicable to the flooding of an LSA
advertisement that the router itself has just originated (see that the router itself has just originated (see Section 12.4).
Section 12.4). For these advertisements, this section provides For these LSAs, this section provides the entirety of the
the entirety of the flooding procedure (i.e., the processing of flooding procedure (i.e., the processing of Section 13 is not
Section 13 is not performed, since, for example, the performed, since, for example, the LSA has not been received
advertisement has not been received from a neighbor and from a neighbor and therefore does not need to be acknowledged).
therefore does not need to be acknowledged).
Depending upon the advertisement's LS type, the advertisement Depending upon the LSA's LS type, the LSA can be flooded out
can be flooded out only certain interfaces. These interfaces, only certain interfaces. These interfaces, defined by the
defined by the following, are called the eligible interfaces: following, are called the eligible interfaces:
AS external link advertisements (LS Type = 5) AS-external-LSAs (LS Type = 5)
AS external link advertisements are flooded throughout the AS-external-LSAs are flooded throughout the entire AS, with
entire AS, with the exception of stub areas (see Section the exception of stub areas (see Section 3.6). The eligible
3.6). The eligible interfaces are all the router's interfaces are all the router's interfaces, excluding
interfaces, excluding virtual links and those interfaces virtual links and those interfaces attaching to stub areas.
attaching to stub areas.
All other LS types All other LS types</