Routing Algorithms in Computer Networks: Distance Vector, Link State & Shortest Path

COMPUTER NETWORKS • CHAPTER 22

Routing Algorithms in Computer Networks: Distance Vector, Link State & Shortest Path

Imagine you want to travel from one city to another.

Usually there is not only one road. There may be many possible routes. One route may be shorter, another may have less traffic, and another may pass through fewer cities.

Routers face almost the same problem. They receive packets and must decide: Which path should this packet follow to reach the destination?

Routing algorithms help routers make this decision.

Distance Vector Learn routes from neighbours

Link State Build network topology knowledge

Dijkstra Shortest Path First

Bellman-Ford Distance Vector foundation

Direct Answer

A routing algorithm is a method used by routers to determine suitable paths for sending packets from a source network to a destination network.

Distance Vector routing learns destination distances from neighbouring routers and is based on the Bellman-Ford idea.

Link State routing distributes information about local links so routers can build a network topology database and run a shortest-path algorithm such as Dijkstra's algorithm.

Complete Chapter Index Concept + Algorithms + Numerical + Exam

1. What Is Routing?
2. What Is a Routing Algorithm?
3. Why Routing Algorithms Are Needed
4. Properties of a Good Routing Algorithm
5. Routing Metrics
6. Routing Algorithm Classification
7. Static Routing
8. Dynamic Routing
9. Adaptive vs Non-Adaptive
10. Shortest Path Routing
11. Network as a Graph
12. Dijkstra Algorithm
13. Dijkstra Solved Example
14. Final Routing Table
15. Distance Vector Routing
16. How Distance Vector Works
17. Bellman-Ford Equation
18. Distance Vector Example
19. Routing Updates
20. Count-to-Infinity Problem
21. Split Horizon
22. Route Poisoning
23. Poison Reverse
24. Hold-Down Concept
25. RIP
26. Link State Routing
27. How Link State Works
28. Neighbour Discovery
29. Link Cost Measurement
30. Link State Advertisement
31. Flooding
32. Link State Database
33. SPF Calculation
34. OSPF
35. Distance Vector vs Link State
36. Advantages & Limitations
37. Routing Convergence
38. Routing Loops
39. Hierarchical Routing
40. Solved Numericals
41. Common Exam Mistakes
42. Important Questions With Answers
43. MCQs With Answers
44. FAQs

What Is Routing?

Routing is the process of selecting a path through a network so that a packet can travel from its source toward its destination.

Suppose Router A wants to send a packet to a network connected behind Router C.

Router A Source Side

Cost 2

Router B Intermediate

Cost 3

Router C Destination Side

The router needs information that tells it which next hop should be used.

Simple Definition: Routing means finding or selecting the path that packets should follow through interconnected networks.

What Is a Routing Algorithm?

A routing algorithm is the logic used to calculate routes.

It helps a router answer questions such as:

• Which destination networks are reachable?
• Which next hop should be used?
• Which path has the lowest cost?
• What should happen if a link fails?
• When should an old route be replaced?

Easy Memory: Routing algorithm decides the route. Routing table stores the result. Forwarding uses that result.

Why Do We Need Routing Algorithms?

A small network may have only one path.

But large networks can contain thousands of routers and many possible routes.

A router cannot simply guess where a packet should go.

It needs a systematic method to:

• Learn the network
• Find reachable destinations
• Select suitable paths
• React to failures
• Update the routing table

Properties of a Good Routing Algorithm

1

Correctness

The algorithm should calculate valid routes toward reachable destinations.

2

Simplicity

Routing logic should not create unnecessary complexity.

3

Robustness

It should continue working when links or routers change or fail.

4

Stability

Route calculations should eventually settle instead of constantly changing without reason.

5

Efficiency

Routing should avoid excessive memory, CPU and bandwidth overhead.

6

Adaptability

Dynamic algorithms should adjust when topology or network conditions change.

Routing Metrics

A routing algorithm needs some way to compare paths.

The value used to compare routes is called a metric.

Common routing metrics include:

• Hop count
• Bandwidth-related cost
• Delay
• Link cost
• Reliability
• Administrative policy

Important: The word “shortest” does not always mean physically shortest in kilometres. It normally means the route having the smallest value according to the selected routing metric.

Classification of Routing Algorithms

Non-Adaptive Routing

Routes do not automatically change according to current network conditions.

Static routing is the common example.

Adaptive Routing

Routes can change when routers learn new topology or reachability information.

Distance Vector and Link State algorithms are important examples.

Static Routing

In static routing, routes are manually configured.

The router does not automatically calculate a new route simply because the network topology changes.

Advantages

• Simple for very small networks
• No routing update traffic
• Predictable route configuration

Limitations

• Difficult to manage in large networks
• Manual changes may be required after failures
• Poor scalability for frequently changing networks

Dynamic Routing

Dynamic routing allows routers to exchange or calculate routing information automatically.

If a route fails, the routers may calculate an alternative path.

Examples of routing protocols using dynamic techniques include:

• RIP
• OSPF
• IS-IS
• BGP

Adaptive vs Non-Adaptive Routing

Point	Adaptive Routing	Non-Adaptive Routing
Route Change	Can change according to new network information	Does not automatically adapt
Updates	Routing information is learned dynamically	Usually configured manually
Failure Handling	Can calculate alternative routes	Administrator may need to change configuration
Example	Distance Vector, Link State	Static routing

Shortest Path Routing

One common routing idea is to represent the network as a graph.

In this graph:

• Routers are represented as nodes.
• Links are represented as edges.
• Each link may have a cost.

The goal is to find a path whose total cost is minimum.

Path Cost

Total Cost = Sum of Costs of All Links in the Path

Representing a Network as a Graph

Consider the following link costs:

Example Network

A Source

A-B = 4

B

A-C = 2

C

C-B = 1

D

B-D = 5

E Destination

We will use this type of cost information to understand shortest-path calculation.

Dijkstra's Shortest Path Algorithm

Dijkstra's algorithm finds shortest paths from one source node to other nodes when link costs are non-negative.

Link State routing protocols commonly use a Shortest Path First calculation based on Dijkstra's algorithm.

Basic Idea

Give the source node cost 0.

Give other nodes an initial cost of infinity.

Select the unvisited node having the smallest known cost.

Check whether going through that node gives a cheaper path to its neighbours.

Update the cost if a better route is found.

Mark the selected node permanent or visited.

Continue until required shortest paths are known.

Dijkstra Algorithm Solved Example

Consider these links:

A-B = 4

A-C = 2

C-B = 1

B-D = 5

C-D = 8

B-E = 7

D-E = 2

C-E = 10

Source node is:

A

Dijkstra Calculation from A

0

Start with A = 0. All other nodes are initially ∞.

1

From A: B = 4 and C = 2.

2

C has smaller cost 2, so select C.

3

Through C, cost to B = 2 + 1 = 3. This is better than direct cost 4, so B becomes 3.

4

Through C, D = 2 + 8 = 10 and E = 2 + 10 = 12.

5

Select B with cost 3. Through B, D = 3 + 5 = 8, which improves D from 10 to 8.

6

Through B, E = 3 + 7 = 10, improving E from 12 to 10.

7

Select D with cost 8. Through D, E = 8 + 2 = 10. The cost remains 10.

8

Final shortest costs from A: C = 2, B = 3, D = 8 and E = 10.

Shortest Paths

A

→

C

→

B

B

→

D

B

→

E

Routing Table Produced from the Shortest Paths

From router A, the first hop toward B, D and E is C.

Destination

Cost

Next Hop

C

2

C

B

3

C

D

8

C

E

10

C

Distance Vector Routing

Distance Vector routing follows a very simple idea.

A router does not need the complete network map.

Instead, it knows:

• How far a destination appears to be
• Which neighbour should be used to reach it

Distance Vector = Destination Distance + Direction through Neighbour

Routers exchange routing information with neighbouring routers.

How Distance Vector Routing Works

Each router knows the cost to its directly connected neighbours.

It creates a distance vector containing its known destinations and costs.

It sends routing information to neighbouring routers.

A neighbour receives the vector.

The neighbour adds its own cost to reach the advertising router.

It compares the new route with the route already stored.

If the new route is better, the routing table is updated.

Bellman-Ford Equation in Distance Vector Routing

The basic Distance Vector idea can be written as:

Dₓ(y) = minᵥ { c(x,v) + Dᵥ(y) }

Where:

• Dₓ(y) = router x's estimated cost to destination y
• c(x,v) = cost from router x to neighbour v
• Dᵥ(y) = neighbour v's advertised cost to destination y

Meaning in simple words: Ask every neighbour: “How much does it cost you to reach the destination?” Then add the cost of reaching that neighbour. Choose the smallest answer.

Distance Vector Routing Example

Suppose:

A → B = 2

B → C = 3

A → C directly = 8

Router A has two choices to reach C.

Direct Route

A → C = 8

Route Through B

A → B + B → C

= 2 + 3

= 5

Therefore Router A selects:

A → B → C
Total Cost = 5

Example Distance Vectors

A

A=0, B=2, C=5

B

A=2, B=0, C=3

C

A=5, B=3, C=0

Distance Vector Routing Updates

Distance Vector protocols may send routing information to neighbours periodically.

They may also send triggered updates when important route changes occur, depending on the routing protocol.

Router A

Sends known destination costs to neighbouring router B.

Router B

Compares A's information with its current routing table.

Update

B changes a route if the newly calculated path is better or if route state changes require an update.

Count-to-Infinity Problem

Distance Vector routing can suffer from slow convergence after some failures.

The classic problem is called:

Count-to-Infinity

Suppose router A reaches destination X through B.

If the route to X fails, incorrect information may circulate between routers.

One router may believe another router still has a valid path.

Start

A thinks X is reachable through B.

1

Route fails, but incorrect old information remains.

2

Neighbours may advertise progressively larger route costs.

3

Metric continues increasing until the protocol's infinity value is reached.

In RIP, hop count 16 is treated as unreachable. Therefore RIP's practical infinity value is 16.

Split Horizon

Split Horizon is used to reduce routing-loop problems.

The basic idea is:

Do not advertise a route back through the same interface from which that route was learned.

Example:

If Router A learned route X from Router B, A should not tell B that X is reachable through A.

Route Poisoning

Route poisoning means advertising a failed route using an infinite or unreachable metric.

This tells neighbours:

“Do not use this route.”

Poison Reverse

Poison Reverse is related to Split Horizon.

Instead of simply not advertising the route back, a router advertises it back with an infinite metric.

Easy Difference: Split Horizon → Do not send the learned route back. Poison Reverse → Send it back as unreachable.

Hold-Down Concept

Some Distance Vector systems use hold-down behaviour to reduce instability after route failures.

For a period of time, suspicious updates about a failed destination may be ignored or handled carefully.

The aim is to give the network time to remove old information.

RIP — Distance Vector Routing Protocol Example

RIP stands for:

Routing Information Protocol

RIP is a well-known Distance Vector routing protocol.

Important RIP Points

• Uses hop count as its basic metric.
• Lower hop count is preferred.
• Maximum usable hop count is 15.
• Hop count 16 means unreachable.
• It is mainly suitable for comparatively small networks.

Link State Routing

Link State routing uses a different idea.

Instead of telling neighbours only a list of destination distances, each router describes its own local links.

That information is distributed through the routing area or domain.

Routers build a common topology database and calculate shortest paths.

Easy Memory: Distance Vector asks neighbours for routes. Link State learns the network map.

How Link State Routing Works

Discover neighbouring routers.

Determine the cost of links to those neighbours.

Create a Link State Advertisement or similar topology information.

Flood that information through the routing domain.

Build the Link State Database.

Run the Shortest Path First algorithm.

Install the resulting routes in the routing table.

Neighbour Discovery

A Link State router must first know which routers are directly reachable on its links.

Routing protocols use neighbour discovery or hello-type mechanisms to identify neighbouring routers.

This creates the local view from which topology information is built.

Link Cost Measurement

Each link is given a cost.

The exact way the cost is calculated depends on the routing protocol.

A lower cost generally represents a more preferred path.

A routing protocol may derive cost from bandwidth or other configured values. The exact metric is protocol-specific.

Link State Advertisement

A router creates information describing the state of its links.

This may include:

• Router identity
• Neighbour information
• Connected links
• Link cost
• Sequence information

The information is then distributed to other routers in the appropriate routing scope.

Flooding in Link State Routing

Flooding means distributing Link State information through the network so that relevant routers receive it.

A router receiving new Link State information forwards it appropriately to other neighbours.

Mechanisms such as sequence numbers and ageing help routers distinguish fresh information from old information.

Link State Database — LSDB

Routers collect the flooded Link State information into a topology database.

This is commonly called:

LSDB — Link State Database

Routers in the same Link State routing scope aim to maintain a consistent view of that topology.

Example LSDB View

A

B:4, C:2

B

A:4, C:1, D:5

C

A:2, B:1, D:8

D

B:5, C:8

Shortest Path First — SPF Calculation

After building the LSDB, each router treats itself as the root of the network graph.

It then runs a shortest-path algorithm.

The result is a shortest-path tree.

LSDB → Dijkstra/SPF → Shortest Path Tree → Routing Table

OSPF — Link State Routing Protocol Example

OSPF stands for:

Open Shortest Path First

OSPF is a widely used Link State Interior Gateway Protocol.

Main Ideas

• Discovers neighbours.
• Exchanges Link State information.
• Builds an LSDB.
• Uses an SPF calculation.
• Supports hierarchical area design.
• Can react to topology changes more quickly than simple traditional Distance Vector designs.

Distance Vector vs Link State Routing

Point	Distance Vector	Link State
Knowledge	Knows destination distance through neighbours	Builds a topology database
Information Shared	Routing distance information	State and cost of local links
Who Receives Information?	Mainly neighbours	Topology information is flooded through the routing scope
Algorithm Idea	Bellman-Ford	Dijkstra / SPF
Network View	No complete topology map required	Maintains topology database
Convergence	Can be slower in classic designs	Generally faster after topology information is synchronized
Loop Problem	More vulnerable to classic routing loops and count-to-infinity	Uses topology information and sequence mechanisms, reducing classic DV problems
Resource Requirement	Usually simpler	Requires more topology information and computation
Example	RIP	OSPF

Advantages and Limitations

Distance Vector

Advantages

• Simple concept
• Lower topology knowledge requirement
• Suitable for smaller environments

Limitations

• Routing loops can occur
• Count-to-infinity problem
• Traditional convergence can be slow

Link State

Advantages

• Detailed network topology knowledge
• Fast reaction to topology changes in well-designed implementations
• Efficient shortest-path calculation
• Suitable for larger routed networks

Limitations

• More memory required
• More CPU needed for SPF calculations
• More complex protocol operation

What Is Routing Convergence?

Convergence means routers have processed a topology change and their routing information has reached a stable, consistent state.

For example:

A link fails.

Routers detect the failure.

New routing information is exchanged or flooded.

Routes are recalculated.

Routers begin using the new stable routes.

Fast convergence is desirable because packets may otherwise be lost, delayed or routed incorrectly during topology changes.

Routing Loops

A routing loop occurs when routers repeatedly forward packets in a circle instead of toward the destination.

Example:

Router A → Router B → Router C → Router A → Router B ...

Routing loops waste:

• Bandwidth
• Router processing
• Buffer space

IP TTL or IPv6 Hop Limit eventually prevents an individual packet from looping forever, but routing protocols should still try to prevent the incorrect route itself.

Hierarchical Routing

A very large network becomes difficult to manage if every router must process every detail of the entire network.

Hierarchical routing divides a large routing system into smaller logical areas, regions or administrative domains.

Benefits

• Reduces routing information
• Improves scalability
• Allows route summarization
• Limits some topology information to smaller regions

OSPF areas are a common example of hierarchical routing inside an autonomous system.

Routing Protocol Examples

RIP Distance Vector protocol using hop count.

OSPF Link State protocol using Shortest Path First calculation.

IS-IS Link State routing protocol used in many large networks.

BGP Path Vector protocol used for routing between autonomous systems.

Important: BGP is not a normal Distance Vector or Link State protocol. It is generally classified as a Path Vector routing protocol.

Solved Routing Numericals

Numerical 1: Find Path Cost

Suppose:

A → B = 3

B → C = 4

C → D = 2

Find the cost of:

A → B → C → D

= 3 + 4 + 2

= 9

Answer = 9

Numerical 2: Choose the Shortest Route

Router A has two possible paths to D.

Path 1: A-B-D = 4 + 5 = 9

Path 2: A-C-D = 2 + 3 = 5

Therefore:

Shortest Path = A → C → D
Cost = 5

Numerical 3: Bellman-Ford Update

Router A wants to reach destination X.

A has:

Cost A → B = 2

B advertises distance to X = 5

Cost A → C = 4

C advertises distance to X = 2

Through B:

2 + 5 = 7

Through C:

4 + 2 = 6

So Router A selects:

Next Hop = C
Distance to X = 6

Numerical 4: RIP Reachability

A RIP route reaches a destination in 15 hops.

15 hops = reachable.

If the metric becomes 16:

16 hops = unreachable in RIP.

Numerical 5: Dijkstra Shortest Route

Given:

S-A = 2

S-B = 6

A-B = 1

B-D = 2

A-D = 7

Possible route:

S → A → B → D

= 2 + 1 + 2

= 5

Direct alternative through A:

S → A → D

= 2 + 7

= 9

Shortest Path = S → A → B → D
Cost = 5

Common Exam Mistakes

1. Routing and forwarding are the same.

Routing calculates or learns routes. Forwarding sends an individual packet using routing information.

2. Shortest path always means minimum physical distance.

Wrong. Shortest means minimum routing cost according to the selected metric.

3. Distance Vector routers always know the complete topology.

Wrong. Classical Distance Vector operation mainly depends on information learned from neighbours.

4. Link State routers only know their immediate neighbour's routing table.

Wrong. Link State routers build a topology database from flooded link-state information.

5. Dijkstra is the basic algorithm of Distance Vector routing.

Wrong. Distance Vector is based on the Bellman-Ford idea. Dijkstra is associated with Link State shortest-path calculation.

6. Count-to-infinity is mainly a Link State problem.

Wrong. It is a classic Distance Vector problem.

7. RIP supports unlimited hops.

Wrong. RIP treats 16 as unreachable.

8. Split Horizon advertises a learned route back normally.

Wrong. Split Horizon avoids advertising that route back through the interface from which it was learned.

9. Link State flooding means sending user data to every router.

Wrong. Flooding here refers to distributing routing topology information.

10. BGP is a Link State protocol.

Wrong. BGP is generally classified as a Path Vector routing protocol.

40 Important Routing Algorithm Questions With Answers

1. What is routing?

Routing is the process of selecting a path through a network so that packets can move toward their destination.

2. What is a routing algorithm?

A routing algorithm is the logic used by routers or routing protocols to calculate suitable paths to destination networks.

3. What is a routing metric?

A routing metric is a value used to compare possible routes, such as hop count, cost, delay or bandwidth-related cost.

4. What is shortest path routing?

Shortest path routing selects the route having the minimum total cost according to the routing metric being used.

5. How is a network represented for shortest path calculation?

The network is represented as a graph where routers are nodes, links are edges and link metrics are edge costs.

6. What is Dijkstra's algorithm?

Dijkstra's algorithm calculates the shortest paths from one source node to other nodes when link costs are non-negative.

7. Which routing approach commonly uses Dijkstra's algorithm?

Link State routing commonly uses Dijkstra's Shortest Path First calculation.

8. What is Distance Vector routing?

Distance Vector routing is a distributed routing approach in which routers learn destination distances from neighbouring routers and select lower-cost routes.

9. Which algorithmic idea is used in Distance Vector routing?

Distance Vector routing is based on the Bellman-Ford shortest-path principle.

10. What information does a Distance Vector router maintain?

It maintains destination reachability, estimated distance or metric and the next hop used to reach the destination.

11. Write the Bellman-Ford routing equation.

Dₓ(y) = min over neighbours v of [c(x,v) + Dᵥ(y)].

12. What does c(x,v) represent?

It represents the direct cost from router x to its neighbour v.

13. What is the count-to-infinity problem?

It is a Distance Vector problem where routers may repeatedly increase the metric to a failed destination because they continue receiving incorrect reachability information from one another.

14. What is Split Horizon?

Split Horizon prevents a router from advertising a learned route back through the same interface from which the route was learned.

15. What is route poisoning?

Route poisoning marks a failed route with an unreachable or infinite metric and advertises that information to neighbours.

16. What is Poison Reverse?

Poison Reverse advertises a route back toward the neighbour from which it was learned, but with an infinite metric so that neighbour will not use that route through the advertising router.

17. What is a hold-down mechanism?

It is a temporary period during which suspicious route updates after a failure are restricted so that unstable or old information is less likely to be accepted.

18. What is RIP?

RIP stands for Routing Information Protocol. It is a classic Distance Vector routing protocol using hop count as its metric.

19. What is the maximum usable hop count in RIP?

The maximum usable RIP hop count is 15.

20. What does hop count 16 mean in RIP?

A hop count of 16 means the destination is unreachable.

21. What is Link State routing?

Link State routing distributes information about local links so routers can build a topology database and independently calculate shortest paths.

22. What are the main steps in Link State routing?

Discover neighbours, determine link costs, create Link State information, flood it, build the LSDB, run SPF and install routes.

23. What is an LSDB?

LSDB means Link State Database. It stores topology information learned from Link State advertisements.

24. What is flooding in Link State routing?

Flooding is the controlled distribution of Link State information so relevant routers receive updated topology information.

25. What is SPF?

SPF means Shortest Path First. It calculates a shortest-path tree from the topology database.

26. What is OSPF?

OSPF stands for Open Shortest Path First. It is a Link State Interior Gateway Protocol that uses a Shortest Path First calculation.

27. Differentiate Distance Vector and Link State routing.

Distance Vector learns destination distances mainly through neighbours, while Link State distributes local link information, builds a topology database and calculates shortest paths from that topology.

28. Which generally converges faster: Distance Vector or Link State?

Link State protocols generally converge faster than traditional Distance Vector designs because topology changes are distributed and routers recalculate paths using the updated topology database.

29. What is routing convergence?

Convergence is the process of routers reaching a stable and consistent routing state after a topology change.

30. What is a routing loop?

A routing loop occurs when packets repeatedly circulate between routers because of incorrect or inconsistent routing information.

31. What prevents an IP packet from looping forever?

IPv4 TTL or IPv6 Hop Limit eventually reaches zero, causing the packet to be discarded.

32. What is hierarchical routing?

Hierarchical routing divides a large routing system into smaller logical regions or areas to improve scalability and reduce routing information.

33. What is static routing?

Static routing uses manually configured routes that do not automatically adapt to network topology changes.

34. What is dynamic routing?

Dynamic routing uses routing protocols to learn routes and update routing information automatically when the network changes.

35. What is the difference between routing and forwarding?

Routing determines or learns paths, while forwarding sends individual packets through the outgoing interface selected from routing information.

36. If A-B = 2 and B-C = 5, what is the path cost A-B-C?

Total cost = 2 + 5 = 7.

37. A can reach X through B with cost 7 and through C with cost 5. Which route is selected?

The route through C is selected because its total cost 5 is lower.

38. A has cost 3 to B and B advertises destination X at cost 4. What is A's cost to X through B?

Cost = 3 + 4 = 7.

39. Is BGP a Distance Vector or Link State protocol?

BGP is generally classified as a Path Vector routing protocol.

40. Give the easiest difference between Distance Vector and Link State.

Distance Vector learns route distances from neighbours, while Link State learns topology information and builds a network map before calculating shortest paths.

20 Routing Algorithm MCQs With Answers

1. Routing is mainly used to:

A. Select paths for packets
B. Change screen resolution
C. Create HTML pages
D. Compress images

Answer: A — Select paths for packets

2. Distance Vector routing is based on:

A. Bellman-Ford
B. Prim only
C. Huffman coding
D. RSA

Answer: A — Bellman-Ford

3. Link State routing commonly uses:

A. Dijkstra
B. Binary search only
C. Bubble sort
D. FIFO scheduling

Answer: A — Dijkstra

4. Which routing algorithm maintains a topology database?

A. Link State
B. Basic Distance Vector only
C. Static routing only
D. None

Answer: A — Link State

5. RIP is an example of:

A. Distance Vector routing
B. Link State routing
C. Transport protocol
D. Application protocol

Answer: A — Distance Vector

6. OSPF is an example of:

A. Link State routing
B. Distance Vector routing
C. Application protocol
D. Physical Layer protocol

Answer: A — Link State

7. RIP uses which metric?

A. Hop count
B. File size
C. MAC address
D. Port number

Answer: A — Hop count

8. Maximum usable RIP hop count is:

A. 15
B. 16
C. 255
D. Unlimited

Answer: A — 15

9. In RIP, metric 16 means:

A. Unreachable
B. Best route
C. Direct route
D. Zero cost

Answer: A — Unreachable

10. Count-to-infinity is associated mainly with:

A. Distance Vector routing
B. Link State routing
C. Ethernet framing
D. TCP checksum

Answer: A

11. Split Horizon helps reduce:

A. Routing loops
B. Screen flicker
C. Frame size
D. Encryption

Answer: A — Routing loops

12. Poison Reverse advertises a route as:

A. Unreachable
B. Zero cost
C. Best route
D. Static

Answer: A — Unreachable

13. LSDB stands for:

A. Link State Database
B. Local Switching Data Block
C. Link Signal Data Bus
D. Logical State Data Byte

Answer: A — Link State Database

14. SPF stands for:

A. Shortest Path First
B. Secure Packet Frame
C. Simple Path Format
D. Static Protocol Field

Answer: A — Shortest Path First

15. Which protocol uses OSPF areas?

A. OSPF
B. RIP
C. HTTP
D. ARP only

Answer: A — OSPF

16. Dijkstra's algorithm requires link costs to be:

A. Non-negative
B. Always negative
C. Text values only
D. MAC addresses

Answer: A — Non-negative

17. Which approach mainly exchanges route information with neighbours?

A. Distance Vector
B. Link State only
C. Circuit switching
D. Token passing

Answer: A

18. Routing convergence means:

A. Routers reach a stable routing state
B. All packets are encrypted
C. Routers shut down
D. Frames become packets

Answer: A

19. BGP is generally classified as:

A. Path Vector
B. Link State
C. Pure Distance Vector
D. Data Link protocol

Answer: A — Path Vector

20. Routing table information is mainly used during:

A. Packet forwarding
B. Image compression
C. HTML rendering
D. Keyboard scanning

Answer: A — Packet forwarding

Frequently Asked Questions

What is a routing algorithm in simple words?

A routing algorithm is a method that helps routers decide which path packets should use to reach a destination network.

What is Distance Vector routing?

Distance Vector routing is a method where routers learn destination costs from neighbouring routers and choose the lowest-cost available route.

Which algorithm is used in Distance Vector routing?

Distance Vector routing is based on the Bellman-Ford shortest-path idea.

What is Link State routing?

Link State routing distributes information about local links so routers can build a topology database and calculate shortest paths.

Which algorithm is used in Link State routing?

Link State routing commonly uses Dijkstra's Shortest Path First algorithm.

What is the count-to-infinity problem?

It is a Distance Vector problem where routers can slowly increase a metric to a failed destination because incorrect route information continues circulating.

What is Split Horizon?

Split Horizon prevents a route from being advertised back through the same interface from which it was learned.

What is an LSDB?

LSDB means Link State Database. It stores topology information learned by Link State routers.

What is the main difference between RIP and OSPF?

RIP is a Distance Vector protocol using hop count, while OSPF is a Link State protocol that builds a topology database and runs an SPF calculation.

What is routing convergence?

Routing convergence is the process by which routers update their information after a topology change and eventually reach a stable routing state.

Is BGP a Link State protocol?

No. BGP is generally classified as a Path Vector routing protocol.

What does shortest path mean in routing?

It means the path with the minimum total routing metric or cost, not necessarily the shortest physical distance.

Quick Routing Algorithms Revision

Routing: Selects paths for packets.

Routing Metric: Value used to compare routes.

Shortest Path: Minimum total routing cost.

Dijkstra: Used for shortest-path calculation in Link State routing.

Distance Vector: Learns destination distances from neighbours.

Bellman-Ford: Foundation of Distance Vector routing.

Link State: Builds topology knowledge.

LSDB: Link State Database.

RIP: Distance Vector + Hop Count.

RIP Infinity: 16 hops.

OSPF: Link State + SPF.

Split Horizon: Do not advertise a learned route back.

Poison Reverse: Advertise the route back as unreachable.

Count-to-Infinity: Classic Distance Vector problem.

Convergence: Routers reach a stable routing state.

BGP: Path Vector routing protocol.

Final Memory Trick:

Distance Vector = Ask your neighbours.
Link State = Build the complete map.
Dijkstra = Find the cheapest path on that map.
Bellman-Ford = Compare the cost through each neighbour.