L4 - Internet Routing 2 Flashcards
Give 3 issues with Link State Algorithms.
- Slow network changes
- May not output correct result if graph has negative edges
- Large forwarding tables and frequent LSM consume bandwidth.
What is a solution to the issues of LS algorithms?
Distance Vector Routing Algorithm
Define what a Distance Vector Algorithm is…
A class of network routing algorithms which use the concept of Distance Vectors to estimate the cost from a source node to an end node.
What is a Distance Vector?
A table of a node containing the estimated cost ( distance ) from that node to all other nodes. Remember, Vectors have magnitude and direction, thus, the Distance vector doesn’t account for other nodes. It’s the estimated cost from X to Y, which is resolved by other nodes in the network.
Each node is essentially saying → ‘I know the cost from myself to my neighbours, so I can provide the minimum of these. After that, I will let the other nodes deal with the remainder of the path.’
What are the 3 defining properties of a Distance Vector Algorithm? Define each…
- Distributed
- Each node only receives information from it’s neighbours ( local topology )
- Performs calculations based on neighbours and returns results to neighbours.
- Iterative
- Iterates neighbours until no more information is exchanged between them.
- Asynchronous
- Nodes don’t need to work in sync.
In DV algorithms, who can each node communicate with?
Direct neighbours.
In DV algorithms, what does the forwarding table of each node contain?
- Cost of X to it’s neighbours.
- Distance Vector of X to all N-1 nodes.
- Distance Vector of X’s neighbours.
Define the Bellman Ford algorithm…
A dynamic programming algorithm. It’s designed to find the shortest path from a source node to all other nodes in a weighted and directed graph.
How would the Bellman Ford Algorithm go about finding the shorted path from X to Y?
The distance between X and Y is the least cost path between X and it’s neighbours, plus the least cost path between that neighbour and Y.
What is the time complexity of the BFA?
- Complete graph → N(N-1)(|E|) → N( N^3 )
- Usually → N(|E|) → O( N^2 )
Explain the process of Relaxation in the BFA…
Comparing current cost of neighbour node to cost of current node + local distance to neighbour node.
What is an issue with the BFA?
If we have a negative cycle, the cost will decrement continuously until iteration stops at E-1.
Explain the general idea of how the Distance Vector Routing Algorithm works…
- ach vertex X periodically sends it’s DV to it’s neighbours.
- Upon receiving DV, neighbours update their own DV based on the Bellman Ford Equation.
- This dynamic process results in a natural convergence to the least cost path from X to Y.
During the DVRA, what is the 4 step process that occur asynchronously at each node?
- Initialise the graph from origin node.
- Wait for local links to change values.
- Recompute the Distance Vector.
- Notify all neighbours of the updated Distance Vector.
What is the result of the DVRA?
A natural convergence to the least cost path.
