We’ve discussed several techniques to improve the performance of Distance-Vector (D-V) protocols. With that accomplished, the next thing to do is to examine their scalability. With the D-V protocols, as the size of an internetwork grows, the number of prefixes to be advertised and stored grows, requiring greater bandwidth and RAM. Also, as the number of routing updates increases, more CPU power is required to send and receive the updates.
Around 1990, based on the projected growth of internetworks, it became apparent that the scalability of the D-V protocols would present a problem. To deal with this, an entirely new category of routing protocols was developed: the “Link-State” protocols.
Each Link-State router builds a topology database that contains everything that router knows about the topology of the internetwork. This information includes which IP prefixes are directly connected to which routers, and the metric information for each prefix. It’s referred to as a “Link-State” protocol because each router knows the detailed prefix (link) and metric (state) information…in other words, the state of the links.
It’s like a jigsaw puzzle, where each router contributes a piece of the puzzle (the prefixes to which it is directly connected). The goal is to collect all of the pieces, and then assemble the puzzle.
Each router begins by placing an entry for itself in its topology database. Next, the router uses a “hello” protocol to discover its directly connected neighbors. The neighbors then exchange topology information. When an update containing new topology information is received, the router adds that piece to its topology database, and then floods that piece. Each neighbor does the same. When this process is complete, all routers will have detailed information about the entire topology, and each router can then determine the best path from itself to each destination prefix.
Think of the internetwork as being like a shopping mall. There’s a map near each door that shows where all the stores are. Because it’s all one mall the maps are identical, except for one thing: the “You Are Here” marker. We can use the nearest map to find the best route from where we are to each of the stores that we’d like to visit. Similarly, each router has a topology database. Because all of the routers are part of one internetwork, all of the topology databases are identical. Using its copy of the topology database, each router individually calculates the best next hop for each known destination prefix, and places this information in its routing table. At this point, routing has converged.
There are, however, a few differences between a real Link-State protocol and our shopping mall analogy. First, the maps in the mall are diagrams, while routers keep the topology databases in table form. Second, while most shoppers are interested in visiting only a few stores within the mall (there may be exceptions), routers calculate the best next hop for all known prefixes.
Key Point: With a Link-State protocol, what’s being advertised from one router to another is raw topology information, not routing table entries. As a result, each Link-State router knows the entire topology of the internetwork. Since the topology updates are acknowledged (making the protocol reliable), there is no need for frequent periodic updates. Instead, updates need only be sent when a topology change occurs. In between changes, the hello protocol is used to verify the continued availability of neighbors.
Next time, we’ll look at Link-State protocols in more detail, including some real-world examples.
Author: Al Friebe