Internet Routing -- Overview & RIP

Serving as examples of route management protocols, RIP and OSPF attack the problem through different techniques

One of the more powerful features of packet switched systems are their ability to dynamically route packets. This power also comes with a complexity that can lead to an interesting set of problems. If one could count on a network operating in a static configuration with no failures, the routing problem would be simple; static tables could suffice as the basis for all routing decisions. For each packet destined to a particular destination, the next hop would be identified in the table, and the packet would be forwarded.

However, in the real world, nodes are added to networks, links fail, and topologies change. As networks get larger, administration and management headaches increase. Therefore, automated route management rapidly becomes a necessity. This article takes a look at two of the more significant routing mechanisms that are used in the Internet, the Routing Information Protocol (RIP), and the Open Shortest Path First (OSPF). RIP, implemented in the widely available BSD UNIX daemon routed, has been around for some time and is an example of a vector-distance routing scheme. OSPF is a newer development, and is based on a link-state algorithm. The Open Systems Interconnect (OSI) Intermediate System (IS) to IS protocol is similar in concept to OSPF as it is based on a link-state algorithm and includes many of the same features that can be found in OSPF.

The Internet architecture is based on the concept of the interconnection of many "Autonomous Systems." An Autonomous System is characterized by a single management authority along with the use of a consistent routing architecture. Each of these systems is responsible for the maintenance of its own routing, and connects to the network through different routing protocols. The routing algorithms used within the Autonomous System are referred to as Interior Gateway Protocols (IGP), that can be RIP, OSPF, or whatever else is chosen by the network architects. The routing algorithm used to connect the Autonomous System to the Internet is referred to as Exterior Gateway protocols. Several exterior gateway protocols are in use today, with the most popular being the Exterior Gateway Protocol (EGP) and the Border Gateway Protocol (BGP). The term "gateway" is somewhat historical, and is the term applied in early Internet architecture efforts. The term "router" is more consistent with the concepts as defined within the OSI standards.

Routing Methodologies

The two major classes of routing algorithms employed within the Internet are the vector-distance (also known as Bellman-Ford) and link-state algorithms. The distinction between these protocols is in the methods used to describe and exchange routing information. The vector-distance algorithms are based on the exchange of distance and reachability information between routers. Link-state algorithms are based on the exchange of more extensive information, including a complete database of how each routing node reaches other nodes in the network, the type of link, and more detailed cost information. With a more complete picture of the state of all links in the target network, each routing node is then able to identify the shortest path to a destination node or network. It is from this concept that the term "Shortest Path First" has been coined.

*Feature*	*RIP*	*OSPF*
Algorithm	vector-distance	link-state
Maximum Hops	15. 16 hops is considered to be infinity, implying that the destination is unreachable	Limited only by size of routing tables within routers
Subsystem Segmentation	Treats the autonomous system as a single subsystem	Breaks the autonomous system into one or more areas with two levels of routing algorithms, intra-area, and inter-area.
Metric	destination/hop	destination/cost/link identifier
Integrity	no authentication in RIP-1, Authentication has been added to RIP-2	Supports Authentication. Several authentication algorithms are available ranging from simple password operations to more complex cryptographic algorithms.
Complexity	Relatively Simple - Each router	More Complex. Several more PDUs and exchanges are defined in the protocol. Routing tables are large and include not only destinations, but also a tree representation of local network.
Acceptance	Widely Available, BSD routed supports RIP	newer, published in RFCs
Route Options	Identifies a single route to a destination	Supports multiple routes to a single destination. Facilitates load-balancing traffic distribution
Types of Routes	host, network. RIP-2 adds the ability to transfer subnetwork route entries	Host, network, and subnetwork routes

Table 1 - Major Features of RIP, OSPF

While there are significant differences in the techniques applied with each of these algorithms, there are some common features. The ability to reach adjacent nodes cannot generally be derived from the link or IP layers of the network; both RIP and OSPF include features that can detect the failure of an adjacent routing node, or the link to that node. These services are based on periodic transfers between adjacent routing nodes. The lack of traffic from an adjacent node for a prescribed time-limit is used to imply a failure to reach that node. Both algorithms result in a set of route tables that define the next hop between the routing node and packet destinations. Its just the way that they calculate the next hops that is different.

Vector-Distance Routing

The basic concept used in vector-distance routing is the regular exchange of reachability information between adjacent routers. This information consists of a list of all nodes that can be reached by the broadcasting node, combined with the number of routing hops required to reach the selected node. For example, in the network configuration shown in Figure 1, with all interconnections and nodes operating properly, the route report from Node D will contain the route metrics shown in Table 2. This report contains all pertinent information that is used by adjacent nodes in making routing decisions. Node D's internal representation includes a third column, that represents the adjacent node used to reach the selected destination host (or network).

Node	Hops
A	2
B	1
C	1
E	1
F	1
G	2
H	1

Table 2 - Node D Normal RIP route report (See Figure 1)

This report reflects the best case routes to each of the nodes E, F, and G. Note that if the direct link between node D and E and D and F were to fail, the route through node C could be selected at a hop count of 2 rather than 1. Nodes A and B will similarly broadcast route reports, that will contain hop counts that node D can ignore while calculating its routing tables. Each node in the network can therefore calculate its hop distance on the basis of reports received by the adjacent routing nodes.

Figure 1 - Example Network Architecture

The state of health of adjacent routing nodes are broadcast to all of each node's adjacent routers every 30 seconds. Through repeated transmissions over unreliable UDP services, lost routing information is recovered through subsequent transmissions. The regular transmission of the routing information serves an additional purpose. The lack of a message from an adjacent routing node within 180 seconds is used to identify failed routes. With no link state information available to indicate a routing path failure, this mechanism provides indication that the path to the indicated node is no longer available.

One of the more significant problems with RIP, and with vector-distance protocols is slow convergence. As an example of slow convergence, consider a case in which the link between Node D and Node H in figure 1 fails. While Node H is no longer reachable, nodes C and B will initially determine that they reach node D through A and E. Taking a look at the interaction between nodes A and B, the following information will be transferred with regard to reaching node H:

Node D determines H is no longer directly reachable, sets its hop count to 3, based on the report from nodes B and C. On the next reporting interval, node D advertises this information to nodes B and C.
Nodes B and C in turn receive the increased hop count information from node D, and increment their reachability information to H to a hop count of 4 (3 from Node D plus 1 to reach node D)
Node D in turn receives the hop count of 4 and assumes that Node H is now 5 hops away.

This pattern continues until the hop count reaches infinity, that is fortunately only 16 within RIP. Once infinite hops (16) have been reached, the routing node determines that the target is no longer reachable. With a reporting interval of 30 seconds, these types of situations can take as much as 8 to 16 minutes to resolve themselves. Strategies to speed up route resolution include "split horizon with poisoned reverse," and "triggered updates."

Split horizon involves the reporting of only those routes not sourced by the destination router. Split horizon with poisoned reverse reports the destination dependent routes as having a route metric of infinity. In our example, Node B would report routing information to Node A with Node D being at infinity. This scheme works best when only two stations are involved. More involved loops, such as node A can result in more involved cases of route deception. For example, Node A is using reachability information from both Nodes B and C.

Triggered updates are designed to address more complicated routing loops. They add event-driven behavior to the route reporting algorithms. When implementing the triggered update mechanism, routers immediately report changes in reachability information. By reporting the changes immediately rather than delaying until the next reporting period, convergence still requires several iterations, however, the convergence iteration is performed at the speed of the network transport rather than being paced at the reporting rate. As in the case of "split horizon with poisoned reverse," "triggered updates" are not a fool-proof solution to the RIP slow convergence. Periodic updates continue, and the receipt of a periodic update prior to the triggered transmission can prolong the convergence process.

As can be seen by this discussion on routing, RIP provides the major services required to perform automated route management within an autonomous system, provided that the system complexity is kept small (no greater than 15 logical hops between any two nodes), can afford to risk faulty routing broadcasts, and does not require any form of load balancing. Systems requiring these services should consider either RIP-2 that adds features for logical subnetting and authentication, or consider using the more complex OSPF protocols. OSPF, as a link-state protocol, scales to larger topologies and avoids the slow convergence problems through routers maintaining a more complete map of the network topology.