Routing Basics

Routing: selecting a path in a network

A route from Los Angeles to New York can use different roads and intermediate cities. In a computer network, routing selects a path for a packet between networks. The decision is performed by specialized devices called routers.

Routing determines how packets move between networks. A router examines the packet's destination address, selects the next hop, and forwards the packet toward the destination network. The decision is made independently at each router, so a route can change between segments. Each hop consults its own forwarding information and does not require the first router to know every physical link. The goal is to select the best path according to metrics, policy, and the available routes while preserving reachability.

The routing table

A router makes forwarding decisions using rules stored in a database called a routing table. For each known destination prefix, the routing table stores the information needed to forward a packet: "To reach destination network X, send the packet to next router Y through local interface Z." If several entries match, the router selects the more specific prefix by longest-prefix matching. An entry can represent a directly connected network, a static route, or a route learned through a dynamic protocol.

The table can be built from directly connected, static, and dynamic routes and then used by the forwarding process. If no specific entry matches, a configured default route may be used; if no usable route exists, the router cannot forward the packet toward that destination. A router can also compare route preference and metric after matching the destination prefix. This leads to the distinction between static and dynamic routing.

Static routing: manual configuration

Static routing defines a destination prefix, mask or prefix length, and next hop manually. The administrator can also specify an outgoing interface and configures entries on routers according to the intended topology.

Example: A fixed route can specify Highway 5 followed by exit 23. In a network configuration, a similar entry remains active until an administrator changes or removes it, even when the surrounding topology changes.

Advantages of Static Routing

• Simplicity and low overhead: The entries are simple and do not require a routing protocol to exchange routes. The router uses no link bandwidth for those protocol messages, although it still stores entries in its forwarding structures and performs address lookup.
• Predictability and control: The administrator defines the next hop and interface for each route. This gives direct control over path selection and can restrict the route to required prefixes.
• Limited route advertisements: Static routing does not exchange routes through a dynamic protocol, which limits topology information in those messages. A static entry does not replace filtering or access control.

Disadvantages of Static Routing

• Lack of automatic adaptation: After a link or router failure, a static route that points to the failed path remains unreachable until an administrator changes it. Entries using that path can then cause packets to be discarded. An alternate entry or tracking mechanism can change this behavior.
• Scalability issues: Manual configuration fits small networks with a few routers. In a network with hundreds or thousands of routers, maintaining routes for many prefixes increases the number of changes and the risk of errors.
• Administrative burden: Adding a network segment requires manual updates to the tables on relevant routers. In a large topology, the same change may affect many devices.

Dynamic routing: exchanging information

Dynamic routing lets routers exchange reachability information and update routes after topology changes. It requires protocol configuration, a defined exchange scope, and time for convergence after each topology change in practice.

Example: Waze recalculates a route after road conditions change. A routing protocol performs a similar update after a change in link state, prefixes, or metrics. Routing protocols do not necessarily exchange information about traffic jams or transient congestion.

How Dynamic Routing Works

Routers running dynamic protocols exchange advertisements about prefixes, neighbors, and metrics. They may first form protocol-specific neighbor relationships and then exchange periodic or triggered updates. The frequency and contents of messages depend on the protocol. Each router builds its table from received information and local route-selection rules.

Advantages of Dynamic Routing

• Adaptation after failure: After a link failure, a protocol can advertise the change and calculate another route when one is available. Availability of an alternative depends on topology and policy. Traffic then uses the new path after convergence.
• Scalability: In large networks, dynamic protocols automate the exchange of information about growing prefix sets and topology changes. The protocol still needs a defined scope and policy for each domain.
• Reduced administrative overhead: An administrator maintains protocol configuration, authentication, and filtering rules instead of changing every entry after each topology change. Operational monitoring remains necessary.

Disadvantages of Dynamic Routing

• Resource consumption: Routing protocols use CPU and RAM for calculations and link bandwidth for control messages. The overhead depends on the number of prefixes, neighbors, and update frequency, especially after topology changes.
• Complexity: Configuring and diagnosing a dynamic protocol requires knowledge of its adjacencies, metrics, convergence state, and route advertisements.

Routing protocols

Routers use specialized protocols to exchange route information. It is useful to distinguish the protocol carrying packets from the protocol building the routing table.

• Routable protocol (e.g., IP): This is the protocol whose packets are forwarded. It provides logical addressing, including source and destination addresses. IP and IPX are examples.
• Routing protocol (e.g., OSPF, BGP): Routers use it to exchange information with each other. The information builds routing tables that then forward packets of the routable protocol.

Protocols within and between autonomous systems

The Internet consists of many autonomous systems. A university, corporation, or Internet Service Provider (ISP) network may be managed by one organization and is known as an Autonomous System (AS). Routing protocols are divided into two main categories based on whether they operate within or between these autonomous systems. An ASN identifies an autonomous system during inter-operator route exchange. Inter-AS policy can control which prefixes are accepted, preferred, or announced.

Route selection: metrics and convergence

Routing metrics: the cost of a route

When a dynamic routing protocol knows multiple routes to the same destination, it compares them using its metric and policy. In protocols that minimize cost, a lower metric has priority. If values tie, the protocol can apply additional selection rules. Different protocols use different metrics:

• Hop count: RIP counts the routers on a route. Under this metric, fewer hops produce a lower cost, while RIP treats 16 as infinity.
• Bandwidth: OSPF uses an interface cost that is commonly related inversely to bandwidth and then sums costs along a route. Raw bandwidth is not the name of the OSPF metric; the protocol compares configured costs.
• Delay (Latency): The time a packet takes to cross a link. EIGRP includes delay in its composite metric.
• Load: How heavily a link is used. EIGRP can include load when configured to do so.
• Reliability: A measure of link reliability that EIGRP can include in its metric.
• Cost: A protocol or administrator-defined value used to compare routes.

Convergence after a topology change

The process by which routers reach a consistent view of routing information after a change is called convergence.Convergence time affects forwarding continuity after a link failure. It includes failure detection, information propagation, and calculation of new paths. During this period, packets may be dropped or looped, and some prefixes may temporarily lack a usable route. Protocols use neighbor messages, timers, and their own calculation mechanisms. RIP, OSPF, and EIGRP use different update and calculation mechanisms, so convergence time depends on configuration, timers, topology, and the failure-detection method.