Description
- According to the distance-vector algorithm using the Bellman-Ford equation, the least-cost path from any node A to any node B will be DA(B) = minv { cA,v + Dv(b) } for all neighbouring nodes v. Therefore, to build the distance table from z, we use the BF equation to calculate the least-cost path to each node, starting with the neighbours of z.
Dz(x) = min { 2 + 0, 6 + 3 } = 2
Dz(v) = min { 6 + 0, 2 + 3 } = 5
Dz(y) = min { 2 + 3, 2 + 3 + 1 + 2} = 5 Dz(u) = min { 2 + 3 + 2, 2 + 3 + 1 } = 6 The resulting distance table is:
Distance table from node z
| Node | Path | Cost | ||
| x | {z,x} | 2 | ||
| v | {z,x,v} | 5 | ||
| y | {z,x,y} | 5 | ||
| u | {z,x,v,u} | 6 |
Alternatively, here is a sequence of tables showing how z and its neighbours x and v obtain their least cost distances:
- a) Using poisoned reverse, z informs w that Dz(x)=∞, and informs y that Dz(x)=6. w informs y that Dw(x)=∞, and z that Dw(x)=5. Finally, y informs both w and z that Dy(x)=4.
- At time t0, z, w, and y have the information from part a), and the link cost c(x,y) changes from 4 to 60. At t1, y informs z that Dy(x)=∞ and informs w that Dy(x)=9. At t2, w informs y that Dw(x)=∞ and z that Dw(x)=10. At t3, z must update its least costs, so it informs w that Dz(x)=∞ and y that Dz(x)=11. At t4, y must update its table, and informs w that Dy(x)=14 and z that Dy(x)=∞. At t4, w must update its table… at this point we can tell we have a count to infinity problem.
Continuing with this logic, at t27, z calculates that the least cost to x is 50 from its direct path to x, so it advertises to both y and w that Dz(x)=50. At t28, w advertises to y that Dw(x)=∞ and to z that Dw(x)=∞, and y advertises to w that Dy(x)=53 and to z that Dy(x)=∞. At t29, w calculates that the least cost to x is 51, so it advertises to y that Dw(x)=51 and to z that Dw(x)=∞. At t30, y must update its least costs, so it advertises to w that Dy(x)=∞ and to z that Dy(x)=52. Finally, the system is stabilized at t31, where for z, the path to x through w has cose ∞, through y it has cost 55, and through its direct link to z, cost 50. For w, the cost to access x either directly or through y is ∞, and through z is 51. Finally, for y, to access x through w is 52, through y is 60, and through z is 53.
- Since poisoned reverse does not work when a router is connected to more than two other routers, the only solution to the count to infinity problem in this graph is to eliminate the connection between y and z.
3) a) eBGP – 3c learns of x from 4c in a different autonomous system, using eBGP. b) iBGP – 3a learns of x from 3b in the same autonomous system, so iBGP.
- eBGP – 1c learns of x from 3a: different autonomous system, so eBGP.
- iBGP – 1d learns of x from either 1a (most likely) or 1b: same autonomous system, so iBGP.
4) X’s view of the network topology is as follows:
Since X is a multi-homed access ISP, it can reach both B and C directly. By policy, any traffic passing through X must have X as either its source or destination. Therefore, to reach Y, it must pass through C with a path XCY. To reach W, it appears as though there are two possible paths, XBAW and XCAW. W has advertised a path to A, X has advertised a path to B and C, and Y has advertised a path to C. If B learns of a path to W through A which is then advertised to X, X will let C know that it has a path to W. Since X already has a path to W, C will not advertise a path to W through A since this could potentially increase the load on C, so the path AC is not advertised. Similarly, B would not advertise a route to C to reduce the traffic from B to C.
W’s view of the network topology is as follows:
Similar to X’s topology, W advertises a path to A, Y advertises a path to C, and X advertises a path to B. Since X will not accept any traffic without itself as the source or destination, it does not advertise its link to C. To reduce traffic through itself, B also neglects to advertise a path from B to C.
“ Fun” with coding
- a) The output for the given graph is as follows (note I modified the code to use the python functions for undirected graphs) Legend:
A = 0 B=1 C=2 D=3 E=4
This output is as expected
- The output for the graph in question 1 is as follows (again using undirected graphs)Legend:
u=0 v=1 x=2 y=3 z=4
Once again, the output is as expected
- From the generated plot, we see the array implementation increasing in time complexity as a function of n as a second order polynomial, which matches our expectations of the time complexity of Dijkstra’s algorithm being O(n2). Since a heap is a tree-based data structure, the best case time complexity (if the tree is a complete binary tree) is O(logan) where a is the number of branches in the tree. This is reflected by the lower observed time complexity in the generated plot.
