Computer Networks I  Assignment 4

EECS 325 Computer Networks I
 Assignment 4
Instructions

Please typewrite your answers and submit a pdf file to Canvas. You should complete this
assignment individually.
There are some extra credits for EECS 325 and 325N students. Credit points are shown
in front of each question. Credits are marked as red for EECS 325/325N, and blue
for EECS 425, if they are different.
Questions
1. (15 pts) 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)
1 of 4
EECS 325 Computer Networks I
Spring 2020 Assignment 3
(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. (8pts) 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
2 of 4
EECS 325 Computer Networks I
Spring 2020 Assignment 3
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
3 of 4
EECS 325 Computer Networks I
Spring 2020 Assignment 3
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?
4 of 4