Our final topic is routing, or how packets are directed through the maze of networks in order to arrive at their destination host. Routing is trivial on LANs because the topologies are either very simple or very regular. In an Ethernet, every transmitted message is heard by every attached host, called broadcasting, so routing is unnecessary. Token rings always transmit packets to their one downwind neighbor, so routing is trivially simple. Star topologies also have trivial routing. All messages that a host sends are sent to the hub, which then forwards them to their destination. Only in meshes is routing tricky.
The original ARPANET was a mesh with a number of minicomputers called IMPs (Interface Message Processors) acting as the routers. Hosts attached to these IMPs, so hosts didn't have to worry about routing -- they sent everything to their attached IMP. However, the IMPs used a sophisticated algorithm for determining the best route for packets.
Fig. 23.13.1 shows a typical mesh network. Hosts are not shown, only the IMPs, which are assigned letters. The ten links, wires that carry the packets, are labeled L1 through L10, and their maximum speed in Kilobits per second are given. L1 has a maximum speed of 56,000 bits per second.
The heart of the routing problem is to figure out which IMP to send a packet that is not meant for you, but is simply passing through. For example, suppose that a packet originates at a host attached to IMP A and is destined for a host attached to IMP I. We will use the shortcut by saying that the packet originates at A and is destined for I. Since there is no direct connection between A and I, it must go through some intermediate IMPs, and there are numerous choices.
Every router has a table that says "If an incoming packet is destined for X, then send it to Y" where X is an IMP that is not directly connected to this router and Y is one that is.
Following is a routing table for IMP B in Fig. 23.13.1:
Destination Send to...
--------------------------
F E
G E
I D
H E
Notice that B is directly connected to A, C, D and E so these need not be mentioned in the table. Only IMPs that are not directly connected are listed in the table. The Send to... columns mentions only IMPs that are directly connected to B. Since the B to E link, L3, runs at 128 kbps, it is very fast and can handle a lot of traffic. In order to keep it from getting bogged down, we specify that some traffic such as that going to I should go through D instead.
Another way to specify the routing table for B would be the following:
Destination Send to... -------------------------- I D default E
In this smaller table, all packets go to E unless otherwise directed.
There are two basic approaches to constructing these routing tables. The static method is to write them all once and for all, based on careful consideration of how far away the IMPs are and the speed of the lines between them. However, traffic patterns may vary and certain lines may become clogged due to overuse. In this case, dynamic methods of maintaining and changing the routing tables are better, which is the approach that ARPANET and now the Internet use.
Every so often, a router (they are no longer called IMPs in the modern Internet) recalculates its routing table by averaging how many packets have gone through a particular line to an attached router. If a certain line is being used too much, then some traffic that was formerly directed through it is rerouted to another. Also, if a line goes down due to some technical problem then the routing tables have to be rewritten. In order to determine where those downed lines are, routers typically send a steady stream of AYA packets: Are You Alive? The router at the other end of the line, upon receiving this, will send back IAA, "I am Alive!" Sometimes it compares timestamps to measure how far out of synch clocks are and how long it took for the packet to arrive. This kind of polling by packets is called pinging because it resembles sonar probing of the ocean floor.
There are many sophisticated algorithms that attempt to find the best, or nearly the best, routes that a packet can go to get from one host to another. It is widely believed that in order to find the very best route, extremely time-consuming algorithms would have to be run, algorithms that are too expensive to use, so more approximate algorithms are used.
We have only touched on the highlights of networking; entire courses are devoted to this topic. There are many open problems still to be solved and many areas that urgently need more work. Growing reliance on worldwide networking makes this a very exciting time to be studying networking.