Routing Flashcards
what is routing
selecting the best path for a packet from source to dest
what are the 2 main routing algorithms
- bellman ford (distance vector)
- link state
how does bellman ford work
- each node has a table with <dest, cost, next-hop>
- a node shares with all its neighbours all of its info it has
- eventually the network stabilizes
whats the issue with distance vector
- count to infinity problem
A –X– B —– C
link from A to B fails
C tells B it can reach A since it doesnt know about the failure. B now thinks it can reach A through C and they go back and forth and the cost reaches inf
delay propogation
- solution to count 2 inf
- when link fails, delay sending any info, eventually C will think B is gone and will try to find a different route
set inf to small value
by setting inf to 16 instead of counting to inf we can just count to 16
- problem: limits the size of the network as 16 is the max cost
split horizon
C does not tell B about any routes that go though B
never advertise a route to neighbour X if the route passes through X
- problem: C will still have the stale route
poison reverse
- B tells C that its route to A is dead
- C can know set its route to A as dead
problem: unstable for 3 router loops
how does Link state routing work
- each router has entire picture of network in the routing table
- nodes send small updates to all other nodes in network
- using all this info the node will do dikjstras alg to find shortest path to all other nodes
pros of link state routing
- no loops
- stabalizes fast
cons of link state routing
- more storage requiremnts
- overhead to do dikjras
distance vector vs LSR
in dist: node only talks to neighbour but tells them everything
in LSR: nodes talk to everyone but only tell them their direct links
