Overview Of Key Routing Protocol Concepts: Architectures, Protocol Types, Algorithms and Metrics
(Page 3 of 3)
Routing Protocol Algorithms and Metrics
Another key differentiation of routing protocols is on the basis of the algorithms and metrics they use. An algorithm refers to a method that the protocol uses for determining the best route between any pair of networks, and for sharing routing information between routers. A metric is a measure of cost that is used to assess the efficiency of a particular route. Since internetworks can be quite complex, the algorithms and metrics of a protocol are very important, and can be the determining factor in deciding that one protocol is superior to another.
There are two routing protocol algorithms that are most commonly encountered: distance-vector and link-state. There are also protocols that use a combination of these methods, or others.
A distance vector routing algorithm, also called a Bellman-Ford algorithm after two of its inventors, is one where routes are selected based on the distance between networks. The distance metric is something simpleusually the number of hops, or routers between them.
Routers using this type of protocol maintain information about the distance to all known networks in a table. They regularly send that table to each router they immediately connect with (their neighbors or peers). These routers then update their tables and send to their neighbors. This causes distance information to propagate across the internetwork, so that eventually each router obtains distance information about all networks on the internet.
Distance-vector routing protocols are somewhat limited in their ability to choose the best route. They also are subject to certain problems in their operation that must be worked around through the addition of special heuristics and features. Their chief advantages are simplicity and history (they have been used for a long time).
A link-state algorithm selects routes based on a dynamic assessment of the shortest path between any two networks, and is for that reason also called a shortest-path first method. Each router maintains a map describing the current topology of the internetwork. This map is updated regularly by testing reachability of different parts of the internet, and by exchanging link-state information with other routers. The determination of the best route (shortest path) can be made based on a variety of metrics that indicate the true cost of sending a datagram over a particular route.
Link-state algorithms are much more powerful than distance-vector algorithms. They adapt dynamically to changing internetwork conditions, and also allow routes to be selected based on more realistic metrics of cost than simply the number of hops between networks. However, they are more complicated to set up and use more computer processing resources than distance-vector algorithms, and aren't as well-established.
There are also hybrid protocols that combine features from both types of algorithms, and other protocols that use completely different algorithms. For example, the Border Gateway Protocol (BGP) is a path-vector algorithm, which is somewhat similar to the distance-vector algorithm, but communicates much more detailed route information. It includes some of the attributes of distance-vector and link-state protocols, but is more than just a combination of the two.
You may also occasionally see routing protocols categorized by type as static and dynamic, so this is the last concept I want to discuss in this overview. This terminology is somewhat misleading. The term static routing simply refers to a situation where the routing tables are manually set up, so they remain static. In contrast, dynamic routing is the subject of this entire section: the use of routing protocols to dynamically update routing tables. Thus, all routing protocols are dynamic. There is no such thing as a static routing protocol unless you consider a network administrator editing a routing table a protocol.
Home - Table Of Contents - Contact Us
The TCP/IP Guide (http://www.TCPIPGuide.com)
Version 3.0 - Version Date: September 20, 2005
© Copyright 2001-2005 Charles M. Kozierok. All Rights Reserved.
Not responsible for any loss resulting from the use of this site.