Rate adaptation, Congestion Control and Fairness: A Tutorial. JEAN-YVES LE BOUDEC Ecole Polytechnique Fédérale de Lausanne (EPFL) - PDF

Rate adaptation, Congestion Control and Fairness: A Tutorial JEAN-YVES LE BOUDEC Ecole Polytechnique Fédérale de Lausanne (EPFL) September 12, Thanks to all who contributed to reviews and debugging

Please download to get full document.

View again

of 21
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Food & Beverages

Publish on:

Views: 51 | Pages: 21

Extension: PDF | Download: 0

Rate adaptation, Congestion Control and Fairness: A Tutorial JEAN-YVES LE BOUDEC Ecole Polytechnique Fédérale de Lausanne (EPFL) September 12, 2014 2 Thanks to all who contributed to reviews and debugging of this document, in particular B. Radunovic, M. Vojnovic and Miroslav Popovic. Contents 1 Congestion Control for Best Effort: Theory The objective of congestion control Congestion Collapse Efficiency versus Fairness Fairness Max-Min Fairness Proportional Fairness Utility Approach to Fairness Max Min Fairness as a limiting case of Utility Fairness Different forms of congestion control Max-min fairness with fair queuing Additive increase, Multiplicative decrease and Slow-Start Additive Increase, Multiplicative Decrease Slow Start The fairness of additive increase, multiplicative decrease with FIFO queues A simplified model Additive Increase, Multiplicative Decrease with one Update per RTT Additive Increase, Multiplicative Decrease with one Update per Packet Summary Congestion Control for Best Effort: Internet Congestion control algorithms of TCP Congestion Window Slow Start and Congestion avoidance Fast Recovery The fairness of TCP Summary and Comments Other Mechanisms for Congestion Control TCP Friendly Applications Active Queue Management 4 CONTENTS Explicit Congestion Notification Summary CHAPTER 1 CONGESTION CONTROL FOR BEST EFFORT: THEORY In this chapter you learn why it is necessary to perform congestion control the additive increase, multiplicative decrease rule the three forms of congestion control schemes max-min fairness, proportional fairness This chapter gives the theoretical basis required for Congestion Control in the Internet. 1.1 THE OBJECTIVE OF CONGESTION CONTROL CONGESTION COLLAPSE Consider a network where sources may send at a rate limited only by the source capabilities. Such a network may suffer of congestion collapse, which we explain now on an example. We assume that the only resource to allocate is link bit rates. We also assume that if the offered traffic on some link l exceeds the capacity c l of the link, then all sources see their traffic reduced in proportion of their offered traffic. This assumption is approximately true if queuing is first in first out in the network nodes, neglecting possible effects due to traffic burstiness. Consider first the network illustrated on Figure 1.1. Sources 1 and 2 send traffic to destination nodes D1 and D2 respectively, and are limited only by their access rates. There are five links labeled 1 through 5 with capacities shown on the figure. Assume sources are limited only by their first link, without feedback from the network. Call λ i the sending rate of source i, and λ i the outgoing rate. For example, with the values given on the figures we find λ 1 = 100kb/s and λ 2 = 1000kb/s, but only λ 1 = λ 2 = 10kb/s, and the total throughput is 20kb/s! Source 1 can send only at 10 kb/s because it is competing with source 2 on link 3, which sends at a high rate on that link; however, source 2 is limited to 10 kb/s because of link 5. If source 2 would be aware of the global situation, and if it would cooperate, then it would send at 10 kb/s only already on link 2, which would allow source 1 to send at 100 kb/s, without any penalty for source 2. The total throughput of the network would then become θ = 110kb/s. 5 6 CHAPTER 1. CONGESTION CONTROL FOR BEST EFFORT: THEORY Source 1 1 link 1 c1 = 100 kb/s link 3 c3 = 110 kb/s link 4 c4 = 100 kb/s D1 X Y 2 Source 2 link 2 c2 = 1000 kb/s link 5 c5 = 10 kb/s D2 Figure 1.1: A simple network exhibiting some inefficiency if sources are not limited by some feedback from the network The first example has shown some inefficiency. In complex network scenarios, this may lead to a form of instability known as congestion collapse. To illustrate this, we use the network illustrated on Figure 1.2. The topology is a ring; it is commonly used in many networks, because it is a simple way to provide some redundancy. There are I nodes and links, numbered 0, 1,..., I 1. Source i enters node i, uses links [(i + 1) mod I] and [(i + 2) mod I], and leaves the network at node (i + 2) mod I. Assume that source i sends as much as λ i, without feedback from the network. Call λ i the rate achieved by source i on link [(i+1) mod I] and λ i the rate achieved on link [(i+2) mod I]. This corresponds to every source choosing the shortest path to the destination. In the rest of this example, we omit modi when the context is clear. We have then: ) λ i (λ = min c i, i λ i λ +λ i ( i 1 ) λ i = min λ i, (1.1) c i+1 λ i +λ λ i+1 i I K H? A A E E E E A E E E Figure 1.2: A network exhibiting congestion collapse if sources are not limited by some feedback from the network Applying Equation 1.1 enables us to compute the total throughput θ. In order to obtain a closed form solution, we further study the symmetric case, namely, we assume that c i = c and λ i = λ for all i. Then we have obviously λ i = λ and λ i = λ for some values of λ and λ which we compute now. If λ c 2 then there is no loss and λ = λ = λ and the throughput is θ = Iλ. Else, we have, from Equation (1.1) λ = cλ λ + λ We can solve for λ (a polynomial equation of degree 2) and obtain λ = λ 2 ( c ) λ & $ 1.1. THE OBJECTIVE OF CONGESTION CONTROL 7 We have also from Equation (1.1) Combining the last two equations gives λ = cλ λ + λ ( cλ 1 ) λ = c λ 2 Using the limited development, valid for u 0 we have 1 + u = u 1 8 u2 + o(u 2 ) λ = c2 λ + o( 1 λ ) Thus, the limit of the achieved throughput, when the offered load goes to +, is 0. This is what we call congestion collapse. Figure 1.3 plots the throughput per source λ as a function of the offered load per source λ. It confirms that after some point, the throughput decreases with the offered load, going to 0 as the offered load goes to +. %! ' #!! % ! ' # # $ $ % %! % ' & # ' ' % Figure 1.3: Throughput per source as a function of the offered load per source, in Mb/s, for the network of Figure 1.2. Numbers are in Mb/s. The link rate is c = 20Mb/s for all links. The previous discussion has illustrated the following fact: FACT (Efficiency Criterion). In a packet network, sources should limit their sending rate by taking into consideration the state of the network. Ignoring this may put the network into congestion collapse. One objective of congestion control is to avoid such inefficiencies. Congestion collapse occurs when some resources are consumed by traffic that will be later discarded. This phenomenon did happen in the Internet in the middle of the eighties. At that time, there was no end-to-end congestion control in TCP/IP. As we will see in the next section, a secondary objective is fairness EFFICIENCY VERSUS FAIRNESS Assume that we want to maximize the network throughput, based on the considerations of the previous section. Consider the network example in Figure 1.4, where source i sends at a rate x i, i = 0, 1..., I, and 8 CHAPTER 1. CONGESTION CONTROL FOR BEST EFFORT: THEORY all links have a capacity equal to c. We assume that we implement some form of congestion control and that there are negligible losses. Thus, the flow on link i is n 0 x 0 + n i x i. For a given value of n 0 and x 0, maximizing the throughput requires that n i x i = c n 0 x 0 for i = 1,..., I. The total throughput, measured at the network output, is thus Ic (I 1)n 0 x 0 ; it is maximum for x 0 = 0! n0 Type 0 Sourcesat rate x0 link i capacity c ni Type i Sourcesat rate xi Figure 1.4: A simple network used to illustrate fairness (the parking lot scenario) The example shows that maximizing network throughput as a primary objective may lead to gross unfairness; in the worst case, some sources may get a zero throughput, which is probably considered unfair by these sources. In summary, the objective of congestion control is to provide both efficiency and some form of fairness. We will study fairness in more detail now. 1.2 FAIRNESS MAX-MIN FAIRNESS In a simple vision, fairness simply means allocating the same share to all. In the simple case of Figure 1.4 with n i = 1 for all i, this would mean allocating x i = c 2 to all sources i = 0,..., I. However, in the case of a network, such a simple view does not generally make sense. Consider again the example of Figure 1.4, now with general values for n i. If we follow the previous line c of reasoning, we would allocate the fraction n 0 +n i to each of the n 0 + n i sources using link i. This yields x i = c n 0 +n i for i 1; for i = 0, the reasoning of the previous section indicates that we should allocate c x 0 = min 1 i I n 0 +n i. For example, with I = 2, n 0 = n 1 = 1 and n 2 = 9, we would allocate x 0 = 0.1c, x 1 = 0.5c and x 2 = 0.1c. This allocation however would not fully utilize link 1; we could decide to increase the share of sources of type 1 since this can be done without decreasing the shares of other sources. Thus, a final allocation could be x 0 = 0.1c, x 1 = 0.9c and x 2 = 0.1c. We have illustrated that allocating resources in an equal proportion is not a good solution since some sources can get more that others without decreasing others shares. Formally, this leads to our first definition of fairness called max-min fairness. Consider an allocation problem; define the vector x whose ith coordinate is the allocation for user i. Let X be the set of all feasible allocations. DEFINITION (Max-min Fairness). [2]A feasible allocation of rates x is max-min fair if and only if an increase of any rate within the domain of feasible allocations must be at the cost of a decrease of some already smaller rate. Formally, for any other feasible allocation y, if y s x s then there must exist some s such that x s x s and y s x s. Depending on the problem, a max-min fair allocation may or may not exist. However, if it exists, it is unique 1.2. FAIRNESS 9 (see later for a proof). We develop the theory in a special case where existence is always guaranteed. For a general set of results, see [Radunovic02-Allerton]. NETWORK MODEL We use the following simplified network model in the rest of this section. We consider a set of sources s = 1,..., S and links 1,..., L. Let A l,s be the fraction of traffic of source s which flows on link l, and let c l be the capacity of link l. We define a network as the couple ( x, A). A feasible allocation of rates x s 0 is defined by: S s=1 A l,sx s c l for all l. Our network model supports both multicast and load sharing. For a given source s, the set of links l such that A l,s 0 is the path followed by the data flow with source s. In the simplest case (no load sharing), A l,s {0, 1}; if a flow from source s is equally split between two links l 1 and l 2, then A l1,s = A l2,s = 0.5. In principle, A l,s 1, but this is not mandatory (in some encapsulation scenarios, a flow may be duplicated on the same link). It can be seen (and this is left as an exercise) that the allocation in the previous example is max-min fair. The name max-min comes from the idea that it is forbidden to decrease the share of sources that have small values, thus, in some sense, we give priority to flows with small values. In general, we might ask ourselves whether there exists a max-min fair allocation to our network model, and how to obtain it. This will result from the key concept of bottleneck link. DEFINITION (Bottleneck Link). With our network model above, we say that link l is a bottleneck for source s if and only if 1. link l is saturated: c l = i A l,ix i 2. source s on link l has the maximum rate among all sources using link l: x s x s for all s such that A l,s 0. Intuitively, a bottleneck link for source s is a link which is limiting, for a given allocation. In the previous numerical, example, link 2 is a bottleneck for sources of type 0 and 2, and link 1 is a bottleneck for the source of type 1. THEOREM A feasible allocation of rates x is max-min fair if and only if every source has a bottleneck link. PROOF: Part 1. Assume that every source has a bottleneck link. Consider a source s for which we can increase the rate x s while keeping the allocation feasible. Let l be a bottleneck link for s. Since l is saturated, it is necessary to decrease x s for some s such that A l,s 0. We assumed that we can increase the rate of s: thus there must exist some s s that shares the bottleneck link l. But for all such s, we have x s x s, thus we are forced to decrease x s for some s such that x s x s : this shows that the allocation is max-min fair. Part 2. Conversely, assume that the allocation is max-min fair. For any source s, we need to find a bottleneck link. We proceed by contradiction. Assume there exists a source s with no bottleneck link. Call L 1 the set of saturated links used by source s, namely, L 1 = {l such that c l = i A l,ix i and A l,s 0}. Similarly, call L 2 the set of non-saturated links used by source s. Thus a link is either in L 1 or L 2, or is not used by s. Assume first that L 1 is non-empty. By our assumption, for all l L 1, there exists some s such that A l,s 0 and x s x s. Thus we can build a mapping σ from L 1 into the set of sources {1,..., S} such that A l,σ(l) 0 and x σ(l) x s (see Figure 1.5 for an illustration). Now we will show that we can increase the rate x s in a way that contradicts the max-min fairness assumption. We want to increase x s by some value δ, at the expense of decreasing x s by some other values δ s, for all s that are equal to some σ(l ). We want the modified allocation to be feasible; to that end, it is sufficient to have: 10 CHAPTER 1. CONGESTION CONTROL FOR BEST EFFORT: THEORY source σ(l1) link l1 source s link l2 source σ(l1) Figure 1.5: A network example showing one multicast source A l,s δ A l,σ(l) δ σ(l) for all l L 1 (1.2) A l,s δ c l A l,i x i i for all l L 2 (1.3) δ σ(l) x σ(l) for all l L 1 (1.4) Equation (1.2) expresses that the increase of flow due to source s on a saturated link l is at least compensated by the decrease of flow due to source σ(l). Equation (1.3) expresses that the increase of flow due to source s on a non-saturated link l does not exceed the available capacity. Finally, equation (1.4) states that rates must be non-negative. This leads to the following choice. δ = min{ x σ(l)a l,σ(l) } min{ c l i A l,ix i } (1.5) l L 1 l L 2 A l,s A l,s which ensures that Equation (1.3) is satisfied and that δ 0. In order to satisfy Equations (1.2) and (1.4) we need to compute the values of δ σ(l) for all l in L 1. Here we need to be careful with the fact that the same source s may be equal to σ(l) for more than one l. We define δ(s ) by δ(s ) = 0 if there is no l such that s = σ(l) (1.6) δ(s ) = max {l such that σ(l)=s }{ δa l,s A l,σ(l) } otherwise (1.7) This definition ensures that Equation (1.2) is satisfied. We now examine Equation (1.4). Consider some s for which there exists an l with σ(l) = s, and call l 0 the value which achieves the maximum in (1.7), namely: From the definition of δ in (1.5), we have δ(s ) = δa l 0,s A l0,s (1.8) δ x σ(l 0 )A l0,σ(l 0 ) A l0,s = x s A l 0,s A l0,s 1.2. FAIRNESS 11 Combined with (1.8), this shows that Equation (1.4) holds. In summary, we have shown that we can increase x s at the expense of decreasing the rates for only those sources s such that s = σ(l) for some l. Such sources have a rate higher than x s, which shows that the allocation x is not max-min fair and contradicts our hypothesis. It remains to examine the case where L 1 is empty. The reasoning is the same, we can increase x s without decreasing any other source, and we also have a contradiction. THE ALGORITHM OF PROGRESSIVE FILLING The previous theorem is particularly useful in deriving a practical method for obtaining a max-min fair allocation, called progressive filling. The idea is as follows. You start with all rates equal to 0 and grow all rates together at the same pace, until one or several link capacity limits are hit. The rates for the sources that use these links are not increased any more, and you continue increasing the rates for other sources. All the sources that are stopped have a bottleneck link. This is because they use a saturated link, and all other sources using the saturated link are stopped at the same time, or were stopped before, thus have a smaller or equal rate. The algorithm continues until it is not possible to increase. The algorithm terminates because L and S are finite. Lastly, when the algorithm terminates, all sources have been stopped at some time and thus have a bottleneck link. By application of Theorem 1.2.1, the allocation is max-min fair. EXAMPLE Let us apply the progressive filling algorithm to the parking lot scenario. Initially, we let x i = 0 for all i = 0,..., I; then we let x i = t until we hit a limit. The constraints are n 0 x 0 + n i x i c for all i = 1,..., I c Thus the first constraint is hit at t 1 = min{ n 0 +n i } and it concerns sources of type 0 and type i 0 for all values of index i 0 which minimize the expression above. Thus c x 0 = min{ } n 0 + n i In order to compute the rates for sources of other types, we continue to increase their rates. Now all constraints become independent and we finally have x i = c n 0x 0 n i If all n i s are equal, the we see that all sources obtain the same rate. In some sense, max-min fairness ignores the fact that sources of type 0 use more network resources than those of type i, i 1. In that case, the total throughput for the parking lot network is (I+1)c 2, which is almost half of the maximum admissible throughput of Ic. THEOREM For the network defined above, with fixed routing parameters A l,s, there exists a unique max-min fair allocation. It can be obtained by the algorithm of progressive filling. PROOF: We have already proven the existence. Assume now that x and y are two max-min fair allocations for the same problem, with x y. Without loss of generality, we can assume that there exists some i such that x i y i. Consider the smallest value of x i that satisfies x i y i, and call i 0 the corresponding index. Thus, x i0 y i0 and if x i y i then x i0 x i (1.9) Now since x is max-min fair, from Definition 1.2.1, there exists some j with y j x j x i0 (1.10) 12 CHAPTER 1. CONGESTION CONTROL FOR BEST EFFORT: THEORY Now y is also max-min fair, thus by the same token there exists some k such that Combining (1.10) and (1.11), we obtain x k y k y j (1.11) which contradicts (1.9). x k y k y j x j x i0 The notion of max-min fairness can be easily generalized by using weights in the definition [2, 16] PROPORTIONAL FAIRNESS The previous definition of fairness puts emphasis on maintaining high values for the smallest rates. As shown in the previous example, this may be at the expense of some network inefficiency. An alternative definition of fairness has been proposed in the context of game theory [20]. DEFINITION (Proportional Fairness). An allocation of rates x is proportionally fair if and only if, for any other feasible allocation y, we have: S s=1 y s x s x s 0 In other words, any change in the allocation must have a negative average change. Let us consider for example the parking lot scenario with n s = 1 for all s. Is the max-min fair allocation proportionally fair? To get the answer, remember that, for the max-min fair allocation, x s = c/2 for all s. Consider a new allocation resulting from a decrease of x 0 equal to δ: y 0 y s = c 2 δ = c 2 + δ s = 1,..., I For δ c 2, the new allocation y is feasible. The average rate of change is ( I s=1 ) 2δ 2δ c c = 2(I 1)δ c which is positive for I 2. Thus the max-min fair allocation for this example is not proportionally fair for I 2. In this example, we see that a decrease in rate for sources of type 0 is less important than the corresponding increase which is made possible for the other sources, because the increase is multiplied by the number of sources. Informally, we say that proportional fairness takes i
Related Search
Similar documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks