The Routing Information
Protocol (RIP) provides
the standard IGP protocol for local area networks, and provides great network
stability, guaranteeing that if one network connection goes down the network
can quickly adapt to send
through another connection. The following subsections describe how
RIP was invented,
how RIP works, and other RIP
How RIP was invented. The Routing
Information Protocol (RIP) was written by C. Hedrick from Rutgers University
in June 1988, and has since become the most common Internet routing protocol
for routing within
RIP is based on the computer program "routed", which was widely
distributed with the Unix 4.3 Berkeley Software Distribution (BSD) operating system,
and became the de-facto standard for routing in research labs supported by vendors
of network gateways.
All RIP routing protocols are based on a distance
vector algorithm called the Bellman-Ford algorithm, after Bellman's development
of the equation used as the basis of dynamic programming, and Ford's early work
in the area.
Software based on these algorithms was used as early as 1969
on the ARPANET, but the main protocol development was done by the Xerox network
research and development division. The earliest RIP protocol was the PUP protocol,
which used the Gateway Information Protocol to exchange routing information,
and was invented by a team that included R. M. Metcalfe, who later developed
Ethernet physical layer network protocol.
The PUP protocol was later upgraded to support the Xerox
Network Systems (XNS) architecture, and named "Routing Information Protocol",
usually just called RIP.
How RIP works. What makes RIP work
is a routing database that stores information on the fastest route from computer
to computer, an update process that enables each router to tell other routers
which route is the fastest from its point of view, and an update algorithm that
enables each router to update its database with the fastest route communicated
from neighboring routers:
- Database. Each RIP router on a given
network keeps a database that stores the following information for every
- IP Address. The Internet Protocol
address of the computer.
- Gateway. The best gateway to
send a message addressed to that IP address.
The number of routers between this router and the router that can send the message
directly to that IP address.
- Route change flag. A flag
that indicates that this information has changed, used by other routers to update
their own databases.
- Timers. Various timers.
- Algorithm. The RIP algorithm works like this:
- Update. At
regular intervals each router sends an update message describing its routing database
to all the other routers that it is directly connected to. Some routers will send
this message as often as every 30 seconds, so that the network will always have
up-to-date information to quickly adapt to changes as computers and routers come
on and off the network.
- Propagation. When a router X finds that a router
Y has a shorter and faster path to a router Z, then it will update its own routing
database to indicate that fact. Any faster path is quickly propagated to neighboring
routers through the update process, until it is spread across the entire RIP network.
A mathematical description of this algorithm is shown below.
- Let D(i,j) be the metric for the best route from router i to router
- Let d(i,j) represent the distance from router i to router j, set to
infinite if i and j are the same or if i and j are not immediate neighbors.
best distance is then
D ( i, i ) = 0, for all i
D ( i, j ) = min ( d ( i, k
) + D ( k, j ) ), for i <> j, over all k
P. Bertsekas and R. G. Gallaher proved the RIP algorithm converged to the best
of distance to each destination address.
The RIP routing protocol uses UDP
because it is particularly efficient, and there are no problems
if a message gets, which is fine for router updates where
another update will be coming along shortly anyway.
Resources. The following references provide more information about
1058; Hedrick, C.; Routing Information Protocol; June 1988
1388; Malkin, G.; RIP Version 2, Carrying Additional Information;
1723, Malkin, G.; RIP Version 2, Carrying Additional Information;
2453; Malkin, G.; RIP Version 2; November 1998, Internet