Understanding Routing Protocols

An alternative to relying on ICMP redirect messages is to use a routing protocol to give machines a better idea of which routers to use for which destination networks. A routing protocol used on an ordinary host is probably not worth the effort because it will probably take more work than processing ICMP redirects unless multiple routers are available on the net-work. Relying on ICMP messages from a default router will not be effective when the default router fails (which is why Windows 95 and Windows NT have a list of routers as auxiliaries). Of course, routers need routing protocols to exchange routing information with peer routers unless you use manually configured routing tables. Routing protocols may also be vulnerable to an attack leading to corrupted routing tables on both routers and ordinary hosts.

Two categorizations of protocols used to describe routing protocols: one categorization separates protocols by intended use; the other categorization separates protocols by the kind of algorithm used to determine which router to use for a given destination network.

The first categorization separates internal routing protocols and external routing protocols. Internal routing protocols are used between routers that are within the same corporate network and eternal routing protocols are used between routers that belong to different companies.

The second categorization separates protocols that require only local information—no information except information about directly connected routers—from protocols that require global information, or information about the status of every inter-router link in the entire network.

The external protocols are much more limited in the information they share. The technical name for a set of networks of a single company is an “autonomous system.” An autonomous system consists of one or more networks that may share detailed and complete routing information with each other, but do not share complete routing information with other autonomous systems. External routing protocols are used to communicate routing information between autonomous systems. Within an autonomous system, the routers have information about how the networks are divided into subnets and about all routes to other autonomous systems.

The internal subnet structure of one company’s network almost always should be separate from another company’s network. One company may also want to keep its network(s) from carrying datagrams from another company to third parties. For these reasons, external routing protocols are designed specifically to limit the knowledge they convey and to limit the degree of trust put in the information they provide. External protocols are typically only used on “border” routers that connect autonomous systems to each other. At the very least, each site with a network connected to the Internet has a single border router that connects the site with an Internet Service Provider (ISP).

At times, companies with strategic alliances will have border routers connecting their networks to bypass the ISP for IP datagrams that have their source in one company’s network and their destination in the other company’s network. Clearly, you must limit your trust in routing information provided from other autonomous regions. Today’s strategic partner may be tomorrow’s primary competitor and you have no control over the level of security provided within another autonomous region. A security breach in another autonomous network could turn into a security breach in your own autonomous region by spoofing the internal routing protocol and then propagating that information using an external routing protocol.

Another category of routing protocols tries to find the best route through the Internet. One type of protocol uses the vector-distance approach in which each router advertises some measure of “distance” or “cost” of delivering datagrams to each destination network for which it advertises a route. Vector-distance routing protocols (also called Bellman-Ford protocols) only require that each router be aware of the routers it can deliver to directly.

Another type of routing protocol is the link-state, also called the Shortest Path First (SPF), in which each router has a complete picture of the corporate network. In link-state routing protocols, each router actively tests the status of its direct links to other routers, propagates change information about the status of such routers to all such routers, and uses an algorithm to compute the best path to all destinations from itself. Such an algorithm is Dijkstra’s shortest path algorithm from graph theory.

The most commonly used routing protocol is a vector-distance protocol called simply the Routing Information Protocol (RIP). RIP predates IP: it is part of the Xerox Networking System (XNS), which was a networking protocol in use even before IP. According to some, RIP was introduced to IP by a graduate student at Berkeley who produced the first implementation overnight when he realized the IP would need some form of routing protocol.

RIP works by combining information sent by active participants in the protocol with information on hand in passive participants. Ordinary hosts participate in the protocol passively by listening to UDP broadcasts on port 520 to get information from the routing tables for each router on their network. The hosts then merge these tables to determine which router to use for which destination networks.

Routers participate in protocol actively by broadcasting their entire routing table every 30 seconds. Instead of the destination network being associated with a router IP address as in the actual routing table, these broadcasts contain destination networks and their associated hop count. The hop count is the number of routers between the router making the broadcast and the destination network. A router that can directly deliver to a given network would advertise a hop count of zero to that network.

A router using exactly one intermediary router to reach a network would advertise a hop count of one to that network. RIP treats a hop count of 16 as an infinite distance indicating an inability to deliver to the given network. Using such a low value eliminates routing loops quickly, but limits RIP to networks with at most 16 routers between any two hosts.