Routing
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 (campus, regional...).
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
-
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 BSD routed.
- Routed
-
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 networks.
- 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
situations.
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.
- Gated
-
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 (fedor@devvax.tn.cornell.edu) 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.
