2. cnp3-ebook
3. protocols/congestion
4. English
5. Zen

28 ../../protocols/congestion.rst:175
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — The last point that needs to be discussed about Explicit Congestion Notification is the algorithm that is used by routers to detect congestion. On a router, congestion manifests itself by the number of packets that are stored inside the router buffers. As explained earlier, we need to distinguish between two types of routers : 328/10000 · 328
29 ../../protocols/congestion.rst:177
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — routers that have a single FIFO queue 37/10000 · 37
30 ../../protocols/congestion.rst:178
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — routers that have several queues served by a round-robin scheduler 66/10000 · 66
31 ../../protocols/congestion.rst:180
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Routers that use a single queue measure their buffer occupancy as the number of bytes of packets stored in the queue [#fslot]_. A first method to detect congestion is to measure the instantaneous buffer occupancy and consider the router to be congested as soon as this occupancy is above a threshold. Typical values of the threshold could be 40% of the total buffer. Measuring the instantaneous buffer occupancy is simple since it only requires one counter. However, this value is fragile from a control viewpoint since it changes frequently. A better solution is to measure the *average* buffer occupancy and consider the router to be congested when this average occupancy is too high. Random Early Detection (RED) [FJ1993]_ is an algorithm that was designed to support Explicit Congestion Notification. In addition to measuring the average buffer occupancy, it also uses probabilistic marking. When the router is congested, the arriving packets are marked with a probability that increases with the average buffer occupancy. The main advantage of using probabilistic marking instead of marking all arriving packets is that flows will be marked in proportion of the number of packets that they transmit. If the router marks 10% of the arriving packets when congested, then a large flow that sends hundred packets per second will be marked 10 times while a flow that only sends one packet per second will not be marked. This probabilistic marking allows marking packets in proportion of their usage of the network resources. 1524/10000 · 1524
32 ../../protocols/congestion.rst:182
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — If the router uses several queues served by a scheduler, the situation is different. If a large and a small flow are competing for bandwidth, the scheduler will already favor the small flow that is not using its fair share of the bandwidth. The queue for the small flow will be almost empty while the queue for the large flow will build up. On routers using such schedulers, a good way of marking the packets is to set a threshold on the occupancy of each queue and mark the packets that arrive in a particular queue as soon as its occupancy is above the configured threshold. 576/10000 · 576
33 ../../protocols/congestion.rst:186
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Modeling TCP congestion control 31/10000 · 31
34 ../../protocols/congestion.rst:189
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Thanks to its congestion control scheme, TCP adapts its transmission rate to the losses that occur in the network. Intuitively, the TCP transmission rate decreases when the percentage of losses increases. Researchers have proposed detailed models that allow the prediction of the throughput of a TCP connection when losses occur [MSMO1997]_ . To have some intuition about the factors that affect the performance of TCP, let us consider a very simple model. Its assumptions are not completely realistic, but it gives us good intuition without requiring complex mathematics. 572/10000 · 572
35 ../../protocols/congestion.rst:191
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — This model considers a hypothetical TCP connection that suffers from equally spaced segment losses. If :math:`p` is the segment loss ratio, then the TCP connection successfully transfers :math:`\frac{1}{p}-1` segments and the next segment is lost. If we ignore the slow-start at the beginning of the connection, TCP in this environment is always in congestion avoidance as there are only isolated losses that can be recovered by using fast retransmit. The evolution of the congestion window is thus as shown in the figure below. Note that the `x-axis` of this figure represents time measured in units of one round-trip-time, which is supposed to be constant in the model, and the `y-axis` represents the size of the congestion window measured in MSS-sized segments. 765/10000 · 765
36 ../../protocols/congestion.rst:197
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Evolution of the congestion window with regular losses 54/10000 · 54
37 ../../protocols/congestion.rst:199
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — As the losses are equally spaced, the congestion window always starts at some value (:math:`\frac{W}{2}`), and is incremented by one MSS every round-trip-time until it reaches twice this value (`W`). At this point, a segment is retransmitted and the cycle starts again. If the congestion window is measured in MSS-sized segments, a cycle lasts :math:`\frac{W}{2}` round-trip-times. The bandwidth of the TCP connection is the number of bytes that have been transmitted during a given period of time. During a cycle, the number of segments that are sent on the TCP connection is equal to the area of the yellow trapeze in the figure. Its area is thus : 650/10000 · 650
38 ../../protocols/congestion.rst:201
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — :math:`area=(\frac{W}{2})^2 + \frac{1}{2} \times (\frac{W}{2})^2 = \frac{3 \times W^2}{8}` 90/10000 · 90
39 ../../protocols/congestion.rst:203
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — However, given the regular losses that we consider, the number of segments that are sent between two losses (i.e. during a cycle) is by definition equal to :math:`\frac{1}{p}`. Thus, :math:`W=\sqrt{\frac{8}{3 \times p}}=\frac{k}{\sqrt{p}}`. The throughput (in bytes per second) of the TCP connection is equal to the number of segments transmitted divided by the duration of the cycle : 385/10000 · 385
40 ../../protocols/congestion.rst:205
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — :math:`Throughput=\frac{area \times MSS}{time} = \frac{ \frac{3 \times W^2}{8}}{\frac{W}{2} \times rtt}` or, after having eliminated `W`, :math:`Throughput=\sqrt{\frac{3}{2}} \times \frac{MSS}{rtt \times \sqrt{p}}` 214/10000 · 214
41 ../../protocols/congestion.rst:209
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — More detailed models and the analysis of simulations have shown that a first order model of the TCP throughput when losses occur was :math:`Throughput \approx \frac{k \times MSS}{rtt \times \sqrt{p}}`. This is an important result which shows that : 248/10000 · 248
42 ../../protocols/congestion.rst:211
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — TCP connections with a small round-trip-time can achieve a higher throughput than TCP connections having a longer round-trip-time when losses occur. This implies that the TCP congestion control scheme is not completely fair since it favors the connections that have the shorter round-trip-times. 295/10000 · 295
43 ../../protocols/congestion.rst:212
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — TCP connections that use a large MSS can achieve a higher throughput that the TCP connections that use a shorter MSS. This creates another source of unfairness between TCP connections. However, it should be noted that today most hosts are using almost the same MSS, roughly 1460 bytes. 285/10000 · 285
44 ../../protocols/congestion.rst:214
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — In general, the maximum throughput that can be achieved by a TCP connection depends on its maximum window size and the round-trip-time if there are no losses. If there are losses, it depends on the MSS, the round-trip-time and the loss ratio. 242/10000 · 242
45 ../../protocols/congestion.rst:216
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — :math:`Throughput<\min(\frac{window}{rtt},\frac{k \times MSS}{rtt \times \sqrt{p}})` 84/10000 · 84
46 ../../protocols/congestion.rst:219
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — The TCP congestion control zoo 30/10000 · 30
47 ../../protocols/congestion.rst:221
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — The first TCP congestion control scheme was proposed by `Van Jacobson`_ in [Jacobson1988]_. In addition to writing the scientific paper, `Van Jacobson`_ also implemented the slow-start and congestion avoidance schemes in release 4.3 `Tahoe` of the BSD Unix distributed by the University of Berkeley. Later, he improved the congestion control by adding the fast retransmit and the fast recovery mechanisms in the `Reno` release of 4.3 BSD Unix. Since then, many researchers have proposed, simulated and implemented modifications to the TCP congestion control scheme. Some of these modifications are still used today, e.g. : 622/10000 · 622