Routing

Introduction

Routing: process of determining a path for data packets through a network from source to destination. Function: performed at network layer. Objective: optimize path based on criteria such as shortest distance, least cost, or minimum delay. Essential for packet switching, internetworking, and scalable communication.

"Routing is the art and science of moving information from one point to another in an efficient, reliable, and scalable manner." -- Andrew S. Tanenbaum

Routing Concepts

Definition and Scope

Routing: selection of paths in a network. Scope: intra-domain and inter-domain routing. Key components: routing algorithms, routing protocols, routing tables, forwarding mechanisms.

Routing vs Forwarding

Routing: path determination performed by control plane. Forwarding: moving packets based on routing decisions performed by data plane. Separation enables modular design and efficiency.

Routing Metrics

Metrics define path cost: hop count, bandwidth, delay, load, reliability, administrative weight. Metric choice impacts route selection and network performance.

Static vs Dynamic Routing

Static routing: manual configuration, fixed paths, low overhead, limited scalability. Dynamic routing: automatic updates, adapts to topology changes, uses routing protocols, higher complexity.

Routing Algorithms

Overview

Algorithms compute best path based on network topology and metrics. Two main categories: distance vector and link state.

Distance Vector Algorithm

Principle: each router shares routing table with neighbors. Info: distance (metric) and next hop. Repeated updates converge to shortest paths. Simplicity: suitable for small networks.

Link State Algorithm

Principle: each router floods link states to all nodes. Complete network map constructed. Shortest path tree computed via Dijkstra’s algorithm. Faster convergence, scalable, complex.

Path Vector Algorithm

Used in inter-domain routing (e.g., BGP). Maintains path information to prevent loops. Path attributes used for policy-based routing.

Routing Protocols

Classification

Interior Gateway Protocols (IGPs): operate within autonomous systems. Examples: RIP, OSPF, EIGRP. Exterior Gateway Protocols (EGPs): operate between autonomous systems. Example: BGP.

RIP (Routing Information Protocol)

Distance vector protocol. Metric: hop count (max 15). Updates: periodic broadcasts every 30 seconds. Simple, but slow convergence and limited scalability.

OSPF (Open Shortest Path First)

Link state protocol. Metric: cost based on bandwidth. Uses areas to support hierarchy. Fast convergence, supports large networks.

BGP (Border Gateway Protocol)

Path vector protocol. Controls inter-domain routing on Internet. Uses policy-based path selection. Path attributes: AS path, origin, next hop.

Routing Tables

Structure and Content

Entries: destination network, next hop, metric, interface, timestamp. Used by router to forward packets. Maintained dynamically or statically.

Routing Table Lookup

Longest prefix match applied to destination IP. Lookup speed critical for performance. Implemented using trie structures, TCAMs in hardware.

Route Aggregation

Combines multiple routes into single summary route. Reduces table size, improves scalability, limits routing update overhead.

Path Selection Metrics

Hop Count

Counts number of routers between source and destination. Simple, but ignores bandwidth, delay, reliability.

Bandwidth

Preference for high-bandwidth links. Metric inversely proportional to bandwidth. Used in OSPF cost calculation.

Delay

Measures latency on links. Important for real-time applications. Tradeoff with bandwidth.

Load & Reliability

Load: current traffic on link. Reliability: historical stability of link. Metrics combined for composite cost.

Distance Vector Routing

Algorithm Description

Each node maintains vector of distances to all nodes. Periodic exchange with neighbors. Bellman-Ford algorithm used to update routes.

Advantages

Simple, easy to implement. Low processing overhead. Good for small or stable networks.

Disadvantages

Slow convergence. Count-to-infinity problem. Limited scalability.

Count-to-Infinity Problem

Routing loops cause metric to increment indefinitely. Solutions: split horizon, poison reverse, hold-down timers.

Link State Routing

Algorithm Description

Routers broadcast link state packets (LSPs). Each router builds complete topology map. Dijkstra’s algorithm computes shortest path tree.

Advantages

Faster convergence. Accurate topology knowledge. Scalable to large networks.

Disadvantages

Higher processing and storage requirements. Flooding overhead.

Dijkstra’s Algorithm

Initialize: Set of nodes N in network Set distance to source node = 0 Set distances to other nodes = infinity Set all nodes unvisitedWhile unvisited nodes remain: Select unvisited node with smallest tentative distance For each neighbor of selected node: Calculate tentative distance through selected node If tentative distance < current distance: Update distance Mark selected node as visited 

Hierarchical Routing

Concept

Network divided into regions or areas. Local routing within area, summarized routing between areas. Reduces routing table size and update overhead.

OSPF Areas

Backbone area (Area 0) interconnects other areas. Area border routers summarize routes. Supports scalability and administrative control.

Benefits

Improved scalability. Reduced routing overhead. Faster convergence within areas.

Challenges

Complex configuration. Area boundary failure impacts routing.

Interdomain Routing

Autonomous Systems (AS)

Independent administrative domains. Routing policies enforced per AS. AS numbers identify domains.

BGP Protocol

Path vector protocol for inter-AS routing. Exchanges network reachability and policy info. Supports route filtering, aggregation, and path selection.

Policy-Based Routing

Routing decisions influenced by business agreements, security, preferences. Not necessarily shortest path.

Route Advertisement and Withdrawal

BGP routers advertise reachable prefixes. Withdraw unreachable routes. Supports incremental updates.

Routing Loop Avoidance

Causes

Incorrect or outdated routing info. Temporary inconsistencies during topology changes.

Techniques

Split Horizon: do not advertise route back to origin. Poison Reverse: advertise infinite metric to prevent loops. Hold-Down Timers: suppress unstable routes.

Loop-Free Alternates

Precomputed backup routes avoiding loops. Used for fast reroute in case of link failure.

TTL Field

Packet’s Time-to-Live decremented at each hop. Prevents endless circulation of looping packets.

Scalability and Performance

Challenges

Large network size: increased routing table size. Frequent topology changes: overhead in updates. Balancing convergence speed and stability.

Techniques

Hierarchical routing. Route aggregation and summarization. Triggered updates. Efficient data structures for routing tables.

Performance Metrics

Convergence time: speed to update routes after change. Overhead: bandwidth and CPU consumed. Memory: space for routing info.

References

• J. Moy, "OSPF Version 2," RFC 2328, 1998, pp. 1-210.
• Y. Rekhter, T. Li, "A Border Gateway Protocol 4 (BGP-4)," RFC 4271, 2006, pp. 1-122.
• A. S. Tanenbaum, D. J. Wetherall, "Computer Networks," 5th Ed., Pearson, 2010, pp. 321-389.
• C. E. Perkins, E. M. Royer, "Ad-hoc On-Demand Distance Vector Routing," IEEE WMCSA, vol. 2, 1999, pp. 90-100.
• R. Perlman, "Interconnections: Bridges, Routers, Switches, and Internetworking Protocols," 2nd Ed., Addison-Wesley, 2000, pp. 250-300.