Side_1_360

2.3 Distance-vector and Link-state

Routing

The two fundamental routing algorithms in
IP networks are distance-vector and link-state
routing.

Both algorithms assume that a router knows

• the address of each neighbour, and


• the cost of reaching each neighbour (where the
  cost measures quantities like the link’s capac-
  ity, the current queuing delay, or a per-packet
  charge).

Both algorithms allow a router to find global
routing information, that is, the next hop to reach
every destination in the network by the shortest
path, by exchanging routing information with
only its neighbour. In the following, we will give
a brief introduction to these two algorithms.
More details can be found in many places in the
literature, such as [HUIT00].

2.3.1 Distance-vector Routing
In distance-vector routing, we assume that each
router knows the identity of every other router in
the network (but not necessarily the shortest path
to it). Each router maintains a distance vector,
which is a list of <destination, cost> tuples, one
tuple per destination, where cost is the current
estimate for the sum of the link costs on the
shortest path to that destination. Each router ini-
tialises the cost to reach all non-neighbour nodes
to a value higher than the expected cost of any
route in the network (commonly referred to in
the routing literature as infinity). A router sends
a copy of its distance vector to all its neighbours.

When a router receives a distance vector from

a neighbour, it determines whether its cost to

reach any destination would decrease if it routed

packets to that destination through that neigh-

bour (Figure 2.1). It can easily do so by compar-

ing its current cost to reach a destination with

the sum of the cost to reach its neighbour and

its neighbour’s cost to reach that destination.

With the continued exchange of distance vec-

tors, the cost of every link is eventually known

throughout the network. The distance-vector

algorithm is also called Bellman-Ford

([BELL57], [FF62]) after its creators.

The distance-vector algorithm works well if

nodes and links are always up, but it runs into

many problems when links go down or come up.

The root cause of problems is that when a node

updates and distributes a distance vector, it hides

the sequence of operations it used to compute

the vector. Thus, downstream routers do not

have sufficient information to figure out whether

their choice of a next hop will cause loops to

form. One typical problem is count-to-infinity

[KESH97]. Solutions to this problem can be

found in many places in the routing literature

(e.g. [HUIT00]).

2.3.2 Link-state Routing

In distance-vector routing, a router knows only

the cost to each destination or, sometimes, the

path to the destination. This cost of path is partly

determined on its behalf by other routers in the

network. This hiding of information is the cause

of many problems with distance-vector algo-

rithms.

Figure 2.1 Distance-vector

algorithm at node A. In the

figure, A receives a distance

vector from its neighbours B

and D. It uses this information

to find that it can reach nodes

C and E at a lower cost. It

therefore updates its own

distance vector and chooses

B as its next hop to nodes C

and E

Computation at A when Distance Vectors from B

and D arrive

1. Cost to destinations via B = Cost to go to B + Cost to
   destinations from B = (1,1,1,1,1) + (1,0,2,∞,4) =
   (2,1,3,∞,5)


2. Cost to destinations via D = Cost to go to D + Cost to
   destinations from D = (3,3,3,3,3) + (3,∞,∞,0,6) =
   (6,∞,∞,3,9)


3. Current cost from A = (0,1,∞,3,∞)
   Minimum cost to destinations = (0,1,3,3,5)

Initial

E ∞^4560

D^3 ∞^ ∞^06

C ∞^20 ∞^5

B^102 ∞^4

01 ∞ 3 ∞

ABCDE

A B C

D E

12

6

5

34

A