EECS325-Assignment 4 Solved

Questions
1.    Consider the network below. Assume that a simple distance vector routing (without poisoned reverse) is used to route packets.

 

The table below shows the distance and next-hop router to node F from each node after the algorithm stablizes.

 
Before update (distance, next-hop)
A to F
4, E
B to F
3, E
C to F
4, B
D to F
3, F
E to F
1, F
Assume that routing messages and forwarding table updates happen at the same time on all nodes. Assume routers break ties between equal cost paths by picking the nexthop router with the lower ID.

(a)    Using distance vector without Poisoned Reverse, what is E’s second best path to

F? (i.e., which one of E’s other neighbors provides the least-cost path to F)

(b)    Now the link cost between nodes E and F increases from 1 to 6. Once E detects the change in link cost, what distance to F does E advertise to its neighbors? Fill in the routing entry (distance and next-hop router) that E’s neighbors compute for destination F after receiving E’s update.

E’s advertised distance to F is  

 
After E’s update (distance, next-hop)
A to F
 
B to F
 
D to F
 
(c)    Continuing with the previous question, what distance does B advertise for destination F in the next iteration? Fill in the routing entry (distance and next-hop) that B’s neighbors compute for destination F after receiving B’s update.

B’s advertised distance to F is  

 
After B’s update (distance, next-hop)
A to F
 
C to F
 
E to F
 
(d)    Continuing with the previous question, what distance to F does C now advertise? Fill in the routing entry (distance and next-hop) that C’s neighbors compute for destination F after receiving C’s update.

C’s advertised distance to F is  

 
After C’s update (distance, next-hop)
B to F
 
                       Are all routers now following the correct shortest path?                     Yes                                                                               No

(e)    Will the routing tables converge faster if we use Poisoned Reverse?

2.    General Routing. Consider the network shown below. Supporse AS3 and AS2 are running OSPF for their intra-AS routing protocol. Suppose AS1 and AS4 aer running RIP (distance vector routing algorithm) for their intra-AS routing protocol. Supppose 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?

BGP Policies. Consider an interdomain network with domains A through F. For simplicity, assume that destination in this problem are domains, not prefixes. Routes are represented by a series of domains, e.g., [A - B - C] denotes a route that start with domain A and go to domain B and then go to domain C (which is the destination). Domains always advertise the route to themselves (i.e., domain X advertise paths to X to all peers, customers, and providers). The following connectivity/business relationship exists:

•   B is a customer of A

•   C is a customer of A

•   D is a customer of A

•   B and C are peers

•   C and D are peers

•   E is a customer of B

•   F is a customer of B

•   F is a customer of C

•   G is a customer of D

Assuming that each domain’s routing policies follow normal business practice, and that

BGP has converged,

i) What routes does A advertise to B? ii) What routes does C advertise to B? iii) What routes does E advertise to B? iv) What routes does F advertise to B?