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.
184.108.40.206. 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:
220.127.116.11. 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 108 by the line speed in bits per second. This formula is out-dated, as interface speed today is in the range of 109 (e.g., Gigabit Ethernet) or even 1010. 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."
18.104.22.168. 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.
22.214.171.124. 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."
126.96.36.199. 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
188.8.131.52. 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
184.108.40.206. 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.
220.127.116.11. 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
18.104.22.168. 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).
22.214.171.124. 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:
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.
126.96.36.199. 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.
The fields of the OSPF header are explained in detail in the following list:
188.8.131.52. 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
184.108.40.206. 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:
220.127.116.11. 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.
18.104.22.168. 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.
22.214.171.124. 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.
126.96.36.199. 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.
188.8.131.52. 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:
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
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.
184.108.40.206. 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:
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.
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.
220.127.116.11. 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:
18.104.22.168. 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.
22.214.171.124. 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:
126.96.36.199. 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.
188.8.131.52. 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:
184.108.40.206. 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:
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:
220.127.116.11. 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:
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
18.104.22.168. 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:
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
22.214.171.124. 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.
126.96.36.199. 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 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:
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.
188.8.131.52. 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.
184.108.40.206. 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.
220.127.116.11. 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.