Routing Algorithms

1. Introduction to Routing

 Definition: The routing algorithm is the part of the network layer software responsible
for deciding which output line an incoming packet should be transmitted on.

 Datagram Networks: If the network uses datagrams internally, this decision must be
made anew for every arriving packet because the best route may have changed.

 Algorithm Goals: Stability (converging to a fixed set of paths), fast convergence, fairness,
and efficiency.

 Two Major Classes:

o Non-adaptive (Static Routing): Routes are computed in advance (offline) and

o Adaptive (Dynamic Routing): Changes routing decisions dynamically to reflect

2. The Optimality Principle & Sink Trees

 The Optimality Principle: States that if router $J$ is on the optimal path from router $I$
to router $K$, then the optimal path from $J$ to $K$ also falls along the exact same
route.

 Sink Tree: A direct consequence of this principle. The set of optimal routes from all
sources to a given destination forms a tree rooted at the destination.

 Key Feature: Sink trees do not contain any loops, ensuring that every packet gets
delivered within a finite number of hops.

3. Shortest Path Algorithms (Dijkstra's)

 Concept: Computes optimal paths by building a graph where nodes represent routers
and edges represent communication links.

 Metrics: The "shortest" path can be measured by hop count, geographic distance, mean
delay, bandwidth, or communication cost.

 How It Works:

1. Starts at the source node and marks it as "permanent."

2. Examines adjacent "working" nodes, labeling them tentatively with the distance
from the source.
 3. Searches the graph for the tentative node with the smallest value, makes it
permanent, and repeats the process until the destination is reached.

4. Flooding

 Concept: A simple local technique where every incoming packet is sent out on every
outgoing line except the one it arrived on.

 Loop Prevention: To prevent an infinite number of duplicate packets, a hop counter is

 Use Cases: Highly robust for military networks or disaster zones. Also used as a baseline
metric to compare other algorithms because flooding always finds the absolute shortest
path.

5. Distance Vector Routing

 Also Known As: The distributed Bellman-Ford routing algorithm.

 Mechanism: Each router maintains a table (a vector) giving the best-known distance to
each destination and the preferred outgoing line to use.

 Updates: Routers periodically exchange their delay estimates with their immediate
neighbors and update their own tables if a neighbor offers a faster route.

 The Count-to-Infinity Problem: The major flaw of this algorithm. It reacts very quickly to
"good news" (finding a new short path) but extremely slowly to "bad news" (a router
going down), causing routers to loop and slowly increment distances to infinity.

6. Hierarchical Routing

 Problem: As networks grow, routing tables consume too much memory, CPU time, and
bandwidth.

 Solution: Routers are divided into regions. A router knows everything about routing
within its own region but knows nothing about the internal structure of other regions.

 Trade-off: Saves massive amounts of table space, but incurs the penalty of increased
path length (packets may take a slightly longer route due to region boundaries).

7. Broadcasting Routing

 Concept: Sending a packet to all destinations simultaneously.

 Reverse Path Forwarding: The most elegant method for broadcasting. When a broadcast
packet arrives at a router, it checks if the packet arrived on the link that is normally used
 for sending packets toward the source. If yes, it forwards it. If no, it discards it as a
duplicate.

8. Multicast Routing

 Concept: Sending messages to well-defined groups (e.g., live sports streaming) without
broadcasting to the entire network. Uses spanning trees.

 Dense Groups (Pruned Spanning Trees): If a router receives a multicast packet but has
no hosts interested in that group, it sends a PRUNE message upstream to stop receiving
that traffic. (e.g., DVMRP).

 Sparse Groups (Core-Based Trees): Computes a single spanning tree for the group. All
routers agree on a root (the "core" or "rendezvous point"). Senders shoot packets to the
core, which then forwards them down the tree to group members.

9. Routing in Ad Hoc Networks (MANETs)

 Characteristics: Nodes are mobile, communicate wirelessly, and act as both hosts and
routers. Topology changes constantly.

 AODV (Ad hoc On-demand Distance Vector): * Route Discovery: Routes are discovered
on demand (only when someone wants to send a packet) to save battery and bandwidth.

o Mechanism: The sender floods a ROUTE REQUEST. The destination sends back a
ROUTE REPLY along the reverse path.

o Optimization: Uses the IP Time to live (TTL) field to limit broadcast scope,
searching locally first and expanding outward if needed.

o Route Maintenance: Nodes periodically broadcast Hello messages. If a neighbor