Problem Set 3 Solution

Problem 1 (10pts)

Consider a network with MPLS enabled routers as shown in Figure 1 below. We would like to perform traffic engineering using MPLS so that traffic from R1 to R6 will be routed as R1-R3-R5-R6-A and traffic from R2 to R6 will be routed as R2-R3-R4-C.



Figure 1. MPLS enabled network for Problem 1




Please fill in the following tables of MPLS entries for each router.







R1
In

label
Out

label
Dst
Out

interface
-
1
A
0



R2
In

Label
Out

Label
Dst
Out

interface
-
2
C
0



R3
In

label
Out

label
Dst
Out

interface






















R4
In

label
Out

label
Dst
Out

interface
3
-
C
0














R5
In

label
Out

label
Dst
Out

interface
4
5
A
0






R6
In

label
Out

label
Dst
Out

interface























Problem 2 (20pts)



Figure 2. Network setup for Problem 2.




The Figure 2. above is a typical home network setup. An ISP Modem provides internet service; a wireless router is connected to the ISP Modem via Ethernet. Hosts A, B and C are connected to the wireless router to access the Internet.

In order for the hosts A, B, and C to access the Web Server, Network Address Translation (NAT) with random port mapping needs to be enabled for both the Wireless Router and the ISP Modem. Assume Hosts will pick a random port number between 8000 and 9000, the Wireless Router can choose a random port number between 2000 and 2500, and the ISP Modem can choose a random port number between 3000 and 4000. Please fill in the NAT table for the Wireless Router and the ISP Modem below.



NAT Table of Wireless Router
LAN side
WAN side



























NAT Table of ISP Modem
LAN side
WAN side





















Now we look into the details about how packets are exchanged between Host B and Web Server. Assume Host B sends a HTTP request packet to Web Server. And Web Server then sends HTTP content back to Host B. Please fill in the tables below to show how the packet’s IP header changed along the route. (Please formulate your answer based on your answers for (a). )



HTTP request Before entering Router
Src IP


Src Port


Dst IP


Dst Port








HTTP request After exiting Router
Src IP


Src Port


Dst IP


Dst Port














HTTP request After exiting Modem
Src IP


Src Port


Dst IP


Dst Port








HTTP response Before entering Modem
Src IP


Src Port


Dst IP


Dst Port








HTTP response After exiting Modem
Src IP


Src Port


Dst IP


Dst Port








HTTP response After exiting Router
Src IP


Src Port


Dst IP


Dst Port


 

Suppose now Host A also runs a webserver on port 8888, it is attached to a domain name http://www.mylocalhomeserver.com, explain what NAT entries should be added so that people from the internet can assess this webserver via URL. You can assume that the above domain name is registered properly.







































The wireless link at the last mile is very error prone and you would like to improve the performance. What would you do in this case?








































































Problem 3 (10pts)

Suppose a router has three input flows and one output flow. It receives the packets listed in the Table 1. below, all at about the same time, in the order listed, during a period in which the output port is busy but all queues are otherwise empty. Give the order in which the packets are transmitted, assuming:

Fair queuing






























Weighted fair queuing with flow 2 having twice as much share as flow 1, and flow 3 having 1.5 times as much share as flow 1. Note that ties are to be solved in the order of flow1, flow2 and flow3.


















Packet
Size
Flow
1
200
1
2
200
1
3
160
2
4
200
2
5
160
2
6
210
3
7
120
3
8
90
3



Table 1.




Problem 4 (15pts)






Figure 3. Congestion Window Size




Assuming TCP Reno is the protocol experiencing the behavior shown above, answer the following questions:




Identify the RTT rounds when TCP runs Slow Start (e.g., from the 1th round to which round?)



Identify the RTT rounds when TCP runs Congestion Avoidance



After the 14th RTT round, is segment loss detected by a triple duplicate ACK or by a timeout and why?



During which RTT round the 170th segment is sent?



Assuming a packet loss is detected after the 23th RTT round by the receipt of triple duplicate ACKs, what will be the value of the congestion window?









Problem 5 (15pts)

Figure 4. below shows how 2 disconnected LAN are connected by IP tunnel (the dash line). For each interface the IP and MAC addresses are shown in the figure. (HW1- HW14 are used to represent hardware addresses)






Figure 4. Network setup for Problem 5




Now Host B sends a packet to Host A. Please show how the packet travels along the route, please describe header information along the route.





























































Problem 6 (20pts)




Derive the expected throughput of the following TCP congestion control algorithm: The additive increment factor is α. Multiplicative decrease factor β, which means after loss, the windows size will change from W to (1-β)W. Please order the throughput for each flow. AIMD(a,b) means the cwnd increases a per each round trip time and the cwnd set to (1-b)W from W when the loss happens.




Flow1: AIMD(a=1,b=0.5), RTT=10ms, loss rate = 10-6

Flow2: AIMD(a=2,b=0.2), RTT=100ms, loss rate = 10-8

Flow3: AIMD(a=5,b=0.8), RTT=300ms, loss rate = 10-9

Flow4: AIMD(a=8,b=0.4), RTT=1000ms, loss rate = 10-4

Flow5: AIMD(a=6,b=0.5), RTT=100ms, loss rate = 10-10






















Problem 7 (10pts)




Suppose that TCP uses the combination of quick acknowledgements (quick ack) and delayed acknowledgements (delayed ack). The quick ack only triggers up to 8 packets (the cwnd at the sender becomes 16 after receiving 8 quick acks) starting from 1 packet during slow start. The maximum capacity of the link is 5000 KBps, the RTT is 10ms, and 1MSS = 1KB. Note that KBps is KB per second).










About what is cwnd at the time of first packet loss?






























About how long until sender discovers first loss?