DYNAMIC ROUTING PROTOCOLS 1

Running head: CHOOSING A DYNAMIC ROUTING PROTOCOL

Choosing an Appropriate Dynamic Routing Protocol Based Upon Predefined Specifications

Unit 4 Individual Project

Boris Karloff

Carnegie-Mellon University

Enterprise Network Design

ITP630-02

Professor Manny Astte, PhD

September 20, 2003


Abstract

The transition from a static routing protocol to a dynamic routing protocol can be a process fraught with difficulty or it can be a process made easy by the selection of an appropriate routing protocol. An appropriate routing protocol is one that will be compatible with your network, will be easy to implement/maintain, and will suit the network needs of your particular situation. This paper will help to illuminate some of the selection criteria to be considered for a given scenario and will hopefully help you to match network requirements to the protocol which has the closest matching characteristics.


Choosing an appropriate dynamic routing protocol based upon predefined specifications.

1)  Preface – the given scenario presents a number of challenges that must be addressed before a viable solution is arrived at. The first challenge is that there are a number of unknowns that make the determination of the best solution more difficult. The first unknown is “what type/brand of equipment is being utilized.” The use of proprietary solutions is always geared towards one vendor or another. One vendor’s solutions often do not work with another vendor’s equipment. Another unknown is “what staff is available and what experience level does the staff have for the purpose of implementing and maintaining complex dynamic routing protocols in this scenario.” Making certain assumptions, therefore, will be necessary to arrive at a “best” solution that addresses all of the needs of the given scenario.

2)  Given the following scenario, chose the best routing protocol that meets the needs identified in the scenario.

a)  “…You have been tasked with reconfiguring the network for your company, which has grown considerably over the past year. You have used only static routing in the past, but you do not wish to spend the administrative time required to maintain the routing tables now that the network has grown. You have recently experienced numerous inaccuracies in the routing table cause by entries you made when in a hurry. You would like to automate the entry and updating of routing information, but you are concerned about excessive memory and processor utilization if you implement dynamic routing protocols…”

b)  “…You also wish to minimize the use of network bandwidth. You prefer that the most efficient use of bandwidth be made so that packets will travel to their destination over the truly shortest path, rather than just the path with the lowest number of hops. You have heard that routing loops can be a problem and wish to avoid them. However, you are concerned that if a link goes down, there should be redundancy so that traffic will go through…”

c)  “How can you accomplish your objectives, and what routing protocols and protocol features will you use to do so?”

3)  Routing Protocols

a)  Choosing a Routing Protocol – “…routing protocols are used only to collect data about current network status and contribute to the selection of the best path…” (Dean, T., 2002).

i)  Classifications of Routing Protocols

(1)  Static versus dynamic

(2)  Single-path versus multi-path

(3)  Flat versus hierarchical

(4)  Host-intelligent versus router-intelligent

(5)  Intra-domain versus inter-domain

b)  In this scenario it is evident that a change from a static routing protocol to a dynamic routing protocol needs to be made.

c)  Types of Dynamic Routing Protocols

i)  Link-State Routing Protocols (LS) - “…This type of routing protocol requires each router to maintain at least a partial map of the network. When a network link changes state (up to down, or vice versa), a notification, called a link state advertisement (LSA) is flooded throughout the network. All the routers note the change, and re-compute their routes accordingly. This method is more reliable, easier to debug and less bandwidth-intensive than Distance-Vector. It is also more complex and more compute- and memory-intensive…” (FreeSoft.org, 2003). The only limitation of link state routing protocols is the complexity of maintaining these complicated protocols, which scale well to large network applications. Link state routing algorithms are also known as Dijkstra Shortest Path algorithms. The following are a few examples of this type of routing protocols.

(1)  OSPF

(2)  IS-IS

(3)  NLSP

(a)  NetWare Link Services Protocol

(b)  “…advanced link-state routing protocol developed by Novell…” (Lammle, T. and Barkl, A., 2003).

(c)  “…intended to replace both RIP and SAP [service advertising protocol]…” (Lammle, T. and Barkl, A., 2003).

(d)  The NetWare Link Services Protocol (NLSP™) provides link state routing for Internetwork Packet Exchange networks (IPX). It is a protocol for information exchange among routers geared to the needs of large IPX networks.

(e)  Route Summarization

(i)  “…The benefits of summarization are derived through efficient resource utilization. Since multiple addresses can be summarized as a single routing entry, the number of Link State Packets (Lisps) can be reduced, thus minimizing the amount of bandwidth required for routing updates…” (Cisco Systems, 2003).

ii)  Distance-Vector Routing Protocols (DV) - “…This type of routing protocol requires that each router simply inform its neighbors of its routing table. For each network path, the receiving routers pick the neighbor advertising the lowest cost, then add this entry into its routing table for re-advertisement…” (FreeSoft.org, 2003). Distance vector routing protocols are usually limited to small networks consisting of fewer than 100 routers. In order to avoid routing loops, distance vector routing protocols use such techniques as “counting to infinity,” “split horizon,” “[reverse] route poisoning,” and “hold-downs.” Distance vector routing algorithms are also known as Bellman-Ford routing algorithms and Ford-Fulkerson routing algorithms. (HowStuffWorks.com, 2003). The following are a few examples of this type of protocol.

(1)  RIP

(2)  RIP-2

(3)  RTMP

(4)  IGRP

(5)  Hello Routing Protocol

(6)  EGP

iii)  Balanced Hybrid/Balanced Routing Protocols - balanced hybrid routing protocols have some of the best features of both distance-vector routing protocols and link-state routing protocols. An example of one protocol of this type follows.

(1)  EIGRP

(a)  Enhanced Interior Gateway Routing Protocol

(b)  Uses the same route metrics as IGRP (see IGRP above).

(c)  “…developed in the mid-1980s by Cisco Systems…” (Dean, T., 2002).

(d)  “…it has a fast convergence time and a low network overhead…” (Dean, T., 2002).

(e)  “…is easier to configure and less CPU-intensive than OSPF…” (Dean, T., 2002).

(f)  “…EIGRP…uses distance-vector and link-state information when calculating routes using the DUAL algorithm…convergence is much faster than with IGRP…” (Lammle, T. and Barkl, A., 2003).

(g)  “…also offers the benefits of supporting multiple protocols and limiting unnecessary network traffic between routers…” (Dean, T., 2002).

(h)  “…accommodates very large and heterogeneous networks…” (Dean, T., 2002).

(i)  “…is only supported by Cisco routers…” (Dean, T., 2002).

(j)  “…uses the same vector information as IGRP…” (Lammle, T. and Barkl, A., 2003).

(k)  “…EIGRP employs four key technologies, including neighbor discovery/recovery, Reliable Transport Protocol (RTP), Diffusion Update Algorithm (DUAL) finite-state machine, and a modular architecture that enable support for new protocols to be easily added to an existing network…” (Cisco.com, 2003).

iv)  Path State Routing Protocols – These exterior gateway protocols are usually only used to route datagrams between autonomous systems and are seldom seen inside of an autonomous system. The following are examples of this type of protocol.

(1)  GGP

(2)  BGP-4

4)  Selection Criteria

a)  Minimize the use of network bandwidth

i)  No periodic updates – Only the link state protocols meet the selection criteria of not sending out periodic updates, but instead only multicasting changes when they are necessary.

ii)  Routing protocols that do not send out periodic updates make better use of available bandwidth than do those which must send full updates every few seconds.

b)  Packets should use the shortest path, rather than just the path with the lowest number of “hops.”

i)  Intelligent route “metrics”

ii)  Shortest Path First – Dijstra Algorithm

iii)  Distance-Vector (DS) routing protocols only consider the number of hops (or routers) between source and destination.

iv)  Link-state routing protocols more intelligently calculate the best route based upon several metrics (depending upon the link-state routing protocol chosen).

c)  Avoid routing loops – most routing protocols suffer from the tendency to create routing loops. Several techniques exist with link-state and hybrid routing protocols to avoid routing loops.

i)  Spanning Tree Algorithm – used by the Spanning Tree Protocol to prevent routing loops.

ii)  Spanning Tree Protocol - “…Spanning-Tree Protocol is a link management protocol that provides path redundancy while preventing undesirable loops in the network. For an Ethernet network to function properly, only one active path can exist between two stations…” (Cisco Systems, 2003).

d)  Automatic selection of alternate routes if critical links go “down.”

i)  Spanning Tree Protocol

(1)  Redundancy – “…To provide path redundancy, Spanning-Tree Protocol defines a tree that spans all switches in an extended network. Spanning-Tree Protocol forces certain redundant data paths into a standby (blocked) state…” (Cisco Systems, 2003).

(2)  Fault Tolerance – “…. If one network segment in the Spanning-Tree Protocol becomes unreachable, or if Spanning-Tree Protocol costs change, the spanning-tree algorithm reconfigures the spanning-tree topology and reestablishes the link by activating the standby path…” (Cisco Systems, 2003).

5)  Matching Protocols

a)  OSPF

b)  EIGRP

c)  NLSP

6)  Conclusion – depending upon the brand of equipment used for routing devices and depending upon the selection of protocols to be routed, the link-state routing protocols NLSP (for IPX) or OSPF (for IP) or the hybrid routing protocol EIGRP could be used to meet all of the criteria specified as important to this client. The best choice of protocols, equipment permitting, would probably the proprietary Cisco protocol, EIGRP. If the routers on this client’s network were not all Cisco, though, that would be impossible, as EIGRP is only useable on Cisco equipment. If only Cisco equipment is available, EIGRP becomes the best choice because of its support of IP, AppleTalk, and the IPX protocols. If EIGRP cannot be used, the second best choice, if the IPX protocol were the only protocol present on the network, would be NLSP. If, instead, the TCP/IP protocol were being used, then the OSPF routing protocol would be the second best choice of a routing protocol. The use of OSPF, along with the features of the Spanning Tree Algorithm, part of the Spanning Tree Protocol, can be used to avoid routing loops,


References

Cisco Systems (2003). Internetworking Technology Handbook. Retrieved on September 14, 2003 from http://www.cisco.com/univercd/cc/td/doc/cisintwk/ito_doc .

Dean, T. (2002). Network+ Guide to Networks. 2nd Ed. Course Technology, Boston, MA. PP. 90, 283-285

FAQS.org (2003). What IP routing protocol should I use? Internet FAQ Archives. Retrieved on September 14, 2003 from http://www.faqs.org/faqs/cisco-networking-faq/section-28.html .

FreeSoft.org (2003). Connected: An Internet Encyclopedia – Routing. Retrieved on September 14, 2003 from http://www.freesoft.org/CIE/Topics/87.htm .

HowStuffWorks.com (2003). How Routing Algorithms Work. Retrieved on September 14 2003 from http://computer.howstuffworks.com/routing-algorithm1.htm .

Lammle, T. and Barkl, A. (2003). CCDA Cisco Certified Design Associate. 2nd Ed. SYBEX, Inc. Alameda, CA. PP. 137, 311-354