5.
2 Routing Algorithm
#computernetwork #chapter5
Routing Algorithm
The network layer's primary function is to route packets from the source to the destination, often
requiring multiple hops. Routing decisions depend on algorithms that choose paths and
maintain routing tables. In datagram networks, routing is determined for each packet
individually, while in virtual-circuit networks, routes are set during connection setup and used
throughout the session.
Routing involves two key processes: routing (deciding routes and updating routing tables) and
forwarding (sending packets along the chosen routes). Effective routing algorithms must
ensure correctness, simplicity, robustness, stability, fairness, and efficiency. Robustness
is crucial, as networks must operate continuously despite hardware and software failures.
Stability ensures that routing algorithms converge to a fixed state quickly to avoid disruptions.
Fairness and efficiency often conflict. For example, maximizing total traffic flow may require
limiting certain connections, which can seem unfair to those connections. Networks aim to
balance these by optimizing metrics such as minimizing delay or the number of hops per
packet.
Routing algorithms are categorized into nonadaptive (static) and adaptive (dynamic) types.
Nonadaptive algorithms use predefined routes, suitable for stable scenarios, but do not respond
to changes. Adaptive algorithms adjust to changes in topology or traffic, using metrics like
distance, hops, or transit time. Dynamic algorithms differ in how and when they gather
information and update routes.
In summary, routing in the network layer involves complex trade-offs between efficiency,
fairness, and adaptability to ensure smooth and reliable data transmission.
Types of Routing Algorithm
The Optimality Principle: A theoretical basis for routing, stating that if a router is on the
optimal path between two other routers, it should be part of the route for packets between
them.
Shortest Path Routing: This algorithm finds the shortest path between two nodes in a
network. Dijkstra’s algorithm is a well-known example used to compute the shortest path.
Flooding: In this method, every incoming packet is sent out on every outgoing line except
the one it arrived on. This ensures that the packet reaches its destination but can lead to
excessive traffic.
Distance Vector Routing: Each router maintains a table (vector) of the minimum distance
to every other router. Routers periodically share their tables with their neighbors to update
their own tables.
Link State Routing: Each router has knowledge of the entire network topology. Routers
send information about their neighbors to every other router in the network, allowing each
router to build a complete map of the network
Hierarchical Routing: This method divides the network into regions. Routers within a
region know the details of their region but only know the path to reach other regions,
reducing the size of routing tables.
Broadcast Routing: This technique involves sending a packet to all nodes in the network.
It can be implemented using methods like flooding or spanning tree algorithms.
Multicast Routing: This method is used to send a packet to a specific group of hosts. It
involves creating a multicast tree that spans all the members of the group.
Routing for Mobile Hosts: Addresses challenges of routing when devices frequently
change their network location, such as in mobile IP.
Routing in Ad Hoc Networks: Specialized routing for networks with no fixed
infrastructure, relying on dynamic, decentralized algorithms to handle frequently changing
topologies. Networks of nodes that just happen to be near each other are called ad hoc
networks or MANETs (Mobile Ad hoc NETworks)
The Optimality Principle
The Optimality Principle means that the best route from one router to another is made up of
smaller best routes along the way. For example, if router JJ is the best stop between router II
and router KK, then the path from JJ to KK is also the best.
This idea helps create a sink tree, which is like a map showing the shortest, most efficient
paths from all routers to one specific destination. It’s loop-free and ensures packets reach their
destination quickly. However, in real networks, changes like broken links can make it tricky to
always follow the sink tree perfectly.
Shortest Path Routing
Graph Representation: Each router is a node, and each link between routers is an edge.
The edges have weights, representing the cost (distance, time, bandwidth, etc.) to
traverse them.
Shortest Path Concept: The shortest path depends on the chosen metric (e.g., fewest
hops, least distance, or least delay). The algorithm can adapt to different criteria.
Dijkstra's Algorithm:
Start at the source node. Label it with a distance of 0 and all other nodes with
infinity.
Mark the source as permanent and examine its neighbors. Update their distances if
a shorter path is found via the source.
Among the nodes with tentative labels, pick the one with the smallest value, mark it
permanent, and repeat the process for its neighbors.
Continue until all nodes are permanent, meaning the shortest paths are established.
Why It Works:
By always picking the smallest tentative label, the algorithm ensures that the shortest
path to a node is finalized before moving on.
If a shorter path existed, the algorithm would detect it earlier during the process.
Example: In a network, if A → B → E is shorter than A → X → Y → E, Dijkstra's method
will prioritize the shorter path.
Output: Once completed, it provides the shortest path from the source to all other nodes.
This is often visualized as a tree of optimal paths.
Flooding
In this method, every incoming packet is sent out on every outgoing line except the one it
arrived on. This ensures that the packet reaches its destination but can lead to excessive traffic.
Distance Vector Routing
The distance vector routing algorithm is a method used in computer networks to calculate
the shortest paths between routers dynamically. Each router maintains a routing table with the
best-known distances to each destination and the corresponding outgoing link. These tables
are updated through periodic exchanges of information with neighboring routers.
Key Points:
1. Algorithm Basics:
Each router knows the distance to its neighbors.
It calculates the total delay to each destination via every neighbor and updates its
table based on the shortest path.
2. Alternate Names:
Known as the Distributed Bellman-Ford algorithm.
Used in protocols like RIP (Routing Information Protocol).
3. Process:
Routers exchange delay information periodically.
They compute the shortest paths based on neighbors' updates.
4. Count-to-Infinity Problem:
The Count-to-Infinity Problem in distance vector routing arises because routers depend
on their neighbors' information to update routes. If a link goes down (bad news), incorrect
routing information is propagated in a loop, causing routers to incrementally increase their
distance metric to "infinity." This process highlights the slow convergence of distance
vector protocols.
How It Happens (Aligned with the Figure):
1. Initially, all routers know accurate distances to AAA: B=1,C=2,D=3,B = 1, C = 2, D =
3,B=1,C=2,D=3, and E=4E = 4E=4.
2. Suddenly, AAA becomes unreachable (or the link between AAA and BBB is cut).
Exchange 1:
BBB detects the loss of connection to AAA, but CCC advertises a path to AAA with a
distance of 222 (though CCC's path actually loops back through BBB).
BBB updates its route to AAA as B=3B = 3B=3, assuming CCC's path is valid.
Exchange 2:
CCC, now seeing BBB's updated distance of 333, updates its own route to C=4C =
4C=4.
DDD and EEE retain their original distances for now.
Exchange 3:
DDD, observing C=4C = 4C=4, updates its distance to D=5D = 5D=5.
EEE remains unchanged.
Exchange 4:
EEE sees D=5D = 5D=5 and updates its distance to E=6E = 6E=6.
3. This process continues, with routers incrementally increasing their distances to AAA until
they reach "infinity" (a predefined maximum hop count).
Why It Happens:
Routers blindly trust their neighbors' advertisements without knowing if the advertised paths
loop back through them. In this case:
BBB trusts CCC,
CCC trusts BBB,
resulting in incorrect updates propagating through the network.
Result:
The problem demonstrates that bad news travels slowly in distance vector routing. Routers
take several exchanges to converge, depending on the value set for "infinity."
This issue is illustrated in Figure 5-10(b), where each row shows the gradual increase in
distances at every exchange. Solutions like split horizon or poisoned reverse attempt to
mitigate this, but they cannot fully resolve the problem
- Good news (shorter paths) propagates quickly.
- Bad news (e.g., link failures) propagates slowly due to a problem where
routers may loop incorrect paths indefinitely.
- Solutions like "split horizon" and "poisoned reverse" exist but are not
fully effective.
This simplicity makes distance vector routing useful but highlights its limitations for large-scale,
dynamic networks.
Link State Routing
Each router has knowledge of the entire network topology. Routers send information about their
neighbors to every other router in the network, allowing each router to build a complete map of
the network.
1. Transition from Distance Vector Routing to Link State
Routing
Reason for Change:
Distance vector routing was replaced by link state routing in ARPANET in 1979 due to
issues like slow convergence and the count-to-infinity problem.
Replacement Algorithms:
Link state routing variants, such as IS-IS and OSPF, are now widely used in large
networks and the Internet.
2. Five Key Steps in Link State Routing
1. Discovering Neighbors:
Routers send HELLO packets to identify direct neighbors.
For broadcast networks (e.g., Ethernet), a designated router acts as a representative
of the LAN node in the topology.
2. Setting Link Costs:
Costs are based on metrics like bandwidth (e.g., inverse proportionality) or delay
(measured using ECHO packets).
Shorter, faster links are prioritized.
3. Building Link State Packets (LSPs):
LSPs contain the router's ID, sequence number, age, neighbors, and link costs.
They are built periodically or in response to network changes.
4. Distributing LSPs:
Flooding mechanism:
LSPs are sent to all routers with sequence numbers to track updates and prevent
duplication.
Age field ensures outdated packets are discarded.
Acknowledgment flags ensure reliable delivery.
Refinements like holding areas prevent redundant updates during rapid topology
changes.
5. Computing Shortest Paths:
Using the Dijkstra algorithm, each router computes the shortest path to every other
router based on the collected LSPs.
The routing tables are updated with optimal paths.
3. Advantages of Link State Routing
Faster Convergence:
The flooding mechanism ensures that topology changes are propagated quickly across the
network.
Avoidance of Routing Loops:
Consistent topology data allows all routers to calculate compatible routing tables.
Flexibility in Cost Metrics:
Customizable cost metrics enable efficient routing in diverse network environments.
4. Challenges and Solutions
Memory and Computation Overhead:
Link state routing requires significant memory to store the entire topology and greater
computational power to run the Dijkstra algorithm.
Sequence Number Issues:
Wrapping around of sequence numbers or crashes leading to resets can cause
problems, but using a 32-bit sequence number and the age field mitigates these
risks.
Flooding Redundancy:
Holding areas for packets and acknowledgment mechanisms improve efficiency and
reliability.
5. Practical Protocols
IS-IS (Intermediate System to Intermediate System):
Handles multiple protocols, making it suitable for multiprotocol networks.
OSPF (Open Shortest Path First):
Focuses on IP and introduces innovations like designated routers, path splitting, and
multiple metrics.
Although similar, IS-IS supports multiprotocol environments, while OSPF is more IP-centric,
making both protocols suitable for specific network needs.
Link state routing’s robustness and scalability make it the backbone of modern large-scale
networks, despite its computational and memory demands.
