Description
1. (2pt) Compare and contrast link-state and distance-vector
routing algorithms.
2. (3pt) Consider the following network. With the indicated
link costs, use Dijkstra’s shortest-path algorithm to
compute the shortest path from x to all network nodes.
Show the algorithm by computing a table similar to Slide
15 in Chapter 5.
3. (5pt) Consider the network shown below, and assume that
each node initially knows the costs to each of its
neighbors. Consider the distance-vector algorithm and
show the distance table entries at node z. (Show the
distance table entries in each step)
4. (2pt) Suppose we have the forwarding tables shown in the
following table for nodes A and F, in a network where all
links have cost 1. Give a diagram of the smallest network
consistent with these tables.
A
Node Cost Nexthop
B 1 B
C 2 B
D 1 D
E 2 B
F 3 D
F
Node Cost Nexthop
A 3 E
B 2 C
C 1 C
D 2 E
E 1 E
5. (3pt) Consider the network below. When the link cost c(x,
y) increases from 4 to 60. Explain why it takes 44 iterations
for the algorithm to stabilize. (Hint: show the distance
table entries in each iteration)
6. (4pt) Consider the network shown 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 prefix 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?
x z
4 1
50
y
60
7. (4pt) In the figure below, X, Y and Z are access ISPs and A,
B and C are backbone provider networks. Suppose an ISP
only wants to route traffic to/from its customer networks
(does not want to carry transit traffic between other ISPs).
Another BGP policy X wants to enforce is that X does not
want to route from B to C via X.
Following is the topology view at Y. Draw the topology
views of W and X.
