Connected: An Internet Encyclopedia
Routing

Top: Connected: An Internet Encyclopedia
Up: Topics
Up: Functions

Search: |  | Search Depth: |
Search Type: | String RegEx | Search Options: | NoCase WholeWord

### Routing

Routing is the main process used by Internet hosts to deliver packets. Internet uses a hop-by-hop routing model, which means that each host or router that handles a packet examines the Destination Address in the IP header, computes the next hop that will bring the packet one step closer to its destination, and delivers the packet to the next hop, where the process is repeated. To make this work, two things are needed. First, routing tables match destination addresses with next hops. Second, routing protocols determine the contents of these tables.

#### Routing Tables

Internet hosts use routing tables to compute the next hop for a packet. Routing tables can take many forms, but here is a simple model that can explain most Internet routing. Each entry in a routing table has at least three fields - Routing Address, Routing Mask, and Next Hop. The Next Hop is always the IP address of another host or router that is directly reachable via an Ethernet, serial link, or some other physical connection. Bridged networks are regarded as single connections. The Routing Address and Routing Mask are used like a subnet address and mask to specify a set of destinations for which the routing entry is valid for. In order to be in this set, the Destination Address and Routing Address bits must match for each 1 bit in the Routing Mask. For example, a Routing Address/Mask pair of 128.8.0.0/255.255.0.0 would match any IP Destination Address whose first two bytes were 128.8.

If no routing table entries match a packet's Destination Address, the packet is discarded as undeliverable (possibly with an ICMP notification to the sender). If multiple routing tables entries match, the longest match is prefered. The longest match is the entry with the most 1 bits in its Routing Mask.

To avoid needing routing entries for every possible Internet destination, most hosts and routers use a default route (some routing tables contain nothing but a single default route). A default route has a Routing Address/Mask pair of 0.0.0.0/0.0.0.0. In other words, it matches every IP address, but since there are no 1 bits in its Routing Mask, any other match would be selected by the longest match rule. The default route will only be used if there are no others matches in the routing table, thus its name. Default routes are quite common, and are put to best use on networks with only a single link connecting to the global Internet. On such a network, routing tables will have entries for local nets and subnets, as well as a single default route leading to the outbound link. However, remember that all Next Hops must be directly reachable, so the default routes won't necessarily point to the same IP address. Also, some networks (large Internet service providers, mostly) use defaultless routing tables that must be able to match every IP address in the global net.

#### Routing Protocols

"Real network engineers construct routing tables by hand," but the rest of us use routing protocols. Routing protocols form the core of the hacker's Internet, because it is here that all the decisions get made. Network engineers assign costs to network paths, and routing protocols select the least-cost path to the destination.

`\begin{soapbox}`

I find that routing protocols bear an uncanny resemblence to capitalist market economics. In both systems, there is a large group of "nodes", the decisions of each being driven by a cost-minimization algorithm. The end result is a reasonably efficient distribution of "resources". Furthermore, cost determination is done in similar ways. A router, like an import/export firm, will compute its cost, add on profit for its part in the transaction, and pass this cost along to customers. Both systems use this method to achieve reasonable efficiency.

`\end{soapbox}`

#### Distance-Vector Routing Protocols

One type of routing protocol requires that each router simply inform its neighbors of its routing table. For each network path, the receiving routers pick the neighbor advertising the lowest cost, then add this entry into its routing table for re-advertisement. Hello and RIP are common D-V routing protocols. Common enhancements to D-V algorithms include split horizon, poison reverse, triggered updates, and holddown. You will find a good discussion of D-V, or Bellman-Ford algorithms in RIP's protocol specification, RFC 1058.

#### Link State Routing Protocols

This type of routing protocol requires each router to maintain at least a partial map of the network. When a network link changes state (up to down, or vice versa), a notification is flooded throughout the network. All the routers note the change, and recompute their routes accordingly. This method is more reliable, easier to debug and less bandwidth-intensive than Distance-Vector. It is also more complex and more compute- and memory-intensive. OSPF and OSI's IS-IS are link state routing protocols.

#### Interior Routing

Interior routing occurs within an autonomous system. Most common routing protocols, such as RIP and OSPF, are interior routing protocols. The basic routable element is the IP network or subnetwork, or CIDR prefix for newer protocols.

#### Exterior Routing

Exterior routing occurs between autonomous systems, and is of concern to service providers and other large or complex networks. The basic routable element is the Autonomous System, a collection of CIDR prefixes identified by an Autonomous System number. While there may be many different interior routing scheme, a single exterior routing system manages the global Internet, based on the BGP-4 exterior routing protocol.

- BGP-4 Protocol Overview
- OSPF-2 Protocol Overview
- RIP Protocol Overview

Connected: An Internet Encyclopedia
Routing