Link State Routing

Question 1

What is Link State Routing (LSR)?

Answer 1

LSR, also known as Shortest Path First (SPF) forwarding, is a routing method where routers maintain a complete view of the network topology using link-state packets (LSPs) and calculate shortest paths using Dijkstra’s Algorithm.

Question 2

What triggers the generation of Link State Packets (LSPs)?

Answer 2

LSPs are generated by:

Periodic updates.
Changes in network topology, such as:
New neighbors or links.
Changes in link costs.
Link or node failures.

Question 3

What information is contained in an LSP?

Answer 3

An LSP contains:

A list of neighbors.
The cost to each neighbor.

Question 4

How are LSPs distributed in the network?

Answer 4

Using the flooding method, where routers send LSPs to all neighbors (except the source).

Improved Flooding reduces redundancy by discarding duplicate LSPs and only forwarding updated ones.

Question 5

What are the steps in Dijkstra’s Algorithm for LSR?

Answer 5

Initialize the root router (cost = 0).
Add neighbors to a tentative list (TENT) with costs.
Move the neighbor with the lowest cost to the confirmed list (PATH).
Update TENT with paths from the newly confirmed router.
Repeat until all nodes are in PATH.
Outputs: PATH (shortest paths) and the forwarding table.

Question 6

What happens when there are topology changes in LSR?

Answer 6

Events like adding/removing routers or changes in link cost trigger recalculation of PATH and forwarding tables using Dijkstra’s Algorithm.
Example: A new link with a lower cost prompts a route update.

Question 7

What is Open Shortest Path First (OSPF)?

Answer 7

A popular link-state routing protocol with features like:

Dividing networks into areas for scalability.
Load balancing and multi-level routing.
Key Messages:
Hello (tests reachability).
LSA (shares topology information).
LSR (queries link status).
LSU (responds with updates).
Acknowledgment (confirms LSU receipt).

Question 8

How does OSPF handle multicast routing?

Answer 8

OSPF uses Dijkstra’s tree with the sender as the root and forwards messages to all child nodes in the tree.

Question 9

What techniques are used for load balancing in LSR?

Answer 9

1.Load Splitting:
*Multiple routes are maintained per destination.
*Routes are chosen via:
—–Round-robin.
—–Random selection.
Congestion-based metrics.
2.Variable Link Cost:
*Link costs adjust dynamically based on traffic, enabling automatic load balancing.

Question 10

How does LSR compare to DVR (Distance Vector Routing)?

Answer 10

Bandwidth Usage: Dependent on network topology. Both can grow bandwidth-intensive in large networks.
Computation:

Challenges: High communication overhead in large networks, mitigated by multi-level routing.