Networked Life-Homework 7 Congestion and TCP Solved

Exercise 1. Congestion and TCP  
 

 

Figure 1:Flow allocation: two links, three users 

 

In the  

 

Figure 1  above, links are represented by tubes: User A is using both links, while each of users 1 and 2 requests one of the two links. All links have the same capacity C.

1.  Suppose all users have utility 𝑈(𝑥) = log(𝑥). What is the optimal allocation to maximize social welfare?

 

2.  Now look at the TCP utility function

𝑈  , 𝑅𝑇𝑇    

                                                                                             𝑅𝑇𝑇                                                                                           √2⁄3

and find the optimal allocation to maximize social welfare.

3.  Finally find the optimal allocation to maximize throughput, i.e, use 𝑈(𝑥) = 𝑥.

4.  What happens when the number of bottom users is 𝑛, as in the Figure 2  below, and links have capacity? Which allocations are still “fair”? Compare the three different methods.

 

 

 

                  User 1, 𝑥1       User 2, 𝑥2                     User n, 𝑥𝑛 
  

User A, 𝑥𝐴                                                          

 

Figure 2:Flow allocation: n links, n + 1 users 

 

 

Exercise 2.
Consider the case of 2 links 1,2, with capacities 𝐶1,𝐶2. Flow 1 uses both links 1,2, and flow 2 uses only link 2. Assume that the utility functions of the flows are identical and equal to

 

𝑈(𝑥) = 2√𝑥. We don’t make any assumptions about the relative size of 𝐶1 and 𝐶2. The purpose of this exercise is to make you acquainted with the solution of maximization problems with inequality constraints. In particular, link 1 may not be full at the optimum and the corresponding price may be zero. An obvious case is when 𝐶1 𝐶2, since 𝑥1 ≤ 𝐶1. But this could happen even when 𝐶1 < 𝐶2 as we will see in this exercise.

 

 

 

1.    Compute the optimum solution 𝑥1,𝑥2 of NUM (which also corresponds to the market equilibrium) and the corresponding link prices 𝜆1,𝜆2. Show that 𝜆1 = 0 iff  𝐶  .  

A way to understand this is as follows: suppose that 𝐶1 = ∞ and hence only link 2 matters. Then the equilibrium prices are 𝜆1 = 0,  𝜆2 0 for which 𝑥1 = 𝑥2 = 𝐶2/2 since the utilities are identical. Now let’s start decreasing 𝐶1. This can limit only flow 1. Since 𝑥1 = 𝐶2/2, there will be no restriction (and hence no price 𝜆1 increase) unless 𝐶1 < 𝐶2/2. But you need to derive this by solving the optimization equation. 

 

2.    Assume that there are 𝑘 identical copies of flow 2 passing only through link 2. What will be the solution in this case? What are the conditions on capacities so that 𝜆1 = 0?  

Hint: do it for 𝑘 = 2 and see how it will generalize for arbitrary 𝑘.

Lesson: Link 1 becomes bottleneck, i.e., restricts flow 1 only if there is not enough  competition in the rest of the path of this flow (in our case, in link 2).  

 

 

Exercise 3. A closer look at TCP  ) 
We look at the two most important parameters of the TCP algorithm. We call congestion window (cwind) the number of packets that the sender will send at each time step. The slowstart threshold (ssthreshold), given in number of packets, encodes our belief about congestion. We believe that if the number of packets we send is below ssthreshold, then congestion is low. On the other hand, we want to be more careful if we are sending a number of packets higher than ssthreshold.

Both numbers are determined by the TCP algorithm. The version we study here can be in four different states:

    Slow-start: cwind is doubled at each time step until the slow-start threshold (ssthreshold) is reached.

  Congestion avoidance: cwind increases linearly at each time step.

 Triple duplicate ACK (Packet loss 1): The sender receives a triple duplicate acknowledgement. This does not indicate severe congestion, since something is coming through. Thus the TCP algorithm sets the ssthreshold to half of the current cwind, decreases cwind to that level and goes to congestion avoidance state.

    Timeout event (Packet loss 2): This time, the sender receives nothing, so assumes the packets are not going through at all. It sets ssthreshold to half of the current cwind, restarts the TCP algorithm at cwind = 1 and goes to slow-start state.

To synthesize, the algorithm is either optimistic (doubles the number of packets it sends at each time step) or careful (increases the number of packets it sends by 1 at each time step). Meanwhile, it has to respond to packet loss events. When they happen, it sets the ssthreshold to half of the current cwind level. Depending on whether the packet loss is of type 1 or type 2, it either sets cwind to be half of its previous value and is careful, or sets cwind to 1 packet and is optimistic.

Use the above terminology to explain the sequence of events in the following graph. Give for each event the value of ssthreshold and cwind before and after the event.

  

Figure 3: An example of TCP 

 

Exercise 4. Long fat pipes
This exercise introduces the problem of ``long fat pipes''. We would like you to understand why the usual definition of TCP, due to its slow window increase, might be inadequate for links where the bandwidth-delay product is very large (either because the speed of the link is many Gbps or because the delay is long as in the case of satellite links, where delays can be 800ms and more).

We assume that TCP is used for sending data over a given data connection. We have already defined the bandwidth-delay product 𝐵𝐷𝑃 as 𝐵𝑊 × 𝑅𝑇𝑇𝑑, where 𝐵𝑊 is the bitrate of the data connection (at the bottleneck link) and 𝑅𝑇𝑇𝑑 is the total delay in the forward and backward path. The 𝐵𝐷𝑃 corresponds then to the maximum amount of bits that can travel on the communication medium (not in the intermediate buffers, which are anyway not relevant in this simple case). For an example of calculating such BDPs see Wikipedia[1]. In the following, it may be easier to work with the rate of packets sent. We assume that the size of a packet is 1460 bytes, so we can get the maximum number of packets that can travel over the link as the BDP divided by the size of a packet in bits.

Assumptions: Since the TCP window size is a 16-bit field in the TCP packet header, it limits the maximum size of the TCP window to 65535 bytes (because TCP ACKs refer to the last correctly received byte in its actual implementation), which corresponds to a maximum window size of 𝑀𝐴𝑋 = 44 packets (we assumed packet size = 1460 bytes). Let's forget that discussion about bytes and assume from now on that each ACK acknowledges correctly received packets, as we did in class.

We assume that TCP uses ``congestion avoidance'', i.e., increases its window size 𝑊 by one (packet) every 𝑅𝑇𝑇𝑑 starting initially from 𝑊 = 1, and each time there is a loss it halves it (but we will not have to deal with losses in this analysis as you will see).

In the next questions we assume that the sender and the receiver are directly connected through this bi-directional link with no intermediate router (intermediate queue), and that the receiver can process packets at the maximum speed of the link (hence no losses) and acknowledge back to the sender.

1.    Why is it true that in general for TCP to use effectively a connection it must reach a window size at least equal to the BDP?

2.    In our specific case of single link network, is it true that the 𝐵𝐷𝑃 is achieved when the sender transmits continuously at the maximum speed the link allows? Is it true that for physical reasons there is no way to increase further its window? Hence in this case 𝐵𝐷𝑃 (in packets) is an upper bound on the maximum achievable window size?

3.    Assuming your answer is yes in the previous question, and that a single TCP connection is using the link, is it true that the evolution of its window size W is extremely simple: increase linearly from zero until  𝑊 = mi n(𝑀𝐴𝑋, 𝐵𝐷𝑃) and then stay constant at this maximum value?

4.    Consider a local LAN link such as an Ethernet link, connecting the sender and the receiver with 10Mbps, and 𝑅𝑇𝑇𝑑 = 2𝑚𝑠. What is the 𝐵𝐷𝑃? Is TCP eventually constrained by 𝑀𝐴𝑋 or 𝐵𝐷𝑃? What is the maximum rate achievable? How much time does it take to reach this maximum rate?

5.    Consider a fiber optic link of 10 𝐺𝑏𝑝𝑠 and  𝑅𝑇𝑇𝑑 = 20𝑚𝑠. Repeat the previous questions. What do you observe?

  

6.    Suppose we remove the constraint that TCP uses the 𝑀𝐴𝑋 window size, i.e., we set 𝑀𝐴𝑋 = ∞. Repeat the previous question. What is the main issue here?

7.    Suppose that we double the window size every 𝑅𝑇𝑇𝑑 (again assuming 𝑀𝐴𝑋 = ∞.). How much time does it take to reach the maximum rate?

8.    Think of the time it takes to transmit a file of say 20 𝑀𝑏𝑦𝑡𝑒𝑠. Compare the time it takes if we use TCP (as in the previous question) and the time if we could use 100% of the

10𝐺𝑏𝑝𝑠 link.

 


 
[1] https://en.wikipedia.org/wiki/Bandwidth-delay\_product