As an example, let’s configure static routing on the imaginary workstation rodent. Figure 7-1 shows the subnet 172.16.12.0. There are two gateways on this subnet, crab and horseshoe. crab is the gateway to thousands of networks on the Internet; horseshoe provides access to the other subnets on books-net. We’ll use crab as our default gateway because it is used by thousands of routes. The smaller number of routes through horseshoe can easily be entered individually. The number of routes through a gateway, not the amount of traffic it handles, decides which gateway to select as the default. Even if most of rodent’s network traffic goes through horseshoe to other hosts on books-net, the default gateway should be crab.

Figure 7-1. Routing on a subnet

To install the default route on rodent, we enter:

# route add default gw 172.16.12.1

The destination is default, and the gateway address (172.16.12.1) is crab’s address. Now crab is rodent’s default gateway. Notice that the command syntax is slightly different from the Solaris route example shown earlier. rodent is a Linux system. Most values on the Linux route command line are preceded by keywords. In this case, the gateway address is preceded by the keyword gw.

After installing the default route, examine the routing table to make sure the route has been added:^[72]

# route -n
Kernel IP routing table
Destination   Gateway       Genmask         Flags Metric Ref Use Iface
172.16.12.0   0.0.0.0       255.255.255.0   U     0      0     0 eth0
127.0.0.0     0.0.0.0       255.0.0.0       U     0      0     0 lo
0.0.0.0       172.16.12.1   0.0.0.0         UG    0      0     0 eth0

Try ping again to see whether rodent can now communicate with remote hosts. If we’re lucky,^[73] the remote host responds and we see:

% ping 207.25.98.2 
PING 207.25.98.2: 56 data bytes 
64 bytes from ruby.ora.com (207.25.98.2): icmp_seq=0. time=110. ms 
64 bytes from ruby.ora.com (207.25.98.2): icmp_seq=1. time=100. ms 
^C 
----207.25.98.2 PING Statistics---- 
2 packets transmitted, 2 packets received, 0% packet loss
round-trip (ms)  min/avg/max = 100/105/110

This display indicates successful communication with the remote host, which means that we now have a good route to hosts on the Internet.

However, we still haven’t installed routes to the rest of books-net. If we ping a host on another subnet, something interesting happens:

% ping 172.16.1.2 
PING 172.16.1.2: 56 data bytes 
ICMP Host redirect from gateway crab.wrotethebook.com (172.16.12.1) 
 to horseshoe.wrotethebook.com (172.16.12.3) for ora.wrotethebook.com (172.16.1.2) 
64 bytes from ora.wrotethebook.com (172.16.1.2): icmp_seq=1. time=30. ms 
^C 
----172.16.1.2 PING Statistics---- 
1 packets transmitted, 1 packets received, 0% packet loss round-trip (ms)  min/avg/max = 30/30/30

rodent believes that all destinations are reachable through its default route. Therefore, even data destined for the other subnets is sent to crab. If rodent sends data to crab that should go through horseshoe, crab sends an ICMP Redirect to rodent telling it to use horseshoe. (See Chapter 1 for a description of the ICMP Redirect Message.) ping shows the ICMP Redirect in action. The redirect has a direct effect on the routing table:

# route -n
Kernel IP routing table
Destination   Gateway       Genmask         Flags Metric Ref Use Iface
172.16.12.0   0.0.0.0       255.255.255.0   U     0      0     0 eth0
127.0.0.0     0.0.0.0       255.0.0.0       U     0      0     0 lo
0.0.0.0       172.16.12.1   0.0.0.0         UG    0      0     0 eth0 
172.16.1.2    172.16.12.3   255.255.255.0   UGHD  0      0   514 eth0

The route with the D flag set was installed by the ICMP Redirect.

Some network managers take advantage of ICMP Redirects when designing a network. All hosts are configured with a default route, even those on networks with more than one gateway. The gateways exchange routing information through routing protocols and redirect hosts to the best gateway for a specific route. This type of routing, which is dependent on ICMP Redirects, became popular because of personal computers (PCs). Many PCs cannot run a routing protocol; some early models did not have a route command and were limited to a single default route. ICMP Redirects were one way to support these clients. Also, this type of routing is simple to configure and well suited for implementation through a configuration server, as the same default route is used on every host. For these reasons, some network managers encourage repeated ICMP Redirects.

Other network administrators prefer to avoid ICMP Redirects and to maintain direct control over the contents of the routing table. To avoid redirects, specific routes can be installed for each subnet using individual route statements:

# route add -net 172.16.1.0 netmask 255.255.255.0 gw 172.16.12.3 
# route add -net 172.16.6.0 netmask 255.255.255.0 gw 172.16.12.3
# route add -net 172.16.3.0 netmask 255.255.255.0 gw 172.16.12.3
# route add -net 172.16.9.0 netmask 255.255.255.0 gw 172.16.12.3

rodent is directly connected only to 172.16.12.0, so all gateways in its routing table have addresses that begin with 172.16.12. The finished routing table is shown below:

# route -n
Kernel IP routing table
Destination   Gateway       Genmask         Flags Metric Ref Use Iface
172.16.6.0    172.16.12.3   255.255.255.0   UG    0      0     0 eth0
172.16.3.0    172.16.12.3   255.255.255.0   UG    0      0     0 eth0
172.16.12.0   0.0.0.0       255.255.255.0   U     0      0     0 eth0
172.16.1.0    172.16.12.3   255.255.255.0   UG    0      0     0 eth0
172.16.9.0    172.16.12.3   255.255.255.0   UG    0      0     0 eth0
127.0.0.0     0.0.0.0       255.0.0.0       U     0      0     0 lo
0.0.0.0       172.16.12.1   0.0.0.0         UG    0      0     0 eth0 
172.16.1.2    172.16.12.3   255.255.255.0   UGHD  0      0   514 eth0

The routing table we have constructed uses the default route (through crab) to reach external networks, and specific routes (through horseshoe) to reach other subnets within books-net. Rerunning the ping tests produces consistently successful results. However, if any subnets are added to the network, the routes to these new subnets must be manually added to the routing table. Additionally, if the system is rebooted, all static routing table entries are lost. Therefore, to use static routing, you must ensure that the routes are re-installed each time your system boots.

route -n add default 172.16.12.1 > /dev/console 
route -n add 172.16.1.0 172.16.12.3 > /dev/console 
route -n add 172.16.6.0 172.16.12.3 > /dev/console 
route -n add 172.16.3.0 172.16.12.3 > /dev/console
route -n add 172.16.9.0 172.16.12.3 > /dev/console

As delivered with many Unix systems, Routing Information Protocol (RIP) is run by the routing daemon routed (pronounced “route” “d”). When routed starts, it issues a request for routing updates and then listens for responses to its request. When a system configured to supply RIP information hears the request, it responds with an update packet based on the information in its routing table. The update packet contains the destination addresses from the routing table and the routing metric associated with each destination. Update packets are issued in response to requests as well as periodically to keep routing information accurate.

To build the routing table, routed uses the information in the update packets. If the routing update contains a route to a destination that does not exist in the local routing table, the new route is added. If the update describes a route whose destination is already in the local table, the new route is used only if it is a better route. As noted previously, RIP considers a route with a lower " hop count” to be a better route. In RIP terminology, the hop count is called the cost of the route or the routing metric. We saw earlier that the routing metric in the local routing table can be manually controlled using the metric argument of the route command. To select the best route, RIP must first determine the cost of the route. The cost of a route is determined by adding the cost of reaching the gateway that sent the update to the metric contained in the RIP update packet. If the total cost is less than the cost of the current route, the new route is used.

RIP also deletes routes from the routing table. It accomplishes this in two ways. First, if the gateway to a destination says the cost of the route is greater than 15, the route is deleted. Second, RIP assumes that a gateway that doesn’t send updates is dead. All routes through a gateway are deleted if no updates are received from that gateway for a specified time period. In general, RIP issues routing updates every 30 seconds. In many implementations, if a gateway does not issue routing updates for 180 seconds, all routes through that gateway are deleted from the routing table.

Running RIP with routed

To run RIP using the routing daemon (routed),^[75] enter the following command:

# routed

The routed statement is often used without any command-line arguments, but you may want to use the -q option. The -q option prevents routed from advertising routes. It just listens to the routes advertised by other systems. If your computer is not a gateway, you should probably use the -q option.

In the section on static routing, we did not need to comment out the routed statement found in the inetinit startup file because Solaris runs routed only if the system has two network interfaces or if the /etc/gateways file is found. If your Unix system starts routed unconditionally, no action is required to run RIP; just boot your system and RIP will run. Otherwise, you need to make sure the routed command is in your startup and the conditions required by your system are met. The easiest way to get Solaris to run routed is to create a gateways file—even an empty one will do.

routed reads /etc/gateways at startup and adds its information to the routing table. routed can build a functioning routing table simply by using the RIP updates received from the RIP suppliers. However, it is sometimes useful to supplement this information with, for example, an initial default route or information about a gateway that does not announce its routes. The /etc/gateways file stores this additional routing information.

The most common use of the /etc/gateways file is to define an active default route, so we’ll use that as an example. This one example is sufficient because all entries in the /etc/gateways file have the same basic format. The following entry specifies crab as the default gateway:

net 0.0.0.0 gateway 172.16.12.1 metric 1 active

The entry starts with the keyword net. All entries start with either the keyword net or the keyword host to indicate whether the address that follows is a network address or a host address. The destination address 0.0.0.0 is the address used for the default route. In the route command we used the keyword default to indicate this route, but in /etc/gateways the default route is indicated by network address 0.0.0.0.

Next is the keyword gateway followed by the gateway’s IP address. In this case it is the address of crab (172.16.12.1).

Then comes the keyword metric followed by a numeric metric value. The metric is the cost of the route. The metric was almost meaningless when used with static routing, but now that we are running RIP, the metric is used to make routing decisions. The RIP metric represents the number of gateways through which data must pass to reach its final destination. But as we saw with ifconfig, the metric is really an arbitrary value used by the administrator to prefer one route over another. (The system administrator is free to assign any metric value.) However, it is useful to vary the metric only if you have more than one route to the same destination. With only one gateway to the Internet, the correct metric to use for crab is 1.

All /etc/gateways entries end with either the keyword passive or the keyword active . “Passive” means the gateway listed in the entry is not required to provide RIP updates. Use passive to prevent RIP from deleting the route if no updates are expected from the gateway. A passive route is placed in the routing table and kept there as long as the system is up. In effect, it becomes a permanent static route.

The keyword active, on the other hand, creates a route that can be updated by RIP. An active gateway is expected to supply routing information and will be removed from the routing table if, over a period of time, it does not provide routing updates. Active routes are used to “prime the pump” during the RIP startup phase, with the expectation that the routes will be updated by RIP when the protocol is up and running.

Our sample entry ends with the keyword active, which means that this default route will be deleted if no routing updates are received from crab. Default routes are convenient; this is especially true when you use static routing. But when you use dynamic routing, default routes should be used with caution, especially if you have multiple gateways that can reach the same destination. A passive default route prevents the routing protocol from dynamically updating the route to reflect changing network conditions. Use an active default route that can be updated by the routing protocol.

RIP is easy to implement and simple to configure. Perfect! Well, not quite. RIP has three serious shortcomings:

Limited network diameter

The longest RIP route is 15 hops. A RIP router cannot maintain a complete routing table for a network that has destinations more than 15 hops away. The hop count cannot be increased because of the second shortcoming.

Slow convergence

Deleting a bad route sometimes requires the exchange of multiple routing update packets until the route’s cost reaches 16. This is called “counting to infinity” because RIP keeps incrementing the route’s cost until it becomes greater than the largest valid RIP metric. (In this case, 16 is infinity.) Additionally, RIP may wait 180 seconds before deleting the invalid routes. In network-speak, we say that these conditions delay the “convergence of routing,” i.e., it takes a long time for the routing table to reflect the current state of the network.

Classful routing

RIP interprets all addresses using the class rules described in Chapter 2. For RIP, all addresses are class A, B, or C, which makes RIP incompatible with the current practice of interpreting an address based on the address bit mask.

Nothing can be done to change the limited network diameter. A small metric is essential to reduce the impact of counting to infinity. However, limited network size is the least important of RIP’s shortcomings. The real work of improving RIP concentrates on the other two problems, slow convergence and classful routing.

Features have been added to RIP to address slow convergence. Before discussing them we must understand how the “counting-to-infinity” problem occurs. Figure 7-2 illustrates a network where a counting-to-infinity problem might happen.

Figure 7-2. Sample network

Figure 7-2 shows that crab reaches subnet 3 through horseshoe and then through ora. Subnet 3 is two hops away from crab and one hop away from horseshoe. Therefore horseshoe advertises a cost of 1 for subnet 3 and crab advertises a cost of 2, and traffic continues to be routed through horseshoe. That is, until something goes wrong. If ora crashes, horseshoe waits for an update from ora for 180 seconds. While waiting, horseshoe continues to send updates to crab that keep the route to subnet 3 in crab’s routing table. When horseshoe’s timer finally expires, it removes all routes through ora from its routing table, including the route to subnet 3. It then receives an update from crab advertising that crab is two hops away from subnet 3. horseshoe installs this route and announces that it is three hops away from subnet 3. crab receives this update, installs the route, and announces that it is four hops away from subnet 3. Things continue on in this manner until the cost of the route to subnet 3 reaches 16 in both routing tables. If the update interval is 30 seconds, this could take a long time!

Split horizon and poison reverse are two features that attempt to avoid counting to infinity. Here’s how:

Split horizon

With this feature, a router does not advertise routes on the link from which those routes were obtained. This would solve the count-to-infinity problem described above. Using the split horizon rule, crab would not announce the route to subnet 3 on subnet 12 because it learned that route from the updates it received from horseshoe on subnet 12. While this feature works for the previous example described, it does not work for all count-to-infinity configurations. (More on this later.)

Poison reverse

This feature is an enhancement of split horizon. It uses the same idea: “Don’t advertise routes on the link from which those routes were obtained.” But it adds a positive action to that essentially negative rule. Poison reverse says that a router should advertise an infinite distance for routes on this link. With poison reverse, crab would advertise subnet 3 with a cost of 16 to all systems on subnet 12. The cost of 16 means that subnet 3 cannot be reached through crab.

Split horizon and poison reverse solve the problem described above. But what happens if crab crashes? Refer to Figure 7-2. With split horizon, aulds and smith do not advertise to crab the route to subnet 12 because they learned the route from crab. They do, however, advertise the route to subnet 12 to each other. When crab goes down, aulds and smith perform their own count to infinity before they remove the route to subnet 12. Triggered updates address this problem.

Triggered updates are a big improvement. Instead of waiting the normal 30-second update interval, a triggered update is sent immediately. Therefore, when an upstream router crashes or a local link goes down, the router sends the changes to its neighbors immediately after it updates its local routing table. Without triggered updates, counting to infinity can take almost eight minutes! With triggered updates, neighbors are informed in a few seconds. Triggered updates also use network bandwidth efficiently. They don’t include the full routing table; they include only the routes that have changed.

Triggered updates take positive action to eliminate bad routes. Using triggered updates, a router advertises the routes deleted from its routing table with an infinite cost to force downstream routers to also remove them. Again, look at Figure 7-2. If crab crashes, smith and aulds wait 180 seconds and remove the routes to subnets 1, 3, and 12 from their routing tables. They then send each other triggered updates with a metric of 16 for subnets 1, 3, and 12. Thus they tell each other that they cannot reach these networks and no count to infinity occurs. Split horizon, poison reverse, and triggered updates go a long way toward eliminating counting to infinity.

It is the final shortcoming—the fact that RIP is incompatible with CIDR supernets and variable-length subnets—that caused the RIP protocol to be moved to “historical” status in 1996. RIP is not compatible with current and future plans for the TCP/IP protocol stack. A new version of RIP had to be created to address this final problem.

RIP version 2 (RIP-2), defined in RFC 2453, is a new version of RIP. It is not a completely new protocol; it simply defines extensions to the RIP packet format. RIP-2 adds a network mask and a next-hop address to the destination address and metric found in the original RIP packet.

The network mask frees the RIP-2 router from the limitation of interpreting addresses based on outdated address class rules. The mask is applied to the destination address to determine how the address should be interpreted. Using the mask, RIP-2 routers support variable-length subnets and CIDR supernets.

The next-hop address is the IP address of the gateway that handles the route. If the address is 0.0.0.0, the source of the update packet is the gateway for the route. The next-hop route permits a RIP-2 supplier to provide routing information about gateways that do not speak RIP-2. Its function is similar to an ICMP Redirect, pointing to the best gateway for a route and eliminating extra routing hops.

RIP-2 adds other new features to RIP. It transmits updates via the multicast address 224.0.0.9 to reduce the load on systems that are not capable of processing a RIP-2 packet. RIP-2 also introduces a packet authentication scheme to reduce the possibility of accepting erroneous updates from misconfigured systems.

Despite these changes, RIP-2 is compatible with RIP. The original RIP specification allowed for future versions of RIP. RIP has a version number in the packet header, and several empty fields for extending the packet. The new values used by RIP-2 did not require any changes to the structure of the packet. The new values are simply placed in the empty fields that the original protocol reserved for future use. Properly implemented RIP routers can receive RIP-2 packets and extract the data that they need from the packet without becoming confused by the new data.

Split horizon, poison reverse, triggered updates, and RIP-2 eliminate most of the problems with the original RIP protocol. But RIP-2 is still a distance-vector protocol. There are other, newer routing technologies that are considered superior for large networks. In particular, link-state routing protocols are favored because they provide rapid routing convergence and reduce the possibility of routing loops.

Open Shortest Path First (OSPF), defined by RFC 2328, is a link-state protocol. As such, it is very different from RIP. A router running RIP shares information about the entire network with its neighbors. Conversely, a router running OSPF shares information about its neighbors with the entire network. The “entire network” means, at most, a single autonomous system. RIP doesn’t try to learn about the entire Internet, and OSPF doesn’t try to advertise to the entire Internet. That’s not their job. These are interior routing protocols, so their job is to construct the routing inside an autonomous system. OSPF further refines this task by defining a hierarchy of routing areas within an autonomous system:

Only a large autonomous system needs to be subdivided into areas. The sample network shown in Figure 7-2 is small and would not need to be divided. We can, however, use it to illustrate the different areas. We could divide this autonomous system into any areas we wish. Assume we divide it into three areas: area 1 contains subnet 3; area 2 contains subnet 1 and subnet 12; and area 3 contains subnet 25, subnet 36, and the PPP links. Furthermore, we could define area 1 as a stub area because ora is that area’s only area border router. We also could define area 2 as the backbone area because it interconnects the other two areas and all routing information between areas 1 and 3 must be distributed by area 2. Area 2 contains two area border routers, crab and ora, and one interior router, horseshoe. Area 3 contains three routers: crab, smith, and aulds.

Clearly OSPF provides lots of flexibility for subdividing an autonomous system. But why is it necessary? One problem for a link-state protocol is the large quantity of data that can be collected in the link-state database and the amount of time it can take to calculate the routes from that data. A look at the protocol shows why this is true.

Every OSPF router builds a directed graph of the entire network using the Dijkstra Shortest Path First (SPF) algorithm. A directed graph is a map of the network from the perspective of the router; that is, the root of the graph is the router. The graph is built from the link-state database, which includes information about every router on the network and all the neighbors of every router. The link-state database for the autonomous system in Figure 7-2 contains 5 routers and 10 neighbors: ora has 1 neighbor, horseshoe; horseshoe has 2 neighbors, ora and crab; crab has 3 neighbors, horseshoe, aulds, and smith; aulds has 2 neighbors, crab and smith; and smith has 2 neighbors, aulds and crab. Figure 7-3 shows the graph of this autonomous system from the perspective of ora.

Figure 7-3. A network graph

The Dijkstra algorithm builds the map in this manner:

The information in the link-state database is gathered and distributed in a simple and efficient manner. An OSPF router discovers its neighbors through the use of Hello packets.^[76] It sends Hello packets and listens for Hello packets from adjacent routers. The Hello packet identifies the local router and lists the adjacent routers from which it has received packets. When a router receives a Hello packet that lists it as an adjacent router, it knows it has found a neighbor. It knows this because it can hear packets from that neighbor and, because the neighbor lists it as an adjacent router, the neighbor must be able to hear packets from it. The newly discovered neighbor is added to the local system’s neighbor list.

The OSPF router then advertises all of its neighbors. It does this by flooding a Link-State Advertisement (LSA) to the entire network. The LSA contains the address of every neighbor and the cost of reaching that neighbor from the local system. Flooding means that the router sends the LSA out of every interface and that every router that receives the LSA sends it out of every interface except the one from which it was received. To avoid flooding duplicate LSAs, the routers store a copy of the LSAs they receive and discard duplicates.

Figure 7-2 provides an example. When OSPF starts on horseshoe it sends a Hello packet on subnet 1 and one on subnet 12. ora and crab hear the Hello and respond with Hello packets that list horseshoe as an adjacent router. horseshoe hears their Hello packets and adds them to its neighbor list. horseshoe then creates an LSA that lists ora and crab as neighbors with appropriate costs assigned to each. For instance, horseshoe might assign a cost of 5 to ora and a cost of 10 to crab. horseshoe then floods the LSA on subnet 1 and subnet 12. ora hears the LSA and floods it on subnet 3. crab receives the LSA and floods it on both of its PPP links. aulds floods the LSA on the link toward smith, and smith floods it on the same link to aulds. When aulds and smith received the second copy of the LSA, they discarded it because it duplicated one that they had already received from crab. In this manner, every router in the entire network receives every other router’s link-state advertisement.

OSPF routers track the state of their neighbors by listening for Hello packets. Hello packets are issued by all routers on a periodic basis. When a router stops issuing packets, it or the link it is attached to is assumed to be down. Its neighbors update their LSA and flood them through the network. The new LSAs are included into the link-state database on every router on the network, and every router recalculates its network map based on this new information. Clearly, limiting the number of routers by limiting the size of the network reduces the burden of recalculating the map. For many networks, the entire autonomous system is small enough. For others, dividing the autonomous system into areas improves efficiency.

Another feature of OSPF that improves efficiency is the designated router . The designated router is one router on the network that treats all other routers on the network as its neighbors, while all other routers treat only the designated router as their neighbor. This helps reduce the size of the link-state database and thus improves the speed of the Shortest-Path-First calculation. Imagine a broadcast network with 5 routers. Five routers each with 4 neighbors produce a link-state database with 20 entries. But if one of those routers is the designated router, then that router has 4 neighbors and all other routers have only 1 neighbor, for a total of 10 link-state database entries. While there is no need for a designated router on such a small network, the larger the network, the more dramatic the gains. For example, a broadcast network with 25 routers has a link-state database of 50 entries when a designated router is used, versus a database of 600 entries without one.

OSPF provides the router with an end-to-end view of the route between two systems instead of the limited next-hop view provided by RIP. Flooding quickly disseminates routing information throughout the network. Limiting the size of the link-state database through areas and designated routers speeds the SPF calculation. Taken altogether, OSPF is an efficient link-state routing protocol.

OSPF also offers additional features that RIP doesn’t. It provides simple password authentication to ensure that the update comes from a valid router using an eight-character, clear-text password. It provides Message Digest 5 (MD5) crypto-checksum for stronger authentication.

OSPF also supports equal-cost multi-path routing . This mouthful means that OSPF routers can maintain more than one path to a single destination. Given the proper conditions, this feature can be used for load balancing across multiple network links. However, many systems are not designed to take advantage of this feature. Refer to your router’s documentation to see if it supports load balancing across equal-cost OSPF routes.

With all of these features, OSPF is the preferred TCP/IP interior routing protocol for dedicated routers.

A gateway running EGP announces that it can reach networks that are part of its autonomous system. It does not announce that it can reach networks outside its autonomous system. For example, the exterior gateway for our imaginary autonomous system book-as can reach the entire Internet through its external connection, but only one network is contained in its autonomous system. Therefore, it would announce only one network (172.16.0.0) if it ran EGP.

Before sending routing information, the systems exchange EGP Hello and I-Heard-You (I-H-U) messages. These messages establish a dialogue between two EGP gateways. Computers communicating via EGP are called EGP neighbors, and the exchange of Hello and I-H-U messages is called acquiring a neighbor .

Once a neighbor is acquired, routing information is requested via a poll . The neighbor responds by sending a packet of reachability information called an update. The local system includes the routes from the update into its local routing table. If the neighbor fails to respond to three consecutive polls, the system assumes that the neighbor is down and removes the neighbor’s routes from its table. If the system receives a poll from its EGP neighbor, it responds with its own update packet.

Unlike the interior protocols discussed above, EGP does not attempt to choose the “best” route. EGP updates contain distance-vector information, but EGP does not evaluate this information. The routing metrics from different autonomous systems are not directly comparable. Each AS may use different criteria for developing these values. Therefore, EGP leaves the choice of a “best” route to someone else.

When EGP was designed, the network relied upon a group of trusted core gateways to process and distribute the routes received from all of the autonomous systems. These core gateways were expected to have the information necessary to choose the best external routes. EGP reachability information was passed into the core gateways, where the information was combined and passed back out to the autonomous systems.

A routing structure that depends on a centrally controlled group of gateways does not scale well and is therefore inadequate for the rapidly growing Internet. As the number of autonomous systems and networks connected to the Internet grew, it became difficult for the core gateways to keep up with the expanding workload. This is one reason why the Internet moved to a more distributed architecture that places a share of the burden of processing routes on each autonomous system. Another reason is that no central authority controls the commercialized Internet. The Internet is composed of many equal networks. In a distributed architecture, the autonomous systems require routing protocols, both interior and exterior, that can make intelligent routing choices. Because of this, EGP is no longer popular.

Border Gateway Protocol (BGP) is the leading exterior routing protocol of the Internet. It is based on the OSI InterDomain Routing Protocol (IDRP). BGP supports policy-based routing, which uses non-technical reasons (for example, political, organizational, or security considerations) to make routing decisions. Thus BGP enhances an autonomous system’s ability to choose between routes and to implement routing policies without relying on a central routing authority. This feature is important in the absence of core gateways to perform these tasks.

Routing policies are not part of the BGP protocol. Policies are provided externally as configuration information. As described in Chapter 2, the National Science Foundation provides Routing Arbiters (RAs) at the Network Access Points (NAPs) where large Internet Service Providers (ISPs) interconnect. The RAs can be queried for routing policy information. Most ISPs also develop private policies based on the bilateral agreements they have with other ISPs. BGP can be used to implement these policies by controlling the routes it announces to others and the routes it accepts from others. In the gated section later in this chapter, we discuss the import command and the export command, which control what routes are accepted (import) and what routes are announced (export). The network administrator enforces the routing policy through configuring the router.

BGP is implemented on top of TCP, which provides BGP with a reliable delivery service. BGP uses well-known TCP port 179. It acquires its neighbors through the standard TCP three-way handshake. BGP neighbors are called peers. Once connected, BGP peers exchange OPEN messages to negotiate session parameters, such as the version of BGP that is to be used.

The UPDATE message lists the destinations that can be reached through a specific path and the attributes of the path. BGP is a path-vector protocol. It is called a path-vector protocol because it provides the entire end-to-end path of a route in the form of a sequence of autonomous system numbers. Having the complete AS path eliminates the possibility of routing loops and count-to-infinity problems. A BGP UPDATE contains a single path vector and all of the destinations reachable through that path. Multiple UPDATE packets may be sent to build a routing table.

BGP peers send each other complete routing table updates when the connection is first established. After that, only changes are sent. If there are no changes, just a small (19-byte) KEEPALIVE message is sent to indicate that the peer and the link are still operational. BGP is very efficient in its use of network bandwidth and system resources.

By far the most important thing to remember about exterior protocols is that most systems never run them. Exterior protocols are required only when an AS must exchange routing information with another AS. Most routers within an AS run an interior protocol such as OSPF. Only those gateways that connect the AS to another AS need to run an exterior routing protocol. Your network is probably an independent part of an AS run by someone else. ISPs are good examples of autonomous systems made up of many independent networks. Unless you provide a similar level of service, you probably don’t need to run an exterior routing protocol.

Although there are many routing protocols, choosing one is usually easy. Most of the interior routing protocols mentioned above were developed to handle the special routing problems of very large networks. Some of the protocols have been used only by large national and regional networks. For local area networks, RIP is still a common choice. For larger networks, OSPF is the choice.

If you must run an exterior routing protocol, the protocol that you use is often not a matter of choice. For two autonomous systems to exchange routing information, they must use the same exterior protocol. If the other AS is already in operation, its administrators have probably decided which protocol to use, and you will be expected to conform to their choice. Most often this choice is BGP.

The type of equipment affects the choice of protocols. Routers support a wide range of protocols, though individual vendors may have a preferred protocol. Hosts don’t usually run routing protocols at all, and most Unix systems are delivered with only RIP. Allowing host systems to participate in dynamic routing could limit your choices. gated, however, gives you the option to run many different routing protocols on a Unix system. While the performance of hardware designed specifically to be a router is generally better, gated gives you the option of using a Unix system as a router.

In the following sections we discuss the Gateway Routing Daemon (gated) software that combines interior and exterior routing protocols into one software package. We look at examples of running RIP, RIPv2, OSPF, and BGP with gated.

There are two sides to every routing protocol implementation. One side, the external side, exchanges routing information with remote systems. The other side, the internal side, uses the information received from the remote systems to update the routing table. For example, when OSPF exchanges Hello packets to discover a neighbor, it is an external protocol function. When OSPF adds a route to the routing table, it is an internal function.

The external protocol functions implemented in gated are the same as those in other implementations of the protocols. However, the internal side of gated is unique for Unix systems. Internally, gated processes routing information from different routing protocols, each of which has its own metric for determining the best route, and combines that information to update the routing table. Before gated was written, if a Unix system ran multiple routing protocols, each would write routes into the routing table without knowledge of the others’ actions. The route found in the table was the last one written—not necessarily the best route.

With multiple routing protocols and multiple network interfaces, it is possible for a system to receive routes to the same destination from different protocols. gated compares these routes and attempts to select the best one. However, the metrics used by different protocols are not directly comparable. Each routing protocol has its own metric. It might be a hop count, the delay on the route, or an arbitrary value set by the administrator. gated needs more than that protocol’s metric to select the best route. It uses its own value to prefer routes from one protocol or interface over another. This value is called preference.

Preference values help gated combine routing information from several different sources into a single routing table. Table 7-1 lists the sources from which gated receives routes and the default preference given to each source. Preference values range from 0 to 255, with the lowest number indicating the most preferred route. From this table you can see that gated prefers a route learned from OSPF over the same route learned from BGP.

Preference can be set in several different configuration statements. It can be used to prefer routes from one network interface over another, from one protocol over another, or from one remote gateway over another. Preference values are not transmitted or modified by the protocols. Preference is used only in the configuration file. In the next section we’ll look at the gated configuration file (/etc/gated.conf) and the configuration commands it contains.

The details in Appendix B may make gated configuration appear more complex than it is. gated’s rich command language can be confusing, as can its support for multiple protocols and the fact that it often provides a few ways to do the same thing. But some realistic examples will show that individual configurations do not need to be complex.

The basis for the sample configurations is the network in Figure 7-4. We have installed a new router that provides our backbone with direct access to the Internet, and we have decided to install new routing protocols. We’ll configure a host to listen to RIP-2 updates, an interior gateway to run RIP-2 and OSPF, and an exterior gateway to run OSPF and BGP.

Figure 7-4. Sample routing topology

Gateway limulus interconnects subnet 172.16.9.0 and subnet 172.16.1.0. To hosts on subnet 9, it advertises itself as the default gateway because it is the gateway to the outside world. It uses RIP-2 to advertise routes on subnet 9. On subnet 1, gateway limulus advertises itself as the gateway to subnet 9 using OSPF.

Gateway chill provides subnet 1 with access to the Internet through autonomous system 164. Because gateway chill provides access to the Internet, it announces itself as the default gateway to the other systems on subnet 1 using OSPF. To the external autonomous system, it uses BGP to announce itself as the path to the internal networks it learns about through OSPF.

Let’s look at the routing configuration of host minasi, gateway limulus, and gateway chill.

# 
#  enable rip, don't broadcast updates, 
#  listen for RIP-2 updates on the multicast address, 
#  check that the updates are authentic. 
# 
rip yes { 
        nobroadcast ; 
        interface 172.16.9.23 
             version 2  
             multicast  
             authentication simple "REAL stuff" ; 
 } ;

#  Don't time-out subnet 9 
interfaces { 
    interface 172.16.9.1 passive ; 
} ; 
# Define the OSPF router id 
routerid 172.16.1.9 ; 
# Enable RIP-2; announce OSPF routes to 
# subnet 9 with a cost of 5. 
rip yes { 
    broadcast ; 
    defaultmetric 5 ; 
    interface 172.16.9.1 
         version 2 
         multicast 
         authentication simple "REAL stuff" ; 
} ; 
# Enable OSPF; subnet 1 is the backbone area; 
# use password authentication. 
ospf yes { 
     backbone { 
          interface 172.16.1.9 { 
              priority 5 ; 
              auth simple "It'sREAL" ; 
              } ; 
          } ;
} ;

# Defines our AS number for BGP 
autonomoussystem 249; 
 
# Defines the OSPF router id 
routerid 172.16.1.1; 
 
# Disable RIP 
rip no; 
 
# Enable BGP 
bgp yes { 
   group type external peeras 164 { 
        peer 10.6.0.103 ; 
        peer 10.20.0.72 ; 
        }; 
}; 
 
# Enable OSPF; subnet 1 is the backbone area; 
# use password authentication. 
ospf yes { 
     backbone { 
         interface 172.16.1.1 { 
              priority 10 ; 
              auth simple "It'sREAL" ; 
              } ; 
          } ; 
}; 
 
# Announce routes learned from OSPF and route 
# to directly connected network via BGP to AS 164 
export proto bgp as 164 { 
     proto direct ; 
     proto ospf ; 
}; 
 
# Announce routes learned via BGP from  
# AS number 164 to our OSPF area. 
export proto ospfase type 2  { 
     proto bgp autonomoussystem 164  { 
          all ;    
          };
};

# Announce a default route when peering  
# with a BGP neighbor.  
export proto ospfase type 2  { 
     proto default ;
};

Test the configuration file before you try to use it; the gated configuration syntax is complex and it is easy to make a mistake. Create your new configuration in a test file, test the new configuration, and then move the test configuration to /etc/gated.conf. Here’s how.

Assume that a configuration file called test.conf has already been created. It is tested using -f and -c on the command line:

% gated -c -f test.conf trace.test

The -f option tells gated to read the configuration from the named file instead of from /etc/gated.conf. In the sample it reads the configuration from test.conf. The -c option tells gated to read the configuration file and check for syntax errors. When gated finishes reading the file, it terminates; it does not modify the routing table. The -c option turns on tracing, so specify a trace file or the trace data will be displayed on your terminal. In the sample we specified trace.test as the trace file. The -c option also produces a snapshot of the state of gated after reading the configuration file, and writes the snapshot to /usr/tmp/gated_dump.^[81] You don’t need to be superuser or to terminate the active gated process to run gated when the -c option is used.

The dump and the trace file (trace.test) can then be examined for errors and other information. When you’re confident that the configuration is correct, become superuser and move your new configuration (test.conf) to /etc/gated.conf.

An alternative command for testing the configuration file is gdc , though it must be run by the root user or as a setuid root program. It includes features for checking and installing a new configuration. gdc uses three different configuration files. The current configuration is /etc/gated.conf. The previous configuration is stored in /etc/gated.conf-. The “next” configuration is stored in /etc/gated.conf+, which is normally the configuration that needs to be tested. Here’s how gdc tests a configuration:

# cp test.conf /etc/gated.conf+ 
# gdc checknew 
configuration file /etc/gated.conf+ checks out okay 
# gdc newconf 
# gdc restart 
gated not currently running
gdc: /etc/gated was started

In this sample, the test configuration is copied to /etc/gated.conf+ and tested with the gdc checknew command. If syntax problems are found in the file, a warning message is displayed and detailed error messages are written to /usr/tmp/gated_parse. There are no syntax errors in the example, so we make the test file the current configuration with the gdc newconf command. This command moves the current configuration to gated.conf- and moves the new configuration (gated.conf+) to the current configuration. The gdc restart command terminates gated if it is currently running—it was not in the example—and starts a new copy of gated using the new configuration.

if [ -f /usr/sbin/gated -a -f /etc/gated.conf ]; then 
     /usr/sbin/gated;      echo -n 'gated' > /dev/console
fi