Routing Algorithms MCQs

1. What is the main objective of the shortest path algorithm in routing?

a) Minimize the number of hops b) Minimize the total path cost c) Maximize bandwidth d) Reduce packet size

Correct Answer: b) Minimize the total path cost

Explanation:
The shortest path algorithm aims to find the path with the lowest total cost (sum of link costs) between source and destination, not necessarily the fewest hops.

2. Which algorithm is commonly used to find the shortest path in a graph with non-negative edge weights?

a) Bellman-Ford b) Dijkstra's c) Floyd-Warshall d) Kruskal's

Correct Answer: b) Dijkstra's

Explanation:
Dijkstra's algorithm is the most efficient for finding shortest paths in graphs with non-negative weights. Bellman-Ford can handle negative weights, and Floyd-Warshall finds paths between all pairs.

3. Dijkstra's algorithm is an example of:

a) Distance Vector Routing b) Link State Routing c) Path Vector Routing d) Hierarchical Routing

Correct Answer: b) Link State Routing

Explanation:
Dijkstra's algorithm is used in Link State Routing protocols where each router has complete topology information and computes shortest paths independently.

4. What is the time complexity of Dijkstra's algorithm using a binary heap?

a) O(V) b) O(V log V + E log V) c) O(V²) d) O(E log V)

Correct Answer: b) O(V log V + E log V)

Explanation:
With a binary heap implementation, each extract-min operation takes O(log V) and there are V such operations. Each edge relaxation takes O(log V) and there are E edges.

5. In Dijkstra's algorithm, which data structure is optimal for extracting the minimum distance node efficiently?

a) Queue b) Stack c) Priority Queue (Min-Heap) d) Linked List

Correct Answer: c) Priority Queue (Min-Heap)

Explanation:
A min-heap allows O(1) access to the minimum element and O(log n) insertion and extraction, making it ideal for Dijkstra's algorithm which repeatedly needs the node with the smallest tentative distance.

6. Which of the following is a key feature of Distance Vector Routing?

a) Routers exchange entire routing tables with neighbors b) Routers flood Link State Advertisements (LSAs) c) Uses Dijkstra's algorithm d) Requires OSPF protocol

Correct Answer: a) Routers exchange entire routing tables with neighbors

Explanation:
In Distance Vector Routing, routers periodically send their complete routing tables to directly connected neighbors, containing information about all known destinations and distances.

7. What is the main issue with Distance Vector Routing?

a) High bandwidth usage b) Count-to-infinity problem c) Complex implementation d) Requires centralized control

Correct Answer: b) Count-to-infinity problem

Explanation:
The count-to-infinity problem occurs when routers slowly increment their metric for a destination that has become unreachable, potentially causing routing loops until the metric reaches its maximum value.

8. Which algorithm is used in Distance Vector Routing to update routing tables?

a) Dijkstra's algorithm b) Bellman-Ford algorithm c) Floyd-Warshall algorithm d) Prim's algorithm

Correct Answer: b) Bellman-Ford algorithm

Explanation:
The Bellman-Ford algorithm forms the mathematical basis for Distance Vector Routing, where each router calculates distances based on information from its neighbors.

9. What is "Split Horizon" used for in DVR?

a) To prevent routing loops b) To reduce packet size c) To increase network speed d) To encrypt routing updates

Correct Answer: a) To prevent routing loops

Explanation:
Split Horizon prevents a router from advertising a route back to the neighbor from which it learned that route, which helps prevent routing loops.

10. Which protocol uses Distance Vector Routing?

a) OSPF b) BGP c) RIP d) IS-IS

Correct Answer: c) RIP

Explanation:
RIP (Routing Information Protocol) is the most common Distance Vector Routing protocol. OSPF and IS-IS are link-state protocols, while BGP is a path-vector protocol.

11. Which of the following is a characteristic of Link State Routing?

a) Routers know only about their neighbors b) Routers flood Link State Advertisements (LSAs) c) Uses Bellman-Ford algorithm d) Prone to count-to-infinity problem

Correct Answer: b) Routers flood Link State Advertisements (LSAs)

Explanation:
In Link State Routing, routers flood LSAs throughout the network, allowing each router to build a complete topological map of the network.

12. Which algorithm is used in Link State Routing to compute the shortest path?

a) Bellman-Ford b) Dijkstra's c) Kruskal's d) Prim's

Correct Answer: b) Dijkstra's

Explanation:
Link State Routing protocols use Dijkstra's algorithm to compute shortest paths from the complete network topology stored in the link-state database.

13. What is the purpose of a "Link State Database" in LSR?

a) Stores the entire network topology b) Stores only neighbor information c) Stores MAC addresses d) Stores encrypted packets

Correct Answer: a) Stores the entire network topology

Explanation:
The Link State Database contains information about all routers and links in the network, forming a complete topological map used for shortest path calculations.

14. Which protocol uses Link State Routing?

a) RIP b) BGP c) OSPF d) EIGRP

Correct Answer: c) OSPF

Explanation:
OSPF (Open Shortest Path First) is the most common Link State Routing protocol. RIP is distance vector, BGP is path vector, and EIGRP is an advanced distance vector protocol.

15. What is the main advantage of Link State Routing over Distance Vector Routing?

a) Lower bandwidth usage b) Faster convergence c) Simpler implementation d) No need for LSAs

Correct Answer: b) Faster convergence

Explanation:
Link State Routing converges faster than Distance Vector Routing because changes are flooded immediately throughout the network and each router can independently recalculate paths.

Your Score: /15