The OSPF protocol is a link-state routing protocol, that is, each router maintains a link-state database (LSDB) that comprises link-state information collected from all participating OSPF routers within an AS. Link-state information (or just link-state) refers to a router’s local view of its immediate network topology, which includes the router’s operational interfaces, the cost of sending traffic out on an interface and the address information of its attached networks. Each router floods its link-state throughout the AS resulting in each participating OSPF router having an identical LSDB (we will revisit this sentence in Section 1.6.2). In essence, this LSDB represents the complete network topology of the entire AS. As we will explain in Section 1.6.3, this LSDB may also contain information about networks that are outside the AS, and may include routing information that is derived from other routing protocols such as BGP or RIPng.
In RIPng, each router computes its routing table based on the computation results of other routers. Unlike RIPng, each OSPF router computes its routing table to reachable nodes and networks from its LSDB independently. Entries of this LSDB represent a directed graph. Route computation involves the construction of the shortest path tree to each destination out of this graph. This shortest path tree represents the most efficient routing paths to all reachable destinations.
OSPF can operate over various types of networks. In the following sections we will focus our discussions around broadcast-capable networks so that we can concentrate on the more important concepts.
Router Adjacency and LSDB Synchronization
The key to the correct link-state protocol operation is the reliable timely synchronization of the LSDB. A router newly becoming operational must acquire a large part of its LSDB from another router that has been in operation for a period of time. OSPF introduces the concept of adjacency that is similar to the BGP peer concept. Two routers may be neighbors but they may not be adjacent. An OSPF router exchanges routing information (thus LSDB synchronization) only with its adjacent routers.
When N routers are present on a subnetwork, if a router were to form adjacency with all of its neighbors and synchronize its LSDB with these neighbors, the number of LSDB exchanges is in the order of N2 and may cause a large amount of routing traffic and overhead. OSPF introduces the concepts of designated router (DR) and backup designated router (BDR) to solve this problem. A DR and a BDR are elected dynamically on each subnetwork. Instead of forming adjacency with every other neighbor, all routers form adjacencies to just the DR and the BDR. Since each router establishes adjacency to only the DR and the BDR, LSDB synchronization would be performed with just the DR resulting in both routing traffic reduction and time reduction. Routing update from one router is propagated to all other neighbors through the DR.
An OSPF router discovers its neighbors and then subsequently forms adjacency with the DR and BDR through the OSPF Hello protocol. The Hello protocol also allows an OSPF router to verify bidirectional connectivity with its neighbors. In addition, the DR and BDR are elected through the Hello protocol. BDR provides protocol reliability because when the BDR detects that the DR is unavailable through the Hello protocol, the BDR becomes the DR and a new BDR is chosen.
The LSDB synchronization begins with each router sending database description packets to its adjacent neighbor. Each database description packet describes a list of link state advertisements (LSA) that exist in the LSDB of the sending router. The receiving router checks these LSAs against its own LSDB, and remembers those LSAs that are either missing from its LSDB or are more recent than those in its LSDB. Subsequently the receiving router requests those specific LSAs from its adjacent neighbor. The LSDB synchronization completes when both adjacent routers have sent the database description packets to each other and have received from each other their requested LSAs.
Two link-local scope multicast addresses are assigned to OSPFv3. The ff02::5 multicast address is known as the AllSPFRouters address. All OSPFv3 routers must join this multicast group and listen to packets for this multicast group. The OSPFv3 Hello packets are sent to this address. The ff02::6 multicast address is known as the AllDRouters address. The DR and BDR must join this multicast group and listen to packets for this multicast group. The use of these multicast groups depends on the protocol packet type and the router that is sending the packet. The use of the ALLSPFRouters and the AllDRouters addresses is similar to that of IPv4. The reader should consult [RFC2328] for more details.
The following points summarize the key characteristics of the OSPF protocol.
• The link-state information originated by one router is not modified by any of the receiving routers.
• The link-state information is flooded, unmodified, throughout the routing domain.
• Distribution of routing information is reliable because each LSA is explicitly acknowledged. We do not cover this topic in this topic. The reader is encouraged to consult [RFC2328] for details.
• Dynamic neighboring router discovery can be done by the Hello protocol.
• A router sends the link-state information to its adjacent routers.
• Each router maintains an identical database that contains all of the link-state information that has been advertised by all of the participating routers.
• The routing algorithm can compute loop-free paths.
• Route computation is independently performed at each router; however, since loop avoidance relies on the synchronized shortest paths, route selection decision is not as flexible as BGP4+.
Area Types and Router Classification
The amount of route information exchanged over OSPF can be reduced with the concept of areas. An OSPF area is a collection of subnetworks. The reachability information distributed by the responsible router for the area is about the area as a whole, not about the individual subnetwork. Thus an area reduces routing traffic and the amount of routing information flooded in the AS. Besides route aggregation, an area offers routing protection because topological change taking place outside the area does not affect shortest path tree calculation in an area. An area may also restrict the flow of external routes into the area depending on the area type. OSPF areas can be normal areas, stub areas, and not-so-stubby areas (NSSA). Routing within an area is called intra-area routing while routing between areas is called inter-area routing.
A router can now be classified as internal router, area border router (ABR), or AS boundary router (ASBR). A router with attached networks that all belong to the same area is called an internal router. A router that is attached to multiple areas is called an area border router. An ABR maintains a separate LSDB for each attached area. In Section 1.6 we indicated that each router would have an identical LSDB. To be more precise, each router in an area would have identical LSDBs for that area. A router that exchanges routing information with routers in other ASs2 and distributes the external routing information in the local AS is called an AS boundary router.
Figure 1-26 illustrates the area concept and the situations of the various types of routers.
As shown in the figure, routers R1, R2, R3, R4 and R6 are internal routers. Routers R5, R7, and R9 are ABRs. Routers R8 and R9 are ASBRs. Router R5 maintains one LSDB for Area-1 and one LSDB for Area-2. All of the routers in Area-1, including R5 have the same LSDB about Area-1. Similarly routers R5, R6 and R9 have the same LSDB about Area-2.
Area 0 is a special area called the backbone area. Routing information about other areas are distributed through the backbone area. In Figure 1-26, routers R5, R7, R8 and R9 are connected to the backbone area and share a common network. Virtual links are used to connect these routers if they are physically separate. In this case a virtual link is similar to an unnumbered point-to-point link. Virtual links are always part of the backbone. Although these routers may be physically separate, they must share a common area. This common area is called the transit area because the virtual link is connected across this area. A related concept is the transit network. Transit network is defined as a network on which pass-through traffic can flow across.
All link state information, including routing information that is external to an AS, is flooded into a normal area. AS external routes are not flooded into the stub areas. Virtual links cannot be configured through a stub area. Details of an NSSA are beyond the scope of this topic and are omitted.
Link State Advertisement and LSA Types
An OSPF router sends the link-state information through a set of Link State Advertisements (LSAs), contained in Link State Update packets. OSPF deploys a reliable flooding mechanism, that is, each LSA is explicitly acknowledged by a Link State Acknowledgment packet.
FIGURE 1-10
OSPFv3 is described in [RFC2740] and defines the following types of LSA:
Router-LSA The Router-LSA describes the advertising router’s interfaces that are attached to the area. The state and cost of each interface is described by the Router-LSA. Each router originates a set of Router-LSAs for its interfaces. The Router-LSA is flooded throughout the area.
Network-LSA The Network-LSA is originated by a link’s DR, which describes all of the attached routers to that link. The Network-LSA is flooded throughout the area.
Inter-Area-Prefix-LSA The Inter-Area-Prefix-LSA is originated by the ABR, which describes the reachable IPv6 prefixes that are part of other areas. The Inter-Area-Prefix-LSA is flooded throughout the area.
Inter-Area-Router-LSA The Inter-Area-Router-LSA is originated by an ABR, which describes the reachable routers of other areas. The Inter-Area-Router-LSA is flooded throughout the area.
AS-External-LSA The AS-External-LSA is originated by an ASBR, which describes the reachable prefixes that belong to other ASs. The AS-External-LSAs are flooded throughout the entire AS (except certain stub areas).
TABLE 1-4
|
LSA type |
Flooding scope |
Originator |
IPv4 equivalent |
|
Router-LSA |
area |
each router |
Router-LSA |
|
Network-LSA |
area |
DR |
Network-LSA |
|
Inter-Area-Prefix-LSA |
area |
ABR |
Type-3 summary-LSA |
|
Inter-Area-Router-LSA |
area |
ABR |
Type-4 summary-LSA |
|
AS-external-LSA |
AS |
ASBR |
AS-external-LSA |
|
Link-LSA |
link |
each router |
(none) |
|
Intra-Area-Prefix-LSA |
area |
each router |
(none) |
Link-LSA The Link-LSA is generated by each router attached to that link, which conveys the following information to other routers attached to that same link:
• the link-local address of the advertising router on that link
• the prefixes that are assigned to that link
• the options to be set in the Network-LSA to be generated by the DR of that link
The Link-LSA is flooded on that link only.
Intra-Area-Prefix-LSA The Intra-Area-Prefix-LSA is originated by each router to describe the IPv6 address prefixes that are assigned to the router. The Intra-Area-Prefix-LSA is also sent by each router to describe the IPv6 address prefixes that are associated with an attached stub network segment or a transmit network segment. The Intra-Area-Prefix-LSA is flooded throughout the area.
The flooding scope of each type of LSA is summarized in Table 1-4.
LSA Formats
In this section we will describe the formats of the various types of LSAs. We first explain the detail of the Options that are part of the Link-LSAs, Network-LSAs, Router-LSAs, and Inter-Area-Router-LSAs, which indicate router capabilities such as whether an advertising OSPF router is capable of forwarding IPv6 transit traffic. We then discuss the detail of the Prefix Options field that is part of the Inter-Area-Prefix-LSA, the Intra-Area-Prefix-LSA, the AS-External-LSA and the Link-LSA. The LS Type field is another field with subcomponents and its structure is explained. Then the LSA Header is described followed by the descriptions on the individual LSAs.
Options
Figure 1-27 shows the format of the Options field.
The most relevant bits for this topic are the R-bit and the V6-bit. The R-bit indicates whether an advertising router is an active router or not. The router will participate in the routing protocol but will not forward transit traffic if the R-bit is cleared. In this case routes that transit through the non-active router node cannot be computed. Otherwise the router is an active router that both participates in the routing protocol and forwards the transit traffic.
FIGURE 1-27
FIGURE 1-28
The V6-bit must be set in order for the router and its link to be included in the calculation. Both the R-bit and the V6-bit must be set in order for IPv6 transit packets to be forwarded through a particular router.
Prefix Options
Figure 1-28 shows the format of the Prefix Options field.
NU This bit is called the no unicast capability bit. When this bit is set, the given prefix should be excluded from IPv6 unicast calculation; otherwise the prefix should be included.
LA This bit is called the local address capability bit. The advertised prefix is an IPv6 address of the advertising router if this bit is set.
MC This bit is called the multicast capability bit. When this bit is set, the given prefix should be included in the IPv6 multicast routing calculation; otherwise the prefix should be excluded.
P This bit is called the propagate bit. The advertised prefix should be readvertised at the NSSA area border.
LS Type
Figure 1-29 shows the format of the LS Type field.
U This bit indicates how a router should handle LSAs with an unrecognized LSA function code. When this bit is 0, the LSAs are given link-local flooding scope. When this bit is set to 1, the LSAs are stored and flooded as if the function code is recognized.
FIGURE 1-29
TABLE 1-5
|
Function code |
LSA type |
Description |
|
1 |
0×2001 |
Router LSA |
|
2 |
0×2002 |
Network LSA |
|
3 |
0×2003 |
Inter-Area-Prefix LSA |
|
4 |
0×2004 |
Inter-Area-Router LSA |
|
5 |
0×4005 |
AS-External LSA |
|
6 |
0×2006 |
Group-membership LSA (not discussed) |
|
7 |
0×2007 |
Type-7 LSA (not discussed) |
|
8 |
0×0008 |
Link LSA |
|
9 |
0×2009 |
Intra-Area-Prefix LSA |
S2 S1 These two bits determine the flooding scope of the given LSA. The values of these two bits and the flood scope these bits represent are as follows:
0 0 link-local
0 1 area 10 AS
1 1 Reserved
The remaining bits of the LS Type field belong to the LSA function code. Table 1-5 outlines the LSA function code and the final LSA type.
LSA Header
Figure 1-30 shows the format of the LSA header.
LS age This 16-bit field specifies the time in seconds since the LSA was originated. The LS age field allows a router to identify an expired LSA that needs to be removed from the routing domain.
LS type This 16-bit field identifies the LSA type. This field is divided into the bit definition given in Figure 1-29.
FIGURE 1-30
Link State ID The combination of this field, the LS Type and the Advertising Router uniquely identifies an LSA in the LSDB.
Advertising Router This field specifies the router ID of the advertising router. The router ID is assigned to the OSPF router and uniquely identifies the router within the AS. A typical value used for router ID is an IPv4 address of an interface attached to the router.
LS sequence number This is a 32-bit signed integer that is used to detect old and duplicated instances of an LSA.
LS checksum This field holds the Fletcher checksum of the entire LSA packet, which includes the LSA header but excludes the LS age field. The Fletcher checksum is documented in [RFC905].
Length This field specifies the length of the entire LSA packet including the LSA header.
