IP Link-State Routing Principles
In this chapter, the concepts of routing with IP using the link-state algorithm and the mechanics of the process are dealt with generically as a foundation for the subsequent chapters. Although this chapter compares the routing protocols OSPF, IS-IS, and BGP-4, subsequent chapters deal with each routing protocol individually. The subsequent chapters assume that you comprehend the subjects covered in this chapter.
“Do I Know This Already?” Quiz
The purpose of the “Do I Know This Already?” quiz is to help you decide what parts of this chapter to use. If you already intend to read the entire chapter, you do not necessarily need to answer these questions now.
The 15-question quiz, derived from the major sections in the “Foundation Topics” portion of the chapter, helps you to determine how to spend your limited study time.
Table 5-1 outlines the major topics discussed in this chapter and the “Do I Know This Already?” quiz questions that correspond to those topics.
Table 5-1 “Do I Know This Already?” Foundation Topics Section-to-Question Mapping
156 Chapter 5: IP Link-State Routing Principles
NOTE The goal of self-assessment is to gauge your mastery of the topics in this chapter. If you do not know the answer to a question or are only partially sure of the answer, you should mark this question wrong for purposes of the self-assessment. Giving yourself credit for an answer you correctly guess skews your self-assessment results and might provide you with a false sense of security.
1. In a network running a link-state routing protocol, every router will have which of the following?
a. A localized routing table
b. An identical view of the network
c. A spanning tree
d. TCP connections with adjacent neighbors
2. Link-state routing protocols use which of the following algorithms?
a. Bellman Ford
d. Path attributes
3. A link-state routing protocol uses which of the following?
a. Incremental updates
b. Hello packets
c. Topology databases
d. Transport layer protocols
4. Which of the following are supported by OSPF?
b. Split Horizon
c. Path Attributes
d. Classless routing
5. OSPF uses a hierarchical design for which of the following reasons?
a. To support VLSM
b. To prevent the 15-hop limitation
c. To conserve network resources
d. To limit the scope of poison reverse
6. OSPF uses multicast addresses for updates. What are the multicast addresses?
7. Which Layer 3 protocols are supported by IS-IS?
a. IP, AppleTalk, and IPX
b. IP and CLNS
c. IP and IPV6
d. DECnet Phase V
8. IS-IS runs at which layer?
a. Layer 3
b. Layer 4
c. Layer 2
d. Layer 5
9. IS-IS is deﬁned in which document?
a. IETF 1195
b. ISO 1195
c. RFC 2043
d. ISO 10589
10. Which of the following best describes the routing protocol BGP-4?
a. BGP-4 connects autonomous systems.
b. BGP-4 sends the entire routing table every 20 minutes.
c. BGP-4 uses path vectors to determine the best path.
d. BGP-4 is an interior routing protocol.
11. At what layer does BGP-4 send keepalives?
a. Layer 2
b. Layer 3
c. Layer 5
d. Layer 4
12. Which of the following characteristics is true of BGP?
a. Uses a best effort delivery
b. Sends the entire routing table every 30 minutes
c. Uses a holddown of 30 seconds
d. Sends only trigger or incremental updates after the initial setup
13. When an OSPF router receives an LSA, which of the following best describes the action taken?
a. Update the routing table and ﬂood the new routing table out of all interfaces
b. Update the topology table and ﬂood the LSA out of its interfaces
c. Put the suspect route into holddown for 30 seconds
d. Mark the entry as suspect and query neighbors for a new route
14. Which of the following routing protocols runs the Dijkstra algorithm to rebuild the routing table?
15. When a neighbor is no longer available, what action will the BGP router take?
a. Clears the route from the routing table and ﬂoods a LSA out of all interfaces
b. Queries neighbors for a new route
c. Uses a holddown of 30 seconds
d. Tries to reconnect to its neighbor
The answers to this quiz are found in Appendix A, “Answers to Chapter ‘Do I Know This Already?’ Quizzes and Q&A Sections.” The suggested choices for your next step are as follows:
■ 7 or less overall score —Read the entire chapter. This includes the “Foundation Topics” and “Foundation Summary” sections, the “Q&A” section, and the “Scenarios” at the end of the chapter.
■ 8–10 overall score —Begin with the “Foundation Summary” section, and then go to the “Q&A” section and the “Scenarios” at the end of the chapter. If you have trouble with these exercises, read the appropriate sections in “Foundation Topics.”
■ 11 or more overall score —If you want more review on these topics, skip to the “Foundation Summary” section, and then go to the “Q&A” section and the “Scenarios” at the end of the chapter. Otherwise, move to the next chapter.
160 Chapter 5: IP Link-State Routing Principles
Link-State Routing Protocol Overview
A link-state routing protocol is a sophisticated protocol dedicated to maintaining loop-free, accurate routing tables. It does not send the entire routing table periodically via broadcasts, as the original distance vector protocols (such as RIPv1) do, but instead uses multicast addressing and incremental updates. Some routing protocols send incremental updates in addition to a compressed copy of the routing table. However, the full routing update is sent every 30 minutes, instead of every 30 seconds, and has a multicast address.
The Meaning of Link State
A link refers to the connection between routers, that is, the physical connection or medium between the routers, over which a logical link is formed. A link-state routing protocol is therefore a protocol that sends information about the links between routers, when there is a change in the state of one of those links. Thus, when the Ethernet connection between Router A and Router B fails, an update is propagated by Router A and Router B, informing the entire network that the link between A and B is in the down state.
Unlike distance vector protocols, the information concerns only the local links (not the routes) connected to the router, and these links are propagated, unchanged, to every other router in the network. Therefore, every router has the same image of the network, created from the original updates from every other router in the network. Sending an update about links is more efﬁcient than sending data about routes, because one link might affect many routes. Sending information about the links allows the routers to compute the routes that might be affected. The resources used are router CPU rather than network bandwidth.
Learning About the Network
The routing protocol develops and maintains the neighbor relationship with routers on the same link by sending a simple hello message across the medium. This is a connection-oriented exchange. After the routers have synchronized their routing tables by exchanging routing updates, they are deemed to be adjacent neighbors.
This neighbor relationship and the subsequent adjacency is maintained as long as the Hello protocol is received. For this to work, the two routers must have the same subnet mask and hello timers. Because the neighbor relationship is continuous, information can be exchanged between the routing processes quickly and efﬁciently. Therefore, link changes in the network are realized very quickly.
A router knows quickly whether the neighbor, who might also be the next hop, is dead, because the router no longer receives Hello protocol messages.
As soon as the routing protocol identiﬁes a problem, it sends out a message immediately, without waiting for the update timer to expire. This is also known as a triggered update. This is an incremental update because it contains only the network change. The incremental update improves convergence time and also reduces the amount of information that needs to be sent across the network. The network overhead on the physical media is eased, allowing more bandwidth for data.
Link-state routing protocols are used in larger networks because the method that they use to update the routing tables requires fewer network resources.
Link-state routing protocols attempt to reduce network overhead by:
■ Using multicast addressing
■ Sending triggered updates
■ Sending network summaries infrequently, if at all
■ Using small packets from every router to describe their local connectivity, instead of the entire routing table
Updating Local Network Tables
A link-state protocol holds a topology database, a network map of every link seen by the routing protocol. The topology database of the network updates the routing table database, after the incremental updates are received and processed. In OSPF, for example, the incremental updates are called link-state advertisements (LSAs). After an update is received and forwarded, the routing protocol computes a new topology database and, from this, a new path. The routing protocol uses the Dijkstra algorithm to achieve this new understanding of the network.
The routing protocol selects the best path to a destination, via the metric. Link-state routing protocols state the metric to be cost, although many vendors supply a default that can be overridden manually. This is true of Cisco’s implementation of OSPF, which uses the inverse of bandwidth as its default.
Examples of link-state routing protocols for IP are OSPF and IS-IS.
Rarely is a name as descriptive as the one given to this protocol, Open Shortest Path First (OSPF). OSPF is an open standard, deﬁned in detail in many RFCs, including RFC 2328. OSPF uses the SPF algorithm to compute the best path to any known destination. OSPF ensures a loop-free topology with fast convergence, although it can use a lot of CPU. OSPF was devised to overcome the limitations of early distance vector protocols, such as RIPv1.
162 Chapter 5: IP Link-State Routing Principles
OSPF, as a link-state routing protocol, is an improvement over a distance vector routing protocol, such as RIPv1, for large networks for the following reasons:
■ It uses bandwidth more efﬁciently by sending incremental updates while requiring greater memory and CPU to calculate the Dijkstra algorithm.
■ The updates are not broadcast as in RIPv1 but are directed to multicast addresses 184.108.40.206 and 220.127.116.11.
■ It propagates changes in the network more quickly with incremental updates and neighbor relationships.
■ It is not limited in size by a maximum hop count of 15.
■ It allows for variation in network design throughout the organization, using VLSM.
■ It has security options, allowing it to use the Message-Digest version 5 (MD5) speciﬁcation.
■ The metric can be deﬁned manually, allowing for greater sophistication in the path determination.
■ It is more responsive to network changes and is ﬂexible in network addressing and design, allowing the network to scale.
OSPF is designed to offer the greatest ﬂexibility in network design. As an open standard, it is required to offer interoperability while allowing the network to grow. These requirements make OSPF a highly complex routing protocol.
To understand this complexity, it is useful to identify the main characteristics of OSPF. These key attributes of OSPF include the following:
■ Maintains adjacent neighbors.
■ Uses hello timers to maintain adjacencies. These are sent every 60 seconds on a WAN and every 10 seconds on LAN. If nothing has been heard from a neighbor within four times the hello timer, the neighbor is declared dead, requiring the generation of an LSA.
■ Sends the minimum amount of information in an incremental update when there has been a change in the network. This allows for fast network convergence. If the network is stable and there have been no updates within 30 minutes, a compressed update is sent.
■ Adds another level of hierarchy to the IP address by designing networks into areas.
■ Is a classless routing protocol.
■ Uses VLSM and both manual and automatic summarization at the IANA class boundary.
■ Uses cost as the metric, deﬁned by Cisco to be the inverse bandwidth; the formula is 108/bandwidth (in bps).
■ Assigns speciﬁc functionality to different routers to streamline the process of communication change in the network.
■ Operates within an organization as an interior routing protocol.
IS-IS and OSPF share many of the same features because they both attempt to solve the limitations in distance vector routing protocols. Like OSPF, IS-IS is a link-state routing protocol that uses the SPF routing algorithm. Both OSPF and IS-IS offer fast convergence, are ﬂexible, and are designed to resist routing loops and to support very large networks.
IS-IS is an integrated protocol. First designed by Digital Equipment Corporation for DECnet Phase V, it became a standard ratiﬁed by the International Standards Organization (ISO). It has a large address space, allowing for incredibly large networks, such as those in the United States government, including the armed forces. The hierarchical design of the protocol allows for this large size in both the interpretation of the address and the transmission of the routing updates. The packet structure was conceived with the intention of allowing the protocol to incorporate enhancements, making it a very ﬂexible protocol.
IS-IS has the following features:
■ It routes CLNP trafﬁc, as deﬁned in the ISO 10589 standard.
■ It routes IP trafﬁc, as deﬁned in RFC 1195.
■ It is a classless routing protocol.
■ It allows VLSM and both manual and automatic summarization at the IANA class boundary.
■ It uses the network design of areas to limit CPU-intensive computation.
■ It uses metric of cost deﬁned by Cisco to be 10 on all media.
■ It assigns functionality to routers to streamline the communication of network change. Level 1 routers deal with interarea updates, whereas Level 2 routers communicate between areas.
■ It sends incremental updates to conserve both bandwidth and CPU, though broadcast media synchronize databases every 10 minutes.
■ It maintains neighbor relations through the Hello protocol, sent every 10 seconds on all media.
■ It considers neighbors dead after 30 seconds of silence.
■ It operates within an autonomous system as an internal routing protocol.
BGP is not a link-state routing protocol. Strictly speaking, it is a path vector routing protocol, which has some of the characteristics of both link-state and distance vector routing protocols. It is an exterior routing protocol and, as such, is completely different from anything seen before. It is included in this comparison chapter on link-state routing protocols because it ﬁts most conveniently here as one of the more complex protocols. The term path vector refers to the list of autonomous system numbers that are carried in the BGP-4 updates. The vector indicates the direction to send the trafﬁc to ﬁnd the path to a remote network. Developed to connect an enormous amount of networks together, BGP is used primarily to connect the Internet and Internet service providers (ISPs).
There are two ﬂavors of BGP: internal BGP (IBGP) and external BGP (EBGP). Essentially, BGP is an external routing protocol used to connect BGP autonomous systems, referred to as EBGP. IBGP is used to send routing information internally across an autonomous system, using it as a transit area to another autonomous system. IBGP needs a fully meshed BGP network, but the routers do not need to be directly connected. BGP updates can be sent to the other BGP routers, or the BGP data trafﬁc can ﬁnd the remote destination by listening to the interior IP routing protocol. Although the remote peer does not have to be directly connected, an entry must be in the routing table of the remote peer for the routers to communicate with each other.
BGP, which is deﬁned in RFC 1771, sends very little information in its updates, which are only sent when there is a change in the network. One of the main goals of BGP is to allow you to determine the path that different types of trafﬁc can take. It is essentially possible to program the routing protocol to allow trafﬁc from one source to take the high road, while other trafﬁc is sent on the low road. This ﬂexibility and the ability to grow the network to large sizes are the main strengths of BGP. This is a very different protocol from the other protocols studied so far, as shown in the following list of characteristics:
■ It is a classless routing protocol.
■ It allows VLSM and both manual and automatic summarization.
■ It sends full routing updates at the beginning of the session.
■ It sends only trigger or incremental updates after the initial setup.
■ It maintains connections between BGP routers by using periodic hellos every 60 seconds. After 180 seconds, the neighbor is declared dead. The Hello protocol is connection-orientated, using TCP, port 179.
■ It uses the hierarchical structure of autonomous systems.
■ It has a complex metric called attributes by which trafﬁc paths can be manipulated.