2. cnp3-ebook
3. principles/sharing
4. English
5. Zen

149 ../../principles/sharing.rst:934
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — The congestion control scheme should be `fair`. Most congestion schemes aim at achieving `max-min fairness`. An allocation of transmission rates to sources is said to be `max-min fair` if : 189/10000 · 189
150 ../../principles/sharing.rst:936
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — no link in the network is congested 35/10000 · 35
151 ../../principles/sharing.rst:937
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — the rate allocated to source :math:`j` cannot be increased without decreasing the rate allocated to a source :math:`i` whose allocation is smaller than the rate allocated to source :math:`j` [Leboudec2008]_ . 208/10000 · 208
152 ../../principles/sharing.rst:939
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Depending on the network, a `max-min fair allocation` may not always exist. In practice, `max-min fairness` is an ideal objective that cannot necessarily be achieved. When there is a single bottleneck link as in the example above, `max-min fairness` implies that each source should be allocated the same transmission rate. 322/10000 · 322
153 ../../principles/sharing.rst:941
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — To visualize the different rate allocations, it is useful to consider the graph shown below. In this graph, we plot on the `x-axis` (resp. `y-axis`) the rate allocated to host `B` (resp. `A`). A point in the graph :math:`(r_B,r_A)` corresponds to a possible allocation of the transmission rates. Since there is a `2 Mbps` bottleneck link in this network, the graph can be divided into two regions. The lower left part of the graph contains all allocations :math:`(r_B,r_A)` such that the bottleneck link is not congested (:math:`r_A+r_B<2`). The right border of this region is the `efficiency line`, i.e. the set of allocations that completely utilize the bottleneck link (:math:`r_A+r_B=2`). Finally, the `fairness line` is the set of fair allocations. 753/10000 · 753
154 ../../principles/sharing.rst:947
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Possible allocated transmission rates 37/10000 · 37
155 ../../principles/sharing.rst:950
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — As shown in the graph above, a rate allocation may be fair but not efficient (e.g. :math:`r_A=0.7,r_B=0.7`), fair and efficient ( e.g. :math:`r_A=1,r_B=1`) or efficient but not fair (e.g. :math:`r_A=1.5,r_B=0.5`). Ideally, the allocation should be both fair and efficient. Unfortunately, maintaining such an allocation with fluctuations in the number of flows that use the network is a challenging problem. Furthermore, there might be several thousands flows that pass through the same link [#fflowslink]_. 506/10000 · 506
156 ../../principles/sharing.rst:952
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — To deal with these fluctuations in demand, which result in fluctuations in the available bandwidth, computer networks use a congestion control scheme. This congestion control scheme should achieve the three objectives listed above. Some congestion control schemes rely on a close cooperation between the end hosts and the routers, while others are mainly implemented on the end hosts with limited support from the routers. 422/10000 · 422
157 ../../principles/sharing.rst:954
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — A congestion control scheme can be modeled as an algorithm that adapts the transmission rate (:math:`r_i(t)`) of host :math:`i` based on the feedback received from the network. Different types of feedback are possible. The simplest scheme is a binary feedback [CJ1989]_ [Jacobson1988]_ where the hosts simply learn whether the network is congested or not. Some congestion control schemes allow the network to regularly send an allocated transmission rate in Mbps to each host [BF1995]_. 487/10000 · 487
158 ../../principles/sharing.rst:959
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Let us focus on the binary feedback scheme which is the most widely used today. Intuitively, the congestion control scheme should decrease the transmission rate of a host when congestion has been detected in the network, in order to avoid congestion collapse. Furthermore, the hosts should increase their transmission rate when the network is not congested. Otherwise, the hosts would not be able to efficiently utilize the network. The rate allocated to each host fluctuates with time, depending on the feedback received from the network. The figure below illustrates the evolution of the transmission rates allocated to two hosts in our simple network. Initially, two hosts have a low allocation, but this is not efficient. The allocations increase until the network becomes congested. At this point, the hosts decrease their transmission rate to avoid congestion collapse. If the congestion control scheme works well, after some time the allocations should become both fair and efficient. 991/10000 · 991
159 ../../principles/sharing.rst:965
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Evolution of the transmission rates 35/10000 · 35
160 ../../principles/sharing.rst:968
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Various types of rate adaption algorithms are possible. `Dah Ming Chiu`_ and `Raj Jain`_ have analyzed, in [CJ1989]_, different types of algorithms that can be used by a source to adapt its transmission rate to the feedback received from the network. Intuitively, such a rate adaptation algorithm increases the transmission rate when the network is not congested (ensure that the network is efficiently used) and decrease the transmission rate when the network is congested (to avoid congestion collapse). 505/10000 · 505
161 ../../principles/sharing.rst:970
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — The simplest form of feedback that the network can send to a source is a binary feedback (the network is congested or not congested). In this case, a `linear` rate adaptation algorithm can be expressed as : 206/10000 · 206
162 ../../principles/sharing.rst:972
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — :math:`rate(t+1)=\alpha_C + \beta_C rate(t)` when the network is congested 74/10000 · 74
163 ../../principles/sharing.rst:973
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — :math:`rate(t+1)=\alpha_N + \beta_N rate(t)` when the network is *not* congested 80/10000 · 80
164 ../../principles/sharing.rst:975
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — With a linear adaption algorithm, :math:`\alpha_C,\alpha_N, \beta_C` and :math:`\beta_N` are constants. The analysis of [CJ1989]_ shows that to be fair and efficient, such a binary rate adaption mechanism must rely on `Additive Increase and Multiplicative Decrease`. When the network is not congested, the hosts should slowly increase their transmission rate (:math:`\beta_N=1~and~\alpha_N>0`). When the network is congested, the hosts must multiplicatively decrease their transmission rate (:math:`\beta_C < 1~and~\alpha_C = 0`). Such an AIMD rate adaptation algorithm can be implemented by the pseudo-code below. 614/10000 · 614
165 ../../principles/sharing.rst:989
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Which binary feedback ? 23/10000 · 23
166 ../../principles/sharing.rst:991
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Two types of binary feedback are possible in computer networks. A first solution is to rely on implicit feedback. This is the solution chosen for TCP. TCP's congestion control scheme [Jacobson1988]_ does not require any cooperation from the router. It only assumes that they use buffers and that they discard packets when there is congestion. TCP uses the segment losses as an indication of congestion. When there are no losses, the network is assumed to be not congested. This implies that congestion is the main cause of packet losses. This is true in wired networks, but unfortunately not always true in wireless networks. Another solution is to rely on explicit feedback. This is the solution proposed in the DECBit congestion control scheme [RJ1995]_ and used in Frame Relay and ATM networks. This explicit feedback can be implemented in two ways. A first solution would be to define a special message that could be sent by routers to hosts when they are congested. Unfortunately, generating such messages may increase the amount of congestion in the network. Such a congestion indication packet is thus discouraged :rfc:`1812`. A better approach is to allow the intermediate routers to indicate, in the packets that they forward, their current congestion status. Binary feedback can be encoded by using one bit in the packet header. With such a scheme, congested routers set a special bit in the packets that they forward while non-congested routers leave this bit unmodified. The destination host returns the congestion status of the network in the acknowledgments that it sends. Details about such a solution in IP networks may be found in :rfc:`3168`. Unfortunately, as of this writing, this solution is still not deployed despite its potential benefits. 1763/10000 · 1763
167 ../../principles/sharing.rst:996
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Congestion control with a window-based transport protocol 57/10000 · 57
168 ../../principles/sharing.rst:999
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — AIMD controls congestion by adjusting the transmission rate of the sources in reaction to the current congestion level. If the network is not congested, the transmission rate increases. If congestion is detected, the transmission rate is multiplicatively decreased. In practice, directly adjusting the transmission rate can be difficult since it requires the utilization of fine grained timers. In reliable transport protocols, an alternative is to dynamically adjust the sending window. This is the solution chosen for protocols like TCP and SCTP that will be described in more details later. To understand how window-based protocols can adjust their transmission rate, let us consider the very simple scenario of a reliable transport protocol that uses `go-back-n`. Consider the very simple scenario shown in the figure below. 828/10000 · 828