🧭 Routing & Congestion Control
Why it matters: Distance vector versus link state comparisons, RIP/OSPF/BGP facts and token bucket numericals.
Subtopics
Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 4 done.
1Distance vector routing
2Link state routing
3RIP, OSPF, BGP and the Internet hierarchy
4Congestion and traffic shaping: leaky and token bucket
Formulas
Bellman-Ford update
D_x(y) = min over neighbours k of [ c(x,k) + D_k(y) ]
Convergence
at most n − 1 rounds of exchanges
Dijkstra with a heap
O((V + E) log V)
RIP
hop count, infinity = 16, UDP port 520
Token bucket burst length
t = C / (M − r)
Token bucket total time
t + (D − M·t) / r
What GATE asks from this
Question types seen repeatedly in past papers. More stars means more frequent.
★★★
Compare link state and distance vector
Overhead, loop behaviour with split horizon, convergence speed.
★★★
Which protocol is intra- or inter-domain, algorithm used
OSPF = Dijkstra, link state, hierarchical; RIP = distance vector; BGP = inter-domain.
★★★
Token bucket: minimum time to send D data
Burst until the bucket empties, then token-rate limited.
Ratings are approximate, based on recurring patterns in past GATE CSE papers.
Previous year questions
3 real questions from the official GATE CSE papers (2014 to 2023), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.
3 questions · 0 correct of 0 attempted · marks 0 / 4
Year:
GATE 2023 · Q25MSQ1 mark
Which of the following statements is/are INCORRECT about the OSPF (Open Shortest Path First) routing protocol used in the Internet?
One or more options may be correct. Select all that apply, then submit.
GATE 2016 Set 1 · Q54NAT2 marks
For a host machine that uses the token bucket algorithm for congestion control, the token bucket has a capacity of 1 megabyte and the maximum output rate is 20 megabytes per second. Tokens arrive at a rate to sustain output at a rate of 10 megabytes per second. The token bucket is currently full and the machine needs to send 12 megabytes of data. The minimum time required to transmit the data is ______ seconds.
GATE 2014 Set 1 · Q23MCQ1 mark
Consider the following three statements about link state and distance vector routing protocols, for a large network with 500 network nodes and 4000 links. [S1] The computational overhead in link state protocols is higher than in distance vector protocols. [S2] A distance vector protocol (with split horizon) avoids persistent routing loops, but not a link state protocol. [S3] After a topology change, a link state protocol will converge faster than a distance vector protocol. Which one of the following is correct about S1, S2, and S3?
Common traps
Link-state does not use Bellman-Ford; distance vector does.
BGP exchanges path/policy information and runs over TCP; it is not a shortest-path protocol.
Split horizon reduces, but does not fully remove, counting to infinity (loops of three or more routers).
In the token bucket the burst and the token arrival happen at the same time, so the burst lasts C/(M − r), not C/M.