[SOLVED] COSC328-Lab 6

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 D_A(B) = min_v { c_A,v + D_v(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.

D_z(x) = min { 2 + 0, 6 + 3 } = 2

D_z(v) = min { 6 + 0, 2 + 3 } = 5

D_z(y) = min { 2 + 3, 2 + 3 + 1 + 2} = 5 D_z(u) = min { 2 + 3 + 2, 2 + 3 + 1 } = 6 The resulting distance table is:

Distance table from node z

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 D_z(x)=∞, and informs y that D_z(x)=6. w informs y that D_w(x)=∞, and z that D_w(x)=5. Finally, y informs both w and z that D_y(x)=4.

60. 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 D_y(x)=∞ and informs w that D_y(x)=9. At t2, w informs y that D_w(x)=∞ and z that D_w(x)=10. At t3, z must update its least costs, so it informs w that D_z(x)=∞ and y that D_z(x)=11. At t4, y must update its table, and informs w that D_y(x)=14 and z that D_y(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 D_z(x)=50. At t28, w advertises to y that D_w(x)=∞ and to z that D_w(x)=∞, and y advertises to w that D_y(x)=53 and to z that D_y(x)=∞. At t29, w calculates that the least cost to x is 51, so it advertises to y that D_w(x)=51 and to z that D_w(x)=∞. At t30, y must update its least costs, so it advertises to w that D_y(x)=∞ and to z that D_y(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.

1. 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.

1. eBGP – 1c learns of x from 3a: different autonomous system, so eBGP.
2. 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

1. 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

1. 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

1. 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(n²). Since a heap is a tree-based data structure, the best case time complexity (if the tree is a complete binary tree) is O(log_an) where a is the number of branches in the tree. This is reflected by the lower observed time complexity in the generated plot.