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