Routing is the algorithm by which a network directs a packet from
its source to its destination. To appreciate the problem, watch a
small child trying to find a table in a restaurant. From the adult
point of view the structure of the dining room is seen and an
optimal route easily chosen. The child, however, is presented with
a set of paths between tables where a good path, let alone the
optimal one to the goal is not discernible.
A little more background might be appropriate. IP gateways (more
correctly routers) are boxes which have connections to multiple
networks and pass traffic between these nets. They decide how the
packet is to be sent based on the information in the IP header of
the packet and the state of the network. Each interface on a
router has an unique address appropriate to the network to which
it is connected. The information in the IP header which is used is
primarily the destination address. Other information (e.g. type of
service) is largely ignored at this time. The state of the network
is determined by the routers passing information among themselves.
The distribution of the database (what each node knows), the form
of the updates, and metrics used to measure the value of a
connection, are the parameters which determine the characteristics
of a routing protocol.
Under some algorithms each node in the network has complete
knowledge of the state of the network (the adult algorithm).
This implies the nodes must have larger amounts of local
storage and enough CPU to search the large tables in a short
enough time (remember this must be done for each packet).
Also, routing updates usually contain only changes to the
existing information (or you spend a large amount of the
network capacity passing around megabyte routing updates).
This type of algorithm has several problems. Since the only
way the routing information can be passed around is across
the network and the propagation time is non-trivial, the
view of the network at each node is a correct historical
view of the network at varying times in the past. (The
adult algorithm, but rather than looking directly at the
dining area, looking at a photograph of the dining room.
One is likely to pick the optimal route and find a bus-cart
has moved in to block the path after the photo was taken).
These inconsistencies can cause circular routes (called
routing loops) where once a packet enters it is routed in a
closed path until its time to live (TTL) field expires and
it is discarded.
Other algorithms may know about only a subset of the network. To
prevent loops in these protocols, they are usually used in a
hierarchical network. They know completely about their own area,
but to leave that area they go to one particular place (the
default gateway). Typically these are used in smaller networks
Routing protocols in current use:
- Static (no protocol-table/default routing)
Don't laugh. It is probably the most reliable, easiest
to implement, and least likely to get one into trouble
for a small network or a leaf on the Internet. This
is, also, the only method available on some
CPU-operating system combinations. If a host is connected
to an Ethernet which has only one gateway off of
it, one should make that the default gateway for the
host and do no other routing. (Of course that gateway
may pass the reachablity information somehow on the
other side of itself).
One word of warning, it is only with extreme caution
that one should use static routes in the middle of a
network which is also using dynamic routing. The
routers passing dynamic information are sometimes confused
by conflicting dynamic and static routes. If
your host is on an ethernet with multiple routers to
other networks on it and the routers are doing dynamic
routing among themselves, it is usually better to take
part in the dynamic routing than to use static routes.
RIP is a routing protocol based on XNS (Xerox Network
System) adapted for IP networks. It is used by many
routers (Proteon, cisco, UB...) and many BSD Unix systems.
BSD systems typically run a program called
routed to exchange information with other systems running RIP.
RIP works best for nets of small diameter
where the links are of equal speed. The reason for
this is that the metric used to determine which path is
best is the hop-count. A hop is a traversal across a
gateway. So, all machines on the same Ethernet are
zero hops away. If a router connects connects two networks
directly, a machine on the other side of the
router is one hop away.... As the routing information
is passed through a gateway, the gateway adds one to
the hop counts to keep them consistent across the network.
The diameter of a network is defined as the
largest hop-count possible within a network. Unfortunately,
a hop count of 16 is defined as infinity in
RIP meaning the link is down. Therefore, RIP will not
allow hosts separated by more than 15 gateways in the
RIP space to communicate.
The other problem with hop-count metrics is that if
links have different speeds, that difference is not
reflected in the hop-count. So a one hop satellite link
(with a .5 sec delay) at 56kb would be used instead of
a two hop T1 connection. Congestion can be viewed as a
decrease in the efficacy of a link. So, as a link gets
more congested, RIP will still know it is the best
hop-count route and congest it even more by throwing
more packets on the queue for that link.
The protocol is not well documented. A group of people
are working on producing an RFC to both define the
current RIP and to do some extensions to it to allow it
to better cope with larger networks. Currently, the
best documentation for RIP appears to be the code to
The routed program, which does RIP for 4.2BSD systems,
has many options. One of the most frequently used is:
routed -q (quiet mode) which means listen to RIP information
but never broadcast it. This would be used by a
machine on a network with multiple RIP speaking gateways.
It allows the host to determine which gateway is
best (hopwise) to use to reach a distant network. (Of
course you might want to have a default gateway to
prevent having to pass all the addresses known to the
Internet around with RIP).
There are two ways to insert static routes into routed,
the /etc/gateways file and the route add command.
Static routes are useful if you know how to reach a
distant network, but you are not receiving that route
using RIP. For the most part the route add command is
preferable to use. The reason for this is that the
command adds the route to that machine's routing table
but does not export it through RIP. The /etc/gateways
file takes precedence over any routing information
received through a RIP update. It is also broadcast as
fact in RIP updates produced by the host without question,
so if a mistake is made in the /etc/gateways
file, that mistake will soon permeate the RIP space and
may bring the network to its knees.
One of the problems with routed is that you have very
little control over what gets broadcast and what
doesn't. Many times in larger networks where various
parts of the network are under different administrative
controls, you would like to pass on through RIP only
nets which you receive from RIP and you know are reasonable.
This prevents people from adding IP addresses
to the network which may be illegal and you being
responsible for passing them on to the Internet. This
type of reasonability checks are not available with
routed and leave it usable, but inadequate for large
- Hello (RFC-891)
Hello is a routing protocol which was designed and
implemented in a experimental software router called a
"Fuzzball" which runs on a PDP-11. It does not have
wide usage, but is the routing protocol currently used
on the NSFnet backbone. The data transferred between
nodes is similar to RIP (a list of networks and their
metrics). The metric, however, is milliseconds of
delay. This allows Hello to be used over nets of various
link speeds and performs better in congestive
One of the most interesting side effects of Hello based
networks is their great timekeeping ability. If you
consider the problem of measuring delay on a link for
the metric, you find that it is not an easy thing to
do. You cannot measure round trip time since the
return link may be more congested, of a different
speed, or even not there. It is not really feasible
for each node on the network to have a builtin WWV
(nationwide radio time standard) receiver. So, you
must design an algorithm to pass around time between
nodes over the network links where the delay in
transmission can only be approximated. Hello routers
do this and in a nationwide network maintain synchronized
time within milliseconds.
- Exterior Gateway Protocol (EGP RFC-904)
EGP is not strictly a routing protocol, it is a reachability
protocol. It tells only if nets can be reached
through a particular gateway, not how good the connection is.
It is the standard by which gateways to local
nets inform the ARPAnet of the nets they can reach.
There is a metric passed around by EGP but its usage is
not standardized formally. Its typical value is value
is 1 to 8 which are arbitrary goodness of link values
understood by the internal DDN gateways. The smaller
the value the better and a value of 8 being unreachable.
A quirk of the protocol prevents distinguishing
between 1 and 2, 3 and 4..., so the usablity of this as
a metric is as three values and unreachable. Within
NSFnet the values used are 1, 3, and unreachable. Many
routers talk EGP so they can be used for ARPAnet gateways.
So we have regional and campus networks talking RIP
among themselves, the NSFnet backbone talking
Hello, and the DDN speaking EGP.
How do they interoperate? In the beginning there was
static routing, assembled into the Fuzzball software
configured for each site. The problem with doing
static routing in the middle of the network is that it
is broadcast to the Internet whether it is usable or
not. Therefore, if a net becomes unreachable and you
try to get there, dynamic routing will immediately
issue a net unreachable to you. Under static routing
the routers would think the net could be reached and
would continue trying until the application gave up (in
2 or more minutes). Mark Fedor of Cornell
(firstname.lastname@example.org) attempted to solve these
problems with a replacement for routed called gated.
Gated talks RIP to RIP speaking hosts, EGP to EGP
speakers, and Hello to Hello'ers. These speakers frequently
all live on one Ethernet, but luckily (or
unluckily) cannot understand each others ruminations.
In addition, under configuration file control it can
filter the conversion. For example, one can produce a
configuration saying announce RIP nets via Hello only
if they are specified in a list and are reachable by
way of a RIP broadcast as well. This means that if a
rogue network appears in your local site's RIP space,
it won't be passed through to the Hello side of the
world. There are also configuration options to do
static routing and name trusted gateways.
This may sound like the greatest thing since sliced
bread, but there is a catch called metric conversion.
You have RIP measuring in hops, Hello measuring in milliseconds,
and EGP using arbitrary small numbers. The
big questions is how many hops to a millisecond, how
many milliseconds in the EGP number 3.... Also,
remember that infinity (unreachability) is 16 to RIP,
30000 or so to Hello, and 8 to the DDN with EGP. Getting
all these metrics to work well together is no
small feat. If done incorrectly and you translate an
RIP of 16 into an EGP of 6, everyone in the ARPAnet
will still think your gateway can reach the unreachable
and will send every packet in the world your way. For
these reasons, Mark requests that you consult closely
with him when configuring and using gated.