Routing Information Protocol Version 1 (RIP-1)

The Routing Information Protocol (RIP) was the first of the TCP/IP routing protocols used on what is now the Internet. There are two versions of this protocol available today: RIP-1 and RIP-2. Both of these versions are still important in today’s routing schemes—the first for backward compatibility and the second because of its broader range of capabilities.

The Algorithm

Let’s separate out the algorithm behind RIP-1 from the protocol itself for a moment. RIP-1 uses a distance vector algorithm to determine where to send packets, and a number of newer routing protocols have followed suit. To be specific, RIP-1 uses the Bellman-Ford algorithm to make its computations. This algorithm begins with the source location, which is a single point when we ignore the routing aspect. It assigns the distance from the source point to itself as zero. The distance to all other points is assumed to be infinite.

The major assumption applied is that there is at least one way to get from any point in the system to the source point; no points are completely isolated from the source. Furthermore, the path to the source point ends when it reaches the source point. It does not travel through it, around some more, and then back. It also cannot travel the same path twice.

The goal of this algorithm is to find the shortest total travel distance from any single point to the source point. Bellman-Ford works in iterations. To start, take a look at the graph points in Figure 1.5 (you should recognize these from Figure 1.4).

The algorithm maps the path from the remote points to the source points for each iteration using a specific number of jumps and the distance for each jump. Iteration one results in Figure 1.6.

The moment you get past just one jump, you have to start looking for more than just the correct number of iterations. In each case, the total distance must be as short as possible from the destination point to the source point. As you get into two jumps (Figure 1.7), three jumps (Figure 1.8), and more, you refine the determination of what exactly is the fastest way to get from any point to the source point.

Examine these first three iterations only for now. Table 1.2 outlines the total distance it takes to get from each point to the source per iteration, using the point labels shown in Figure 1.5.

Table 1.2. Breakdown of Travel Distances for Three Bellman-Ford Iterations

Point	Iteration 1(m)	Iteration 2(m)	Iteration 3(m)
Ag	21	95	147.5
Eng	59	56.5	147.5
Phys	108	106.5	106.5
Hum	134	133.5	137.5
Arts	74	87	97.5
Chem	112	106	146
Math	55	108.5	121.5

Notice the wildly varying results in this table. In some cases, the shortest distance is one jump. In others, it’s two. None in this example benefit from three iterations, although Phys comes close.This is not always the case, however. It really depends on the spread of the points. Completing the example would require four more iterations, a total of seven, just as there are seven points not counting the source point.

Of course, RIP-1 uses this algorithm from the perspective of TCP/IP routing. When you are trying to find the fastest way to get from “here” to “there” from a routing point of view, distance is not the only factor to consider. Another important issue is that of how long it takes the data to travel from connection to connection. The shortest physical distance is not always the fastest route.

Rather than referring to a purely physical distance between points A and B, the distance in RIP-1 is a weight value defining how long it will take information to travel if it jumps between the two points in question. Originally, all distances were listed as one. This is meant as a hop count—with each router the data must pass through being one “hop.” Distances used today are more varied, with the number being slightly higher for cases where data has to travel along a very slow connection to get to the next point or other reasons that might cause delays.

Let’s return to Figure 1.8 from the example network and the data in Table 1.1. The first thing you might do is go through this table and assign the distance or cost of traveling between each of the points. One example of what you might end up with is shown in Figure 1.9.

There are two things to notice here. First, there is not a path from every point to every point as there would be in the raw Bellman-Ford algorithm. The only valid paths are the ones where there are physical connections in place. Second, notice that distances are not assigned exactly according to speed. Anything at least the speed of a T1 line received a one, and from there down the costs increased. A number of approaches can be taken when assigning distances.This is just one of them.

You are in charge of Emerald. For each destination in your routing table—in this case, Abacus and the main campus routers—you must enter the information regarding where to send data to get to that destination. Let’s start with the longest piece of travel, from Emerald to Abacus. Using the Bellman-Ford algorithm, iterate using the number of jumps. There is no single-jump direct route available. Neither is there a two-jump route, nor a three, but there are four-jump paths:

There are also five-jump paths:

Six-jumps paths:

Seven-jump paths:

And, finally, the eight-jump path:

Table 1.3 lays out the cost of each of these paths. As you can see, the quickest path for this packet to follow is B—with C, E, and F all good second choices. Notice what a difference the weighted values make. If every hop were worth one, as they were originally, you would always go with either A or B, while A is among the third longest “distances” the data can travel.

Table 1.3. Travel Cost for Example Network Using Bellman-Ford

Jump	Values	Total
A	2+1+3+3	9
B	2+1+1+3	7
C	2+1+1+1+3	8
D	2+1+3+1+2	9
E	2+1+1+1+1+2	8
F	2+1+1+1+1+2	8
G	2+1+1+1+1+3	9
H	2+1+3+1+1+1+2	11
I	2+1+1+1+1+1+3	10
J	2+1+3+1+1+1+1+3	13

One thing to be aware of with RIP-1 is that you cannot have more than fifteen jumps if you use the value of one per jump rule. This protocol is not designed to carry data for longer distances than that. We hit the limit just in this one small example. With some of the jumps weighted higher than one, the largest total we get here is 13.

You might wonder then what use this protocol is if it cannot handle more than 15 jumps or a value of 15 total cost. RIP-1 is not used to handle the majority of Internet traffic. Its purpose is to work within network groups, such as an office building or campus with complex network structures, where RIP-1 is there only at the most local levels.

RIP-1 is also often the least common denominator protocol. While you may have no specific reason to use this protocol for your own needs, you may need your routers to be able to communicate with outside routers that do not use your primary choice of routing protocols. RIP-1 is often considered a kind of insurance policy in these situations.

A router running RIP-1 keeps its data in a routing table. This table stores information on:

• Network gateways. Machines containing more than one network interface (such as an Ethernet card or using an IP with an alias under Linux), with each interface leading to a different subnet or network.

• Routers. The traffic directors on the Information Superhighway.

• Hosts. Individual machines that require special mention, such as remote machines in a WAN or VPN.

The router then occasionally sends copies of its routing tables to its direct neighbors, and it receives updates from them as well. Whenever a router receives an updated table from one of its neighbors, it calculates whether there have been any changes in the cost metrics applied downstream. For example, say that Emerald received an update from the router at Hum. Our router knows that the cost of the trip from itself to Hum is two. The Emerald RIP-1 tool then adds two to all of the items in the table it just received and compares them against its own. The following list describes the actual values contained within the RIP-1 routing table:

• The TCP/IP network address or host IP address referred to

• The gateway that must be traveled through to get to this address

• The hardware interface that must be traveled through to get to the gateway

• The route cost

• The time since this entry was last updated

If one or more of the results from Emerald and Hum’s tables do not add up, there has been a change in the metrics. Any new values received from Hum are copied, have two added to them, and then are placed in Emerald’s routing table as a new metric value.

There Can Be Only One Notice that there is only one entry for each destination in the RIP-1 routing table. RIP-1 stores only the current best path of travel; it does not store the entire results of the algorithm calculation.

The Bellman-Ford algorithm does not have to deal with the fact that some of the points may become permanently or temporarily unavailable. RIP-1 does, however, avoid the risk of sending packets on a road to nowhere if a particular connection or machine goes down or is removed.

The update message discussed previously is sent every 30 seconds in RIP-1. Whenever an update is received from a particular machine, the time since update is changed in the routing table for that single machine. After 180 seconds of silence from that particular machine, it is assumed that there is a problem, and the router is marked in the table as unavailable by setting the distance to this destination as 16, one higher than the maximum cost.

How It Works

Now, let me set up an example. As I mentioned before, Emerald needs to send data through Abacus. All Emerald knows is that to get data to the appropriate network (192.168.13.x), it needs to send that data through the interface that leads to router Hum. Hum knows that the fastest way for it to send data to network 192.168.13 is through Arts. Arts knows to send the data through Math, and Math knows it can send directly to Abacus.

This data path works great until Hum does not hear from the router at Arts for 180 seconds, which is a series of six check-in times. Router Hum then marks Arts as unreachable and passes this information to Emerald. As a result Emerald doesn’t know how to send any data to Abacus! Remember, there is only one method of getting from here to there kept in the RIP-1 routing tables.

Several different things could be going on here:

• Router Arts was intentionally removed. It had a critical failure, and there is no backup router available to take its place for a week.

  Because it can take a long time for news to travel from router to router in RIP-1, the administrator in Emerald’s section explicitly tells router Phys that the new cost for router Arts is 16, which means that it is not available. After the usual 30 seconds, router Phys sends out its updates.These updates include all of the routes that are available through Phys.

  Phys’s only neighbor now is Hum. Phys sends Hum its list of networks to which it knows how to send information, as well as the costs to get to those networks. Included in this list is the fact that it now costs 16 units to get to Arts through Phys. Router Hum knows that it costs one to get from Hum to Phys, so it adds the two costs together and updates the cost for data to go to from Hum to Arts to a total of 17. Hum doesn’t know that it is talking about Arts; it only looks at the networks it can get to fastest through Phys. Phys is not part of the path to get to 192.168.13.x, so Hum still does not know it has a problem. Hum does know, however, that it cannot reach anything that requires it to go through Phys and then Arts.

  After 180 seconds of not hearing from Arts, Hum realizes for itself that Arts is unreachable. It now updates its own cost to get data to Arts to 16. The problem now is that this is the only way Hum knew to get data to 192.168.13.x. Any data that comes from Emerald with the destination 192.168.13.x is going to get bounced back or simply lost in the great void of networking problems. The same happens with all of the other routers, eventually, when they need to send data through Arts.

• Router Arts was intentionally removed. It is not going to be replaced with anything else.The administrator has access to router Chem and updates its tables to advertise routes through Math that replace the invalid routes through Arts.

  The administrator for router Chem removes Arts from its routing tables and recalculates the distance vector. In its usual 30-second update after the change, Chem tells its neighbors—Math and Hum—that they can get to the networks that became unreachable through it. The cost from Chem to Abacus through Math is six (3+3), so this is the cost that Chem advertises in the routing table to get to 192.168.13.x. Hum knows that its cost to get to Chem is one, so it now tells Emerald and Phys about the cool new path to 192.168.13.x at a cost of seven (3+3+1). This change spreads through the network as well until everything is fully operational once again.

• The connection Arts uses to access the network went down temporarily, isolating this router, the machines on its own network, and any networks that it is supposed to pass data to from everyone else. This connection stays down for three hours.

  By the time the connection comes back up, all of the neighbor routers have long since noticed that Arts was unavailable and have passed the information along to all of the other routers in the example network. When router Arts’s connection comes back up, it will have decided that all of the other routers are unavailable as well.

  The details regarding this scenario are discussed later in this section.

At least one problem might become obvious from the scenarios listed above. Routers send updates to all of their neighbors, even the ones from which they just received an update. If a router blindly trusts what its neighbor tells it, this problem can wreak all kinds of havoc. Routers that have marked another router as unreachable might be told by neighbors that it, in fact, is working fine—when it’s not. In the meantime, packets of data are being sent all over the place and are getting lost while the routers continue to disagree.

A technique often used to solve this dilemma in routing protocols is split horizon. This addition simply uses a common sense rule: Do not send updates about a route to the router from which you just heard the news. For example, consider the problem of Arts going down again. In Scenario 1, an administrator tells router Phys that Arts is no longer accessible. Thirty seconds later router Phys has incorporated this data into its tables, marking certain networks as unreachable through it, and shares this information with its neighbors, which now turn out to be just Hum.

Thirty seconds later, Hum has incorporated the data into its tables and has marked certain networks as unreachable through it, and Hum now informs its neighbors. This would now be Phys, Emerald, and Chem. However, it received the news from Phys. Due to split horizon, Hum sends an update to all of the machines but only sends information involving data that has to go through Phys to Emerald and Chem. After all, Hum has other information that does not pass through Phys, and Phys has to be kept up to date about that.

Then, Chem tells Math about the updates but does not send Hum the items relating to it. From there, Math shares the new information with Ag and Abacus. Abacus gives the new information to Ag because it got the news from Math and not from Ag, and Ag tells Eng. Figure 1.10 illustrates this progression.

This is not a perfect method, but it’s more efficient than letting conflicting information bounce back and forth between the same machines. There is still another concern, however. Loops can be formed where a series of routers end up trapping packets accidentally. Because it only prevents updates of routers from which it just received the update, split horizon is not enough to take care of this fact.

RIP-1 uses a combination of split horizon with poisoned reverse. In a way, this takes us back to what we were doing originally. Routers send updates about all routes to all neighbors, even the one they just received a particular route from. The difference is that if Phys tells Hum that Arts is back up and the distance is one, Hum then tells

Emerald and Chem that Arts is available and that the cost is two, but Hum tells Phys that the cost to get to Arts from Hum through Phys is 16. Got that? Let me break it down:

As you can see, RIP-1 is a relatively basic routing protocol. It has rudimentary features for keeping track of which machines are available but would not be reliable in a network where things change often. The program used to implement RIP-1 under Linux is routed. You can also use the multi-protocol daemons gated or zebra. See Chapter 5 for more information on where to find these programs and how they work.