!main_tags!Routing Algorithms - Computer Networks | What's Your IQ !main_header!

Routing Algorithms

Fundamental mechanisms and protocols to determine optimal paths for data packet forwarding in computer networks.

Introduction to Routing Algorithms

Definition and Purpose

Routing algorithms: computational procedures to determine optimal paths from source to destination in networks. Purpose: efficient, reliable packet forwarding. Essential in network layer of OSI model.

Role in Computer Networks

Enable dynamic path selection, load balancing, fault tolerance. Impact latency, throughput, network utilization. Adapt to topology changes and link failures.

Basic Routing Process

1. Topology discovery. 2. Metric evaluation. 3. Path calculation. 4. Forwarding table update. 5. Packet transmission.

"Routing is the backbone of scalable and efficient communication in modern networks." -- Andrew S. Tanenbaum

Routing Metrics

Definition and Importance

Quantitative measures guiding route selection. Influence algorithm decisions. Metrics determine shortest, fastest, or most reliable path.

Common Metrics

Hop count, bandwidth, delay, load, reliability, cost, MTU (Maximum Transmission Unit).

Metric Calculation

Static: preset values (e.g., hop count). Dynamic: measured continuously (e.g., delay). Composite metrics combine multiple factors.

Metric Description Typical Use
Hop Count Number of intermediate routers Distance Vector Routing
Bandwidth Available data rate on link Load balancing, QoS routing
Delay Time for packet traversal Real-time applications

Classification of Routing Algorithms

Static vs Dynamic Routing

Static: preconfigured routes, no topology updates. Dynamic: adapt to network changes, use routing algorithms.

Centralized vs Distributed

Centralized: single node computes routes (e.g., network controller). Distributed: each node computes independently via information exchange.

Flat vs Hierarchical Routing

Flat: all nodes equal role, full topology knowledge. Hierarchical: network divided in layers or domains, reduces routing complexity.

Distance Vector Routing

Basic Principle

Each router maintains distance vector: cost to each destination. Exchanges vectors with neighbors periodically.

Bellman-Ford Algorithm

Iterative update: for each destination, select neighbor with minimum cost plus link cost.

for each destination D: distance[D] = min { cost to neighbor N + distance_N[D] }

Advantages and Limitations

Advantages: simple, low computation. Limitations: slow convergence, routing loops, count-to-infinity problem.

Enhancements

Split horizon, route poisoning, hold-down timers mitigate loops and convergence delay.

Path Vector Routing

Concept

Each route advertisement carries entire path (sequence of ASes). Prevents loops by checking path information.

Application: BGP

Border Gateway Protocol uses path vector routing for inter-domain routing on the Internet.

Key Features

Policy-based routing, path attributes, loop avoidance, scalability for large networks.

Hierarchical Routing

Need and Benefits

Scales large networks by dividing into regions or domains. Reduces routing table size and update overhead.

Two-Level Hierarchy

Intra-domain routing: detailed topology inside domain. Inter-domain routing: abstracted paths between domains.

Examples

OSPF areas, BGP Autonomous Systems, IS-IS multi-level routing.

Common Routing Protocols

Interior Gateway Protocols (IGP)

RIP: Distance vector, hop count metric, max 15 hops, slow convergence. OSPF: Link state, hierarchical areas, fast convergence. IS-IS: Link state, flexible metric, supports ISO protocols.

Exterior Gateway Protocols (EGP)

BGP: Path vector, policy-based, inter-domain routing, scalable.

Protocol Features Comparison

Protocol Algorithm Type Metric Scope
RIP Distance Vector Hop Count Intra-domain
OSPF Link State Cost (bandwidth-based) Intra-domain
BGP Path Vector Policy-based Inter-domain

Comparison of Routing Algorithms

Convergence Speed

Link state: fast due to global view. Distance vector: slower, prone to loops. Path vector: moderate, depends on policy.

Scalability

Distance vector: limited by count-to-infinity. Link state: memory intensive but scalable with hierarchy. Path vector: highly scalable for large internetworks.

Complexity

Distance vector: low complexity, simple implementation. Link state: higher CPU and memory usage. Path vector: complex policy handling and path management.

Fault Tolerance

Link state detects failures quickly via flooding updates. Distance vector slower, vulnerable to routing loops. Path vector relies on policy and path validation.

Algorithmic Complexity and Scalability

Distance Vector Complexity

Time: O(N) per update per node, N = number of nodes. Space: O(N) for routing table.

Link State Complexity

Time: O(N^2) for Dijkstra’s algorithm in naive form, improved with heaps to O(N log N). Space: O(N^2) for topology database.

Scalability Techniques

Hierarchical routing reduces update scope. Aggregation of routes. Incremental updates. Use of area division in OSPF.

Security Considerations in Routing

Threats

Route spoofing, blackhole attacks, routing table poisoning, wormhole attacks.

Mitigation Techniques

Authentication of routing messages (e.g., cryptographic signatures). Secure routing protocols (e.g., Secure BGP). Monitoring and anomaly detection.

Protocol-specific Security

RIP lacks security features. OSPF supports authentication. BGP supports MD5 and TCP-AO for secure sessions.

References

  • Andrew S. Tanenbaum, David J. Wetherall, "Computer Networks," 5th ed., Pearson, 2011, pp. 345-390.
  • Larry L. Peterson, Bruce S. Davie, "Computer Networks: A Systems Approach," 5th ed., Morgan Kaufmann, 2011, pp. 415-460.
  • R. Perlman, "Interconnections: Bridges, Routers, Switches, and Internetworking Protocols," 2nd ed., Addison-Wesley, 2000, pp. 301-340.
  • E. Rosen, A. Viswanathan, R. Callon, "Multiprotocol Label Switching Architecture," RFC 3031, 2001, pp. 1-79.
  • D. Awduche et al., "Overview and Principles of Internet Traffic Engineering," RFC 3272, 2002, pp. 1-28.
!main_footer!