Computer Network
Allowed material: one-sided notes page and a calculator
Please write each answer on a separate page.
Please answer Problem 3 and Part of Problem 1 on the exam form/tables. Please submit
the exam form and the additional tables
If you make any assumptions, please state them CLEARLY.
Name: _____________________________
UNI: _____________________________
Problem 1 (20 pts.)
Consider three local area networks connected by two routers as described in the figure below:
Subnet 1 has the network address 111.111.111/24, Subnet 2 has the network address 122.122.122/24, and
Subnet 3 has the network address 133.133.133.128/28. The MAC address of Node i (i = A,…,F) is FF-FFFF-FF-FF-0i.
The MAC address of the two interfaces of Router i (i=1,2) are FF-FF-FF-FF-FF-i1 and FFFF-FF-FF-FF-i2.
A. (3 pt.) Assign IP addresses to all the interfaces.
B. (4 pt.) How many nodes can be added to subnet 3? Explain your answer.
C. (12 pt.) Consider sending a TCP packet containing some application data from Node A to Node F.
Suppose all the ARP tables are empty and that there is no existing TCP connection between A and F.
Assume that the nodes know their own IP addresses and the IP addresses of
3
Problem 2 (15 pts.)
Consider two co-located Slotted Aloha networks A and B both with infinite number of nodes. Both systems have the same slot size and same packet size (1-slot long). In both systems, old and new packets are transmitted according to a Poisson arrival process with arrival rates GA and GB (packets/time unit). The networks use a frequency hopping scheme. Namely, all the stations in a given network move to a new
frequency in every time slot. There are N possible frequencies and the new frequency is selected Uniformly
at random (i.e., every frequency has 1/N probability of being selected).
At a certain slot, if Network A operates on frequency f1 and Network B operates on frequency f2, even if
stations in both networks transmit simultaneously, their packets will not collide. If they operate on the same
frequency and stations in both networks transmit, their packets will collide.
A. (5 pt.) Given that in a certain slot there is a transmission in Network A, what is the probability of
success?
B. (5 pt.) What is the throughput of network A?
Now consider the case in which all nodes operate on the same frequency and network B is moved to
distance d≥0 from network A (i.e., it may take time until a packet from A arrives to B and vice versa).
Network A operates as described above. Network B now operates using the following simple version of
CSMA:
– Packets are one time unit long.
– Old and new packets arrive according to a Poisson arrival process.
– When a packet arrives, a node tries to transmit it (i.e., there are no slots in Network B).
– Before transmitting, a node senses the channel. The node can only detect transmissions from
network A. If it detects such a transmission, it does not transmit.
C. (5 pt.) In which case will the throughput of Network A be higher – when d > 0 or when d = 0?
Explain your answer (no need to compute anything).
Problem 3 (27 pts.) – Please answer on the exam form
Consider a Peer-to-Peer system with the overlay topology described below. The numbers represent the
delays on the links (assume that the delays are constant and known to the nodes).
In order to broadcast packets in the network, the nodes use the Propagation of Information (PI) algorithm,
discussed in class, with the following modifications:
1. A packet has a time to live (TTL) field.
2. Each node that receives a packet decrements the TTL by the delay value of the link on which the packet
arrived. When the TTL value £ 0, the packet is discarded.
Moreover, consider the version in which when a node sends a message it sends it to all its neighbors.
Node A wants to broadcast a packet containing a query. In order to limit its distribution, when the packet
is sent, node A sets TTL=8.
A. (10 pt.) Use the table below to describe the packets that will be sent (line 1 is an example and the table does not necessarily have to be full).
B. (10 pt.) Use the Dijkstra algorithm to compute the minimum TTL value for which all the nodes will
receive a copy of the query packet. Describe the operation of the Dijkstra algorithm in the table below and then indicate the TTL value.
C. (4 pt.) How many packets will be sent in the network when the revised PI algorithm (described above)
is used with the smallest value of TTL that guarantees that every node will receive a copy of the query
packet?
D. (3 pt.) Explain why the assumption that the delay on a link in a peer-to-peer system is constant is not
realistic.
6
Problem 4 (14 pts.)
Consider a TCP connection between hosts A and B that are connected by a standard point-to-point link in
which the packets arrive in order.
§ Host A is sending data to host B.
§ Host A has an infinite amount of bytes to send.
§ The round trip time is 6 seconds.
§ The MSS is 500 bytes.
§ The time to transmit a segment with 500 bytes is 1 second.
§ Assume that the time to transmit an ACK is negligible.
§ Assume that an ACK is transmitted immediately after a packet is received.
§ Segments and ACKs do not fail.
§ There is no flow control mechanism.
A. (7pts) Host A starts the connection establishment process at time 0. How many data bytes will be
received by host B after (i) 10 seconds? (ii) 20 seconds? Explain your computations and use figures
if necessary.
Now, assume that there is also a flow control mechanism with the following characteristics:
§ The buffer size at host B is 1000 bytes.
§ Host B reads segments from the buffer at the rate of 500 bytes per second.
§ Reading the segments from the buffer starts once the full segment has been received by host B.
B. (7pts) Host A starts the connection establishment process at time 0. How many data bytes will be
received by host B within: (i) the first 10 seconds? (ii) the first 20 seconds? (iii) the first 30 seconds?
Explain your computations and use figures if necessary.
Problem 5 (12 pts.) (Please write concise answers – wrong/unrelated information can result in point
deduction)
1. Assume that all the DNS root servers are shut down by an attack. What would be the consequences?
2. Describe the different types of the resource records – A, NS, MX.
3. What header fields can be changed by NAT?
4. Why do HTTP, SMTP, and POP3 run on top of TCP rather than on UDP?
7
Problem 6 (12 pts.) – Answer with True or False (in the notebook, not on the exam form)
1. A router can be associated with multiple IP addresses.
2. BGP is a link state protocol.
3. The window size used by TCP is the minimum of the congestion window and the flow control window. 4. TCP Fast Retransmit follows a timeout event
