Routing Protocols

Large internetworks spanning multiple workgroups, subnetworks, and host computers create special problems for system administrators. Like managers of local networks, they must deal with products from multiple vendors , get different network operating systems to communicate, and justify the costs of new services and applications.

But they also face the task of selecting, managing, and maintaining bridges, routers, and gatewaysthe internetworking devices that permit widely separated clusters of networks to communicate. These products offer important capabilities to help network managers solve particular problems, but each poses special implementation challenges, too.

This is especially true of routers and their associated routing protocols. Routers connect logically separate networks operating under the same transport protocol, such as the Transmission Control Protocol/Internet Protocol (TCP/IP).

Routers, which operate at the network (or third) layer of the Open Systems Interconnection (OSI) reference model, are protocol-dependent devices. That is, they must support each routing protocol on that LAN.

A Wealth Of Protocols

A wide variety of routing protocols can be found on enterprise-wide networks today. Some are proprietary, or single-vendor, solutions developed specifically for use with a vendor's own products. Others are "open" in that they have been standardized by official sanctioning agencies.

Among the proprietary ones are the Internetwork Packet eXchange (IPX) protocol used by Novell's NetWare and the Interior Gateway Routing Protocol (IGRP) used by Cisco Systems. Open protocols include the Routing Information Protocol (RIP) for use with the TCP/IP suite and the OSI Intermediate System-to-Intermediate System (IS-IS) protocol. These were formulated or standardized by the Internet Activities Board (IAB) and the International Organization for Standardization (ISO), respectively. Since they are open, they can be used with multiple vendors' products in heterogeneous networks.

Other widely used routing protocols include the IETF's Open Shortest Path First (OSPF), DECnet Phase IV, the OSI's Connectionless Network Services (CLNS) protocol, and Apple Computer's Datagram Delivery Protocol (DDP).

Routing Algorithms

The primary role of a router is to transmit similar types of data packets from one machine to another across wide area communications links such as T1 lines or Fiber Distributed Data Interface (FDDI) rings. Ideally, the router exchanges data by selecting the best path between the source and destination machines. It determines what is best via routing algorithms, which are complex sets of rules that take into account a variety of factors.

In operation, these algorithms' first task is to determine which of the paths on the internetwork will take a data packet to its destination. Because multiple paths often exist between any two routers, the algorithms are used to select the best paths. These decisions are based on a prescribed set of conditions, which might include the fastest set of transmission media or which network segment carries the least amount of traffic.

Flooding The Network

Without microprocessors to perform the complex mathematical calculations required by routing algorithms, early routers were slow. The networks they ran on were equally low- powered , with little bandwidth and not complex. This meant that routers could be simple and operate without knowing much about where the other routers on the network were located.

These types of routers were isolated in that they did not exchange network routing information with other routers on the network. As a result, they forwarded data merely by flooding every path with packets. Data packets eventually reach their destination in this scheme, but flooding also risks creating routing loops , in which certain packets can travel around the network indefinitely.

Several measures can be taken to help flooding-type routers choose reasonable paths. One is called backward-learning. In this scheme, a router remembers the source addresses of all incoming packets and notes the physical interface it came in on. When it's time to forward a packet to that address, the router bases its decisions on this stored information.

Some routers avoid the entire issue of path-finding by relying either on a human or host computer to make these decisions. In the former case, the network manager provides each router with a block of static routing configuration information at start-up, including the information needed to make routing decisions.

In the host-router implementation, end hosts place information in every packet they place on the network. This information indicates every path and the immediate router the data must pass through to get to its destination. This is source-routing.

Adding Complexity

More complex networks require dynamic routing solutions. In large wide area networks with multiple links between networks, routers perform more efficiently when they understand how the network is linked together. An integrated router does this by exchanging information about the network's topology with other integrated routers. As a result of this exchange, integrated routers create routing tables that show the best paths between the various links on the internet.

Algorithms for integrated routers must be able to quickly determine the network topology. This process, called convergence, must take place rapidly , otherwise routers with obsolete or incorrect data about the network can send data into dead-end networks or across unnecessary links.

Distributed Routing

Routers can be arrayed in centralized or distributed configurations. Central routers with intensive CPU resources and lots of memory control how data packets are moved around. These relatively expensive central routers receive topology information from remote, less-powerful "slaves," then build routing tables and pass them along to the remote routers as needed.

The newer , increasingly sophisticated routers with their own CPU and memory resources available make centralized routing obsolete. In the distributed routing environments now prevalent , all routers on the internetwork can calculate routing algorithms quickly and efficiently.

The two main distributed-routing algorithms are a distance-vector algorithm, or the Bellman-Ford algorithm, and a shortest path first, or Dijkstra algorithm. Both are in wide use, in proprietary and standard protocols. For instance, RIP (used with TCP/IP, Xerox Network Systems [XNS], and IPX), DECnet Phase IV, and Cisco's IGRP implement distance-vector algorithms. OSPF, used in TCP/IP, is a shortest path routing algorithm.

Distance-vector routers create a network map by communicating in a periodic and progressive sequence with each other. This information exchange helps them determine the scope of their network in a series of router hops that reveals more information about the network.

Here's how the algorithm works: When the network is started, each router knows about only the networks it is connected to directly. Each router then advertises information about its immediate connections to the routers it is directly connected to. By incorporating the updates it receives from routers nearest to it, each router learns about networks connected to its neighbors, two router hops away. Additional updates expand each router's knowledge hop-by-hop .

Shortest Path First (SPF) routers update each other and learn the topology of an internetwork by periodically flooding the network with link-state information. Link-state data includes the cost and identification of only those networks directly connected to each router.

SPF routers send link-state data to all routers on a LAN. This allows OSPF routers to perform two important subsequent steps. First, they use the link-state data to build a complete table of router and network connections. Then each router calculates the optimal path from itself to each link. In this repetitive process, each router checks the potential pathways between the links on the network, eliminating the most indirect path in favor of the shortest. That path, with any routers connected to it, is put on an active list. This process goes on until all possible shortest links are active.

TCP/IP Routing

The TCP/IP protocol suite offers a slightly confusing routing picture, partly due to its nomenclature , and partly due to the structure of the internetwork that spawned TCP/IP.

The Internet community uses the word "gateway" to describe a device that the rest of the internetwork marketplace calls a router. In the Internet, the devices serving as gateways do so within two interconnected environments: One, they link the subnetworks within individual universities and research institutions into a large network, and, two, they act as the physical links between individual universities and research institutions.

Also confusing is the Internet's use of the terms interior gateways and exterior gateways to describe certain gateways, or what are normally called routers. These gateways (hereafter called routers) perform specific duties within the hierarchical Internet architecture, with the duties matching the services required by this structure.

The TCP/IP routing scheme used in the Internet relies on interior gateways, or routers, (noted with "I" in the illustration), to move data packets within an autonomous system, such as the network at a university campus. Exterior gateways, or routers, (noted with "E"), pass data packets between these autonomous systems.

Figure 1: The TCP/IP routing scheme used in the Internet relies on interior gateways, or routers, (noted with "I" in the illustration), to move data packets within an autonomous system, such as the network at a university campus. Exterior gateways, or routers, (noted with "E"), pass data packets between these autonomous systems.

An interior router moves information within an autonomous system. An autonomous system is a group of networks under the control and authority of a single entity. An example is the networked computing resources at a single university. Among the Interior Gateway Protocols (IGPs) are RIP and OSPF.

An exterior router moves data from one autonomous system to anotherthat is, from one university's internet to another's. The TCP/IP Exterior Gateway Protocol (EGP) is an example of this type of protocol.

This tutorial, number 35, by Jim Carr, was originally published in the June 1991 issue of LAN Magazine/Network Magazine.