"Routing Protocols: Shortest Path, Flooding, Distance Vector & Link State" — Practice

Question 1

State the complexity of Dijkstra's algorithm with a simple array and with a binary heap, and the condition it requires.

Accepted Answer

O(n squared) with an array and O(E log n) with a binary heap, and it requires all edge costs to be non-negative.

Question 2

What value does RIP treat as infinity, and what does that imply about network size?

Accepted Answer

Sixteen. A destination at 16 hops is unreachable, so the usable network diameter is capped at 15 hops.

Question 3

What does a link state advertisement contain?

Accepted Answer

Only the originating router's own links and their costs. Every router floods one, and each assembles the full topology from the collection.

Question 4

Run Dijkstra from A on the graph with A-B 4, A-C 2, B-C 1, B-D 5, C-D 8, C-E 10, D-E 2, and give the final distances.

Accepted Answer

Finalise A at 0, C at 2, B at 3 via C, D at 8 via B, and E at 10 via D. The shortest path to E is A, C, B, D, E at cost 10, which beats the two-hop A-C-E at 12.

Question 5

Explain count-to-infinity in a three-router line when the far link fails.

Accepted Answer

C loses its route, but B still advertises distance 2, a route that actually goes through C. Since the advertisement carries no path, C adopts it at cost 3, then B updates to 4 through C, and the distances climb one step per round until they reach the protocol's infinity.

Question 6

Give three differences between distance vector and link state routing.

Accepted Answer

Distance vector routers know only neighbours' distances while link state routers know the whole topology; distance vector sends full vectors to neighbours only while link state floods small per-router advertisements to everyone; and distance vector converges slowly with a counting problem while link state converges in about the network diameter with only transient loops.

Question 7

A network of 900 routers is split into 30 regions of 30. Compare table sizes with flat routing.

Accepted Answer

Flat routing needs 899 entries per router. Hierarchical routing needs 29 entries for the other routers in the region plus 29 summary entries for the other regions, a total of 58, a reduction of more than fifteen times.

Question 8

Show that split horizon fails for a loop of three routers and explain why.

Accepted Answer

With A, B and C mutually connected and the destination beyond C, C's failure lets A learn a stale route from B and B learn one from A, so the obsolete information circulates around the triangle. Split horizon only forbids advertising a route back to the neighbour it came from, and in each of these exchanges the recipient is a different neighbour, so the rule is never violated.

Question 9

Compare the message complexity of the two families and say what the choice actually turns on.

Accepted Answer

Both are O(nE) per round, since link state floods n advertisements over E links and distance vector sends n-entry vectors across E adjacencies. The choice turns on convergence time, which favours link state, memory, which favours distance vector, and per-update computation, which also favours distance vector.

Question 10

Give two reasons BGP carries paths rather than distances.

Accepted Answer

First, loop detection becomes trivial, since a router discards any advertisement whose AS path already contains its own number, which matters at a scale where count-to-infinity delays would be intolerable. Second, policy cannot be expressed as a distance, because an operator may prefer a longer customer path to a shorter transit path, and that decision depends on who is on the path rather than how long it is.

Practice — "Routing Protocols: Shortest Path, Flooding, Distance Vector & Link State"

Sign in to save attempts to your dashboard and track your accuracy over time

Find a verified tutor

Join a live course

Browse coaching centres

About

Categories

Support

Documentation

Get Study Tips & Updates

Download Our App

Download for iOS

Download for Android

Popular Cities