Routing Algorithms

Gateway-To-Gateway Protocol (GGP)

This was the protocol used by the core-routers to exchange routing information among
themselves. This is based on Distance Vector Algorithm and uses number of hops as the distance
metric. This is a very poor metric as this does not take into account the load on the links and
whether a link is slow or fast. A provision is made to manually increment the hop count in case a
link is particularly slow.A protocol based on Shortest Path First Algorithm , known as SPREAD
,was also used for the same purpose.

Interior Gateway Protocols (IGP)

IGP is a type of protocols used by the routers in an autonomous system to exchange network
reachability and routing information. Some of IGPs are given below.

Routing Information Protocol (RIP)

This is one of the most widely used IGP. It was developed at Berkeley. This is also known by the
name of the program that implements it, routed .This implements Distance Vector
algorithm.Features of RIP:

RIP uses a hop count metric to measure the distance to a destination. To compensate for
differences in technologies, many RIP implementations allow managers to configure artificially
high hop counts when advertising connections to slow networks. All routinfg updates are
broadcast. This allows all hosts on the network to know about the routes.
To prevent routes from oscillating between two or more equal cost paths, RIP specifies that
existing routes should be retained until a new route has strictly lower cost. Since RIP does not
explicitly detect routing loops, RIP must either assume participants can be trusted (being part of
one autonomous system) or take precautions to prevent such loops.
To prevent instabilities, RIP must use a low value for the maximum possible distance.RIP uses 16
as the maximum hop count. This restricts the maximum network diameter of the system to 16.
To solve the slow convergence problem arising due to slow propagation of routing information,
RIP uses Hold Down. If a particular link is down , any new information about that link is not
accepted till some time. This is because the router must wait till the information aboutthe link
being down propagates to another router before accepting information from that router about
that down link.
RIP runs on top of TCP/IP. RIP allows addresses to be of a maximum size of 14 Bytes. The
Distance varies from 1 to 16 (where 16 is used to signify infinity). RIP address 0.0.0.0 denotes a
default route. There is no explicit size of the RIP message and any number of routes can be
advertized.

Compiled by Sudeep Basu for CSE/IT Dept, SIT

Page 1
The message format is as shown:

OSPF(Open Shortest Path First )

This is an Interior Gateway Protocol designed by the Internet Engineering Task Force ( IETF ).
This algorithm scales better than the vector distance algorithms. This Protocol tackles several
goals:

OSPF includes type of service(ToS) routing. So, you can installmultiple routers to a given
destination, one for each type of service. When routing a datagram, a router running OSPF uses
both the destination address and type of service fields in the IP Header to choose a route.
OSPF provides load balancing. If there are multiple routes to a given destination at the same
cost, OSPF distributes traffic over all the routes equally.
OSPF allows for creation of AREA HIERARCHIES. This makes the growth of the network easier
and makes the network at a site easier to manage. Each area is self contained, so, multiple
groups within a site can cooperate in the use of OSPF for routing.

Compiled by Sudeep Basu for CSE/IT Dept, SIT

Page 2
 OSPF protocol specifies that all exchanges between the routers be authenticated. OSPF allows
variety of authentication schemes, and even allows one area to choose a different scheme from
the other areas.
To accomodate multi-access networks like ethernet, OSPF allows every multi-access network to
have a designated router( designated gateway).
To permit maximum flexibility, OSPF allows the description of a virtual network topology that
abstracts away from details of physical connections.
OSPF also allows for routers to exchange routing information learned from other sites. The
message format distinguishes between information acquired from external sources and
information acquired from routers interior to the site, so there is no ambiguity about the source
or reliability of routes.
It hastoo much overhead of sending LSPs but is gradually becoming popular.

Exterior Gateway Protocol (EGP)

If two routers belonging to two different autonomous systems exchange routing information ,the
protocol used is called EGP . EGP consists of:

Acquisition Request: A router sends a request to another neighbour router saying 'I want to
talk'.
Acquisition Confirm: This is a positive reply to the Acquisition request.
Acquisition Refuse: This is a negative response to the Acquisition request.
Cease Request: This requests termination of neighbour relationship.
Cease Confirm: This is a confirmation response to the Cease Request.
Hello : This is used to find if the neighbour router is up or down.This requests router to respond
if alive.
I Heard You: This is a response to the Hello message confirming that the router is alive. Because
it is possible for Hello or I Heard You messages to be lost in transit, EGP uses a k-out-of-n rule to
determine whether a network is down.At least k of the last n messages must fail for the router
to declare its neighbour down.
Poll Request: This is a request for network routing update.
Routing Update: This conveys routing information about reachable networks to its EGP
neighbour. The routing information is the distance vector of the reachable networks.
Error: This is a response to an incorrect message.

Compiled by Sudeep Basu for CSE/IT Dept, SIT

Page 3
EGP is used only to find network reachability and not for differentiating between good and bad
routes. We can only use distance metric to declare a route plausible and not for comparing it with
some other route (unless the two route form part of a same autonomous system). Since there
cannot be two different routes to the same network, EGP restricts the topology of any internet to
a tree structure in which a core system forms the root. There are no loops among other
autonomous systems connected to it. This leads to several problems:

Univerasal connectivity fails if the core gateway system fails.

EGP can advertise only one path to a given network.
EGP does not support load sharing on routers between arbitrary autonomous systems.
Multiple backbone networks with multiple connections between them cannot be handled by
EGP.

Border Gateway Protocol(BGP)

BGP is a distance-vector protocol used to communicate between different ASes. Instead of maintaining
just the cost to each destination,each BGP router keeps track of the exact path used.Similarly,instead of
periodically giving each neighbour its estimated cost to each destination, each BGP router tells its
neighbours the path it is using.Every BGP router contains a module that examines routes to a given
destination and scores them returning a number for destination to each route. Any route violating a
policy constraint automatically gets a score of infinity. The router adapts a route with shortest
distance.The scoring function is not a part of the BGP protocol and can be any function that the system
managers want.BGP easily solves the count to infinity problem that plagues other distance-vector
algorithms as whole path is known.

Shortest Path Algorithm

1. Dijktstra's Algorithm:

At the end each node will be labeled (see Figure.1) with its distance from source node along the best
known path. Initially, no paths are known, so all nodes are labeled with infinity. As the algorithm
proceeds and paths are found, the labels may change reflecting better paths. Initially, all labels are
tentative. When it is discovered that a label represents the shortest possible path from the source to
that node, it is made permanent and never changed thereafter.

Look at the weighted undirected graph of Figure.1(a), where the weights represent, for example,
distance. We want to find shortest path from A to D. We start by making node A as permanent,
indicated by a filled in circle. Then we examine each of the nodes adjacent to A (the working
node), relabeling each one with the distance to A. Whenever a node is relabeled, we also label it
with the node from which the probe was made so that we can construct the final path later.
Having examined each of the nodes adjacent to A, we examine all the tentatively labeled nodes
in the whole graph and make the one with the smallest label permanent, as shown in Figure.1(b).
This one becomes new working node.

Compiled by Sudeep Basu for CSE/IT Dept, SIT

Page 4
We now start at B, and examine all nodes adjacent to it. If the sum of the label on B and the
distance from B to the node being considered is less than the label on the node, we have a shorter
path, so the node is relabeled. After all the nodes adjacent to the working node have been
inspected and the tentative labels changed if possible, the entire graph is searched for the
tentatively labeled node with the smallest value. This node is made permanent and becomes the
working node for the next round. The Figure. 1 shows the first five steps of the algorithm.

Note: Dijkstra's Algorithm is applicable only when cost of all the nodes is non-negative.

2. Bellman Ford's Algorithm:

We look at the distributed version which works on the premise that the information about far
away nodes can be had from the adjoining links.

The algorithm works as follows.

o Compute the link costs from the starting node to every directly connected node .
o Select the cheapest links for every node (if there is more than one) .
o For every directly connected node, compute the link costs for all these nodes.
o Select the cheapest route for any node .
Repeat until all nodes have been processed.

Every node should have the information about it's immediate neighbors and over a period of time
we will have information about other nodes. Within n units of time , where n is the diameter of

Compiled by Sudeep Basu for CSE/IT Dept, SIT

Page 5
the network, every node will have the complete information. We do not need to be synchronized
i.e. do not need to exchange information at the same time.

Routing algorithms based on Dijkstra's algorithm are called Link State Algorithms. Distance
Vector Protocols are based on distributed Bellman's algorithm. In the former we are sending little
information to many nodes while in the latter we send huge information to few neighbors.

Count-to-Infinity problem:

Suppose the link between A and E is down events may occur are:
(1) F tells A that it has a path to E with cost 6
(2) A sets cost to E to be 11, and advertise to F again
(3) F sets the cost to E to be 16, and advertise to A again

This cycle will continue and the cost to E goes to infinity. The core of the problem is that when
X tells Y that it has a path somewhere ,Y has no way to know whether it itself is on the path.

During this process of counting to infinity, packets from A or F destined to E are likely to loop
back and forth between A and F, causing congestion for other packets.

Compiled by Sudeep Basu for CSE/IT Dept, SIT

Page 6