Question 1 (X marks)
Use separate answer booklet for each section SECTION 1 – Questions 1 – 4
An intelligent group of super speedy ants decide to set up a point-to-point link between two ant holes, denoted by hole A and hole B. Suppose the bandwidth of this “link” is 1000bps, or bread crumbs per second (you can imagine that each ant holds a bread crumb, and they leave hole A at a rate of 1000 ants per second). The distance from hole A to hole B is 100 meters, and the ants walk at a speed of 1 m/s.
(a) Calculate the Round Trip Time (RTT) for the link between the two holes.
(b) Using the delay as half the RTT (i.e. just going from A to B, not going back), calculate the delay x bandwidth product for the link, in bread crumbs.
(c) Suppose the queen ant in hole A sends a messenger ant to Hole B to request 10,000 bread crumbs (remember each ant holds exactly one bread crumb). Assume that 10,000 ants are ready to leave when the messenger arrive. What is the duration of time that will elapse between when the messenger departed the queen (i.e. hole A) and all 10,000 ants have arrived at hole A.
Question 2 (X marks)
Assume that the SendBase for a TCP Reno sender is currently 4000. The TCP sender has sent four TCP segments with sequence numbers 4000, 4500, 5500 and 7000. The sender then receives a segment with an acknowledgement number 7500 and a receive window 6000. The congestion window, CongWin, is set to 10000 bytes after this ACK is processed. Answer the questions (i)-(iii) assuming that this ACK is processed and no further ACKs are received:
(i) What is the value of SendBase?
(ii) How many bytes in total are sent in the four TCP segments?
(iii) What is the last byte (number) that the TCP sender can send with certainty that the
receiver’s buffer will not overflow?
Now assume that the sender receives three more TCP segments, such that all three segments have TCP acknowledgement number 7500. Answer the questions (iv)-(v) assuming that all three ACKs are processed and no further ACKs are received:
(iv) What is the value of CongWin?
(v) What is the sequence number of the next segment that will be sent?
Question 3 (X marks)
In the lecture (and in the text) we observed how the AIMD algorithm implemented by TCP enables two TCP connections sharing a bottleneck link to achieve a fair share of the bottleneck link capacity (see Figure 3.56 in the text). Suppose that instead of a multiplicative
2
decrease TCP decreased the window size by a constant amount. Would the resulting AIAD algorithm converge to an equal share algorithm? Justify your answer using a diagram similar to Figure 3.56.
Question 4 (X marks)
Consider that only a single TCP Reno connection uses one 10Mbps link which does not buffer any data. Suppose that this link is the only congested link between the sending and receiving hosts. Assume that the TCP sender has a huge file to send to the receiver and the receiver’s receive buffer is much larger than the congestion window. We also make the following assumptions: each TCP segment is 1,500 bytes; the two-way propagation delay of this connection is 150 msec; and this TCP connection is always in congestion avoidance phase, that is ignore slow start.
(a) What is the maximum window size (in segments) that this TCP connection can achieve?
(b) What is the average window size (in segments) and average throughput (in bps) of this TCP connection?
(c) How long would it take for this TCP connection to reach its maximum window again after recovering from a packet loss?
PLEASE TURN OVER
3
Question 5 (X marks)
Use separate answer booklet for each section SECTION 2 – Questions 5 – 8
Figure 1: Figure for Question 5
a) Consider the network topology shown in the figure above. Show the operation of Dijkstra’s link-state algorithm to compute routes from node A to all destinations.
b) Show the distance table that would be computed by the distance vector algorithm in A once the distance vector algorithm has finished executing. You do not have to run the distance vector algorithm; you should be able to compute the table by inspection. Note: make sure you have a row in the distance table for each neighbour of A.
c) Consider three instances of link failure: (i) Link A-B fails, (ii) Link A-C fails, and (iii) Link A-E fails. In each of these three cases, all links except the one mentioned are still active. In which of the three instances of link failure will the count-to-infinity problem occur? Describe briefly how this problem occurs for the chosen instance. Name a solution to the count-to-infinity problem.
Question 6 (X marks)
Sheldon Cooper is designing a Network Address Translator (NAT) device to use at home so that multiple computers share a single global IP address (nat ip).
(a) In his first attempt Sheldon designs a NAT, which maps an outgoing {source ip, source port, destination ip, destination port} tuple to {nat ip, new port, destination ip, destination port}. To his surprise, he finds that routers in the Internet drop every packet sent by his NAT. What is missing in Sheldon’s NAT design?
(b) Now assume that Sheldon has corrected the above problem. He now finds that he can successfully browse the Web through the NAT, but he cannot use FTP. Why?
4
Question 7 (X marks)
Assume that the forwarding table of a router is as follows:
Which interface would the datagrams with the following destination IP address be forwarded to?
(a) 128.96.171.92 (b) 128.96.167.151 (c) 128.96.163.151 (d) 128.96.169.192 (e) 128.96.165.121
Question 8 (X marks)
Let’s consider the operation of a self-learning Ethernet switch in the context of a network in which 6 nodes labelled A through F are star connected into the self-learning switch (one node connected to each link). Suppose that (i) B sends a frame to E, (ii) E replies with a frame to B, (iii) A sends a frame to B, (iv) B replies with a frame to A. The switch table is initially empty. Show the state of the switch table before and after each of these events. For each of these events, identify the link(s) on which the transmitted frame will be forwarded, and briefly justify your answers.
Prefix
Link Interface
128.96.170.0/23
0
128.96.168.0/23
1
128.96.166.0/23
2
128.96.164.0/22
3
Default
4
PLEASE TURN OVER
5
Question 9 (X marks)
Use separate answer booklet for each section SECTION 3 – Questions 9 – 12
Why doesn’t 802.11 implement collision detection? What compensation mechanism does it implement?
Question 10 (X marks)
Consider the wireless network composed of four nodes in Figure 2, which has a linear topology deployed along a highway. The distance between neighbouring nodes is equal. Assume all nodes are using 802.11 MAC with RTS/CTS enabled. The radio range for each node is fixed, and this radio range is slightly longer than the inter-node distance, i.e., each node can reach only its left and right neighbours. Assume that if there are two simultaneous transmissions within the radio range of the receiver, both transmissions will be unsuccessful.
ABCD
Figure 2: Figure for Question 10
(a) Assume that node A is currently sending a data frame (not an ACK, an RTS, or a CTS) to node B. Node C wants to send a packet to node D. Assume that node C (and only C) ignores the 802.11 MAC and sends the packet. Would C’s packet arrive successfully at D? Would A’s packet arrive successfully at B? Explain your reasoning.
(b) Consider the same situation as above except that all nodes are using the 802.11 MAC. Will C start transmission while A is sending the data packet? Why or why not? If not, how does C know that A is transmitting a data frame?
(c) Is there any way for C to know when A’s transmission will end? Explain.
Question 11 (X marks)
Suppose Alice wants to send a message to Bob. Bob has a public-private key pair (KB+, KB-), and Alice has Bob’s certificate. But Alice does not have a public, private key pair. Alice and Bob share the same hash function H(.)
(a) In this situation, is it possible to design a scheme so that Bob can verify that Alice created the message? If so, show how with a block diagram for Alice and Bob.
(b) Is it possible to design a scheme that provides confidentially for sending the message from Alice to Bob? If so, show how with a block diagram for Alice and Bob.
6
Question 12 (X marks)
Consider the scenario depicted in Figure 3. The device installed between the public Internet and the local site functions both as a packet filter and an application gateway. Using the table on the next page, fill in the values that achieve the following policies. Assume that any policies not mentioned below are disallowed. Note that you may or may not need to fill in all rows. The first rule is already filled in, as an example.
• Any external host can access HTTP Server 1.
• Any external host can access the SMTP Server.
• Only the HTTP client in Figure 7 can access HTTP Server 2.
• HTTP is allowed from any internal host to any external host.
• BitTorrent is allowed between any internal and external peers, in either direction
except for the SMTP server.
• Outgoing SMTP is allowed only from the SMTP server.
The rules are applied in the order R1, R2, ….
(Hint: When you fill in the rules, be careful of the order of the rules)
25.5.6.7
Internet
98.2.3.4
Firewall/ Application Gateway
HTTP Server 1
Internal Site
Figure 3: Figure for Question 12
SMTP Server
98.4.5.6
98.3.4.5
HTTP Server 2
Rule
Source
Destination
Application
Action
R1
Any-outside
98.2.3.4
HTTP
Allow
R2
R3
R4
R5
R6
R7
R8
R9
R10
R11
Note: Redraw this table in your answer booklet. Do not write on the question booklet. It is not necessary that you MUST fill in all rows in the table above.
END OF EXAM
PLEASE TURN OVER
7
HTTP Client