Prepared for Prof. Dr. Hassan Peyravi
Department of Computer
Science, Kent State University
Date: December 2003
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:
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.
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.
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:
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:
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"
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.
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.
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
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