Routing

Determining the path used to deliver packets from source to destination.

End systems send and receive data. Intermediate systems (routers) forward packets between networks.

Routing Algorithms

Algorithms to compute the best path in a network. Best path depends on context and the entity making the decision.

A routing algorithm must provide:

• Correctness
  Always finds a valid path if one exists.
• Simplicity
  Low implementation and maintenance overhead.
• Robustness
  Handles link failures and topology changes without crashing.
• Stability
  Converges to a fixed set of routes; does not oscillate.
• Fairness
  Distributes network resources equitably across flows.
• Optimality
  Selects the path with the lowest cost.

Best Path

Defined by a cost metric assigned to each link or path. Common cost factors:

• Number of hops
• Bandwidth (inverse: higher bandwidth = lower cost)
• Delay / latency
• Error rate
• Congestion level
• Communication cost
• Physical distance

Multiple metrics can be combined into a single composite cost.

Static Routing

Non-adaptive routing. Routing tables are manually configured and remain fixed until changed by an administrator.

Properties:

• Simple to implement and reason about.
• No protocol overhead.
• Not adaptive
  Does not react to failures or congestion.
• Requires manual update whenever topology changes.
• Does not scale beyond small networks.

Static routes are assigned a fixed cost. A default route is typically included to handle unknown destinations. Excessive static routes increase lookup time on the router.

Hierarchical Routing

Routers are grouped into regions using the most-significant bits of addresses. Intra-region routing uses local tables. Inter-region routing is handled by dedicated gateway routers.

Properties:

• Reduces routing table size at each router.
• Scales to large networks; the Internet uses hierarchical routing.
• May require more than two levels for very large topologies.

Dynamic Routing

Adaptive routing. Routers exchange routing information periodically and recompute best paths automatically. Routing tables update in response to topology changes and link failures.

Flooding

Every incoming packet is forwarded to all outgoing links except the one it arrived on. Delivery is guaranteed as long as a path exists.

Properties:

• Generates very high traffic volume.
• Without loop prevention, packets circulate indefinitely.
• Loop prevention uses sequence numbers.
• Routers discard packets whose sequence number has already been seen.

Broadcast Routing

Packets are sent to all nodes in the network. Guaranteed delivery. Higher overhead than flooding.

Shortest Path Routing

Models the network as a weighted graph. Each router runs Dijkstra’s algorithm on a full topology view to compute the minimum-cost path to every destination.

Distance Vector Routing

Each router maintains a distance table to every destination. Tables are shared with direct neighbors periodically. Each router updates its own table using the Bellman-Ford equation:

• $x$: current router
• $y$: destination
• $v$: neighbor of $x$
• $c(x, v)$: link cost from $x$ to $v$

No router has a global topology view. Susceptible to the count-to-infinity problem when a link fails.

Example: Routing Information Protocol (RIP).

Path Vector Routing

Extension of distance vector routing. Each router tracks the full path to each destination, not just the distance. Loops are detected by checking whether the receiving router’s ID already appears in the path.

• Policy-aware
  Routers can reject paths that traverse unwanted networks.
• No count-to-infinity problem.

Example: Border Gateway Protocol (BGP), used for inter-AS routing on the Internet.

Link State Routing

Each router floods its directly connected link states to every other router. Every router independently builds a full topology map and runs Dijkstra’s algorithm.

• Faster convergence than distance vector routing.
• No count-to-infinity problem.
• Higher memory and CPU usage.

Example: Open Shortest Path First (OSPF).

Source Routing

The source node specifies the complete route that packets must follow. Intermediate routers do not make forwarding decisions.

Classification by Number of Receivers

In multicast routing, packets are forwarded to multiple outgoing links. Routers maintain group membership tables. The set of destination nodes is called a multicast group.

Inside a Router

Forwarding Table

Each router stores a forwarding table mapping destination prefixes to outgoing interfaces. The table is derived from the routing table but optimized for fast lookup.

• Routing table
  Computed by routing protocols. Stores full path information.
• Forwarding table
  Used per-packet. Stores only next-hop and interface.

Queueing

When packets arrive, the router decides whether to:

• Forward the packet via the forwarding table.
• Prioritize the packet over others in the queue.
• Discard the packet (buffer full or policy rule matched).

Different queue disciplines apply different rules per traffic class.

Inter-Router Configuration

A /30 subnet is the conventional choice for point-to-point links between two routers. Provides exactly two usable host addresses, one per router interface.

If two non-adjacent routers $A$ and $B$ connect through intermediaries, they may reuse the same subnet address on their inter-router interfaces. Avoided in medium to large networks to prevent address ambiguity.

By convention, the address assigned to a router interface on a /30 link is either:

• The first usable address (network address + 1).
• The second usable address (broadcast address - 1).