Network Routing Algorithms

Network Performance Measures

• Two Performance Measures

– Quantity of Service (Throughput)
• How much data travels across the net?
• How long does it take to transfer long files?
– Quality of Service (Average packet delay)
• How long does it take for a packet to arrive at its
destination?
• How responsive is the system to user commands?
• Can the network support real-time delivery such as
audio and video?
Fairness versus Optimality
• Quantity of service versus
quality of service.
• To optimize throughput,
saturate paths between A
and A’, B and B’, and C
and C’, but what happens
to the response time from
X to X’?
 Types of Routing Algorithms
• Nonadaptive (static)
– Do not use measurements of current conditions
– Static routes are downloaded at boot time
• Adaptive Algorithms
– Change routes dynamically
• Gather information at runtime
– locally
– from adjacent routers
– from all other routers
• Change routes
– Every delta T seconds
– When load changes
– When topology changes
 Optimality principle

• If router j is on the optimal path from i to k,

then the optimal path from j to k also falls
along the same route.

(j)
k
i

(j)
(j)
Sink Trees
• The set of optimal
routes to a particular
node forms a sink tree.
• Sink trees are not
necessarily unique
• Goal of all routing
algorithms
– Discover sink trees for
all destinations
 Shortest Path Routing
(a nonadaptive routing algorithm)

• Given a network topology and a set of

weights describing the cost to send data
across each link in the network
• Find the shortest path from a specified
source to all other destinations in the
network.
• Shortest path algorithm first developed by
E. W. Dijkstra
 Shortest Path Routing
(a nonadaptive routing algorithm)
Mark the source node as permanent.
Designate the source node as the working node.
Set the tentative distance to all other nodes to infinity.
While some nodes are not marked permanent
Compute the tentative distance from the source to all nodes
adjacent to the working node. If this is shorter than the current
tentative distance replace the tentative distance of the
destination and record the label of the working node there.

Examine ALL tentatively labeled nodes in the graph. Select

the node with the smallest value and make it the new working
node. Designate the node permanent.
Example of Shortest Path Routing
 Why the Shortest Path Algorithm Works
B
E
A

• Perhaps A*ZE is a better path to E than ABE

• Two cases
1.) If Z is permanent, then we have already checked A*ZE
2.) If Z is tentatively labeled, paths to Z must be longer
than paths to E, otherwise Z would have been made
permanent
 Flooding
(a nonadaptive routing algorithm)

• Brute force routing

– Every incoming packet is sent on every outgoing line
– Always finds the shortest path quickly
– Also finds many long paths
– Time to live is set to size of subnet
• Selective Flooding
– Flood only in the direction of the destination
• Practical in a few settings
– Military Applications
– Distributed Databases
– Metric for comparison
 Flow-based Routing
(a nonadaptive routing algorithm)
B H
D E
A
G
C
F

• This algorithm uses both topology and load

for routing .
• If suppose there is huge traffic from A to B
then it is better to route the traffic from A to
C.
• Such an algorithm is called FLOW BASED
ROUTING.

• The basic idea for this algorithm is that for

a given line ,if the capacity and average
flow are known , it is possible to compute
the mean delay on that line.
• To use this technique certain information
should be known in advance.
• First the subnet topology must be known.
• Second the traffic matrix Fij must be
known.
• Third the capacity of the line must be
known.
• Finally a routing algorithm must be chosen.
• Queuing theory formula
• T=1/ µC-λ
• T=Mean delay time
• 1/µ-mean packet size
in bps
• C is the capacity of
the channel in kbps
• λ-is the mean flow of
packets/sec
• 1/µ=800 bits
 Analyzing Network Flow
(Optimize for mean delay)

Mean delay is Ti = 1/uCi - lambdai Weight is the percent of packet

where 1/u is mean packet size in bits traffic that traverses this path.
Ci is capacity in kbps Mean delay is weighted average of T.
lambdai = mean flow in packets/sec Recalculate mean delay for all possible routes.
 Distance Vector Routing
(an adaptive routing algorithm)

• Bellman-Ford Routing
• Ford Fulkerson Algorithm
• Original ARPANET routing algorithm
• Previously used on Internet (RIP)
• Early version of DecNet and Novell’s IPX
• AppleTalk and Cisco routers use improved
versions of this algorithm
 Distance Vector Routing
(an adaptive routing algorithm)

• Neighboring routers periodically exchange

information from their routing tables.
• Routers replace routes in their own routing tables
anytime that neighbors have found better routes.
• Information provided from neighbors
– Outgoing line used for destination
– Estimate of time or distance
• can be number of hops, time delay, packet queue length,
etc.
 Distance Vector Routing
(an adaptive routing algorithm)
The Count to Infinity Problem
 Link State Routing
(an adaptive routing algorithm)

• Five Steps
1.) Discover your neighbors and learn their addresses.
2.) Measure the cost (delay) to each neighbor.
3.) Construct a packet containing all this information
4.) Send this packet to all other routers.
5.) Compute the shortest path to every other router.
 1.) Discovering Your Neighbors
• When the router is booted its first task is to
learn who its neighbors are.
• It send a “Hello” packet on each point-to-
point line. Destination node replies with its
address.
• The below diag shows 2 or more routers are
connected by LAN. Here the situation is
complicated.
• Each of these routers are connected to one or
more additional router
•One way to model this LAN is to consider
it as a node itself
•Introduce a new artificial node N to
which A.C, F are attached
•The path for going from A to C is from N
i.e ANC`
 2.) Measuring Line Cost
• The LSR requires each router to know the
delay to each of its neighbors.
• So it sends an “ECHO” packet over the line.
• Destination is required to respond to
“ECHO” packet immediately.
• Measure the round trip time required for this
operation.
• Question: Should we measure just the time it
takes to transmit the packet, or should we
include the time that the packet waits in the
queue?
• To factor the load ,the round trip timer
must be started when the ECHO packet is
queued.
• To ignore the load the times is started when
the ECHO packet reached the front of the
queue.
 Build Link State Packets
• Once the information is collected ,the next step
is for each router to build a packet containing all
the data.
• The packet starts with the identity of the sender
followed by sequence no and age and the list of
neighbors.
• The delay from one router to another is entered
in the table.
• The LSP are build for all six routers.
•The LSP are build periodically at regular
intervals
 Distributing the Link State
Packets
• Use selective flooding
• Sequence numbers prevent duplicate
packets from being propagated
• Lower sequence numbers are rejected as
obsolete
 Computing the New Routes
• Dijkstra’s Shortest Path algorithm is used to
determine the shortest path to each
destination.
 Hierarchical Routing
• Addresses the growth of routing tables
• Routers are divided into regions
• Routers know the routes for their own
regions only
• Works like telephone routing
• Possible hierarchy
– city, state, country, continent
• The full routing table for router 1A has 17
entries as shown in fig.
• When routing is done hierarchically there
are entries for all the local routers and also
other routers have been condensed into a
single region.
• Hierarchical routing has reduced the tables
from 17 to 7 entries.
• Thus this technique saves table space to
much extent.
 Broadcast Routing
• Send a separate packet to each destination
• Use flooding
• Use multidestination routing
– Each packet contains a list of destinations
– Routers duplicate packet for all matching
outgoing lines
• Use spanning tree routing
– a subset of the subnet that includes all routers but
contains no loops.
 Spanning Tree Broadcasting
• Uses the minimum
number of packets
necessary
• Routers must be able to
compute spanning tree
– Available with link state
routing
– Not available with
distance vector routing
 Broadcast Routing (continued)
• Reverse Path Forwarding
– Use When knowledge of a spanning tree is not
available
– Provides an approximation of spanning tree routing
– Routers check to see if incoming packet arrives from
the same line that the router uses to route outgoing
packets to the broadcast source
• If so, the router duplicates the packet on all other outgoing
lines
• Otherwise, the router discards the packet
 Reverse Path Forwarding Example
This router routes
packets bound for
128.173.41.41 to
via line A. A B

Any broadcast from C

128.173.41.41 that
arrives from line A
is broadcast on lines
B, C, D, and E

Any broadcast from D

E
128.173.41.41 that
arrives from line B,
C, D, or E is discarded
 Multicast Routing
• A method to broadcast packets to well-defined
groups
• Hosts can join multicast groups.
– They inform their routers
– Routers send group information throughout the
subnet
• Each router computes a spanning tree for each
group. The spanning tree includes all the
routers needed to broadcast data to the group
Spanning Trees for Multicast Routing
 Multicast Routing (continued)
• With Link State Routing the routers are
aware of network topology and the
spanning tree can be computed
• With Distance Vector Routing reverse path
forwarding is used.
– When a router receives a packet for a multicast
group for which it has no subscribers (hosts or
other routers), the router sends a PRUNE
message to the source router.
 Congestion Control Algorithms
• Congestion - the situation in which too
many packets are present in the subnet.
 Causes of Congestion
• Congestion occurs when a router receives
data faster than it can send it
– Insufficient bandwidth
– Slow hosts
– Data simultaneously arriving from multiple
lines destined for the same outgoing line.
• The system is not balanced
– Correcting the problem at one router will
probably just move the bottleneck to another
router.
 Congestion Causes More Congestion
– Incoming messages must be placed in queues
• The queues have a finite size
– Overflowing queues will cause packets to be dropped
– Long queue delays will cause packets to be resent
– Dropped packets will cause packets to be resent
• Senders that are trying to transmit to a congested
destination also become congested
– They must continually resend packets that have been
dropped or that have timed-out
– They must continue to hold outgoing/unacknowledged
messages in memory.
Congestion Control versus Flow Control
• Flow control
– controls point-to-point traffic between sender
and receiver
– e.g., a fast host sending to a slow host
• Congestion Control
– controls the traffic throughout the network
 Two Categories of Congestion Control

• Open loop solutions

– Attempt to prevent problems rather than correct
them
– Does not utilize runtime feedback from the
system
• Closed loop solutions
– Uses feedback (measurements of system
performance) to make corrections at runtime.
 General Principles of Closed Loop
Congestion Control
• Monitor the system to detect when and
where congestion occurs.
• Pass this information to places where action
can be taken.
• Adjust the system operation to correct the
problem.
 Metrics Used in Closed Loop Congestion
Control
• Percentage of packets discarded due to
buffer overflow
• Average queue length
• Percentage of packets that time-out
• Average packet delay
• Standard deviation of packet delay
 Reducing Congestion
• Two Methods
– Increase resources
• Get additional bandwidth
– Use faster lines
– Obtain additional lines
– Utilize alternate pathways
– Utilize “spare” routers
– Decrease Traffic
• Send messages to senders telling them to slow down
• Deny service to some users
• Degrade service to some or all users
• Schedule usage to achieve better load balance