Packet Switching Network Routing Protocols and Strategies

Posted on Oct 3, 2025 in Computer Engineering

Routing in Packet Switching Networks

Routing is a key design issue for packet-switched networks, involving selecting the optimal route across the network between end nodes.

Required Routing Characteristics

  • Correctness
  • Simplicity
  • Robustness
  • Stability
  • Fairness
  • Optimality
  • Efficiency

Internet Routing Protocols

Routers are responsible for receiving and forwarding packets through interconnected networks. They make routing decisions based on knowledge of the topology and traffic/delay conditions, exchanging information using specialized routing protocols.

Key Concepts in Routing Function

  • Routing Information: Data concerning the topology and delays within the internet.
  • Routing Algorithm: The algorithm used to make a routing decision for a particular datagram, based on current routing information.

Performance Criteria for Route Selection

Routes are selected based on criteria such as:

  • Minimum Hop: Selecting the path with the fewest intermediate nodes.
  • Least Cost Routing: Selecting the path with the lowest cumulative cost (often based on delay or utilization).

Least cost routing is generally more flexible and common than minimum hop routing.

Routing Decision Time

Decisions can be made on a:

  • Packet (datagram) or virtual circuit basis.
  • Fixed or dynamically changing basis.

Routing Decision Place

Decisions can be made:

  • Distributed: Made by each node. This approach is more complex but more robust.
  • Centralized: Made by a designated node.
  • Source: Made by the source station.

Network Information Source and Update Timing

Routing decisions are usually based on knowledge of the network topology, traffic load, and link cost.

Information Sources
  • Distributed Routing: Uses local knowledge, information from adjacent nodes, or information from all nodes on a potential route.
  • Central Routing: Collects information from all nodes.
Update Timing

Update timing depends on the routing strategy:

  • Fixed: Never updated.
  • Adaptive: Regular updates.

Routing Strategies

Fixed Routing

Fixed routing uses a single permanent route for each source-to-destination pair of nodes. The route is determined using a least-cost algorithm and remains fixed until a change in network topology occurs or based on expected traffic/capacity.

  • Advantage: Simplicity.
  • Disadvantage: Lack of flexibility; does not react to network failure or congestion.

Flooding Strategy

In flooding, a packet is sent by a node to every neighbor. Eventually, multiple copies arrive at the destination. This strategy requires no prior network information.

Mechanisms are needed to limit incessant retransmission:

  • Nodes can remember the identity of retransmitted packets.
  • A hop count can be included in packets.
Properties of Flooding
  • Advantages:
    • All possible routes are tried.
    • Highly robust.
    • Can be used to send emergency messages.
    • At least one packet will have taken the minimum hop route.
    • All nodes directly or indirectly connected to the source are visited.
  • Disadvantages:
    • High traffic load generated.
    • Security concerns.

Random Routing Strategy

Random routing offers the simplicity of flooding but generates much less traffic load. The node selects only one outgoing path for retransmission of an incoming packet.

  • Selection can be random or round robin.
  • A refinement involves selecting the outgoing path based on probability calculation.
  • No network information is needed.

Note: A random route is typically neither least cost nor minimum hop.

Adaptive Routing Strategy

Adaptive routing is used by almost all packet switching networks. Routing decisions change dynamically as network conditions change (e.g., due to failure or congestion). This strategy requires current network information.

Adaptive Routing Characteristics
  • Advantages:
    • Improved performance.
    • Aids in congestion control.
  • Disadvantages:
    • Routing decisions are more complex.
    • Potential for oscillation (routing loops).
Classification of Adaptive Routing Strategies

Adaptive strategies are often classified based on the information source:

Local (Isolated)
Routes packets to the outgoing link with the shortest queue. Can include bias for each destination. Rarely used as it does not utilize available network information.
Adjacent Nodes
Takes advantage of delay and outage information shared between neighboring nodes. Can be distributed or centralized.
All Nodes
Similar to adjacent node strategies but involves information exchange across the entire network (e.g., Link-State protocols).

ARPANET Routing Strategies

ARPANET (Advanced Research Projects Agency Network) employed several generations of routing strategies:

1st Generation: Distance Vector Routing
  • Distributed adaptive routing using estimated delay.
  • Queue length was used as the estimate of delay.
  • Employed a version of the Bellman-Ford algorithm.
  • Nodes exchanged delay vectors with neighbors and updated routing tables based on incoming information.
  • Limitation: Did not consider line speed, only queue length, and responded slowly to congestion.
2nd Generation: Link-State Routing
  • Distributed adaptive routing using a measured delay criterion.
  • Delay was measured using timestamps of arrival, departure, and ACK times.
  • Average delays were re-computed every 10 seconds.
  • Any changes were flooded to all other nodes.
  • Routing was re-computed using Dijkstra’s algorithm.
  • Performance: Good under light and medium loads, but under heavy loads, there was little correlation between reported delays and experienced delays.
3rd Generation Improvements

The third generation focused on refining link cost calculation to damp routing oscillations and reduce routing overhead:

  • Measured average delay over the last 10 seconds and transformed it into a link utilization estimate.
  • Normalized this estimate based on current and previous results.
  • Set link cost as a function of average utilization.

Autonomous Systems (AS)

An Autonomous System (AS) is a fundamental concept in internet routing, exhibiting the following characteristics:

  • It is a set of routers and networks managed by a single organization.
  • It consists of a group of routers exchanging information via a common routing protocol.
  • Except in times of failure, the AS is connected (in a graph-theoretic sense), meaning there is a path between any pair of nodes.

Interior Router Protocol (IRP)

An IRP is a shared routing protocol that passes routing information between routers within an Autonomous System (AS). IRPs are often custom-tailored to specific applications and requirements.

Exterior Router Protocol (ERP)

An ERP is used to pass routing information between routers in different ASs.

The ERP needs to pass less detailed information than an IRP because:

  • If a datagram is transferred from a host in one AS to a host in another AS, a router in the first system only needs to determine the target AS and devise a route to reach that target system.
  • Once the datagram enters the target AS, the internal routers (using the IRP) cooperate to deliver the datagram.
  • The ERP is not concerned with, and does not know about, the detailed internal route within the target AS.

Examples of Routing Protocols:

  • Border Gateway Protocol (BGP) (Typically an ERP)
  • Open Shortest Path First (OSPF) (Typically an IRP)

Core Approaches to Internet Routing Protocols

Internet routing protocols (specifically IRPs) employ one of three primary approaches for gathering and using routing information:

  1. Distance-Vector Routing
  2. Path-Vector Routing
  3. Link-State Routing

Distance-Vector Routing Explained

This approach requires that each node exchange information with its neighboring nodes (nodes directly connected to the same network).

  • It was used in the first-generation routing algorithm for ARPANET.
  • Each node maintains a vector of link costs for each directly attached network, along with distance and next-hop vectors for each destination.
  • The Routing Information Protocol (RIP) uses this approach.