Routing Information Protocol (RIP)

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 packets through another connection. The following subsections describe how RIP was invented, how RIP works, and other RIP resources.

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 networks.

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 the 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 computer in that network:
    • IP Address. The Internet Protocol address of the computer.
    • Gateway. The best gateway to send a message addressed to that IP address.
    • Distance: 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 j.
      • 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.
      • The 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

D. P. Bertsekas and R. G. Gallaher proved the RIP algorithm converged to the best estimates 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 RIP.

  • RFC 1058; Hedrick, C.; Routing Information Protocol; June 1988
  • RFC 1388; Malkin, G.; RIP Version 2, Carrying Additional Information; January 1993
  • RFC 1723, Malkin, G.; RIP Version 2, Carrying Additional Information; November 1994
  • RFC 2453; Malkin, G.; RIP Version 2; November 1998, Internet Standard 56.