Hitchhiker's Guide to the Internet - Ed Krol (read along books .txt) 📗

-9- 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…).

-10-

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 net- works 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 net- work. The diameter of a network is defined as the largest hop-count possible within a network. Unfor- tunately, 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

-11-

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 infor- mation but never broadcast it. This would be used by a machine on a network with multiple RIP speaking gate- ways. 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

-12-