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 readvertisement. To find
the shortest path, DV is based
on one of two basic algorithms:
the BellmanFord (RIP) and the
Dijkstra algorithms (OSPF).
In RIP (The Routing Information
Protocol), DV is known as the
"BellmanFord" algorithm
(1957) or FordFulkerson 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.
 Distribution: This algorithm
enables each node receives some
information from one or more
of its directly attached neighbors.
 Iteration: The process of
exchanging information will
continue until no more information
is exchanged between the neighborhood.
 Asynchronous: This algorithm
does not require all of the
nodes to operate in lock step
with each other
What is RIP?
RIP is a distancevector 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, BellmanFord 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 BellmanFord algorithm
works:
Routers that use this algorithm
have to maintain the distance
tables (which is a onedimension
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 distancevector 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
directone hop link between
X and Z, c(X,Z), plus neighboring
Z's currently known minimumcost
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 neighbortoneighbor
communication that will take
place in the DV algorithm 
each node must know the cost
of each of its neighbors' minimumcost
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.
