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 efficient 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 efficiently . 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 identifies 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. Path Selection 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. OSPF Rarely is a name as descriptive as the one given to this protocol, Open Shortest Path First (OSPF). OSPF is an open standard, defined 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. 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 efficiently 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 224.0.0.5 and 224.0.0.6. -
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) specification. -
The metric can be defined manually, allowing for greater sophistication in the path determination. -
It is more responsive to network changes and is flexible in network addressing and design, allowing the network to scale. OSPF is designed to offer the greatest flexibility 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, defined by Cisco to be the inverse bandwidth; the formula is 10 8 /bandwidth (in bps). -
Assigns specific 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 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 flexible, 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 ratified 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 flexible protocol. IS-IS has the following features: -
It routes CLNP traffic, as defined in the ISO 10589 standard. -
It routes IP traffic, as defined 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 defined 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-4 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 fits 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 traffic to find 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 flavors 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 traffic can find 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 defined 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 traffic can take. It is essentially possible to program the routing protocol to allow traffic from one source to take the high road, while other traffic is sent on the low road. This flexibility 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 traffic paths can be manipulated. Convergence Each routing protocol has a different method of updating the routing table, affecting the time to converge the routing tables. Some new concepts are introduced in the following comparison. The concepts are explained in depth in the chapters that concentrate on the specific protocols. OSPF Convergence The steps for OSPF convergence are as follows : -
When a router detects a link failure, the router sends an LSA to its neighbors. If the router is on a multiaccess link, it sends the update to the designated router (DR) and the backup designated router (BDR), not to all neighbors. -
The path is removed from the originating router's tables. -
On receipt of the LSA, all routers update the topology table and flood the LSA out its interfaces. -
The routing protocol runs the Dijkstra algorithm to rebuild the routing table. For OSPF, convergence is detection time, plus LSA flooding, plus 5 seconds before computing the topology table. This amounts to a few seconds. IS-IS Convergence The steps for IS-IS convergence are as follows: -
When a router detects a link failure, an LSP is sent to its neighbors. If the router is on a multiaccess link, the update is sent to the designated intermediate system (DIS the IS-IS term for a designated router), not to all neighbors. -
The path is removed from the originating router's tables. -
On receipt of the LSP, all routers update the topology table and flood the LSP out its interfaces, except for the interface that received the LSP. -
Each router runs the Dijkstra algorithm to rebuild the forwarding table. For IS-IS, convergence is detection time, plus LSP flooding. The time to converge the network amounts to a few seconds. If convergence is deemed to be the topology table being updated, this could take longer. BGP Convergence BGP convergence is different, depending on whether IBGP or EBGP is being run. Reliability is far more important to EBGP than how long it takes to update the routing table, whereas IBGP needs to ensure a faster convergence to remain synchronized with the interior routing protocol. When a neighbor is no longer available, the BGP router tries to reconnect to its neighbor. If this fails, the session is formally closed and the information from the router is removed from the database. An update is sent to all neighbors. |
