# The Bellman Ford Algorithm Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Bellman-Ford Algorithm and the Protocols That Use It. How do routers make their decisions? Routers make their decisions based on 2 different types of dynamic routing protocols. Dynamic routing protocols use metrics of bandwidth, hop count, load, delay, reliability or cost. The type of dynamic protocol that I am going to discuss is distance vector routing protocols that use the Bellman-Ford Algorithm. In the name distance vector distance refers to how far and vector is a representation of the logical line between the hops. Distance vector routing protocols determine the path on distance. Bellman- Ford distance vector routing protocols aren't capable of measuring bandwidth, reliability, load, delay, like the other dynamic routing protocols. Distance vector routing protocols using the Bellman-Ford algorithm choose the lowest-cost path or lowest hop count (Distance Vector Routing and Protocols). RIP is one of the most popular routing protocols that use the Bellman-Ford algorithm.

Distance Vector routing protocols rely on Algorithms to determine the lowest-cost path. There are several Algorithms out there. The one that I am focusing on is the Bellman-Ford algorithm. It was written in the 50's and is still in full force today.

The Bellman ford algorithm was written by Richard Bellman and Lester Ford Jr. Richard Bellman had a Ph.D. from Princeton and was a pioneer for Dynamic Programming. He was a mathematical genius that had an incredible amount of publications. 'For example the paper [3] list 621 papers, 41 books and 21 translations of books authored (or co-authored) by Bellman' on mathematics (O'Connor & Robertson, 2005)

Lester Ford Jr. the other man who helped create the Bellman- ford algorithm was an American mathematician who was a specialist in network flow problems. He was co author to the Ford-Fulkerson algorithm in addition to the Bellman-Ford algorithm.

The Bellman-Ford algorithm is an efficient way to solve for the shortest paths from a specific source vertex to every other vertex in a weighted digraph. Let's break that down into network terms. There is a small office network with 6 routers. In that network the source vertex would be Router 1 and every other vertex would be rest of the routers that Router 1 is connected to. The weighted graph would represent a logical representation of the network that Router 1 is on. So, what is the hop count to every other router from Router 1 in the network? The algorithm finds out the answer to that question and builds a routing table based on what it finds (Black, 2009)

The images above are an example of a simple network and what a bellman-ford table for it might look like. The top row of the graph represents the destination router. The row on the left side represents the source router. The numbers on the graph represent the amount of hops and the letters next to the numbers represent the next hop router. ( (Madhusudhan) (Doyle, 2001).

Each router will keep a list of all known routes in the table. Each entry in the table identifies a destination network and the distance from the router with the table to every destination in the network measured in hops. Every once in a while every router on the network will send a copy of its routing table to all the neighbor routers that they have direct connections to. During the time that the routers share information if a router gets a route that it doesn't know it will add it to the table. If a router has a table shared with it and that table has a lower hop count to another router, it will add that route to its table replacing what it had with n+1. For n+1 n is equal to the amount of hops on the route being shared and +1 is to compensate for the hop between the receiver of the shared table and the router sharing the table. If a router that is sharing its table with a neighbor has a route through itself from the neighbor and it changes the neighbors table will be updated to reflect the change and will apply (Comer, 2006)

So now that we have an understanding of how the Bellman-Ford algorithm works let's examine a protocol that uses the algorithm. RIP (Routing Information Protocol) is based off of a BSD (Berkeley Science Distribution) application called 'routed'. RIP-1 'was the first routing protocol accepted as the standard for TCP/IP' (Dynamic Routing Protocols, 2003). It was designed for smaller IP based networks and has become the de facto standard for exchange of routing information between routers and hosts ( (Hedrick, 1988). RIP is good for smaller networks because the routing isn't as complex and accounting for things such as bandwidth are not as important. Also RIP only supports a maximum of 15 hops which wouldn't scale well on large networks. Some say that RIP has become obsolete due to protocols such as OSPF and IS-IS.RIP does have an advantage on a smaller network though. One advantage is that the amount of overhead created by RIP is low compared to other protocols and the amount of configuration and management time is also minimal. If you had a large network the overhead would be very large with some more advanced protocols (Malkin, 1998)RIP is the most compatible routing protocol out there. It is supported by all routing devices, so it may be the only option for some dynamic routing environments.

Communication between neighboring routers is a fundamental distance vector protocol ability which allows its routing table to grow. The sharing between routers has led to distance vector routing being labeled as 'routing by rumors' because of how information is learned.

The RIP updates are sent in an IP datagram on port 520. A RIP entry is the second through the sixth line. The RIP-1 IP datagram can contain up to 25 RIP entries each for a different destination address (Kozierok). There are several different kinds of commands that happen in the RIP IP datagram. The first is a request for 'either a partial or full table update from another RIP router.' The second is a response to the request for a table. Another command is trace on/trace off which has become obsolete and not used anymore. Then there is the reserved command which is only used by Sun Microsystems who uses it for its own purpose. The Version field contains the version of RIP that is being used. Address Family ID tells what kind of network addressing is being used (IP, IPX, etc.). The Metric field contains the amount of hops. The IP address field represents the destination address that the information is being sent about. The IP address field can contain a network ID, subnet or a host because no distinction is made between different types of devices on RIP-1. The zeroes fields are not used in RIP-1 but

RIP has a series of timers that it uses. The update timer sets the time for broadcasting a full list of all the routes known 30 seconds. When a RIP router receives a broadcast message it runs the Bellman-Ford algorithm to create a list of routes and their lowest hop counts. The hold- down timer is a way for RIP to prevent routing loops. If a route becomes unreachable the hold-down timer starts. If the timer reaches 90 seconds the route is removed from the table (The hold-down timer is not part of the RFC standard for RIP. It's a Cisco thing). If new route information comes in during the countdown then the new route is added to the table. The timeout timer is the 'Interval a route should stay 'live' in the routing table. This counter is reset every time the router hears an update for this route.' The RIP flush timer 'controls how long before a route is completely flushed from the routing table' (Routing Information Protocol (RIP)) .

RIP-2 is the second version of RIP that has some improvements of RIP-1. RIP-1 does not support classless addressing because when it was developed IP subnets had not been formally introduced. RIP-1 is able to use subnets 'through the use of a heuristic to determine if the destination is a network, subnet or host. However, there was no way to clearly specify the subnet mask for an address using RIP-1 messages.' RIP-2 adds support for subnets and VLSM by allowing for a subnet mask to be added to the route entry. RIP-2 has added a next hop specification. This feature allows for RIP to traverse through routers that are not running RIP. A router that is not using RIP can be selected as the Next Hop regardless of the protocols being used on it. A security measure added to RIP-2 is authentication. In RIP-1 a malicious host could poison the routes. RIP-2 has added an authentication measure to gain the identity of a router before it receives messages from it. RIP-2 has added a Route Tag which gives more information about where a route was to help identify where the route updates are learned from. Lastly RIP-2 has added Multicasting support to decrease overhead and to keep from sending unsolicited messages (Kozierok)

The Bellman-Ford algorithm has been a very helpful algorithm to aid in their development of distance vector routing protocols. The Bellman-Ford algorithm is behind the well know protocol RIP. RIP has many different implementations in the past and has a couple newer versions to help keep it up to date.