Introduction

Routing is moving information across a network from source to destination. Along the way, at least one intermediate node is typically encountered. Routing is often contrasted with bridging which seems to accomplish precisely the same thing. The primary difference between the two is that bridging occurs at Layer 2 (the link layer) of the OSI reference model, while routing occurs at Layer 3 (the network layer).

This distinction provides routing and bridging with different information to use in the process of moving information from source to destination. As a result, routing and bridging accomplish their tasks in different ways and, in fact, there are several different kinds of routing and bridging.

Routing Components

Routing involves two basic activities: determination of optimal routing paths and the transport of information groups (typically called packets) through an network.  The latter of these is referred to as switching. Switching is relatively straightforward. Path determination, on the other hand, can be very complex.

Figure 1. Network Router

Path Determination

A metric is a number used assigned to a parameter and is used to quanitfy how "good" or "bad" that parameter is for a task. For example, path length is used by routing algorithms to determine the optimal path to a destination. To aid the process of path determination, routing algorithms initialize and maintain routing tables, which contain route information. Route information varies depending on the routing algorithm used.

Routing algorithms fill routing tables with a variety of information. Destination/next hop associations tell a router that a particular destination can be gained optimally by sending the packet to a particular router representing the "next hop" on the way to the final destination. When a router receives an incoming packet, it checks the shows an example of a destination/next hop routing table.

Figure 2. Destination/Next Hop Routing Table

Routing tables can also contain other information, such as information about the desirability of a path. Routers compare metrics to determine optimal routes. Metrics differ depending on the design of the routing algorithm being used. A variety of common metrics will be introduced and described later in this chapter.

Routers communicate with one another (and maintain their routing tables) through the transmission of a variety of messages. The routing update message is one such message. Routing updates generally consist of all or a portion of a routing table. By analyzing routing updates from all routers, a router can build a detailed picture of network topology. A link-state advertisement is another example of a message sent between routers. Link-state advertisements inform other routers of the state of the sender's links. Link information can also be used to build a complete picture of network topology. Once the network topology is understood, routers can determine optimal routes to network destinations.

Metrics

Routing tables contain information used by switching software to select the best route. But how, specifically, are routing tables built? What is the specific nature of the information they contain? How do routing algorithms determine that one route is preferable to others?

Routing algorithms have used many different metrics to determine the best route. Sophisticated routing algorithms can base route selection on multiple metrics, combining them in a single (hybrid) metric. All of the following metrics have been used:

• Path Length

• Reliability

• Delay

• Bandwidth

• Load

• Communication Cost

Path Length

Path length is the most common routing metric. Some routing protocols allow network administrators to assign arbitrary costs to each network link. In this case, path length is the sum of the costs associated with each link traversed. Other routing protocols define hop count, a metric that specifies the number of passes through networking products (such as routers) that a packet must take en route from a source to a destination.

Reliability

Reliability, in the context of routing algorithms, refers to the reliability (usually described in terms of the bit-error rate) of each network link. Some network links may go down more often than others. Once down, some network links may be repaired more easily or more quickly than other links. Any reliability factors can be taken into account in the assignment of reliability ratings. Reliability ratings are usually assigned to network links by network administrators. They are typically arbitrary numeric values.

Delay

Routing delay refers to the length of time required to move a packet from source to destination through the network. Delay depends on many factors, including the bandwidth of intermediate network links, the port queues at each router along the way, network congestion on all intermediate network links, and the physical distance to be traveled. Because it is a conglomeration of several important variables, delay is a common and useful metric.

Bandwidth

Bandwidth refers to the available traffic capacity of a link. All other things being equal, a 10-Mbps Ethernet link would be preferable to a 64-kbps leased line. Although bandwidth is a rating of the maximum attainable throughput on a link, routes through links with greater bandwidth do not necessarily provide better routes than routes through slower links. If, for example, a faster link is much busier, the actual time required to send a packet to the destination may be greater through the fast link.

Load

Load refers to the degree to which a network resource (such as a router) is busy. Load can be calculated in a variety of ways, including CPU utilization and packets processed per second. Monitoring these parameters on a continual basis can itself be resource intensive.

Communication Cost

Communication cost is another important metric. Some companies may not care about performance as much as they care about operating expenditures. Even though line delay might be longer, they will send packets over their own lines rather than through public lines that will cost money for usage time.

Routing Protocols

Routing protocols are broken into the Exterior Routing protocols which are used in the main part of the Internet and the Interior Routing protocols used within a trusted environment. Each of these categories has several different types of technologies.

Static Routing

Usually an experienced network administrator will seek to minimize any manual configuration. In the case of Exterior routing, this may be different, as static routing offers a number of advantages when routing between Autonomous Systems. These advantages can be summarized as follows:

• Complete flexibility over the advertisement of subnet's and their next hop routers

• No routing protocol traffic travels over the link connecting Autonomous Systems

• As no routing protocol is operating over the inter-AS link, there is no possibility of a faulty router in one AS affecting the other AS.

Exterior Routing Protocols

Exterior Gateway Protocol - EGP

As its name suggests, the Exterior Gateway Protocol, or EGP, was the first example of an exterior gateway protocol. EGP has three components, Neighbor acquisition, Neighbor reachability and routing information. EGP was designed to add a measure of automation to the configuration of routes between different Autonomous Systems.

The routing information of EGP is similar to distance vector protocols, but it omits the metric for routes advertised. EGP was implemented like this because it was designed for the Internet, when it was assumed that there would be a core network, with separate routing domains connected to this core by one router. The major problem with using EGP in a more generalized network is that, since no use is made of metrics, if there is more than one path to a destination, packets can very easily get caught in routing loops.

EGP has been superseded by the Border Gateway Protocol, BGP.

Border Gateway Protocol - BGP

The main features of BGP are that it introduced a reliable transport protocol, to ensure that route updates are received. BGP also implements a keep-alive mechanism, ensuring that BGP routers know if neighboring BGP routers fail. BGP does not transmit metrics with it's route updates, but does transmit a path for each AS that lists the AS's to be visited on the way to the destination AS. BGP thus avoids the circulating packet problem of EGP.

BGP works on the principle of enforcing policies. A policy is manually configured and allows a BGP enabled router to rank possible routes to other Autonomous Systems, selecting the best path.

Interior Routing Protocols

Open Shortest Path First - OSPF

Open Shortest Path First (OSPF) is a routing protocol. As such, it calls for the sending of link state advertisements (LSAs) to all other routers within the same hierarchical area. Information on attached interfaces, metrics used, and other variables are included in OSPF LSAs. As OSPF routers accumulate link state information, they use the SPF algorithm to calculate the shortest path to each node.

As a link state routing protocol, OSPF contrasts with RIP and IGRP, which are distance vector routing protocols. Routers running the distance vector algorithm send all or a portion of their routing tables in routing update messages, but only to their neighbors.

Routing Information Protocol - RIP

The Routing Information Protocol (RIP) is a routing protocol that keeps tract of routers in its immediate network and is a very fast routing protocol and useful for small networks.

Each entry in a RIP routing table provides a variety of information, including the ultimate destination, the next hop on the way to that destination, and a metric. The metric indicates the distance in number of hops to the destination. Other information can also be present in the routing table, including various timers associated with the route. A typical RIP routing table is shown in Figure 3.

Figure 3. Typical RIP Routing Table

RIP maintains only the best route to a destination. When new information provides a better route, this information replaces old route information. Network topology changes can provoke changes to routes, causing, for example, a new route to become the best route to a particular destination.

When network topology changes occur, they are reflected in routing update messages. For example, when a router detects a link failure or a router failure, it recalculates its routes and sends routing update messages. Each router receiving a routing update message that includes a change updates its tables and propagates the change.

Interior Gateway Routing Protocol and Enhanced IGRP

The Interior Gateway Routing Protocol (IGRP) is a robust routing protocol and may have an arbitrarily complex topology consisting of media with diverse bandwidth and delay characteristics. IGRP uses distance vector routing and has each router send all or a portion of its routing table in a routing update message at regular intervals to each of its neighboring routers. As routing information proliferates through the network, routers can calculate distances to all nodes within the network.

Distance vector routing protocols are often contrasted with link state routing protocols, which send local connection information to all nodes in the network.

IGRP uses a combination (vector) of metrics. Network delay, bandwidth, reliability, and are all factored into the routing decision. Network administrators can set the weighting factors for each of these metrics. IGRP uses either the administrator-set or the default weightings to automatically calculate optimal routes.

IGRP provides a wide range for its metrics. For example, reliability and load can take on any value between 1 and 255; bandwidth can take on values reflecting speeds from 1,200 bps to 10 gigabits per second; while delay can take on any value from 1 to 2 to the 24^th power. Wide metric ranges allow satisfactory metric setting in networks with widely varying performance characteristics. Most importantly, the metric components are combined in a user-definable algorithm. As a result, network administrators can influence route selection in an intuitive fashion.

In Summary:

• Routers use Layer 3 (IP) to determine how to route a packet

• The routing algorithms used outside of a secure environment are Exterior Gateway Routing Protocols

• Routers try to determine the optimum path based on a variety of metrics

• Addresses may be dynamic (temporary) or static (permanent)