A Survey of IP Routing Protocols

Author: David Tucker
email:  mailto:dtucker@cs.kent.edu, homepage: www.edinboiro.edu/~dtucker

Prepared for Prof. Dr. Hassan Peyravi
Department of Computer Science, Kent State University
Date: December 2003


Abstract:  Among networks that run IP (Internet Protocol) there are many different choices of which protocols to choose from.  This paper attempts make the reader more informed about protocols by bringing together in one source, background information of IP routing, description of the common protocols, and their advantages and disadvantages.  It will discuss RIP - Routing Information Protocol, OSPF - Open Shortest Path First protocol, BGP - Border Gateway Protocol, and EIGRP - Enhanced Interior Gateway Routing Protocol.

Table of Contents


Introduction

This paper will discuss the different IP protocols that are being used.  The next section will give some background information leading up what IP is, why we need different protocols.  The background will be followed by a break down of each protocol, its description and how it fits into the overall scheme of the internet.  Included in this paper are links to that can be used to further the reader's understanding of the material.

Background

What is a protocol?

One good way to think of what a protocol is, is that it is similar to a language that we speak.  When people are talking we are using rules,  when to talk, what to say, order of words, pronunciation of words, etc.  It's not that much different with computers, they need to talk to each other, and their languages are the protocols.  The internet uses IP as its protocol to communicate between different systems.  Among IP there are different types of protocols that are used to determine the best route to send data over a network.  This paper will summarize some of the common protocols used for updating routing tables among the nodes of a network.  Information on what routing tables are follows.

What is routing?

Routing is just what the word implies, the routing or directing of things, in this case it is traffic that consists of data packets.  Another way of thinking of it is the finding of a path from a source to a destination.  If a user wishes to send data to another computer and the two are not directly connected then the data needs to be routed to the other computer.  The data will be first sent to a router, which according to a routing table will then forward that data to another router or the destination.  Where the protocol comes in is how the routing tables are created.  The objective being that a packet gets to it's destination in the most efficient  way possible, by looking up where the packet should be sent according to the routing table. Two basic concepts that are beyond the scope of the paper, and not discussed here, that the reader may want to read further about, are the concepts of an internet data packet and what a router is.  The figure below shows a simple network and demonstrates that there could be many different paths that a data packet may take when a client computer sends data to an internet server and vise versa.  Each of the routers will have a routing table to look up where to send packets for their next hop.

The main requirements on any routing protocol are:

  1. Ensuring the routing tables are consistent.  This makes sure that routes will work when packets move from one router to another as the path is being constructed.
  2. Minimizing the size of the routing table. The smaller the routing table the more efficient that router is going to work.  The lookup will not cause additional delay in the transmission of the packet and there will be less data to exchange between the routers when updating tables.
  3. Minimizing control messages. Control messages are used when the nodes/routers talk to each other to update routing information.  If to much of this is done it can cause congestion in the network.
  4. Robustness. Keep the errors to a minimum, errors such as packets being sent down dead-end paths (black holes), packets running in loops and oscillations where the decision of which path to take changes frequently.

What is IP?

IP stands for Internet Protocol, and is one of many protocols used when delivering data over a network.  IP is very important to most people (without knowing) because it is the protocol used over the internet.  Other common protocols include Novell's Netware , Apple Talk, and ATM.  These are very common and generally used within a local area, this paper concentrates on networks that are using IP.

Goal of the Paper

The goal of this paper is to bring together in one source a summary of common IP routing protocols.  It will discuss different ways in which the routing tables of IP networks are created and how that information is propagated among the nodes of a network.  It wil also discuss the advantages and disadvantages of these protocols.  It will follow with a discussion of future trends.


IP Routing Protocols

RIP - Routing Information Protocol

This protocol's purpose is to help build and update routing tables inside an autonomous system (AS) by sharing information about the network with it's neighbors.  This is an example of an interior gateway protocol, where the protocol is designed to be used by an AS only and not out on the internet.

How RIP works is an initial router will send a copy of its entire routing table to all of it's neighboring routers every 30 seconds plus a small random number to avoid all of the routers updating their tables at the same time.  Those routers will then update their tables with that information, keeping only the best routs in their routing tables, then send their entire routing table to their neighbors.  This cycle will continue until all of the routers in the network have exchanged information about each other.  The information being passed is the number of hops a given node is away.  A hop meaning the next step in the network.  This is known as distance vectoring.  The protocols avoids indefinite routing loops by limiting how many hops away a destination can be.  If a destination is more than 15 hops away, RIP marks it as unreachable.  This has the advantage of avoiding loops and the disadvantage of limiting the size of a network to 15 hops.

There is also a version of the protocol that includes information about the amount of time it takes to get to another node.  This could improve the performance because it is considering the amount of time it takes to get to a node plus the number of nodes it is away.  These help to carry out the objective, to get data to its destination and in the best possible way.

In addition, as a reminder, this is an interior gateway protocol that is used for an autonomous system, a network system that is administered by one central unit and not very large.  This type of protocol would not work in a large network such as the internet mostly because of the large number of routers causing an unmanageable amount of table updating to occur over the internet.

The advantage to RIP is that it is very straight forward, mature, stable and  has low computational overhead, it is also widely used and most routers will be able to use this protocol.  The disadvantage is that it doesn't support multiple ASs or subnetting.  Subnetting is discussed in the next protocol witch fixes these two disadvantages.

The technical details from which the protocol was designed can be found in Request For Comments (RFC) 1058 and Internet Standard (STD) 56.

OSPF - Open Shortest Path First

Like RIP this protocol is also an interior gateway protocol (not for use out on the internet) and is an alternative to RIP, it extends what the RIP protocol does, mostly the difference is that it can be used to connect multiple autonomous systems (still under one administration) versus just one and it also supports subnetting, the use of subnets in a network which extends the network administrators capabilities of segregating the network.  

How it works, the OSPF protocol will  notice that there has been a change in the network or routing table.  It then immediately sends to all of the nodes on that network the new change, the nodes then update their routing tables accordingly.  Instead of sending the entire routing table as RIP does, OSPF nodes only send information about the updated node.  In addition another difference to RIP is that it doesn't periodically send an update, OSPF nodes only send an update when there has been a change in the network.

As with any routing protocol the goal is shortest (working) path routing decisions.  RIP used counting the number of hops, OSPF bases it routing decision on link states.  That is to give each router complete information about the nodes in the network and let the routers calculate the best routing tables based on that information.  The following is the what is exchanged:

  1. That router's ID.
  2. The ID of one of the router's neighbors.
  3. The cost of the link to that neighbor.

Once the information has been received, the algorithm used to calculate the shortest path between 2 nodes  is usually Dijkstra's algorithm.  This algorithm is not discussed here because of  the complexity and it is outside the scope of this paper but note that it is very important part of the protocol.

Some of the advantages have already been mentioned, that OSPF support subnetting and can operate on multiple ASs.  Another advantages is that this protocol supports giving priority based on the type of service the packet is.  So if a packet is urgent, it is possible to make it a high priority.   Also this protocol may generate less network traffic because updates are only done when required versus periodically.  One disadvantage to OSPF is when a node fails or changes relative to the network, there will be a period of time that the other routers will not no this information and their routing tables will be obsolete and possibly send packets down a bad or nonexistent path.  In addition, since there is no periodic update, it may be longer then RIP's 30 seconds to update the routing tables.

Also note that most routers that are running OSPF can run RIP also, this is to insure backward compatibility since RIP is older and more widely used.

Technical details from which the protocol was designed can be found in The OSPF specification is published as Request For Comments (RFC) 1247.

EIGRP - Enhanced Interior Gateway Routing Protocol

This protocol is a revision to the earlier Interior Gateway Routing Protocol, which was skipped in this paper in favor of this one.  It takes the advantages of link state protocols and and puts them into a distance vector protocol.  This protocol can also be used in Novel Netware and Apple Talk.

EIGRP is different in many ways, one is that it will keep a copy of it neighbor's routing tables.  If it is looking up a destination for a packet and it can't find it on it's own or it's neighbor's routing tables (which it has a copy of) then it's  neighbors will query their neighbors routing tables.  If not found it will continue the cycle until a path is found.  In addition when a change is made to a routing table, it doesn't send the whole table, it only sends the routes that need updated.  This is different than the other distance vector algorithm looked at earlier.

To keep aware of the existence of its neighbors EIGRP nodes send a periodic "hello" packet to keep aware of the status of its neighbors.  If this packet is not received from a node in a certain amount of time then it will assume that it is down.  EIGRP uses the Diffusing-Update Algorithm (DUAL) to determine the route with the least cost.  This algorithm considers distance and whether the route to the destination is not a loop.

Some additional advantages of this protocol are that it includes support for subnetting, partial update, and can be used on different network protocols.  One disadvantage is that this protocol is relatively new and therefore may not be supported in all routers.  A network may need to reconfigure all of its routers for this to work.

BGP - Border Gateway Protocol

This protocol differs significantly from the other that were discussed in its purpose.  BGP is used to exchange routing information between the nodes/routers that connect a network of autonomous systems.  It is often used in the routers that connect ASs to the internet.  There are two versions that should be mentioned, Internal BGP (IBGP) and External BGP (EBGP).   EBGP is used to for updating routing information between two or more Internet Service Providers.  Within a service provider the routers will exchange routing information using IBGP.

Similar to OSPF, this protocol only sends updates of changes in the network or failure of a node when such an incident happens and only the items in the routing table that are affected are sent.  The latest version of this protocol allows for an administrator to modify what determines the cost of a link to another node. 

Their routing tables will contain the following:

  1. List of known routers
  2. Address they can reach
  3. Cost associated with the path to each router.

To help further explain how this protocol works included are the attributes that BGP uses to determine the best route with a short explanation.

The BGP router will receive many advertisements for the same routes to a particular destination, BGP will calculate the best path, enter this into its IP routing table and then propagate that path to its neighbors.

The advantage to BGP IP routing is that it is very robust and commonly used throughout the internet.

More technical details can be found at the request for comments, RFC 1771, "BGP4"

Ongoing Research:

One hot topic in the area of IP routing is in mobile communication or MobileIP.  Where a node is moving in and out of several wireless networks.  The problem is how to set up the routing for such a node.  Buddhikokt, Hari, Singh, and Miller suggest a method in which two IP address are assigned to one node, one being a virtual IP and the other the physical IP address.   The virtual address is one that stays the same allowing other nodes to send packets there, the physical IP will change as the node is moving to different networks.  Forward routing must be set up according to each new network entered and that information is told to a server that is acting as a post office for the virtual IP.

Another recent topic in IP routing is the idea of routing for satellite communication.  Akyildiz, Ekici, and Yue look into trying to reduce the cost associated broadcasting to several nodes at the same time.  Here the author proposes a way to populate routing information on the nodes in a distributed manor.

In the third research paper, Belding-Royer looked at routing protocols for ad-hoc networks.  That is a network that is created spontaneously.  For example if an airplane was to drop a bunch of tiny computers out of it and these computers needed to talk to each other, an ad-hoc network would have to be created.  The author proposes two clustering protocols that improve the way routing is done in relation to the ability of these networks to grow.


Evaluation &Conclusion

RIP had been in use for a long time, relative to IP, and has done well.  With the increased demand on all networks, especially IP, there needs to be improvement in performance, and that is where OSPF comes in, making a protocol that is more flexible and always creates an optimal path between a source and destination node.  One point that is worth pointing out again is the effort the designers of OSPF have made, so the transition to the new protocol is easier, by building into the protocol the backward compatibility for RIP.  So if one router is "speaking" RIP to a router that understands OSPF the system will not fail.  The third internal procol, EIGRP seems to be another improvement  with every advantage of both, with the exception that it may not be as widely used as RIP.

Notice that all of the articles that this paper looks at for further research are in the area of wireless networking, that was intentional because the trend in networking is going towards wireless.  This opens up new areas of research, one of them being the design of new routing protocols.  This paper talks about IP routing, but the future could be dominated by a different protocol that new routing algorithms will need to be developed for.


References

http://www.cisco.com/univercd/cc/td/doc/cisintwk/ito_doc/
Information about all the protocol mentioned

http://searchnetworking.techtarget.com/
Source for many of the links to definitions

http://links.math.rpi.edu/devmodules/graph_networking/compat/page13.html
Information on Link States and Dijkstra's algorithm

Roaming and handoff management: MobileNAT: a new technique for mobility across heterogeneous address spaces
Milind Buddhikot, Adiseshu Hari, Kundan Singh, Scott Miller
September 2003 Proceedings of the 1st ACM international workshop on Wireless mobile applications and services on WLAN hotspots

A distributed multicast routing scheme for multi-layered satellite IP networks
Ian F. Akyildiz, Eylem Ekici, Gaofeng Yue; September 2003, Wireless Networks,  Volume 9 Issue 5

Multi-level hierarchies for scalable ad hoc routing
Elizabeth M. Belding-Royer; September 2003, Wireless Networks,  Volume 9 Issue 5

Research Groups

Scope

The scope of this survey includes information found on the internet, mostly what was found in the references.  In general I used the Google internet search engine, searching on key words such as RIP, IP, IP Routing, Internet, and OSPF.  There is an incredible wealth of information on this topic.  The research articles were found using Kent State's ACM portal and searching under the key words IP Routing Protocols and sorting by date.