OSPF routers must first discover each other before they can exchange their topological databases. Once each router has the complete topological database, it can use the SPF algorithm to compute the shortest path to every network. This section focuses on neighbor discovery and the exchange of topological databases.
Let’s begin at the beginning.
OSPF
packets are encapsulated directly in IP with the protocol field set
to 89. The destination IP address in OSPF depends on the network
type. OSPF uses two IP multicast addresses on broadcast and
point-to-point networks: 225.0.0.5 for all OSPF
routers and 224.0.0.6 for all DR/BDR (designated
router/backup designated router) routers. Using IP multicast
addresses is more efficient than using broadcast addresses. If
broadcast addresses are used, all attached devices must receive the
broadcast packet, unwrap it, and then discard the contents if they
are not running OSPF. NBMA networks and virtual links use unicast
addresses because they do not support multicast addresses.
Following the IP header is the OSPF header (see Figure 6-5). The OSPF header is common to all types of OSPF packets. The following list defines the format of the OSPF header and the five types of OSPF packets:
- Version
The OSPF version in use. The current version number is 2.
- Type
There are five types of OSPF packets:
- Type 1
Hello packets, described in the next section.
- Type 2
Database description packets, described later under Section 6.4.5.
- Type 3
Link state requests, described in Section 6.4.5.
- Type 4
Link state updates, described in Section 6.4.5.
- Type 5
Link state acknowledgments, described in Section 6.4.5.
- Packet length
The length of the OSPF packet, including the header.
- Router ID
The router ID of the router originating the OSPF packet.
- Area ID
The area ID of the network on which this packet is being sent.
- Checksum
The checksum for the entire packet, including the header.
- Au type
The type of authentication scheme in use. The possible values for this field are:
- 0
No authentication
- 1
Clear-text password authentication
- 2
MD5 checksum
- Authentication data
The authentication data.
Every router generates OSPF hello packets on every OSPF-enabled interface. Hello packets are sent every 10 seconds on broadcast media and every 30 seconds on nonbroadcast media. Routers discover their neighbors by listening to hellos. The output of the command show ip ospf neighbor lists the neighbors that have been discovered.
Each hello packet contains the fields described in the following sections. The format of a hello packet is shown in Figure 6-6.
When the OSPF process first starts on a router (e.g., when the router is powered up) it attempts to establish a router ID. The router ID is the name or label that will be attached to the node representing the router in the SPF topology graph. If OSPF cannot establish a router ID, the OSPF process aborts.
How does a router choose its router ID? There are two situations to consider here:
If a router has one or more loopback interfaces, it chooses the highest IP address from the pool of loopback interfaces as its router ID. Loopback interfaces are always active.
If a router has no loopback interfaces, it chooses the highest IP address from any of its active interfaces as its router ID. If a router has no active interface with an IP address, it will not start the OSPF process.
The router ID is chosen when the OSPF process first starts: the addition or deletion of interfaces or addresses on a router after the router ID has been selected does not change the router ID. A new router ID is picked only when the router is restarted (or when the OSPF process is restarted).
So, for example, the router ID of NewYork can be checked as follows:
NewYork#sh ip ospf
Routing Process "ospf 10" with ID 172.16.251.1
Supports only single TOS(TOS0) routes
SPF schedule delay 5 secs, Hold time between two SPFs 10 secs
......In this example, the router ID was derived using the router’s highest IP address. It is usually preferable to configure loopback interfaces to assign predictable router IDs to OSPF routers (since a loopback interface is a virtual interface and will not go down, as a physical interface would). The router ID must be unique within the topology database.
The configuration on NewYork may be modified as follows:
hostname NewYork ! interface Loopback0 ip address 192.168.1.1 255.255.255.255 ...
After NewYork is rebooted, its router ID will change as follows:
NewYork#sh ip ospf Routing Process "ospf 10" with ID 192.168.1.1 ...
Since the router ID is critical to the OSPF process, it is important for the network engineer to maintain a table of all router IDs.
Note the following points:
Since the router ID is needed only to represent the router in the SPF graph, it is not required that OSPF advertise the router ID. However, if the router ID is advertised, it will be represented as a stub link in a router LSA.
A mask of
255.255.255.255may be chosen for the loopback interface to conserve on network addresses, as in the earlier example.If the router ID is not advertised, any unique address can be used to represent the router ID -- the use of nonreserved IP addresses will not cause any routing-table conflicts.
The duration between hello packets. The default value of hello-interval is 10 seconds on most interfaces.
The hello-interval can be modified with the following command in interface configuration mode:
ip ospf hello-interval secondsOSPF defines several optional capabilities that a router may or may not support. The options field is one octet long, as shown in Figure 6-7.
Routers that support demand circuits set the DC bit; NSSA support is signified using the N bit. The E bit signifies that the router accepts external LSAs -- stub routers turn off this bit. The T bit signifies the support of multiple types of service.
A router with a higher priority takes precedence in the DR election algorithm. A value of makes the router ineligible for DR/BDR election. The default value of this field is 1.
If no hello packets are received for the duration of the dead-interval, the neighbor is declared dead. This value can be altered with the following command in interface configuration mode:
ip ospf dead-interval valueThe designated router for multi-access
networks. This field is set to 0.0.0.0 if no DR
has been elected on the network.
The IP address of the backup designated
router’s interface on this network.This field is set to 0.0.0.0 if no BDR
has been elected on the network.
The neighbor router ID list is the list of neighboring routers from which this router has received hellos within the last dead-interval seconds. Before a router lists its neighbor in its hello packet, the two routers must agree on the following: area ID, authentication mechanism, network mask, hello-interval, router dead-interval, and options fields. If these values match, the routers become neighbors and start listing each other in their hello packets.
The following output shows NewYork’s neighbors:
NewYork#show ip ospf neighbor Neighbor ID Pri State Dead Time Address Interface 192.168.1.2 1FULL/- 00:00:31 172.16.250.2 Serial0 192.168.1.3 1FULL/- 00:00:32 172.16.251.2 Serial1
Note that the state of NewYork’s relationship with both neighbors is “Full,” implying that the neighbors have exchanged LS databases to become adjacent. Under normal, stable conditions, the state of each neighbor relationship should be “2-way” or “Full.” “2-way” implies that the neighbors have seen each other’s hello packets but have not exchanged LSAs. In the process of maturing into a “Full” relationship, neighbors transition through the states “Exstart,” “Exchange,” and “Loading,” indicating that neighbors have seen each other’s hello packets and are attempting to exchange their LS databases. These are transitory states, all being well.
Then there are the problem states. “Down” indicates that a hello packet has not been received from the neighbor in the last router dead-interval. “Attempt” applies to NBMA networks and indicates that a hello has not yet been received from the neighbor. “Init” implies that a hello was received from the neighbor but its neighbor router ID list did not include the router ID of this router.
Consider n routers on a broadcast network (such as Ethernet). If a router exchanged its topological database with every other router on the network, (n x (n - 1)) / 2 adjacencies would be formed on the segment. This would create a lot of OSPF overhead traffic. OSPF solves this problem by electing a designated router (DR) and a backup designated router (BDR) on each broadcast network. Each router on a broadcast network establishes an adjacency with only the DR and the BDR. The DR and the BDR flood this topology information to all other routers on the segment.
DR/BDR election can be described in the following steps. Remember that the DR/BDR election process occurs on every multi-access network (not router). A router may be the DR on one interface but not another.
The following description assumes that a router R has just been turned up on a multi-access network:
On becoming active on a multi-access network, the OSPF process on router R begins receiving hellos from neighbors on its interface to the multi-access network. If the hellos indicate that there already are a DR and a BDR, the DR/BDR election process is terminated (even if R’s OSPF priority is higher than the current DR/BDR priority).
If hellos from neighbors indicate that there is no active BDR on the network, the router with the highest priority is elected the BDR. If the highest priority is shared by more than one router, the router with the highest router ID wins.
If there is no active DR on the network, the BDR is promoted to DR.
The following can be stated as corollaries of the above rules:
If a DR and BDR have already been elected, bringing up a new router (even with a higher priority) will not alter the identities of the DR/BDR.
If there is only one DR-eligible router on a multi-access network, that router will become the DR.
If there are only two DR-elegible routers on a multi-access network, one will be the DR and the other, the BDR.
A router with a higher priority takes precedence during DR election. A priority value of indicates that the router is ineligible for DR election. The default priority value is 1. Routers with low memory and CPU resources should be made ineligible for DR election.
The router interface priority may be modified with the following command in interface configuration mode:
ip ospf priority numberwhere number is between 0 and 255.
The state of an OSPF interface (including the result of the DR/BDR election process) can be seen as output of the show ip ospf interface command:
NewYork#sh ip ospf interface
Ethernet0 is up, line protocol is up
Internet Address 172.16.1.1/24, Area 0
Process ID 10, Router ID 172.16.251.1, Network Type BROADCAST, Cost: 10
9 Transmit Delay is 1 sec, State DR, Priority 1
Designated Router (ID) 172.16.251.1, Interface address 172.16.1.1
10 No backup designated router on this network
Timer intervals configured, Hello 10, Dead 40, Wait 40, Retransmit 5
Hello due in 00:00:02
11 Neighbor Count is 0, Adjacent neighbor count is 0
Suppress hello for 0 neighbor(s)
...Note that NewYork is the DR on Ethernet0. Since there is no other router on this network, there is no BDR (line 10) and the router has not established any adjacencies (line 11).
The state of an interface can have one of the following values:
- Down
The interface state is down as indicated by lower-level protocols, and no OSPF traffic has been sent or received yet.
- Loopback
The interface is looped and will be advertised in LSAs as a host route.
- Point-to-point
The interface is up and is recognized as a serial interface or a virtual link. After entering the point-to-point state, the neighbors will attempt to establish adjacency.
- Waiting
This state applies only to broadcast/NBMA networks on which the router is attempting to identify the DR/BDR.
- DR
This router is the DR on the attached network.
- Backup
This router is the BDR on the attached network.
- DRother
This router is neither the DR nor the BDR on the attached network. The router will form adjacencies with the DR and BDR (if they exist).
As an example, the state of NewYork’s interface to Chicago is point-to-point (line 12) and NewYork and Chicago have established adjacency (lines 13 and 14):
NewYork#sh ip ospf interface
...
Serial0 is up, line protocol is up
Internet Address 172.16.250.1/24, Area 0
Process ID 10, Router ID 172.16.251.1, Network Type POINT_TO_POINT, Cost: 64
12 Transmit Delay is 1 sec, State POINT_TO_POINT,
Timer intervals configured, Hello 10, Dead 40, Wait 40, Retransmit 5
Hello due in 00:00:01
13 Neighbor Count is 1, Adjacent neighbor count is 1
14 Adjacent with neighbor 69.1.1.1
Suppress hello for 0 neighbor(s)Not all neighbors establish adjacency. Neighbors may stay at “2-way” or enter into a “Full” relationship, depending on the type of network, as follows:
- Point-to-point networks
Routers on point-to-point networks always establish adjacency.
- Broadcast networks
Routers on broadcast networks establish adjacency only with the DR and the BDR, maintaining a 2-way relationship with the other routers on the network.
- Non-broadcast multi-access (NBMA) networks
Routers on NBMA networks establish adjacency only with the DR and the BDR.
- Virtual links
Routers on virtual links always establish adjacency.
The database description (DD) packet is used to describe the contents of the LS database to a peer OSPF router. Only LSA headers are sent in DD packets; the peer router responds by sending its own LSA headers in DD packets.
The LSA header (Figure 6-8) uniquely identifies a piece of the OSPF network topology. The key fields in the LSA header are the advertising router , LS type , and link state ID . The advertising router is the router ID of the originator of the LSA. The LS type identifies the type of the LSA that follows. The link state ID depends on the LS type, as shown in Table 6-3.
Table 6-3. LS type and link state ID
|
LS type |
Link state ID |
|---|---|
|
1 (router LSA) |
Router ID of the originator of the LSA |
|
2 (network LSA) |
IP address of the DR’s interface to the multi-access network |
|
3 (summary LSA) |
IP address of the destination network |
|
4 (ASBR summary LSA) |
Router ID of the ASBR |
|
5 (external LSA) |
IP address of the destination network |
Several copies of an LSA may be circulating in a network. The LS sequence number,a signed 32-bit integer, helps identify the most recent LSA. The first instance of an LSA record contains a sequence number field of 0x80000001. Each new instance of the LSA contains a sequence number that is one higher. The maximum sequence number is 0x7fffffff, after which the sequence numbers are recycled. The sequence number helps identify the most recent instance of an LSA.
Upon receiving LSA headers in DD packets, both routers check to see if this piece of the OSPF topology is already contained in their LS databases. In this process, the advertising router, LS type, and link state ID fields (from the LSA header) are compared against the router’s LS database. If no matching records are found or if a matching record is found with a lower sequence number, the complete LSA is requested using the link state request packet. The LS request packet contains the LSA header to help identify the record being sought.
In response to a link state request, a router issues a link state update containing the LSA. The LSA completely describes the piece of OSPF topology in question. LS updates are issued (a) in response to an LS request, as just described; (b) because of a change in the state of the link; and (c) every 30 minutes, with a new sequence number and the age field set to 0.
All LS updates are acknowledged in link state acknowledgment packets (see Figure 6-9).
Figure 6-9. Database description, link state request, link state update, and link state acknowledgment packets
There are six types of LSA records, each representing a different piece of the network topology. We’ll use TraderMary’s network with a French extension (Figure 6-10) to take a closer look at the various LSA types.
TraderMary’s network in New York is configured as follows. NewYork2 is an ABR with a serial link in area 1 to router Paris (line 15).
hostname NewYork2
!
interface Loopback0
ip address 192.168.1.4 255.255.255.0
!
interface Ethernet0
ip address 172.16.1.2 255.255.255.0
ip pim sparse-mode
!
interface Serial1
description Paris link
ip address 10.0.1.2 255.255.255.0
bandwidth 56
!
router ospf 10
network 172.16.0.0 0.0.255.255 area 0
15 network 10.0.0.0 0.255.255.255 area 1 Paris is an ASBR redistributing RIP routes from a legacy network into OSPF (line 16):
hostname Paris
!
interface Loopback0
ip address 192.168.1.5 255.255.255.255
!
interface Ethernet0
ip address 10.0.2.1 255.255.255.0
!
interface Serial1
description link to NewYork2
ip address 10.0.1.1 255.255.255.0
!
router ospf 10
16 redistribute rip metric 100 subnets
network 10.0.0.0 0.255.255.255 area 1
!
router rip
network 10.0.0.0The 10.0.0.0
subnets -- 10.0.1.0,
10.0.2.0, and
10.0.3.0 -- are known to both the OSPF and RIP
processes on router Paris.
Let’s see how NewYork learns
these subnets. Here is
NewYork’s routing table:
NewYork#sh ip route
...
10.0.0.0/24 is subnetted, 3 subnets
17 O IA 10.0.2.0 [110/1805] via 172.16.1.2, 00:07:45, Ethernet0
18 O E2 10.0.3.0 [110/100] via 172.16.1.2, 00:07:46, Ethernet0
19 O IA 10.0.1.0 [110/1795] via 172.16.1.2, 00:07:46, Ethernet0
192.168.1.0/32 is subnetted, 1 subnets
C 192.168.1.1 is directly connected, Loopback0
172.16.0.0/24 is subnetted, 6 subnets
O 172.16.252.0 [110/128] via 172.16.250.2, 00:07:46, Serial0
C 172.16.250.0 is directly connected, Serial0
C 172.16.251.0 is directly connected, Serial1
O 172.16.50.0 [110/74] via 172.16.250.2, 00:07:46, Serial0
C 172.16.1.0 is directly connected, Ethernet0
O 172.16.100.0 [110/192] via 172.16.250.2, 00:07:46, Serial0Note that the routing table shows that NewYork
learns 10.0.3.0 as an external route whereas
10.0.1.0 and 10.0.2.0 are
learned as inter-area routes (lines 17-19) -- this is because
inter-area routes are preferred over external routes. The OSPF order
of route preference, from most preferred to least preferred, is as
follows: intra-area, inter-area, type 1 external, type 2 external.
A router LSA describes the advertising router’s directly connected links. Routers Chicago, Ames, NewYork, and NewYork2 advertise router LSAs that are flooded throughout area 0. NewYork’s LS database holds router LSAs from all these routers, but for the sake of brevity I’ll show only the contents of the LSA from NewYork2.
The number of links (as in line 20 in the upcoming code block) described in the LSA is 1. Although NewYork2 has two directly connected links -- an Ethernet segment and a serial link -- only the Ethernet segment is described in the LSA to NewYork. This is because the serial link is in area 1 and router LSAs do not cross OSPF area boundaries.
The link described is a transit network (line 21), implying that there are multiple routers on the link. Other link types are point-to-point (for serial links), stub network (for a network with only one router), and virtual link (for OSPF virtual links).
The value of the link ID field depends on the type of link being described, as shown in Table 6-4.
Table 6-4. Link type and link ID
|
Link type |
Link ID |
|---|---|
|
Point-to-point |
Neighbor’s router ID |
|
Transit network |
DR’s IP address on network |
|
Stub network |
IP network number or subnet number |
|
Virtual link |
Neighbor’s router ID |
In our example, the DR is NewYork, so the link ID (in line 22) contains NewYork’s IP address.
The contents of the link data field also depend on the link type, as shown in Table 6-5.
Table 6-5. Link type and link data
|
Link type |
Link data |
|---|---|
|
Point-to-point |
IP address of network interface |
|
Transit network |
IP address of network interface |
|
Stub network |
IP network number or subnet number |
|
Virtual link |
MIB II ifIndex for the router’s interface |
In our example, the link data field (in line 23) specifies the IP address of NewYork2:
NewYork#sh ip ospf database router
OSPF Router with ID (192.168.1.1) (Process ID 10)
Routing Bit Set on this LSA
LS age: 209
Options: (No TOS-capability, DC)
LS Type: Router Links
Link State ID: 192.168.1.4
Advertising Router: 192.168.1.4
LS Seq Number: 800000FF
Checksum: 0x2BA1
Length: 36
Area Border Router
AS Boundary Router
20 Number of Links: 1
21 Link connected to: a Transit Network
22 (Link ID) Designated Router address: 172.16.1.1
23 (Link Data) Router Interface address: 172.16.1.2
Number of TOS metrics: 0
TOS 0 Metrics: 10A network LSA describes broadcast/NBMA networks. The network LSA is originated by the DR and describes all attached routers.
The LSA in the following example is self-originated, as seen in the advertising router field (line 24), which shows NewYork’s own router ID. The network LSA describes the mask on the multi-access network (line 25) and the IP addresses of the routers on the multi-access network (lines 26 and 27).
NewYork#sh ip ospf database network
OSPF Router with ID (192.168.1.1) (Process ID 10)
Net Link States (Area 0)
Routing Bit Set on this LSA
LS age: 1728
Options: (No TOS-capability, DC)
LS Type: Network Links
Link State ID: 172.16.1.1 (address of Designated Router)
24 Advertising Router: 192.168.1.1
LS Seq Number: 800000F4
Checksum: 0x172B
Length: 32
25 Network Mask: /24
26 Attached Router: 192.168.1.1
27 Attached Router: 192.168.1.4A summary LSA is advertised by an ABR and describes inter-area routes.
The summary LSAs in the following example are originated by
NewYork2 (192.168.1.4) and
describe routes to 10.0.1.0 and
10.0.2.0, respectively. The link state ID
describes the summary network number (lines 28 and 31). Note that
each LSA describes just one summary network number.
NewYork#sh ip ospf database summary
OSPF Router with ID (192.168.1.1) (Process ID 10)
Summary Net Link States (Area 0)
Routing Bit Set on this LSA
LS age: 214
Options: (No TOS-capability, DC)
LS Type: Summary Links(Network)
28 Link State ID: 10.0.1.0 (summary Network Number)
29 Advertising Router: 192.168.1.4
LS Seq Number: 80000062
Checksum: 0x85A
Length: 28
30 Network Mask: /24
TOS: 0 Metric: 1785
Routing Bit Set on this LSA
LS age: 214
Options: (No TOS-capability, DC)
LS Type: Summary Links(Network)
31 Link State ID: 10.0.2.0 (summary Network Number)
32 Advertising Router: 192.168.1.4
LS Seq Number: 80000061
Checksum: 0x62F5
Length: 28
33 Network Mask: /24
TOS: 0 Metric: 1795An ASBR summary LSA describes the route to the ASBR. The mask associated with a type 4 LSA is 32 bits long because the route advertised is to a host -- the host being the ASBR. ASBR summary LSAs are originated by ABRs.
The link state ID (line 34) in this example describes the router ID of Paris, which is the ASBR redistributing RIP into OSPF. The advertising router is the ABR -- NewYork2 (line 35).
NewYork#sh ip ospf database asbr-summary
OSPF Router with ID (192.168.1.1) (Process ID 10)
Summary ASB Link States (Area 0)
Routing Bit Set on this LSA
LS age: 115
Options: (No TOS-capability, DC)
LS Type: Summary Links(AS Boundary Router)
34 Link State ID: 192.168.1.5 (AS Boundary Router address)
35 Advertising Router: 192.168.1.4
LS Seq Number: 80000061
Checksum: 0x9A63
Length: 28
Network Mask: /0
TOS: 0 Metric: 1785External LSAs originate at ASBRs and describe routes external to the OSPF process. External LSAs are flooded throughout the OSPF network, with the exception of stub areas.
Network 10.0.1.0 is learned via RIP from
NewYork2, which floods an external LSA with a
link state ID of 10.0.1.0. Interestingly,
10.0.1.0 is also known as an inter-area route (see
the section Section 6.4.5.3). Router
NewYork prefers the IA route (see line 19) but
will keep the external LSA in its topological database. The
advertising router (line 37) is Paris, the ASBR,
which redistributes RIP into OSPF. The forwarding address (in line
39) is 0.0.0.0, indicating that the destination
for 10.0.1.0 is the ASBR. The LSA (in line 40)
specifies an external route tag of 0, which indicates a type 1
external route; a value of 1 would indicate a type 2 external route.
NewYork#sh ip ospf database external
OSPF Router with ID (192.168.1.1) (Process ID 10)
Type-5 AS External Link States
LS age: 875
Options: (No TOS-capability, No DC)
LS Type: AS External Link
36 Link State ID: 10.0.1.0 (External Network Number )
37 Advertising Router: 192.168.1.5
LS Seq Number: 80000060
Checksum: 0x6F27
Length: 36
38 Network Mask: /24
Metric Type: 2 (Larger than any link state path)
TOS: 0
Metric: 100
39 Forward Address: 0.0.0.0
40 External Route Tag: 0
...Note that NewYork’s external
database contains two other LSAs -- with link state IDs of
10.0.2.0 and
10.0.3.0 -- which were not shown here.
NSSA external LSAs describe routes external to the OSPF process. However, unlike type 5 external LSAs, NSSA external LSAs are flooded only within the NSSA.
There are no type 7 LSAs in this network. In fact, there aren’t even any NSSAs in this network:
NewYork#sh ip ospf database nssa-external
OSPF Router with ID (192.168.1.1) (Process ID 10)The format of the NSSA external LSA is identical to that of the AS external LSA, except for the forwarding address field. The forwarding address field in an NSSA external LSA always indicates the address to which traffic should be forwarded.
LSAs are generated every 30 minutes, or sooner if there is a change in the state of a link. LSAs are exchanged between routers that have established adjacency, as was described earlier.
The rules for the flooding of LSAs are governed by the hierarchical structure of OSPF, as given in Table 6-6.
Table 6-6. Rules for the flooding of LSAs
|
LSA type |
Originating router |
Area in which flooded |
|---|---|---|
|
Router LSA (type 1) |
Every router |
Router’s local area. |
|
Network LSA (type 2) |
DR |
Router’s local area. |
|
Summary LSA (type 3) |
ABR |
Nonlocal area. |
|
ASBR summary LSA (type 4) |
ASBR |
All areas except stub area, totally stubby area, or NSSA. |
|
External LSA (type 5) |
ASBR |
All areas except stub area, totally stubby area, or NSSA. |
|
NSSA external LSA (type 7) |
ASBR |
Router’s local area. NSSA external LSA may be forwarded by ABR as a type 5 LSA. |