would never be interested.”
Network equipment vendors do
not currently permit apps. An app
that fulfills a niche market is a dis-
traction from the vendor’s roadmap.
It could ruin the product’s “c’est la
mode.” Routers are too critical. Rout-
er protocols are difficult to design,
implementing them requires highly
specialized programming skills, and
verification is expensive. These excus-
es sound all-to familiar.
But What if it Became Easy?
To understand why writing routing
protocols is so difficult requires understanding how routing works in today’s networks. Networks are made of
endpoints (your PC and the server it is
talking to) and the intermediate devices that connect them. Between your
PC and www.acm.org there may be 20
to 100 routers (technically, routers and
switches but for the sake of simplicity
all packet-passing devices are called
routers in this article). Each router
has many network-interface jacks, or
ports. A packet arrives at one port, the
router examines it to determine where
it is trying to go, and sends it out the
port that will bring it one hop closer to
its destination.
When your PC sends a packet, it
does not know how to get to the destination. It simply marks the packet
with the desired destination, gives it to
the next hop, and trusts that this router, and all the following routers, will
eventually get the packet to the destination. The fact that this happens
trillions of times a second around the
world and nearly every packet reaches
its destination is awe-inspiring.
No “Internet map” exists for planning the route a packet must take to
reach its destination. Your PC does
not know ahead of time the entire
path to the destination. Neither does
the first router, nor the next. Every hop
trusts that the next hop will be one
step closer and eventually the packet
will reach the destination.
How does each router know what
the next hop should be? Every router
works independently to figure it out
for itself. The routers cooperate in an
algorithm that works like this: each
one periodically tells its neighbors
which networks it connects to, and
each neighbor accumulates this infor-
how does each
router know
what the next hop
should be?
Every router works
independently
to figure it out
for itself.
mation and uses it to deduce the de-
sign of the entire network. If a router
could think out loud, this is what you
might hear: “My neighbor on port 37
told me she is 10 hops away from net-
work 172.11.11.0, but the neighbor on
port 20 told me he is four hops away.
Aha! I’ll make a note that if I receive
a packet for network 172.11.11.0, I
should send it out port 20. Four hops
is better than 10!”
Although they share topological
information, routers do the route cal-
culations independently. Even if the
network topology means two nearby
routers will calculate similar results,
they do not share the results of the
overlapping calculations. Since every
CPU cycle uses a certain amount of
power, this duplication of effort is not
energy efficient.
Fortunately, routers need to be
concerned with only their particular
organization’s network, not the entire
Internet. Generally, a router stores
the complete route table for only its
part of the Internet—the company,
university, or ISP it is part of (its autonomous domain). Packets destined
for outside that domain are sent to
gateway routers, which interconnect
with other organizations. Another algorithm determines how the first set
of routers knows where the gateway
routers are. The combination of these
two algorithms requires less RAM and
CPU horsepower than if every router
had to know the entire Internet. If it
were not for this optimization, then
every router would need enough RAM
and CPU horsepower to store an inventory of the entire Internet. The cost
would be staggering.
The routing algorithms are complicated by the fact that routers are given
clues and must infer what they need
to know. For example, the conclusion
that “port 20 is the best place to send
packets destined for 172.11.11.0” is
inferred from clues given by other
routers. A router has no way of sending a question to another router.
Imagine if automobiles had no windows but you could talk to any driver
within 25 feet. Rather than knowing
what is ahead, you would have to infer
a worldview based on what everyone
else is saying. If everyone were using
the same vocabulary and the same
system of cooperative logical reason-
