ROUTING ALGORITHMS

ROUTING ALGORITHMS
• Software responsible or deciding which output
line an incoming packet should be sent.
• Done for every arriving packet (datagram
subnet)
• Made only during connection setup (virtual
circuit subnet) – session routing
 ROUTING ALGORITHMS
• Router have two processes:
• Routing - filling and updating of routing tables
• Forwarding – looks for outgoing link in routing
table and forwards the packet
 ROUTING ALGORITHMS
• Properties of Routing algorithm:
• Correctness
• Simplicity
• Robustness
• Fairness
• Optimality
 ROUTING ALGORITHMS
• Principle of optimality – states that if a router
J is on the optimal path from router I to router
K, the optimal path from J to K also falls along
the same route.
ROUTING ALGORITHMS

(a) A subnet. (b) A sink tree for router B.

 ROUTING ALGORITHMS
• Sink tree
– Set of optimal routes from all sources to a given
destination from a tree routed at the destination.
– not unique (other trees with same path lengths
may exist)
– No loops
 ROUTING ALGORITHMS
• SHORTEST PATH ROUTING
• Metrics:
• Number of hops
• Distance
• Delay
• Bandwidth
• Load
 ROUTING ALGORITHMS
• ‘Dijkstra's algorithm’
– Uses distance to find the shortest path
– Ex., Mark source node(A) as permanent and
examine each of the nodes adjacent to A,
relabeling each one with the distance to A.
– Also examine all the tentatively labeled nodes in
the whole graph and make the one with the
smallest label permanent.
– This one becomes the new working node.
ROUTING ALGORITHMS
 ROUTING ALGORITHMS

• FLOODING
• Every incoming packet is sent out on every outgoing
line except the one it arrived on.
• Problem:
• generates too many duplicate packets
• Solution:
• hop counter be contained in header of each packet, which is
decremented at each hop and discarded when counter becomes
zero.
• Sequence numbering
• Selective flooding:
• Send incoming packets to only those lines that are going
approximately in the right direction.
 ROUTING ALGORITHMS
• Uses
• Military applications
– Where robustness is needed
• Distributed databases
– multiple sources
– update all at once
 ROUTING ALGORITHMS
FLOW BASED ROUTING
• Above algorithms only consider topology
– Do not consider load

 Ex: if huge traffic from A to B then better path would be

AGEFC
 ROUTING ALGORITHMS
• Considers both topology and load for routing
• Basic idea behind the analysis for a given line
– If the capacity and average flow are known, it is
possible to compute the mean packet delay on that
line from queueing theory.
– From the mean delay on all the lines, flow weighted
average is calculated to get the mean packet delay for
the whole subnet.
– The routing problem then reduces to find the routing
algorithm that produces the min. avg delay for the
subnet.
 ROUTING ALGORITHMS
• To use this technique, certain info. must be
known in advance
– Subnet topology
– Traffic matrix,Fij
– Line capacity matrix, Cij, specifying the capacity of
each line in bps.
• Finally a routing algorithm must be chosen
 ROUTING ALGORITHMS
• DISTANCE VECTOR ROUTING
• Every router maintain a table (i.e. a vector) which
gives the best known distance to each destination
and which line to use.
• Tables are updated by exchange of information with
neighbors.
• Commonly known as Bellman-Ford routing and Ford-
Fulkerson algorithm.
 ROUTING ALGORITHMS
• Router maintains a routing table containing
one entry for each router in the subnet.
• This entry contains two parts: the preferred
outgoing line to use for that destination, and
an estimate of the time or distance to that
destination.
• Metric might be number of hops, time delay in
milliseconds, total number of packets queued
along the path etc.
 ROUTING ALGORITHMS
• Ex., consider delay is used as a metric and that
the router knows the delay to each of its
neighbours.
• Once every T msec, each router sends to each
neighbour a list of its estimated delays to each
destination
• It also receives a similar list from each
neighbour.
 ROUTING ALGORITHMS
• In the fig., the first four columns of part b
shows the delay vectors received from the
neighbours of router J.
• A claims to have a 12 msec delay to B, a 25
msec delay to C, a 40 msec delay to D etc.
• Suppose that J has measured its delay to its
neighbours, A,I,H and K as 8, 10, 12 and 16
msec respectively.
ROUTING ALGORITHMS
 ROUTING ALGORITHMS
• Consider how J computes its new route to router
G.
• It knows that it can get to A in 8 msec, and A
claims to be able to get to G in 18 msec, so J
knows it can count on a delay of 26 msec to G if it
forwards packets bound for G to A.
• Similarly , it computes the delay to G via I,H and K
as 41(31+10), 18 (6+12) and 37(31+6) msec
respectively.
• The best of these values is 18 msec, and that the
route to use is via H.
 ROUTING ALGORITHMS
• Example –consider the five node subnet of the
previous fig. a, where the delay metric is the
number of hops.
• Suppose A is down initially and all the other
routers know this (ie., all the others have
recorded the delay to A as infinity).
• When A comes up, other routers learn about
it via the vector exchanges.
 ROUTING ALGORITHMS
The Count –to-Infinity Problem
Reacts quickly to good news
 ROUTING ALGORITHMS
• At the time of first exchange, B learns that its left
neighbour has zero delay to A.
• B now makes an entry in its routing table that A is
one hop away to the left.
• All the other routers still think that A is down.
• On the next exchange, C learns that B has a path
of length 1 to A, so it updates its routing table to
indicate a path of length 2 , but D and E do not
hear it.ie., this good news is spreading at the rate
of one hop per exchange.
 ROUTING ALGORITHMS
• In fig. b, all the lines and routers are initially up.
• Routers B,C, D and E have distances to A of 1,2,3, and 4 respectively.
• Suddenly A goes down, or alternatively, the line b/w A and B is cut,
which is effectively the same thing from B’s point of view.
• At the first package exchange, B does not hear anything from A.
• Fortunately C says to B not to worry and it has a path to A of length 2.
• But B does not know that C runs thru itself.
• B now thinks it can reach A via C, with a path length of 3.
• D and E do not update their entries for A on the first exchange.
• On the second exchange, C notices that each of its neighbours claims
to have a path to A of length 3.
• It picks one of them at random and makes its new distance to A as 4
etc.
 ROUTING ALGORITHMS

Reacts slowly to bad news : Count to Infinity

 ROUTING ALGORITHMS
• Solution: Count to Infinity
• The Split Horizon Hack
• The distance to X is not reported on the line that packets
for X are sent on.
• Example, in the previous fig., C tells D the truth about the
distance to A, but C tells B that its distance to A is infinite.
• Similarly, D tells the truth to E but lies to C.
• For ex., when A goes down, on the first exchange, B
discovers that the direct line is gone, and C is reporting an
infinite distance to A as well.
 ROUTING ALGORITHMS
• Since neither of its neighbours can get to A, B sets its distance
to infinity as well.
• On the next exchange, C hears that A is unreachable from
both of its neighbours, so it marks A as unreachable too.
• Using split horizon, the bad news propagates one hop per
exchange
• This rate is much better than without split horizon.
 ROUTING ALGORITHMS
• LINK STATE ROUTING
• Each router must do the following:
1. Discover its neighbors, learn their network address.
2. Measure the delay or cost to each of its neighbors.
3. Construct a packet telling all it has just learned.
4. Send this packet to all other routers.
5. Compute the shortest path to every other router.
 ROUTING ALGORITHMS
• Learning about the neighbors
• HELLO Packets are used by the routers on each point to point
line
• Router on the other end sends back the reply telling who it is.
• Names must be globally unique
• Measuring line cost
• ECHO Packets are used by the routers to know the delay of
each of its neighbours.
• By measuring round trip time and dividing by two, the sending
router can get a reasonable estimate of the delay.
• Test can be conducted several times and the avg can be used.
 ROUTING ALGORITHMS

• Building Link State Packets

• Each router has to build a packet containing all the data.
• The packet starts with the identity of the sender, followed by a
sequence number and age and a list of neighbors.
• For each neighbor, the delay to that neighbor is given.
• An example subnet is given in the fig. a, with delays shown in the
lines.
• The corresponding link state packets for all six routers are shown in
fig. b.
 ROUTING ALGORITHMS
• Building the link state packets is easy.
• Hard part is determining when to build them.
• One possibility is to build them periodically,
that is, at regular intervals.
• Another possibility is when some significant
event occurs, such as a line or neighbour
going down or coming back up again, or
changing its properties appreciably.
 ROUTING ALGORITHMS
• Distributing the Link State Packets:
• Use flooding to distribute the link state packets.
• Routers keep track of all the (source router, sequence)
pairs they see.
• When a new link state packet comes in, it is checked
against the list of packets already seen.
• If it is new, it is forwarded on all lines except the one it
arrived on.
• If it is a duplicate, it is discarded.
 ROUTING ALGORITHMS
• Computing the new routes
• Dijkstra’s shortest path algorithm
• The results of this algorithm can be installed in the
routing tables, and normal operation resumed.
• Memory store required
• Subnet of n routers, each router with k neighbors
requires k.n
 ROUTING ALGORITHMS
• Hierarchical Routing
– Routers are divided into regions , with each router
knowing all the details about how to route packets to
destinations within its own region, but knowing
nothing about the internal structure of other regions.
– When different networks are connected together,
each one is considered as a separate region.
– For huge n/ws, a two level hierarchy is insufficient –
regions are grouped into clusters, clusters into zones,
zones into groups etc.
 ROUTING ALGORITHMS
• Other routing algorithms are
• Routing for mobile hosts
• Broadcast routing
• Mulitcast routing