# SOME DESCRIPTIVE TITLE. # Copyright (C) 2019 Olivier Bonaventure # This file is distributed under the same license as the Computer networking # : Principles, Protocols and Practice package. # FIRST AUTHOR , 2019. # msgid "" msgstr "" "Project-Id-Version: Computer networking : Principles, Protocols and Practice " "3\n" "Report-Msgid-Bugs-To: \n" "POT-Creation-Date: 2019-10-09 12:39+0000\n" "PO-Revision-Date: 2021-08-27 14:47+0000\n" "Last-Translator: Anthony Gego \n" "Language-Team: French \n" "Language: fr\n" "MIME-Version: 1.0\n" "Content-Type: text/plain; charset=utf-8\n" "Content-Transfer-Encoding: 8bit\n" "Plural-Forms: nplurals=2; plural=n > 1;\n" "X-Generator: Weblate 3.9.1\n" "Generated-By: Babel 2.7.0\n" #: ../../principles/sharing.rst:8 msgid "" "This is an unpolished draft of the third edition of this e-book. If you " "find any error or have suggestions to improve the text, please create an " "issue via https://github.com/CNP3/ebook/issues?milestone=3 or help us by " "providing pull requests to close the existing issues." msgstr "" "Ceci est une ébauche non révisée de la troisième édition de cet e-book. Si " "vous trouvez une quelconque erreur ou avez des suggestions pour améliorer ce " "texte, n'hésitez pas à envoyer une issue via https://github.com/CNP3/ebook/" "issues?milestone=3 ou aidez-nous en fournissant une pull request afin de " "clore les issues existantes." #: ../../principles/sharing.rst:14 msgid "Sharing resources" msgstr "Le partage de ressources" #: ../../principles/sharing.rst:16 msgid "" "A network is designed to support a potentially large number of users that" " exchange information with each other. These users produce and consume " "information which is exchanged through the network. To support its users," " a network uses several types of resources. It is important to keep in " "mind the different resources that are shared inside the network." msgstr "" #: ../../principles/sharing.rst:18 msgid "" "The first and more important resource inside a network is the link " "bandwidth. There are two situations where link bandwidth needs to be " "shared between different users. The first situation is when several hosts" " are attached to the same physical link. This situation mainly occurs in " "Local Area Networks (LAN). A LAN is a network that efficiently " "interconnects several hosts (usually a few dozens to a few hundreds) in " "the same room, building or campus. Consider for a example a network with " "five hosts. Any of these hosts needs to be able to exchange information " "with any of the other five hosts. A first organization for this LAN is " "the full-mesh." msgstr "" #: ../../principles/sharing.rst:24 msgid "A Full mesh network" msgstr "" #: ../../principles/sharing.rst:26 msgid "" "The full-mesh is the most reliable and highest performing network to " "interconnect these five hosts. However, this network organization has two" " important drawbacks. First, if a network contains `n` hosts, then " ":math:`\\frac{n\\times(n-1)}{2}` links are required. If the network " "contains more than a few hosts, it becomes impossible to lay down the " "required physical links. Second, if the network contains `n` hosts, then " "each host must have :math:`n-1` interfaces to terminate :math:`n-1` " "links. This is beyond the capabilities of most hosts. Furthermore, if a " "new host is added to the network, new links have to be laid down and one " "interface has to be added to each participating host. However, full-mesh " "has the advantage of providing the lowest delay between the hosts and the" " best resiliency against link failures. In practice, full-mesh networks " "are rarely used expected when there are few network nodes and resiliency " "is key." msgstr "" #: ../../principles/sharing.rst:28 msgid "" "The second possible physical organization, which is also used inside " "computers to connect different extension cards, is the bus. In a bus " "network, all hosts are attached to a shared medium, usually a cable " "through a single interface. When one host sends an electrical signal on " "the bus, the signal is received by all hosts attached to the bus. A " "drawback of bus-based networks is that if the bus is physically cut, then" " the network is split into two isolated networks. For this reason, bus-" "based networks are sometimes considered to be difficult to operate and " "maintain, especially when the cable is long and there are many places " "where it can break. Such a bus-based topology was used in early Ethernet " "networks." msgstr "" #: ../../principles/sharing.rst:34 msgid "A network organized as a Bus" msgstr "" #: ../../principles/sharing.rst:36 msgid "" "A third organization of a computer network is a star topology. In such " "networks, hosts have a single physical interface and there is one " "physical link between each host and the center of the star. The node at " "the center of the star can be either a piece of equipment that amplifies " "an electrical signal, or an active device, such as a piece of equipment " "that understands the format of the messages exchanged through the " "network. Of course, the failure of the central node implies the failure " "of the network. However, if one physical link fails (e.g. because the " "cable has been cut), then only one node is disconnected from the network." " In practice, star-shaped networks are easier to operate and maintain " "than bus-shaped networks. Many network administrators also appreciate the" " fact that they can control the network from a central point. " "Administered from a Web interface, or through a console-like connection, " "the center of the star is a useful point of control (enabling or " "disabling devices) and an excellent observation point (usage statistics)." msgstr "" #: ../../principles/sharing.rst:43 msgid "A network organized as a Star" msgstr "" #: ../../principles/sharing.rst:45 msgid "" "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." msgstr "" #: ../../principles/sharing.rst:51 msgid "A network organized as a ring" msgstr "" #: ../../principles/sharing.rst:53 msgid "" "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." msgstr "" #: ../../principles/sharing.rst:59 msgid "A network organized as a Tree" msgstr "" #: ../../principles/sharing.rst:62 msgid "Sharing bandwidth" msgstr "" #: ../../principles/sharing.rst:64 msgid "" "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." msgstr "" #: ../../principles/sharing.rst:66 msgid "Fairness in computer networks" msgstr "" #: ../../principles/sharing.rst:68 msgid "" "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 " "highways, police cars and ambulances have priority to use the highways. " "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." msgstr "" #: ../../principles/sharing.rst:101 msgid "" "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." msgstr "" #: ../../principles/sharing.rst:103 msgid "" "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`." msgstr "" #: ../../principles/sharing.rst:106 ../../principles/sharing.rst:172 msgid "Network congestion" msgstr "" #: ../../principles/sharing.rst:108 msgid "" "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 " "network nodes. All 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." msgstr "" #: ../../principles/sharing.rst:129 msgid "" "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." msgstr "" #: ../../principles/sharing.rst:133 msgid "" "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." msgstr "" #: ../../principles/sharing.rst:137 msgid "" "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, several copies of the " "same packet will be transmitted over the `R1-R2`, but only one file will " "be delivered (very slowly) to the destination. 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." msgstr "" #: ../../principles/sharing.rst:139 msgid "Congestion collapse on the Internet" msgstr "" #: ../../principles/sharing.rst:141 msgid "" "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." msgstr "" #: ../../principles/sharing.rst:143 msgid "" "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 network node 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. Network nodes are usually designed" " to be able to sustain a given packet processing rate, measured in " "packets per second." msgstr "" #: ../../principles/sharing.rst:145 msgid "Packets per second versus bits per second" msgstr "" #: ../../principles/sharing.rst:148 msgid "The performance of network nodes can be characterized by two key metrics :" msgstr "" #: ../../principles/sharing.rst:150 msgid "the node's capacity measured in bits per second" msgstr "" #: ../../principles/sharing.rst:151 msgid "the node's lookup performance measured in packets per second" msgstr "" #: ../../principles/sharing.rst:153 msgid "" "The node's capacity in bits per second mainly depends on the physical " "interfaces that it uses and also on the capacity of the internal " "interconnection (bus, crossbar switch, ...) between the different " "interfaces inside the node. Many vendors, in particular for low-end " "devices will use the sum of the bandwidth of the nodes' interfaces as the" " node capacity in bits per second. Measurements do not always match this " "maximum theoretical capacity. A well designed network node will usually " "have a capacity in bits per second larger than the sum of its link " "capacities. Such nodes will usually reach this maximum capacity when " "forwarding large packets." msgstr "" #: ../../principles/sharing.rst:155 msgid "" "When a network node forwards small packets, its performance is usually " "limited by the number of lookup operations that it can perform every " "second. This lookup performance is measured in packets per second. The " "performance may depend on the length of the forwarded packets. The key " "performance factor is the number of minimal size packets that are " "forwarded by the node every second. This rate can lead to a capacity in " "bits per second which is much lower than the sum of the bandwidth of the " "node's links." msgstr "" #: ../../principles/sharing.rst:161 msgid "" "Let us now try to present a broad overview of the congestion problem in " "networks. We will assume that the network is composed of dedicated links " "having a fixed bandwidth [#fadjust]_. A network contains hosts that " "generate and receive packets and nodes that forward packets. Assuming " "that each host is connected via a single link to the network, the largest" " demand is :math:`\\sum{Access Links}`. In practice, this largest demand " "is never reached and the network will be engineered to sustain a much " "lower traffic demand. The difference between the worst-case traffic " "demand and the sustainable traffic demand can be large, up to several " "orders of magnitude. Fortunately, the hosts are not completely dumb and " "they can adapt their traffic demand to the current state of the network " "and the available bandwidth. For this, the hosts need to `sense` the " "current level of congestion and adjust their own traffic demand based on " "the estimated congestion. Network nodes can react in different ways to " "network congestion and hosts can sense the level of congestion in " "different ways." msgstr "" #: ../../principles/sharing.rst:163 msgid "" "Let us first explore which mechanisms can be used inside a network to " "control congestion and how these mechanisms can influence the behavior of" " the end hosts." msgstr "" #: ../../principles/sharing.rst:165 msgid "" "As explained earlier, one of the first manifestation of congestion on " "network nodes is the saturation of the network links that leads to a " "growth in the occupancy of the buffers of the node. This growth of the " "buffer occupancy implies that some packets will spend more time in the " "buffer and thus in the network. If hosts measure the network delays (e.g." " by measuring the round-trip-time between the transmission of a packet " "and the return of the corresponding acknowledgment) they could start to " "sense congestion. On low bandwidth links, a growth in the buffer " "occupancy can lead to an increase of the delays which can be easily " "measured by the end hosts. On high bandwidth links, a few packets inside " "the buffer will cause a small variation in the delay which may not " "necessarily be larger that the natural fluctuations of the delay " "measurements." msgstr "" #: ../../principles/sharing.rst:167 msgid "" "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]_." msgstr "" #: ../../principles/sharing.rst:175 msgid "" "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." msgstr "" #: ../../principles/sharing.rst:179 msgid "" "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 " ":" msgstr "" #: ../../principles/sharing.rst:181 msgid "" "`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." msgstr "" #: ../../principles/sharing.rst:182 msgid "" "`Which packet(s) should be discarded ?` Once the network node has decided" " to discard packets, it needs to actually discard real packets." msgstr "" #: ../../principles/sharing.rst:185 msgid "" "By combining different answers to these questions, network researchers " "have developed different packet discard mechanisms." msgstr "" #: ../../principles/sharing.rst:187 msgid "" "`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 the 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." msgstr "" #: ../../principles/sharing.rst:188 msgid "" "`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." msgstr "" #: ../../principles/sharing.rst:189 msgid "" "`probabilistic drop`. Various random drop techniques have been proposed. " "Compared to the previous techniques. 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." msgstr "" #: ../../principles/sharing.rst:191 msgid "" "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." msgstr "" #: ../../principles/sharing.rst:195 msgid "" "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." msgstr "" #: ../../principles/sharing.rst:197 msgid "" "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)`." msgstr "" #: ../../principles/sharing.rst:199 msgid "" "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 controlled 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." msgstr "" #: ../../principles/sharing.rst:203 msgid "" "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." msgstr "" #: ../../principles/sharing.rst:207 msgid "A round-robin scheduler" msgstr "" #: ../../principles/sharing.rst:210 msgid "" "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 allocates the bandwidth" " fairly 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." msgstr "" #: ../../principles/sharing.rst:231 msgid "Distributing the load across the network" msgstr "" #: ../../principles/sharing.rst:235 msgid "" "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 to minimize the " "maximum link loads. If the congestion lasts longer, changing the weights " "is not sufficient anymore and the network needs to be upgraded with few " "or faster links. However, in Wide Area Networks, adding new links can " "take months." msgstr "" #: ../../principles/sharing.rst:237 msgid "" "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." msgstr "" #: ../../principles/sharing.rst:239 msgid "" "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." msgstr "" #: ../../principles/sharing.rst:241 msgid "" "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." msgstr "" #: ../../principles/sharing.rst:243 msgid "" "Another way to share the network resources is to distribute the load " "across multiple links. Many techniques have been designed to spread the " "load over the network. As an illustration, let us briefly consider how " "load can be shared when accessing some content. Consider a large and " "popular file such as the image of a Linux distribution or the upgrade of " "a commercial operating system that will be downloaded by many users. " "There are many ways to distribute this large file. A naive solution is to" " place one copy of the file on a server and allow all users to download " "this file from the server. If the file is popular and millions of users " "want to download it, the server will quickly become overloaded. There are" " two classes of solutions that can be used to serve a large number of " "users. A first approach is to store the file on servers whose name is " "known by the clients. Before retrieving the file, each client will query " "the name service to obtain the address of the server. If the file is " "available from many servers, the name service can provide different " "addresses to different clients. This will automatically spread the load " "since different clients will download the file from different servers. " "Most large content providers use such a solution to distribute large " "files or videos." msgstr "" #: ../../principles/sharing.rst:250 msgid "" "There is another solution that allows to spread the load among many " "sources without relying on the name service. The popular `bittorent " "`_ service is an example of this approach. " "With this solution, each file is divided in blocks of a fixed size. To " "retrieve a file, a client needs to retrieve all the blocks that compose " "the file. However, nothing forces the client to retrieve all the blocks " "in sequence and from the same server. Each file is associated with " "metadata that indicates for each block a list of addresses of hosts that " "store this block. To retrieve a complete file, a client first downloads " "the metadata. Then, it tries to retrieve each block from one of the hosts" " that store the block. In practice, implementations often try to download" " several blocks in parallel. Once one block has been successfully " "downloaded, the next block can be requested. If a host is slow to provide" " one block or becomes unavailable, the client can contact another host " "listed in the metadata. Most deployments of bittorrent allow the clients " "to participate to the distribution of blocks. Once a client has " "downloaded one block, it contacts the server which stores the metadata to" " indicate that it can also provide this block. With this scheme, when a " "file is popular, its blocks are downloaded by many hosts that " "automatically participate in the distribution of the blocks. Thus, the " "number of `servers` that are capable of providing blocks from a popular " "file automatically increases with the file's popularity." msgstr "" #: ../../principles/sharing.rst:254 msgid "" "Now that we have provided a broad overview of the techniques that can be " "used to spread the load and allocate resources in the network, let us " "analyze two techniques in more details : Medium Access Control and " "Congestion control." msgstr "" #: ../../principles/sharing.rst:260 msgid "Medium Access Control algorithms" msgstr "" #: ../../principles/sharing.rst:265 msgid "" "The common problem among Local Area Networks is how to efficiently share " "the available bandwidth. If two devices send a frame at the same time, " "the two electrical, optical or radio signals that correspond to these " "frames will appear at the same time on the transmission medium and a " "receiver will not be able to decode either frame. Such simultaneous " "transmissions are called `collisions`. A `collision` may involve frames " "transmitted by two or more devices attached to the Local Area Network. " "Collisions are the main cause of errors in wired Local Area Networks." msgstr "" #: ../../principles/sharing.rst:267 msgid "" "All Local Area Network technologies rely on a `Medium Access Control` " "algorithm to regulate the transmissions to either minimize or avoid " "collisions. There are two broad families of `Medium Access Control` " "algorithms :" msgstr "" #: ../../principles/sharing.rst:269 msgid "" "`Deterministic` or `pessimistic` MAC algorithms. These algorithms assume " "that collisions are a very severe problem and that they must be " "completely avoided. These algorithms ensure that at any time, at most one" " device is allowed to send a frame on the LAN. This is usually achieved " "by using a distributed protocol which elects one device that is allowed " "to transmit at each time. A deterministic MAC algorithm ensures that no " "collision will happen, but there is some overhead in regulating the " "transmission of all the devices attached to the LAN." msgstr "" #: ../../principles/sharing.rst:270 msgid "" "`Stochastic` or `optimistic` MAC algorithms. These algorithms assume that" " collisions are part of the normal operation of a Local Area Network. " "They aim to minimize the number of collisions, but they do not try to " "avoid all collisions. Stochastic algorithms are usually easier to " "implement than deterministic ones." msgstr "" #: ../../principles/sharing.rst:273 msgid "" "We first discuss a simple deterministic MAC algorithm and then we " "describe several important optimistic algorithms, before coming back to a" " distributed and deterministic MAC algorithm." msgstr "" #: ../../principles/sharing.rst:277 msgid "Static allocation methods" msgstr "" #: ../../principles/sharing.rst:279 msgid "" "A first solution to share the available resources among all the devices " "attached to one Local Area Network is to define, `a priori`, the " "distribution of the transmission resources among the different devices. " "If `N` devices need to share the transmission capacities of a LAN " "operating at `b` Mbps, each device could be allocated a bandwidth of " ":math:`\\frac{b}{N}` Mbps." msgstr "" #: ../../principles/sharing.rst:283 msgid "" "Limited resources need to be shared in other environments than Local Area" " Networks. Since the first radio transmissions by `Marconi " "`_ more than one century " "ago, many applications that exchange information through radio signals " "have been developed. Each radio signal is an electromagnetic wave whose " "power is centered around a given frequency. The radio spectrum " "corresponds to frequencies ranging between roughly 3 KHz and 300 GHz. " "Frequency allocation plans negotiated among governments reserve most " "frequency ranges for specific applications such as broadcast radio, " "broadcast television, mobile communications, aeronautical radio " "navigation, amateur radio, satellite, etc. Each frequency range is then " "subdivided into channels and each channel can be reserved for a given " "application, e.g. a radio broadcaster in a given region." msgstr "" #: ../../principles/sharing.rst:288 msgid "" "`Frequency Division Multiplexing` (FDM) is a static allocation scheme in " "which a frequency is allocated to each device attached to the shared " "medium. As each device uses a different transmission frequency, " "collisions cannot occur. In optical networks, a variant of FDM called " "`Wavelength Division Multiplexing` (WDM) can be used. An optical fiber " "can transport light at different wavelengths without interference. With " "WDM, a different wavelength is allocated to each of the devices that " "share the same optical fiber." msgstr "" #: ../../principles/sharing.rst:293 msgid "" "`Time Division Multiplexing` (TDM) is a static bandwidth allocation " "method that was initially defined for the telephone network. In the fixed" " telephone network, a voice conversation is usually transmitted as a 64 " "Kbps signal. Thus, a telephone conservation generates 8 KBytes per second" " or one byte every 125 microseconds. Telephone conversations often need " "to be multiplexed together on a single line. For example, in Europe, " "thirty 64 Kbps voice signals are multiplexed over a single 2 Mbps (E1) " "line. This is done by using `Time Division Multiplexing` (TDM). TDM " "divides the transmission opportunities into slots. In the telephone " "network, a slot corresponds to 125 microseconds. A position inside each " "slot is reserved for each voice signal. The figure below illustrates TDM " "on a link that is used to carry four voice conversations. The vertical " "lines represent the slot boundaries and the letters the different voice " "conversations. One byte from each voice conversation is sent during each " "125 microseconds slot. The byte corresponding to a given conversation is " "always sent at the same position in each slot." msgstr "" #: ../../principles/sharing.rst:300 msgid "Time-division multiplexing" msgstr "" #: ../../principles/sharing.rst:303 msgid "" "TDM as shown above can be completely static, i.e. the same conversations " "always share the link, or dynamic. In the latter case, the two endpoints " "of the link must exchange messages specifying which conversation uses " "which byte inside each slot. Thanks to these control messages, it is " "possible to dynamically add and remove voice conversations from a given " "link." msgstr "" #: ../../principles/sharing.rst:305 msgid "" "TDM and FDM are widely used in telephone networks to support fixed " "bandwidth conversations. Using them in Local Area Networks that support " "computers would probably be inefficient. Computers usually do not send " "information at a fixed rate. Instead, they often have an on-off behavior." " During the on period, the computer tries to send at the highest possible" " rate, e.g. to transfer a file. During the off period, which is often " "much longer than the on period, the computer does not transmit any " "packet. Using a static allocation scheme for computers attached to a LAN " "would lead to huge inefficiencies, as they would only be able to transmit" " at :math:`\\frac{1}{N}` of the total bandwidth during their on period, " "despite the fact that the other computers are in their off period and " "thus do not need to transmit any information. The dynamic MAC algorithms " "discussed in the remainder of this chapter aim solve this problem." msgstr "" #: ../../principles/sharing.rst:309 msgid "ALOHA" msgstr "" #: ../../principles/sharing.rst:313 msgid "" "In the 1960s, computers were mainly mainframes with a few dozen terminals" " attached to them. These terminals were usually in the same building as " "the mainframe and were directly connected to it. In some cases, the " "terminals were installed in remote locations and connected through a " ":term:`modem` attached to a :term:`dial-up line`. The university of " "Hawaii chose a different organization. Instead of using telephone lines " "to connect the distant terminals, they developed the first `packet radio`" " technology [Abramson1970]_. Until then, computer networks were built on " "top of either the telephone network or physical cables. ALOHANet showed " "that it was possible to use radio signals to interconnect computers." msgstr "" #: ../../principles/sharing.rst:317 msgid "" "The first version of ALOHANet, described in [Abramson1970]_, operated as " "follows: First, the terminals and the mainframe exchanged fixed-length " "frames composed of 704 bits. Each frame contained 80 8-bit characters, " "some control bits and parity information to detect transmission errors. " "Two channels in the 400 MHz range were reserved for the operation of " "ALOHANet. The first channel was used by the mainframe to send frames to " "all terminals. The second channel was shared among all terminals to send " "frames to the mainframe. As all terminals share the same transmission " "channel, there is a risk of collision. To deal with this problem as well " "as transmission errors, the mainframe verified the parity bits of the " "received frame and sent an acknowledgment on its channel for each " "correctly received frame. The terminals on the other hand had to " "retransmit the unacknowledged frames. As for TCP, retransmitting these " "frames immediately upon expiration of a fixed timeout is not a good " "approach as several terminals may retransmit their frames at the same " "time leading to a network collapse. A better approach, but still far from" " perfect, is for each terminal to wait a random amount of time after the " "expiration of its retransmission timeout. This avoids synchronization " "among multiple retransmitting terminals." msgstr "" #: ../../principles/sharing.rst:319 msgid "" "The pseudo-code below shows the operation of an ALOHANet terminal. We use" " this python syntax for all Medium Access Control algorithms described in" " this chapter. The algorithm is applied to each new frame that needs to " "be transmitted. It attempts to transmit a frame at most `max` times " "(`while loop`). Each transmission attempt is performed as follows: First," " the frame is sent. Each frame is protected by a timeout. Then, the " "terminal waits for either a valid acknowledgment frame or the expiration " "of its timeout. If the terminal receives an acknowledgment, the frame has" " been delivered correctly and the algorithm terminates. Otherwise, the " "terminal waits for a random time and attempts to retransmit the frame." msgstr "" #: ../../principles/sharing.rst:338 msgid "" "[Abramson1970]_ analyzed the performance of ALOHANet under particular " "assumptions and found that ALOHANet worked well when the channel was " "lightly loaded. In this case, the frames are rarely retransmitted and the" " `channel traffic`, i.e. the total number of (correct and retransmitted) " "frames transmitted per unit of time is close to the `channel " "utilization`, i.e. the number of correctly transmitted frames per unit of" " time. Unfortunately, the analysis also reveals that the `channel " "utilization` reaches its maximum at :math:`\\frac{1}{2 \\times e}=0.186` " "times the channel bandwidth. At higher utilization, ALOHANet becomes " "unstable and the network collapses due to collided retransmissions." msgstr "" #: ../../principles/sharing.rst:341 msgid "Amateur packet radio" msgstr "" #: ../../principles/sharing.rst:343 msgid "" "Packet radio technologies have evolved in various directions since the " "first experiments performed at the University of Hawaii. The Amateur " "packet radio service developed by amateur radio operators is one of the " "descendants ALOHANet. Many amateur radio operators are very interested in" " new technologies and they often spend countless hours developing new " "antennas or transceivers. When the first personal computers appeared, " "several amateur radio operators designed radio modems and their own " "datalink layer protocols [KPD1985]_ [BNT1997]_. This network grew and it " "was possible to connect to servers in several European countries by only " "using packet radio relays. Some amateur radio operators also developed " "TCP/IP protocol stacks that were used over the packet radio service. Some" " parts of the `amateur packet radio network `_ are " "connected to the global Internet and use the `44.0.0.0/8` IPv4 prefix." msgstr "" #: ../../principles/sharing.rst:347 msgid "" "Many improvements to ALOHANet have been proposed since the publication of" " [Abramson1970]_, and this technique, or some of its variants, are still " "found in wireless networks today. The slotted technique proposed in " "[Roberts1975]_ is important because it shows that a simple modification " "can significantly improve channel utilization. Instead of allowing all " "terminals to transmit at any time, [Roberts1975]_ proposed to divide time" " into slots and allow terminals to transmit only at the beginning of each" " slot. Each slot corresponds to the time required to transmit one fixed " "size frame. In practice, these slots can be imposed by a single clock " "that is received by all terminals. In ALOHANet, it could have been " "located on the central mainframe. The analysis in [Roberts1975]_ reveals " "that this simple modification improves the channel utilization by a " "factor of two." msgstr "" #: ../../principles/sharing.rst:353 msgid "Carrier Sense Multiple Access" msgstr "" #: ../../principles/sharing.rst:356 msgid "" "ALOHA and slotted ALOHA can easily be implemented, but unfortunately, " "they can only be used in networks that are very lightly loaded. Designing" " a network for a very low utilization is possible, but it clearly " "increases the cost of the network. To overcome the problems of ALOHA, " "many Medium Access Control mechanisms have been proposed which improve " "channel utilization. Carrier Sense Multiple Access (CSMA) is a " "significant improvement compared to ALOHA. CSMA requires all nodes to " "listen to the transmission channel to verify that it is free before " "transmitting a frame [KT1975]_. When a node senses the channel to be " "busy, it defers its transmission until the channel becomes free again. " "The pseudo-code below provides a more detailed description of the " "operation of CSMA." msgstr "" #: ../../principles/sharing.rst:377 msgid "" "The above pseudo-code is often called `persistent CSMA` [KT1975]_ as the " "terminal will continuously listen to the channel and transmit its frame " "as soon as the channel becomes free. Another important variant of CSMA is" " the `non-persistent CSMA` [KT1975]_. The main difference between " "persistent and non-persistent CSMA described in the pseudo-code below is " "that a non-persistent CSMA node does not continuously listen to the " "channel to determine when it becomes free. When a non-persistent CSMA " "terminal senses the transmission channel to be busy, it waits for a " "random time before sensing the channel again. This improves channel " "utilization compared to persistent CSMA. With persistent CSMA, when two " "terminals sense the channel to be busy, they will both transmit (and thus" " cause a collision) as soon as the channel becomes free. With non-" "persistent CSMA, this synchronization does not occur, as the terminals " "wait a random time after having sensed the transmission channel. However," " the higher channel utilization achieved by non-persistent CSMA comes at " "the expense of a slightly higher waiting time in the terminals when the " "network is lightly loaded." msgstr "" #: ../../principles/sharing.rst:402 #, python-format msgid "" "[KT1975]_ analyzes in detail the performance of several CSMA variants. " "Under some assumptions about the transmission channel and the traffic, " "the analysis compares ALOHA, slotted ALOHA, persistent and non-persistent" " CSMA. Under these assumptions, ALOHA achieves a channel utilization of " "only 18.4% of the channel capacity. Slotted ALOHA is able to use 36.6% of" " this capacity. Persistent CSMA improves the utilization by reaching " "52.9% of the capacity while non-persistent CSMA achieves 81.5% of the " "channel capacity." msgstr "" #: ../../principles/sharing.rst:407 msgid "Carrier Sense Multiple Access with Collision Detection" msgstr "" #: ../../principles/sharing.rst:412 msgid "" "CSMA improves channel utilization compared to ALOHA. However, the " "performance can still be improved, especially in wired networks. Consider" " the situation of two terminals that are connected to the same cable. " "This cable could, for example, be a coaxial cable as in the early days of" " Ethernet [Metcalfe1976]_. It could also be built with twisted pairs. " "Before extending CSMA, it is useful to understand more intuitively, how " "frames are transmitted in such a network and how collisions can occur. " "The figure below illustrates the physical transmission of a frame on such" " a cable. To transmit its frame, host A must send an electrical signal on" " the shared medium. The first step is thus to begin the transmission of " "the electrical signal. This is point `(1)` in the figure below. This " "electrical signal will travel along the cable. Although electrical " "signals travel fast, we know that information cannot travel faster than " "the speed of light (i.e. 300.000 kilometers/second). On a coaxial cable, " "an electrical signal is slightly slower than the speed of light and " "200.000 kilometers per second is a reasonable estimation. This implies " "that if the cable has a length of one kilometer, the electrical signal " "will need 5 microseconds to travel from one end of the cable to the " "other. The ends of coaxial cables are equipped with termination points " "that ensure that the electrical signal is not reflected back to its " "source. This is illustrated at point `(3)` in the figure, where the " "electrical signal has reached the left endpoint and host B. At this " "point, B starts to receive the frame being transmitted by A. Notice that " "there is a delay between the transmission of a bit on host A and its " "reception by host B. If there were other hosts attached to the cable, " "they would receive the first bit of the frame at slightly different " "times. As we will see later, this timing difference is a key problem for " "MAC algorithms. At point `(4)`, the electrical signal has reached both " "ends of the cable and occupies it completely. Host A continues to " "transmit the electrical signal until the end of the frame. As shown at " "point `(5)`, when the sending host stops its transmission, the electrical" " signal corresponding to the end of the frame leaves the coaxial cable. " "The channel becomes empty again once the entire electrical signal has " "been removed from the cable." msgstr "" #: ../../principles/sharing.rst:418 msgid "Frame transmission on a shared bus" msgstr "" #: ../../principles/sharing.rst:420 msgid "" "Now that we have looked at how a frame is actually transmitted as an " "electrical signal on a shared bus, it is interesting to look in more " "detail at what happens when two hosts transmit a frame at almost the same" " time. This is illustrated in the figure below, where hosts A and B start" " their transmission at the same time (point `(1)`). At this time, if host" " C senses the channel, it will consider it to be free. This will not last" " a long time and at point `(2)` the electrical signals from both host A " "and host B reach host C. The combined electrical signal (shown " "graphically as the superposition of the two curves in the figure) cannot " "be decoded by host C. Host C detects a collision, as it receives a signal" " that it cannot decode. Since host C cannot decode the frames, it cannot " "determine which hosts are sending the colliding frames. Note that host A " "(and host B) will detect the collision after host C (point `(3)` in the " "figure below)." msgstr "" #: ../../principles/sharing.rst:427 msgid "Frame collision on a shared bus" msgstr "" #: ../../principles/sharing.rst:433 msgid "" "As shown above, hosts detect collisions when they receive an electrical " "signal that they cannot decode. In a wired network, a host is able to " "detect such a collision both while it is listening (e.g. like host C in " "the figure above) and also while it is sending its own frame. When a host" " transmits a frame, it can compare the electrical signal that it " "transmits with the electrical signal that it senses on the wire. At " "points `(1)` and `(2)` in the figure above, host A senses only its own " "signal. At point `(3)`, it senses an electrical signal that differs from " "its own signal and can thus detects the collision. At this point, its " "frame is corrupted and it can stop its transmission. The ability to " "detect collisions while transmitting is the starting point for the " "`Carrier Sense Multiple Access with Collision Detection (CSMA/CD)` Medium" " Access Control algorithm, which is used in Ethernet networks " "[Metcalfe1976]_ [IEEE802.3]_ . When an Ethernet host detects a collision " "while it is transmitting, it immediately stops its transmission. Compared" " with pure CSMA, CSMA/CD is an important improvement since when " "collisions occur, they only last until colliding hosts have detected it " "and stopped their transmission. In practice, when a host detects a " "collision, it sends a special jamming signal on the cable to ensure that " "all hosts have detected the collision." msgstr "" #: ../../principles/sharing.rst:436 msgid "" "To better understand these collisions, it is useful to analyze what would" " be the worst collision on a shared bus network. Let us consider a wire " "with two hosts attached at both ends, as shown in the figure below. Host " "A starts to transmit its frame and its electrical signal is propagated on" " the cable. Its propagation time depends on the physical length of the " "cable and the speed of the electrical signal. Let us use :math:`\\tau` to" " represent this propagation delay in seconds. Slightly less than " ":math:`\\tau` seconds after the beginning of the transmission of A's " "frame, B decides to start transmitting its own frame. After " ":math:`\\epsilon` seconds, B senses A's frame, detects the collision and " "stops transmitting. The beginning of B's frame travels on the cable until" " it reaches host A. Host A can thus detect the collision at time " ":math:`\\tau-\\epsilon+\\tau \\approx 2\\times\\tau`. An important point " "to note is that a collision can only occur during the first " ":math:`2\\times\\tau` seconds of its transmission. If a collision did not" " occur during this period, it cannot occur afterwards since the " "transmission channel is busy after :math:`\\tau` seconds and CSMA/CD " "hosts sense the transmission channel before transmitting their frame." msgstr "" #: ../../principles/sharing.rst:443 msgid "The worst collision on a shared bus" msgstr "" #: ../../principles/sharing.rst:446 msgid "" "Furthermore, on the wired networks where CSMA/CD is used, collisions are " "almost the only cause of transmission errors that affect frames. " "Transmission errors that only affect a few bits inside a frame seldom " "occur in these wired networks. For this reason, the designers of CSMA/CD " "chose to completely remove the acknowledgment frames in the datalink " "layer. When a host transmits a frame, it verifies whether its " "transmission has been affected by a collision. If not, given the " "negligible Bit Error Ratio of the underlying network, it assumes that the" " frame was received correctly by its destination. Otherwise the frame is " "retransmitted after some delay." msgstr "" #: ../../principles/sharing.rst:449 msgid "" "Removing acknowledgments is an interesting optimization as it reduces the" " number of frames that are exchanged on the network and the number of " "frames that need to be processed by the hosts. However, to use this " "optimization, we must ensure that all hosts will be able to detect all " "the collisions that affect their frames. The problem is important for " "short frames. Let us consider two hosts, A and B, that are sending a " "small frame to host C as illustrated in the figure below. If the frames " "sent by A and B are very short, the situation illustrated below may " "occur. Hosts A and B send their frame and stop transmitting (point " "`(1)`). When the two short frames arrive at the location of host C, they " "collide and host C cannot decode them (point `(2)`). The two frames are " "absorbed by the ends of the wire. Neither host A nor host B have detected" " the collision. They both consider their frame to have been received " "correctly by its destination." msgstr "" #: ../../principles/sharing.rst:456 msgid "The short-frame collision problem" msgstr "" #: ../../principles/sharing.rst:462 msgid "" "To solve this problem, networks using CSMA/CD require hosts to transmit " "for at least :math:`2\\times\\tau` seconds. Since the network " "transmission speed is fixed for a given network technology, this implies " "that a technology that uses CSMA/CD enforces a minimum frame size. In the" " most popular CSMA/CD technology, Ethernet, :math:`2\\times\\tau` is " "called the `slot time` [#fslottime]_." msgstr "" #: ../../principles/sharing.rst:468 msgid "" "The last innovation introduced by CSMA/CD is the computation of the " "retransmission timeout. As for ALOHA, this timeout cannot be fixed, " "otherwise hosts could become synchronized and always retransmit at the " "same time. Setting such a timeout is always a compromise between the " "network access delay and the amount of collisions. A short timeout would " "lead to a low network access delay but with a higher risk of collisions. " "On the other hand, a long timeout would cause a long network access delay" " but a lower risk of collisions. The `binary exponential back-off` " "algorithm was introduced in CSMA/CD networks to solve this problem." msgstr "" #: ../../principles/sharing.rst:470 msgid "" "To understand `binary exponential back-off`, let us consider a collision " "caused by exactly two hosts. Once it has detected the collision, a host " "can either retransmit its frame immediately or defer its transmission for" " some time. If each colliding host flips a coin to decide whether to " "retransmit immediately or to defer its retransmission, four cases are " "possible :" msgstr "" #: ../../principles/sharing.rst:472 msgid "Both hosts retransmit immediately and a new collision occurs" msgstr "" #: ../../principles/sharing.rst:473 msgid "" "The first host retransmits immediately and the second defers its " "retransmission" msgstr "" #: ../../principles/sharing.rst:474 msgid "" "The second host retransmits immediately and the first defers its " "retransmission" msgstr "" #: ../../principles/sharing.rst:475 msgid "Both hosts defer their retransmission and a new collision occurs" msgstr "" #: ../../principles/sharing.rst:477 msgid "" "In the second and third cases, both hosts have flipped different coins. " "The delay chosen by the host that defers its retransmission should be " "long enough to ensure that its retransmission will not collide with the " "immediate retransmission of the other host. However the delay should not " "be longer than the time necessary to avoid the collision, because if both" " hosts decide to defer their transmission, the network will be idle " "during this delay. The `slot time` is the optimal delay since it is the " "shortest delay that ensures that the first host will be able to " "retransmit its frame completely without any collision." msgstr "" #: ../../principles/sharing.rst:479 #, python-format msgid "" "If two hosts are competing, the algorithm above will avoid a second " "collision 50% of the time. However, if the network is heavily loaded, " "several hosts may be competing at the same time. In this case, the hosts " "should be able to automatically adapt their retransmission delay. The " "`binary exponential back-off` performs this adaptation based on the " "number of collisions that have affected a frame. After the first " "collision, the host flips a coin and waits 0 or 1 `slot time`. After the " "second collision, it generates a random number and waits 0, 1, 2 or 3 " "`slot times`, etc. The duration of the waiting time is doubled after each" " collision. The complete pseudo-code for the CSMA/CD algorithm is shown " "in the figure below." msgstr "" #: ../../principles/sharing.rst:504 msgid "" "The inter-frame delay used in this pseudo-code is a short delay " "corresponding to the time required by a network adapter to switch from " "transmit to receive mode. It is also used to prevent a host from sending " "a continuous stream of frames without leaving any transmission " "opportunities for other hosts on the network. This contributes to the " "fairness of CSMA/CD. Despite this delay, there are still conditions where" " CSMA/CD is not completely fair [RY1994]_. Consider for example a network" " with two hosts : a server sending long frames and a client sending " "acknowledgments. Measurements reported in [RY1994]_ have shown that there" " are situations where the client could suffer from repeated collisions " "that lead it to wait for long periods of time due to the exponential " "back-off algorithm." msgstr "" #: ../../principles/sharing.rst:507 msgid "" "This name should not be confused with the duration of a transmission slot" " in slotted ALOHA. In CSMA/CD networks, the slot time is the time during " "which a collision can occur at the beginning of the transmission of a " "frame. In slotted ALOHA, the duration of a slot is the transmission time " "of an entire fixed-size frame." msgstr "" #: ../../principles/sharing.rst:513 msgid "Carrier Sense Multiple Access with Collision Avoidance" msgstr "" #: ../../principles/sharing.rst:515 msgid "" "The `Carrier Sense Multiple Access with Collision Avoidance` (CSMA/CA) " "Medium Access Control algorithm was designed for the popular WiFi " "wireless network technology [IEEE802.11]_. CSMA/CA also senses the " "transmission channel before transmitting a frame. Furthermore, CSMA/CA " "tries to avoid collisions by carefully tuning the timers used by CSMA/CA " "devices." msgstr "" #: ../../principles/sharing.rst:520 msgid "" "CSMA/CA uses acknowledgments like CSMA. Each frame contains a sequence " "number and a CRC. The CRC is used to detect transmission errors while the" " sequence number is used to avoid frame duplication. When a device " "receives a correct frame, it returns a special acknowledgment frame to " "the sender. CSMA/CA introduces a small delay, named `Short Inter Frame " "Spacing` (SIFS), between the reception of a frame and the transmission " "of the acknowledgment frame. This delay corresponds to the time that is " "required to switch the radio of a device between the reception and " "transmission modes." msgstr "" #: ../../principles/sharing.rst:525 msgid "" "Compared to CSMA, CSMA/CA defines more precisely when a device is allowed" " to send a frame. First, CSMA/CA defines two delays : `DIFS` and `EIFS`. " "To send a frame, a device must first wait until the channel has been idle" " for at least the `Distributed Coordination Function Inter Frame Space` " "(DIFS) if the previous frame was received correctly. However, if the " "previously received frame was corrupted, this indicates that there are " "collisions and the device must sense the channel idle for at least the " "`Extended Inter Frame Space` (EIFS), with :math:`SIFS