Network Routing Protocols: Static or Dynamic?
Introducing Routing and Routing Protocols
The process of transferring information, in the form of packets, within a single network or across different networks, from a source to a destination with typically at least a node in between, is known as routing (Cisco1). Packets are discrete chunks that the whole body of information is broken into for ease of transfer. Each packet of information carries its own identifier, the source address from which it originates and the destination address to which it is headed. Routing takes place in the Network Layer or Layer 3 of the OSI reference model. Routing is achieved through two basic activities: first determining the most optimal path through which the information packet should travel and then transporting the packets through the network which is known as packet switching (Chaudhari, 2005).
Determining the most optimal path a packet should take to reach its destination is a very complex process known as Path Determination. In order to determine the optimal path, a router has to speak or communicate with other routers so that it is able to know exact status of the network. “A routing protocol is the language a router speaks with other routers in order to share information about the reachability and status of networks.” (Doyle, 2001)
All routing protocols are based on a particular algorithm which can be defined as a step-by-step process of arriving at the optimal path. Routing algorithms have one or more different design objectives such as optimality, simplicity and low overhead, robustness and stability, rapid convergence and flexibility.
Routers have routing tables the information in which is used for path determination. The routing algorithm populates the routing table. “To aid the process of path determination, routing algorithms initialise and maintain routing tables, which contain route information.” (CSE, 2008)
For example, the destination or next hop information in a routing table is used to determine to which next router a particular packet has to be sent for it to follow the most optimal route to its destination. When a particular packet reaches a router, the router checks the destination address of the package and tries to associate the destination address with a next hop. Routing tables also have other information such as the degree of a particular path.
To communicate with each other, routers have to maintain their routing tables. They do so by exchanging a variety of messages such as the routing update message which updates the entire or a part of the routing table. The router is able to build a comprehensive picture of the network topology by analyzing routing updates from all other routers in the network.
There are two basic types of routing: Static Routing and Dynamic Routing (Sasase, 2004). In static routing, the routing information is entered manually. The routes that the packets can take are predetermined and fixed, and the scope for route changes is highly restricted. In dynamic routing, on the other hand, the routes are decided on a real-time basis depending on the availability of different routes, and there is frequent change of available routes (Balchunas, 2007). Though hardly any algorithm is used in static routing, routers do have to communicate with each other under some standard protocol. For the purpose of this paper, static routing will also be considered to have a protocol of its own. In dynamic routing, the protocol basically determines the path to the destination, is responsible for updating the route table, chooses the alternative best path if the optimal is not available, and also compensates for network topology changes.
Dynamic routing protocols are broadly classified into two types: Distance Vector protocols and Link State protocols. Popular distance vector protocols include Routing Information Protocols (RIP), Cisco’s Interior Gateway Routing Protocol (IGRP) and Cisco’s Enhanced Interior Gateway Routing Protocol (EIGRP). Similarly, Link State protocol include the Open Shortest Path First (OSPF) protocol and the ISO’s Intermediate System – Intermediate System (IS – IS).
This paper postulates that the selection of the routing protocol depends on the requirements of the network and its users. This paper presents the characteristics and distinct advantages and disadvantages of each of the routing protocols in order to arrive at the thesis statement.
The Pros and Cons of Static Routing
In static routing, the routing table is static. A network administrator creates the table, and maintains and updates it manually. “Routing in a static network is trivial, a simple table of directions calculated once for each destination.”(Levchenko, et al, 2008)
In static routing, a path to every network has to be configured manually on every router to establish full connectivity. Though this would seem to provide a router by router control over the routing, static routing becomes highly impractical for large networks. For smaller networks however, it could be just the right solution, provided other parameters and requirements are considered. The algorithms required for static routing are comparatively very simple to design. Such a type of routing is suitable for network situations where the traffic can be relatively predicted and in which the network design is relatively simple.
In static routing, routers do not share their static routes with each other i.e. routing table updates are not done, and therefore require much les in terms of resources such as CUP and RAM overheads and bandwidth usage.
The biggest disadvantage for static routing is that it is not fault tolerant. Manual intervention is required to cope with any change in the routing infrastructure such as a link not working or the addition of a new network. When routers are configured for static routing, they cannot dynamically choose a better or alternative route when a link goes down. Because static routing cannot react to changes in the network, it is not deemed to be suitable for the large and constantly changing dynamic networks of today.
Dynamic Routing Protocols
In dynamic routing, a routing protocol running on the router handles the tasks of creating, maintaining updating the routing table (Du, 2007). All routers in the network share dynamic routing information, and are therefore constantly are of the network topology and any changes therein. This makes each router capable of dynamically adapting or adjusting to any changes in the network. For example, routing protocols can choose an alternative path which could be better than the original in the given situation in response to a change in the routing infrastructure. Dynamic routing protocols also have the ability of load balancing between multiple links based on the real-time updating of the routing table.
Since the protocol algorithm handles all configuration aspects of the router and the routing table, it is comparatively much more easy and simple to configure a router under dynamic routing protocol for large networks, than in the case of manual or static routing.
On the downside, dynamic routing protocols results in increased usage of resources such as CPU, RAM and bandwidth due to the constant information sharing between the routers in the network. Since the routing protocol maintains and updates the routing table, the best path for any package is decided by the algorithm of the protocol and not by the network administrator. This could be viewed as a loss in granular control for the network administrator.
Before going into the specific properties of Distance Vector protocols and Link State Protocols certain issues that are common to all routing protocols need to be studied in greater detail. These issues are path determination and related metrics, convergence and load balancing.
The essential condition for the functioning of a router is that all networks within an internetwork which the router covers must be somehow mapped in the router. Or in other words, whenever a router has an interface on a network, that interface must have a corresponding address on the network. This interface address of the router becomes the point of origination for all access or coverage information for the router. A router uses the Internet Protocol (IP) addresses and associated masks assigned to it, to deduce to which network it is directly connected. This information is used to populate the routing table of the router. Thereafter, the router transmits this routing table to all other routers in the network. When this exercise is done by each router on the network, information of all connected networks is made available to the routers. Each router thus knows the networks that are connected to its own as well the addresses of the routers to which it is attached.
Though the procedure seems to be simple enough, complexities arise in a scenario of multiple routers transmitting what could be overlapping information on connected networks and router addresses. First there is the possibility of update packets circulating endlessly through the internetwork in a loop. Then there is the matter of selecting the best possible path when more than one router signals direct connectivity to the same network or networks.
Routers use metrics to calculate the best path to the same destination when multiple routes to that destination present themselves. Metrics are used by routing protocols to assess which path would be the best for a packet to travel to its destination or to the next router. “A metric is a standard of measurement, such as path bandwidth, that is used by routing algorithms to determine the optimal path to a destination. To aid the process of path determination, routing algorithms initialize and maintain routing tables, which contain route information. Route information varies depending on the routing algorithm used.” (Cisco, 2002)
Different routing protocols use different metrics, and even multiple metrics, for path determination. The hop count metrics simply counts the number of hops that a package would have to make to reach its destination and opts for the path with the least number of hops.
However, going only by the number of hops may not result in the optimal path as the time of transmission will also depend on the bandwidth. Bandwidth metrics is based on the bandwidth and would prefer a higher bandwidth over a lower bandwidth. But even higher bandwidths may be heavily loaded while a lower bandwidth is carrying much lighter traffic and could therefore carry the packet much more effectively. This problem is addressed by the load metric which checks the links for traffic volume and utilization across available paths. For this metric the best path would be the one with the lowest load. As the load on a preferred route changes, the metric will also change. Care has to be therefore taken so that so that the metric changes are not too frequent resulting in a phenomenon called route flapping. Another metric uses ‘delay’ as the basis for path determination. The delay is a measure of the time that a packet takes to travel along a specified route. A routing protocol that makes use of the delay metrics would chose the route with the minimum delay. When measuring delay, it is not only the delay of the links along the route that is taken into account, but also other factors such as router latency and queuing delay. Reliability metrics is based on the estimation of the probability of failure of links along the routes. Reliability measures can be either variable or fixed. Variable reliability metrics are based on the number of times the link under consideration has failed or produced errors within a certain period of time, while fixed-reliability metrics are based on link reliability as determined by the network administrator. Reliability metrics will choose the path with the highest reliability. The cost metric works on the basis of cost, and is configured by the network administrator as per more-preferred and less-preferred routes. Cost is a generic term, and any policy or link characteristic may define cost, or it could depend on the individual judgment of the network administrator. For example, the Routing Information Protocol (RIP) selects the lowest-cost route based on the number of hops or the hop count.
“A dynamic routing protocol must include a set of procedures for a router to inform other routers about its directly connected networks, to receive and process the same information from other routers, and to pass along the information it receives from other routers. Further, a routing protocol must define a metric by which best paths may be determined.” (Doyle, 2001) Considering this scenario, it is imperative that access or coverage information in the routing tables of all routers in the network must be consistent with each other. If different routers in the network determine different optimal paths for the same packet of information then the routers will keep on sending the information packets back and forth between themselves. This is known as the routing loop and refers to the continuous circling of packages between two or more destinations. The process of brings all routing tables to the desired state of consistency so that there is no routing loop is known as Convergence. The time taking for the routing protocol to update all routing tables via processes such as the update message gives a measure of the convergence.
Finally, a routing protocol has to achieve effective load balancing in order to utilize the available bandwidth effectively. Load balancing refers to the process of distributing network traffic among multiple paths to the same destination instead of routing them through a single path even when the other available paths are loaded less and at equal hops away fro the destination. Such distribution of network traffic will definitely result in better bandwidth utilization.
Distance Vector Routing Protocols
The Distance Vector routing protocol gets its name from the fact that in this protocol the routes are advertized as vectors of distance and direction where distance is defined in terms of a metric such as hop count and the direction is the pointer to the next hop router or the exit interface. Typically, the Bellman-Ford algorithm is used by distance vector protocols for determining the optimal path. They were first used in the original ARPANET (Narten, 1989). Distance-Vector protocols are termed routing by rumor because each router learns about routes from its neighboring routers and in turn pass this route information from its own perspective to its neighbors.
Some distance-vector protocols send periodic updates in the form of complete routing tables to all connected neighbors. The frequency of updates differs for different protocols. AppleTalk’s Routing Table Maintenance Protocol (RTMP) updates every 10 seconds while Cisco’s Internet Gateway Routing Protocol (IGRP) has an update frequency of 90 seconds. The catch-22 situation with update frequency is that too frequent updates could result in network congestion, while too infrequent updates could lead to unacceptably high convergence time. Again, the process of routing by neighbor carries a certain degree of redundancy. When a particular router receives a complete routing table update from its neighbor, it would be redundant to broadcast the same update information back to the router from which it was received. Such a routing update going back to the router from which it was received is known as reverse route. The distance-vector protocol uses a technique known as split horizon to prevent reverse routing. There are two types of Split Horizon techniques – Simple Split Horizon in which the router does not advertise routing updates back to the neighbor which it was received, and Split Horizon with Poisoned Reverse in which routers advertise the reverse routing updates but with an unreachable (infinite) metric.
In the distance-vector protocol, routing is achieved through hop-by-hop updates or by passing updates from neighbor to neighbor. The Bellman-Ford algorithm used by the protocol actually does not give routers the precise topology of the network, but accumulates adequate knowledge to enable the maintenance of a database of all reachable networks. “Distance vector protocols use routers as signposts along the path to the final destination. The only information a router knows about a remote network is the distance or metric to reach that network and which path or interface to use to get there. Distance vector routing protocols do not have an actual map of the network topology.” (Cisco CCNA Exploration Companion Guide, 2008)
The distance-vector protocol uses a broadcast address to incorporate and identify new routers. The presence of a new router is announced by sending corresponding updates to the broadcast address. From there on, neighboring routers working on the same protocol picks up the broadcast and updates themselves and their neighbors in turn.
The distance-vector protocol is capable of re-convergence in the event of a topology change after the initial convergence. This is achieved by setting what is known as a route invalidation timer for each entry in the routing table. The route invalidation timer is a time period that is set by the protocol to identify a route as invalid considering both the events of router failure and specific network failure. This prevents routers from unknowing forwarding packets to unreachable destinations and creating a black hole in the inter-network in the process. Typical route invalidation timeouts range from 2 to 6 update periods.
The distance-vector protocol uses triggered updates or flash updates to send information about metric changes before a regular update is due. This is done both in the case of positive or negative metric changes. Regular updates are not affected by the flash updates. Such flash updates serve to iron out the confusion created by bad information received from routers which are still to be re-converged after any network topology change. Triggered updates work together with Holddown Timers to reduce incidence of acceptance of bad information from routers which may not have the correct information on the exact network topology at any point of time. Holddown Timers actually stops any new updates for a route in which a confirmed change has been identified until the expiry of the timer (Cisco 3, 2000). This is another way of keeping out bad routing updates from yet-to-be re-converged routers in the inter-network.
Link State Routing Protocols
In Link State routing protocols each router gets a clear picture of the network topology, and the network view is not restricted to the status information passed on from neighboring routers. A router configured with a Link State routing protocol gets a complete view of the network topology, the entire network is mapped by gathering and collating information from all other routers. Unlike in Distance Vector protocols, Link State routers obtain first-hand information from all their peer routers. “Each router originates information about itself, its directly connected links, and the state of those links (hence the name). This information is passed around from router to router, each router making a copy of it, but never changing it. The ultimate objective is that every router has identical information about the inter-network, and each router will independently calculate its own best paths.” (Doyle, 2001) Each router sends Link State Advertisements (LSAs) which is copied and stored in an individual database of each router known as the Link State Database (Cain, 2000). The Link State Database defines a graphical representation of the inter-network. Link State protocols use the Dijkstra algorithm to calculate the optimal path the information packets. Because Link State protocols maintain three separate tables – the neighbor table, the network topology table and the shortest-path table, they utilize more CPU and RAM resources of the router.
In Link State Protocol, neighboring routers discover each other through the ‘hello protocol’. The objective of the hello protocol is to define a format and procedure for information exchange and processing between the routers. A ‘hello packet’ typically comprises a router ID, and the instance which is an IP address from one of the interfaces of the router. A hello packet may also carry other information such as the subnet mask, the frequency or hello intervals, the maximum period a router will wait to hear from another router before declaring it ‘dead’ or nonfunctional, a descriptor of the circuit type, etc. When two routers discover each other through the hello protocol, they set up what is known as an adjacency. The hello packets are a way of monitoring all adjacencies. If a hello packet is not received from a particular adjacency within a maximum period specified, the neighboring router is considered unreachable and the adjacency is dropped. The typical frequency for exchange of hello packets is 10 seconds, and an adjacency is broken if there is no hello package exchange within four times that interval.
After the establishment of adjacencies, the routers begin sending the LSAs to every neighbor by a distributed process of sending a package to all routers (Chatzigianakis, et al, 2006). This is known as Link State Flooding. Every neighbor in turn copies the LSAs received and forwards them to their neighbors. The LSA which is received from one neighbor is however not sent back again to that neighbor. Since LSAs are forwarded almost as soon as they are received, and no routing table has to be updated, Link State protocols re-converge much faster than Distance Vector protocols when changes in the network occur (Wade, 2004). Link State protocols do not use periodic updates as in Distance Vector protocols. After the convergence of a network in the Link State protocol, a link update is transmitted only when there is a change in the network topology. Therefore they do not suffer from reverse or routing loops.
Making a Choice
The initial decision that has to be made is between static and dynamic routing. Though the range of capabilities of dynamic routing protocols conveys the impression that they are a much better choice than static routing, yet, it is to be borne in mind that the primary function of dynamic routing protocols mainly detect and adapt to changes in network topologies. If there no changes are expected in network topology, then obviously it would be a waste of routing resources to resort to dynamic routing protocols. It may be difficult to administer static routing in the case of medium to large networks with a varied choice of routes, but in the case of small networks which are not expected to grow and with minimal or no choice of alternative paths, static routing could be the most efficient and resource-effective answer. Many inter-networks strike a balance by using both static and dynamic routing as per the requirements of the individual networks or components.
In the case of dynamic routing protocol, the advantages are many: there is less of administrative work, as the routers do not have to be manually configured when networks are added or deleted; automatic adaptation to network topology changes; less probability of errors in configuration; and scalability in the sense that increase in network can be easily handled by the protocols. However, a higher level of technology knowledge is required to configure and maintain dynamic routing protocols. Higher resources in terms of CPU cycles, memory and bandwidth are also essential, and the choice of the best path is not in the hands of the network administrator but is decided automatically by the router.
Finally when it comes to choosing between the two main types of dynamic routing protocols, the decision has to be made on the basis of the characteristics of the protocols and the type of network that is under consideration. In the case of distance vector protocols in which convergence time is the main concern, its applicability is restricted to situations where network convergence time in not a major issue. Since distance vector protocols do not maintain hierarchical relationship it works best in networks which do not have a hierarchical design and are simple and flat. They are best suited for specific types of networks such as hub and spoke networks. Distance vector protocols also require much less technical expertise than that required in link state protocols. Therefore, the technical expertise of human resources also becomes a factor in deciding which type of dynamic routing protocol to go in for.
Link state protocols are on the other hand preferred when fast convergence of the network is a crucial factor. Link state protocols also become essential in large networks when the network design is hierarchical. The technology knowledge level of the people who configure and administer the network in link state protocol has to be of a very high standard. The human resources involved has to be thoroughly familiar with the technology skills required for the implementation of link state protocols.
It is clear that in spite of technology advances from one type of routing and routing protocol to the other, there are many other factors, besides technology capabilities, that have to be considered in the matter of selection of routing types and protocols. Network type and level of complexity, required level of technology skill and the availability of computing, network and financial resources have to be weighed carefully before making a selection. In many cases, it may be decided not to go in for an absolute type of system but for a hybrid of all the available options put in place according to different requirements within the same inter-network.
Technology management plays an important role in deciding the routing types or protocols for any network. Managers with sound knowledge of the relevant technologies and backed by hardcore ICT professions has to participate in the decision making process to make the right choice of network routing protocols.
Balchunas, A., Static Vs Dynamic Routing, [Online] Available [email protected] [June 12, 2009]
Cain, B., 2000, Fast Link State Flooding, Nortel Networks, 0-7803-5451-1/00/[email protected] IEEE
Chatzigianakis, J., Kokkinos, P., Zaroliagis, C., 2006, Routing Protocols for Efficient Communication in Wireless Ad-hoc Networks, IST Programme for European Union, IST-2005-15964
Chaudhari, B., S., 2005, IP Routing, International Institute of Information Technology, Pune, India
Cisco 1, 2002, Routing Basics, Chapter 5, Routing Components, Internetworking Technologies Handbook, Cisco Press
Cisco 3, 2000, Introduction to Routing Protocols, Networkers, Cisco System.
Cisco2, 2007, Introduction to Dynamic Routing Protocols, Chapter 3, Routing Protocols and Concepts, CCNA Exploration Companion Guide, Cisco Press
CSE, 2008, Routing and Congestion Control, Version2, IIT Kharagpur, India
Doyle, J., 2001, Dynamic Routing Protocols, [Online] Available http://www.informit.com/articles/article.aspx?p=24090 [June 12, 2009]
Du, W., 2007, Routing Protocols, Lecture Notes for CIS/CSE 758: Internet Security, Syracuse University
Levchenko, K., Voelker, G., M., Paturi, R., Savage, S., 2008, XL: An Efficient Network Routing Algorithm, Department of Computer Science and Engineering, University of California, San Diego
Narten, T., Internet Routing, Department of Computer Sciences, Purdue University, ACM 089791-332-9/89/0009/0271
Sasase, I., 2004, Routing Protocol, Department of Information and Computer Science, Keio University
Wade, R., 2004, Advanced IP Networking, WYLUG