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

8 ../../principles/sharing.rst:78
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — A fourth physical organization of a network is the ring topology. Like the bus organization, each host has a single physical interface connecting it to the ring. Any signal sent by a host on the ring will be received by all hosts attached to the ring. From a redundancy point of view, a single ring is not the best solution, as the signal only travels in one direction on the ring; thus if one of the links composing the ring is cut, the entire network fails. In practice, such rings have been used in local area networks, but are now often replaced by star-shaped networks. In metropolitan networks, rings are often used to interconnect multiple locations. In this case, two parallel links, composed of different cables, are often used for redundancy. With such a dual ring, when one ring fails all the traffic can be quickly switched to the other ring. 854/10000 · 854
9 ../../principles/sharing.rst:95
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — A fifth physical organization of a network is the tree. Such networks are typically used when a large number of customers must be connected in a very cost-effective manner. Cable TV networks are often organized as trees. 220/10000 · 220
10 ../../principles/sharing.rst:111
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Sharing bandwidth 17/10000 · 17
11 ../../principles/sharing.rst:113
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — In all these networks, except the full-mesh, the link bandwidth is shared among all connected hosts. Various algorithms have been proposed and are used to efficiently share the access to this resource. We explain several of them in the Medium Access Control section below. 272/10000 · 272
12 ../../principles/sharing.rst:115
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Fairness in computer networks 29/10000 · 29
13 ../../principles/sharing.rst:117
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Sharing resources is important to ensure that the network efficiently serves its user. In practice, there are many ways to share resources. Some resource sharing schemes consider that some users are more important than others and should obtain more resources. For example, on the roads, police cars and ambulances have priority. In some cities, traffic lanes are reserved for buses to promote public services, ... In computer networks, the same problem arise. Given that resources are limited, the network needs to enable users to efficiently share them. Before designing an efficient resource sharing scheme, one needs to first formalize its objectives. In computer networks, the most popular objective for resource sharing schemes is that they must be `fair`. In a simple situation, for example two hosts using a shared 2 Mbps link, the sharing scheme should allocate the same bandwidth to each user, in this case 1 Mbps. However, in a large networks, simply dividing the available resources by the number of users is not sufficient. Consider the network shown in the figure below where `A1` sends data to `A2`, `B1` to `B2`, ... In this network, how should we divide the bandwidth among the different flows ? A first approach would be to allocate the same bandwidth to each flow. In this case, each flow would obtain 5 Mbps and the link between `R2` and `R3` would not be fully loaded. Another approach would be to allocate 10 Mbps to `A1-A2`, 20 Mbps to `C1-C2` and nothing to `B1-B2`. This is clearly unfair. 1513/10000 · 1513
14 ../../principles/sharing.rst:150
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — In large networks, fairness is always a compromise. The most widely used definition of fairness is the `max-min fairness`. A bandwidth allocation in a network is said to be `max-min fair` if it is such that it is impossible to allocate more bandwidth to one of the flows without reducing the bandwidth of a flow that already has a smaller allocation than the flow that we want to increase. If the network is completely known, it is possible to derive a `max-min fair` allocation as follows. Initially, all flows have a null bandwidth and they are placed in the candidate set. The bandwidth allocation of all flows in the candidate set is increased until one link becomes congested. At this point, the flows that use the congested link have reached their maximum allocation. They are removed from the candidate set and the process continues until the candidate set becomes empty. 878/10000 · 878
15 ../../principles/sharing.rst:152
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — In the above network, the allocation of all flows would grow until `A1-A2` and `B1-B2` reach 5 Mbps. At this point, link `R1-R2` becomes congested and these two flows have reached their maximum. The allocation for flow `C1-C2` can increase until reaching 15 Mbps. At this point, link `R2-R3` is congested. To increase the bandwidth allocated to `C1-C2`, one would need to reduce the allocation to flow `B1-B2`. Similarly, the only way to increase the allocation to flow `B1-B2` would require a decrease of the allocation to `A1-A2`. 532/10000 · 532
16 ../../principles/sharing.rst:155 • ../../principles/sharing.rst:223
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Network congestion 18/10000 · 18
17 ../../principles/sharing.rst:157
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Sharing bandwidth among the hosts directly attached to a link is not the only sharing problem that occurs in computer networks. To understand the general problem, let us consider a very simple network which contains only point-to-point links. This network contains three hosts and two routers. All the links inside the network have the same capacity. For example, let us assume that all links have a bandwidth of 1000 bits per second and that the hosts send packets containing exactly one thousand bits. 503/10000 · 503
18 ../../principles/sharing.rst:178
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — In the network above, consider the case where host `A` is transmitting packets to destination `C`. `A` can send one packet per second and its packets will be delivered to `C`. Now, let us explore what happens when host `B` also starts to transmit a packet. Node `R1` will receive two packets that must be forwarded to `R2`. Unfortunately, due to the limited bandwidth on the `R1-R2` link, only one of these two packets can be transmitted. The outcome of the second packet will depend on the available buffers on `R1`. If `R1` has one available buffer, it could store the packet that has not been transmitted on the `R1-R2` link until the link becomes available. If `R1` does not have available buffers, then the packet needs to be discarded. 741/10000 · 741
19 ../../principles/sharing.rst:182
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Besides the link bandwidth, the buffers on the network nodes are the second type of resource that needs to be shared inside the network. The node buffers play an important role in the operation of the network because that can be used to absorb transient traffic peaks. Consider again the example above. Assume that on average host `A` and host `B` send a group of three packets every ten seconds. Their combined transmission rate (0.6 packets per second) is, on average, lower than the network capacity (1 packet per second). However, if they both start to transmit at the same time, node `R1` will have to absorb a burst of packets. This burst of packets is a small `network congestion`. We will say that a network is congested, when the sum of the traffic demand from the hosts is larger than the network capacity :math:`\sum{demand}>capacity`. This `network congestion` problem is one of the most difficult resource sharing problem in computer networks. `Congestion` occurs in almost all networks. Minimizing the amount of congestion is a key objective for many network operators. In most cases, they will have to accept transient congestion, i.e. congestion lasting a few seconds or perhaps minutes, but will want to prevent congestion that lasts days or months. For this, they can rely on a wide range of solutions. We briefly present some of these in the paragraphs below. 1378/10000 · 1378
20 ../../principles/sharing.rst:186
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — If `R1` has enough buffers, it will be able to absorb the load without having to discard packets. The packets sent by hosts `A` and `B` will reach their final destination `C`, but will experience a longer delay than when they are transmitting alone. The amount of buffering on the network node is the first parameter that a network operator can tune to control congestion inside his network. Given the decreasing cost of memory, one could be tempted to put as many buffers [#fbufferbloat]_ as possible on the network nodes. Let us consider this case in the network above and assume that `R1` has infinite buffers. Assume now that hosts `A` and `B` try to transmit a file that corresponds to one thousand packets each. Both are using a reliable protocol that relies on go-back-n to recover from transmission errors. The transmission starts and packets start to accumulate in `R1`'s buffers. The presence of these packets in the buffers increases the delay between the transmission of a packet by `A` and the return of the corresponding acknowledgment. Given the increasing delay, host `A` (and `B` as well) will consider that some of the packets that it sent have been lost. These packets will be retransmitted and will enter the buffers of `R1`. The occupancy of the buffers of `R1` will continue to increase and the delays as well. This will cause new retransmissions, ... In the end, only one file will be delivered (very slowly) to the destination, but the link `R1-R2` will transfer much more bytes than the size of the file due to the multiple copies of the same packets. This is known as the `congestion collapse` problem :rfc:`896`. Congestion collapse is the nightmare for network operators. When it happens, the network carries packets without delivering useful data to the end users. 1793/10000 · 1793
21 ../../principles/sharing.rst:188
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Congestion collapse on the Internet 35/10000 · 35
22 ../../principles/sharing.rst:190
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Congestion collapse is unfortunately not only an academic experience. Van Jacobson reports in [Jacobson1988]_ one of these events that affected him while he was working at the Lawrence Berkeley Laboratory (LBL). LBL was two network nodes away from the University of California in Berkeley. At that time, the link between the two sites had a bandwidth of 32 Kbps, but some hosts were already attached to 10 Mbps LANs. "In October 1986, the data throughput from LBL to UC Berkeley ... dropped from 32 Kbps to 40 bps. We were fascinated by this sudden factor-of-thousand drop in bandwidth and embarked on an investigation of why things had gotten so bad." This work lead to the development of various congestion control techniques that have allowed the Internet to continue to grow without experiencing widespread congestion collapse events. 839/10000 · 839
23 ../../principles/sharing.rst:192
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Besides bandwidth and memory, a third resource that needs to be shared inside a network is the (packet) processing capacity. To forward a packet, a router needs bandwidth on the outgoing link, but it also needs to analyze the packet header to perform a lookup inside its forwarding table. Performing these lookup operations require resources such as CPU cycles or memory accesses. Routers are usually designed to be able to sustain a given packet processing rate, measured in packets per second [#fpps]_. 504/10000 · 504
24 ../../principles/sharing.rst:194
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Packets per second versus bits per second 41/10000 · 41
25 ../../principles/sharing.rst:197
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — The performance of network nodes (either routers or switches) can be characterized by two key metrics : 103/10000 · 103
26 ../../principles/sharing.rst:199
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — the node's capacity measured in bits per second 47/10000 · 47
27 ../../principles/sharing.rst:200
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — the node's lookup performance measured in packets per second 60/10000 · 60