Computer Networks

Homework set no 3: paper exercises. Submission deadline: January 5, 2015, 23:55
1. Packet forwarding in routers (2 points)
Suppose a router has built up the forwarding table shown below.
Destination prefix Next Hop to forward packet to
128.96.168.0/23 I1
128.96.166.0/23 R2
128.96.164.0/22 R3
Default R4
The router can deliver packets directly over interface I1, or it can forward packets to routers R2, R3, or R4,
as shown in the diagram below.
Assume the router performs longest prefix match. Which link does the router use to forward a packet
with destination IP address a) 128.96.167.151, b) 128.96.163.151, c) 128.96.169.192, d) 128.96.165.121
respectively? Justify your answer, you will get no marks for a correct answer that has no justification (0.5
point for each correct answer, for a total of 2 points)
Hint: you may find it easier to solve this problem if you write down the IP address range that is represented
by each destination prefix in the forwarding table.
2. Dijkstra’s algorithm (3 points)
Consider the following network that runs a link state routing protocol. With the indicated link costs, use
Dijkstra’s algorithm to compute least cost paths from node A to all other network nodes.
Figure 1. Network topology.
Show how the algorithm works by computing tables similar to Table 4.3 in the textbook. Also, write down
explicitly the least cost paths from node A to all other nodes.
3. On the distance-vector algorithm (3 points)
a) Consider the count‐to‐infinity problem in the distance vector routing. Will the count‐to‐infinity problem
occur if we decrease the cost of a link? Why? How about if we connect two nodes which do not have a
link? (1 point)
b) Consider the simple 3‐node network shown in Figure 4.31(a) of the textbook, but instead of numeric
values, assume that the costs between links have arbitrary values c(x,y), c(x,z), c(y,z), respectively, but all
values c(x,y), c(x,z), c(y,z) are non‐negative. We run the Bellman‐Ford algorithm.
 Show that at the end of the first iteration, all components of the distance vectors in all nodes have
values that are less than or equal to the corresponding values at initialization. (1 point)
 Show that at the end of the THIRD iteration, the algorithm has converged. (1 point)
Hint: For the first part, you essentially need to run Bellman‐Ford with values c(x,y), c(x,z), c(y,z) and
carefully compare the results between iterations. For the second part, you should be comfortable with
some minor algebra involving min operators. Specifically, you can use the following properties of the min
operator
1. min(B,C)=B, if we know that B≤C.
2. A+min(B,C)= min(A+B,A+C)
3. min(A,B,C)= min(A,B) if we know that A≤C.
You can also assume without any loss of generality that c(x,y)≥c(x,z)≥c(y,z), i.e. you can rename nodes x,y,z
so that they satisfy the above relation.
4. BGP and policy-based routing (2 points)
a) A stub autonomous system is a network that only routes packets for which either the source IP address
or the destination IP address belongs to a host in this network. In other words, a stub AS does NOT route
traffic that originates in other ASs (based on source or destination IP address). Consider the inter‐network
shown in Figure 2, where A,B,C,X,Y,W denote ASs (not individual hosts) and X,Y,W are stub ASs.
Figure 2. Provider‐customer relationships between networks A,B,C,X,Y,W.
The following policies are established by providers A,B,C:
 C will route packets between W and Y (in both directions) but it will NOT route packets between
W and X. Of course, C will route all packets between X and Y (in both directions), otherwise X,Y
would never be able to communicate!
 B and C do not want to route any packets through each other.
Based on the above policies, how does each of stub ASs X,W view the network, i.e. what are the paths to
all other nodes? To give you some help, the view of the network with respect to Y is shown in Figure 3
below, so you are asked to provide similar Figures for the network views w.r.t. X, W. (1 point).
Hint: to solve this problem, you must consider the BGP routes exchanged between the different ASs (you
need only consider the AS‐PATH in each BGP route), and how they are affected by the above policies.
Figure 3. The view of the network according to AS Y
b) In Figure 2, suppose that there is another stub network V that is a customer of ISP A. Suppose that B
and C now have a peering relationship (i.e. they have agreed to route packets to each other), and A is a
customer of both B and C. Suppose that A would like to have the traffic destined to W to come from B
only, and the traffic destined to V from either B or C. How should A advertise its routes from W and V to
B and C? Which AS routes does C receive from A and B? (1 point)