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.
Explain the initialisation step in the DV algorithm…
Create the routing table for each node, where non-neighbouring nodes are set to infinity.
- Explain the relaxation step in the DV algorithm…
- If at any point the DV of a node changes, the nodes neighbours must recalculate their DV’s.
- This ensures the network always has up to date costs, and can dynamically calculate the least cost path from any node.
Explain the Convergence step in the DV algorithm…
Every node has a steady Distance Vector given the current Link Cost configuration, resulting in the least cost route.
Explain what happens when there is a Link Cost change…
The change is communicated to neighbours via DV transmission, and the algorithm repeats until re-convergence occurs.
What happens if a link gets cut?
This can lead to an infinite increase in cost between 2 nodes because one of the nodes is not aware of the lost connection. For example, B → C is cut. B updates DV and informs A. Then A updates its DV, but updates it assuming that B → C is still open. B notices this update and updates its own DV. This cycle continues infinitely.
