Description
Problem 1
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.
At some time T, the prefix x appears in AS4, adjacent to the router 4a. From which routing protocol
(OSPF, RIP, eBGP, or iBGP):
(a) Router 3c learns about prefix x?
(b) Router 3a learns about prefix x?
(c) Router 1c learns about prefix x?
(d) Router 1d learns about prefix x?
Write your solution to Problem 1 in this box
Problem 2
Referring to the previous problem, once router 1d learns about x will put an entry (x, I) in its forwarding
table:
(a) Will I be equal to I1 or I2 for this entry? Explain why in one sentence.
(b) Now suppose that there is a physical link between AS2 and AS4, shown by the dotted line. Suppose
router 1d learns that x is accessible via AS2 as well as via AS3. Will I be set to I1 or I2? Explain why
in one sentence.
(c) Now suppose there is another AS, called AS5, which lies on the path between AS2 and AS4 (not shown
in the figure). Suppose router 1d learns that x is accessible via AS2 AS5 AS4 as well as via AS3 AS4.
Will I be set to I1 or I2? Explain why in one sentence.
Write your solution to Problem 2 in this box
Problem 3
Consider the following topology. The cost metric of a link denotes the one-way propagation delay on the
link in msec (assuming the delays are symmetric). The two ISPs ISP 1 and ISP 2 are peers. CIDR is used
for addressing and BGP is used for inter-domain routing. Assume that both ISPs always try to enforce hotpotato routing above all other routing policies. What is the one-way propagation delay between Customer
1 and Customer 2? Is the routing between two customers symmetric or asymmetric?
Exchange Point
(Public Peering Location)
J
H
I
G
A
C
D
E
F
B
Customer 1
Customer 2
ISP 2
ISP 1
5
5
20
5
10
15
5
10
35 20
5
10
5
Write your solution to Problem 3 in this box
Problem 4
Network Address Translation (NAT) is the translation of an IP address used within one network to a different
IP address known within another network. A NAT capable router essentially translates private IP address
within a network to public IP addresses that can be visited publicly. A simple NAT-capable router will
have mappings between the private addresses within the network to the public address(es) that it uses.
Suppose that the router has a single public address 131.179.176.1 which it uses for all communication with
hosts that are not part of the private network. The private network used is subnet 10.0/16. The router
multiplexes its public IP address(es) as needed and keeps track of the multiplexing in a NAT translation
table.
Assume that the router multiplexes the public address using ports starting from 8000 and then increments
the port number by one for each new entry. For example, if a host behind the router with address and port
10.0.0.5:5000 sends a message to an external server 8.8.8.8:53, then the entry in the NAT table would
be filled in as below.
Table 1: NAT Translation Table
IP:port within private network IP:port outside private network
10.0.0.5:5000 131.179.176.1:8000
. . . . . .
The next time the router will use port 8001 to establish a new connection and so on.
(a) Draw the resulting NAT Translation Table at the end of the following message exchanges following the
format of Table 1 (including the original entry):
(1) 10.0.0.6:5000 sends a message to 172.217.11.78:80
(2) 10.0.0.10:6000 sends a message to 204.79.197.200:80
(3) 10.0.1.101:6001 sends a message to 206.190.36.45:80
(4) 10.0.0.10:6000 sends a message to 204.79.197.200:80
(5) 10.0.1.101:6001 sends a message to 172.217.11.78:80
(6) 10.0.0.7:7000 sends a message to 63.245.215.20:80
(7) 204.79.197.200:80 sends a message to 131.179.176.1:8002
(8) 204.79.197.200:80 sends a message to 131.179.176.1:8003
(b) For simplicity, let us assume that message format is MSG <Sender, Receiver>. In that case, if a host
in the private network with IP address and port 10.0.0.5:5000 sends a message to 132.239.8.45:80.
Then the message received at the router and leaving at the router would look as follows:
Message Received from Host: MSG <10.0.0.5:5000, 132.239.8.45:80>
Message Sent from Router: MSG <131.179.176.1:8000, 132.239.8.45:80>
List the messages, in the same format shown above, received from the host at the router and the
message sent from the router for the following messages:
(1) 10.0.0.6:5000 sends a message to 172.217.11.78:80
(2) 10.0.0.10:6000 sends a message to 204.79.197.200:80
Assume the entries from your NAT Translation Table in (a) to do this.
Problem 4 continued on next page. . . Page 4 of 7
CS 118 Spring 2018 : Homework 7
Write your solution to Problem 4 in this box
Page 5 of 7
Problem 5
In this problem, you will derive the efficiency of a CSMA/CD like multiple access protocol. In this protocol,
time is slotted and all adapters are synchronized to the slots. Unlike slotted ALOHA, however, the length
of a slot (in seconds) is much less than a frame time (the time to transmit a frame). Let S be the length of
a slot. Suppose all frames are of constant length L = kRS, where R is the transmission rate of the channel
and k is a large integer. Suppose there are N nodes, each with an infinite number of frames to send. We also
assume that dprop < S, so that all nodes can detect a collision before the end of a slot time. The protocol is
as follows:
• If for a given slot, no node has possession of the channel, all nodes contend for the channel; in particular,
each node transmits in the slot with probability p. If exactly one node transmits in the slot, that node
takes possession of the channel for the subsequent k − 1 slots and transmits its frame.
• If some node has possession of the channel, all other nodes refrain from transmitting until the node
that possesses the channel has finished transmitting its frame. Once this node has transmitted its
frame, all nodes contend for the channel.
Note that the channel alternates between two states: the productive state, which lasts exactly k slots,
and the non-productive state, which lasts for a random number of slots. The channel efficiency is defined as
the ratio of k/(k + x), where x is the expected number of consecutive non-productive slots.
(a) For fixed N and p, determine the efficiency of this protocol.
(b) For fixed N, determine the p that maximizes the efficiency.
Problem 5 continued on next page. . . Page 6 of 7
Write your solution to Problem 5 in this box
Page 7 of 7
