Section 8.3. OSPF for IPv6 (OSPFv3)

8.3. OSPF for IPv6 (OSPFv3)

OSPF for IPv6 modifies the existing OSPF for IPv4 to support IPv6. The fundamentals of OSPF for IPv4 remain unchanged. Some changes have been necessary to accommodate the increased address size of IPv6 and the changes in protocol semantics between IPv4 and IPv6. OSPF for IPv6 is defined in RFC 2740, which emphasizes the differences between OSPF for IPv4 and OSPF for IPv6. It contains a large number of references to the documentation of OSPF for IPv4, which makes it hard to read. This chapter tries to concatenate the two worlds to make the reading a little bit more comfortable. It starts with an overview of OSPF, including the area structure and external routes. After the overview, it opens up the protocol to get down to the implementation details: it starts with the OSPF message format, proceeds to the neighbor relationship, and finishes with the actual link state database and the calculation of the routing table.

8.3.1. Overview of OSPF for IPv6

OSPF for IPv4 (OSPFv2) is standardized in RFC 2328. In addition to this document, several extensions to OSPF have been defined. RFC 1584 describes IPv4 multicast extensions to OSPF. RFC 3101 (which used to be RFC 1587) adds not-so-stubby areas (NSSAs) to OSPF. RFC 2740 modifies OSPF to support the exchange of routing information for IPv6. OSPF for IPv6 has a new version number: version 3.

OSPF is classified as an IGP, which are used within autonomous systems. It was designed to overcome some of the limitations introduced by RIP, such as the small diameter, long convergence time, and a metric that does not reflect the characteristics of the network. In addition, OSPF handles a much larger routing table to accommodate large number of routes.

8.3.1.1. Differences between OSPF for IPv4 and OSPF for IPv6

Most of the concepts of OSPF for IPv4 have been retained; following is a brief overview of the changes:

Protocol processing per-link, not per-subnet

IPv6 connects interfaces to links. Multiple IP subnets can be assigned to a single link, and two nodes can talk directly over a single link even if they do not share a common IP subnet. OSPF for IPv6 runs per-link instead of per-subnet. The terms "network" and "subnet" used in OSPF for IPv4 should be replaced with the term "link," i.e., an OSPF interface now connects to a link instead of an IP subnet.

Removal of addressing semantics

IPv6 addresses are no longer present in OSPF packet headers. They are only allowed as payload information.

Router-LSA and Network-LSA (yes, they still exist) do not contain IPv6 addresses. OSPF Router ID, Area ID, and Link State ID remain at 32 bits, so they cannot take the value of an IPv6 address. Designated Routers (DRs) and Backup Designated Routers (BDRs) are now always identified by their Router ID and not their IP address.

Flooding scope

Each LSA type contains an explicit code to specify its flooding scope. This code is embedded in the LS type field. Three flooding scopes have been introduced: link-local, area, and AS.

Explicit support for multiple instances per link

Multiple OSPF protocol instances can now run over a single link. This allows for separate ASes, each running OSPF, to use a common link. Another use of this feature is to have a single link belong to multiple areas.

Use of link-local addresses

OSPF assumes that each interface has been assigned a link-local unicast address. All OSPF packets use the link-local address as the Source address. The routers learn the link-local addresses of all their neighbors and use these addresses as the next hop address. Packets sent on virtual links, however, must use either the global or local IP address as the source for OSPF packets.

RFC 2740 still uses the term "site-local address" instead of "local address." Site-local addresses have been deprecated in the meantime. For more information, refer to the sections in Chapter 3 about IPv6 addressing.

Authentication

Because OSPF for IPv6 runs over IPv6, it relies on the IP Authentication Header and the IP Encapsulating Security Payload to insure integrity and authentication of routing exchanges. The authentication of OSPF for IPv4 has been removed. One integrity check remains, which comes in the form of the checksum that is calculated over the entire OSPF packet.

OSPF packet format changes

See the section "Message Format of OSPF for IPv6."

LSA format changes

Type 3 (Summary Link) has been renamed Inter-Area-Prefix-LSA.

Type 4 (AS Summary Link) has been renamed Inter-Area-Router-LSA.

Two new LSAs carry IPv6 prefix information in their payload. Link-LSA (Type 8) carries the IPv6 address information of the local links, and Intra-Area-Prefix-LSA (Type 9) carries the IPv6 prefixes of the router and network links.

For other changes, such as Link State ID and the Options field, see the section "The Link State Database."

Handling unknown LSA types

Instead of simply discarding them, OSPF for IPv6 introduces a more flexible way of handling unknown LSA types. A new LSA handling bit has been added to the LS Type field to allow flooding of unknown LSA types.

Stub area support

The concept of stub areas has been retained in OSPF for IPv6. An additional rule specifies the flooding of unknown LSAs within the stub area.

8.3.1.2. Link state-based protocol

Each router maintains a database describing the link states within the autonomous system. This database is being built by exchanging Link State Advertisements (LSAs) between neighboring routers. Depending on its contents, an LSA is flooded to all routers in the autonomous system (AS flooding scope), all routers within the same area (area flooding scope), or simply to its neighbors. The flooding always occurs along a path of neighboring routers, so a stable neighbor relationship is extremely important for OSPF to work properly. The neighbor relationship is called adjacency . The exact process of forming an adjacency is described later in the section "Forming Adjacencies."

Each router originates router LSAs advertising the local state of its interfaces to all routers within the same area. Additional LSAs are originated to identify links with multiple routers (multi-access networks), IPv6 routes from other areas, or IPv6 routes external to the OSPF autonomous system. All LSA types and the flooding mechanism are described in the sections "The Link State Database" and "LSA Flooding," respectively. Each router puts the received LSA into its LSA database, called the Link-State Database (LSDB).

Using the LSDB as the input, each router runs the same algorithm to build a tree of least-cost paths (shortest-path-first tree [SPF tree]) to each route. The LSDB is like having a map of the network used to plot the shortest paths to each destination. The cost is described by a single dimensionless metric, which is configurable on each interface of the router. The metric assigned to the interface is usually inversely proportional to its line speed, i.e., higher bandwidth means lower cost. A common formula was to divide 10⁸ by the line speed in bits per second. This formula is out-dated, as interface speed today is in the range of 10⁹ (e.g., Gigabit Ethernet) or even 10¹⁰. Most vendors today apply a nonlinear formula. You can always choose and implement your own cost metrics according to corporate standards.

OSPF can put multiple equal-cost paths to the same route into the routing table. The algorithm for distributing traffic among these paths is at the discretion of the routing process itself, normally based on the source and destination IPv6 addresses. I discuss the process of building the SPF and its routing table in detail later in this chapter, in the section "The Link State Database."

8.3.1.3. OSPF areas and external routes

The LSDB can become quite large, and processing such a large database can be CPU- and memory-intensive because changes to the database affect every router in the AS. OSPF allows the AS to be partitioned into areas to reduce processing overhead. In addition, OSPF can import routes derived from external sources (e.g., RIP, BGP, and static routes) into OSPF.

8.3.2. OSPF Areas and External Routes

Within an autonomous system, routers can be grouped together to form areas. Each area is assigned a unique Area ID, a 32-bit integer typically noted as a dotted decimal number. It has no addressing significance other than uniquely identifying the area. An LSA with area flooding scope will never be flooded outside the area. Together, they form the area data structure, also known as the area LSDB. The Router-LSA and Network-LSA belong to this category. Routers and networks from one area are hidden in other areas. It is similar to splitting the map of the network into multiple maps, each of which represents the topology of one area. Each router within one area calculates the SPF tree to all routes within the same area. These routes are called intra-area routes. Routers with all interfaces belonging to a single area are called internal routers. To find paths to routes outside the area, "exit points" are provided in the form of area border routers (ABR). To provide connectivity between all areas, each area must always be directly attached to a single common area called the backbone area. This is achieved by the ABR having at least one interface in the backbone area and one interface in the local area. The ABR advertises all routes of the local area to the backbone area. In return, it advertises all the routes of the backbone area to the local area. This ensures that all routes are distributed within the AS. The backbone area collects and redistributes all routes from and to all areas.

Routing within the AS takes place at two levels. If the Source and Destination IP address of a packet belong to the same area, the packet is forwarded solely on information obtained from the area LSDB. This is called intra-area routing. If the Destination address is outside the area, the packet will have to be forwarded along the path to the ABR of the local area. The ABR knows all destinations and forwards the packet either across the backbone to the ABR of the destination area or to the backbone area. This is called inter-area routing.

The advantage of having areas is the reduction of processing overhead. Because the topology of each area is smaller than the entire AS, the calculation of the SPF tree takes less time. In addition, changes in the topology stay local, and only the routers in the local area need to recalculate the SPF tree. Routers in other areas are less affected because their area topology is not changed. Internal routers profit the most from splitting the AS into areas because their LSDB is much smaller.

8.3.2.1. The backbone area

The backbone area is a special area with an assigned Area ID of 0. The backbone area contains all ABRs of the autonomous system. If the AS is not split into areas, the backbone area is usually the one configured area. If the AS is split into areas, the backbone area is the collection of all routes from all nonbackbone areas. The backbone area must be contiguous: each router within the same area has at least one direct link to another router in the same area, and that link belongs to the area. However, with the introduction of virtual links, a backbone area doesn't have to be physically contiguous. A transit area can be used to create a tunnel (a virtual link) belonging to the backbone area. This will be further discussed later in the section "OSPF Areas and External Routes."

8.3.2.2. Nonbackbone areas

Nonbackbone areas are assigned unique Area IDs other than 0. They must be physically contiguous. Each nonbackbone area must have an ABR connected to the backbone using either a physical link or a virtual link. An ABR advertises all routes of the nonbackbone into the backbone area. In reverse, an ABR advertises all the routes known to the backbone area into the nonbackbone area. Normally, the ABR uses one LSA (called the Inter-Area-Prefix-LSA) for each route advertised. The ABR can be configured to summarize routes using a shorter IPv6 prefix representing some or all of the routes to be advertised. This reduces the number of advertisements, as well as memory and processing requirements. If you want to compress the number of routes in this way, it is very important to carefully plan the assignment of IPv6 prefixes within the area.

A nonbackbone area can have multiple ABRs. Figure 8-9 explains ABRs advertising Inter-Area-Prefix-LSAs.

Figure 8-9. OSPF areas and their routing updates

8.3.2.3. Virtual links

A virtual link is a logical link that tunnels backbone traffic through a nonbackbone area. It can be configured between two ABRs by using a common nonbackbone area called a transit area. A virtual link belongs to the backbone and can cross only a single transit area. The transit area must not be a stub area (more on stub area in the subsection below). A remote area without a physical interface to the backbone area can be connected to the backbone by using virtual links. Virtual links can also be used to create redundant connections to the backbone. OSPF considers a virtual link a point-to-point link. The shortest path between the ABRs through the transit area determines the actual endpoint addresses of the tunnel. These addresses must be global or local unicast IPv6 addresses. Figure 8-10 shows an example of virtual links.

Figure 8-10. Virtual link connecting a remote area

8.3.2.4. External routes

A router can learn about IPv6 routes from different sources, such as RIP, static entries, BGP, IS-IS, etc. Every route from a non-OSPF source is considered to be an OSPF external route and can be imported into OSPF. To import external routes into OSPF, a router must have at least one interface configured with OSPF and know about at least one non-OSPF network. This router is called an autonomous system border router (ASBR). External routes are imported using a single AS-External-LSA for each external route. Depending on the implementation, an ASBR can summarize a range of external routes to a single external LSA. Figure 8-11 explains how external routes are imported into OSPF.

Figure 8-11. External routes imported into OSPF

AS-External-LSAs must be flooded throughout the autonomous system. Any router within the AS forwards packets to external networks to the ASBR or to an optional forwarding address specified by the ASBR. Therefore, there must be an entry to the ASBR in the Area-LSDB, or the forwarding address must be in the local routing table. If the ASBR is not within the local area, the ABR is responsible for advertising the existence of the ASBR to the local area. This is done using an Inter-Area-Router-LSA. Figure 8-11 shows the usage of the Inter-Area-Router-LSA.

Metrics of external routes are not compatible with OSPF metrics. ASBRs advertise external routes using one of two types of metrics: external-1 and external-2 routes. External-1 routes are considered to be close to the ASBR. Routers within the AS add the OSPF cost to reach the ASBR or the advertised forwarding address to the metric of the external-1 route. External-2 routes are assumed to be further away from the ASBR. A metric larger than the cost of any intra-AS path will therefore be added to the metric of the external-2 route.

If the same route is advertised as an OSPF internal route as well as an external route, the path to the OSPF internal route is always chosen over the path to the external route. This can happen if there are multiple ASBRs connected to the same external network. One ASBR advertises an OSPF route to the external routing protocol, and the other ASBR imports the same route back to OSPF.

8.3.2.5. Stub areas

In short, a stub area is a zone free of AS-External-LSAs. These LSAs would normally be flooded throughout the entire AS, which could result in quite a large LSDB consisting of many external advertisements. To reduce the size of the LSDB, an ABR can block AS-External-LSAs into the local area. As the ABR deprives the area of knowledge about external routes, it must make up for it by advertising a replacement route in the form of the default route. It uses the Inter-Area-Prefix-LSA to advertise the default route. The metric associated with the default route is called the stub metric. If there are multiple ABRs for that area, each ABR blocks AS-External-LSAs and replaces them with a default route. Routers internal to the area calculate the best path of the default route by adding the metric of getting to the ABR to the stub metric. Because there are no external routes within a stub area, there is no need for the ABR to advertise the presence of the ASBR into a stub area. The ABR therefore does not originate Inter-Area-Router-LSAs into a stub area. All routers within the stub area must be configured to be in a stub area by turning off the external-capability option. This external-capability option is crucial to forming adjacencies (see "Forming Adjacencies," later in this chapter), as all routers within an area have to agree on the same external-capability option.

There are some restrictions for stub areas. They cannot be configured as transit areas for virtual links. In addition, no ASBR can be placed in a stub area because the routers in a stub area cannot import external information. The backbone area can never be a stub area. To prevent unknown LSA types from being flooded into a stub area, certain measures must be taken. An unknown LSA can be flooded only if the LSA has link-local or area flooding scope and the handling bit (called the U bit) for flooding unknown LSAs is set to 0. Refer to "LSA Flooding," later in this chapter, for details.

As the ABR advertises a default route into the stub area, it could optionally stop originating routes to other areas as well. This can be useful if it is not crucial for the internal routers of a stub area to know the details of all routes to other areas. As long as they have the default route, they are happy. Such an area is sometimes called a totally stubby area. Figure 8-12 gives an example of stub areas.

Figure 8-12. Stub area

8.3.2.6. Not-so-stubby areas

There are cases when stub areas need to connect to routers that have non-OSPF routes. The implementer does not want to revert the area to a normal area to allow these external routes to be imported. Because no AS-External-LSAs are allowed in a stub area, the OSPF designers came up with a new type of LSA called Type-7-LSA. Type-7-LSAs are exactly like AS-External-LSAs, but they can exist in a stub area. Stub areas in which Type-7-LSAs exist are humorously referred to as Not-So-Stubby Areas, or NSSAs. Type-7-LSAs are flooded only within the NSSA. An NSSA ASBR issues one Type-7-LSA per external route. ABRs of the NSSA can translate Type-7-LSAs into AS-External-LSAs to advertise them to the rest of the AS. In addition, these ABRs still behave like ABRs in a stub area, and they advertise a default route by using a Type-7-LSA in this case. All routers within the NSSA must be configured to be in an NSSA by turning on the NSSA capability option. This option must be set on all routers to form adjacencies (see "Forming Adjacencies"). In addition, the external-capability option still must be turned off on all routers within the NSSA. The NSSA has the same restrictions as the stub area. In addition, it cannot be a totally stubby area.

8.3.3. Message Format of OSPF for IPv6

Let's now have a closer look at the protocol implementation starting with the actual OSPF packet encapsulation. The routers use OSPF packets to exchange LSA information and to establish and maintain neighbor relations (adjacencies).

8.3.3.1. Encapsulation in IP datagrams

OSPF packets are directly encapsulated in IPv6, specified by protocol number 89 in the Next Header field of the IPv6 header. This means that OSPF does not run over TCP or UDP.

OSPF doesn't use fragmentation, therefore relying entirely on IP fragmentation when sending packets larger than the MTU. Fragmentation should be avoided whenever possible. Potentially large OSPF packets such as Database Description packets or Link State Update packets can easily be split into multiple packets by OSPF itself.

OSPF messages normally use the link-local IPv6 address of the outgoing interface as their Source addresses. The exceptions are messages sent on a virtual link. They use the local or global unicast address of the virtual link as their source. Depending on the situation, OSPF messages can be sent as a unicast to a specific neighbor or as a multicast to multiple neighbors. The following two multicast addresses are set aside for this purpose:

AllSPFRouters (FF02::5): All routers running OSPF must listen to this multicast address. Hello packets are always sent to this address, with the exception of non-broadcast-capable networks. This address is also used for some packets during LSA flooding.
AllDRouters (FF02::6): Both the DR and the BDR (see the section "Forming Adjacencies") on a multiaccess medium must listen to this multicast address. This address is used for some packets during LSA flooding.

OSPF packets sent to the multicast address have link-local scope, and their IPv6 hop limit is set to 1. They will never be sent over multiple hops.

8.3.3.2. OSPF header

There are five different packet types used by OSPF. All OSPF packets begin with a standard 16-byte header, shown in Figure 8-13.

OSPF uses the word "type" in many instances. Carefully distinguish between OSPF packet type, LSA types, and Link type. This book uses the name of a particular type rather than the type number.

The fields of the OSPF header are explained in detail in the following list:

Version (1 byte)

OSPF for IPv6 uses version number 3.

Type (1 byte)

Defines the type of OSPF messages. Table 8-3 lists all possible types.

Table 8-3. OSPF for IPv6 packet types
Packet type	Name	Description
1	Hello	Initializes and maintains adjacencies. Also used to elect DR and BDR. See the section "Forming Adjacencies."
2	Database Description	Exchanges database description during the formation of adjacencies. See the section "Forming Adjacencies."
3	Link State Request	Requests missing or changed LSAs. See the section "Forming Adjacencies."
4	Link State Update	Transmits LSAs either responding to requests when forming adjacencies or during LSA flooding. See the sections "Forming Adjacencies" and "LSA Flooding."
5	Link State Acknowledgment	Acknowledges the reception of an LSA. Every LSA must be acknowledged. See the sections "Forming Adjacencies" and "LSA Flooding."

Figure 8-13. The OSPF for IPv6 packet header

Packet length (2 bytes)

This is the length of the OSPF protocol packet in bytes, including the OSPF header.

Router ID (4 bytes)

The Router ID of the router originating this packet. Each router must have a unique Router ID, a 32-bit number normally represented in dotted decimal notation. The Router ID must be unique within the entire AS.

Area ID (4 bytes)

The Area ID identifies the area to which this OSPF packet belongs. The area is normally based on the area of the outgoing interface of the router. The Area ID is a 32-bit integer. Area 0 represents the backbone area.

Checksum (2 bytes)

OSPF uses the standard checksum calculation for IPv6 applications. The checksum is computed using the 16-bit one's complement of the one's complement sum over the entire packet. If the packet's length is not an integral number of 16-bit words, the packet is padded with zeros before checksumming. Before computing the checksum, the checksum field in the OSPF packet header is set to 0.

Instance ID (1 byte)

Identifies the OSPF instance to which this packet belongs. The Instance ID is an 8-bit number assigned to each interface of the router. The default value is 0. The Instance ID enables multiple OSPF protocol instances to run on a single link. If the receiving router does not recognize the Instance ID, it discards the packet. For example, routers A, B, C, and D are connected to a common link n. A and B belong to an AS different from the one to which C and D belong. To exchange OSPF packets, A and B will use a different Instance ID from C and D. This prevents routers from accepting incorrect OSPF packets. In OSPF for IPv4, this was done using the Authentication field, which no longer exists in OSPF for IPv6.

8.3.3.3. Processing OSPF packets

When a router sends an OSPF protocol packet, it fills in the header fields as described earlier. The Area ID and Instance ID are taken from the data structure of the outgoing interface. If authentication is required, it is the responsibility of IPv6 to add the necessary headers.

When a router receives an OSPF protocol packet, IPv6 validates it first by checking the IPv6 headers (IPv6 addresses, Next Header field, and authentication). The packet is then given to the OSPF process. OSPF checks the version number (which must be 3), the checksum, the Area ID, and the Instance ID. The Area ID must match the Area ID configured on the incoming interface. If there is no match, but the Area ID is 0, the incoming interface must be the endpoint of a virtual link. The Instance ID must match the interface's Instance ID. If the packet's destination IPv6 address is the AllDRouters multicast address, the router must be either a DR or a BDR on this link. (DR and BDR will be explained in the next section.) If the packet passes all of these tests, it is passed to the appropriate OSPF process for further processing. Otherwise, it must be dropped.

8.3.4. Forming Adjacencies

In order to exchange LSAs, the routers must create reliable channels, called adjacencies, to its neighbors. These channels allow the routers to synchronize the LSDB upon initialization and to flood the LSA in case of a change.

The neighbors need to be discovered first. This is done using the Hello protocol. Each interface on an OSPF router is assigned one of four link types: point-to-point, transit, stub, or virtual. On point-to-point or virtual links, only one neighbor can be discovered. Transit links correspond to multi-access networks (e.g., Ethernet); multiple routers can be connected to this network, and therefore more than one neighbor could be discovered. Forming adjacencies with all routers on transit links is not necessary. Each transit link elects a DR to form adjacencies with all routers on the transit link. This guarantees that all routers on this link have a synchronized LSDB. To ensure uninterrupted operation, a BDR is elected as well; it forms adjacencies with all routers on the transit link, too. Figure 8-14 shows adjacencies on point-to-point links and transit links. If no neighbor is discovered on any given link, the link is declared to be a stub link, and obviously no adjacencies are being formed on such a link.

Figure 8-14. Adjacencies on point-to-point and transit links

8.3.4.1. The Hello packet

The Hello Protocol is responsible for initializing and maintaining adjacencies as well as electing a DR/BDR. It ensures that communication between two routers is bidirectional. Hello packets are sent out through each interface at regular intervals. On point-to-point or broadcast-capable transit networks, OSPF Hello packets are sent to the multicast address AllSPFRouters. The neighbors are discovered dynamically. Multi-access networks not capable of transmitting broadcast or multicast packets (e.g., X.25 and some Frame Relay implementations) are called non-broadcast-multi-access networks (NBMA). NBMA networks can be configured as either point-to-multipoint links or transit links. Point-to-multipoint links are actually point-to-point links as separate logical links are created to each neighbor. As in point-to-point links, no DR or BDR is needed. NBMA networks configured as transit links have static IPv6 address entries for each neighbor. A DR and BDR is elected. OSPF messages are sent as unicast to these statically configured neighbors.

Figure 8-15 shows the Hello packet format. It is an OSPF packet type 1, as explained earlier in Table 8-3.

Figure 8-15. The Hello packet

The following list explains all the fields of the Hello packet in detail:

Interface ID (4 bytes)

Identifies the interface of the Hello packet. Each interface of an OSPF router is assigned an Interface ID. The Interface ID must be unique within the same router. Some implementations use the MIB-II Interface Index as specified in RFC 2863.

Within the field explanations, the terms "interface" and "router" always refer to the originating router and its interface over which the packet was sent.

Router priority (1 byte)

Identifies the router priority number assigned to the interface. It is used for the election of the DR or BDR. This field is meaningful only on transit links. The router with the highest priority becomes the DR or BDR, but only if a DR or BDR has not already been elected. If this field is set to 0, the router of the interface can never be a DR or BDR.

Options (3 bytes)

Describes the optional capabilities of the router. This field is set in OSPF Hello packets, Database Description packets, and the following LSAs: Router-LSA, Network-LSA, Inter-Area-Router-LSA, and Link-LSA. Table 8-4 explains the bits used in the Options field. Only 6 bits are currently used.

Table 8-4. The Options field
Bit	Name	Description
0-17	Not used	Reserved for future use.
18	DC	Handling of Demand Circuits, as described in RFC 1793.
19	R	Indicates that the originator of the Hello packet is an active router. If this bit is set to `0`, the originator will not forward packets: for example, a multihomed host that wants to build an OSPF routing table without actually routing packets.
20	N	All routers within an NSSA must set this bit. In addition, the E bit must be set to `0` (see RFC 3101).
21	MC	Multicast capability, as defined in RFC 1584.
22	E	External-routes capability of the router. All members of an area must agree on the external capability. In a stub area, all routers must set this bit to `0` to achieve adjacency. The E bit is meaningful only in Hello packets (similar to the N bit).
23	V6	Indicates that the router supports OSPF for IPv6. If set to `0`, this router/link should be excluded from IPv6 routing calculation.

Hello interval (2 bytes)

Specifies the number of seconds between Hello packets sent by the router on the link. The default is 10 seconds.

Router Dead Interval (2 bytes)

Specifies the number of seconds before the router declares a silent router on the link to be down. (A silent router is no longer sending Hello packets.) The default is 40 seconds. On a transit link, the Router Dead Interval also determines the waiting timer during the election of the DR or BDR. Upon initialization of a transit link, the interface enters a waiting state to determine whether a DR or BDR has already been elected.

Designated Router ID (4 bytes)

Specifies the Router ID of the DR from the router's perspective on the link. This field is useful only on transit links. It is set to 0.0.0.0 when no DR has yet been elected, or on point-to-point links.

Backup Designated Router ID (4 bytes)

Specifies the Router ID of the BDR from the router's perspective on the link. This field is useful only on transit links. It is set to 0.0.0.0 when no BDR has yet been elected, or on point-to-point links.

Neighbor ID (4 bytes)

Specifies the Router ID of each router from which the router has received valid Hello packets on the link during the last Router Dead Interval.

8.3.4.2. Interface status and election of DR/BDR

As soon as IPv6 on an OSPF interface is operational (link up) the processing of Hello packets begins. A point-to-point link changes its state to point-to-point and is immediately active.

A transit link first enters the waiting state to discover the DR/BDR. Each transit link needs a DR and a BDR, which form adjacencies with all routers on that particular transit link. For each transit link the router does the following: during the waiting period, the router listens to Hello packets to determine whether a DR/BDR already exits. It also sends Hello packets with the DR/BDR field set to 0 to indicate that it is in discovery mode. If a router already claims to be the DR, no election of a DR takes place. If no router declares itself as the DR (all Hello packets contain a zero in their DR field), the router with the highest router priority declares itself the DR. If the priorities are equal, the router with the highest Router ID wins the election. The BDR is elected in exactly the same way. Routers that were not elected as DR/BDR are called DR-Other. The interface status changes to either DR, BDR, or DR-Other and becomes active. Routers with a priority of zero never become DR/BDR. Their interface status changes immediately to DR-Other without entering the waiting state.

If the DR goes silent (not sending Hellos for Router Dead Interval), the BDR becomes the DR, and a new BDR is elected. Because the BDR has already formed all adjacencies, there is no disruption of the synchronized LSDB on that transit link. If the original DR comes back online, it recognizes that there is already a DR and a BDR, and it enters the DR-Other state. If the BDR goes silent, a new BDR is elected.

8.3.4.3. Processing of Hello packets

Before a Hello packet is accepted, a number of criteria must be met. Figure 8-16 shows the decision process to accept a Hello packet.

Figure 8-16. Processing a Hello packet

The OSPF input process has already accepted the packet as described in the section "Message Format of OSPF for IPv6." Now the Hello Interval and Router Dead Interval are checked. They must match the values set on the receiving interface. Next, the E and N bits in the Options field are examined. The settings of these bits must match the value set on the receiving interface.

At this point, if all the criteria matched, the packet is accepted and the neighbor is identified by its Router ID. The router keeps a neighbor state table for each interface. If there is already a full adjacency with this neighbor, the Hello timer is simply reset. Otherwise, the state of this neighbor changes to initialize (Init). The router examines the list of neighbors proclaimed in the received Hello packet. If the router identifies its own Router ID in that list, bidirectional communication has been established, and the neighbor's state changes to two-way. The router decides whether to form an adjacency with this neighbor. If the interface is a point-to-point state, an adjacency is formed with this neighbor. On a transit link, if the router itself or this neighbor is the DR/BDR, an adjacency is formed. If the router decides not to form an adjacency, this neighbor stays in a two-way state.

Figure 8-17 explains the different phases of forming an adjacency and the corresponding neighbor states.

Figure 8-17. Forming an adjacency

The two routers forming an adjacency start communicating the contents of their LSDB. This phase is called the database description exchange. Once the routers know the contents of each other's databases, they request the missing or outdated information. This is the loading phase. After completing the loading phase, the routers are fully adjacent. Continuous sending of Hello packets prevents the adjacency from timing out.

8.3.4.4. Database description exchange

The routers change their neighbor state to exchange-start and send an initial Database Description packet without data. They establish a master-slave relationship to achieve an orderly exchange. Each router declares itself as the master in the initial Database Description packet. The only relevant information within the initial Database Description packet is the database description (DD) sequence number issued by each side. The router with the higher Router ID stays master during the entire DD exchange phase.

The neighbors now enter the Exchange state. Starting with the slave, a series of packets describing the contents of their LSDB are exchanged. The master always increments the sequence number and the slave always uses the master's sequence number in its packet. Each router indicates that it has more data to send by setting the more bit (see Figure 8-17). If one router has sent its entire database description but the other hasn't yet, the first router is obliged to send empty packets to keep the sequence numbers matched. To describe the LSDB, the router only sends the database headers (LSA headers) as described in Figure 8-18. The LSA header is discussed later in "The Link State Database." All Database Description packets are sent to the neighbor as unicast. The unicast addresses are discovered by looking at the source IPv6 address of the Hello packet sent by the neighbor. As soon as both routers have nothing more to send, the routers enter the loading phase.

Figure 8-18. Database Description packet

The following list explains all the fields of the Database Description packet in detail.

Options (3 bytes): The optional capabilities supported by the router according to Table 8-4. They should be the same options advertised in the Hello packet. Changes in the Options field during DD exchange will stop the exchange, and the routers revert back to exchange-start.
Interface MTU (2 bytes): The largest frame size that can be sent through the interface without fragmentation. If the router receives a DD packet stating an MTU larger than it can handle on the receiving interface, the packet is rejected. On virtual links, this should be set to 0.
Init bit (I bit): When set to 1, this bit indicates the first Database Description packet sent by the router. This packet contains no data and starts the exchange process. The M/S bit is set as well.
More bit (M bit): When set to 1, this bit indicates that there are more Database Description packets to follow. When set to 0, it indicates that all database descriptions have been delivered.
Master/slave bit (M/S bit): When set to 1, this bit indicates the router to be the master; otherwise, it's the slave.
DD sequence number (4 bytes): This number makes the exchange reliable. The master increments the sequence number by one for each Database Description packet sent. The slave always quotes the last sequence number received by the master. A mismatch in sequence number causes the DD exchange to fail and the routers to revert back to exchange-start.
List of LSA headers (20 bytes for each header): This list describes the entry in the LSDB. See "The Link State Database."

8.3.4.5. The loading phase

The routers are now requesting the missing or outdated LSAs learned during the exchange of database descriptions. Link State Request packets (OSPF packet type 3) identify the requesting LSA by its LSA header. Multiple requests can be sent using a single packet. A router replies to the request by sending the corresponding LSA from its database. The LSA is sent using Link State Update packets (OSPF packet type 4). Multiple LSAs can be sent in a single packet. Each Link State Update must be acknowledged by using a Link State Acknowledgment packet (OSPF packet type 5). The Link State Acknowledgment packet contains the LSA header of the LSA to be acknowledged. Multiple LSAs can be acknowledged in a single packet. The Link State Request and Acknowledgment packets simply contain a list of requested or acknowledged LSA headers, so I won't discuss them in more detail. Like Database Description packets, all the packets just mentioned are sent to the unicast address of the neighbor. The neighbors now enter the full state. Hello packets keep the adjacency alive. Adjacencies must stay alive, as they are used for flooding LSAs. Refer to "LSA Flooding," later in this chapter.

8.3.5. The Link State Database

The link state database (LSDB) is the most important component of OSPF. Figure 8-19 illustrates the components of the LSDB.

Figure 8-19. Components of the LSDB

The LSDB is a data structure consisting of LSAs exchanged in the AS. The link state information is structured to allow the building of a tree whose branches and leaves represent the shortest paths to all routes within the AS. Each router builds such a tree from its point of view. Most commonly, the routers use the algorithm developed by Dijkstra to build this tree of shortest paths (SPF tree). First, the router builds the intra-area tree to all destinations within its own area. Inter-area and external routes are then attached to the branch representing an ABR or ASBR. At the end, each route within the tree is added to one of four sections of the OSPF routing table: the intra-area routes, inter-area routes, external-1 routes, and finally, external-2 routes. The next hop is always the link-local address of first router in the shortest path to the route. The following sections describe each of these components, starting with the contents of the LSDB. Then I'll discuss how Dijkstra calculates the SPF tree and puts the routes into the routing table.

8.3.5.1. Contents of the LSDB

RFC 2328 describes the SPF as a system of directed graphs using vertices to build a tree. This basically describes the network topology as a set of pointers building a tree. There are three basic pointers within the tree:

Router-to-router: Describes a router's point-to-point interface identifying the Router ID of the neighboring router on a point-to-point link. In LSDB terminology, it points from a Router-LSA to another Router-LSA.
Router to transit link: Describes a router's interface to a transit link by identifying the Interface ID of the DR for this transit link. In LSDB terminology, it points from a Router-LSA to a Network-LSA.
Transit link to routers: Describes a transit link and points to all its attached routers. In LSDB terminology, it points from a Network-LSA to one or many Router-LSAs.

There are also informational elements. They provide complementary information associated to particular branches. It is like adding leaves to branches. Unlike the three previous pointers, which build the actual tree, the informational element just adds information to the tree. LSAs representing an informational element are Inter-Area-Prefix-LSA, Inter-Area-Router-LSA, AS-External-LSA, Type-7-LSA, Link-LSA, and Intra-Area-Prefix-LSA.

Figure 8-20 shows the basic pointers and the informational element in a sample tree structure.

Figure 8-20. LSDB structural pointers

8.3.5.2. LSAs

Each LSA within the LSDB incorporates one or more of the previously mentioned pointers or informational elements. It consists of an LSA header and an LSA body. The LSA header identifies each LSA uniquely.

8.3.5.3. LSA header

Each LSA starts with a common 20-byte header. Figure 8-21 shows the details of this header. The Link State (LS) type, LS ID, and Advertising Router together uniquely identify the LSA.

Figure 8-21. LSA header

The LSA header fields are fully detailed in the following list:

LS Age (2 bytes): LS Age is the time in seconds since the LSA was originated. If it has reached MaxAge (3,600 seconds), the LSA is no longer considered for the SPF tree calculation. The originating router of this LSA must renew the LSA and increment the sequence number before MaxAge is reached, to prevent the LSA from aging out. It is recommended to renew an LSA after MaxAge/2.
LS type (2 bytes): This is the type of this advertised LSA. The first three bits of the LSA type field indicate special properties of the LSA.
U bit (handling of unknown LS type): Identifies the handling of unknown LSA types by the routers. If the bit is set, the LSA must be stored and flooded as if the type were understood. Otherwise, if the bit is 0, the LSA has to be treated as if it had link-local flooding scope.
S2 and S1 bit (flooding scope): Define the flooding scope of the LSA. The four values are:

00 = Link-local, flooded only on the link on which it originated
01 = Area, flooded to all routers in the originating area
10 = AS, flooded to all routers in the AS
11 = Reserved

The last 13 bits represent the actual LSA Function Code. See Table 8-5 for details on link state types. The LS type is represented in hexadecimal notation to reflect the flooding scope.

Table 8-5. Link state (LS) types
LS type	Name	Flooding scope	Advertised by	Link State ID
0x2001	Router-LSA	Area	Each router	Router ID
0x2002	Network-LSA	Area	DR	DR's Interface ID of the transit link
0x2003	Inter-Area-Prefix-LSA	Area	ABR	A locally unique ID set by ABR
0x2004	Inter-Area-Router-LSA	Area	ABR	A locally unique ID set by ABR
0x4005	AS-External-LSA	AS	ASBR	A locally unique ID set by ASBR
0x2006	Group-Membership-LSA	Area	See RFC 1584	See RFC 1584
0x2007	Type-7-LSA	Area	See RFC 3101	See RFC 3101
0x0008	Link-LSA	Link	Each router for each link	Locally unique Interface ID
0x2009	Intra-Area-Prefix-LSA	Area	Each router	A locally unique ID set by router

Link State ID (4 bytes): The Link State ID is part of the link state identification. With Router-LSA and Network-LSA, the Link State ID serves as a value for a pointer in the tree to identify this router or network. For all other LSAs, the originating router uses a locally unique ID.
Advertising Router (4 bytes): The Advertising Router is the Router ID of the router originating this LSA.
LS Sequence Number (4 bytes): The LS Sequence Number identifies the instance of this LSA. It is used to determine which LSA is newer in case of multiple occurrences of the same LSA. The higher the sequence number, the newer the LSA is. The starting sequence number is always 0x80000000. The highest sequence number possible is 0x7FFFFFFF. If this number has been reached, the LSA is aged out (LS Age equals MaxAge) and flooded before a new instance of the LSA (now using 0x80000000) is issued.
Checksum (2 bytes): This is the Fletcher checksum of the complete contents of the LSA, including the LSA header but excluding the LS Age field.
Length (2 bytes): This is the length of the entire LSA in bytes.

The following paragraphs explain all types of LSA in detail, with the exception of Group-Membership-LSAs and Type-7-LSAs. Group-Membership-LSAs are defined in RFC 1584, which has not yet been updated for IPv6. Type-7-LSAs are explained in RFC 3101, which introduces the concept of NSSA. Type-7-LSAs are very similar to As-External-LSAs.

8.3.5.4. Router-LSA (type 0x2001)

Router links describe the router's point-to-point, virtual, or transit links. Basically, it includes all links having at least one neighbor. Unlike OSPF for IPv4, stub links are no longer advertised within a router link. An ABR must originate separate router links for each attached area, containing only links belonging to that particular area. Virtual links always belong to area 0 and are advertised only by ABR. Figure 8-22 outlines a Router-LSA.

Figure 8-22. Router-LSA

The fields of the Router-LSA are fully detailed in the following list:

Flags (1 byte)

The Flags field indicates the special function of the router originating the LSA. Table 8-6 shows the possible values and their corresponding functions.

Table 8-6. Flags in Router-LSA
Bit	Name
W bit	The router is a wildcard multicast receiver. See RFC 1584 for more information.
V bit	The router is the endpoint of a virtual link using the area to which this packet belongs as a transit area.
E bit	The router is an ASBR.
B bit	The router is an ABR.

Options (3 bytes)

This field describes the optional capabilities supported by the router, as outlined in Table 8-4.

Link Entry (16 bytes per link)

Each link entry describes an interface of the router. A link entry has five relevant sub-fields. The link types are shown in Table 8-7 describing the possible link types of an interface. The Neighbor Interface ID and Router ID are learned through the Hello protocol. In addition, there is the actual Interface ID and the metric assigned to the interface. The Link Entries are used as pointers to build the intra-area tree. Interface types 1 and 4 point to the Router-LSA specified in the Neighbor Router ID (LS-ID and Advertised Router). Interface type 2 points to Network-LSA, as specified in the Neighbor Interface ID (LS-ID) and Neighbor Router ID (Advertised Router).

Table 8-7. Link type supported in a Router-LSA
Link type	Name	Neighbor Interface ID	Neighbor Router ID
1	Point-to-point	Interface ID of the neighbor on the other end of the point-to-point link	Router-ID of the neighbor on the other end of the point-to-point link
2	Transit	Interface ID of the DR on this link	Router ID of the DR on this link
3	Reserved	N/A	N/A
4	Virtual	Interface ID of the neighbor on the other end of the virtual link	Router ID of the neighbor on the other end of the virtual link

8.3.5.5. Network-LSA (type 0x2002)

The designated router of each transit link in the area originates a Network-LSA. The Link State ID is set to the Interface ID of the DR's interface to the transit link. Figure 8-23 outlines the Network-LSA. It simply contains the Options field (see Table 8-4 earlier in this chapter), followed by a list of Router IDs identifying all routers attached to this particular transit link. This represents a pointer to all routers attached to this transit link.

Figure 8-23. Network-LSA

The Options field in the Network LSA is set to the logical OR of the options received from each Link-LSA of all the routers attached to this transit link. This provides the common optional capabilities supported by all routers on this link.

8.3.5.6. Inter-Area-Prefix-LSA (type 0x2003)

Inter-Area-Prefix-LSAs are originated by the ABR to advertise IPv6 prefixes from other areas into the area of this LSA. A separate Inter-Area-Prefix-LSA is originated for each route. An ABR could summarize a contiguous range of IPv6 prefixes into a single advertisement. For a stub area, the ABR advertises the default route using this LSA. Inter-Area-Prefix-LSA is the equivalent to Summary-LSA in OSPFv2 and is outlined in Figure 8-24.

Figure 8-24. Inter-Area-Prefix-LSA

In the tree-building process, this LSA represents an informational element associated with the ABR for attaching inter-area routes to the SPF tree. The Inter-Area-Prefix-LSA fields are detailed in the following list:

Metric (20 bits): Defines the cost from the ABR to the IPv6 address prefix advertised with this Inter-Area-Prefix-LSA. If this route represents a summary, the metric should be taken from the highest metric of the member prefixes.
IPv6 Prefix Representation (0 to 20 bytes in multiples of 4): Defines the actual IPv6 prefix advertised. It consists of four fields: the Prefix Length, the Prefix Options, an unused field (set to 0), and the actual IPv6 Address Prefix. The Prefix Length defines the length of the address prefix. The default route is represented by a prefix length of 0. Table 8-8 explains the prefix options. The address prefix represents the IPv6 address. If necessary, it is padded with zero bits to the next full 32-bit word.

Table 8-8. Prefix options starting with the leftmost bit
Bit	Name	Description
0-3	Reserved	N/A
4	P bit	Propagate bit: if set, the NSSA ABR readvertises the prefix into the backbone. Used only in Type-7-LSA.
5	MC bit	Multicast bit: if set, the prefix should be included in IPv6 multicast routing calculations.
6	LA bit	Local address bit: if set, the prefix is actually a local IPv6 address of the originating router.
7	NU bit	No unicast bit: if set, the prefix should be excluded from IPv6 unicast calculation.

8.3.5.7. Inter-Area-Router-LSA (type 0x2004)

Inter-Area-Router-LSAs are originated by ABRs to advertise ASBRs from other areas into the area of this LSA. A separate Inter-Area-Router-LSA is originated for each ASBR. This is necessary to inform all routers in this area of the existence of an outside ASBR. Inter-Area-Router-LSA is the equivalent to AS-Summary-LSA in OSPFv2. As shown in Figure 8-25, the Inter-Area-Router-LSA contains the Options field (refer back to Table 8-4), the Metric field, and the Router ID of the ASBR. The Metric field represents the cost from the ABR to the ASBR.

Figure 8-25. Inter-Area-Router-LSA

In the tree-building process, this LSA represents an informational element associated with the ABR for attaching an ASBR to the SPF tree.

8.3.5.8. AS-External-LSA (type 0x4005)

AS-External-LSAs are advertised by ASBRs to import external IPv6 prefixes into the AS. Each AS-External-LSA represents one IPv6 prefix external to OSPFi.e., learned from RIP, BGP, static, etc. They are flooded throughout the entire AS and are therefore known to every router except the routers in a stub area. Figure 8-26 explains the AS-External-LSA.

Figure 8-26. AS-External-LSA

In the tree-building process, this LSA represents an informational element associated with the ASBR for attaching external routes to the SPF tree. The AS-External-LSA fields are described in the following list:

E bit: If set, the specified metric is a Type 2 external metric as explained in "Overview of OSPF for IPv6." The metric is considered larger than any path to any route within the AS. If set to 0, the metric is a Type 1 external metric. It is expressed using the same units as the metric used in Router-LSA, Inter-Area-Prefix-LSA, and Intra-Area-Prefix-LSA.
F bit: If set, a forwarding address has been included in the LSA.
T bit: If set, an external router tag has been included in the LSA.
Metric (3 bytes): Defines the cost from the ASBR to the external IPv6 prefix. The interpretation of the metric value depends on the E bit.
IPv6 Prefix Representation (0 to 20 bytes in multiples of 4): Defines the actual IPv6 prefix advertised. It consists of four fields: the Prefix Length, the Prefix Options, the Referenced LS Type, and the actual IPv6 Address Prefix. The Prefix Length defines the length of the address prefix. The default route is represented by a 0 length prefix. Table 8-8 explains the prefix options. The Address Prefix represents the IPv6 address. If necessary, it is padded with zero bits to the next full 32-bit word.
Referenced LS Type (part of the IPv6 Prefix Representation): If set to a value other than zero, an additional LSA is associated with this external route. This LSA is specified in the Referenced Link State ID field.
Forwarding address (4 bytes): If the F bit is set, any router in the AS forwards data traffic (to the external IPv6 prefix specified with this LSA) to this forwarding address. If the F bit is not set, data traffic is forwarded to the ASBR originating this LSA. This field must never be set to the IPv6 unspecified address (0:0:0:0:0:0:0:0:0). If any router within the AS cannot reach the forwarding address or the ASBR, the IPv6 prefix of the external route is not added to the routing table.
External Route Tag (4 bytes): If the T bit is set, this field contains additional information about the external route. This information, however, will never be used within the OSPF AS.
Referenced Link State ID (4 bytes): If and only if the Referenced LS Type is set to a value other than zero, the Referenced LS Type, Referenced Link State ID (this field), and the advertising router of this LSA represent an existing LSA in the LSDB, providing additional information for this external IPv6 prefix. This information, however, is not used by the OSPF protocol itself. The precise nature of such information is not part of the OSPF specification.

8.3.5.9. Link-LSA (type 0x0008)

Link-LSAs are originated by each router, one for each link of the router. They are never flooded beyond this link. The Link State ID is set to the Interface ID of this link. The Link-LSA serves three purposes. It provides:

The router's link-local address to all other routers attached to this link
A list of IPv6 prefixes associated with this link
A list of options to be used by the designated router for this link

Figure 8-27 outlines the Link-LSA

Figure 8-27. Link-LSA

In the tree-building process, this LSA represents an informational element associated with each link from or to a Router-LSA. It attaches the link-local address of the link to the SPF tree. The Link-LSA fields are described in the following list:

Router Priority (1 byte): The priority number given to the router on the interface.
Options (3 bytes): The router would like to use the options specified here (see Table 8-4). This is an indication (to the DR on this transit link) of which options it should use.
Link-local address (16 bytes): The link-local address of the interface.
Number of prefixes (4 bytes): The number of prefixes to be advertised with this LSA.
IPv6 Prefix Representation (4 to 20 bytes in multiples of 4): All IPv6 prefixes will be listed here according to the number of prefixes. It consists of four fields: the Prefix Length, the Prefix Options, an unused field (set to 0), and the actual IPv6 Address Prefix. The Prefix Length defines the length of the address prefix. Table 8-8 explains the prefix options. The Address Prefix represents the IPv6 address. If necessary, it is padded with zero bits to the next full 32-bit word.

8.3.5.10. Intra-Area-Prefix-LSA (type 0x2009)

A router uses the Intra-Area-Prefix-LSA to advertise one or more IPv6 prefixes associated with either the router or a Network-LSA. As OSPF for IPv6 has removed all addressing semantics from the Router-LSAs and Network-LSAs, the Intra-Area-Prefix-LSA provides this information. Each address prefix advertised is associated with a Router-LSA or a Network-LSA. Figure 8-28 shows the contents of an Intra-Area-Prefix-LSA. Particular attention should be paid to the Referenced LS Type, Link State ID, and Advertising Router fields, as explained next.

Figure 8-28. Intra-Area-Prefix-LSA

In the tree-building process, this LSA represents an informational element associated with a router, attaching IPv6 prefixes of its interfaces to the SPF tree. It can also be associated with a transit link, attaching its IPv6 prefixes to the SPF tree. The Intra-Area-Prefix-LSA fields are detailed in the following list:

Number of prefixes (2 bytes): The number of prefixes to be advertised with this LSA.
Referenced LS Type, Link State ID, Advertising Router (10 bytes): If the Referenced LS Type is set to 0x2001, the address prefixes are associated with this router. The Referenced Link State ID is set to 0, and the Referenced Advertising Router is set to the Router ID of the router originating this LSA. If the Referenced LS Type is set to 0x2002, the address prefixes are associated with the Network-LSA. The Referenced Link State ID is set to the Interface ID of the link's DR, and the Referenced Advertising Router is the Router ID of the DR.
IPv6 Prefix Representation (4 to 20 bytes in multiples of 4): All IPv6 Prefixes are listed here according to the length of prefixes. It consists of four fields: the Prefix Length, the Prefix Options, the Metric, and the actual IPv6 Address Prefix. The Prefix Length defines the length of the address prefix. Table 8-8 earlier in this chapter explained the prefix options. The Address Prefix represents the IPv6 address. If necessary, it is padded with zero bits to the next full 32-bit word. The Metric field defines the cost of this prefix.

8.3.6. Calculation of the OSPF Routing Table (Dijkstra Algorithm)

Using the LSDB as a base, each router builds an SPF tree and adds the routes to the routing table. Each router keeps multiple LSDBs. The Link LSDB contains all LSAs with link-local flooding scope, the Area LSDB contains all LSAs with area flooding scope, and finally, the AS LSDB contains all LSAs with AS flooding scope. The ABR has one Area LSDB for each locally attached area. The tree-building is based on Dijkstra's shortest path first (SPF) algorithm. It involves the three-step process described in the following subsections. The sample network depicted in Figure 8-29 illustrates the process. Steps 1 and 2 must be performed on the Area LSDB. The ABR has to perform them for each local area as it builds one SPF tree for each area.

Figure 8-29. Sample network and its LSDB

8.3.6.1. Step 1: Intra-area routes

In Step 1, the router builds the core tree using the Router-LSA and Network-LSA for this area. Remember that these two LSAs contain actual pointers. Each router places its own Router-LSA at the root of the tree. Each link entry in the Router-LSA represents a pointer to another Router-LSA (link type 1 or 4) or to a Network-LSA (link type 2). The Neighbor ID and, on link type 2, the Interface ID identify the LSA at the end of the pointer. Each adjacent LSA (called a candidate) is placed temporarily in the tree as a branch, and their metric is noted on the branch. The least-cost branch is made permanent because it represents the shortest path. Its LSA is examined next. Based on the type of LSA, the following happens:

Router-LSA: Each link entry of this router LSA provides a new set of LSAs as candidates. The candidates are added to the tree temporarily unless the candidate is already permanently in the tree and can therefore be ignored. The metrics are added to the branches.
Network-LSA: Each attached router provides a new set of LSAs as candidates. The candidates are added to the tree temporarily unless the candidate is already permanently in the tree and can therefore be ignored. The metrics are not added to the tree, because the metric to this transit link has already been determined and noted in the tree.

All paths to all candidates are being examined. The LSA with the smallest path cost (accumulated metric from the root) is made a permanent branch. If this particular LSA exists as a temporary branch anywhere else in the tree, the temporary branch(es) can be eliminated. In case of two or more branches having the same least costs, each branch is made permanent. The LSA of the newly made permanent branch is examined and these steps are repeated.

This process continues until there are no more Network-LSAs or Router-LSAs to be added. The SPF core tree is now built. The tree, however, contains no addressing information. This address information is provided by the Intra-Area-Prefix-LSA. The router simply adds the Intra-Area-Prefix-LSA to the Router-LSA or Network-LSA according to the referenced LSA. The last step is to find the next hop information. Next hop addresses are the link-local addresses of directly connected routers. This information is provided by the Link-LSA originated by the directly connected routers. The router has now found all routes within the area and adds them to the OSPF routing table as Intra-area routes. Figure 8-30 explains the building of the SPF tree of area 1 for Router R1.

Figure 8-30. Intra-area tree for router R1 in area 1

8.3.6.2. Step 2: Inter-area routes

The router identifies all Inter-Area-Link-LSAs of the local area as they represent routes from areas other than the local area. In addition, all ABRs of the local area are identified based on the intra-area tree constructed in step one. The Inter-Area-Link LSAs are now associated with the corresponding ABRs and added to the tree with the advertised metric. This attaches IPv6 prefixes of routes to the tree. The total cost to these routes consists of the cost to the ABR added to the cost advertised in the Inter-Area-Link-LSA. If the same prefix appears more than once, the one with the best total path cost is considered. If the costs are equal, all equal-cost prefixes must be accepted into the inter-area routing table. The next hop is determined as the directly connected router on the shortest intra-area path to the ABR. Figure 8-31 illustrates this process for Router R1.

Figure 8-31. Inter-area routes for Router R1

If the router itself is an ABR, only Inter-Area-Link-LSAs originated by other ABRs are considered. All Inter-Area-Link-LSAs that represent routes for directly attached areas are ignored because there is always an intra-area path to that destination, and intra-area paths are always preferred.

8.3.6.3. Step 3: External routes

The router first identifies all Inter-Area-Router-LSAs and associates them with the ABRs as described in step 2. This ensures that all ASBRs outside the local area have been identified. The ASBRs of the local area are identified based on the intra-area tree constructed in step one. Next, the router associates all AS-External-LSAs with their corresponding ASBR and adds them to the SPF tree. This attaches the IPv6 prefixes of the external routes to the tree. Depending on the external metric type, the router enters these routes into the external-1 or external-2 routing table. If the same prefix appears more than once, external-1 routes are preferred over external-2 routes. If the same prefix still appears more than once, the one with the best total cost is considered. If the costs are equal, all equal-cost prefixes must be accepted. The next hop is determined as the directly connected router on the shortest intra-area path to the ASBR or to the forwarding address, if the F bit has been set within the LSA. Figure 8-32 illustrates this process for Router R1.

Figure 8-32. External routes for Router R1

The calculation of the OSPF routing table is now finished, and its content is handed to the internal routing process of the router.

8.3.7. LSA Flooding

Any change in the network causes certain link state information to change. Examples of such changes include the following:

The state of a router's OSPF interface changes.
A neighbor transitions to full state.
A neighbor loses full adjacency.
The DR on a transit link changes.
A new IPv6 prefix is added or deleted on any given interface configured for OSPF.
An interface configured for OSPF is added or deleted on a router.
An area's summary information changes.
An external route is added or withdrawn at the ASBR.
The renewal timer (MaxAge/2) of an LSA requires an updated LSA.

The router detecting the change rewrites the LSA accordingly, increases the sequence number, and gives the LSA to the flooding process. According to Table 8-5, the LSA is then flooded to a neighbor only (link scope), to all neighbors in the same area (area scope), or to all neighbors (AS scope).

Flooding means that the LSA is passed from the advertising router to its adjacent neighbors. Depending on the flooding scope of the LSA, the neighbors then pass it on to their neighbors, and so on. Each router receiving an LSA first evaluates whether the LSA is new or has a higher sequence number than the one already installed in the LSDB. If either of these two conditions is true, the LSA is added or replaced in the LSDB. Now the router considers the interfaces to be used for further flooding. It will not flood the LSA out the incoming interface with one exception: if the router is a DR for the incoming interface of the LSA and the LSA was not sent by the BDR, it must be flooded back out the same interface. The DR is responsible for sending LSAs to all its neighbors. Another reason not to flood the LSA is, if the LSA is older than or the same age as the one already installed. This prevents LSAs from looping in the network. LSAs are normally sent to the AllSPFRouters multicast address with the following exceptions:

On transit networks, routers in the DR-Other state send LSAs to the address AllDRouters. The update reaches the DR/BDR, which in turn sends it back to all other routers on this transit link using the AllSPFRouter multicast address.
If a router requests a link state update sending a Link State Request packet, the LSA uses the unicast address of the requesting router.
On NBMA, all LSAs are sent unicast to the statically configured neighbors.
LSA retransmissions (unacknowledged LSAs) are sent to the unicast address of the neighbor.

Figure 8-33 shows the process of a DR receiving new or changed LSAs and flooding them to all routers.

Figure 8-33. LSA flooding

Each router receiving a new or changed LSA has to acknowledge this LSA. Sending a Link State Acknowledgment packet usually accomplishes this. It could also be acknowledged by sending back the LSA if the received LSA is older or the same age as the one already installed in the LSDB. In that case, the sequence number is set to the one already installed. Unacknowledged LSAs have to be retransmitted. Each router keeps track of which neighbor has acknowledged which LSA. Retransmissions are always sent to the unicast address of the neighboring router.

A sequence number is assigned to the LSA by the advertising router to keep track of the most recent instance of this particular LSA. The sequence number is incremented by the advertising router each time the LSA is changed. When a new or changed Router-LSA or Network-LSA is received and accepted, the router installs it in the LSDB. It then recalculates the SPF tree. If a new or changed LSA of another type is received, it is not necessary to recalculate the SPF tree, because these LSAs represent only informational elements. They replace or remove the existing information. The new information is used to reevaluate the best path for the intra-area, inter-area, or external routers.

8.3.7.1. Aging an LSA

In addition to the sequence number, each LSA maintains an Age field. The age is expressed in seconds. Each router increments the Age field of its LSA by one every second. If an LSA is transmitted to the neighbor router, a transmit delay must be added to the Age field. An LSA can never age beyond a Maximum Age (MaxAge), which is an architectural constant set to 3,600 seconds. Usually a router is flooding an update (increment sequence number) of its own LSA when it has reached MaxAge/2. LSAs that have reached MaxAge are not considered for the SPF tree and are eventually deleted from the LSDB. The advertising router can prematurely age an LSA to flush it from the OSPF area or AS. It simply sets the Age field to MaxAge. This would be done if, for example, an external route were withdrawn. Another reason to prematurely age an LSA might occur if the LSA has reached the biggest sequence number possible. Before wrapping the sequence number (starting again), the LSA has to be flushed. This is very unlikely to happen. If there were to be a change of the LSA every second, it would take over 136 years to reach the biggest sequence number.

8.3.7.2. Self-originating LSAs

A router may receive an LSA that it has issued itself. This could happen if there are redundant links within the area, forming a loop. Self-originated LSAs are normally discarded unless the self-originated LSA is newer. Obviously, this should not happen because only the advertising router can increment the sequence number of the LSA. If, however, the router has been rebooted, previously issued LSA are still held in the other router's LSDB. If a newer, self-originated LSA is received, the router prematurely ages that LSA, thereby flushing it from the area or AS.

8.3.7.3. Handling of unknown LSAs

OSPF for IPv6 has added the capability to handle unknown LSAs. Each LSA header contains the U bit in its LSA Type field. If the U bit is set, the unknown LSA is flooded according to the encoded flooding scope. A U bit set to 0 indicates link-local flooding scope. The exception to the previous rule is flooding into a stub area. To prevent unnecessary flooding of LSAs into a stub area, the following rule applies: if the LSA is unknown and either its flooding scope is set to AS or its U bit is set, the LSA is discarded and not flooded into a stub area.