IP Routing Protocols

Routing overview

Routing is an OSI Layer 3 function. Routing is a hierarchical organizational scheme that allows individual addresses to be grouped together. These individual addresses are treated as a single unit until the destination address is needed for final delivery of the data. Routing is the process of finding the most efficient path from one device to another. The primary device that performs the routing process is the router.

The following are the two key functions of a router:

• Routers must maintain routing tables and make sure other routers know of changes in the network topology. This function is performed using a routing protocol to communicate network information with other routers.
• When packets arrive at an interface, the router must use the routing table to determine where to send them. The router switches the packets to the appropriate interface, adds the necessary framing information for the interface, and then transmits the frame.

A router is a network layer device that uses one or more routing metrics to determine the optimal path along which network traffic should be forwarded. Routing metrics are values used in determining the advantage of one route over another. Routing protocols use various combinations of metrics for determining the best path for data.

Routers interconnect network segments or entire networks. Routers pass data frames between networks based on Layer 3 information. Routers make logical decisions regarding the best path for the delivery of data. Routers then direct packets to the appropriate output port to be encapsulated for transmission. The encapsulation and de-encapsulation process occurs each time a packet transfers through a router. As shown in Figure 4, the process of sending data from one device to another involves the process of encapsulation and de-encapsulation. This process breaks up the data stream into segments, adds the appropriate headers and trailers then transmits the data. The de-encapsulation process is the opposite process, removing the headers and trailers, then recombining the data into a seamless stream.

This course focuses on the most common routable protocol, which is the Internet Protocol (IP). Other examples of routable protocols include IPX/SPX and AppleTalk. These protocols provide Layer 3 support. Non-routable protocols do not provide Layer 3 support. The most common non-routable protocol is NetBEUI. NetBEUI is a small, fast, and efficient protocol that is limited to frame delivery within one segment.

Routing versus switching

Routing is often contrasted with switching. Routing and switching might seem to perform the same function to the inexperienced observer. The primary difference is that switching occurs at Layer 2, the data link layer, of the OSI model and routing occurs at Layer 3. This distinction means routing and switching use different information in the process of moving data from source to destination.

The relationship between switching and routing parallels that of telephone local and long distance calls. When a telephone call is made to a number within the same area code, a local switch handles the call. However, the local switch can only keep track of its own local numbers. The local switch cannot handle all the telephone numbers in the world. When the switch receives a request for a call outside of its area code, it switches the call to a higher-level switch that recognizes area codes. The higher-level switch then switches the call so that it eventually gets to the local switch for the area code dialed.

The router performs a function similar to that of the higher-level switch in the telephone example. Figure shows the ARP tables for Layer 2 addressing and routing tables for Layer 3 addressing. Each computer and router interface maintains an ARP table for Layer 2 communication. The ARP table is only effective for the broadcast domain (or LAN) that it is connected to. The router also maintains a routing table that allows it to route data outside of the broadcast domain. Each ARP table contains an IP-MAC address pair (the MAC addresses in the graphic are represented by the acronym MAC, as the actual addresses are too long to fit in the graphic). The routing tables also track how the route was learned (in this case either directly connected [C] or learned by RIP [R]), the network IP address for reachable networks, the hop count or distance to those networks, and the interface the data must be sent out to get to the destination network.

The Layer 2 switch can only recognize its own local MAC addresses and cannot handle Layer 3 IP addresses. When a host has data for a non-local IP address, it sends the frame to the closest router, also known as its default gateway. The host uses the MAC address of the router as the destination MAC address.

A Layer 2 switch interconnects segments belonging to same logical network or subnetwork. If Host X needs to send a frame to a host on a different network or subnetwork, Host X sends the frame to the router that is also connected to the switch. The switch forwards the frame to the router based on the destination MAC address. The router examines the Layer 3 destination address of the packet to make the forwarding decision. Host X knows the IP address of the router because the IP configuration of the router also includes the IP address of the default gateway.

Just as a Layer 2 switch keeps a table of known MAC addresses, the router keeps a table of IP addresses known as a routing table. There is a difference between these two types of addresses. MAC addresses are not logically organized, but IP addresses are organized in a hierarchical manner. A Layer 2 device can handle a reasonable number of unorganized MAC addresses, because it will only have to search its table for those addresses within its segment. Routers need to handle a greater volume of addresses. Therefore, routers need an organized addressing system that can group similar addresses together and treat them as a single network unit until the data reaches the destination segment. If IP addresses were not organized, the Internet simply would not work. An example would be like a library that contained millions of individual pages of printed material in a large pile. This material is useless because it is impossible to locate an individual document. If the pages are organized into books and each page is individually identified, and the books are also listed in a book index, it becomes a lot easier to locate and use the data.

Another difference between switched and routed networks is switched networks do not block broadcasts. As a result, switches can be overwhelmed by broadcast storms. Routers block LAN broadcasts, so a broadcast storm only affects the broadcast domain from which it originated. Because routers block broadcasts, routers also provide a higher level of security and bandwidth control than switches.

Routed versus routing

Protocols used at the network layer that transfer data from one host to another across a router are called routed or routable protocols. Routed protocols transport data across a network. Routing protocols allow routers to choose the best path for data from source to destination. A routed protocol functions include the following: Includes any network protocol suite that provides enough information in its network layer address to allow a router to forward it to the next device and ultimately to its destination. Defines the format and use of the fields within a packet The Internet Protocol (IP) and Novell's Internetwork Packet Exchange (IPX) are examples of routed protocols. Other examples include DECnet, AppleTalk, Banyan VINES, and Xerox Network Systems (XNS). Routers use routing protocols to exchange routing tables and share routing information. In other words, routing protocols enable routers to route routed protocols. A routing protocol functions includes the following: Provides processes for sharing route information Allows routers to communicate with other routers to update and maintain the routing tables Examples of routing protocols that support the IP routed protocol include the Routing Information Protocol (RIP), Interior Gateway Routing Protocol (IGRP), Open Shortest Path First (OSPF), Border Gateway Protocol (BGP), and Enhanced IGRP (EIGRP).

Path determination

Path determination occurs at the network layer. Path determination enables a router to compare the destination address to the available routes in its routing table, and to select the best path. The routers learn of these available routes through static routing or dynamic routing. Routes configured manually by the network administrator are static routes. Routes learned by others routers using a routing protocol are dynamic routes. The router uses path determination to decide which port an incoming packet should be sent out of to travel on to its destination. This process is also referred to as routing the packet. Each router that the packet encounters along the way is called a hop. The hop count is the distanced traveled. Path determination can be compared to a person driving a car from one location in a city to another. The driver has a map that shows the streets that can be taken to get to the destination, just as a router has a routing table. The driver travels from one intersection to another just as a packet travels from one router to another in each hop. At any intersection, the driver can route himself by choosing to turn left, turn right, or go straight ahead. In the same manner, a router decides which outbound port the packet should be sent. The decisions of a driver are influenced by factors such as traffic on a road, the speed limit of the road, the number of lanes on the road, whether or not there is a toll on the road, and whether or not the road is frequently closed. Sometimes it is faster to take a longer route on a smaller, less crowded back street instead of a highway with a lot of traffic. Similarly, routers can make decisions based on the load, bandwidth, delay, cost, and reliability of a network link. The following process is used during path determination for every packet that is routed: The destination address is obtained from the packet. The mask of the first entry in the routing table is applied to the destination address. The masked destination and the routing table entry are compared. If there is a match, the packet is forwarded to the port that is associated with that table entry. If there is not a match, the next entry in the table is checked. If the packet does not match any entries in the table, the router checks to see if a default route has been set. If a default route has been set, the packet is forwarded to the associated port. A default route is a route that is configured by the network administrator as the route to use if there are no matches in the routing table. If there is no default route, the packet is discarded. Usually a message is sent back to the sending device indicating that the destination was unreachable.

Routing tables

Routers use routing protocols to build and maintain routing tables that contain route information. This aids in the process of path determination. Routing protocols fill routing tables with a variety of route information. This information varies depending on the routing protocol used. Routing tables contain the information necessary to forward data packets across connected networks. Layer 3 devices interconnect broadcast domains or LANs. A hierarchical addressing scheme is required for data transfer to occur.

Routers keep track of important information in their routing tables, including the following:

• Protocol type – The type of routing protocol that created the routing table entry
• Destination/next-hop associations – These associations tell a router that a particular destination is either directly connected to the router, or that it can be reached using another router called the “next-hop” on the way to the final destination. When a router receives an incoming packet, it checks the destination address and attempts to match this address with a routing table entry.
• Routing metric – Different routing protocols use different routing metrics. Routing metrics are used to determine the desirability of a route. For example, the Routing Information Protocol (RIP) uses hop count as its only routing metric. Interior Gateway Routing Protocol (IGRP) uses a combination of bandwidth, load, delay, and reliability metrics to create a composite metric value.
• Outbound interfaces – The interface that the data must be sent out on, in order to reach the final destination.

Routers communicate with one another to maintain their routing tables through the transmission of routing update messages. Some routing protocols transmit update messages periodically, while others send them only when there are changes in the network topology. Some protocols transmit the entire routing table in each update message, and some transmit only routes that have changed. By analyzing the routing updates from the neighboring routers, a router builds and maintains its routing table.

Routing algorithms and metrics

An algorithm is a detailed solution to a problem. In the case of routing packets, different routing protocols use different algorithms to decide which port an incoming packet should be sent to. Routing algorithms depend on metrics to make these decisions.

Routing protocols often have one or more of the following design goals:

• Optimization – Optimization describes the capability of the routing algorithm to select the best route. The route will depend on the metrics and metric weightings used in the calculation. For example, one algorithm may use both hop count and delay metrics, but may consider delay metrics as more important in the calculation.
• Simplicity and low overhead – The simpler the algorithm, the more efficiently it will be processed by the CPU and memory in the router. This is important so that the network can scale to large proportions, such as the Internet.
• Robustness and stability – A routing algorithm should perform correctly when confronted by unusual or unforeseen circumstances, such as hardware failures, high load conditions, and implementation errors.
• Flexibility – A routing algorithm should quickly adapt to a variety of network changes. These changes include router availability, router memory, changes in bandwidth, and network delay.
• Rapid convergence – Convergence is the process of agreement by all routers on available routes. When a network event causes changes in router availability, updates are needed to reestablish network connectivity. Routing algorithms that converge slowly can cause data to be undeliverable.

Routing algorithms use different metrics to determine the best route. Each routing algorithm interprets what is best in its own way. The routing algorithm generates a number, called the metric value, for each path through the network. Sophisticated routing algorithms base route selection on multiple metrics, combining them in a single composite metric value. Typically, smaller metric values indicate preferred paths.

Metrics can be based on a single characteristic of a path, or can be calculated based on several characteristics. The following are the metrics that are most commonly used by routing protocols:

• Bandwidth – The data capacity of a link. Normally, a 10-Mbps Ethernet link is preferable to a 64-kbps leased line.
• Delay – The length of time required to move a packet along each link from source to destination. Delay depends on the bandwidth of intermediate links, the amount of data that can be temporarily stored at each router, network congestion, and physical distance.
• Load – The amount of activity on a network resource such as a router or a link.
• Reliability – Usually a reference to the error rate of each network link.
• Hop count – The number of routers that a packet must travel through before reaching its destination. Each router the data must pass through is equal to one hop. A path that has a hop count of four indicates that data traveling along that path would have to pass through four routers before reaching its final destination. If multiple paths are available to a destination, the path with the least number of hops is preferred.
• Ticks – The delay on a data link using IBM PC clock ticks. One tick is approximately 1/18 second.
• Cost – An arbitrary value, usually based on bandwidth, monetary expense, or other measurement, that is assigned by a network administrator.

IGP and EGP

An autonomous system is a network or set of networks under common administrative control, such as the cisco.com domain. An autonomous system consists of routers that present a consistent view of routing to the external world.

Two families of routing protocols are Interior Gateway Protocols (IGPs) and Exterior Gateway Protocols (EGPs).

IGPs route data within an autonomous system.

• Routing Information Protocol (RIP) and (RIPv2)
• Interior Gateway Routing Protocol (IGRP)
• Enhanced Interior Gateway Routing Protocol (EIGRP)
• Open Shortest Path First (OSPF)
• Intermediate System-to-Intermediate System protocol (IS-IS)

EGPs route data between autonomous systems. An example of an EGP is Border Gateway Protocol (BGP).

Link state and distance vector

Routing protocols can be classified as either IGPs or EGPs, which describes whether a group of routers is under a single administration or not. IGPs can be further categorized as either distance-vector or link-state protocols. The distance-vector routing approach determines the distance and direction, vector, to any link in the internetwork. The distance may be the hop count to the link. Routers using distance-vector algorithms send all or part of their routing table entries to adjacent routers on a periodic basis. This happens even if there are no changes in the network. By receiving a routing update, a router can verify all the known routes and make changes to its routing table. This process is also known as “routing by rumor”. The understanding that a router has of the network is based upon the perspective of the adjacent router of the network topology. Examples of distance-vector protocols include the following: Routing Information Protocol (RIP) – The most common IGP in the Internet, RIP uses hop count as its only routing metric. Interior Gateway Routing Protocol (IGRP) – This IGP was developed by Cisco to address issues associated with routing in large, heterogeneous networks. Enhanced IGRP (EIGRP) – This Cisco-proprietary IGP includes many of the features of a link-state routing protocol. Because of this, it has been called a balanced-hybrid protocol, but it is really an advanced distance-vector routing protocol. Link-state routing protocols were designed to overcome limitations of distance vector routing protocols. Link-state routing protocols respond quickly to network changes sending trigger updates only when a network change has occurred. Link-state routing protocols send periodic updates, known as link-state refreshes, at longer time intervals, such as every 30 minutes. When a route or link changes, the device that detected the change creates a link-state advertisement (LSA) concerning that link. The LSA is then transmitted to all neighboring devices. Each routing device takes a copy of the LSA, updates its link-state database, and forwards the LSA to all neighboring devices. This flooding of LSAs is required to ensure that all routing devices create databases that accurately reflect the network topology before updating their routing tables. Link-state algorithms typically use their databases to create routing table entries that prefer the shortest path. Examples of link-state protocols include Open Shortest Path First (OSPF) and Intermediate System-to-Intermediate System (IS-IS).

Routing protocols

RIP is a distance vector routing protocol that uses hop count as its metric to determine the direction and distance to any link in the internetwork. If there are multiple paths to a destination, RIP selects the path with the least number of hops. However, because hop count is the only routing metric used by RIP, it does not always select the fastest path to a destination. Also, RIP cannot route a packet beyond 15 hops. RIP Version 1 (RIPv1) requires that all devices in the network use the same subnet mask, because it does not include subnet mask information in routing updates. This is also known as classful routing. RIP Version 2 (RIPv2) provides prefix routing, and does send subnet mask information in routing updates. This is also known as classless routing. With classless routing protocols, different subnets within the same network can have different subnet masks. The use of different subnet masks within the same network is referred to as variable-length subnet masking (VLSM). IGRP is a distance-vector routing protocol developed by Cisco. IGRP was developed specifically to address problems associated with routing in large networks that were beyond the range of protocols such as RIP. IGRP can select the fastest available path based on delay, bandwidth, load, and reliability. IGRP also has a much higher maximum hop count limit than RIP. IGRP uses only classful routing. OSPF is a link-state routing protocol developed by the Internet Engineering Task Force (IETF) in 1988. OSPF was written to address the needs of large, scalable internetworks that RIP could not. Intermediate System-to-Intermediate System (IS-IS) is a link-state routing protocol used for routed protocols other than IP. Integrated IS-IS is an expanded implementation of IS-IS that supports multiple routed protocols including IP. Like IGRP, EIGRP is a proprietary Cisco protocol. EIGRP is an advanced version of IGRP. Specifically, EIGRP provides superior operating efficiency such as fast convergence and low overhead bandwidth. EIGRP is an advanced distance-vector protocol that also uses some link-state protocol functions. Therefore, EIGRP is sometimes categorized as a hybrid routing protocol. Border Gateway Protocol (BGP) is an example of an External Gateway Protocol (EGP). BGP exchanges routing information between autonomous systems while guaranteeing loop-free path selection. BGP is the principal route advertising protocol used by major companies and ISPs on the Internet. BGP4 is the first version of BGP that supports classless interdomain routing (CIDR) and route aggregation. Unlike common Internal Gateway Protocols (IGPs), such as RIP, OSPF, and EIGRP, BGP does not use metrics like hop count, bandwidth, or delay. Instead, BGP makes routing decisions based on network policies, or rules using various BGP path attributes. Cisco Systems, Inc.