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