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

137 ../../principles/sharing.rst:825
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Most networks contain links having different bandwidth. Some hosts can use low bandwidth wireless networks. Some servers are attached via 10 Gbps interfaces and inter-router links may vary from a few tens of kilobits per second up to hundred Gbps. Despite these huge differences in performance, any host should be able to efficiently exchange segments with a high-end server. 375/10000 · 375
138 ../../principles/sharing.rst:829
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — To understand this problem better, let us consider the scenario shown in the figure below, where a server (`A`) attached to a `10 Mbps` link needs to reliably transfer segments to another computer (`C`) through a path that contains a `2 Mbps` link. 248/10000 · 248
139 ../../principles/sharing.rst:847
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — In this network, the segments sent by the server reach router `R1`. `R1` forwards the segments towards router `R2`. Router `R1` can potentially receive segments at `10 Mbps`, but it can only forward them at `2 Mbps` to router `R2` and then to host `C`. Router `R1` includes buffers that allow it to store the packets that cannot immediately be forwarded to their destination. To understand the operation of a reliable transport protocol in this environment, let us consider a simplified model of this network where host `A` is attached to a `10 Mbps` link to a queue that represents the buffers of router `R1`. This queue is emptied at a rate of `2 Mbps`. 656/10000 · 656
140 ../../principles/sharing.rst:854
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Self clocking 13/10000 · 13
141 ../../principles/sharing.rst:857
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Let us consider that host `A` uses a window of three segments. It thus sends three back-to-back segments at `10 Mbps` and then waits for an acknowledgment. Host `A` stops sending segments when its window is full. These segments reach the buffers of router `R1`. The first segment stored in this buffer is sent by router `R1` at a rate of `2 Mbps` to the destination host. Upon reception of this segment, the destination sends an acknowledgment. This acknowledgment allows host `A` to transmit a new segment. This segment is stored in the buffers of router `R1` while it is transmitting the second segment that was sent by host `A`... Thus, after the transmission of the first window of segments, the reliable transport protocol sends one data segment after the reception of each acknowledgment returned by the destination. In practice, the acknowledgments sent by the destination serve as a kind of `clock` that allows the sending host to adapt its transmission rate to the rate at which segments are received by the destination. This `self-clocking` is the first mechanism that allows a window-based reliable transport protocol to adapt to heterogeneous networks [Jacobson1988]_. It depends on the availability of buffers to store the segments that have been sent by the sender but have not yet been transmitted to the destination. 1332/10000 · 1332
142 ../../principles/sharing.rst:859
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — However, transport protocols are not only used in this environment. In the global Internet, a large number of hosts send segments to a large number of receivers. For example, let us consider the network depicted below which is similar to the one discussed in [Jacobson1988]_ and :rfc:`896`. In this network, we assume that the buffers of the router are infinite to ensure that no packet is lost. 395/10000 · 395
143 ../../principles/sharing.rst:903
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — If many senders are attached to the left part of the network above, they all send a window full of segments. These segments are stored in the buffers of the router before being transmitted towards their destination. If there are many senders on the left part of the network, the occupancy of the buffers quickly grows. A consequence of the buffer occupancy is that the round-trip-time, measured by the transport protocol, between the sender and the receiver increases. Consider a network where 10,000 bits segments are sent. When the buffer is empty, such a segment requires 1 millisecond to be transmitted on the `10 Mbps` link and 5 milliseconds to be the transmitted on the `2 Mbps` link. Thus, the measured round-trip-time measured is roughly 6 milliseconds if we ignore the propagation delay on the links. If the buffer contains 100 segments, the round-trip-time becomes :math:`1+100 \times 5+ 5` milliseconds as new segments are only transmitted on the `2 Mbps` link once all previous segments have been transmitted. Unfortunately, if the reliable transport protocol uses a retransmission timer and performs `go-back-n` to recover from transmission errors it will retransmit a full window of segments. This increases the occupancy of the buffer and the delay through the buffer... Furthermore, the buffer may store and send on the low bandwidth links several retransmissions of the same segment. This problem is called `congestion collapse`. It occurred several times during the late 1980s on the Internet [Jacobson1988]_. 1528/10000 · 1528
144 ../../principles/sharing.rst:905
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — The `congestion collapse` is a problem that all heterogeneous networks face. Different mechanisms have been proposed in the scientific literature to avoid or control network congestion. Some of them have been implemented and deployed in real networks. To understand this problem in more detail, let us first consider a simple network with two hosts attached to a high bandwidth link that are sending segments to destination `C` attached to a low bandwidth link as depicted below. 479/10000 · 479
145 ../../principles/sharing.rst:926
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — To avoid `congestion collapse`, the hosts must regulate their transmission rate [#fcredit]_ by using a `congestion control` mechanism. Such a mechanism can be implemented in the transport layer or in the network layer. In TCP/IP networks, it is implemented in the transport layer, but other technologies such as `Asynchronous Transfer Mode (ATM)` or `Frame Relay` include congestion control mechanisms in lower layers. 418/10000 · 418
146 ../../principles/sharing.rst:930
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Let us first consider the simple problem of a set of :math:`i` hosts that share a single bottleneck link as shown in the example above. In this network, the congestion control scheme must achieve the following objectives [CJ1989]_ : 232/10000 · 232
147 ../../principles/sharing.rst:932
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — The congestion control scheme must `avoid congestion`. In practice, this means that the bottleneck link cannot be overloaded. If :math:`r_i(t)` is the transmission rate allocated to host :math:`i` at time :math:`t` and :math:`R` the bandwidth of the bottleneck link, then the congestion control scheme should ensure that, on average, :math:`\forall{t} \sum{r_i(t)} \le R`. 372/10000 · 372
148 ../../principles/sharing.rst:933
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — The congestion control scheme must be `efficient`. The bottleneck link is usually both a shared and an expensive resource. Usually, bottleneck links are wide area links that are much more expensive to upgrade than the local area networks. The congestion control scheme should ensure that such links are efficiently used. Mathematically, the control scheme should ensure that :math:`\forall{t} \sum{r_i(t)} \approx R`. 417/10000 · 417
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