Bellman Ford's Algorithm
Contributed by Madhusudhan N

Bellman Ford's Algorithm:

Distance Vector routing algorithm (DV):

DV is a decentralized routing algorithm, that requires that each router simply inform its neighbors of its routing table. For each network path, the receiving routers pick the neighbor advertising the lowest cost, then add this entry into its routing table for re-advertisement. To find the shortest path, DV is based on one of two basic algorithms: the Bellman-Ford (RIP) and the Dijkstra algorithms (OSPF).

In RIP (The Routing Information Protocol), DV is known as the "Bellman-Ford" algorithm (1957) or Ford-Fulkerson Algorithm (1962), after its inventors. It is used in many routing protocols in practice, including Internet BGP, ISO IDRP, NOVELL IPX, and the original ARPANET. Currently, Appletalk and Cisco are also used this algorithm.

Main Features of DV:

DV algorithm is iterative, asynchronous, and distributed.
1.Distribution: This algorithm enables each node receives some information from one or more of its directly attached neighbors.
2.Iteration: The process of exchanging information will continue until no more information is exchanged between the neighborhood.
3.Asynchronous: This algorithm does not require all of the nodes to operate in lock step with each other

What is RIP?

RIP is a distance-vector protocol that allows routers to exchange information about destinations for computing routes throughout the network. Destinations may be networks or a special destination used to convey a default route. In RIP, Bellman-Ford algorithms make each router periodically broadcast its routing tables to all its neighbors. Then a router knowing its neighbors' tables can decide to which destination neighbor to forward a packet.

How Bellman-Ford algorithm works:

Routers that use this algorithm have to maintain the distance tables (which is a one-dimension array -- "a vector"), which tell the distances and shortest path to sending packets to each node in the network. The information in the distance table is always updated by exchanging information with the neighboring nodes. The number of data in the table equals to that of all nodes in networks (excluded itself). The columns of table represent the directly attached neighbors whereas the rows represent all destinations in the network. Each data contains the path for sending packets to each destination in the network and distance/or time to transmit on that path (we call this as "cost"). The measurements in this algorithm are the number of hops, latency, the number of outgoing packets, etc.

Formal algorithm:

· The starting assumption for distance-vector routing is each node knows the cost of the link of each of its directly connected neighbors. Next, every node sends a configured message to its directly connected neighbors containing its own distance table. Now, every node can learn and update its distance table with cost and next hops for all nodes network. Repeat exchanging until no more information between the neighbors.
· Consider a node X that is interested in routing to destination Y via a directly attached neighbor Z. Node X's distance table entry, Dx(Y,Z) is the sum of the cost of the direct-one hop link between X and Z, c(X,Z), plus neighboring Z's currently known minimum-cost path (shortest path) from itself(Z) to Y. That is
Dx(Y,Z) = c(X,Z) + minw{Dz(Y,w)} The minw is taken over all the Z's
This equation suggests that the form of neighbor-to-neighbor communication that will take place in the DV algorithm - each node must know the cost of each of its neighbors' minimum-cost path to each destination. Hence, whenever a node computes a new minimum cost to some destination, it must inform its neighbors of this new minimum cost.

Simpler algorithm:

· send my routing table to all my neighbors whenever my link table changes
· when I get a routing table from a neighbor on port P with link metric M:
1. add L to each of the neighbor's metrics
2. for each entry (D, P', M') in the updated neighbor's table:
1. if I do not have an entry for D, add (D, P, M') to my routing table
2. if I have an entry for D with metric M", add (D, P, M') to my routing table if M' < M"
if my routing table has changed, I send all the new entries to all my neighbors

Potential Problems:

Counting to infinity This condition continuously loops packets around the network, despite the fundamental fact that the destination network is down. While the routers are counting to infinity, the invalid information allows a routing loop to exist.

Routing Loops Routing Loops can occur if the internetwork's slow convergence on a new configuration causes inconsistent routing entries."

Implemented Solutions:

Split Horizon - "If you learn a protocol's route on an interface, do not send information about that route back out that interface."

Split Horizon causes the node to not advertise routes to a node that have that node as their next stop. Thus two nodes would not create loops that involve packets bouncing back and fourth. This eliminates routing loops with only two nodes. But if the loops involves more that two it is not as effective.

Defining a Maximum --"Specify a maximum distance vector metric as infinity."

Hold Down Timers or Hold down--"Routers ignore network update information for some period."

Hold downs are ways to try to eliminate larger routing loops. What a hold downs does is when a node eliminates a node from its table it initiates a hold downs so no new entries can be accepted for that node for a specific period of time. This helps to keep that node from being a member of the loop.

Route poisoning -- "Router keeps an entry for the network down state, allowing time for other routers to recompute for the topology change."

This is a form of split horizon where instead of not telling the node about the path, if the route passes through a node when you advertise to that node you tell it that the route is unreachable.

Triggered update

Triggered updates follow the idea that a lot of network traffic for a few seconds is worth having correct routes. Whenever a route is changed in the nodes routing table an update containing the new information for the changed route is send to all the neighboring nodes so they can be informed of the change. This causes a flood of update packets that eventually calm down to correct routes much quicker than the other methods.

Simulation of Bellman's Algorithm

 

1. FDDI Frequently Asked Questions (FAQ)

2. The function and frame format of FDDI.

3. Aloha

4. Comparative analysis between two types of ATM Switches
a) The Knockout Switch
b) The Barcher-Banyan Switch

5. Various popular standards for compressing multimedia data

6. Distributed Multimedia Survey: Standards

7. ASCII to hex value chart

8. Comparative analysis - TCP - UDP

9. Addressing Formats and QoS parameters

10.Bellman Ford's Algorithm