1.3.2 How Do Packet Make Their Way Through Packet-Switched Networks?

Earlier we said that a router takes a packet arriving on one of its attached communication
links and forwards that packet on to another of its attached communication
links. But how does the router determine the link onto which it should forward the
packet? This is actually done in different ways by different types of computer networks.
In this introductory chapter, we will describe one popular approach, namely,
the approach employed by the Internet.
In the Internet, each packet traversing the network contains the address of the
packet's destination in its header. As with postal addresses, this address has a hierarchical
structure. When a packet arrives at a router in the network, the router examines
a portion of the packet's destination address and forwards the packet to an
adjacent router. More specifically, each router has a forwarding table that maps
destination addresses (or portions of the destination addresses) to outbound links.
When a packet arrives at a router, the router examines the address and searches its
table using this destination address to find the appropriate outbound link. The router
then directs the packet to this outbound link.
We just learned that a router uses a packet's destination address to index a forwarding
table and detennine the appropriate outbound link. But this statement begs
yet another question: how do forwarding tables get set? Are they configured by hand
in each and every router, or does the Internet use a more automated procedure? This
issue will be studied in depth in Chapter 4. But to whet your appetite here, we'll note
now that the Internet has a number of special routing protocols that are used to automatically
set the forwarding tables. A routing protocol may, for example, determine
the shortest path from each router to each destination and use the shortest path
results to configure the forwarding tables in the routers.
The end-to-end routing process is analogous to a car driver who does not use
maps but instead prefers to ask for directions. For example, suppose Joe is driving
from Philadelphia to 156 Lakeside Drive in Orlando, Florida. Joe first drives to his
neighborhood gas station and asks how to get to 156 Lakeside Dri ve in Orlando,
Florida. The gas station attendant extracts the Florida portion of the address and tells
Joe that he needs to get onto the interstate highway 1-95 South, which has an
entrance just next to the gas station. He also tells Joe that once he enters Florida he
should ask someone else there. Joe then takes 1-95 South until he gets to Jacksonville,
Florida, at which point he asks another gas station attendant for directions.
The attendant extracts the Orlando portion of the address and tells Joe that he should
continue on 1-95 to Daytona Beach and then ask someone else. In Daytona Beach
another gas station attendant also extracts the Orlando portion of the address and
tells Joe that he should take 1-4 directly to Orlando. Joe takes 1-4 and gets off at the
Orlando exit. Joe goes to another gas station attendant, and this time the attendant
extracts the Lakeside Drive portion of the address and tells Joe the road he must follow
to get to Lakeside Drive. Once Joe reaches Lakeside Drive, he asks a kid on a bicycle how to get to his destination. The kid extracts the 156 portion of the address
and points to the house. Joe finally reaches his ultimate destination.
In the above analogy, the gas-station attendants and kids on bicycles are analogous
to routers. Their forwarding tables, which are in their brains, have been configured
by years of experience.
How would you actually like to see the end-to-end route that packets take in the
Internet? We now invite you to get your hands dirty by interacting with the Traceroute
program, by visiting the site http://www.traceroute.org. (For a discussion of
Traceroute, see Section 1.4.)