Within a network of adjacent routers, each router originates an announcement of its directly connected links and neighbors. As you have already seen, every router in the network must receive every announcement and record a copy in its database. The process of getting the announcement to every router is called flooding. Flooding in the network shown in Figure 2.10 is an easy process: Each router sends its announcement to all of its adjacent neighbors, and each of these neighbors forwards a copy of the announcement to each of its own adjacent neighbors. If split horizon is practiced (no router sends an announcement back to the neighbor it received the announcement from), every router gets a copy of every announcement and the flooding then stops.
The network in Figure 2.12 presents more of a challenge for flooding because of all the loops. Just as split horizon rules are insufficient to stop the looping of vector protocol updates in such a topology, split horizon rules are insufficient to control the flooding of link state announcements. A better process is needed to stop the flooding of an announcement after all routers have a copy.
Figure 2.12. A well-meshed network poses challenges for flooding.
There are other considerations beyond just knowing when to stop flooding. If a router originates an announcement and then fails, how do the other routers know that its announcement no longer is valid? If a router receives differing announcements from the same router, which announcement should be believed? If an announcement becomes corrupted either in transit or in a database, how can a router detect the corruption?
Three mechanisms used to create a more reliable flooding process are aging, sequence numbers, and checksums.
Timely Flooding: Aging
One of the essential concepts of a link state protocol is that the information in every router’s database must be the same as the information in every other router’s database. To guarantee “sameness,” no router can modify another router’s announcement. That means that every router is responsible for its own announcements.
What happens, then, if a router fails after flooding an announcement? If the failure is due to a link problem, the neighbors on the link will detect the failure through the Layer 2 protocol. If the failure is a protocol daemon or the router itself, neighbors will detect the failure through the loss of Hello messages. In either case, the effected neighbors send new announcements indicating the change.
But now there can be a dilemma. If router A fails, nonadjacent routers receive announcements from A’s adjacent neighbors indicating the loss of A. But these routers also still have A’s link announcement in their databases. What should be done with those announcements? Can the other routers safely deduce that A has failed and remove A’s announcement? Is this a violation of the rule that no router can modify another router’s announcement? And more important, how can each router be confident that all other routers have removed the announcement, to preserve database consistency?
To help resolve this dilemma, link state protocols include an age field in each link announcement. When a router originates an announcement, it sets a value in the age field. This value is changed (either incremented or decremented) by other routers during flooding, and by every router as the announcement resides in its database. Some absolute value is specified in the protocol at which, if the age reaches this value, the announcement is declared invalid or “aged out,” and is deleted from the database. The originating router is responsible for sending a new copy of the announcement at some time prior to this age expiration. The origination of a new announcement is called a refresh. In our example scenario, router A’s announcement ages out in all databases because A is no longer refreshing the announcement. Every router in the network then has some assurance that as it deletes A’s announcement, all of the other routers are also deleting the announcement.
An age counter can be either up-counting or down-counting. An up-counting age is less flexible because it is set between two absolutes: zero and the maximum age specified in the protocol design. On the other hand, a down-counting age can start at some arbitrary value, bounded at the upper end only by the size of the age field, and counts down to zero.
Sequential Flooding: Sequence Numbers
Whenever a router receives a link announcement, it sends a copy out each of its downstream interfaces. It is obvious in a well-meshed network such as the one depicted in Figure 2.12 (up) that an announcement will be replicated numerous times during flooding, and as a result some routers will receive multiple copies of the same announcement. If all announcements arrive at the same time, any announcement can be chosen. Of course, delays across different network paths back to the originator are going to vary, so in most cases the multiple copies of the same announcement arrive at different times. In this case, the router might simply accept the announcement with the lowest age, on the grounds that the lowest age indicates the newest announcement.
However, accepting the announcement with the lowest age assumes that the multiple announcements contain the same information. Suppose that very soon after a router originates an announcement a link changes state, prompting a new announcement. It is entirely possible that delay variations in the network could cause the second announcement to arrive with a greater age than the first announcement, causing the second announcement to be incorrectly dropped. Therefore, age is not a reliable determinant for choosing the most recent announcement. A second value, the sequence number, specifies the most recent version of a router’s announcement. Given two announcements from the same router, the announcement with the higher sequence number is newer.
As with aging, the design of the sequence counter is important. The simplest sequence numbering scheme is a linear one: A sequence number starts at zero, and increments up to some maximum. For example, a 32-bit sequence number (used by both OSPF and IS-IS) can range from zero to 232, or about 4.3 billion. If a router always starts numbering its announcements at sequence number one, this many available numbers should last far beyond the lifetime of the router. Even if a router produces a new announcement every seconda sign of a very unstable linkthe maximum sequence number would not be reached for more than 130 years. Presumably someone would repair the instability before then.
What if a router does, for some reason, reach the maximum sequence number? In such a case the router must go back to sequence number 1. The problem is that the last announcement with a high sequence number still resides in databases across the network. If a new announcement is sent with a sequence number of 1, that announcement will be viewed by other routers as an older announcement and will be rejected. To avoid this situation, the router must wait until the existing announcement ages out of all databases. This is unacceptable, because while waiting for the age timer to expirewhich can be one hour or longera possibly incorrect announcement continues to be used for route calculations.
There are several possible approaches to this potential problem. One approach is to just do nothing, trusting that with a large enough sequence number space the maximum sequence number will never be reached. The trust here is not that no router or routing protocol is going to remain in uninterrupted service for more than a century, but that no glitches in the protocol daemon will cause the generation of a very high sequence number, introducing the possibility of counting up to the maximum number soon after.
A better approach is for the router cycling its sequence numbers back to the beginning to first cause its previous announcement to be deleted from all databases. The router can do this by issuing another copy of the announcement with the maximum sequence number, but with the age set to a value indicating that the announcement’s age has expired (MaxAge or 0, depending on whether the age counter is up-counting or down-counting). But remember that when comparing two otherwise identical announcements, the router chooses the one with the lower age. Therefore, the rules must be modified a bit, so that an “aged-out” announcement is always accepted over an identical announcement of any other age.
Of course, there is still a period between when the artificially aged-out announcement is sent and the time the new announcement is installed in all databases. Certainly, it is a far smaller period than just waiting for the announcement to age out normally, but it is still a period during which the originating router is not correctly accounted for in the databases.
So, a third approach to prevent reaching the end of the sequence number space is to create a space in which there is no end: a circular sequence number space. For example, if there is a 32-bit sequence number space, the number after 4,294,967,295 is 0. However, there is the potential for confusion in this scheme. Suppose two announcements are received from a router, one of which has a sequence number of 0xFFFFFFFC and one with a sequence number of 0xFFF10D69. The sequence numbers are not contiguous; so is the first announcement newer, or has the sequence number wrapped, making the second number higher?
A couple of rules can reduce the chance of such confusion. Given some sequence number space of n and two sequence numbers a and b, a is considered larger under either of the following conditions:
- a > b, and (a b) < n/2
- a < b, and (b a) > n/2
Figure 2.13 shows a diagram of a 6-bit sequence number. A 6-bit space means that
n = 26 = 64and
n/2 = 32.
Figure 2.13. Sequence numbers in link state protocols could follow a circular number space.
Given two sequence numbers 48 and 18, 48 is more recent because by the first rule
48 > 18 and (48 18) = 30, and 30 < 32.
Given two sequence numbers 3 and 48, 3 is more recent because by the second rule
3 < 48 and (48 3) = 45, and 45 > 32.
Given two sequence numbers 3 and 18, 18 is more recent because by the first rule
18 > 3 and (18 3) = 15, and 15 < 32.
You can see by comparing the relative positions of the numbers on the graph in Figure 2.13 how the two rules enforce circularity when there is a discontinuity between two sequence numbers.
Although a circular sequence number space seems better than a linear one, an odd series of simultaneous errors in a circular sequence number space can cause a network outage much worse than what sequence number rollover in a linear space causes. This determination is based on a meltdown of the ARPANET on October 27, 1980, when an early link state protocol with a 6-bit circular sequence number space was being used. As a result of that experience, both OSPF and IS-IS use linear sequence numbers.
Reliable Flooding: Checksums
The importance of having consistent information in all databases within a link state network has been emphasized throughout this chapter. Yet in networks a link state announcement can become corrupted in many ways. An announcement can be changed due to noise on a link, or it can be corrupted while it resides in a router’s database. Because of the possibility of the announcement being altered, there should be a mechanism for checking to ensure that the announcement is accurate.
The concern over information corruption certainly extends beyond link state protocols. Most IP packets and messages include error checking, most often in the form of a checksum. A checksum is performed over the entire contents of a link state announcement with the exception of the age field. Because the age changes as the announcement passes through routers during flooding, including it in the checksum would mean recalculating the checksum every time the age changes.
We have now discussed several kinds of identifiers associated with a link state announcement. Some identifiers, such as the router ID, are used to differentiate the announcement from other routers’ announcements. Other identifiers, such as the sequence number, age, and checksum, are used to differentiate between specific instances of an announcement from the same router.
All of these identifiers are included in a header that precedes the actual route information of the announcement. This way, none of the information in the announcement itself must be examined during the flooding processonly the header must be examined.
There is also another benefit to having such identifiers in a header. When a router must describe to a neighbor what announcements it has in its database, or when a router must request a copy of an announcement from a neighbor, the announcements can be fully described by sending just the header rather than the entire announcement. Why routers would need to describe announcements to or request announcements from neighbors is explained in the next section.
You should, by now, have a good understanding of a link state database. Announcements from all routers in the network are flooded, and every router keeps a copy of the most recent announcement from every router (including itself) in the database. You also saw how aging is used to ensure that “orphaned” announcements from missing routers are not kept in the database forever. The age of every announcement is tracked, and if the originating router does not refresh the announcement before the age limit is reached, the announcement is deleted from the database.
There is one other procedure concerning the link state database that must be explained. When a new link state router becomes active in a network, it floods its announcement to update the other databases. But how does the router build its own database? Requiring the other routers to reflood their announcements when they see a new router’s announcement might be one way, but it is not very efficient or scalable.
Remember that for a link state protocol to work, every router must have exactly the same database. As you saw in the previous section on flooding, extensive safeguards are implemented to ensure that all databases are identical. This fact can be exploited to allow a new router to build its database without requiring extensive reflooding. After the router forms adjacencies with one or more neighbors, it initiates a database synchronization. When two routers synchronize their databases, they describe the contents of their databases to each other. If a router sees through its neighbor’s descriptions that the neighbor has one or more announcements that are not in its own database, the router can request that the neighbor send it a full copy of the announcement. With the assurance that the new router’s neighbors have the exact same database as everyone else’s, if the router synchronizes with its neighbor it too now has a complete and consistent database.
This is where the announcement headers discussed in the preceding section come in. Because an announcement is completely differentiated by its header, only the header needs to be sent during the phases of synchronization in which a neighbor is describing the announcements in its database and when a router is requesting a copy of the announcements it does not have.