draft-ietf-ospf-version2-08.txt   draft-ietf-ospf-version2-09.txt 
Network Working Group J. Moy Network Working Group J. Moy
Internet Draft Cascade Communications Corp. Internet Draft Cascade Communications Corp.
Expiration Date: March 1997 September 1996 Expiration Date: July 1997 January 1997
File name: draft-ietf-ospf-version2-08.txt File name: draft-ietf-ospf-version2-09.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.
skipping to change at page 3, line 20 skipping to change at page 3, line 20
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 ..................................... 25 2.5 TOS-based routing ..................................... 24
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 .................................... 27 3.2 Inter-area routing .................................... 26
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 ..................... 41
4.5 Optional OSPF capabilities ............................ 43 4.5 Optional OSPF capabilities ............................ 43
5 Protocol data structures .............................. 44 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 ............................ 53 8 Protocol Packet Processing ............................ 54
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 ........................ 68 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 ....................................... 75 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 ............................ 80 10.3 The Neighbor state machine ............................ 80
10.4 Whether to become adjacent ............................ 86 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 ................ 89 10.6 Receiving Database Description Packets ................ 89
10.7 Receiving Link State Request Packets .................. 92 10.7 Receiving Link State Request Packets .................. 92
10.8 Sending Database Description Packets .................. 92 10.8 Sending Database Description Packets .................. 93
10.9 Sending Link State Request Packets .................... 94 10.9 Sending Link State Request Packets .................... 94
10.10 An Example ............................................ 94 10.10 An Example ............................................ 95
11 The Routing Table Structure ........................... 96 11 The Routing Table Structure ........................... 95
11.1 Routing table lookup .................................. 99 11.1 Routing table lookup ................................. 100
11.2 Sample routing table, without areas .................. 101 11.2 Sample routing table, without areas .................. 101
11.3 Sample routing table, with areas ..................... 101 11.3 Sample routing table, with areas ..................... 102
12 Link State Advertisements (LSAs) ..................... 103 12 Link State Advertisements (LSAs) ..................... 103
12.1 The LSA Header ....................................... 104 12.1 The LSA Header ....................................... 105
12.1.1 LS age ............................................... 105 12.1.1 LS age ............................................... 105
12.1.2 Options .............................................. 105 12.1.2 Options .............................................. 106
12.1.3 LS type .............................................. 106 12.1.3 LS type .............................................. 106
12.1.4 Link State ID ........................................ 106 12.1.4 Link State ID ........................................ 106
12.1.5 Advertising Router ................................... 108 12.1.5 Advertising Router ................................... 108
12.1.6 LS sequence number ................................... 108 12.1.6 LS sequence number ................................... 108
12.1.7 LS checksum .......................................... 109 12.1.7 LS checksum .......................................... 109
12.2 The link state database .............................. 110 12.2 The link state database .............................. 110
12.3 Representation of TOS ................................ 110 12.3 Representation of TOS ................................ 111
12.4 Originating LSAs ..................................... 111 12.4 Originating LSAs ..................................... 112
12.4.1 Router-LSAs .......................................... 114 12.4.1 Router-LSAs .......................................... 115
12.4.1.1 Describing point-to-point interfaces ................. 117 12.4.1.1 Describing point-to-point interfaces ................. 117
12.4.1.2 Describing broadcast and NBMA interfaces ............. 118 12.4.1.2 Describing broadcast and NBMA interfaces ............. 118
12.4.1.3 Describing virtual links ............................. 118 12.4.1.3 Describing virtual links ............................. 119
12.4.1.4 Describing Point-to-MultiPoint interfaces ............ 119 12.4.1.4 Describing Point-to-MultiPoint interfaces ............ 119
12.4.1.5 Examples of router-LSAs .............................. 119 12.4.1.5 Examples of router-LSAs .............................. 119
12.4.2 Network-LSAs ......................................... 121 12.4.2 Network-LSAs ......................................... 122
12.4.2.1 Examples of network-LSAs ............................. 122 12.4.2.1 Examples of network-LSAs ............................. 122
12.4.3 Summary-LSAs ......................................... 123 12.4.3 Summary-LSAs ......................................... 123
12.4.3.1 Originating summary-LSAs into stub areas ............. 125 12.4.3.1 Originating summary-LSAs into stub areas ............. 126
12.4.3.2 Examples of summary-LSAs ............................. 126 12.4.3.2 Examples of summary-LSAs ............................. 126
12.4.4 AS-external-LSAs ..................................... 127 12.4.4 AS-external-LSAs ..................................... 127
12.4.4.1 Examples of AS-external-LSAs ......................... 128 12.4.4.1 Examples of AS-external-LSAs ......................... 128
13 The Flooding Procedure ............................... 129 13 The Flooding Procedure ............................... 130
13.1 Determining which LSA is newer ....................... 133 13.1 Determining which LSA is newer ....................... 133
13.2 Installing LSAs in the database ...................... 133 13.2 Installing LSAs in the database ...................... 134
13.3 Next step in the flooding procedure .................. 135 13.3 Next step in the flooding procedure .................. 135
13.4 Receiving self-originated LSAs ....................... 137 13.4 Receiving self-originated LSAs ....................... 138
13.5 Sending Link State Acknowledgment packets ............ 138 13.5 Sending Link State Acknowledgment packets ............ 138
13.6 Retransmitting LSAs .................................. 139 13.6 Retransmitting LSAs .................................. 141
13.7 Receiving link state acknowledgments ................. 141 13.7 Receiving link state acknowledgments ................. 141
14 Aging The Link State Database ........................ 141 14 Aging The Link State Database ........................ 142
14.1 Premature aging of LSAs .............................. 142 14.1 Premature aging of LSAs .............................. 142
15 Virtual Links ........................................ 143 15 Virtual Links ........................................ 143
16 Calculation of the routing table ..................... 145 16 Calculation of the routing table ..................... 145
16.1 Calculating the shortest-path tree for an area ....... 146 16.1 Calculating the shortest-path tree for an area ....... 146
16.1.1 The next hop calculation ............................. 151 16.1.1 The next hop calculation ............................. 152
16.2 Calculating the inter-area routes .................... 153 16.2 Calculating the inter-area routes .................... 153
16.3 Examining transit areas' summary-LSAs ................ 154 16.3 Examining transit areas' summary-LSAs ................ 154
16.4 Calculating AS external routes ....................... 156 16.4 Calculating AS external routes ....................... 157
16.4.1 External path preferences ............................ 158 16.4.1 External path preferences ............................ 159
16.5 Incremental updates -- summary-LSAs .................. 159 16.5 Incremental updates -- summary-LSAs .................. 159
16.6 Incremental updates -- AS-external-LSAs .............. 160 16.6 Incremental updates -- AS-external-LSAs .............. 160
16.7 Events generated as a result of routing table changes 160 16.7 Events generated as a result of routing table changes 161
16.8 Equal-cost multipath ................................. 161 16.8 Equal-cost multipath ................................. 161
16.9 Building the non-zero-TOS portion of the routing table 162 16.9 Building the non-zero-TOS portion of the routing table 162
Footnotes ............................................ 164 Footnotes ............................................ 164
References ........................................... 168 References ........................................... 168
A OSPF data formats .................................... 170 A OSPF data formats .................................... 170
A.1 Encapsulation of OSPF packets ........................ 170 A.1 Encapsulation of OSPF packets ........................ 170
A.2 The Options field .................................... 172 A.2 The Options field .................................... 172
A.3 OSPF Packet Formats .................................. 174 A.3 OSPF Packet Formats .................................. 174
A.3.1 The OSPF packet header ............................... 175 A.3.1 The OSPF packet header ............................... 175
A.3.2 The Hello packet ..................................... 177 A.3.2 The Hello packet ..................................... 177
skipping to change at page 6, line 20 skipping to change at page 6, line 20
E An algorithm for assigning Link State IDs ............ 216 E An algorithm for assigning Link State IDs ............ 216
F Multiple interfaces to the same network/subnet ....... 218 F Multiple interfaces to the same network/subnet ....... 218
G Differences from RFC 1583 ............................ 219 G Differences from RFC 1583 ............................ 219
G.1 Enhancements to OSPF authentication .................. 219 G.1 Enhancements to OSPF authentication .................. 219
G.2 Addition of Point-to-MultiPoint interface ............ 219 G.2 Addition of Point-to-MultiPoint interface ............ 219
G.3 Support for overlapping area ranges .................. 220 G.3 Support for overlapping area ranges .................. 220
G.4 A modification to the flooding algorithm ............. 221 G.4 A modification to the flooding algorithm ............. 221
G.5 Introduction of the MinLSArrival constant ............ 221 G.5 Introduction of the MinLSArrival constant ............ 221
G.6 Optionally advertising point-to-point links as subnets 222 G.6 Optionally advertising point-to-point links as subnets 222
G.7 Advertising same external route from multiple areas .. 222 G.7 Advertising same external route from multiple areas .. 222
G.8 Retransmission of initial Database Description packets 224
G.9 Detecting interface MTU mismatches ................... 224
Security Considerations .............................. 225 Security Considerations .............................. 225
Author's Address ..................................... 225 Author's Address ..................................... 225
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.
skipping to change at page 21, line 9 skipping to change at page 21, line 9
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
/|\ 6 |\ 7 /|\ 6 |\ 7
8/8|8\ | \ 8/8|8\ | \
/ | \ | \ / | \ 6| \
o | o | \7 o | o | \7
N12 o N14 | \ N12 o N14 | \
N13 2 | \ N13 2 | \
N4 o-----o RT3 \ N4 o-----o RT3 \
/ \ 5 / \ 5
1/ RT10 o-------o Ia 1/ RT10 o-------o Ia
/ |\ / |\
RT4 o-----o N3 3| \1 RT4 o-----o N3 3| \1
/| | \ N6 RT7 /| | \ N6 RT7
/ | N8 o o---------o / | N8 o o---------o
skipping to change at page 22, line 18 skipping to change at page 22, line 18
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
N8 RT10 10 N8 RT10 10
N9 RT10 11 N9 RT10 11
N10 RT10 13 N10 RT10 13
N11 RT10 14 N11 RT10 14
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 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 as dashed lines on the shortest path tree in Figure 5. Use of
this externally derived routing information is considered in the this externally derived routing information is considered in the
skipping to change at page 29, line 4 skipping to change at page 28, line 49
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, AS-external-LSAs from RT5 and RT7 are RT5 and RT7. Finally, AS-external-LSAs from RT5 and RT7 are
flooded throughout the entire AS, and in particular throughout flooded throughout the entire AS, and in particular throughout
Area 1. These LSAs are included in Area 1's database, and yield
routes to Networks N12-N15.
........................... ...........................
. + . . + .
. | 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
Area 1. These LSAs are included in Area 1's database, and yield
routes to Networks N12-N15.
Routers RT3 and RT4 must also summarize Area 1's topology for Routers RT3 and RT4 must also summarize Area 1's topology for
distribution to the backbone. Their backbone LSAs are shown in distribution to the backbone. Their backbone LSAs are shown in
Table 4. These summaries show which networks are contained in Table 4. These summaries show which networks are contained in
Area 1 (i.e., Networks N1-N4), and the distance to these Area 1 (i.e., Networks N1-N4), and the distance to these
networks from the routers RT3 and RT4 respectively. 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
skipping to change at page 30, line 38 skipping to change at page 30, line 35
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 LSAs, and adding in the backbone examining the collected LSAs, and adding in the 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 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.
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 LSA. 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
dist from dist from dist from dist from
RT3 RT4 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 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.
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.
Router RT1 can also determine in this manner the shortest path
to the AS boundary routers RT5 and RT7. Then, by looking at RT5
and RT7's AS-external-LSAs, Router RT1 can decide between RT5 or
RT7 when sending to a destination in another Autonomous System
(one of the networks N12-N15).
Destination RT3 adv. RT4 adv.
_________________________________ _________________________________
Ia,Ib 20 27 Ia,Ib 20 27
N6 16 15 N6 16 15
N7 20 19 N7 20 19
N8 18 18 N8 18 18
N9-N11,H1 29 36 N9-N11,H1 29 36
_________________________________ _________________________________
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.
load share between the two for traffic to Network N8.
Router RT1 can also determine in this manner the shortest path
to the AS boundary routers RT5 and RT7. Then, by looking at RT5
and RT7's AS-external-LSAs, Router RT1 can decide between RT5 or
RT7 when sending to a destination in another Autonomous System
(one of the networks N12-N15).
Note that a failure of the line between Routers RT6 and RT10 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-LSA for the particular route. For example, a summary-LSA for the
skipping to change at page 41, line 13 skipping to change at page 41, line 13
multicast address. multicast address.
LS LSA LSA description LS LSA LSA description
type name type name
________________________________________________________ ________________________________________________________
1 Router-LSAs Originated by all routers. 1 Router-LSAs Originated by all routers.
This LSA 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.
________________________________________________________ ________________________________________________________
2 Network-LSAs Originated for broadcast 2 Network-LSAs Originated for broadcast
and NBMA networks by and NBMA networks by
the Designated Router. This the Designated Router. This
LSA 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-LSAs Originated by area border 3,4 Summary-LSAs Originated by area border
routers, and flooded through- routers, and flooded through-
out the LSA's associated out the LSA's associated
area. Each summary-LSA area. Each summary-LSA
describes a route to a describes a route to a
destination outside the area, destination outside the area,
yet still inside the AS yet still inside the AS
(i.e., an inter-area route). (i.e., an inter-area route).
Type 3 summary-LSAs describe Type 3 summary-LSAs describe
routes to networks. Type 4 routes to networks. Type 4
summary-LSAs describe summary-LSAs describe
routes to AS boundary routers.
________________________________________________________ ________________________________________________________
5 AS-external-LSAs Originated by AS boundary 5 AS-external-LSAs Originated by AS boundary
routers, and flooded through- routers, and flooded through-
out the AS. Each out the AS. Each
AS-external-LSA 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 also be described by
AS-external-LSAs. AS-external-LSAs.
skipping to change at page 47, line 5 skipping to change at page 46, line 44
The OSPF backbone is the special OSPF area responsible for The OSPF backbone is the special OSPF area responsible for
disseminating inter-area routing information. disseminating inter-area routing information.
The area link-state database consists of the collection of router- The area link-state database consists of the collection of router-
LSAs, network-LSAs and summary-LSAs that have originated from the LSAs, network-LSAs and summary-LSAs that have originated from the
area's routers. This information is flooded throughout a single area's routers. This information is flooded throughout a single
area only. The list of AS-external-LSAs (see Section 5) is also area only. The list of AS-external-LSAs (see Section 5) is also
considered to be part of each area's link-state database. considered to be part of each area's link-state database.
Area ID
A 32-bit number identifying the area. The Area ID of 0.0.0.0 is
reserved for the backbone.
List of area address ranges
In order to aggregate routing information at area boundaries,
+----+ +----+
|RT10|------+ |RT10|------+
+----+ \+-------------+ +----+ \+-------------+
/ \ |Routing Table| / \ |Routing Table|
/ \ +-------------+ / \ +-------------+
/ \ / \
+------+ / \ +--------+ +------+ / \ +--------+
|Area 2|---+ +---|Backbone| |Area 2|---+ +---|Backbone|
+------+***********+ +--------+ +------+***********+ +--------+
/ \ * / \ / \ * / \
skipping to change at page 47, line 33 skipping to change at page 47, line 32
|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
Area ID
A 32-bit number identifying the area. The Area ID of 0.0.0.0 is
reserved for the backbone.
List of area address ranges
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
skipping to change at page 53, line 32 skipping to change at page 53, line 27
Two graphs are possible, depending on whether a Designated Two graphs are possible, depending on whether a Designated
Router is elected for the network. On physical point-to-point Router is elected for the network. On physical point-to-point
networks, Point-to-MultiPoint networks and virtual links, networks, Point-to-MultiPoint networks and virtual links,
neighboring routers become adjacent whenever they can neighboring routers become adjacent whenever they can
communicate directly. In contrast, on broadcast and NBMA communicate directly. In contrast, on broadcast and NBMA
networks only the Designated Router and the Backup Designated networks only the Designated Router and the Backup Designated
Router become adjacent to all other routers attached to the Router become adjacent to all other routers attached to the
network. network.
These graphs are shown in Figure 10. It is assumed that Router
RT7 has become the Designated Router, and Router RT3 the Backup
Designated Router, for the Network N2. The Backup Designated
Router performs a lesser function during the flooding procedure
than the Designated Router (see Section 13.3). This is the
reason for the dashed lines connecting the Backup Designated
Router RT3.
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
These graphs are shown in Figure 10. It is assumed that Router
RT7 has become the Designated Router, and Router RT3 the Backup
Designated Router, for the Network N2. The Backup Designated
Router performs a lesser function during the flooding procedure
than the Designated Router (see Section 13.3). This is the
reason for the dashed lines connecting the Backup Designated
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
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 74, line 6 skipping to change at page 74, line 6
Master/Slave Master/Slave
When the two neighbors are exchanging databases, they form a When the two neighbors are exchanging databases, they form a
master/slave relationship. The master sends the first Database master/slave relationship. The master sends the first Database
Description Packet, and is the only part that is allowed to Description Packet, and is the only part that is allowed to
retransmit. The slave can only respond to the master's Database retransmit. The slave can only respond to the master's Database
Description Packets. The master/slave relationship is Description Packets. The master/slave relationship is
negotiated in state ExStart. negotiated in state ExStart.
DD Sequence Number DD Sequence Number
A 32-bit number identifying individual Database Description The DD Sequence number of the Database Description packet that
packets. When the neighbor state ExStart is entered, the DD is currently being sent to the neighbor.
sequence number should be set to a value not previously seen by
the neighboring router. One possible scheme is to use the Last received Database Description packet
machine's time of day counter. The DD sequence number is then The initialize(I), more (M) and master(MS) bits, Options field,
incremented by the master with each new Database Description and DD sequence number contained in the last Database
packet sent. The slave's DD sequence number indicates the last Description packet received from the neighbor. Used to determine
packet received from the master. Only one packet is allowed whether the next Database Description packet received from the
outstanding at a time. neighbor is a duplicate.
Neighbor ID Neighbor ID
The OSPF Router ID of the neighboring router. The Neighbor ID The OSPF Router ID of the neighboring router. The Neighbor ID
is learned when Hello packets are received from the neighbor, or is learned when Hello packets are received from the neighbor, or
is configured if this is a virtual adjacency (see Section C.4). is configured if this is a virtual adjacency (see Section C.4).
Neighbor Priority Neighbor Priority
The Router Priority of the neighboring router. Contained in the The Router Priority of the neighboring router. Contained in the
neighbor's Hello packets, this item is used when selecting the neighbor's Hello packets, this item is used when selecting the
Designated Router for the attached network. Designated Router for the attached network.
skipping to change at page 82, line 27 skipping to change at page 82, line 27
New state: Depends upon action routine. New state: Depends upon action routine.
Action: Determine whether an adjacency should be established Action: Determine whether an adjacency should be established
with the neighbor (see Section 10.4). If not, the with the neighbor (see Section 10.4). If not, the
new neighbor state is 2-Way. new neighbor state is 2-Way.
Otherwise (an adjacency should be established) the Otherwise (an adjacency should be established) the
neighbor state transitions to ExStart. Upon neighbor state transitions to ExStart. Upon
entering this state, the router increments the DD entering this state, the router increments the DD
sequence number for this neighbor. If this is the sequence number in the neighbor data structure. If
first time that an adjacency has been attempted, the this is the first time that an adjacency has been
DD sequence number should be assigned some unique attempted, the DD sequence number should be assigned
value (like the time of day clock). It then some unique value (like the time of day clock). It
declares itself master (sets the master/slave bit to then declares itself master (sets the master/slave
master), and starts sending Database Description bit to master), and starts sending Database
Packets, with the initialize (I), more (M) and Description Packets, with the initialize (I), more
master (MS) bits set. This Database Description (M) and master (MS) bits set. This Database
Packet should be otherwise empty. This Database Description Packet should be otherwise empty. This
Description Packet should be retransmitted at Database Description Packet should be retransmitted
intervals of RxmtInterval until the next state is at intervals of RxmtInterval until the next state is
entered (see Section 10.8). entered (see Section 10.8).
State(s): ExStart State(s): ExStart
Event: NegotiationDone 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
skipping to change at page 84, line 43 skipping to change at page 84, line 43
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 LSAs. Then the state request list are cleared of LSAs. Then the
router increments the DD sequence number for this router increments the DD sequence number in the
neighbor, declares itself master (sets the neighbor data structure, declares itself master
master/slave bit to master), and starts sending (sets the master/slave bit to master), and starts
Database Description Packets, with the initialize sending Database Description Packets, with the
(I), more (M) and master (MS) bits set. This initialize (I), more (M) and master (MS) bits set.
Database Description Packet should be otherwise This Database Description Packet should be 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
skipping to change at page 89, line 34 skipping to change at page 89, line 34
On NBMA networks, receipt of an Hello Packet may also cause an On NBMA networks, receipt of an Hello Packet may also cause an
Hello Packet to be sent back to the neighbor in response. See Hello Packet to be sent back to the neighbor in response. See
Section 9.5.1 for more details. Section 9.5.1 for more details.
10.6. Receiving Database Description Packets 10.6. Receiving Database Description Packets
This section explains the detailed processing of a received This section explains the detailed processing of a received
Database Description Packet. The incoming Database Description Database Description Packet. The incoming Database Description
Packet has already been associated with a neighbor and receiving Packet has already been associated with a neighbor and receiving
interface by the generic input packet processing (Section 8.2). interface by the generic input packet processing (Section 8.2).
The further processing of the Database Description Packet Whether the Database Description packet should be accepted, and
depends on the neighbor state. If the neighbor's state is Down if so, how it should be further processed depends upon the
or Attempt the packet should be ignored. Otherwise, if the neighbor state.
state is:
If a Database Description packet is accepted, the following
packet fields should be saved in the corresponding neighbor data
structure under "last received Database Description packet":
the packet's initialize(I), more (M) and master(MS) bits,
Options field, and DD sequence number. If these fields are set
identically in two consecutive Database Description packets
received from the neighbor, the second Database Description
packet is considered to be a "duplicate" in the processing
described below.
If the Interface MTU field in the Database Description packet
indicates an IP datagram size that is larger than the router can
accept on the receiving interface without fragmentation, the
Database Description packet is rejected. Otherwise, if the
neighbor state is:
Down
The packet should be rejected.
Attempt
The packet should be rejected.
Init Init
The neighbor state machine should be executed with the event The neighbor state machine should be executed with the event
2-WayReceived. This causes an immediate state change to 2-WayReceived. This causes an immediate state change to
either state 2-Way or state ExStart. If the new state is either state 2-Way or state ExStart. If the new state is
ExStart, the processing of the current packet should then ExStart, the processing of the current packet should then
continue in this new state by falling through to case continue in this new state by falling through to case
ExStart below. ExStart below.
2-Way 2-Way
skipping to change at page 90, line 18 skipping to change at page 90, line 39
Exchange), the packet's Options field should be recorded in Exchange), the packet's Options field should be recorded in
the neighbor structure's Neighbor Options field and the the neighbor structure's Neighbor Options field and the
packet should be accepted as next in sequence and processed packet should be accepted as next in sequence and processed
further (see below). Otherwise, the packet should be further (see below). Otherwise, the packet should be
ignored. ignored.
o The initialize(I), more (M) and master(MS) bits are set, o The initialize(I), more (M) and master(MS) bits are set,
the contents of the packet are empty, and the neighbor's the contents of the packet are empty, and the neighbor's
Router ID is larger than the router's own. In this case Router ID is larger than the router's own. In this case
the router is now Slave. Set the master/slave bit to the router is now Slave. Set the master/slave bit to
slave, and set the DD sequence number to that specified slave, and set the neighbor data structure's DD sequence
by the master. number to that specified by the master.
o The initialize(I) and master(MS) bits are off, the o The initialize(I) and master(MS) bits are off, the
packet's DD sequence number equals the router's own DD packet's DD sequence number equals the neighbor data
sequence number (indicating acknowledgment) and the structure's DD sequence number (indicating
neighbor's Router ID is smaller than the router's own. acknowledgment) and the neighbor's Router ID is smaller
In this case the router is Master. than the router's own. In this case the router is
Master.
Exchange Exchange
If the state of the MS-bit is inconsistent with the Duplicate Database Description packets are discarded by the
master/slave state of the connection, generate the neighbor master, and cause the slave to retransmit the last Database
event SeqNumberMismatch and stop processing the packet. Description packet that it had sent. Otherwise (the packet
Otherwise: is not a duplicate):
o If the state of the MS-bit is inconsistent with the
master/slave state of the connection, generate the
neighbor event SeqNumberMismatch and stop processing the
packet.
o If the initialize(I) bit is set, generate the neighbor o If the initialize(I) bit is set, generate the neighbor
event SeqNumberMismatch and stop processing the packet. event SeqNumberMismatch and stop processing the packet.
o If the packet's Options field indicates a different set o If the packet's Options field indicates a different set
of optional OSPF capabilities than were previously of optional OSPF capabilities than were previously
received from the neighbor (recorded in the Neighbor received from the neighbor (recorded in the Neighbor
Options field of the neighbor structure), generate the Options field of the neighbor structure), generate the
neighbor event SeqNumberMismatch and stop processing the neighbor event SeqNumberMismatch and stop processing the
packet. packet.
o If the router is master, and the packet's DD sequence o Database Description packets must be processed in
number equals the router's own DD sequence number (this sequence, as indicated by the packets' DD sequence
packet is the next in sequence) the packet should be numbers. If the router is master, the next packet
accepted and its contents processed (below). received should have DD sequence number equal to the DD
sequence number in the neighbor data structure. If the
o If the router is master, and the packet's DD sequence router is slave, the next packet received should have DD
number is one less than the router's DD sequence number, sequence number equal to one more than the DD sequence
the packet is a duplicate. Duplicates should be number stored in the neighbor data structure. In either
discarded by the master. case, if the packet is the next in sequence it should be
accepted and its contents processed as specified below.
o If the router is slave, and the packet's DD sequence
number is one more than the router's own DD sequence
number (this packet is the next in sequence) the packet
should be accepted and its contents processed (below).
o If the router is slave, and the packet's DD sequence
number is equal to the router's DD sequence number, the
packet is a duplicate. The slave must respond to
duplicates by repeating the last Database Description
packet that it had sent.
o Else, generate the neighbor event SeqNumberMismatch and o Else, generate the neighbor event SeqNumberMismatch and
stop processing the packet. stop processing the packet.
Loading or Full Loading or Full
In this state, the router has sent and received an entire In this state, the router has sent and received an entire
sequence of Database Description Packets. The only packets sequence of Database Description Packets. The only packets
received should be duplicates (see above). In particular, received should be duplicates (see above). In particular,
the packet's Options field should match the set of optional the packet's Options field should match the set of optional
OSPF capabilities previously indicated by the neighbor OSPF capabilities previously indicated by the neighbor
skipping to change at page 92, line 6 skipping to change at page 92, line 24
the LSA. If it does not, or if the database copy is less recent the LSA. If it does not, or if the database copy is less recent
(see Section 13.1), the LSA is put on the Link state request (see Section 13.1), the LSA is put on the Link state request
list so that it can be requested (immediately or at some later list so that it can be requested (immediately or at some later
time) in Link State Request Packets. 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 in the neighbor data
already sent its entire sequence of Database Description structure. If the router has already sent its entire
Packets, and the just accepted packet has the more bit (M) sequence of Database Description Packets, and the just
set to 0, the neighbor event ExchangeDone is generated. accepted packet has the more bit (M) set to 0, the neighbor
Otherwise, it should send a new Database Description to the event ExchangeDone is generated. Otherwise, it should send
slave. a new Database Description to the slave.
Slave Slave
Sets the DD sequence number to the DD sequence number Sets the DD sequence number in the neighbor data structure
appearing in the received packet. The slave must send a to the DD sequence number appearing in the received packet.
Database Description Packet in reply. If the received The slave must send a Database Description Packet in reply.
packet has the more bit (M) set to 0, and the packet to be If the received packet has the more bit (M) set to 0, and
sent by the slave will also have the M-bit set to 0, the the packet to be sent by the slave will also have the M-bit
neighbor event ExchangeDone is generated. Note that the set to 0, the neighbor event ExchangeDone is generated.
slave always generates this event before the master. Note that the 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 LSAs that the neighbor wishes to receive. specify a list of LSAs that the neighbor wishes to receive.
Link State Request Packets should be accepted when the neighbor Link State Request Packets should be accepted when the neighbor
is in states Exchange, Loading, or Full. In all other states is in states Exchange, Loading, or Full. In all other states
Link State Request Packets should be ignored. Link State Request Packets should be ignored.
skipping to change at page 92, line 42 skipping to change at page 93, line 14
located in the router's database, and copied into Link State located in the router's database, and copied into Link State
Update packets for transmission to the neighbor. These LSAs Update packets for transmission to the neighbor. These LSAs
should NOT be placed on the Link state retransmission list for should NOT be placed on the Link state retransmission list for
the neighbor. If an LSA cannot be found in the database, the neighbor. If an LSA 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 Database Description packet's Interface MTU
Section 4.5) are transmitted to the neighbor in the Options field is set to the size of the largest IP datagram that can be
field of the Database Description packet. The router should sent out the sending interface, without fragmentation. Common
maintain the same set of optional capabilities throughout the MTUs in use in the Internet can be found in Table 7-1 of
Database Exchange and flooding procedures. If for some reason [Ref22]. Interface MTU should be set to 0 in Database
the router's optional capabilities change, the Database Exchange Description packets sent over virtual links.
procedure should be restarted by reverting to neighbor state
ExStart. There are currently two optional capabilities defined. The router's optional OSPF capabilities (see Section 4.5) are
The T-bit should be set if and only if the router is capable of transmitted to the neighbor in the Options field of the Database
calculating separate routes for each IP TOS. The E-bit should Description packet. The router should maintain the same set of
be set if and only if the attached network belongs to a non-stub optional capabilities throughout the Database Exchange and
area. The rest of the Options field should be set to zero. flooding procedures. If for some reason the router's optional
capabilities change, the Database Exchange procedure should be
restarted by reverting to neighbor state ExStart. There are
currently two optional capabilities defined. The T-bit should
be set if and only if the router is capable of calculating
separate routes for each IP TOS. The E-bit should be set if and
only if the attached network belongs to a non-stub 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 LSA in the area's link-state database router's database. Each LSA in the area's link-state database
(at the time the neighbor transitions into Exchange state) is (at the time the neighbor transitions into Exchange state) is
listed in the neighbor Database summary list. When a new listed in the neighbor Database summary list. Each new Database
Database Description Packet is to be sent, the packet's DD Description Packet copies its DD sequence number from the
sequence number is incremented, and the (new) top of the neighbor data structure and then describes the current top of
Database summary list is described by the packet. Items are the Database summary list. Items are removed from the Database
removed from the Database summary list when the previous packet 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
by echoing the DD sequence number or b) RxmtInterval seconds by echoing the DD sequence number or b) RxmtInterval seconds
elapse without an acknowledgment, in which case the previous elapse without an acknowledgment, in which case the previous
skipping to change at page 95, line 4 skipping to change at page 95, line 31
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
Packets.
11. The Routing Table Structure
The routing table data structure contains all the information
necessary to forward an IP data packet toward its destination. Each
routing table entry describes the collection of best paths to a
particular destination. When forwarding an IP data packet, the
+---+ +---+ +---+ +---+
|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 96, line 4 skipping to change at page 97, 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.
11. The Routing Table Structure
The routing table data structure contains all the information
necessary to forward an IP data packet toward its destination. Each
routing table entry describes the collection of best paths to a
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
provides the next hop towards the packet's destination. OSPF also provides the next hop towards the packet's destination. OSPF also
provides for the existence of a default route (Destination ID = provides for the existence of a default route (Destination ID =
DefaultDestination, Address Mask = 0x00000000). When the default DefaultDestination, Address Mask = 0x00000000). When the default
route exists, it matches all IP destinations (although any other route exists, it matches all IP destinations (although any other
matching entry is a better match). Finding the routing table entry matching entry is a better match). Finding the routing table entry
that best matches an IP destination is further described in Section that best matches an IP destination is further described in Section
11.1. 11.1.
skipping to change at page 101, line 27 skipping to change at page 102, line 5
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-LSAs originated by RT5 and RT7 are assumed all AS-external-LSAs originated by RT5 and RT7 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
Consider the previous example, this time split into OSPF areas.
An OSPF area configuration is pictured in Figure 6. Router
RT4's routing table will be described for this area
configuration. Router RT4 has a connection to Area 1 and a
backbone connection. This causes Router RT4 to view the AS as
the concatenation of the two graphs shown in Figures 7 and 8.
The resulting routing table is displayed in Table 13.
Again, Routers RT5 and RT7 are AS boundary routers. Routers
RT3, RT4, RT7, RT10 and RT11 are area border routers. Note that
there are two routing entries for the area border router RT3,
since it has two areas in common with RT4 (Area 1 and the
backbone).
Backbone paths have been calculated to all area border routers.
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
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 *
N N7 0 intra-area 12 RT10 * N N7 0 intra-area 12 RT10 *
N N8 0 intra-area 10 RT10 * N N8 0 intra-area 10 RT10 *
N N9 0 intra-area 11 RT10 * N N9 0 intra-area 11 RT10 *
N N10 0 intra-area 13 RT10 * N N10 0 intra-area 13 RT10 *
N N11 0 intra-area 14 RT10 * N N11 0 intra-area 14 RT10 *
N H1 0 intra-area 21 RT10 * N H1 0 intra-area 21 RT10 *
R RT5 0 intra-area 6 RT5 * R RT5 0 intra-area 6 RT5 *
R 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).
11.3. Sample routing table, with areas
Consider the previous example, this time split into OSPF areas.
An OSPF area configuration is pictured in Figure 6. Router
RT4's routing table will be described for this area
configuration. Router RT4 has a connection to Area 1 and a
backbone connection. This causes Router RT4 to view the AS as
the concatenation of the two graphs shown in Figures 7 and 8.
The resulting routing table is displayed in Table 13.
Again, Routers RT5 and RT7 are AS boundary routers. Routers
RT3, RT4, RT7, RT10 and RT11 are area border routers. Note that
there are two routing entries for the area border router RT3,
since it has two areas in common with RT4 (Area 1 and the
backbone).
Backbone paths have been calculated to all area border routers.
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 backbone (by Router RT11). Note that the cost of this route is
the maximum of the set of costs to its individual components. the maximum 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
intra-area path through Area 1). This would yield a cost of 1
for the virtual link. The routing table entries changes that
would be caused by the addition of this virtual link are shown
in Table 14.
12. Link State Advertisements (LSAs)
Each router in the Autonomous System originates one or more link
state advertisements (LSAs). This memo defines five distinct types
of LSAs, which are described in Section 4.3. The collection of LSAs
forms the link-state database. Each separate type of LSA has a
separate function. Router-LSAs and network-LSAs describe how an
area's routers and networks are interconnected. Summary-LSAs
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.
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 *
R RT3 1 intra-area 1 * *
__________________________________________________________________ __________________________________________________________________
N Ib 0 intra-area 22 RT5 * N Ib 0 intra-area 22 RT5 *
N Ia 0 intra-area 27 RT5 * N Ia 0 intra-area 27 RT5 *
R RT3 0 intra-area 21 RT5 * R RT3 0 intra-area 21 RT5 *
R RT5 0 intra-area 8 * * R RT5 0 intra-area 8 * *
R RT7 0 intra-area 14 RT5 * R RT7 0 intra-area 14 RT5 *
R RT10 0 intra-area 22 RT5 * R RT10 0 intra-area 22 RT5 *
R RT11 0 intra-area 25 RT5 * R RT11 0 intra-area 25 RT5 *
__________________________________________________________________ __________________________________________________________________
N N6 0 inter-area 15 RT5 RT7 N N6 0 inter-area 15 RT5 RT7
N N7 0 inter-area 19 RT5 RT7 N N7 0 inter-area 19 RT5 RT7
N N8 0 inter-area 18 RT5 RT7 N N8 0 inter-area 18 RT5 RT7
N N9-N11,H1 0 inter-area 36 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.
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
for the virtual link. The routing table entries changes that
would be caused by the addition of this virtual link are shown
in Table 14.
12. Link State Advertisements (LSAs)
Each router in the Autonomous System originates one or more link
state advertisements (LSAs). This memo defines five distinct types
of LSAs, which are described in Section 4.3. The collection of LSAs
forms the link-state database. Each separate type of LSA has a
separate function. Router-LSAs and network-LSAs describe how an
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 *
R RT3 0 intra-area 1 * * R RT3 0 intra-area 1 * *
R RT10 0 intra-area 16 RT3 * R RT10 0 intra-area 16 RT3 *
R RT11 0 intra-area 19 RT3 *
________________________________________________________________ ________________________________________________________________
N N9-N11,H1 0 inter-area 30 RT3 RT11 N N9-N11,H1 0 inter-area 30 RT3 RT11
Table 14: Changes resulting from an Table 14: Changes resulting from an
additional virtual link. additional virtual link.
area's routers and networks are interconnected. Summary-LSAs
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 12.1. The LSA Header
The LSA header contains the LS type, Link State ID and The LSA header contains the LS type, Link State ID and
Advertising Router fields. The combination of these three Advertising Router fields. The combination of these three
fields uniquely identifies the LSA. fields uniquely identifies the LSA.
There may be several instances of an LSA present in the There may be several instances of an LSA present in the
Autonomous System, all at the same time. It must then be Autonomous System, all at the same time. It must then be
determined which instance is more recent. This determination is 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
skipping to change at page 106, line 29 skipping to change at page 107, line 4
throughout a single area only. AS-external-LSAs are flooded throughout a single area only. AS-external-LSAs are flooded
throughout the entire Autonomous System, excepting stub throughout the entire Autonomous System, excepting stub
areas (see Section 3.6). Each separate LSA type is briefly areas (see Section 3.6). Each separate LSA type is briefly
described below in Table 15. 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 LSA. Depending on the LSA's LS is being described by the LSA. Depending on the LSA's LS
type, the Link State ID takes on the values listed in Table type, the Link State ID takes on the values listed in Table
16.
Actually, for Type 3 summary-LSAs (LS type = 3) and AS-
external-LSAs (LS type = 5), the Link State ID may
additionally have one or more of the destination network's
"host" bits set. For example, when originating an AS-
external-LSA for the network 10.0.0.0 with mask of
255.0.0.0, the Link State ID can be set to anything in the
range 10.0.0.0 through 10.255.255.255 inclusive (although
10.0.0.0 should be used whenever possible). The freedom to
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 LSA is describing a network (LS type = 2, 3 or 5),
the network's IP address is easily derived by masking the
Link State ID with the network/subnet mask contained in the
body of the LSA. When the LSA is describing a router (LS
type = 1 or 4), the Link State ID is always the described
router's OSPF Router ID.
LS Type LSA description LS Type LSA description
________________________________________________ ________________________________________________
1 These are the router-LSAs. 1 These are the router-LSAs.
They describe the collected They describe the collected
states of the router's states of the router's
interfaces. For more information, interfaces. For more information,
consult Section 12.4.1.
________________________________________________ ________________________________________________
2 These are the network-LSAs. 2 These are the network-LSAs.
They describe the set of routers They describe the set 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-LSAs. 3 or 4 These are the summary-LSAs.
They describe inter-area routes, They describe inter-area routes,
and enable the condensation of and enable the condensation of
routing information at area routing information at area
borders. Originated by area border borders. Originated by area border
routers, the Type 3 summary-LSAs routers, the Type 3 summary-LSAs
describe routes to networks while the describe routes to networks while the
Type 4 summary-LSAs describe routes to Type 4 summary-LSAs describe routes to
AS boundary routers.
________________________________________________ ________________________________________________
5 These are the AS-external-LSAs. 5 These are the AS-external-LSAs.
Originated by AS boundary routers, Originated by AS 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-LSA. described by an AS-external-LSA.
Table 15: OSPF link state advertisements (LSAs). Table 15: OSPF link state advertisements (LSAs).
16.
Actually, for Type 3 summary-LSAs (LS type = 3) and AS-
external-LSAs (LS type = 5), the Link State ID may
additionally have one or more of the destination network's
"host" bits set. For example, when originating an AS-
external-LSA for the network 10.0.0.0 with mask of
255.0.0.0, the Link State ID can be set to anything in the
range 10.0.0.0 through 10.255.255.255 inclusive (although
10.0.0.0 should be used whenever possible). The freedom to
set certain host bits allows a router to originate separate
LSAs for two networks having the same address but different
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 LSA's Link State ID. Table 16: The LSA's Link State ID.
masks. See Appendix E for details.
When the LSA is describing a network (LS type = 2, 3 or 5),
the network's IP address is easily derived by masking the
Link State ID with the network/subnet mask contained in the
body of the LSA. When the LSA is describing a router (LS
type = 1 or 4), the Link State ID is always the described
router's OSPF Router ID.
When an AS-external-LSA (LS Type = 5) is describing a When an AS-external-LSA (LS Type = 5) is 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 LSA's This field specifies the OSPF Router ID of the LSA's
originator. For router-LSAs, this field is identical to the originator. For router-LSAs, this field is identical to the
Link State ID field. Network-LSAs are originated by the Link State ID field. Network-LSAs are originated by the
network's Designated Router. Summary-LSAs originated by network's Designated Router. Summary-LSAs originated by
skipping to change at page 114, line 38 skipping to change at page 115, line 5
AS-external-LSAs that it had previously originated. These AS-external-LSAs that it had previously originated. These
LSAs can be flushed via the premature aging procedure LSAs can be flushed via the premature aging procedure
specified in Section 14.1. specified in Section 14.1.
The construction of each type of LSA is explained in detail The construction of each type of LSA is explained in detail
below. In general, these sections describe the contents of the below. In general, these sections describe the contents of the
LSA body (i.e., the part coming after the 20-byte LSA header). LSA body (i.e., the part coming after the 20-byte LSA header).
For information concerning the building of the LSA header, see For information concerning the building of the LSA header, see
Section 12.1. Section 12.1.
12.4.1. Router-LSAs
A router originates a router-LSA for each area that it
belongs to. Such an LSA describes the collected states of
the router's links to the area. The LSA is flooded
throughout the particular area, and no further.
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
.................................... ....................................
. 192.1.2 Area 1 . . 192.1.2 Area 1 .
. + . . + .
. | . . | .
. | 3+---+1 . . | 3+---+1 .
. N1 |--|RT1|-----+ . . N1 |--|RT1|-----+ .
. | +---+ \ . . | +---+ \ .
. | \ _______N3 . . | \ _______N3 .
. + \/ \ . 1+---+ . + \/ \ . 1+---+
. * 192.1.1 *------|RT4| . * 192.1.1 *------|RT4|
skipping to change at page 115, line 29 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
12.4.1. Router-LSAs
A router originates a router-LSA for each area that it
belongs to. Such an LSA describes the collected states of
the router's links to the area. The LSA is flooded
throughout the particular area, and no further.
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 by setting (or resetting) the T-bit of the LSA's Options
field. 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-LSAs. This (bit B and bit E, respectively) in its router-LSAs. This
enables paths to those types of routers to be saved in the enables paths to those types of routers to be saved in the
routing table, for later processing of summary-LSAs and AS- routing table, for later processing of summary-LSAs and AS-
external-LSAs. Bit B should be set whenever the router is external-LSAs. 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
skipping to change at page 130, line 4 skipping to change at page 130, line 18
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 LSA. Flushing an LSA is discussed in can then flush its LSA. Flushing an LSA is discussed in
Section 14.1. Section 14.1.
13. The Flooding Procedure 13. The Flooding Procedure
Link State Update packets provide the mechanism for flooding LSAs. Link State Update packets provide the mechanism for flooding LSAs.
A Link State Update packet may contain several distinct LSAs, and A Link State Update packet may contain several distinct LSAs, and
floods each LSA one hop further from its point of origination. To floods each LSA one hop further from its point of origination. To
make the flooding procedure reliable, each LSA must be acknowledged make the flooding procedure reliable, each LSA must be acknowledged
separately. Acknowledgments are transmitted in Link State
Acknowledgment packets. Many separate acknowledgments can also be
grouped together into a single packet.
The flooding procedure starts when a Link State Update packet has
been received. Many consistency checks have been made on the
received packet before being handed to the flooding procedure (see
Section 8.2). In particular, the Link State Update packet has been
associated with a particular neighbor, and a particular area. If
the neighbor is in a lesser state than Exchange, the packet should
be dropped without further processing.
All types of LSAs, other than AS-external-LSAs, are associated with
+ +
| |
+---+.....|.BGP +---+.....|.BGP
|RTA|-----|.....+---+ |RTA|-----|.....+---+
+---+ |-----|RTX| +---+ |-----|RTX|
| +---+ | +---+
+---+ | +---+ |
|RTB|-----| |RTB|-----|
+---+ | +---+ |
| |
+---+ | +---+ |
|RTC|-----| |RTC|-----|
+---+ | +---+ |
| |
+ +
Figure 16: Forwarding address example Figure 16: Forwarding address example
separately. Acknowledgments are transmitted in Link State
Acknowledgment packets. Many separate acknowledgments can also be
grouped together into a single packet.
The flooding procedure starts when a Link State Update packet has
been received. Many consistency checks have been made on the
received packet before being handed to the flooding procedure (see
Section 8.2). In particular, the Link State Update packet has been
associated with a particular neighbor, and a particular area. If
the neighbor is in a lesser state than Exchange, the packet should
be dropped without further processing.
All types of LSAs, other than AS-external-LSAs, are associated with
a specific area. However, LSAs do not contain an area field. An a specific area. However, LSAs do not contain an area field. An
LSA's area must be deduced from the Link State Update packet header. LSA's area must be deduced from the Link State Update packet header.
For each LSA contained in a Link State Update packet, the following For each LSA contained in a Link State Update packet, the following
steps are taken: steps are taken:
(1) Validate the LSA's LS checksum. If the checksum turns out to be (1) Validate the LSA's LS checksum. If the checksum turns out to be
invalid, discard the LSA and get the next one from the Link invalid, discard the LSA and get the next one from the Link
State Update packet. State Update packet.
skipping to change at page 139, line 34 skipping to change at page 140, line 4
Network N3, it is received by routers RT1, RT2, and RT3. These Network N3, it is received by routers RT1, RT2, and RT3. These
routers will not flood the LSA back onto net N3, but they still routers will not flood the LSA back onto net N3, but they still
must ensure that their link-state databases remain synchronized must ensure that their link-state databases remain synchronized
with their adjacent neighbors. So RT1, RT2, and RT4 are waiting with their adjacent neighbors. So RT1, RT2, and RT4 are waiting
to see an acknowledgment from RT3. Likewise, RT4 and RT3 are to see an acknowledgment from RT3. Likewise, RT4 and RT3 are
both waiting to see acknowledgments from RT1 and RT2. This is both waiting to see acknowledgments from RT1 and RT2. This is
best achieved by sending the acknowledgments as multicasts. best achieved by sending the acknowledgments as multicasts.
The reason that the acknowledgment logic for Backup DRs is The reason that the acknowledgment logic for Backup DRs is
slightly different is because they perform differently during slightly different is because they perform differently during
the flooding of LSAs (see Section 13.3, step 4).
13.6. Retransmitting LSAs
LSAs flooded out an adjacency are placed on the adjacency's Link
state retransmission list. In order to ensure that flooding is
reliable, these LSAs are retransmitted until they are
acknowledged. The length of time between retransmissions is a
configurable per-interface value, RxmtInterval. If this is set
too low for an interface, needless retransmissions will ensue.
If the value is set too high, the speed of the flooding, in the
face of lost packets, may be affected.
Several retransmitted LSAs may fit into a single Link State
Update packet. When LSAs are to be retransmitted, only the
number fitting in a single Link State Update packet should be
Action taken in state Action taken in state
Circumstances Backup All other states Circumstances Backup All other states
_______________________________________________________________ _______________________________________________________________
LSA has No acknowledgment No acknowledgment LSA has No acknowledgment No acknowledgment
been flooded back sent. sent. been flooded back sent. sent.
out receiving in- out receiving in-
terface (see Sec- terface (see Sec-
tion 13, step 5b).
_______________________________________________________________ _______________________________________________________________
LSA is Delayed acknowledg- Delayed ack- LSA is Delayed acknowledg- Delayed ack-
more recent than ment sent if adver- nowledgment sent. more recent than ment sent if adver- nowledgment sent.
database copy, but tisement received database copy, but tisement received
was not flooded from Designated was not flooded from Designated
back out receiving Router, otherwise back out receiving Router, otherwise
interface do nothing interface do nothing
_______________________________________________________________ _______________________________________________________________
LSA is a Delayed acknowledg- No acknowledgment LSA is a Delayed acknowledg- No acknowledgment
duplicate, and was ment sent if adver- sent. duplicate, and was ment sent if adver- sent.
treated as an im- tisement received treated as an im- tisement received
plied acknowledg- from Designated plied acknowledg- from Designated
ment (see Section Router, otherwise ment (see Section Router, otherwise
13, step 7a). do nothing
_______________________________________________________________ _______________________________________________________________
LSA is a Direct acknowledg- Direct acknowledg- LSA is a Direct acknowledg- Direct acknowledg-
duplicate, and was ment sent. ment sent. duplicate, and was ment sent. ment sent.
not treated as an not treated as an
implied ack- implied ack-
nowledgment. nowledgment.
_______________________________________________________________ _______________________________________________________________
LSA's LS Direct acknowledg- Direct acknowledg- LSA's LS Direct acknowledg- Direct acknowledg-
age is equal to ment sent. ment sent. age is equal to ment sent. ment sent.
MaxAge, and there is MaxAge, and there is
no current instance no current instance
of the LSA of the LSA
in the link state in the link state
database (see database (see
Section 13, step 4). Section 13, step 4).
Table 19: Sending link state acknowledgements. Table 19: Sending link state acknowledgements.
the flooding of LSAs (see Section 13.3, step 4).
13.6. Retransmitting LSAs
LSAs flooded out an adjacency are placed on the adjacency's Link
state retransmission list. In order to ensure that flooding is
reliable, these LSAs are retransmitted until they are
acknowledged. The length of time between retransmissions is a
configurable per-interface value, RxmtInterval. If this is set
too low for an interface, needless retransmissions will ensue.
If the value is set too high, the speed of the flooding, in the
face of lost packets, may be affected.
Several retransmitted LSAs may fit into a single Link State
Update packet. When LSAs are to be retransmitted, only the
number fitting in a single Link State Update packet should be
sent. Another packet of retransmissions can be sent whenever sent. Another packet of retransmissions can be sent whenever
some of the LSAs are acknowledged, or on the next firing of the some of the LSAs are acknowledged, or on the next firing of the
retransmission timer. retransmission timer.
Link State Update Packets carrying retransmissions are always Link State Update Packets carrying retransmissions are always
sent as unicasts (directly to the physical address of the sent as unicasts (directly to the physical address of the
neighbor). They are never sent as multicasts. Each LSA's LS neighbor). They are never sent as multicasts. Each LSA's LS
age must be incremented by InfTransDelay (which must be > 0) age must be incremented by InfTransDelay (which must be > 0)
when it is copied into the outgoing Link State Update packet when it is copied into the outgoing Link State Update packet
(until the LS age field reaches the maximum value of MaxAge). (until the LS age field reaches the maximum value of MaxAge).
skipping to change at page 155, line 28 skipping to change at page 155, line 45
table entry, overwrite N's list of next hops with those used table entry, overwrite N's list of next hops with those used
for BR, and set N's routing table cost to IAC. Else, if IAC for BR, and set N's routing table cost to IAC. Else, if IAC
is the same as N's current cost, add BR's list of next hops is the same as N's current cost, add BR's list of next hops
to N's list of next hops. In any case, the area associated to N's list of next hops. In any case, the area associated
with N's routing table entry must remain the backbone area, with N's routing table entry must remain the backbone area,
and the path type (either intra-area or inter-area) must and the path type (either intra-area or inter-area) must
also remain the same. also remain the same.
It is important to note that the above calculation never makes It is important to note that the above calculation never makes
unreachable destinations reachable, but instead just potentially unreachable destinations reachable, but instead just potentially
finds better paths to already reachable destinations. The
calculation installs any better cost found into the routing
table entry, from which it may be readvertised in summary-LSAs
to other areas.
As an example of the calculation, consider the Autonomous System
pictured in Figure 17. There is a single non-backbone area
........................ ........................
. Area 1 (transit) . + . Area 1 (transit) . +
. . | . . |
. +---+1 1+---+100 | . +---+1 1+---+100 |
. |RT2|----------|RT4|=========| . |RT2|----------|RT4|=========|
. 1/+---+********* +---+ | . 1/+---+********* +---+ |
. /******* . | . /******* . |
. 1/*Virtual . | . 1/*Virtual . |
1+---+/* Link . Net|work 1+---+/* Link . Net|work
=======|RT1|* . | N1 =======|RT1|* . | N1
+---+\ . | +---+\ . |
. \ . | . \ . |
. \ . | . \ . |
. 1\+---+1 1+---+20 | . 1\+---+1 1+---+20 |
. |RT3|----------|RT5|=========| . |RT3|----------|RT5|=========|
. +---+ +---+ | . +---+ +---+ |
. . | . . |
........................ + ........................ +
Figure 17: Routing through transit areas Figure 17: Routing through transit areas
finds better paths to already reachable destinations. The
calculation installs any better cost found into the routing
table entry, from which it may be readvertised in summary-LSAs
to other areas.
As an example of the calculation, consider the Autonomous System
pictured in Figure 17. There is a single non-backbone area
(Area 1) that physically divides the backbone into two separate (Area 1) that physically divides the backbone into two separate
pieces. To maintain connectivity of the backbone, a virtual link pieces. To maintain connectivity of the backbone, a virtual link
has been configured between routers RT1 and RT4. On the right has been configured between routers RT1 and RT4. On the right
side of the figure, Network N1 belongs to the backbone. The side of the figure, Network N1 belongs to the backbone. The
dotted lines indicate that there is a much shorter intra-area dotted lines indicate that there is a much shorter intra-area
backbone path between router RT5 and Network N1 (cost 20) than backbone path between router RT5 and Network N1 (cost 20) than
there is between Router RT4 and Network N1 (cost 100). Both there is between Router RT4 and Network N1 (cost 100). Both
Router RT4 and Router RT5 will inject summary-LSAs for Network Router RT4 and Router RT5 will inject summary-LSAs for Network
N1 into Area 1. N1 into Area 1.
skipping to change at page 179, line 32 skipping to change at page 179, line 32
| Router ID | | Router ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Area ID | | Area ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Checksum | AuType | | Checksum | AuType |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication | | Authentication |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication | | Authentication |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 0 | 0 | Options |0|0|0|0|0|I|M|MS | Interface MTU | Options |0|0|0|0|0|I|M|MS
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| DD sequence number | | DD sequence number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
+- -+ +- -+
| | | |
+- An LSA Header -+ +- An LSA Header -+
| | | |
+- -+ +- -+
| | | |
skipping to change at page 180, line 8 skipping to change at page 180, line 8
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... | | ... |
The format of the Database Description packet is very similar to The format of the Database Description packet is very similar to
both the Link State Request and Link State Acknowledgment packets. both the Link State Request and Link State Acknowledgment packets.
The main part of all three is a list of items, each item describing The main part of all three is a list of items, each item describing
a piece of the link-state database. The sending of Database a piece of the link-state database. The sending of Database
Description Packets is documented in Section 10.8. The reception of Description Packets is documented in Section 10.8. The reception of
Database Description packets is documented in Section 10.6. Database Description packets is documented in Section 10.6.
0 These fields are reserved. They must be 0. Interface MTU
The size in bytes of the largest IP datagram that can be sent
out the associated interface, without fragmentation. The MTUs
of common Internet link types can be found in Table 7-1 of
[Ref22]. Interface MTU should be set to 0 in Database
Description packets sent over virtual links.
Options Options
The optional capabilities supported by the router, as documented The optional capabilities supported by the router, as documented
in Section A.2. in Section A.2.
I-bit I-bit
The Init bit. When set to 1, this packet is the first in the The Init bit. When set to 1, this packet is the first in the
sequence of Database Description Packets. sequence of Database Description Packets.
M-bit M-bit
skipping to change at page 225, line 5 skipping to change at page 224, line 19
Unfortunately, this change is not backward compatible. While Unfortunately, this change is not backward compatible. While
the change prevents routing loops when all routers run the the change prevents routing loops when all routers run the
new preference rules, it can actually create routing loops new preference rules, it can actually create routing loops
when some routers are running the new preference rules and when some routers are running the new preference rules and
other routers implement RFC 1583. For this reason, a new other routers implement RFC 1583. For this reason, a new
configuration parameter has been added: configuration parameter has been added:
RFC1583Compatibility. Only when RFC1583Compatibility is set RFC1583Compatibility. Only when RFC1583Compatibility is set
to "disabled" will the new preference rules take effect. See to "disabled" will the new preference rules take effect. See
Appendix C for more details. Appendix C for more details.
G.8 Retransmission of initial Database Description packets
This memo allows retransmission of initial Database Description
packets, without resetting the state of the adjacency. In some
environments, retransmission of the initial Database Description
packet may be unavoidable. For example, the link delay incurred
by a satellite link may exceed the value configured for an
interface's RxmtInterval. In RFC 1583 such an environment
prevents a full adjacency from ever forming.
In this memo, changes have been made in the reception of
Database Description packets so that retransmitted initial
Database Description packets are treated identically to any
other retransmitted Database Description packets. See Section
10.6 for details.
G.9 Detecting interface MTU mismatches
When two neighboring routers have a different interface MTU for
their common network segment, serious problems can ensue: large
packets are prevented from being successfully transferred from
one router to the other, impairing OSPF's flooding algorithm and
possibly creating "black holes" for user data traffic.
This memo provides a fix for the interface MTU mismatch problem
by advertising the interface MTU in Database Description
packets. When a router receives a Database description packet
advertising an MTU larger than the router can receive, the
router drops the Database Description packet. This prevents an
adjacency from forming, telling OSPF flooding and user data
traffic to avoid the connection between the two routers. For
more information, see Sections 10.6, 10.8, and A.3.3.
Security Considerations Security Considerations
All OSPF protocol exchanges are authenticated. OSPF supports All OSPF protocol exchanges are authenticated. OSPF supports
multiple types of authentication; the type of authentication in use multiple types of authentication; the type of authentication in use
can be configured on a per network segment basis. One of OSPF's can be configured on a per network segment basis. One of OSPF's
authentication types, namely the Cryptographic authentication authentication types, namely the Cryptographic authentication
option, is believed to be secure against passive attacks and provide option, is believed to be secure against passive attacks and provide
significant protection against active attacks. When using the significant protection against active attacks. When using the
Cryptographic authentication option, each router appends a "message Cryptographic authentication option, each router appends a "message
digest" to its transmitted OSPF packets. Receivers then use the digest" to its transmitted OSPF packets. Receivers then use the
skipping to change at page 225, line 43 skipping to change at page 225, line 43
John Moy John Moy
Cascade Communications Corp. Cascade Communications Corp.
5 Carlisle Road 5 Carlisle Road
Westford, MA 01886 Westford, MA 01886
Phone: 508-952-1367 Phone: 508-952-1367
Fax: 508-692-9214 Fax: 508-692-9214
Email: jmoy@casc.com Email: jmoy@casc.com
This document expires in March 1997. This document expires in July 1997.
 End of changes. 

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/