ROUTABLE PROTOCOL A network protocol that can be routed. Routable protocols are network protocols that use Layer 3 (network layer) addresses for forwarding packets to their destination. The most commonly used routable protocol today is the Transmission Control Protocol/Internet Protocol (TCP/IP), which is the protocol used on the Internet and in most enterprise networking environments. Other routable protocols, now considered legacy protocols, include . Internetwork Packet Exchange/Sequential Packet Exchange (IPX/SPX) . Xerox Network Systems (XNS) . DECnet . AppleTalk . Banyan VINES Seldom-used network protocols that are not routable include . NetBEUI . Data Link Control (DLC) A routable protocol is a network layer protocol that can be routed. A routing protocol, however, is something different: a protocol by which routers can communicate routing table information with one another. Do not get them confused! ROUTE A path a packet travels across an internetwork and a command for displaying and configuring routing tables on routers. The route a packet takes as it crosses an internetwork is the path, starting from the sending host to a neighboring router and then hopping from router to router until the packet reaches its destination host on some remote network. The process by which the best route to forward a packet is identified is known as routing. Route is also a command that allows viewing and modification of entries in the internal routing table on an Internet Protocol (IP) host such as a Microsoft Windows 2000, Windows XP, or Windows .NET Server computer. This internal routing table contains routing information that determines how the computer delivers packets to local and remote hosts on the network. Typing route print at the Windows command prompt displays the routing table of the local computer. Typing route add 172.16.25.0 mask 255.255.255.0 172.16.10.1 metric 2 adds a new route to the routing table, specifies that any packets destined for the network with network ID 172.16.25.0 should be forwarded to the router interface 172.16.10.1 in the local network, and specifies that packets sent along this route will traverse two hops on the network. ROUTER A device used to connect or segment networks. Routers are most often used in Transmission Control Protocol/Internet Protocol (TCP/IP) networks, the Internet being the prime example of a large routed network. Routers can be used either to connect many smaller networks into a larger network called an internetwork or to segment a large network into smaller subnetworks in order to improve performance or manageability. Routers are also sometimes used to join dissimilar media, such as unshielded twisted-pair (UTP) cabling and fiber-optic cabling, and different network architectures, such as Token Ring and Ethernet. Routers can also be used to connect local area networks (LANs) to telecommunication services such as leased lines or Digital Subscriber Line (DSL). A router used to connect a LAN to a leased line such as a T1 line is often called an access server, and a router used to access DSL servers is known as a DSL router. These routers often support basic firewall functionality to filter out packets based on their source or destination network address. Such a device is sometimes called a packet-filtering router. Routers generally block broadcast traffic and can thus prevent broadcast storms from slowing down the flow of traffic in a network. Routers are so complex that Cisco Systems, the major vendor of enterprise-level routers, has developed an operating system called Internetwork Operating System (IOS) that is devoted solely to managing routers. Routers can be either . Static routers: These must have their routing tables configured manually with all network addresses and paths within the internetwork. or . Dynamic routers: These automatically create their routing tables by listening to network traffic and communicating with other routers. Routers are similar to bridges in that they both forward packets and can be used to either segment or join networks. However, routers use Layer 3 (network layer) addresses such as IP addresses to forward packets, but bridges employ Layer 2 addresses (MAC addresses) for this purpose. When should you use a bridge and when should you use a router? Use bridges to connect network segments that run the same network protocol. for example, to connect an IP segment to an IP segment. Also use bridges when you run legacy nonroutable network protocols such as NetBEUI on your network. On the other hand, use routers to connect network segments that run different network protocols.for example, to connect an IP segment to an Internetwork Packet Exchange (IPX) segment. Generally speaking, routers are more intelligent than bridges and improve network bandwidth by not forwarding broadcast packets to other networks. Finally, use routers when you want to connect your network to the Internet. Routers work at the network layer (Layer 3) of the Open Systems Interconnection (OSI) reference model. They forward packets between networks on the basis of their destination logical addresses (IP addresses in the case of TCP/IP). Routers also route packets based on the available paths and their costs, thus taking advantage of redundant paths that can exist in a mesh topology network. To do this, routers contain internal tables called routing tables that keep track of the paths that packets can take as they move across the internetwork, along with the cost of reaching each remote network. Because routers operate at a higher OSI level than bridges do, they have more powerful switching and filtering capabilities. They also generally require greater processing power, which results in routers usually costing more than bridges. Also, because routers use network addresses for routing packets, they can only work if the network protocol is a .routable protocol. such as TCP/IP or Internetwork Packet Exchange/Sequenced Packet Exchange (IPX/SPX). This is different from bridges, which are basically protocol-independent Layer 2 devices. Cisco holds the dominant place in the high-end router marketplace, with over 88 percent of the market share. Cisco produces a wide variety of routers with varying capabilities for small, medium, and large enterprises. They also produce routers that are used to form the backbone of the Internet. Some common models of Cisco routers include . 1600 and 1700 Series: These are used primarily for small businesses to provide wide area network (WAN) access. . 2600 Series: These are standard routers for branch office access to corporate headquarters over WAN links. . 3600 Series: These are multifunction routers that can be used in branch/enterprise environments and are more powerful and flexible than the 2600 series. . 7200 and 7500 Series: These are high-end multiprotocol routers that support a wide variety of media and are used to build both collapsed backbones and WANs. . 12000 Series: These are heavy-duty router/switch combinations used in collapsed backbones and carrier networks. Other popular router manufacturers include Nortel Networks, Juniper Networks, Ericsson, and 3Com Corporation. A few years ago it was thought that Layer 3 Ethernet switches (also simply called Layer 3 switches) would drive the router market out of existence. This has not entirely happened, despite the fact that such switches, being hardware-based, perform much better than traditional software routers. In the enterprise LAN arena, Layer 3 switches do indeed dominate now in collapsed backbones where routers once ruled in distributed backbones. But in the WAN access arena, routers are still going strong and it looks like they will be around for a long time, driven mainly by Internet service providers needing more routers to handle increased traffic. Appearing on the horizon are terabit routers capable of forwarding 1012 bits per second (bps). These routers are intended mainly for use by telecommunications carriers in their backbone networks, and leading vendors include Cisco, Lucent Technologies, and Avici Systems. A startup called Hyperchip is even developing a petabit router capable of switching packets at 1015 bits per second, a speed equivalent to a million Gigabit Ethernet (GbE) ports! Such high-end routers are intended for the next generation of all-optical networks that are expected to emerge around 2005. ROUTER ROUTING Routing that occurs at the routers. Routers are generally used to connect different networks together. Router routing is the process by which a router examines an incoming packet and determines which interface on the router to forward the packet to. This is different from host routing, which is routing that occurs at the host itself. Usually the term router routing is simply abbreviated as routing. Whether this actually refers to host routing or router routing can usually be determined from the context of the discussion. ROUTING Forwarding packets from one network to another across an internetwork. Routing is a method of joining multiple networks in a way that allows packets to travel from one network to the next. To do this, devices called routers are used to connect different networks. These routers accept packets destined to remote networks and forward them to the next step along the way. Routing is only possible with network protocols that are .routable.. Examples of routable protocols include . Transmission Control Protocol/Internet Protocol (TCP/IP): The standard network protocol used on the Internet and in most enterprise networking environments today. . Internetwork Packet Exchange/Sequenced Packet Exchange (IPX/SPX): A legacy protocol used in Novell Netware 2.x and 3.x platforms. The rest of this article focuses on TCP/IP routing, which is the most common type. Routing can be classified in different ways depending on what is under consideration. For example, there is . Host routing: This is routing that occurs at the host itself. Each host on an IP network normally maintains its own internal routing table. This table is used to determine whether to send a packet to the local network, to a specific router interface, or to the default gateway address. . Router routing: This is routing that occurs at the routers that connect the various networks. Networks connected by routers are generally called subnets, although this term has a more precise meaning in the context of IP addressing. Most of the discussion below focuses on router routing, which is usually simply called routing. Routing can also be classified according to how routers are configured to forward packets, specifically: . Static routing: Administrators manually enter entries in router tables. . Dynamic routing: Routing tables can be updated automatically when different routers communicate with one another using routing protocols. Routing takes place at the network layer (Layer 3) of the Open Systems Interconnection (OSI) reference model. In TCP/IP networking, this means that routing of packets is based on their destination IP addresses. Routing takes place on a packet-by-packet basis and involves two steps: . Determining the best route (path) over which the packet should travel to reach its destination host. . Forwarding the packet to the appropriate remote network according to its destination IP address. Forwarding of packets is handled independently by each router along the path the packet has to travel. In other words, the packet is forwarded across each successive .hop. until it arrives at its destination. Routers perform this forwarding using internal tables called routing tables, which contain information describing the potential paths that data can take to travel to remote networks. Between any two subnets on an internetwork there may be more than one route by which the packet can reach its destination. The information in the routing table, therefore, includes the metric (cost value) for each possible route to the destination, and the packet is usually sent along the path with the lowest cost. If two paths to the same destination have the same cost, the stream of packets can be load-balanced between the two routes. Each network traversed on a routed internetwork is called a subnet. The value of the metric for a specific path depends on several factors. For example, the metric might be proportional to the number of routers that the packet stream must be switched through (the number of hops traversed), the delay or latency of packets when they are processed by each router, the amount of traffic congestion (load) at the router, the available bandwidth along a route, and even the relative reliability of the routers. For static routers, network administrators manually specify metrics for each path and enter them into routing tables, but for dynamic routers routing algorithms are used to automatically calculate metrics for each possible path. Dynamic routers do this by communicating with each other using special protocols called routing protocols. Examples of common routing protocols include the Routing Information Protocol (RIP) and the Open Shortest Path First (OSPF) protocol. Once the routing table for a static router has been properly configured (or once the tables of all dynamic routers have .converged. and stabilized), the router carries out its packet-forwarding function. The entire routing process works like this: if a local host wants to send a packet to a host on a remote network, the local host first checks its own internal routing table (host routing) to determine which nearby router to forward the packet to. The host then uses Address Resolution Protocol (ARP) to obtain the MAC address of the near-side interface of this router and sends the packet directly to this interface. This packet.s header contains the destination host.s logical network layer address (IP address). When the router receives the packet, it inspects this destination address and compares it to the information stored in its internal routing table to determine what to do with the packet. If the router cannot determine what to do with the packet, it simply drops the packet. Otherwise, it forwards the packet (router routing) to the destination host (if it is on a network connected to the router) or to a more distant router, which forwards the packet again until finally the packet reaches the network where its destination host resides. As the packet is forwarded from router to router across the internetwork, its network layer destination address remains the same, but its MAC address keeps changing to that of the next router interface along the path. Routing in a network can suffer from a number of problems. One problem is the existence of routing loops, which occur when a packet passes through the same router more than once on a given trip. The result is that the packet loops until its lifetime decreases to zero and a router discards it. The originating host usually never knows that the packet was dropped and did not reach its destination. Routing loops occur most often in networks that use incorrectly configured static routers. Routing algorithms for dynamic routers can usually detect loops and reconfigure routing tables to eliminate them. Another problem is convergence. In a large internetwork using dynamic routers, it might take some time for a change in one router.s tables to propagate to all other routers in the internetwork. In the meantime, temporary routing loops can occur and less efficient network paths might be chosen, resulting in more traffic congestion. Properly designed routing protocols and routers help avoid such issues and make routing a reliable process for building large internetworks from smaller networks. See Also: black hole, bridge, convergence, default gateway, dynamic routing, flooding, hop count, host routing, internetwork, Open Systems Interconnection (OSI) reference model, routable protocol, route, router, router routing, routing algorithm, routing interface, routing metric, routing protocol, routing table, static routing, subnet ROUTING ALGORITHM A mathematical procedure that a dynamic router uses to calculate entries for its routing table. Routing algorithms underlie the routing protocols that enable dynamic routers to exchange information with one another in order to calculate the metrics of various paths or routes throughout an internetwork. These algorithms generally operate using a combination of variables obtained either by inspecting header information in packets received by the router or manually specified by administrators. The routing algorithm processes the values of these variables to generate the internal routing table for the router. These variables are known as routing metrics and can include the following: . Hops: The number of intermediate routers between a given network and the local router . Latency: The time delay in processing a packet through the router or over a given route . Congestion: The length of the packet queue at the incoming port of the router . Load: The processor use at the router or the number of packets per second that it is currently processing . Bandwidth: The available capacity of a route to support network traffic; decreases as network traffic increases . Reliability: The relative amount of downtime that a particular router might experience because of malfunctions . Maximum Transmission Unit (MTU): The largest packet size that the router can forward without needing to fragment the packet Routing algorithms are usually implemented as a combination of dynamic (real-time calculated) and static (specified by the network administrator) factors, usually in a distributed fashion where each router independently calculates its own routing tables. In the case of dynamic routers, the exchange of routing information between routers is also part of this process. This provides a degree of fault tolerance for the routing network, for if one router goes down, the remaining routers can recalculate their routing tables to ensure they are able to route traffic around the failed router. Then, when the failed router is restored, the routing tables are recalculated a second time. Some routing algorithms support forwarding packets over several paths to a given destination (when such multiple paths exist) and thus better manage network traffic by load balancing packets accordingly. An important distinction between routing algorithms involves the space within which they operate. In a flat routing space, all routers are peers, but in a hierarchical routing space, different routing domains, areas, or autonomous systems are connected using a backbone routing network. The advantage of a hierarchical routing space is that it reduces the amount of intercommunication traffic that must take place between routers in order for them to calculate their routing tables. For example, routers that forward traffic only within their own routing table do not need to exchange routing information with routers in other domains. The downside, of course, is that a hierarchical system is much more difficult to implement and maintain than a flat routing space. Based on this distinction, routing algorithms come in two basic types: . Distance vector routing algorithms: These use a flat routing space, and an example of a routing protocol of this type is the Routing Information Protocol (RIP). Distance-vector routing is sometimes called Bellman-Ford routing or even .old ARPANET routing. by those who are familiar with this algorithm.s origins. . Link state routing algorithms: These employ a hierarchical routing space, and an example of a routing protocol of this type is the Open Shortest Path First (OSPF) protocol. Link state algorithms were developed later than distance-vector ones and have largely displaced them in enterprise networking. From a network administrator.s perspective, the differences between these algorithms are as follows: A routing protocol based on the distance vector routing algorithm is simpler to implement than one based on the link state routing algorithm. Routing loops are less likely to occur when the link state algorithm is used, but link state algorithms require more processing power and routers that implement it are generally more costly. The two algorithms offer a trade-off with respect to network traffic between routers. Specifically, routers using the distance vector algorithm periodically send their entire routing table to other routers, but only to routers one hop away, while the link state algorithm floods the entire internetwork with information from each router, but only updated information is sent when needed. ROUTING INTERFACE A port where a router connects to a network. For any particular network, the port on the router that is directly connected to the local network is called the local interface, and any port on the router that is connected to a different network is called a remote interface. Each router interface has a unique MAC address burned into it, just like a network interface card (NIC) in a computer. If only one router is connected to the local network, the local interface is the default gateway for all hosts on that network. ROUTING METRIC A variable used by a dynamic router to calculate its routing table entries. Dynamic routers employ metrics to determine which routing interface the router should forward a packet to in order to route it to its destination. Routing metrics enable routers to make intelligent decisions about how to forward packets to ensure that . Packets are delivered efficiently and quickly . Congestion does not occur over links between networks . Packets are not lost by being dropped by overloaded or dead routers The simplest metric used by routers to calculate routing table entries is the number of hops to a given destination network. This kind of metric is used by the Routing Information Protocol (RIP), an older routing protocol that enables dynamic routers to communicate with each other to share their routing information and synchronize the entries of their routing tables. On the other hand, if you need a more complicated metric that provides you with more control over the various paths that packets take across your network, you can use a routing protocol such as Open Shortest Path First (OSPF) instead. This protocol employs several variables in calculating its metric, including . Load: Generally, the number of packets being processed per second by the router or its central processing unit (CPU) utilization. If the load on a router becomes high, the router can advise other routers to recalculate routing tables in order to divert traffic around it. . Latency: The time interval needed to route a packet through the router or over a specific path through the internetwork. Latency can be increased by delays due to such factors as port congestion on the router, heavy router load, bandwidth utilization of links between networks, and physical distance between networks. Some routing metrics are manually entered into a router.s configuration by administrators who have a knowledge of the network.s physical layout and performance. Such metrics can include . Bandwidth: The total capacity of each network link to carry traffic between different networks in the internetwork. . Reliability: The relative amount of anticipated downtime for a given link between two networks. . Cost: A parameter roughly proportional to the actual cost in dollars of using each network link. Some wide area network (WAN) links might have more latency but cost much less. . Maximum Transmission Unit (MTU): The largest size of packet that the router can forward without segmenting the packet into subpackets. Segmentation of network traffic by routers adds additional latency to network communication. ROUTING PROTOCOL A protocol that enables routers to communicate with each other. Routing protocols are the software implementation of routing algorithms, mathematical procedures for determining the cost of various paths or routes through an internetwork so that traffic can be efficiently routed. Routing algorithms are used by dynamic routers, which exchange information with each other that enables them to build routing tables that accurately represent the possible paths on which packets may be routed through the network. A good routing protocol should have the following characteristics: . It should allow rapid convergence (recalculation) of routing table information when the network changes.for example, when a router goes down. . It should prevent routing loops from occurring. . It should select the optimal route for packets to be forwarded to reach their destination, based on routing metric information. Routing protocols can be classified in different ways. For example, you can classify them according to how they are affected by administrative boundaries in networks, which results in the following: . Interior Gateway Protocols (IGPs): These routing protocols are used to exchange information between routers within a given administrative area or autonomous system (AS). Other names for this kind of routing protocol are interior routing protocol or intradomain routing protocol. . Exterior Gateway Protocols (EGPs): These protocols are used to exchange information between routers in different administrative areas or autonomous systems (ASs). Other names for this kind of routing protocol are exterior routing protocol and interdomain routing protocol. Routing protocols can also be classified according to the type of routing algorithm they use, specifically: . Distance-vector routing protocols: These protocols employ the distance-vector routing algorithm to calculate their routing tables and send their entire routing table (or most of it) to other routers when updates are required. Because of their high overhead in communications, distance-vector routing protocols are useful only on relatively small networks with few routers. . Link-state routing protocols: These protocols use the link-state routing algorithm for routing table calculation and send only the state of their own interfaces to other routers, minimizing communications overhead and making these protocols suitable for large networks with many routers. Finally, routing protocols can be classified as either . Classful routing protocols: These use Internet Protocol (IP) address class distinctions to derive subnet masks. They are essentially simple protocols that are limited in their scalability to large networks. or . Classless routing protocols: These protocols propagate subnet masks and do not consider IP address classes when routing packets. In other words, they employ classless interdomain routing (CIDR) in their operation. Common examples of routing protocols include . Routing Information Protocol (RIP): Based on the distance vector routing algorithm and used in small to medium-sized internetworks, RIP is an intradomain routing protocol that can function only within a given routing domain. Microsoft Windows NT Server, Windows 2000 Server, and Windows .NET Server support RIP; a multihomed machine running Windows NT, Windows 2000, or Windows .NET Server can be used as a RIP router. . Interior Gateway Routing Protocol (IGRP): Based on the distance vector routing algorithm and used in medium-sized to large-sized internetworks, IGRP is an intradomain routing protocol that can function only within a given routing domain. IGRP uses a number of metrics to determine routing cost, including load, bandwidth, latency, reliability, and Maximum Transmission Unit (MTU). The router determines some of these factors dynamically as it inspects incoming traffic, but others are specified by the network administrator. IGRP supports multipath routing for load balancing and fault tolerance. . Open Shortest Path First (OSPF): Based on the link state routing algorithm and used in mediumsized to large-sized internetworks, OSPF is a hierarchical, intradomain routing protocol that is used within an autonomous system (AS). OSPF evolved from an earlier Open Systems Interconnection (OSI) routing protocol called intermediate-systemto- intermediate-system (IS-IS). OSPF supports multipath routing and uses one or more routing metrics, including bandwidth, reliability, load, latency, and MTU. If OSPF is configured to use more than one metric, it can also support type-ofservice (TOS) requests for differentiating traffic. . Exterior Gateway Protocol (EGP): An interdomain routing protocol for routing between different routing domains that are connected by a routing backbone such as the Internet. EGP was the first interdomain routing protocol and was designed in 1984 to enable communication between the core routers of the Internet. EGP does not use routing metrics.it simply keeps track of which networks are currently reachable through a given router. . Border Gateway Protocol (BGP): Another interdomain routing protocol created specifically to enable the core or backbone routers of the Internet to communicate with each other. BGP is superior to EGP because it can detect routing loops and use routing metrics, and it has displaced EGP as the interdomain protocol of choice for the Internet. Some less commonly used routing protocols include . NetWare Link Services Protocol (NLSP): Used in Novell NetWare 4.x as part of its Multi-Protocol Router (MPR). NLSP is based on a combination of OSPF routing and Novell.s Service Advertising Protocol (SAP) functions and is also based on the link state routing algorithm. . Routing Table Maintenance Protocol (RTMP): Used in AppleTalk networks and based on the distance vector routing algorithm. RTMP is derived from RIP. Remember that a routing protocol is different from a routable protocol. A routing protocol is used by routers to communicate with each other. A routable protocol, on the other hand, is a network protocol, such as Transmission Control Protocol/Internet Protocol (TCP/IP) or Internetwork Packet Exchange/Sequenced Packet Exchange (IPX/SPX), that allows packets to be routed across an internetwork. ROUTING TABLE An internal table that determines which interface to send a packet to, based on its destination network addresses. Routing tables enable both computers and routers to forward packets to their destinations. On Microsoft Windows platforms these routing tables are built automatically and are used to determine whether to forward specific packets to . The local network for destination hosts on the local network segment . A near-side router interface for destination hosts on a specific remote network segment . The default gateway for hosts in unknown locations To view the internal Transmission Control Protocol/ Internet Protocol (TCP/IP) routing table on a computer running Windows, type route print at the command prompt. The result is a typical routing table that looks something like the following: Active Routes: Gateway Network Address Netmask Address Interface Metric 127.0.0.0 255.0.0.0 127.0.0.1 127.0.0.1 1 172.16.8.0 255.255.255.0 172.16.8.50 172.16.8.50 1 172.16.8.50 255.255.255.255 127.0.0.1 127.0.0.1 1 172.16.255.255 255.255.255.255 172.16.8.50 172.16.8.50 1 224.0.0.0 224.0.0.0 172.16.8.50 172.16.8.50 1 255.255.255.255 255.255.255.255 172.16.8.50 172.16.8.50 1 This particular computer has a single network interface card (NIC) with the address 172.16.8.50. The columns of this table are interpreted as follows: . Network Address: A destination network address on the network . Netmask: The portion of the network address that must match in order for that route to be used . Gateway Address: Where the packet needs to be forwarded (a local NIC or a local router interface) . Interface: The address of the NIC through which the packet should be sent . Metric: The number of hops to the destination network DYNAMIC ROUTING A routing mechanism for dynamically exchanging routing information among routers on an internetwork. Dynamic routing operates using a dynamic routing protocol, such as Routing Information Protocol (RIP) or Open Shortest Path First (OSPF) Protocol. Routers that use dynamic routing are sometimes called dynamic routers. For dynamic routing to work, the routing protocol must be installed on each router in the internetwork. The routing table of one router is manually seeded with routing information for the first hop, and then the routing protocol takes over and dynamically builds the routing table for each router. Dynamic routers periodically exchange their routing information so that if the network is reconfigured or a router goes down, the routing tables of each router are automatically modified accordingly. Dynamic routers are much simpler to administer than static routers, but they are sometimes less secure because routing protocol information can be spoofed. If the network is reconfigured or a router goes down, it takes a certain period of time for this information to propagate between the various routers on the network. This router reconfiguration process is usually referred to as convergence. However, getting a dynamic router up and running is often as simple as connecting the interfaces and turning it on.routes are discovered automatically by communications with other routers on the network. Dynamic routers are also fault-tolerant, for when a router fails the other routers soon learn about it and adjust their routing tables accordingly to maintain communications across the network. Using dynamic routing protocols also creates additional network traffic due to routing table updates and exchanges, and different dynamic routing protocols offer their own advantages and disadvantages in this regard. Dynamic routers cannot exchange information with static routers. To configure static and dynamic routers to work together on the same internetwork, you must add manual routes to the routing tables of both types of routers. You can configure a multihomed Microsoft Windows 2000 or Windows .NET Server server as a dynamic RIP router by selecting Enable IP Forwarding on the Routing tab of the Transmission Control Protocol/Internet Protocol (TCP/IP) property sheet and then using the Services tab of the Network property sheet to add the RIP for Internet Protocol (IP) service to the server. Another example of a dynamic router is a multihomed computer running Windows 2000 Server with Routing and Remote Access Service (RRAS) and either RIP or OSPF configured. DYNAMIC ROUTING PROTOCOL A protocol that enables dynamic routing to be used to simplify management of a routed network. If we focus on Internet Protocol (IP) routing, which is the standard for the Internet and most corporate networks, several kinds of dynamic routing protocols can be deployed. These routing protocols can be classified in a hierarchical scheme as shown in the illustration. First, dynamic routing protocols can be one of two types: . Interior Gateway Protocols (IGPs): These are used to manage routing within autonomous systems (ASs). IGPs are further classified below. . Exterior Gateway Protocols (EGPs): These are used to manage routing between different ASs. The de facto example of an EGP is the Border Gateway Protocol (BGP) used on the Internet. G0DXX39 (new to 2E) IGPs can be further classified according to the type of algorithm used to build and distributed routing table information. Specifically, IGPs can employ the . Distance vector routing algorithm: Examples of dynamic routing protocols that use this algorithm include Routing Information Protocol (RIP), Interior Gateway Routing Protocol (IGRP), and Enhanced Interior Gateway Routing Protocol (EIGRP). . Link state routing algorithm: Examples of dynamic routing protocols that use this algorithm include Open Shortest Path First (OSPF) and DISTANCE VECTOR ROUTING ALGORITHM A routing algorithm used by certain types of routing protocols. Also called the Bellman-Ford algorithm after its originators, the distance vector routing is an algorithm designed to enable routers to maintain up-to-date information in their routing tables. The main alternative to distance vector routing is link state routing, which is discussed in its own article elswhere in this book. Using the distance vector method, each router on the internetwork maintains a routing table that contains one entry for each possible remote subnet on the network. To do this, each router periodically advertises its routing table information to routers in adjacent subnets. Each routing advertisement contains the following information about each route in that routing table: . The metric (hop count) for the route, which indicates the distance to the remote subnet . The vector (direction) in which the route is located These router advertisements are performed independently by all routers (that is, no synchronization exists between advertisements made by different routers). In addition, routers receiving advertisements do not generate acknowledgments, which reduces the overhead of routing protocol traffic. Routers select the route with the lowest cost to each possible destination and add this to their own routing tables. Routers in adjacent subnets then propagate this information to more distant subnets hop by hop until information from all routers has spread throughout the entire internetwork and convergence (agreement between routing tables on all routers in the internetwork) is attained. The end result is that each router on the network is aware of all remote subnets on the network and has information concerning the shortest path to get to each remote subnet. The Routing Information Protocol (RIP), which is supported by Microsoft Windows 2000, Windows XP, and Windows .NET Server, is one example of a dynamic routing protocol that uses the distance vector routing algorithm. Other examples are described in the article .distance vector routing protocol. elsewhere in this chapter. Distance vector routing protocols (that is, protocols based on the distance vector routing algorithm) are generally simpler to understand and easier to configure than link state routing algorithm protocols. To configure a router that supports distance vector routing, you basically connect the interfaces to the various subnets and turn the router on. The router automatically discovers its neighbors, which add the new router to their routing tables as required. The main disadvantage of the distance vector routing algorithm is that changes are propagated very slowly throughout a large internetwork because all routing tables must be recalculated. This is called the Slow Convergence Problem. When convergence is slow, it is possible that routing loops can temporarily form, which forward packets to black holes on the network, causing information to be lost. Most distance vector routing protocols implement use a technique such as the split horizon method to ensure that the chances of routing loops being formed are extremely small. Another disadvantage of distance vector routing is that routing tables can become extremely large, making distance vector routing protocols unsuitable for large internetworks, and that route advertising generates a large amount of traffic overhead. As a result of these issues, distance vector routing is generally best used in internetworks having 50 routers or fewer and in which the largest distance between two subnets is less than 16 hops. Despite these limitations, distance vector routing protocols are more popular than link state routing protocols, mainly because they are easier to set up and maintain (everything is automatic) and because their CPU processing requirements are small, which allows such protocols to be implemented on low-end and mid-end routers. LINK STATE ROUTING ALGORITHM An algorithm for dynamic routing that was designed to address scalability limitations of distance-vector routing protocols. The first dynamic routing protocols were based on the distance-vector routing algorithm, which required that routers periodically advertise their routing tables to neighboring routers. Routing protocols such as Routing Information Protocol (RIP) that are based on the distance-vector algorithm suffer from two main problems: large amounts of routing updates, which consume valuable network traffic, and slow convergence, which results in an inability to scale to large internetworks. As a result of these problems, the link state routing algorithm was developed. Routing protocols that use link state include . Open Shortest Path First (OSPF): This is the main link state protocol in use today and can be used to build large IP internetworks. . NetWare Link Services Protocol (NLSP): This is a legacy protocol used on Internetwork Packet Exchange (IPX) networks but not much used anymore. . Intermediate System to Intermediate System (IS-IS): This is not much used anymore. Link state routers advertise changes in network topology to other routers using link state packets (LSPs). The router advertises these LSPs only when changes occur in the network.for example, a router going down or a new router being brought up. When a network change occurs, LSPs are sent to all routers everywhere on the network, not just to neighboring routers as in distancevector routing. Using the LSPs a router receives from other routers on the network, link state routers use the Shortest Path First (SPF) algorithm to construct a logical tree that represents the topology of the entire network based on the local router as the root of the tree. The router then uses this tree to calculate the optimal paths to different parts of the network and populates routes in its internal routing table with this information. Every link state router on a network thus knows the exact router topology of the entire network. Link state routing protocols have several advantages over distance-vector protocols: . Faster convergence . Better scalability . Less traffic due to router updates On the other hand, there are some issues with link state protocols: . They are more processor-intensive and memoryintensive in their operation, hence routers using link state are usually more expensive. . They are more complex to configure than distance-vector routing protocols. . When several link state routers start up, there can be a large amount of network traffic associated with router discovery, a problem called link state flooding. This can temporarily saturate the network and make other communications impossible. . If LSPs are not synchronized properly, it is possible for routers to acquire wrong or incomplete link state information, causing black holes and other routing problems. Most link state routers now use time stamps and sequence numbers to ensure that convergence occurs properly. Link state routing protocols are classless routing protocols, a feature that enhances their scalability by allowing discontiguous subnets and variable length subnet masks (VLSMs) to be employed to reduce the amount of interrouter traffic propagated on the network. CONVERGENCE The process of updating routing tables after a change in the routing topology of an internetwork. When a change occurs in the routing infrastructure of an internetwork, information concerning the change needs to be replicated to all routers that need to know about it. The process by which all routers gradually become aware of the change that occurred is called convergence. Examples of occurrences that affect the routing infrastructure of an internetwork include adding a new router to the network, having an existing router fail on the network, and adding a new route to the routing table of a router on the network. When any of these situations arise, the routing protocol used to provide communications between the routers on your network is used to communicate these changes to all the routers that need to be aware of them. It typically takes time (from minutes to hours) for such changes to propagate completely through the internetwork.s routing infrastructure, and as routers become updated with the new routing information, the network is said to .converge. toward its final state. Convergence is important.if it does not occur fully, some routes may be unavailable on the network, making some parts of the network inaccessible. Furthermore, some packets may end up disappearing into .black holes. instead of arriving at their destination. INTERIOR GATEWAY PROTOCOL (IGP) Any routing protocol used to distribute routing information within an autonomous system (AS). Also known as interior routing protocols, interior gateway protocols (IGPs) specify how routers within an AS exchange routing information with other routers within the same AS. This is in contrast to exterior gateway protocols (EGPs), which facilitate the exchange of routing information between routers in different ASs. A network using IGP to route information within an autonomous system and exterior gateway protocol (EGP) to route information between autonomous systems. Examples of IGPs include . Routing Information Protocol (RIP): This is a popular protocol for small to medium-sized internetworks and is based on the distance-vector routing algorithm. . Open Shortest Path First (OSPF) Protocol: This is used mainly on medium-sized to large-sized internetworks and is based on the link-state routing algorithm. . Interior Gateway Routing Protocol (IGRP): This is a proprietary distance-vector routing protocol developed by Cisco Systems. ROUTING INFORMATION PROTOCOL (RIP) A popular distance vector routing protocol. Routing Information Protocol (RIP) is a dynamic routing protocol that is used to exchange routing table information between routers. Depending on the underlying network protocol being supported, this might be . RIP for IP: Used on Internet Protocol (IP) networks . RIP for IPX: Used on Internetwork Packet Exchange (IPX) networks Both of these routing protocols are generally referred to simply as RIP. RIP was also adapted for the AppleTalk networking system to form the basis of the Routing Table Maintenance Protocol (RTMP). RIP evolved from the Xerox Network Systems (XNS) protocol suite developed in the late 1970s and was designed in1980 as the first interior routing protocol, a protocol used to allow routers to communicate within an internetwork under a single administrative authority. RIP is implemented as a flat intradomain routing protocol, that is, an interior routing protocol with a flat routing space or routing domain. RIP first became popular as a result of its inclusion in release 4.2 of the Berkeley Software Distribution UNIX (BSD UNIX) platform. RIP was commonly used throughout the enterprise in the 1980s, but it was supplanted in the 1990s in large enterprises by Open Shortest Path First (OSPF), a link-state interior routing protocol. Today RIP is viewed as a legacy protocol suitable mainly for small internetworks of fewer than 50 routers or so. There are two versions of RIP: . RIPv1: This is the original version of RIP that was defined in RFC 1058. . RIPv2: This is a newer version of RIP defined in RFC 1723. RIPv2 is fully backward compatible with the earlier RIPv1 but is enhanced to support optional multicasting of routing table information to the multicast address of 224.0.0.9, the inclusion of subnet mask values in RIP announcements, and simple password protection to prevent rogue RIP routers from hijacking network traffic. The metric used by RIP-enabled routers for calculated routing table entries is based on the number of hops it takes for packets to reach their destination networks. RIP routers do not employ other routing metrics used in link state routing protocols such as load, bandwidth, latency, or Maximum Transmission Unit (MTU) in calculating these routing costs. The routing table of a RIP router contains the cost in hops of every path to every destination network in the internetwork. When a RIP router is first turned on, it broadcasts its presence using a General RIP Request message. This is done so that neighboring RIP routers can be alerted to send the original router advertisements of their routing tables. These RIP advertisements from neighboring RIP routers allow the original router to dynamically build its own routing tables. In addition, the original RIP router broadcasts to its neighbors all network IDs of locally attached networks so that they can update their own routing tables with this information. RIP-enabled routers broadcast their complete routing tables every 30 seconds over User Datagram Protocol (UDP) port 520. This adds some overhead to network traffic, but this information is information is propagated only throughout the local subnet and thus received only by routers that have a routing interface adjacent to this subnet. RIP does not support multipath routing. If a routing table has multiple routes for a single network ID, RIP stores the route with the lowest metric (number of hops to destination). RIP supports a maximum metric of 15, in other words, networks that are more than 15 hops away from the local network are unreachable when using RIP. The RIP metric is also independent of the packet.s Time to Live (TTL) value, so if two networks are separated by more than 15 routers, the packet is dropped even if the TTL value has not decremented to zero. When you try to send a packet to a network more than 15 hops away, a RIP router returns an Internet Control Message Protocol (ICMP) Destination Unreachable message. RIP is a well-supported industry standard routing protocol, but its maximum of 15 hops, together with the use of broadcast announcements, limits the use of RIP to small internetworks. Another disadvantage is that the routing table of a RIP-enabled router can become quite large since it must contain information about all possible routes to all possible subnets on the internetwork. Another weakness of RIP is that the routing table announcements are not synchronized over the internetwork and are sent without expectation of acknowledgments. In addition, routing entries in a RIP routing table time out 3 minutes after the last RIP announcement is received, so if a RIP router goes down, it takes time for this information to propagate throughout the internetwork, a problem known as slow convergence. This 3-minute timeout value exists so that information about routers that unexpectedly fail or go down can be propagated throughout the internetwork. If neighboring routers do not hear from a RIP router within 3 minutes, networks that are locally attached to the missing router are assigned a hop count of 16, making them unreachable. These factors can result in convergence problems and routing loops on large RIP-enabled internetworks. Another factor is that RIP advertisement packets are only 512 bytes in length and can contain a maximum of 25 different routing table entries, so a large routing table with hundreds of entries means that dozens of RIP packets are broadcast every 30 seconds. This can result in a lot of extra broadcast traffic on the local subnet, making RIP unsuitable for large internetworks or for networks having slow wide area network (WAN) links. Finally, RIP cannot take into account real-time network parameters such as congestion, latency, or router load when the RIP router determines whether to forward a packet along a specific route. An alternative to RIP is to use the Open Shortest Path First (OSPF) protocol, which can dynamically take into account such real-time network parameters, but implementing OSPF is fairly complex and may require you to upgrade existing routers. RIP routers should be turned off properly so that they can advertise the fact that they are being turned off to their neighboring routers. This notification, called a triggered update, declares all locally attached networks to the router as having a hop count of 16, making them unreachable. These triggered changes then propagate throughout the internetwork. If your RIP-enabled internetwork includes slower WAN links as well as fast local area network (LAN) links between networks, you can assign the WAN links hop values that are greater than 1 to compensate for their slower speed. For example, you can assign a T1 link between two networks a hop count of 3 or 4. However, the total hop count between any two networks must still be less than or equal to 15, and such a configuration makes sense only if the topology of the network is a complex mesh involving both fast LAN and slow WAN links. A RIP-enabled router that can receive RIP broadcasts but cannot send them is called a .silent RIP router.. INTERIOR GATEWAY ROUTING PROTOCOL (IGRP) An interior gateway protocol (IGP) developed by Cisco Systems. Interior Gateway Routing Protocol (IGRP) is a proprietary classful interior routing protocol that was developed by Cisco for two reasons: . Routing Information Protocol (RIP) was widely deployed but had several deficiencies, including a simplistic metric that did not mirror real-world network topologies and a limitation in maximum hop count to 15 hops. . Open Shortest Path First (OSPF) was being developed by the Internet Engineering Task Force (IETF) as a successor to RIP and as a routing protocol for larger internetworks, but development of OSPF was slow and the market needed a replacement for RIP. As a result, Cisco developed IGRP as a proprietary protocol for exchange of routing information within an autonomous system (AS). IGRP was tuned to provide optimal routes to ensure that communications within a network would be minimally disrupted should a router go down. IGMP is a stable protocol capable of supporting very large networks, supports up to 255 hops (100 by default), has fast convergence, provides rudimentary load balancing between parallel routes, and prevents routing loops from occurring. IGRP is based on the same distance-vector routing algorithm used by RIP. In this algorithm a router uses IGRP to exchange routing table updates with adjacent (neighboring) routers only. In contrast to the simple metric of RIP, which forwards packets over the route having the least number of hops, IGRP uses a complicated formula to determine the best route to select, basing the decision on link characteristics that mirror the network.s real topology and traffic flow. These factors include . The time it would take a packet to reach its destination when the network is quiet (no traffic) . The amount of bandwidth currently being used by each route (varies with time) . The bandwidth of the slowest hop over the route . The reliability of the route IGRP routing updates are issued every 90 seconds, compared to every 30 seconds for RIP. In addition, IGRP routing updates are issued in a compressed form that requires fewer packets per update than RIP. In addition, IGRP makes use of the following features to provide efficient routing: . Hold-down: Prevents a route that has previously gone bad from being reinstated as a valid route . Split horizon: Prevents routing loops from occurring between two routers . Poison reverse update: Reduces the chance of routing loops occurring between three or more routers Enhanced IGRP (EIGRP) is another proprietary interior routing protocol developed by Cisco. Despite the similarity in their names, EIGRP is a very different protocol from IGRP.