4 - Dynamic Routing and Protocols Flashcards
Dynamic Routing
Router generates tables, detects topology, provides optimal routing. Scalability, robustness and simplicity
Convergence
When all routers have a stable view of the network
What happens when there is not convergence?
Network downtime and packets disappear (black holes)/go back and forward in loops
Least cost path
Sum of cost of links is minimum
Shortest path
Least links used
Distance vector
Accumulates a metric hop by hop as the protocol messages traverse the subnet
- Based on Bellman-Ford algorithm
How do Distance Vector Protocols work?
- Router advertises distances it has to other prefixes/subnets
- Other routers compute next hop table based on least cost from neighbouring routers and the cost to that neighbour itself.
Bellman-Ford Algorithm: Describe the process
dx(y):= cost of least-cost path from x to y
then
dx(y) = min {c(x,v)+dv(y)}
min is taken over all neighbors v of x
What is stored in the RIB?
Accumulated cost
Next hop the entry was received from
Accumulated hop and max hop count
Time received
Why store the accumulated hop and max hop count?
Detect cycles
What happens when distance vector adds a subnet?
- Routing update broadcast to neighbours
- Any router receiving compares the new cost to that in its RIB
- If it is smaller or new then the entry is used and broadcast to all neighbours
What happens in distance vector when a subnet is removed?
Each RIB entry is aged
- Timeout defines when it is removed
Periodically, routes are re-advertised.
If neighbour does not respond witin timeout, all routes learned are removed
Iterative, Asynchronous distance vector
Each iteration caused by:
- local link cost change
- DV update message from neighbour
Distributed distance vector
Each node notifies neighbors only when its DV changes
What happens when link cost changes?
Update routing info, recalculate distance vector
If DV changes, notify neighbours
