Unit-3 Unicast Routing (4350706)

3.5.2 Routing Information Protocol

• The Routing Information Protocol (RIP) is one of the most widely used intradomain routing
protocols based on the distance-vector routing algorithm we described earlier.
• 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.
Hop Count

• A router in this protocol basically implements the distance-vector routing algorithm.

• First, since a router in an AS needs to know how to forward a packet to different networks
(subnets) in an AS, RIP routers advertise the cost of reaching different networks instead of
reaching other nodes in a theoretical graph. In other words, the cost is defined between a
router and the network in which the destination host is located.
• Second, to make the implementation of the cost simpler (independent from performance
factors of the routers and links, such as delay, bandwidth, and so on), the cost is defined
as the number of hops, which means the number of networks (subnets) a packet needs to
travel through from the source router to the final destination host. Note that the network
in which the source host is connected is not counted in this calculation because the source
host does not use a forwarding table; the packet is delivered to the default router. Figure
3.5.2.1 shows the concept of hop count advertised by three routers from a source host to
a destination host.
• In RIP, the maximum cost of a path can be 15, which means 16 is considered as infinity (no
connection). For this reason, RIP can be used only in autonomous systems in which the
diameter of the AS is not more than 15 hops.

Figure 3.5.2.1 Hop counts in RIP

Forwarding Tables

• Although the distance-vector algorithm we discussed in the previous section is concerned

with exchanging distance vectors between neighboring nodes, the routers in an
autonomous system need to keep forwarding tables to forward packets to their
destination networks.
• A forwarding table in RIP is a three-column table in which the first column is the address
of the destination network, the second column is the address of the next router to which
the packet should be forwarded, and the third column is the cost (the number of hops) to
reach the destination network.

Prepared By: Mr. Chetan C. Kamani, LEC, GP. Jamnagar 18

Unit-3 Unicast Routing (4350706)

• Figure 3.5.2.2 shows the three forwarding tables for the routers in Figure 3.5.2.1. Note
that the first and the third columns together convey the same information as does a
distance vector, but the cost shows the number of hops to the destination networks.

Figure 3.5.2.2 Forwarding Tables

• Although a forwarding table in RIP defines only the next router in the second column, it
gives the information about the whole least-cost tree based on the second property of
these trees, discussed in the previous section.
• For example, R1 defines that the next router for the path to N4 is R2; R2 defines that the
next router to N4 is R3; R3 defines that there is no next router for this path. The tree is
then R1 → R2 → R3 → N4.
• A question often asked about the forwarding table is what the use of the third column is.
The third column is not needed for forwarding the packet, but it is needed for updating
the forwarding table when there is a change in the route, as we will see shortly.
RIP Implementation

• RIP is implemented as a process that uses the service of UDP on the well-known port
number 520.
• In BSD, RIP is a daemon process (a process running in the background), named routed
(abbreviation for route daemon and pronounced route-dee). This means that, although
RIP is a routing protocol to help IP route its datagrams through the AS, the RIP messages
are encapsulated inside UDP user datagrams, which in turn are encapsulated inside IP
datagrams. In other words, RIP runs at the application layer, but creates forwarding tables
for IP at the network later.
• RIP has gone through two versions: RIP-1 and RIP-2. The second version is backward
compatible with the first section; it allows the use of more information in the RIP messages
that were set to 0 in the first version. We discuss only RIP-2 in this section.
RIP Messages

• Two RIP processes, a client and a server, like any other processes, need to exchange
messages.
• RIP-2 defines the format of the message, as shown in Figure 3.5.2.3.
• Part of the message, which we call entry, can be repeated as needed in a message.
• Each entry carries the information related to one line in the forwarding table of the router
that sends the message.

Prepared By: Mr. Chetan C. Kamani, LEC, GP. Jamnagar 19

Unit-3 Unicast Routing (4350706)

Figure 3.5.2.3 RIP Message Format

• RIP has two types of messages: request and response.

• A request message is sent by a router that has just come up or by a router that has some
time-out entries. A request message can ask about specific entries or all entries.
• A response (or update) message can be either solicited or unsolicited. A solicited response
message is sent only in answer to a request message. It contains information about the
destination specified in the corresponding request message. An unsolicited response
message, on the other hand, is sent periodically, every 30 seconds or when there is a
change in the forwarding table.
RIP Algorithm

• RIP implements the same algorithm as the distance-vector routing algorithm we discussed
in the previous section.
• However, some changes need to be made to the algorithm to enable a router to update
its forwarding table:
o Instead of sending only distance vectors, a router needs to send the whole
contents of its forwarding table in a response message.
o The receiver adds one hop to each cost and changes the next router field to the
address of the sending router.
o We call each route in the modified forwarding table the received route and each
route in the old forwarding table the old route. The received router selects the old
routes as the new ones except in the following three cases:
▪ If the received route does not exist in the old forwarding table, it should be
added to the route.
▪ 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.
▪ If the cost of the received route is higher than the cost of the old one, but
the value of the next router is the same in both routes, the received route
should be selected as the new one. This is the case where the route was
actually advertised by the same router in the past, but now the situation
has been changed. For example, suppose a neighbor has previously
advertised a route to a destination with cost 3, but now there is no path
between this neighbor and that destination. The neighbor advertises this
destination with cost value infinity (16 in RIP). The receiving router must not
ignore this value even though its old route has a lower cost to the same
destination.

Prepared By: Mr. Chetan C. Kamani, LEC, GP. Jamnagar 20

Unit-3 Unicast Routing (4350706)

o The new forwarding table needs to be sorted according to the destination route
(mostly using the longest prefix first).
Timers in RIP

• RIP uses three timers to support its operation.

o The periodic timer
▪ It controls the advertising of regular update messages.
▪ Each router has one periodic timer that is randomly set to a number
between 25 and 35 seconds (to prevent all routers sending their messages
at the same time and creating excess traffic).
▪ The timer counts down; when zero is reached, the update message is sent,
and the timer is randomly set once again.
o The expiration timer
▪ It governs the validity of a route.
▪ When a router receives update information for a route, the expiration timer
is set to 180 seconds for that particular route.
▪ Every time a new update for the route is received, the timer is reset. If there
is a problem on an internet and no update is received within the allotted
180 seconds, the route is considered expired and the hop count of the
route is set to 16, which means the destination is unreachable.
▪ Every route has its own expiration timer.
o The garbage collection timer
▪ It is used to purge a route from the forwarding table.
▪ When the information about a route becomes invalid, the router does not
immediately purge that route from its table. Instead, it continues to
advertise the route with a metric value of 16.
▪ At the same time, a garbage collection timer is set to 120 seconds for that
route. When the count reaches zero, the route is purged from the table.
▪ This timer allows neighbors to become aware of the invalidity of a route
prior to purging.

Performance

• Update Messages.
o The update messages in RIP have a very simple format and are sent only to
neighbors; they are local.
o They do not normally create traffic because the routers try to avoid sending them
at the same time.
• Convergence of Forwarding Tables.
o RIP uses the distance-vector algorithm, which can converge slowly if the domain is
large, but, since RIP allows only 15 hops in a domain (16 is considered as infinity),
there is normally no problem in convergence.

Prepared By: Mr. Chetan C. Kamani, LEC, GP. Jamnagar 21

Unit-3 Unicast Routing (4350706)

o The only problems that may slow down convergence are count-to-infinity and
loops created in the domain; use of poison-reverse and split-horizon strategies
added to the RIP extension may alleviate the situation.
• Robustness.
o Distance-vector routing is based on the concept that each router sends what it
knows about the whole domain to its neighbors. This means that the calculation
of the forwarding table depends on information received from immediate
neighbors, which in turn receive their information from their own neighbors.
o If there is a failure or corruption in one router, the problem will be propagated to
all routers and the forwarding in each router will be affected.
Example

• Figure 3.5.2.4 shows a more realistic example of the operation of RIP in an autonomous
system.
o First, the figure shows all forwarding tables after all routers have been booted.
o Then we show changes in some tables when some update messages have been
exchanged.
o Finally, we show the stabilized forwarding tables when there is no more change.

Figure 3.5.2.4 Example of autonomous system using RIP.

Prepared By: Mr. Chetan C. Kamani, LEC, GP. Jamnagar 22