Routing Information Protocol (RIP)

ROUTING INFORMATION PROTOCOL (RIP)

Each node constructs a one-dimensional array (a vector) containing the “distances” (costs) to all other nodes and distributes that vector to its immediate neighbors. The starting assumption for distance-vector routing is that each node knows the cost of the link to each of its directly connected neighbors. A link that is down is assigned an infinite cost.

The cost of each link is set to 1, so that a least-cost path is simply the one with the fewest hops. (Since all edges have the same cost, we do not show the costs in the graph. Note that each node only knows the information in one row of the table (the one that bears its name in the left column). The global view that is presented here is not available at any single point in the network.

Initial distances stored at each node (global view).

Implementation

The code that implements this algorithm is very straightforward; we give only some of the basics here. Structure Route defines each entry in the routing table, and constant MAX_TTL specifies how long an entry is kept in the table before it is discarded. One of the most widely used routing protocols in IP networks is the Routing Information Protocol (RIP). Its widespread use is due in no small part to the fact that it was distributed along with the popular Berkeley Software Distribution (BSD) version of UNIX, from which many commercial versions of Unix were derived. It is also extremely Simple.

#define MAX_ROUTES 128 /* maximum size of routing table */ #define MAX_TTL 120 /* time (in seconds) until route expires */ typedef struct {

NodeAddr Destination; /* address of destination */ NodeAddr NextHop; /* address of next hop */

int Cost; /* distance metric */ u_short TTL; /* time to live */ } Route;

int numRoutes = 0;

Route routingTable[MAX_ROUTES];

RIP is in fact a fairly straightforward implementation of distance-vector routing. Routers running RIP send their advertisements every 30 seconds; a router also sends an update message whenever an update from another router causes it to change its routing table. One point of interest is that it supports multiple address families, not just IP. The network-address part of the advertisements is actually represented as a _family, address_ pair.