In many networks, there are various possible routes a message can take to get from one computer to another. For example, in Figure 5.9, a message sent from computer A to computer F could travel first to computer B then to computer C to get to computer F, or it could go to computer D first and then to computer E to get to computer F.
Figure 5.9 A typical network
Routing is the process of determining the route or path through the network that a message will travel from the sending computer to the receiving computer. Every computer that performs routing has a routing table developed by the network manager that specifies how messages will travel through the network. In its simplest form, the routing table is a two-column table. The first column lists every computer in the network, and the second column lists the computer to which the sending computer should send messages if they are destined for the computer in the first column. Figure 5.10 shows a routing table that might be used by computer B in Figure 5.9.6
Obviously, the Internet is more complicated than the simple network in Figure 5.9; it has millions of computers attached. How can we possibly route messages on the Internet? It turns out that most parts of the Internet are connected only to a few other parts of the Internet. That is, any one part of the Internet, such as your university, probably has only two or three connections into the Internet. When messages arrive at the computer that connects your university to the Internet, that computer must choose over which circuit to send the message. Imagine, for example, that computer B in Figure 5.9 is the computer that connects your university to the Internet and that the other computers in this figure are different parts of the Internet.
|
Destination |
Route |
|
A |
A |
|
C |
C |
|
D |
A |
|
E |
E |
|
F |
E |
|
G |
C |
Figure 5.10 Routing table
Some parts of the Internet are best reached by one circuit (e.g., the part represented by computer A), whereas others are best reached via the other circuit (e.g., the part represented by computer E). In this case, the computer is told that messages sent to IP addresses in a certain range (e.g., 128.x.x.x) should go on one circuit, whereas messages to addresses in a different range (e.g., 12.x.x.x) should go on a different circuit. In some cases, computers can be reached equally well on either circuit (e.g., computer D), in which case the network manager may arbitrarily choose one circuit or configure the software to choose either circuit as it likes.
Imagine yourself as a packet that needs to travel over the Internet from the University of Texas to the University of Alberta (e.g., an HTTP request). As you leave the University of Texas on the Internet, you reach a fork in the path. A sign says Texas this way—all other destinations straight ahead (Figure 5.11). Although this sign does not explicitly tell you how to get to the University of Alberta, it is clear that you must continue on straight ahead. As you reach the next fork in the path, there is another sign. Once again, your destination is not listed, but nonetheless, the direction you need to take is clear. The next sign includes your destination (Canada) in a range of destinations, so you turn down that path. The next sign again contains your destination (Alberta) in a range of destinations, so you take that path. At last, you see a sign to your destination. This is one way in which the Internet works.
Because routing is an important function, we often use special-purpose devices called routers to build and maintain the routing tables and perform routing.
Types of Routing
There are three fundamental approaches to routing: centralized routing, static routing, and dynamic routing. As you will see in the TCP/IP Example section later in this topic, the Internet uses all three approaches.
Centralized Routing With centralized routing, all routing decisions are made by one central computer or router. Centralized routing is commonly used in host-based networks,and in this case, routing decisions are rather simple. All computers are connected to the central computer, so any message that needs to be routed is simply sent to the central computer, which in turn retransmits the message on the appropriate circuit to the destination.
Static Routing Static routing is decentralized, which means that all computers or routers in the network make their own routing decisions following a formal routing protocol. In MANs and WANs, the routing table for each computer is developed by its individual network manager (although network managers often share information). In LANs or backbones, the routing tables used by all computers on the network are usually developed by one individual or a committee. Most decentralized routing protocols are self-adjusting, meaning that they can automatically adapt to changes in the network configuration (e.g., adding and deleting computers and circuits).
With static routing, routing decisions are made in a fixed manner by individual computers or routers. The routing table is developed by the network manager, and it changes only when computers are added to or removed from the network.
Figure 5.11 Internet routing
For example, if the computer recognizes that a circuit is broken or unusable (e.g., after the data link layer retry limit has been exceeded without receiving an acknowledgment), the computer will update the routing table to indicate the failed circuit. If an alternate route is available, it will be used for all subsequent messages. Otherwise, messages will be stored until the circuit is repaired. Static routing is commonly used in networks that have few routing options that seldom change.
Dynamic Routing With dynamic routing (or adaptive routing), routing decisions are made in a decentralized manner by individual computers. This approach is used when there are multiple routes through a network, and it is important to select the best route. Dynamic routing attempts to improve network performance by routing messages over the fastest possible route, away from busy circuits and busy computers. An initial routing table is developed by the network manager but is continuously updated by the computers themselves to reflect changing network conditions.
With distance vector dynamic routing, computers or routers count the number of hops along a route. A hop is one circuit, so that a route from one computer to another that passes through only one other computer (e.g., from A to C through B in Figure 5.9) would be two hops whereas a route that passes through three computers (e.g., A to C via D, E, and F in Figure 5.9) would be four hops. With this approach, computers periodically (usually every one to two minutes) exchange information on the hop count and sometimes the relative speed of the circuits in route and how busy they are with their neighbors.
With link state dynamic routing, computers or routers track the number of hops in the route, the speed of the circuits in each route, and how busy each route is. In other words, rather than knowing just a route’s distance, link state routing tries to determine how fast each possible route is. Each computer or router periodically (usually every 30 seconds or when a major change occurs) exchanges this information with other computers or routers in the network (not just their neighbors) so that each computer or router has the most accurate information possible. Link state protocols are preferred to distance vector protocols in large networks because they spread more reliable routing information throughout the entire network when major changes occur in the network. They are said to converge more quickly.
There are two drawbacks to dynamic routing. First, it requires more processing by each computer or router in the network than does centralized routing or static routing. Computing resources are devoted to adjusting routing tables rather than to sending messages, which can slow down the network. Second, the transmission of routing information "wastes" network capacity. Some dynamic routing protocols transmit status information very frequently, which can significantly reduce performance.
Routing Protocols
A routing protocol is a protocol that is used to exchange information among computers to enable them to build and maintain their routing tables. You can think of a routing protocol as the language that is used to build the signs in Figure 5.11. When new paths are added or paths are broken and cannot be used, messages are sent among computers using the routing protocol.
It can be useful to know all possible routes to a given destination. However, as a network gets quite large, knowing all possible routes becomes impractical; there are simply too many possible routes. Even at some modest number of computers, dynamic routing protocols become impractical because of the amount of network traffic they generate. For this reason, networks are often subdivided into autonomous systems of networks.
An autonomous system is simply a network operated by one organization, such as IBM or Indiana University, or an organization that runs one part of the Internet. Remember that we said the Internet was simply a network of networks. Each part of the Internet is run by a separate organization such as AT&T, MCI, and so on. Each part of the Internet or each large organizational network connected to the Internet can be a separate autonomous system.
The computers within each autonomous system know about the other computers in that system and usually exchange routing information because the number of computers is kept manageable. If an autonomous systems grows too large, it can be split into smaller parts. The routing protocols used inside an autonomous system are called interior routing protocols.
Protocols used between autonomous systems are called exterior routing protocols. Although interior routing protocols are usually designed to provide detailed routing information about all or most computers inside the autonomous systems, exterior protocols are designed to be more careful in the information they provide. Usually, exterior protocols provide information about only the preferred or the best routes rather than all possible routes.
There are many different protocols that are used to exchange routing information. Five are commonly used on the Internet: Border Gateway Protocol (BGP), Internet Control Message Protocol (ICMP), Routing Information Protocol (RIP), Intermediate System to Intermediate System (IS-IS) Open Shortest Path First (OSPF), and Enhanced Interior Gateway Routing Protocol (EIGRP).
Border Gateway Protocol (BGP) is a dynamic distance vector exterior routing protocol used on the Internet to exchange routing information between autonomous systems—that is, large sections of the Internet. Although BGP is the preferred routing protocol between Internet sections, it is seldom used inside companies because it is large, complex, and often hard to administer.
Internet Control Message Protocol (ICMP) is the simplest interior routing protocol on the Internet. ICMP is simply an error-reporting protocol that enables computers to report routing errors to message senders. ICMP also has a very limited ability to update routing tables.7
Routing Information Protocol (RIP) is a dynamic distance vector interior routing protocol that is commonly used in smaller networks, such as those operated by one organization. The network manager uses RIP to develop the routing table. When new computers are added, RIP simply counts the number of computers in the possible routes to the destination and selects the route with the least number. Computers using RIP send broadcast messages every minute or so (the timing is set by the network manager) announcing their routing status to all other computers. RIP is used by both TCP/IP and IPX/SPX.
Intermediate System to Intermediate System (IS-IS) is a link state interior routing protocol that is commonly used in large networks. IS-IS is an ISO protocol that has been added to many TCP/IP networks.
Open Shortest Path First (OSPF) is a dynamic link state interior routing protocol that is commonly used on the Internet. It uses the number of computers in a route as well as network traffic and error rates to select the best route. OSPF is more efficient than RIP because it normally doesn’t use broadcast messages. Instead, it selectively sends status update messages directly to selected computers or routers. OSPF is the preferred interior routing protocol used by TCP/IP.
Routing on the Internet
TECHNICAL FOCUS
The Internet is a network of autonomous system networks. Each autonomous system operates its own interior routing protocol while using Border Gateway Protocol (BGP) as the exterior routing protocol to exchange information with the other autonomous systems on the Internet. Although there are a number of interior routing protocols, Open Shortest Path First (OSPF) is the preferred protocol, and most organizations that run the autonomous systems forming large parts of the Internet use OSPF.
Figure 5.12 shows how a small part of the Internet might operate. In this example, there are six autonomous systems (e.g., Sprint, AT&T), three of which we have shown in more detail. Each autonomous system has a border router that connects it to the adjacent autonomous systems and exchanges route information via BGP. In this example, autonomous system A is connected to autonomous system B, which in turn is connected to autonomous system C. A is also connected to C via a route through systems D and E. If someone in A wants to send a message to someone in C, the message should be routed through B because it is the fastest route. The autonomous systems must share route information via BGP so that the border routers in each system know what routes are preferred. In this case, B would inform A that there is a route through it to C (and a route to E), and D would inform A that it has a route to E, but D would not inform A that there is a route through it to C. The border router in A would then have to decide which route to use to reach E.
Each autonomous system can use a different interior routing protocol. In this example, B is a rather simple network with only a few devices and routes, and it uses RIP, a simpler protocol in which all routers broadcast route information to their neighbors every minute or so. A and C are more complex networks and use OSPF. Most organizations that use OSPF create a special router called a designated router to managethe routing information. Every 15 minutes or so, each router sends its routing information to the designated router, which then broadcasts the revised routing table information to all other routers. If no designated router is used, then every router would have to broadcast its routing information to all other routers, which would result in a very large number of messages. In the case of autonomous system C, which has seven routers, this would require 42 separate messages (seven routers each sending to six others). By using a designated router, we now have only 12 separate messages (the six other routers sending to the designated router, and the designated router sending the complete set of revised information back to the other six).
Figure 5.12 Routing on the Internet with Border Gateway Protocol (BGP), Open Shortest Path First (OSPF), and Routing Information Protocol (RIP)
Enhanced Interior Gateway Routing Protocol (EIGRP) is a dynamic link state interior routing protocol developed by Cisco and is commonly used inside organizations. As you might expect, EIGRP is an improved version of Interior Gateway Routing Protocol (IGRP). EIGRP records information about a route’s transmission capacity, delay, reliability, and load. EIGRP is unique in that computer or routers store their own routing table as well as the routing tables for all of their neighbors so they have a more accurate understanding of the network.
Multicasting
The most common type of message in a network is the transmission between two computers. One computer sends a message to another computer (e.g., a client requesting a Web page). This is called a unicast message. Earlier in the topic, we introduced the concept of a broadcast message that is sent to all computers on a specific LAN or subnet. A third type of message called a multicast message is used to send the same message to a group of computers.
Consider a videoconferencing situation in which four people want to participate in the same conference. Each computer could send the same voice and video data from its camera to the computers of each of the other three participants using unicasts. In this case, each computer would send three identical messages, each addressed to the three different computers. This would work but would require a lot of network capacity. Alternately, each computer could send one broadcast message. This would reduce network traffic (because each computer would send only one message), but every computer on the network would process it, distracting them from other tasks. Broadcast messages usually are transmitted only within the same LAN or subnet, so this would not work if one of the computers were outside the subnet.
The solution is multicast messaging. Computers wishing to participate in a multicast send a message to the sending computer or some other computer performing routing along the way using a special type of packet called Internet Group Management Protocol (IGMP). Each multicast group is assigned a special IP address to identify the group. Any computer performing routing knows to route all multicast messages with this IP address onto the subnet that contains the requesting computer. The routing computer sets the data link layer address on multicast messages to a matching multicast data link layer address. Each requesting computer must inform its data link layer software to process incoming messages with this multicast data link layer address. When the multicast session ends (e.g., the videoconference is over), the client computer sends another IGMP message to the organizing computer or the computer performing routing to remove it from the multicast group.
Captain D’s Gets Cooking with Multicast
MANAGEMENT FOCUS
Captain D’s has more than 500 company owned and franchised fast food restaurants across North America. Each restaurant has a small low-speed satellite link that can send and receive data at speeds similar to broadband Internet access (384 Kbps to 1.2 Mbps).
Captain D’s used to send its monthly software updates to each of its restaurants one at a time, which meant transferring each file 500 times, once to each restaurant. You don’t have to be a network wizard to realize that this is slow and redundant.
Captain D’s now uses multicasting to send monthly software updates to all its restaurants at once. What once took hours is now accomplished in minutes.
Multicasting also enables Captain D’s to send large human resource file updates each week to all restaurants and to transmit computer-based training videos to all restaurants each quarter. The training videos range in size from 500-1000 megabytes, so without multicasting it would be impossible to use the satellite network to transmit the videos.
