Routing Protocols (RIP)
Routing is the process of selecting a
path for traffic in a network, or
between or across multiple networks.
Unicast Routing
• If a datagram is destined for only one
destination (one-to-one delivery), we have
unicast routing
• In unicast routing, a packet is routed, hop by
hop, from its source to its destination by the
help of forwarding tables.
• Hop is router or other device between path of
source to destination.
Least Cost Routing
• When an internet is modeled as a weighted graph, one of
the ways to interpret the best route from the source
router to the destination router is to find the least cost
between the two.
• In other words, the source router chooses a route to the
destination router in such a way that the total cost for the
route is the least cost among all possible routes.
• If there are N routers in an internet, there are (N − 1)
least-cost paths from each router to any other router. This
means we need N × (N − 1) least-cost paths for the whole
internet using least cost tree
Routing Algorithms
• Several routing algorithms have been designed in
the past . The differences between these methods
are in the way
– they interpret the least cost
– they create the least - cost tree for each node
• Following are three algorithms
– Distance-Vector Routing
– Link State Routing
– Path Vector Routing
Distance-Vector Routing
• In distance-vector routing, the first thing each
node creates is its own least-cost tree with the
basic information it has about its direct neighbors
• The incomplete trees are exchanged between
immediate neighbors to make the trees more and
more complete
Link State Algo….
• In this algorithm the cost associated with an
edge defines the state of the link. Links with
lower costs are preferred to links with higher
costs; if the cost of a link is infinity, it means
that the link does not exist or has been
broken.
• Flooding is used to create link state database.
• Each node sends greetings message to its
neighbors to collect link cost and Node
identity
Path Vector Routing
• For example, assume that there are some
routers in the internet that a sender wants to
prevent its packets from going through.
• In other words, the least-cost goal, applied by LS
or DV routing, does not allow a sender to apply
specific policies to the route a packet may take.
• To respond to these demands, a third routing
algorithm, called path-vector (PV) routing has
been devised.
Unicast Routing Protocols
• we discuss three common protocols used in
the Internet :
• Routing Information Protocol (RIP), based on
the distance - vector algorithm,
• Open Shortest Path First (OSPF), based on the
link - state algorithm,
• Border Gateway Protocol (BGP), based on the
path - vector algorithm .
Autonomous Systems
• A collection of IP networks and routers under the
control of one entity Like ISP.
• Each AS has a 16 bits number called ASN
• we may have small, medium-size, and large AS
• They are categorized according to the way they
are connected to other Ass and are following
types.
– Stub AS: only one connection to another AS And data
cannot pass through it as customer connection
– Multihomed AS: more than one connection to other
ASs but does not allow traffic to go through it as a
customer may be connected to many networks
– Transient AS: connected to more than one other AS
RIP
• The Routing Information Protocol (RIP) is one
of the most widely used intra-domain routing
protocols based on the distance-vector routing
algorithm.
• RIP was started as part of the Xerox Network
System (XNS), but it was the Berkeley Software
Distribution (BSD) version of UNIX that helped
make the use of RIP widespread.
RIP Algorithm
• Uses distance vector routing algorithm
• But some changes need to be made to the
algorithm to enable a router to update its
forwarding table
• router needs to send the whole contents of its
forwarding table in a response message to
destination hop
• receiver adds one hop to each cost and
changes the next router field to the address of
the sending router with three possibilities.
RIP Algorithm
1. If the received route does not exist in the old
forwarding table, it should be added to the
route
2. If the cost of the received route is lower than
the cost of the old one, the received route
should be selected as the new one
3. If the cost of the received route is higher than
the cost of the old one then it is rejected
Timers in Rip
• RIP uses three timers to support its operation
– periodic timer controls the advertising of regular
update message on predefined time
– expiration timer governs the validity of a route
and timer is set and tables are updated
– garbage collection timer is used to purge a route
from the forwarding table when it becomes invalid
Performance of RIP
• Update Messages are easy to implement
• No problem of Convergence of Forwarding
Tables as RIP supports maximum of 15 hops
• Robustness: calculation of the forwarding
table depends on information received from
immediate neighbors, which in turn receive
their information from their own neighbors
End
