Chapter five continues our survey of internetworking devices. Chapter four began our climb up through the layers of the OSI Model: we left off with bridges -- Layer 2 devices. Chapter five moves up to the Network layer with routers, and then into the upper layers with Gateways.
First, a word of caution. In early literature, particularly in the UNIX community, the terms "router" and "gateway" were used synonymously. That is not the case here, or in current practice. A router is specifically a device which connects systems across a network at Layer 3, a gateway is a system that connects other systems through upper-layer services.
[ I ] ROUTERS
At first blush, bridging and routing seem to be redundant functions. Both provide services to connect systems on different segments of the network together. However, the mechanics of router operation are very different from bridge operation. This difference enables routers to perform functions that bridges cannot do, and connect larger networks than are possible with bridges.
Like bridges, routers store information about the layout of the network in tables. Unlike a bridge's forwarding table, a router's route database does not contain information about the location of individual stations. It contains information about the location of the segments of the network. A bridge would run out of table space trying to store all the addresses of all the stations on every segment of a very large network. Routers, because they deal with whole segments and not individual stations, have much less information to keep track of and can thus operate on much larger networks.
Bridges, because they operate at Layer 2 are confined to forwarding traffic to and from network segments with the same MAC. Because of things such as varying frame size, it would be very difficult to construct a bridge to forward traffic between an Ethernet and a Token-Ring segment. Routers, because they operate at Layer 3 are not bound by this restriction. In fact, connecting dissimilar networks is a primary job for routers. The packet fragmentation and reassembly abilities found at the network layer are there to assist in this very function.
Early versions of DOOM communicated with each other using broadcast frames. Imagine your pleasure at informing the boss that the network has ground to a halt because two jokers in accounting decided to play a little networked DOOM.
Large bridged networks have a weakness that can prove fatal in some circumstances. Each network technology has an address which serves as a broadcast address. All stations listen to broadcast traffic. Bridges will always forward a frame addressed to the broadcast address to all network segments that they are connected to. A malfunctioning, misconfigured, or poorly programed station can emit a flood of broadcast traffic. This traffic will be forwarded to every segment of a bridged network, and can reach such high levels as to bring network throughput to its knees. This unhappy event is a broadcast storm. Routers stop broadcast traffic cold. Routers do not forward broadcast traffic from segment to segment. A broadcast storm may be raging on one segment of the network, but stations on the other side of a router will not be affected.
Bridged networks are said to be flat networks. The entire network is falls under one Layer 3 network address. This can cause problems with upper layer protocols when the number of stations on the network becomes very large. Routed networks, because each segment has its own Layer 3 network address, can be built as hierarchical networks.
Routers are protocol dependant: they must understand a network layer protocol in order to forward it. This involvement with the network layer protocol means that a router can also understand what is inside a packet -- something a bridge cannot do -- and make judgements about forwarding a packet based on its contents. So, in addition to creating a hierarchical network, routers can be programmed to create political boundaries within a network. A boundary might be setup to permit users in one area access to the rest of the network, while denying access from the network at large into that area. For instance, the R&D lab might be on a segment connected to the main network by a router. The router might be programmed to permit R&D users to access any point on the network, but to keep other users from accessing systems on R&D's segment.
The graphic below shows routing's relationship to the OSI Model. The portion labeled "upper layer services" handles tasks such as route discovery and routing table maintenance.
Routing Mechanics
One of the primary differences between router operations and bridge operations is that routers are not transparent devices on the network. Stations know that a router is there, and communicate directly with the router when they have traffic destined for another segment of the network. Looking only at the Layer 2 (MAC) address, frames sent on a bridged network are addressed to the destination station. Frames sent on a routed network are addressed to the local router for passage onto the destination. It is the Layer 3 (Network) address that contains the address for the frame's ultimate destination.
Station B on network 1 has a packet of information to send to station D on network 2. The network layer on B creates a header with a destination address of 2D (station D on network 2), and a source address of 1B (station B on network 1). Layer 3 on B hands the packet down to Layer 2. Layer 2 needs to get the packet to the first stop on its journey. (B knows the address or R1 either through its setup or through router advertising, an upper layer process.) Layer 2 on B writes a header with a destination address of R1 and a source address of B, and sends the frame out on the wire.
Router R1 receives the frame from B: it recognizes itself as the destination in the frame's Layer 2 header. R1 copies the frame into memory, peels off the Layer 2 header, and hands the packet up to its Layer 3. Layer 3 on R1 reads the destination address in the packet's Layer 3 header. The destination network is 2: R1 knows how to get a packet to network 2 -- is has a direct connection! R1's Network layer hands the packet down to its Layer 2 for transmission to station D on network 2. R1's Data Link layer creates a Layer 2 header with a desination address of D, and a source address of R1, and sends the packet out on the wire on network 2. You should note that only the Layer 2 addresses have changed. The Layer 3 addresses will not change at any time.
Station D receives the frame from R1: it sees its MAC address in the frame's Layer 2 header. Layer 2 to on D strips off the Layer 2 header and hands the packet up to its Layer 3. The Network layer on D reads the Layer 3 header and discovers that the originator of the packet is station B on network 1. It retains this information and passes the data in the packet up to the next layer.
If R1 in this example was not directly connected to network 2, it would have looked in its routing table and found the address of the next router on the path from itself to network 2. It would have addressed the Layer 2 header of the frame to that next router and send the packet on its way. The packet would make its way "hop" by "hop" across the network to its destination. (Passing through a router is considered one hop.)
Providing a router's configuration information makes setting up a router a more complex task than setting up a bridge, which will learn all it needs to know about the network on the fly.
Distance Vector Routing
In the previous section on the mechanics of routing, we mentioned a routing table. Each router's routing table contains information about the segments of the network it is directly connected to, and information on how to get to other segments it is not directly connected to. Information about local network segments (the ones that the router is directly connected to) is programmed by the network adminstrator when the router is setup. The rest of the information is gathered while the router is in operation. There are two basic methods for gathering and computing this information. This section deals with one of them: the distance vector method. The next section deals with the other method: link state routing.
Routers using a distance vector routing protocol learn about the network from second-hand information: their neighbor routers send out routing information based on their routing tables. So, if a router learns that its neighbor can get to network P in 3 hops, the router assumes that it can get to P via its neighbor in 4 hops. When a router receives a routing information update from a neighbor router, it recomputes its routing table before sending out its own routing information. Routes are chosen on a "least cost" basis. The cost is computed by counting the number of hops between a router and the destination network. Another term sometimes used instead of hops, is "ticks".
Using the figure below, we will step through the process of generating a routing table for R1. R1 has just been rebooted and needs to learn the layout of the network.
| Network | Next Hop | Cost |
| A | Direct | 1 |
| B | Direct | 1 |
| C | Direct | 1 |
After a few seconds of operation, R1 receives routing information from R2. R2, which hasn't heard from R1 yet, sends the following table:
| Network | Next Hop | Cost |
| B | Direct | 1 |
| C | R4 | 3 |
| D | Direct | 1 |
| E | R4 | 2 |
R1 digests this information. It knows that it has a better route to network C than router R2, so it keeps its own entry. R1's routing table now looks like this:
| Network | Next Hop | Cost |
| A | Direct | 1 |
| B | Direct | 1 |
| C | Direct | 3 |
| D | R2 | 2 |
| E | R2 | 3 |
In another few seconds, R1 receives a routing information packet from R3. From R3's packet, R1 learns of a less costly route to network E. R3's route to network D is more expensive than the route it already learned from R2, so it keeps the older route. After this second update packet, R1 recomputes its table arriving at:
| Network | Next Hop | Cost |
| A | Direct | 1 |
| B | Direct | 1 |
| C | Direct | 3 |
| D | R2 | 2 |
| E | R3 | 2 |
Shortly R1 will send out its own routing update. R2 and R3, R1's neighbor routers will recieve the update and include R1's new information in their routing tables. (R1 is providing a route to network A, gives R2 a shorter route to C, and R3 a shorter route to B.) Within a few minues all of the routers will have exchanged updated routing information, and all of the routers will have a current view of the network. The process of sending and receiving updates will continue as long as the network is operating.
Distance-vector routing has an advantage over link-state routing in that its fairly simple to implement. Distance-vector is more "chatty" than link state, however. Link state routers send out routing information when something changes, distance vector routers send out routing information all the time. This can eat up precious bandwidth in low-speed WAN connections. Distance vector routers are also slow to remove routes for networks that have become unreachable. This slowness is due to the count to infinity phenomenon.
By the time R2 advertises again, R1's route to D has aged out: it sees that R2 is advertising a route to D at a cost of 4, so it replaces its old entry (D, via R2, cost 2) with a new one: D, via R2 cost 5.
This back-and-forth continues until the routes reach the maximum cost permitted ("infinity"), at which point the routers will remove the route to D from their tables. This process takes time. During this time, the routers on the network will erroneously think that a valid route to D exists. The process of propogating correct routing information after a network change (in this case a router failure) is called convergence. Because of the count to infinity phenomenon distance vector routers converge more slowly than link state routers.
Link State Routing
Link state routers use a different method to disseminate routing information. Link state routers first discover who their neighbor routers are. Then they exchange Link State Packets (LSPs). Each router on the network makes up its own LSP. A router's LSP contains only information about the networks the router is directly connected to. Routers save copies of other routers LSPs, so when a neighbor router requests an update (eg: when it has just been powered up) the router can send a complete set of LSPs in one transmission. This gives the neighbor a complete picture of the network all at once. This method is called flooding. Because routers receive copies of LSPs, and not digested information as with distance vector routing, link state routers build their routing tables from first hand information. Unlike link state routers, distance vector routers compute their routing table after sending out updated.
LSPs are only sent when something changes -- a new router announces its presence to a neighbor, a router discovers that a link has gone down -- so the amount of routing update traffic on a link state network is considerably lower than on a distance vector network.
Link state routing permits network administrators to use other cost metrics than hop count to set the cost of a route. This permits the network manager to configure the network so that routers avoid slow or congested links in favor of faster or less congested links -- even if that route involves more router hops than the slower or more congested one.
The diagram below shows the same network layout as in the distance vector example, but with link costs added. In the link state routing table example given below we will count the cost of the destination segment. You can not count the cost of the destination segment in your math; the results will be the same. The only important thing is that you do your cost accounting consistantly!
| Network | Cost |
| A | 2 |
| B | 2 |
| C | 6 |
After receiving copies of all the other routers' LSPs from one of its neighbors, R1's computes its new routing table. The table looks like:
| Network | Forward via | Cost |
| A | Direct | 2 |
| B | Direct | 2 |
| C | Direct | 6 |
| D | R2 | 5 |
| E | R2 | 9 |
Link state networks do not have the count to infinity phenomenon; when a change ocurrs to the network, dead routes are removed immediately because no router will advertise a route to the dead segment in its LSP. Link state routers also become fully effective faster because they receive a complete map of the network (in the form of copies of all the other routers' LSPs) in one update.
Tunneling
Protocol tunneling is an interesting trick that routers can perform. Say, for example, that you have two NetWare networks on either side of a corporate WAN. The NetWare networks use the IPX/SPX protocol, but the WAN only carries traffic using the TCP/IP protocol. How can you get the two NetWare networks to talk? Tunneling provides an answer.
With two routers that support tunneling you can encapsulate one protocol within another protocol and pass it through a network of routers that don't "speak" the encapsulated protocol. In our example, we'd use the two routers attached to the NetWare networks to encapsulate IPX packets within IP packets: the corporate WAN, which is IP-only, will pass along the encapsulated IPX packets in their IP wrappers. Tunneling is not terribly efficient -- it places a load on the routers at either end of the "tunnel" as they encapsulate and de-encapsulate packets. But, if there is no other option, tunneling can get your traffic safely through "hostile" terrain.
A new use of tunneling has to do with getting data through a different kind of hostile terrain than a corporate network with mismatched protocols. The Point-to-Point Tunneling Protocol (PPTP) is designed to permit remote users to establish a secure connection to their corporate offices over the Internet. PPTP tunnels encrypt private network traffic over the Internet so that telecommuters and road-warriors can access corporate resources without having their traffic fall prey to eavesdropping spies and 'net criminals.
Brouters
A hybrid system, called a brouter has been developed to handle networks with a mix of routable and non-routable protocols. Most network protocols, such as TCP/IP and IPX/SPX, support Layer 3 addressing and can be handled by routers. Some older protocols, such as IBM's Systems Network Architecture (SNA), do not support Layer 3 addresses and can only be passed along the network via bridges. To permit companies with mixed protocol networks which inclued non-routable protocols to move away from bridging to routing, router manufacturers developed "bridging routers", or brouters. A brouter will route all protocols which can route, and will treat other traffic using protocols it cannot route as if it were an IEEE 802.1 transparent bridge. Using the brouter functionality of a router you could support a routed IP network that also carried SNA via bridging.
Routers vs. Bridges
Because of the limitations of bridging, bridges are best used to segment a network to improve overall network throughput. Routers should be used whenever networks with different MAC methods need to be connected, when networks are connected by a WAN link, and when packet filtering is needed to create a political boundary.
Bridges are substantially cheaper and easier to install than routers. However, they do not provide the functionality needed on many large or diverse networks. The original large bridged networks of a decade ago have been replaced by routed networks because of the broadcast traffic control and flexibility limitations of bridges.
Bridging, in the form of Layer 2 switching, made a comeback in the middle '90s due to drastically reduced latencies available with new hardware based bridging, and is probably here to stay. However, the flattening of networks with Layer 2 switches reintroduced all of the problems the original bridged networks had. So, network equipment vendors have been developing hardware based routers to permit hierarchical routed networks with the same low latency as hardware bridging. The entire topic of Layer 2 and Layer 3 switching is discussed in detail in chapter ten.
[ II ] GATEWAYS
Gateways exist at the very top of our stack of internetworking devices. They are the most sophisticated of the devices we have looked at so far. Gateway functions operate at the higher levels of the OSI model (see below). Gateways are used to connect systems that have no protocols in common.
Because gatewaying data from one protocol to another involves processes at all levels of the OSI Model, gateways have the highest latency of all internetworking devices. Because of high latency and increased administrative burden, using a gateway should be your last choice in any given situation. However, if you are faced with two systems that must communicate but which share no protocols in common, a gateway can be an invaluable tool.
[ III ] CONCLUSION
Chapter five rounds out our survey of internetworking technologies. We've covered the basics of routing, and the two routing information propogation methods (distance vector and link state), as well as protocol tunneling and hybrid brouters. The chapter concludes at the top of the OSI Model with a brief look at gateways.
[ IV ] SELF CHECK
- How is latency affected by the type of internetworking device that
handles the traffic? Why might this be important?
- As a packet is routed across a network, what happens to the Layer 2
address? What happens to the Layer 3 address?
- What device would you use to segregate traffic on the teachers'
segment from traffic on the students' segment at a college?
- Draw your own network of routers. Pick one of the routers and
determine its routing table using the distance vector method.
- Go back to your network diagram. Assign each link an arbitrary
link cost. Recompute the router's routing table using the link state
method. How did the routes change?
- Could you use tunneling to carry a non-routable protocol through
a routed network, as an alternative to bridging? (Think theoretically!)
- How does a brouter handle traffic using a protocol it understands?
How about traffic on a protocol it doesn't understand?
- At what level of the OSI Model does a gateway operate? Why would
you use one?
|
[ CH 4 ]
[ TOC ]
[ CH 6 ] |
|
1999,2000 Shipman | Created 2-14-99 | Updated 2-6-00