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

33 ../../principles/sharing.rst:218
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — If the buffer's occupancy continues to grow, it will overflow and packets will need to be discarded. Discarding packets during congestion is the second possible reaction of a network node to congestion. Before looking at how a node can discard packets, it is interesting to discuss qualitatively the impact of the buffer occupancy on the reliable delivery of data through a network. This is illustrated by the figure below, adapted from [Jain1990]_. 449/10000 · 449
34 ../../principles/sharing.rst:226
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — When the network load is low, buffer occupancy and link utilization are low. The buffers on the network nodes are mainly used to absorb very short bursts of packets, but on average the traffic demand is lower than the network capacity. If the demand increases, the average buffer occupancy will increase as well. Measurements have shown that the total throughput increases as well. If the buffer occupancy is zero or very low, transmission opportunities on network links can be missed. This is not the case when the buffer occupancy is small but non zero. However, if the buffer occupancy continues to increase, the buffer becomes overloaded and the throughput does not increase anymore. When the buffer occupancy is close to the maximum, the throughput may decrease. This drop in throughput can be caused by excessive retransmissions of reliable protocols that incorrectly assume that previously sent packets have been lost while they are still waiting in the buffer. The network delay on the other hand increases with the buffer occupancy. In practice, a good operating point for a network buffer is a low occupancy to achieve high link utilization and also low delay for interactive applications. 1199/10000 · 1199
35 ../../principles/sharing.rst:230
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Discarding packets is one of the signals that the network nodes can use to inform the hosts of the current level of congestion. Buffers on network nodes are usually used as FIFO queues to preserve packet ordering. Several `packet discard mechanisms` have been proposed for network nodes. These techniques basically answer two different questions : 347/10000 · 347
36 ../../principles/sharing.rst:232
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — `What triggers a packet to be discarded ?` What are the conditions that lead a network node to decide to discard a packet? The simplest answer to this question is : `When the buffer is full`. Although this is a good congestion indication, it is probably not the best one from a performance viewpoint. An alternative is to discard packets when the buffer occupancy grows too much. In this case, it is likely that the buffer will become full shortly. Since packet discarding is an information that allows hosts to adapt their transmission rate, discarding packets early could allow hosts to react earlier and thus prevent congestion from happening. 646/10000 · 646
37 ../../principles/sharing.rst:233
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — `Which packet(s) should be discarded ?` Once the network node has decided to discard packets, it needs to actually discard real packets. 136/10000 · 136
38 ../../principles/sharing.rst:236
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — By combining different answers to these questions, network researchers have developed different packet discard mechanisms. 122/10000 · 122
39 ../../principles/sharing.rst:238
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — `Tail drop` is the simplest packet discard technique. When a buffer is full, the arriving packet is discarded. `Tail drop` can be easily implemented. This is, by far, the most widely used packet discard mechanism. However, it suffers from two important drawbacks. First, since `tail drop` discards packets only when the buffer is full, buffers tend to be congested and real-time applications may suffer from increased delays. Second, `tail drop` is blind when it discards a packet. It may discard a packet from a low bandwidth interactive flow while most of the buffer is used by large file transfers. 601/10000 · 601
40 ../../principles/sharing.rst:239
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — `Drop from front` is an alternative packet discard technique. Instead of removing the arriving packet, it removes the packet that was at the head of the queue. Discarding this packet instead of the arriving one can have two advantages. First, it already stayed a long time in the buffer. Second, hosts should be able to detect the loss (and thus the congestion) earlier. 370/10000 · 370
41 ../../principles/sharing.rst:240
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — `Probabilistic drop`. Various random drop techniques have been proposed. A frequently cited technique is `Random Early Discard` (RED) [FJ1993]_. RED measures the average buffer occupancy and discards packets with a given probability when this average occupancy is too high. Compared to `tail drop` and `drop from front`, an advantage of `RED` is that thanks to the probabilistic drops, packets should be discarded from different flows in proportion of their bandwidth. 468/10000 · 468
42 ../../principles/sharing.rst:242
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Discarding packets is a frequent reaction to network congestion. Unfortunately, discarding packets is not optimal since a packet which is discarded on a network node has already consumed resources on the upstream nodes. There are other ways for the network to inform the end hosts of the current congestion level. A first solution is to mark the packets when a node is congested. Several networking technologies have relied on this kind of packet marking. 455/10000 · 455
43 ../../principles/sharing.rst:246
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — In datagram networks, `Forward Explicit Congestion Notification` (FECN) can be used. One field of the packet header, typically one bit, is used to indicate congestion. When a host sends a packet, the congestion bit is unset. If the packet passes through a congested node, the congestion bit is set. The destination can then determine the current congestion level by measuring the fraction of the packets that it received with the congestion bit set. It may then return this information to the sending host to allow it to adapt its retransmission rate. Compared to packet discarding, the main advantage of FECN is that hosts can detect congestion explicitly without having to rely on packet losses. 697/10000 · 697
44 ../../principles/sharing.rst:248
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — In virtual circuit networks, packet marking can be improved if the return packets follow the reverse path of the forward packets. It this case, a network node can detect congestion on the forward path (e.g. due to the size of its buffer), but mark the packets on the return path. Marking the return packets (e.g. the acknowledgments used by reliable protocols) provides a faster feedback to the sending hosts compared to FECN. This technique is usually called `Backward Explicit Congestion Notification (BECN)`. 511/10000 · 511
45 ../../principles/sharing.rst:250
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — If the packet header does not contain any bit in the header to represent the current congestion level, an alternative is to allow the network nodes to send a control packet to the source to indicate the current congestion level. Some networking technologies use such control packets to explicitly regulate the transmission rate of sources. However, their usage is mainly restricted to small networks. In large networks, network nodes usually avoid using such control packets. These control packets are even considered to be dangerous in some networks. First, using them increases the network load when the network is congested. Second, while network nodes are optimized to forward packets, they are usually pretty slow at creating new packets. 743/10000 · 743
46 ../../principles/sharing.rst:254
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Dropping and marking packets is not the only possible reaction of a router that becomes congested. A router could also selectively delay packets belonging to some flows. There are different algorithms that can be used by a router to delay packets. If the objective of the router is to fairly distribute to bandwidth of an output link among competing flows, one possibility is to organize the buffers of the router as a set of queues. For simplicity, let us assume that the router is capable of supporting a fixed number of concurrent flows, say `N`. One of the queues of the router is associated to each flow and when a packet arrives, it is placed at the tail of the corresponding queue. All the queues are controlled by a `scheduler`. A `scheduler` is an algorithm that is run each time there is an opportunity to transmit a packet on the outgoing link. Various schedulers have been proposed in the scientific literature and some are used in real routers. 957/10000 · 957
47 ../../principles/sharing.rst:319
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — A very simple scheduler is the `round-robin scheduler`. This scheduler serves all the queues in a round-robin fashion. If all flows send packets of the same size, then the round-robin scheduler fairly allocates the bandwidth among the different flows. Otherwise, it favors flows that are using larger packets. Extensions to the `round-robin scheduler` have been proposed to provide a fair distribution of the bandwidth with variable-length packets [SV1995]_ but these are outside the scope of this chapter. 506/10000 · 506
48 ../../principles/sharing.rst:340
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Distributing the load across the network 40/10000 · 40
49 ../../principles/sharing.rst:344
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Delays, packet discards, packet markings and control packets are the main types of information that the network can exchange with the end hosts. Discarding packets is the main action that a network node can perform if the congestion is too severe. Besides tackling congestion at each node, it is also possible to divert some traffic flows from heavily loaded links to reduce congestion. Early routing algorithms [MRR1980]_ have used delay measurements to detect congestion between network nodes and update the link weights dynamically. By reflecting the delay perceived by applications in the link weights used for the shortest paths computation, these routing algorithms managed to dynamically change the forwarding paths in reaction to congestion. However, deployment experience showed that these dynamic routing algorithms could cause oscillations and did not necessarily lower congestion. Deployed datagram networks rarely use dynamic routing algorithms, except in some wireless networks. In datagram networks, the state of the art reaction to long term congestion, i.e. congestion lasting hours, days or more, is to measure the traffic demand and then select the link weights [FRT2002]_ that allow minimizing the maximum link loads. If the congestion lasts longer, changing the weights is not sufficient anymore and the network needs to be upgraded with additional or faster links. However, in Wide Area Networks, adding new links can take months. 1452/10000 · 1452
50 ../../principles/sharing.rst:346
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — In virtual circuit networks, another way to manage or prevent congestion is to limit the number of circuits that use the network at any time. This technique is usually called `connection admission control`. When a host requests the creation of a new circuit in the network, it specifies the destination and in some networking technologies the required bandwidth. With this information, the network can check whether there are enough resources available to reach this particular destination. If yes, the circuit is established. If not, the request is denied and the host will have to defer the creation of its virtual circuit. `Connection admission control` schemes are widely used in the telephone networks. In these networks, a busy tone corresponds to an unavailable destination or a congested network. 804/10000 · 804
51 ../../principles/sharing.rst:348
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — In datagram networks, this technique cannot be easily used since the basic assumption of such a network is that a host can send any packet towards any destination at any time. A host does not need to request the authorization of the network to send packets towards a particular destination. 290/10000 · 290
52 ../../principles/sharing.rst:350
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Based on the feedback received from the network, the hosts can adjust their transmission rate. We discuss in section `Congestion control` some techniques that allow hosts to react to congestion. 194/10000 · 194