Link State and Distance Vector Routing Algorithms
Finally, much controversy surrounds the debate over link state versus distance vector routing algorithms. Link state algorithms (also known as shortest path first algorithms) flood routing information to all nodes in the internetwork. However, each router sends only that portion of the routing table that describes the state of its own links, as opposed to its entire routing table.
Distance vector algorithms (also known as Bellman-Ford algorithms) call for each router to send its entire routing table, but only to its neighbors.
In essence, link state algorithms send small updates everywhere; distance vector algorithms send large updates only to neighboring routers.
Because they create a consistent view of the internetwork, link state algorithms are somewhat less prone to routing loops than are distance vector algorithms. On the down side, link state algorithms can cause significant, widespread control traffic. They are also computationally difficult compared to distance vector algorithms, requiring more CPU power and memory than distance vector algorithms. Link state algorithms can therefore be more expensive to implement and support. Despite their differences, both algorithm types perform well in most circumstances.
As alluded to previously, routing tables contain information used (by switching software) to select the best route. How, specifically, are routing tables built? What is the specific nature of the information they contain? This section on algorithm metrics attempts to answer the following question: How do routing algorithms determine that one route is preferable to others?
Many different metrics have been used in routing algorithms. Sophisticated routing algorithms can base route selection on multiple metrics, combining them in a manner resulting in a single (hybrid) metric. All of the following metrics have been used:
Reliability, in the context of routing algorithms, refers to the reliability of each network link. Some network links might go down more often than others.
After they go down, some network links can be repaired more easily or more quickly than other links. Any reliability factors can be taken into account in the assignment of reliability ratings. Reliability ratings are usually assigned to network links by network administrators. They are typically arbitrary numeric values based on factors such as circuit speed, traffic patterns, and overall network design considerations.
Routing delay refers to the length of time required to move a packet from source to destination through the internetwork. Delay depends on many factors, including the bandwidth of intermediate network links, the port queues at each router along the way, network congestion on all intermediate network links, and the physical distance to be traveled. Because it is a conglomeration of several important variables, delay is a common metric.
Bandwidth refers to the available traffic capacity of a link. A 10Mbps Ethernet link, for instance, would be preferable to a 64Kbps leased line. Although bandwidth is a rating of the maximum attainable throughput on a link, routes through links with greater bandwidth do not necessarily provide better routes than routes through slower links. If, for example, a faster link is much busier, the actual time required to send a packet to the destination could be greater through the fast link.
Load refers to the degree to which a network resource (such as a router interface or circuit) is busy. Load can be calculated in a variety of ways, including CPU utilization, actual/available, and packets processed per second. Monitoring these parameters on a continual basis can itself be resource intensive.
Maximum Transfer Unit (MTU)
MTU (Maximum Transfer Unit) refers to the maximum size of a packet that can traverse a particular network link. For example, an Ethernet network can handle frames as large as roughly 1.5 Kilobytes (KB). FDDI can handle frame sizes up to roughly 4KB. Token Ring networks do not specify frame size limits (practical Token Ring limits are introduced by the maximum token-hold time).
Communication cost is another important metric. Some companies might not care about performance as much as they care about operating expenditures. Although line delay might be longer, they will send packets over their own lines rather than through public lines that will cost money for usage time.
Distance Vector Protocols
This section details the type of routing protocols known as distance vector protocols. The basic characteristics that each must have to classify as a distance vector and what these mean to you and your network operations will be discussed.
Distance vector protocols have often been referred to as Bellman-Ford because they are based on a shortest path first computation algorithm described by R.E. Bellman, and the first description of the distributed algorithm is attributed to Ford and Fulkerson.
Distance vector means that information sent from router to router is based upon an entry in a routing table consisting of the distance and vector to destinationdistance being what it costs to get there and vector being the path.
Distance vector protocols have been used in several networks, such as the early ARPANET. This and other early implementations were the basis for the development of RIP.
Distance vector algorithms are a class of routing algorithms that iterate on the number of hops in a route to find the shortest path. Distance vector routing algorithms call for each router to send its entire routing table in each update, but only to its neighbors. Distance vector routing algorithms can be prone to routing loops, but are computationally simpler than link state routing algorithms.
This chapter concentrates on the RIP distance vector protocol to demonstrate and correlate how OSPF has improved on RIP. This will help introduce some of the fundamental characteristics of these types of protocols.