1. Consider the network shown below. Using Dijkstra’s algorithm, and showing your work using a table similar to Table 5.1 (textbook), do the following:
a) Compute the shortest path from v to all network nodes.
b) Compute the shortest path from z to all network nodes.
2. Consider a general topology (that is, not the specific network shown above) and asynchronous version of the distance-vector algorithm. Suppose that at each iteration, a node exchanges its distance vectors with its neighbors and receives their distance vectors. Assuming that the algorithm begins with each node knowing only the costs to its immediate neighbors, what is the maximum number of iterations required before the distributed algorithm converges? Justify your answer.
3. Consider the three-node topology shown below (i.e., Figure 5.6 in textbook). Rather than having the link costs shown in the figure, the link costs are c(x,y)=3, c(y,z)=6, c(z,x)=4. Compute the distance tables after the initialization step and after each iteration of a synchronous version of the distance vector algorithm.
4. Consider the network below. Suppose AS3 and AS2 are running OSPF for their intra-AS routing protocol. Suppose AS1 and AS4 are running RIP for their intra-AS routing protocol. Suppose eBGP and iBGP are used for the inter-AS routing protocol. Initially suppose there is no physical link between AS2 and AS4.
a) Router 3c learns about prefix x from which routing protocol: OSPF, RIP, eBGP, or iBGP?
b) Router 3a learns about x from which routing protocol?
c) Router 1c learns about x from which routing protocol?
d) Router 1d learns about x from which routing protocol?
5. Referring to the previous problem, once router 1d learns about x it will put an entry (x, I) in its forwarding table.
a) Will I be equal to I1 or I2 for this entry? Explain why in one sentence.
b) Now suppose that there is a physical link between AS2 and AS4, shown by the dotted line. Suppose router 1d learns that x is accessible via AS2 as well as via AS3. Will I be set to I1 or I2? Explain why in one sentence.
c) Now suppose there is another AS, called AS5, which lies on the path between AS2 and AS4 (not shown in diagram). Suppose router 1d learns that x is accessible via AS2 AS5 AS4 as well as via AS3 AS4. Will I be set to I1 or I2? Explain why in one sentence.
