0.

Introduction
1. Overview
The network layer plays a important role in the networking stack by ensuring that data packets are
delivered from the source to the destination. This process usually involves multiple intermediary nodes
and requires mechanisms for:

Optimal path selection (Routing)

Efficient packet transfer (Forwarding)

Routing is especially critical in broadcast networks when the source and destination reside on separate
subnets. The key challenge here is to maintain timely, reliable, and efficient delivery, particularly in
dynamic and unpredictable network conditions.

2. Routing vs. Forwarding

2.1 Routing: The Decision-Making Process

Purpose: Determines the optimal path for packets to travel through the network.
Characteristics:
Operates over longer time scales, focusing on strategic decision-making.
Utilizes routing algorithms to update and maintain routing tables dynamically or statically.
Considers various metrics such as hop count, bandwidth, and latency to decide the best
route.
Outcome: Updates routing tables that guide the forwarding process.

2.2 Forwarding: The Execution Phase

Purpose: Directs individual packets to the appropriate outgoing link.

Characteristics:
Operates at shorter time scales, focusing on immediate processing.
Uses the routing table to make hop-by-hop decisions.
Relies on hardware acceleration in modern routers for faster processing.
Outcome: Ensures packets physically move from one node to the next toward their destination.

3. Routing Implementation 1 / 40
3.1 Datagram Networks: Connectionless Approach

Each packet is treated independently, with no prior knowledge of preceding or following packets.
Advantages:
Highly adaptable to changes in network topology.
Allows for flexible load balancing as routes can vary for each packet.
Disadvantages:
Higher overhead since routing decisions must be made for each packet.
Potential for out-of-order delivery if packets take different routes.

3.2 Virtual Circuit Networks: Connection-Oriented Approach

A fixed path (virtual circuit) is established before any data transmission begins.
Advantages:
Guarantees in-order packet delivery since all packets follow the same route.
Reduces per-packet processing overhead after the connection setup.
Disadvantages:
Less adaptable to network changes during a session.
Connection setup introduces initial delay, unsuitable for short-lived sessions.

4. Properties of Routing Algorithms

4.1 Key Characteristics

1. Correctness:
Ensures accurate route computation and error-free packet delivery.
Validates routes against potential routing loops or dead ends.
2. Simplicity:
Avoids overly complex algorithms that may require excessive computational resources.
Prioritizes maintainable code for real-world implementations.
3. Robustness:
Handles hardware or software failures gracefully.
Adapts to changes in network topology without significant disruptions.
4. Stability:
Maintains consistent routes even during transient network changes.
Achieves convergence (route updates) quickly to avoid oscillations or inconsistencies.
5. Fairness:
Balances resource allocation across competing users or data flows.
Prevents scenarios where certain users 2dominate
/ 40
bandwidth.
 6. Efficiency:
Minimizes packet delays while maximizing overall network throughput.
Strives for optimal resource utilization with minimal overhead.

4.2 Trade-offs in Routing

Fairness vs. Efficiency: Achieving fairness may involve redistributing resources, potentially
lowering overall throughput.
Stability vs. Adaptability: Highly adaptive algorithms can destabilize networks due to frequent
updates.
Complexity vs. Performance: More sophisticated algorithms may improve performance but
require greater processing power.

5. Types of Routing Algorithms

5.1 Nonadaptive (Static) Algorithms

Predefined routes are computed offline and loaded into routers.

Advantages:
Simple to implement and manage.
Effective in predictable, unchanging networks.
Disadvantages:
Inflexible, cannot adapt to traffic changes or failures.
Prone to inefficiencies in dynamic networks.

5.2 Adaptive (Dynamic) Algorithms

Routes are adjusted in real-time based on network conditions.

Information Sources:
Local Data: Collected by the router itself (e.g., queue length).
Adjacent Routers: Exchanges routing information with directly connected neighbors.
Network-Wide Data: Utilizes centralized or distributed updates from across the network.
Update Triggers:
Topology Change: Reacts to link failures or new connections.
Periodic Updates: Regularly refreshes routing tables at set intervals.
Load-Based Adjustments: Adapts routes based on traffic congestion or link utilization.
Optimization Metrics:
Physical Distance: Shortest path by physical length.
Hop Count: Minimizes the number of intermediate nodes.
Link Capacity: Chooses paths with higher
3 / 40bandwidth availability.
 Current Load: Avoids congested links to improve performance.

6. Optimization Goals
6.1 Performance Metrics

1. Mean Packet Delay: Reduces the average time taken for packets to traverse the network.
2. Network Throughput: Maximizes the rate of successful packet delivery over the network.
3. Resource Utilization: Optimizes the use of network infrastructure, avoiding bottlenecks or
underutilized paths.
4. Path Efficiency: Minimizes path length or energy consumption in wireless networks.

6.2 Key Challenges

Balancing competing metrics like delay vs. throughput.

Handling trade-offs between fairness, simplicity, and adaptability.
Achieving global optimization with localized decision-making in distributed networks.

7. Stability and Robustness in Routing

7.1 Stability:
Ensures quick convergence to avoid oscillating routes.
Uses mechanisms like route dampening to suppress frequent updates.
7.2 Robustness:
Accounts for link failures, rerouting traffic seamlessly to alternate paths.
Supports recovery mechanisms like path redundancy or fast reroute protocols.
7.3 Handling Topology Changes:
Rapidly adjusts to node or link additions/removals.
Prevents cascading failures by limiting the scope of updates.
7.4 Traffic Patterns:
Adapts to shifting traffic demands while maintaining service levels

1. The Optimality Principle

1. Overview
4 / 40
The Optimality Principle (Bellman, 1957) is a foundational concept in routing algorithms, stating that
optimal routes from one node to another depend on the optimality of intermediate nodes. This principle
helps define how routing paths are determined and provides a benchmark for evaluating routing
algorithms.

2. Explanation of the Principle

2.1 Optimal Path Behavior

If router b is part of the optimal path from router a to router c, the optimal path from b to c must
also lie along the same route.

2.2 Mathematical Insight

The full path from a to c is divided into two parts:

From a to b (denoted as ab).
From b to c (denoted as bc).
If a better route than bc existed, it could be appended to ab to create a new, improved path from a
to c, contradicting the assumption that the original route (ab + bc) was optimal.

3. Consequences of the Optimality Principle

3.1 Sink Tree Formation

The result of this principle is that optimal paths from all routers to a destination form a tree, called
a sink tree.
Sink Tree: A tree rooted at the destination node, where all optimal paths converge.
Example: If the distance metric is hops, a sink tree shows the least number of hops needed
to reach the destination.

3.2 Non-uniqueness

Sink trees are not necessarily unique, as other trees with the same path lengths might exist.
When considering all possible paths, the structure can be generalized into a Directed Acyclic
Graph (DAG), which represents all paths but without any loops.

4. Practical Considerations
5 / 40
4.1 Robustness of Paths

The assumption is made that paths do not interfere with each other (e.g., no congestion).
In reality, network conditions can change dynamically, causing disruptions such as link failures or
varying router states.

4.2 Sink Tree Computation

The method by which routers acquire the information to compute their respective sink trees is not
straightforward.
Routers may need to individually gather topology data or rely on other means of information
collection.
This becomes an important consideration in real-world implementations.

4.3 Real-world Challenges

Since a sink tree is indeed a tree, it does not contain any loops, so each packet will be delivered
within a finite and bounded number of hops.
In practice, life is not quite this easy. Links and routers can go down and come back up during
operation, so different routers may have different ideas about the current topology.

5. Key Takeaways

1. The Optimality Principle is fundamental to understanding routing behavior in networks, helping

routers determine the best path based on intermediate nodes.
2. The sink tree concept provides a clear way of visualizing the optimal paths in a network.
3. While the principle offers an idealized view, real-world challenges like dynamic topologies and
information gathering add complexity to routing algorithms.
4. The goal of all routing algorithms is to discover and use the sink trees for all routers.

2. Shortest Path Algorithm

1. Introduction to Shortest Path Algorithms

Routing algorithms aim to find the most optimal paths between nodes in a network. In scenarios where
routers may not have complete network knowledge, an optimal path is computed based on a complete
picture of the network. A shortest path between two routers is defined as the path with the least cost,

6 / 40
based on a specific metric. These metrics can range from the number of hops to more sophisticated
measures like delay, bandwidth, or communication cost.

2. Graph Representation of the Network

2.1 Graph Construction

The network is represented as a graph:

Nodes: Each router in the network is represented by a node.

Edges: The communication links between routers are represented as edges.

2.2 Metrics for Path Evaluation

Hops: The number of intermediate routers between two endpoints.

Geographic Distance: Physical distance between routers, such as kilometers, assuming the
network layout is geographically relevant.
Other Metrics: These can include network delay, bandwidth, traffic load, or even cost of
communication (e.g., monetary or energy consumption).

2.3 Choosing the Optimal Path

The metric used will determine the shortest path. For instance, if we're considering hops, the algorithm
will prioritize paths with fewer routers. However, if we are considering delay, the algorithm will prioritize
paths with the minimum cumulative delay.

3. Dijkstra’s Shortest Path Algorithm

3.1 Overview

Dijkstra’s algorithm, introduced by Edsger Dijkstra in 1959, is a well-known algorithm for computing the
shortest paths between a source node and all other nodes in a graph. It works by iteratively exploring
the graph, updating tentative distances (labels) for each node until the shortest paths are found.

3.2 Key Properties

The algorithm works on weighted graphs where each edge has a non-negative weight (e.g., delay
or distance).
The algorithm assigns a distance label to each node, representing the shortest known distance
from the source node.
7 / 40
 Initially, all nodes are labeled with infinity (∞), indicating that no paths are known. As the algorithm
progresses, labels are updated to reflect shorter paths.
Once the shortest path to a node is found, the label is made permanent, and no further updates
are made to that node.

4. Detailed Algorithm Process

4.1 Initialization

Every node starts with an initial label of infinity, except for the source node, which has a label of 0,
representing the distance from itself.
A node is said to be "tentatively labeled" when its distance is still subject to change. Once a node's
label reflects the shortest distance from the source node, it is considered "permanent."

4.2 Step-by-Step Execution

1. Start with the Source Node:

Mark the source node as permanent (label it with 0).
Update the labels of all adjacent nodes with the distances from the source node.
2. Choose the Next Node:
From the remaining nodes, choose the one with the smallest tentative label and make it
permanent.
3. Update Neighboring Nodes:
For each node adjacent to the newly permanent node, calculate the total distance by adding
the distance of the permanent node to the weight of the edge connecting to the neighbor.
If this new distance is smaller than the current tentative label of the neighbor, update the
label.
4. Repeat:
Repeat this process until all nodes are made permanent, and the shortest paths from the
source node are determined.

5. Why the Algorithm Works

5.1 Proof of Correctness

At each step, Dijkstra’s algorithm guarantees that once a node’s label is made permanent, it
reflects the shortest possible path from the source node.
If there were a shorter path discovered later, it would have been found earlier because any new
tentative path must be longer than any current8 / permanent
40 path.
 This ensures that the algorithm always finds the shortest path in the graph.

5.2 No Cycles

The algorithm assumes that the graph is free of negative-weight cycles, as negative weights would
allow for infinite reductions in the path length, violating the assumption of non-negative labels.

6. Code Implementation Notes

6.1 Backward Search

In some implementations, the search starts from the destination node and proceeds backward. This is
done by labeling each node with its predecessor, and the final path is reconstructed by reversing the
order of labels.

6.2 Efficiency

The algorithm’s time complexity is O(n^2) in the naive implementation, though more efficient versions
using priority queues (like Fibonacci heaps) can achieve a time complexity of O(E + log V).

7. Conclusion

7.1 Versatile Metric Usage

Dijkstra's algorithm can work with various metrics, such as delay, cost, or hops, allowing it to be applied
in different types of networks with different optimization goals.

7.2 Widely Used in Routing

This algorithm forms the foundation for many routing protocols in modern computer networks, ensuring
efficient data transfer by computing optimal paths.

7.3 Applicability in Distributed Routing

Even in distributed settings where not all routers have complete network knowledge, algorithms like
Dijkstra’s are used to find optimal routes.

3. Flooding

9 / 40
Flooding is a routing technique where each incoming packet is sent out on every outgoing link, except
the one it arrived on. It enables routers to make decisions based solely on local knowledge, without
requiring a complete view of the network.

1. Challenges with Flooding

1.1 Duplicate Packets: Flooding can result in a massive number of duplicate packets, potentially
leading to an infinite number of them.
1.2 Hop Counter:
Each packet contains a hop counter in its header.
The counter is decremented at each hop, and the packet is discarded once the counter
reaches zero.
Ideally, the hop counter is initialized to the path length between source and destination.
If the path length is unknown, the worst-case value (the network's full diameter) is used.
1.3 Exponential Growth: Even with a hop counter, flooding can still generate exponential
numbers of duplicate packets as the hop count increases.

2. Improving Flooding Efficiency

2.1 Tracking Packets: Routers can track which packets have already been flooded by using a
sequence number.
Each source router adds a unique sequence number to its packets.
Routers maintain a list of sequence numbers they’ve processed per source router.
If a router sees a packet with a sequence number it has already processed, the packet is not
flooded again.
2.2 Counter (k): To avoid an unbounded list, a counter k is used, which indicates all sequence
numbers up to k have been seen.
When a packet arrives, if its sequence number is less than or equal to k, it is discarded.
This counter-based approach reduces the need for a full list of sequence numbers.

3. Use Cases of Flooding

3.1 Broadcasting:
Flooding ensures that a packet reaches every node in the network.
It is effective for broadcasting, although inefficient for communication with a single
destination.
10 / 40
 3.2 Wireless Networks:
In wireless networks, messages transmitted by a station are received by all stations within its
radio range.
This behavior mimics flooding and is used by some algorithms for efficient data distribution.
3.3 Robustness:
Flooding is resilient, capable of finding a path even if large parts of the network fail (e.g., in
conflict zones).
It will still deliver a packet as long as some route exists.
3.4 Minimal Setup:
Flooding requires minimal setup: routers only need to know their immediate neighbors.
This simplicity allows flooding to serve as a building block for more sophisticated routing
algorithms.

4. Flooding as a Benchmark

4.1 Shortest Path Guarantee:

Flooding explores all possible paths in parallel, ensuring that it always chooses the shortest
path.
It serves as an ideal benchmark for comparing other routing algorithms.
No other algorithm can produce a shorter delay than flooding (if we ignore the overhead
generated by the flooding process itself).
4.2 Overhead Considerations:
While flooding generates significant overhead, it guarantees the shortest delay for packet
delivery.

4. Distance Vector Routing

Distance vector routing is a class of dynamic routing algorithms used to determine the best path to
each destination in a computer network. It is called "distance vector" because each router maintains a
table (or vector) that lists the distance (or cost) to reach each destination in the network. These distance
vectors are periodically exchanged between neighboring routers to update routing tables. This allows
routers to collectively compute the best possible paths for routing packets to their destinations.

1- How Distance Vector Routing Works:

1. Routing Table Structure:

11 / 40
 Every router maintains a routing table containing the best-known distances to all other routers
in the network.
Each entry in the table includes:
Destination router: The router the current router wants to reach.
Cost (or distance): The metric used to calculate the distance (e.g., the number of hops,
delay, or bandwidth).
Next hop: The immediate neighbor to which packets should be forwarded to reach the
destination.
2. Exchange of Information:
Routers periodically exchange their routing tables with their immediate neighbors.
During each exchange, a router shares its current best-known distances to all destinations
with its neighbors.
When a router receives an updated routing table from a neighbor, it uses this new information
to recalculate its own distances to destinations. It updates its routing table if it finds a better
(shorter) path.
3. Distance Calculation:
Each router computes the best path to each destination by considering the paths from its
neighbors.
If router A sends a routing table to router B, and router A reports a path to destination X of
distance D_A , router B adds the cost of the link between them to this distance ( D_B = D_A +
cost(A to B) ) to calculate its new distance to destination X.
4. Metrics:
The metric used for routing can vary depending on the network and its needs:
Number of hops: A simple metric where each link between routers counts as one hop.
Propagation delay: The time it takes for a packet to travel from one router to another.
Bandwidth: The maximum data transfer rate of a link.
5. Convergence:
Over time, as routers exchange information, they gradually update their tables until they
converge on the optimal paths to all destinations.
The convergence process is the router network collectively adjusting its routing information to
reflect the true state of the network, where all routers agree on the best routes.

2- Example:

12 / 40
Consider a network where routers use delay as the metric for routing. Each router knows the delay to
its immediate neighbors, and they exchange this information with each other. Let's assume that router J
has neighbors A, I, H, and K, with known delays of 8, 10, 12, and 6 milliseconds, respectively.

Suppose router J wants to compute the best route to router G. Here's how J might update its routing
table:

Route through A: The delay to A is 8 msec, and A reports a delay of 18 msec to G. So, the total
delay to G via A is 8 + 18 = 26 msec.
Route through I: The delay to I is 10 msec, and I reports a delay of 31 msec to G. So, the total
delay to G via I is 10 + 31 = 41 msec.
Route through H: The delay to H is 12 msec, and H reports a delay of 6 msec to G. So, the total
delay to G via H is 12 + 6 = 18 msec.
Route through K: The delay to K is 6 msec, and K reports a delay of 31 msec to G. So, the total
delay to G via K is 6 + 31 = 37 msec.

From these calculations, router J concludes that the best route to G is through H, with a total delay of
18 msec.

3- The Count-to-Infinity Problem:

13 / 40
While distance vector routing is simple and effective in many cases, it has a significant drawback known
as the count-to-infinity problem.

This issue arises when a network experiences a topology change, such as a link failure. Due to the
nature of distance vector routing, routers may take a long time to update their tables and may
temporarily use suboptimal routes, leading to inefficient routing and slow convergence.

4- Explanation of Count-to-Infinity:

Imagine a simple linear network of routers: A, B, C, D, and E. Suppose that the link between A and B
fails, causing the routers to update their routing tables. Here’s how the count-to-infinity problem unfolds:

1. Initial State: Initially, the routers know that A is unreachable because the link between A and B is
down. Thus, the distance to A for all routers except A is infinity.
2. First Exchange: When router B sends its routing table to C, it tells C that it has no path to A. C will
then update its table, marking the distance to A as 2 (C’s distance to B + 1).
3. Subsequent Exchanges: C then sends this information to D, which updates its distance to A as 3
(C’s distance to A + 1). D then sends this to E, and so on, gradually increasing the distance to A in
each router's table.
4. Count to Infinity: This process continues until all routers eventually converge to the fact that A is
unreachable, but this may take a significant number of exchanges. The number of exchanges
grows with the length of the network, causing delays in convergence.

In some cases, routers may even temporarily believe that they have a valid path to A through another
router, causing the routing tables to increment by one hop per exchange. This gradual increase in the
distance to infinity is what gives the problem its name.

5- Limitations and Alternatives:

Despite these techniques, distance vector routing is still slower in terms of convergence compared
to link-state routing algorithms.
In link-state routing, routers have a complete map of the network and can compute the shortest
paths more efficiently.
In particular, it reacts rapidly to good news, but leisurely to bad news
Distance vector routing is better suited for smaller networks with fewer topological changes.

6- Conclusion:

Distance vector routing is a simple and effective method for dynamic routing in networks, relying
on periodic exchanges of routing tables between neighboring routers.
Convergence can take time, especially when the network experiences failures, and the count-to-
infinity problem can cause delays in the network’s recovery.
Techniques like split horizon, poisoned reverse, and triggered updates help mitigate the
problem, but distance vector routing remains less efficient compared to link-state routing in large
14 / 40
 and complex networks.

This algorithm continues to be popular in small-scale or legacy networks, especially in protocols like
RIP (Routing Information Protocol), but more modern networks often prefer link-state routing for
faster convergence and better scalability.

5. Link State

1. Introduction
Distance Vector Routing was used in ARPANET until 1979 but was replaced by Link State
Routing due to inefficiency in handling network topology changes (e.g., the count-to-infinity
problem).
Link State Routing is faster and avoids the pitfalls of Distance Vector Routing.
Modern Protocols: Variants like IS-IS and OSPF are widely used in large networks and the
Internet today.

2. Key Idea
Link State Routing involves distributing the complete network topology to every router.
Each router uses this information to compute the shortest path to every other router using
Dijkstra’s Algorithm.

3. Five Steps of Link State Routing

3.1 Discover Neighbors

Each router identifies its directly connected neighbors and learns their network addresses.

3.2 Determine Link Costs

The router calculates the cost metric for each link to its neighbors (e.g., based on bandwidth,
delay, or other criteria).

3.3 Create Link State Packets (LSPs)

The router generates a packet containing all the information it has learned about its neighbors and
link costs.
15 / 40
3.4 Flood LSPs Across the Network

LSPs are distributed to all other routers through flooding. Each router receives and processes the
LSPs from all others.

3.5 Compute Shortest Paths

With the complete topology data, each router applies Dijkstra’s Algorithm to compute the
shortest path to every other router.

4. Learning About the Neighbors and Setting Link Costs

4.1 Learning About the Neighbors
When a router starts up, its first task is to identify its neighbors. This process differs based on the type
of connection:

4.1.1 Point-to-Point Connections

The router sends a special HELLO packet on each link.

Neighboring routers respond with their globally unique names (to avoid confusion when the
same name appears across multiple routers).

4.1.2 Broadcast Networks (e.g., Ethernet, Switch, or Ring)

More complex due to multiple routers sharing the network.

Example: In Fig. 5-11(a), routers A, C, and F are connected via a broadcast LAN, which provides
connectivity between all pairs.
Challenges:
Modeling the LAN as many point-to-point links can lead to inefficiencies (e.g., larger topology,
wasteful messages).
Solution:
Treat the LAN as a single artificial node (N) (Fig. 5-11(b)).
One router is designated to represent N in the routing protocol.
Connectivity between routers is modeled as paths (e.g., A → N → C).

4.2 Setting Link Costs

Link state routing requires assigning a cost metric to each link. These costs are used to compute the
shortest paths.

4.2.1 Cost Determination

16 / 40
 Automatic or Manual: Costs can be determined by the router or manually configured by the
operator.
Common Metric: Cost is often inversely proportional to bandwidth.
Example:
1 Gbps Ethernet: Cost = 1
100 Mbps Ethernet: Cost = 10
(Higher bandwidth = Lower cost)

4.2.2 Considering Geographic Spread

Link Delay: For geographically dispersed networks, delay can be considered in the cost metric.
Measuring Delay:
Use an ECHO packet:
1. Send an ECHO packet over the link.
2. The neighbor immediately sends it back.
3. Measure the round-trip time (RTT) and divide it by two to estimate the delay.

5. Building and Distributing Link State Packets

5.1 Building Link State Packets

Once a router gathers all necessary information about its neighbors, it prepares a link state packet
(LSP). The packet includes:

Sender identity
Sequence number (incremented with each new packet)
Age (to manage outdated information)
List of neighbors and the cost of reaching each one

5.1.1 Example

17 / 40
For the network in Fig. 5-12(a):

Costs are shown on the links.

Corresponding link state packets are displayed in Fig. 5-12(b).

The Data Structure Used by Router B:

The data structure used by router B for managing link state packets is illustrated in Fig. 5-13. Each row
corresponds to a link state packet that has recently arrived but has not yet been fully processed. The
table keeps track of the packet’s source, sequence number, age, and data. Additionally, flags for
sending and acknowledging packets are included for each of B's three links (to A, C, and F).

Here’s the table structure:

Explanation of how the flags work:

The send flags indicate where the packet must be sent.

The acknowledgement flags indicate where18the
/ 40 packet must be acknowledged.
Example of Packet Handling:

When the link state packet from A arrives at router B, it is sent to routers C and F and must be
acknowledged by router A.
Similarly, the packet from F is forwarded to A and C and acknowledged by F.

Handling Duplicate Packets:

If a duplicate packet arrives while the original is still being processed in the buffer, the flags need
to be updated. For example, if the C state packet arrives again from F before the original packet
is forwarded, the flags are changed to 100011, indicating that the packet must be acknowledged
by F but not forwarded to F again.

5.1.2 Timing for Packet Creation

Periodic updates: LSPs are generated at regular intervals.

Event-driven updates: LSPs are created when significant events occur, such as:
A link or neighbor going down or coming up.
Changes in link properties.

5.2 Distributing Link State Packets

The challenge lies in ensuring fast and reliable distribution of LSPs across the network. Any
inconsistency in the topology among routers can lead to:

Loops
Unreachable devices
Other routing issues

5.2.1 Basic Distribution Algorithm: Flooding

1. LSPs are flooded across the network to all routers.

2. Sequence numbers ensure proper tracking of packets:
Routers maintain a list of (source router, sequence number) pairs.
When a router receives an LSP:
If it's new, the packet is forwarded to all links except the one it came from.
If it's a duplicate, it is discarded.
If the sequence number is lower than the latest seen, it is rejected as obsolete.
3. Preventing Issues:
Sequence number wraparound: Use a 32-bit sequence number, which takes 137 years to
wrap (1 packet/sec).
Router crash: The router loses track of its sequence number. This can be addressed using
the Age field.
19 / 40
 Corrupted sequence numbers: If a packet arrives with a corrupted sequence number (e.g.,
65,540 instead of 4), packets with legitimate sequence numbers may be rejected.

5.2.2 Role of the Age Field

The Age field prevents old packets from lingering indefinitely:

Age starts high and decreases by 1 second per hop.
When age = 0, the packet is discarded.
This mechanism ensures:
Timely removal of outdated information.
Elimination of stale packets during the flooding process.

5.3 Refinements for Robustness

1. Holding Area:
When an LSP arrives, it is temporarily stored in a holding area before being forwarded.
This allows the router to:
Combine updates.
Discard duplicates.
2. Duplicate Handling:
If a second LSP arrives before the first is sent:
If sequence numbers are equal, discard the duplicate.
If sequence numbers are different, keep the latest and discard the older one.
3. Acknowledgments:
LSPs are acknowledged to ensure reliability.

6. Steps to Compute New Routes

6.1 Construct the Network Graph

Each router collects all the link state packets from every other router in the network.
Using this information, it builds a network graph, where:
Nodes represent routers.
Edges represent links between routers with their associated costs.
Links are bidirectional, and their costs may differ in each direction.

6.2 Run Dijkstra’s Algorithm

Each router runs Dijkstra’s shortest path algorithm locally on its network graph to determine:
The shortest path to every other router.
20 / 40
 The next hop to take for each destination.
The result is stored in the routing table.

7- Comparison between Distance Vector Routing and Link State

Routing:

1. Memory Requirement:
Link State Routing requires storing information about all links in the network, which scales
with kn (where k is the average number of neighbors per router, and n is the total number of
routers).
This is at least as large as the size of a routing table listing all destinations, making it
memory-intensive.
2. Computation Time:
Computing the shortest paths using Dijkstra's Algorithm involves processing the entire
network topology. Even with efficient data structures, the computation time grows faster than
kn, which can be a concern in large networks.
3. Advantages of Link State Routing:
Despite its higher resource demands, Link State Routing is preferred in many practical
scenarios because it avoids slow convergence issues seen in Distance Vector Routing
(e.g., the count-to-infinity problem).
Its ability to quickly adapt to topology changes makes it well-suited for dynamic networks.

In essence, while Link State Routing is more demanding in terms of memory and processing, its
reliability and speed in handling network changes often outweigh these drawbacks, particularly in
modern networks.

Feature Distance Vector Routing Link State Routing

Bandwidth Low (due to local sharing and no High (due to flooding and large link
Requirement flooding) state packets)
Knowledge of Local (based on information from Global (knowledge of entire network
Network neighbors only) topology)
Routing Bellman-Ford Algorithm Dijkstra's Algorithm
Algorithm
Traffic Low (minimal traffic due to small High (more traffic due to flooding)
updates)
Convergence Slow (good news spreads fast, bad Fast (converges quickly)
Speed news slowly)
Count to Infinity Yes (causes persistent routing No (no count to infinity problem)
Problem loops)
21 / 40
 Feature Distance Vector Routing Link State Routing
Persistent Yes (loops may persist indefinitely) No (only transient loops may occur)
Looping
Examples of RIP (Routing Information Protocol), OSPF (Open Shortest Path First), ISIS
Protocols IGRP (Interior Gateway Routing (Intermediate System to Intermediate
Protocol) System)

7. Broadcast Routing

Introduction

In some applications, hosts need to send messages to many or all other hosts.
For example, a service distributing weather reports, stock market updates, or live radio programs might
work best by sending to all machines and letting those that are interested read the data. Sending a
packet to all destinations simultaneously is called broadcasting. Various methods have been proposed
for accomplishing it.

Methods of Broadcasting
1- Simple Broadcasting

The source sends a distinct packet to each destination.

Disadvantages:
Wasteful of bandwidth.
Slow.
Requires the source to have a complete list of all destinations.
Despite being widely applicable, this method is not desirable in practice.

2- Multidestination Routing

Each packet contains either:

A list of destinations.
A bitmap indicating the desired destinations.
Process:
When a packet arrives at a router:
The router checks all destinations to determine the set of required output lines.
22 / 40
 A new copy of the packet is generated for each output line, including only the
destinations that use the respective line.
After enough hops, each packet will carry only one destination like a normal packet.
Advantages:
Efficient use of network bandwidth.
Disadvantages:
Requires the source to know all destinations.
As much work for a router as handling multiple distinct packets.

3- Flooding

Implemented with a sequence number per source.

Uses links efficiently with a simple decision rule at routers.
Advantages:
Useful for broadcasting.
Disadvantages:
not suited for point-to-point communication.
Observation:
Can be further optimized once the shortest path routes for regular packets are computed.

4- Reverse Path Forwarding

Concept:
23 / 40
 When a broadcast packet arrives at a router, the router checks if the packet arrived on the
preferred link used for sending packets toward the broadcast source.
If yes, the router forwards the packet to all links except the one it arrived on.
If no, the packet is discarded as a likely duplicate.
Example: Refer to Figure 5-15:
Part (a): A network.
Part (b): A sink tree for router I.
Part (c): Reverse path forwarding in action.
Steps:
First hop:
Router I sends packets to F, H, J, and N.
Packets arrive on the preferred path to I.
Second hop:
Eight packets are generated (two by each receiving router).
All eight arrive at previously unvisited routers, with five arriving along the preferred line.
Third hop:
Six packets are generated; three arrive on the preferred path (C, E, and K), while the
rest are duplicates.
Final result:
Broadcasting terminates after five hops and 24 packets.
Comparatively, following the sink tree exactly would take four hops and 14 packets.
Advantages:
Efficient and easy to implement.
Each broadcast packet is sent over each link only once in each direction.
Does not require sequence numbers or a list of destinations in the packet.

5- Spanning Tree-Based Broadcasting

Makes explicit use of a spanning tree (e.g., sink tree).

Process:
Each router copies an incoming broadcast packet to all spanning tree lines except the one it
arrived on.
Advantages:
Generates the absolute minimum number of packets necessary.
Example: In Fig. 5-15(b), using the sink tree minimizes the packets to 14.
Disadvantages:
Requires each router to know the spanning tree.
Availability of Information:
24 / 40
 Available in link state routing (all routers know the complete topology).
Unavailable in distance vector routing.

Summary of Methods

Method Advantages Disadvantages

Direct Broadcasting Simple, universally Wasteful bandwidth, requires destination
applicable list
Multidestination Efficient bandwidth usage High router processing, requires
destination list
Flooding Simple, effective for High redundancy and overhead
broadcasting
Reverse Path Efficient, no duplicates Requires routing knowledge for all
Forwarding destinations
Spanning Tree Minimum packets, highly Requires spanning tree knowledge
efficient

Each method has trade-offs between efficiency, simplicity, and implementation requirements, making
them suitable for different network scenarios.

6. Hierarchical Routing
Here's a detailed explanation of Hierarchical Routing, including the concept, benefits, drawbacks, and
practical examples, while incorporating additional depth as requested:

1. Hierarchical Routing: Concept and Importance

As networks grow in size, the challenge of maintaining routing tables in routers becomes significant due
to:

1. Memory Requirements:
Larger networks mean more entries in routing tables, consuming substantial router memory.
2. Processing Overhead:
Scanning through extensive routing tables requires more CPU time.
3. Bandwidth Usage:
Status reports on table updates consume network bandwidth.

25 / 40
To address these issues, hierarchical routing introduces a structure where the network is divided into
regions. Routers manage detailed routing for their own region but store summarized information about
other regions.

2. How Hierarchical Routing Works

1. Regions and Interconnection:

The network is divided into regions (or groups).
Each router:
Knows detailed routes within its region.
Maintains summarized routes for other regions (e.g., one entry per region).
2. Routing in Large Networks:
When routing across regions, packets are routed to a designated gateway router for inter-
region traffic.
Example:
In a two-level hierarchy, a packet from Router 1A in Region 1 to Router 5C in Region 5
passes through intermediate gateway routers at different levels of the hierarchy.
26 / 40
 3. Multi-level Hierarchies:
For very large networks, regions can be grouped into clusters, zones, or other hierarchical
levels.
Example: In a three-level hierarchy, regions are grouped into clusters, and clusters into
zones, reducing the need for routers to store detailed information about distant areas.

3. Efficiency Gains
1. Reduction in Routing Table Size:
Hierarchical routing condenses routing tables by grouping remote destinations into fewer
entries.
Example (Fig. 5-14):
A router’s table reduces from 17 entries (flat routing) to 7 entries (hierarchical
routing) in a two-level hierarchy.
2. Scalability:
With growing network size, the ratio of regions to routers per region increases, further
reducing the number of routing entries.
3. Optimal Hierarchy Levels

When a single network grows very large, the question arises: How many levels should the
hierarchy have?
1. Example: A Network with 720 Routers:
No Hierarchy: Each router needs 720 entries.
Two-Level Hierarchy:
The network is divided into 24 regions with 30 routers each.
Each router requires 30 local entries + 23 remote entries, totaling 53 entries.
Three-Level Hierarchy:
The network is divided into 8 clusters, each containing 9 regions with 10 routers
each.
Each router requires:
10 entries for local routers.
8 entries for other regions in the cluster.
7 entries for distant clusters.
Total: 25 entries.
2. Mathematical Insight:
Kamoun and Kleinrock (1979) discovered that the optimal number of levels for an N-
router network is Ln N, requiring a total of e Ln N entries per router.
The increase in effective mean path length caused by hierarchical routing is typically
small and acceptable.
27 / 40
4. Drawbacks of Hierarchical Routing
1. Increased Path Length:
Simplified routing results in non-optimal paths, increasing the travel distance for packets.
Example:
In a flat network, the best path from Router 1A to Router 5C passes through Region 2
In a hierarchical setup, the packet may pass through Region 3 instead, as all Region 5
traffic is directed via Region 3.
2. Complex Configuration:
Designing and maintaining a multi-level hierarchy can be challenging, especially as the
number of levels increases.
3. Fault Tolerance:
If a gateway router fails, inter-region communication can be disrupted unless redundancy is
implemented.

5. Practical Example
Imagine a large international network with thousands of routers:

1. Level 1 (Local Regions):

Routers within a city form a region. Each router knows all other routers in its region.
2. Level 2 (National Clusters):
Regions in the same country form a cluster. Routers know how to route packets to other
regions within the same cluster.
3. Level 3 (International Zones):
Clusters across different countries form zones. Routers only store one entry per cluster
outside their own zone.

Example Routing Path:

A packet from Berkeley, California, to Malindi, Kenya:
1. Berkeley Router → Routes within California.
2. Los Angeles Router → Handles all out-of-state traffic, sending it to New York Router
3. New York Router → Routes all foreign traffic to the Kenyan gateway in Nairobi.
4. Nairobi Router → Routes the packet to Malindi via regional routers.

6. Key Insights
28 / 40
 1. Trade-off Between Space and Path Length:
Hierarchical routing drastically reduces the size of routing tables but may increase path
lengths.
This trade-off is generally acceptable for large-scale networks.
2. Scalability:
Hierarchical routing supports scaling to millions of routers, as seen in the Internet and
telephone networks.
3. Optimal Hierarchy Design:
The hierarchy must balance:
Levels of hierarchy (too few vs. too many).
Redundancy to prevent failures at critical points.
4. Use Cases:
Widely used in the Internet, where autonomous systems (ASes) represent regions in
hierarchical routing.

Summary
Hierarchical routing is an essential strategy for managing large networks by dividing them into regions
and grouping these regions into higher levels. While it offers significant efficiency in memory and
processing, it comes with the cost of slightly increased path lengths. By optimizing the number of
hierarchical levels, networks can maintain scalability without compromising performance.

8. Multicast Routing Overview

Introduction

Multicast routing is essential for efficiently sending packets to multiple receivers in large networks. This
method is used in applications like multiplayer games or live video streaming, where delivering distinct
packets to each receiver is too costly, and broadcasting would be wasteful. The primary objective of
multicast routing is to send messages to specific groups of receivers without overburdening the
network. The routing algorithms for multicast focus on creating and maintaining efficient paths to deliver
packets to group members while minimizing bandwidth usage.

1- Key Concepts of Multicast Routing

Multicast Groups: Each multicast group is identified by a multicast address, and routers know
which groups they belong to.
Efficient Use of Bandwidth: Instead of broadcasting packets to all network nodes or sending
individual packets to each receiver, multicast29routing
/ 40 sends data to well-defined groups, reducing
 wasted bandwidth.

2- Dense vs. Sparse Groups

Multicast routing schemes are designed to handle both dense and sparse groups:

Dense Groups: For groups where receivers are scattered across most of the network, broadcast
can be a good starting point. However, broadcast is inefficient as it reaches routers not interested
in the message. Pruning the broadcast tree removes unnecessary links and optimizes the
multicast path.
Sparse Groups: For groups with a limited number of receivers compared to the network size,
efficient routing is achieved by constructing a multicast tree that minimizes the network resources
used.

3- Pruning Broadcast Spanning Trees

One solution for dense groups is to prune the broadcast spanning tree by removing links that do not
lead to group members. This creates a more efficient multicast tree. For example:

Spanning Tree for Broadcast: Initially, a spanning tree can be used for broadcast but is not
optimal for multicast due to redundant paths.30 / 40
 Pruned Spanning Tree: By removing non-essential paths, the tree becomes more efficient. For
example, a multicast tree for group 1 may be pruned to include only the links necessary to reach
members of group 1, reducing the total number of links from 10 to 7 (fig 5.16 b and fig 5.16 c).

4- Pruning Strategies

Link State Routing: In this approach, routers know the entire network topology, including group
membership, and can prune spanning trees accordingly. The MOSPF (Multicast OSPF) protocol
is an example of this.
Distance Vector Routing: This approach involves reverse path forwarding. Routers without any
hosts interested in the group will send a PRUNE message to stop forwarding multicast packets for
that group. This process continues recursively, pruning unnecessary paths.

While pruning improves efficiency, it requires significant router processing, especially in large networks.
For instance, if a network has n groups and each group has an average of m nodes, routers must store
mn pruned spanning trees, which can be resource-intensive.

5- Core-Based Trees

An alternative approach to pruning is the use of core-based trees, which construct a single spanning
tree for the entire multicast group. The tree is rooted at a core (or rendezvous point), and packets are
sent from each member to this core, merging the paths into a unified tree.

Tree Construction: All routers agree on the core, and the tree is built by sending packets from
group members to the core.
Performance Optimization: Once a packet reaches the tree, it can be forwarded both up towards
the core and down to other branches, reducing latency.

31 / 40
 Efficiency Concerns: Although core-based trees may not always provide the shortest path (e.g.,
when the core is far from the sender), they are efficient for sparse groups because routers only
need to maintain one tree per group, instead of multiple pruned trees.

6- Benefits of Core-Based Trees

Storage and Bandwidth Savings: With a shared tree, routers store only one tree per group,
significantly reducing storage requirements and message overhead.
Suitable for Sparse Groups: Core-based trees are commonly used for sparse multicast groups,
as seen in protocols like PIM (Protocol Independent Multicast).

Conclusion

Multicast routing, through strategies like pruning and core-based trees, optimizes the delivery of
packets to multicast groups. While pruning offers tailored, efficient paths for dense groups, core-based
trees provide a simplified and efficient structure for sparse groups, ensuring that multicast routing
scales effectively across large networks.

9. Anycast Routing
The content has been structured and formatted for clarity and readability as follows:

Anycast is a routing model where a packet is delivered to the nearest member of a group of nodes,
rather than a specific one. This is distinct from unicast (one-to-one), multicast (one-to-many), and
broadcast (one-to-all) delivery models. In anycast, the main goal is not to contact a particular node, but
to get the right information from any node in a group.

1- Why Use Anycast?

Anycast is useful when a service or information is provided by multiple nodes, and the key factor
is receiving the data, not the specific node providing it. For example, services like time of day or
content distribution can work with any node in the group.
One of the common uses of anycast on the Internet is DNS (Domain Name System), where DNS
servers that respond to a query can be geographically distributed. The closest or least congested
server is the one that answers.

2- How Anycast Works

32 / 40
Anycast routing does not require entirely new routing protocols. Distance vector and link state
protocols can be adapted to support anycast.

Distance vector routing: Multiple nodes can be assigned the same address (e.g., group 1 in the
diagram), and each node will receive routing information as usual. When a node wants to send a
packet to "1," it will send it to the closest instance of that address, according to the routing table.
For example, the routing in Figure 5-18(a) shows how nodes will route to the nearest instance
of destination "1." The routing protocol doesn't differentiate between the multiple nodes that
share the same address; it simply sends the packet along the shortest path to the destination.
This procedure works because the routing protocol does not realize that there are multiple
instances of destination 1. That is, it believes that all the instances of node 1 are the same
node, as in the topology shown in Fig. 5-18(b)
Link state routing: Works similarly, though with a slight difference in how routing information is
handled. The protocol must avoid calculating routes that incorrectly pass through the same
instance of "1," as this could cause loops or incorrect routing paths. Link state protocols already
differentiate between routers and hosts, so this distinction helps avoid errors.

Summary
Anycast routing allows for efficient delivery to the nearest available node in a group, making it useful for
services where the specific node doesn't matter, but proximity does. Regular routing protocols like
distance vector and link state can be adapted to work with anycast by considering multiple nodes as
a single entity for routing purposes.

10. Routing for Mobile Hosts

33 / 40
1- Introduction
Millions of people use computers while on the go, from truly mobile situations with wireless devices in
moving cars to nomadic situations where laptop computers are used in various locations. We will use
the term mobile hosts to refer to both scenarios, as distinct from stationary hosts that never move.

With the increasing need to stay connected from virtually anywhere in the world, mobile hosts introduce
a challenge in routing: how to route packets to a mobile host, which can be located anywhere. To
address this, we explore a model where hosts have a permanent home location and home address
that never changes. The routing goal is to enable sending packets to mobile hosts using their fixed
home addresses while efficiently reaching them wherever they may be.

2- Challenges of Routing with Mobile Hosts

Dynamic Nature of Mobile Hosts: One approach to solving the routing problem would be to
recompute routes as the mobile host moves, causing changes in network topology. However, as
the number of mobile hosts grows, this approach leads to constant route recalculations, making it
inefficient.
Alternative Models: Another model would involve providing mobility above the network layer,
where mobile hosts acquire new network addresses when they change locations. In this model,
there is no association between the old and new addresses, and the network is unaware that they
belong to the same device. This model limits functionality:
Hosts can't receive incoming packets (e.g., for an incoming call) without using higher-layer
location services (e.g., re-signing into services like Skype).
Existing connections can’t be maintained during movement; new connections must be
initiated.
Network-layer mobility is useful to fix these problems

3- Network-Layer Mobility for Routing

The basic idea used for mobile routing in Internet and cellular networks involves a home agent. The
mobile host notifies this agent about its current location. The home agent then forwards packets so they
reach the mobile host, wherever it is.

34 / 40
Mobile Routing Process:

1. Registration with Home Agent:

The mobile host, now in a new location (e.g., San Diego), acquires a care of address (a
temporary local address). It registers this address with the home agent by sending a control
message (registration message).
2. Data Packet Routing:
A sender in Seattle sends a packet to the mobile host using its permanent home address. The
packet is routed to the home location in New York, where the home agent intercepts it because
the mobile host is not at home.
3. Tunneling:
The home agent encapsulates the data packet with a new header and sends it to the care of
address (using tunneling). This process ensures that the packet reaches the mobile host.
4. Packet Arrival:
Once the packet reaches the care of address, the mobile host unwraps it and retrieves the data.
The mobile host then responds directly to the sender.
5. Subsequent Communication:
For further communication, packets can bypass the home location entirely by being tunneled
directly to the care of address, ensuring faster communication.

Important Concepts:

Triangle Routing: This routing model is referred to as triangle routing, as the packets may take
a longer, indirect path (from Seattle → New York → San Diego) if the remote location is far from
the home location.
35 / 40
 Dynamic Routing: After the initial interaction, subsequent packets are routed directly to the
mobile host’s care of address, ensuring faster communication.

4- Security Considerations
When a mobile host changes its location, the home agent must verify the authenticity of the registration
message to prevent unauthorized users from hijacking the mobile host’s packets. Cryptographic
protocols ensure the validity of such messages.

5- Mobile Routing Variations

Foreign Agent: In some schemes, a foreign agent (located at the mobile host’s new location) is
used instead of or alongside the home agent. This foreign agent performs similar tasks, managing
the mobile host’s location.
Mobile Hosts as Foreign Agents: In more recent models, mobile hosts can act as their own
foreign agents, eliminating the need for a separate foreign agent.
Mobile Networks: Extensions of the basic mobile routing scheme support mobile networks, such
as networks in vehicles (e.g., planes), where the mobile host does not need to perform specific
actions.

6- Summary
In mobile routing, the home agent plays a central role in tracking the mobile host’s location and
forwarding packets to its current address. This approach allows packets to be sent to the mobile host’s
permanent home address while routing them to the correct current location. This method prevents the
need for constant route recalculations and ensures that mobile hosts can stay connected even while
moving across different networks.

11. Routing in Ad Hoc Networks

1- Introduction
Ad hoc networks (or MANETs, Mobile Ad hoc Networks) are formed by mobile nodes that communicate
wirelessly and act as both hosts and routers. These networks are dynamic, meaning the topology can
change frequently as nodes move or join/leave the network.

Key Challenges of Ad Hoc Networks:

1. Topology Changes: The network topology can change at any time due to mobility.
2. Dynamic Routes: Routes may become invalid or change frequently.
3. Limited Resources: Ad hoc nodes have limited bandwidth and battery life.
36 / 40
Example Use Cases:

Emergency workers at a disaster site.

Military vehicles on a battlefield.
Ships at sea.
Gathering of people in areas lacking infrastructure.

Routing in Ad Hoc Networks

Routing in such networks is more complex than traditional fixed networks due to the dynamic nature of
the topology. There are various algorithms designed for ad hoc networks, one of the most popular being
AODV (Ad hoc On-demand Distance Vector).

2- AODV Routing Protocol

AODV is a distance vector-based routing algorithm designed for mobile networks. It discovers routes
on-demand, i.e., only when data needs to be sent.

Route Discovery Process:

1- Route Request (RREQ) Process:

Node A sends a Route Request (RREQ) packet to locate Node I.

The request is broadcasted using flooding. This means the packet is passed through all
neighboring nodes, which then rebroadcast it.
37 / 40
 Each node that receives the RREQ rebroadcasts it to its neighbors, expanding the request's
reach.

2- Flooding and Sequence Number:

The transmission from A reaches B and D (Figure 5-20(a)).

The rebroadcasting continues to nodes F, G, and C (Figure 5-20(c)), and finally to H, E, and I
(Figure 5-20(d)).
Sequence numbers are used to weed out duplicate packets during the flooding process.
For example, Node D discards the transmission from B in Figure 5-20(c) because it had
already received and forwarded the request.

3- Route Reply (RREP) Process:

Once the RREQ reaches the destination node I, it constructs a Route Reply (RREP) packet.
The RREP is unicast back to the source (A) along the reverse path taken by the RREQ.

4- Intermediate Nodes' Role:

Each intermediate node, like B, D, and G, remembers the node from which it received the
request. This memory allows the RREP to follow the reverse route correctly.
Each intermediate node also increments a hop count as the RREP is forwarded. This hop count
indicates the distance (in terms of hops) from the destination.

5- Route Selection:

As the RREP travels back toward the source, intermediate nodes, such as G and D, use the best
route they have heard (based on the hop count) to update their routing tables.

6- New Route Creation:

Finally, when the RREP reaches Node A, a new route (denoted ADGI) is created, which now
allows Node A to communicate with Node I via nodes D, G, and I.

3- Route Maintenance
The network topology can change dynamically due to node mobility. To ensure route validity:

1. Hello Messages: Nodes periodically send Hello messages to neighbors. If a node does not
receive a response, it knows that the neighbor is unreachable.
2. Route Purging: If a node detects that a neighbor is unreachable, it purges any routes involving
that neighbor. This information is propagated throughout the network to ensure consistency.

38 / 40
 3. Sequence Numbers: To avoid issues like count-to-infinity or slow convergence during topology
changes, a sequence number is used to ensure that newer routes are preferred over old ones.
Nodes ask for routes with higher sequence numbers to ensure they are using up-to-date paths.
4. Efficient Resource Use: AODV minimizes bandwidth usage by only maintaining routes that are in
use. Other routes are discarded after a timeout.

4- Route Discovery Example

Consider the network in Figure 5-20:

1. Node A wants to send data to Node I but doesn't have a route.

2. Node A sends an RREQ to its neighbors (B, D).
3. Nodes B, D, C, F, G, E, H rebroadcast the RREQ.
4. Node I receives the RREQ and sends an RREP back via the reverse path (D → G → A).
5. The route from A to I is established as A → D → G → I.

5- Optimizations
To reduce overhead, the scope of broadcasts is limited using the Time to Live (TTL) field in the IP
packet. The TTL is incremented in successive attempts, ensuring the search starts locally and gradually
expands.

If multiple nodes need the same route (e.g., B also needs to reach I), they share the discovered route,
preventing redundant broadcasts.

6- Other Ad Hoc Routing Protocols

1. DSR (Dynamic Source Routing): Similar to AODV, but it uses source routing, where the sender
knows the entire route to the destination.
2. GPSR (Greedy Perimeter Stateless Routing): A geographic routing protocol where nodes
forward packets by heading in the general direction of the destination based on their geographic
position.

7- Conclusion

39 / 40
Routing in ad hoc networks is challenging due to dynamic topology and resource constraints. AODV is
one of the widely-used routing protocols due to its on-demand nature, sequence numbering, and
minimal maintenance overhead. However, the choice of protocol depends on the specific application,
and other protocols like DSR and GPSR are also popular for different types of networks.

40 / 40