msgid "" msgstr "" "Project-Id-Version: French (cnp3-ebook)\n" "Report-Msgid-Bugs-To: \n" "POT-Creation-Date: 2026-04-18 14:27+0200\n" "PO-Revision-Date: YEAR-MO-DA HO:MI+ZONE\n" "Last-Translator: FULL NAME \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 5.14.3\n" #: ../../principles/reliability.rst:194 msgid "" "To enable the transmission/reception of frames, the first problem to be " "solved is how to encode a frame as a sequence of bits, so that the receiver " "can easily recover the received frame despite the limitations of the " "physical layer." msgstr "" #: ../../principles/reliability.rst:199 msgid "" "If the physical layer were perfect, the problem would be very simple. We " "would simply need to define how to encode each frame as a sequence of " "consecutive bits. The receiver would then easily be able to extract the " "frames from the received bits. Unfortunately, the imperfections of the " "physical layer make this framing problem slightly more complex. Several " "solutions have been proposed and are used in practice in different network " "technologies." msgstr "" #: ../../principles/reliability.rst:202 msgid "Framing" msgstr "" #: ../../principles/reliability.rst:204 msgid "" "The `framing` problem can be defined as : \"`How does a sender encode frames " "so that the receiver can efficiently extract them from the stream of bits " "that it receives from the physical layer`\"." msgstr "" #: ../../principles/reliability.rst:206 msgid "" "A first solution to this problem is to require the physical layer to remain " "idle for some time after the transmission of each frame. These idle periods " "can be detected by the receiver and serve as a marker to delineate frame " "boundaries. Unfortunately, this solution is not acceptable for two reasons. " "First, some physical layers cannot remain idle and always need to transmit " "bits. Second, inserting an idle period between frames decreases the maximum " "bit rate that can be achieved." msgstr "" #: ../../principles/reliability.rst:208 msgid "Bit rate and bandwidth" msgstr "" #: ../../principles/reliability.rst:210 msgid "" "Bit rate and bandwidth are often used to characterize the transmission " "capacity of the physical service. The original definition of `bandwidth " "`_, as listed in the `" "Webster dictionary `_ is `a " "range of radio frequencies which is occupied by a modulated carrier wave, " "which is assigned to a service, or over which a device can operate`. This " "definition corresponds to the characteristics of a given transmission medium " "or receiver. For example, the human ear is able to decode sounds in roughly " "the 0-20 KHz frequency range. By extension, bandwidth is also used to " "represent the capacity of a communication system in bits per second. For " "example, a Gigabit Ethernet link is theoretically capable of transporting " "one billion bits per second." msgstr "" #: ../../principles/reliability.rst:215 msgid "" "Given that multi-symbol encodings cannot be used by all physical layers, a " "generic solution which can be used with any physical layer that is able to " "transmit and receive only bits `0` and `1` is required. This generic " "solution is called `stuffing` and two variants exist : `bit stuffing` and `" "character stuffing`. To enable a receiver to easily delineate the frame " "boundaries, these two techniques reserve special bit strings as frame " "boundary markers and encode the frames so that these special bit strings do " "not appear inside the frames." msgstr "" #: ../../principles/reliability.rst:217 msgid "" "`Bit stuffing` reserves the `01111110` bit string as the frame boundary " "marker and ensures that there will never be six consecutive `1` symbols " "transmitted by the physical layer inside a frame. With bit stuffing, a frame " "is sent as follows. First, the sender transmits the marker, i.e. `01111110`. " "Then, it sends all the bits of the frame and inserts an additional bit set " "to `0` after each sequence of five consecutive `1` bits. This ensures that " "the sent frame never contains a sequence of six consecutive bits set to `1`. " "As a consequence, the marker pattern cannot appear inside the frame sent. " "The marker is also sent to mark the end of the frame. The receiver performs " "the opposite to decode a received frame. It first detects the beginning of " "the frame thanks to the `01111110` marker. Then, it processes the received " "bits and counts the number of consecutive bits set to `1`. If a `0` follows " "five consecutive bits set to `1`, this bit is removed since it was inserted " "by the sender. If a `1` follows five consecutive bits sets to `1`, it " "indicates a marker if it is followed by a bit set to `0`. The table below " "illustrates the application of bit stuffing to some frames." msgstr "" #: ../../principles/reliability.rst:220 #: ../../principles/reliability.rst:258 msgid "Original frame" msgstr "" #: ../../principles/reliability.rst:220 #: ../../principles/reliability.rst:258 msgid "Transmitted frame" msgstr "" #: ../../principles/reliability.rst:222 msgid "0001001001001001001000011" msgstr "" #: ../../principles/reliability.rst:222 msgid "01111110000100100100100100100001101111110" msgstr "" #: ../../principles/reliability.rst:223 msgid "0110111111111111111110010" msgstr "" #: ../../principles/reliability.rst:223 msgid "01111110011011111011111011111011001001111110" msgstr "" #: ../../principles/reliability.rst:224 msgid "01111110" msgstr "" #: ../../principles/reliability.rst:224 msgid "0111111001111101001111110" msgstr "" #: ../../principles/reliability.rst:228 msgid "" "For example, consider the transmission of `0110111111111111111110010`. The " "sender will first send the `01111110` marker followed by `011011111`. After " "these five consecutive bits set to `1`, it inserts a bit set to `0` followed " "by `11111`. A new `0` is inserted, followed by `11111`. A new `0` is " "inserted followed by the end of the frame `110010` and the `01111110` marker." msgstr "" #: ../../principles/reliability.rst:231 msgid "" "`Bit stuffing` increases the number of bits required to transmit each frame. " "The worst case for bit stuffing is of course a long sequence of bits set to " "`1` inside the frame. If transmission errors occur, stuffed bits or markers " "can be in error. In these cases, the frame affected by the error and " "possibly the next frame will not be correctly decoded by the receiver, but " "it will be able to resynchronize itself at the next valid marker." msgstr "" #: ../../principles/reliability.rst:236 msgid "" "`Bit stuffing` can be easily implemented in hardware. However, implementing " "it in software is difficult given the complexity of performing bit " "manipulations in software. Software implementations prefer to process " "characters than bits, software-based datalink layers usually use `character " "stuffing`. This technique operates on frames that contain an integer number " "of characters. In computer networks, characters are usually encoded by " "relying on the :term:`ASCII` table. This table defines the encoding of " "various alphanumeric characters as a sequence of bits. :rfc:`20` provides " "the ASCII table that is used by many protocols on the Internet. For example, " "the table defines the following binary representations :" msgstr "" #: ../../principles/reliability.rst:238 msgid "`A` : `1000011` b" msgstr "" #: ../../principles/reliability.rst:239 msgid "`0` : `0110000` b" msgstr "" #: ../../principles/reliability.rst:240 msgid "`z` : `1111010` b" msgstr "" #: ../../principles/reliability.rst:241 msgid "`@` : `1000000` b" msgstr "" #: ../../principles/reliability.rst:242 msgid "`space` : `0100000` b" msgstr "" #: ../../principles/reliability.rst:244 msgid "" "In addition, the :term:`ASCII` table also defines several non-printable or " "control characters. These characters were designed to allow an application " "to control a printer or a terminal. These control characters include `CR` " "and `LF`, that are used to terminate a line, and the `BEL` character which " "causes the terminal to emit a sound." msgstr "" #: ../../principles/reliability.rst:246 msgid "`NUL`: `0000000` b" msgstr "" #: ../../principles/reliability.rst:247 msgid "`BEL`: `0000111` b" msgstr "" #: ../../principles/reliability.rst:248 msgid "`CR` : `0001101` b" msgstr "" #: ../../principles/reliability.rst:249 msgid "`LF` : `0001010` b" msgstr "" #: ../../principles/reliability.rst:250 msgid "`DLE`: `0010000` b" msgstr "" #: ../../principles/reliability.rst:251 msgid "`STX`: `0000010` b" msgstr "" #: ../../principles/reliability.rst:252 msgid "`ETX`: `0000011` b" msgstr "" #: ../../principles/reliability.rst:254 msgid "" "Some characters are used as markers to delineate the frame boundaries. Many `" "character stuffing` techniques use the `DLE`, `STX` and `ETX` characters of " "the ASCII character set. `DLE STX` (resp. `DLE ETX`) is used to mark the " "beginning (end) of a frame. When transmitting a frame, the sender adds a " "`DLE` character after each transmitted `DLE` character. This ensures that " "none of the markers can appear inside the transmitted frame. The receiver " "detects the frame boundaries and removes the second `DLE` when it receives " "two consecutive `DLE` characters. For example, to transmit frame `1 2 3 DLE " "STX 4`, a sender will first send `DLE STX` as a marker, followed by `1 2 3 " "DLE`. Then, the sender transmits an additional `DLE` character followed by `" "STX 4` and the `DLE ETX` marker." msgstr "" #: ../../principles/reliability.rst:260 msgid "**1** **2** **3** **4**" msgstr "" #: ../../principles/reliability.rst:260 msgid "`DLE STX` **1** **2** **3** **4** `DLE ETX`" msgstr "" #: ../../principles/reliability.rst:261 msgid "**1** **2** **3** **DLE** **STX** **4**" msgstr "" #: ../../principles/reliability.rst:261 msgid "`DLE STX` **1** **2** **3** **DLE** `DLE` **STX** `4` `DLE ETX`" msgstr "" #: ../../principles/reliability.rst:262 msgid "**DLE STX DLE ETX**" msgstr "" #: ../../principles/reliability.rst:262 msgid "`DLE STX` **DLE** `DLE` **STX** **DLE** `DLE` ETX** `DLE ETX`" msgstr "" #: ../../principles/reliability.rst:304 msgid "Recovering from transmission errors" msgstr "" #: ../../principles/reliability.rst:306 msgid "" "In this section, we develop a reliable datalink protocol running above the " "physical layer service. To design this protocol, we first assume that the " "physical layer provides a perfect service. We will then develop solutions to " "recover from the transmission errors." msgstr "" #: ../../principles/reliability.rst:308 msgid "" "The datalink layer is designed to send and receive frames on behalf of a " "user. We model these interactions by using the `DATA.req` and `DATA.ind` " "primitives. However, to simplify the presentation and to avoid confusion " "between a `DATA.req` primitive issued by the user of the datalink layer " "entity, and a `DATA.req` issued by the datalink layer entity itself, we will " "use the following terminology :" msgstr "" #: ../../principles/reliability.rst:310 msgid "" "the interactions between the user and the datalink layer entity are " "represented by using the classical `DATA.req` and the `DATA.ind` primitives" msgstr "" #: ../../principles/reliability.rst:311 msgid "" "the interactions between the datalink layer entity and the framing sub-layer " "are represented by using `send` instead of `DATA.req` and `recvd` instead of " "`DATA.ind`" msgstr "" #: ../../principles/reliability.rst:334 msgid "" "To solve this problem, a reliable protocol must include a feedback mechanism " "that allows the receiver to inform the sender that it has processed a frame " "and that another one can be sent. This feedback is required even though " "there are no transmission errors. To include such a feedback, our reliable " "protocol must process two types of frames :" msgstr "" #: ../../principles/reliability.rst:336 msgid "data frames carrying a SDU" msgstr "" #: ../../principles/reliability.rst:339 msgid "" "These two types of frames can be distinguished by dividing the frame in two " "parts :" msgstr "" #: ../../principles/reliability.rst:341 msgid "" "the `header` that contains one bit set to `0` in data frames and set to `1` " "in control frames" msgstr "" #: ../../principles/reliability.rst:342 msgid "the payload that contains the SDU supplied by the application" msgstr "" #: ../../principles/reliability.rst:344 msgid "" "The datalink entity can then be modeled as a finite state machine, " "containing two states for the receiver and two states for the sender. The " "figure below provides a graphical representation of this state machine with " "the sender above and the receiver below." msgstr "" #: ../../principles/reliability.rst:353 msgid "" "The above FSM shows that the sender has to wait for an acknowledgment from " "the receiver before being able to transmit the next SDU. The figure below " "illustrates the exchange of a few frames between two hosts." msgstr "" #: ../../principles/reliability.rst:372 msgid "Services and protocols" msgstr "" #: ../../principles/reliability.rst:389 msgid "Reliable data transfer on top of an imperfect link" msgstr "" #: ../../principles/reliability.rst:391 msgid "" "The datalink layer must deal with the transmission errors. In practice, we " "mainly have to deal with two types of errors in the datalink layer :" msgstr "" #: ../../principles/reliability.rst:393 msgid "Frames can be corrupted by transmission errors" msgstr "" #: ../../principles/reliability.rst:394 msgid "Frames can be lost or unexpected frames can appear" msgstr "" #: ../../principles/reliability.rst:399 msgid "" "To deal with these types of imperfections, reliable protocols rely on " "different types of mechanisms. The first problem is transmission errors. " "Data transmission on a physical link can be affected by the following errors " ":" msgstr "" #: ../../principles/reliability.rst:401 msgid "" "random isolated errors where the value of a single bit has been modified due " "to a transmission error" msgstr "" #: ../../principles/reliability.rst:402 msgid "" "random burst errors where the values of `n` consecutive bits have been " "changed due to transmission errors" msgstr "" #: ../../principles/reliability.rst:403 msgid "" "random bit creations and random bit removals where bits have been added or " "removed due to transmission errors" msgstr "" #: ../../principles/reliability.rst:405 msgid "" "The only solution to protect against transmission errors is to add " "redundancy to the frames that are sent. `Information Theory` defines two " "mechanisms that can be used to transmit information over a transmission " "channel affected by random errors. These two mechanisms add redundancy to " "the transmitted information, to allow the receiver to detect or sometimes " "even correct transmission errors. A detailed discussion of these mechanisms " "is outside the scope of this chapter, but it is useful to consider a simple " "mechanism to understand its operation and its limitations." msgstr "" #: ../../principles/reliability.rst:407 msgid "" "`Information theory` defines `coding schemes`. There are different types of " "coding schemes, but let us focus on coding schemes that operate on binary " "strings. A coding scheme is a function that maps information encoded as a " "string of `m` bits into a string of `n` bits. The simplest coding scheme is " "the (even) parity coding. This coding scheme takes an `m` bits source string " "and produces an `m+1` bits coded string where the first `m` bits of the " "coded string are the bits of the source string and the last bit of the coded " "string is chosen such that the coded string will always contain an even " "number of bits set to `1`. For example :" msgstr "" #: ../../principles/reliability.rst:409 msgid "`1001` is encoded as `10010`" msgstr "" #: ../../principles/reliability.rst:410 msgid "`1101` is encoded as `11011`" msgstr "" #: ../../principles/reliability.rst:412 msgid "" "This parity scheme has been used in some RAMs as well as to encode " "characters sent over a serial line. It is easy to show that this coding " "scheme allows the receiver to detect a single transmission error, but it " "cannot correct it. However, if two or more bits are in error, the receiver " "may not always be able to detect the error." msgstr "" #: ../../principles/reliability.rst:414 msgid "" "Some coding schemes allow the receiver to correct some transmission errors. " "For example, consider the coding scheme that encodes each source bit as " "follows :" msgstr "" #: ../../principles/reliability.rst:416 msgid "`1` is encoded as `111`" msgstr "" #: ../../principles/reliability.rst:417 msgid "`0` is encoded as `000`" msgstr "" #: ../../principles/reliability.rst:419 msgid "" "For example, consider a sender that sends `111`. If there is one bit in " "error, the receiver could receive `011` or `101` or `110`. In these three " "cases, the receiver will decode the received bit pattern as a `1` since it " "contains a majority of bits set to `1`. If there are two bits in error, the " "receiver will not be able anymore to recover from the transmission error." msgstr "" #: ../../principles/reliability.rst:426 msgid "" "To understand `error detection codes`, let us consider two devices that " "exchange bit strings containing `N` bits. To allow the receiver to detect a " "transmission error, the sender converts each string of `N` bits into a " "string of `N+r` bits. Usually, the `r` redundant bits are added at the " "beginning or the end of the transmitted bit string, but some techniques " "interleave redundant bits with the original bits. An `error detection code` " "can be defined as a function that computes the `r` redundant bits " "corresponding to each string of `N` bits. The simplest error detection code " "is the parity bit. There are two types of parity schemes : even and odd " "parity. With the `even` (resp. `odd`) parity scheme, the redundant bit is " "chosen so that an even (resp. odd) number of bits are set to `1` in the " "transmitted bit string of `N+r` bits. The receiver can easily recompute the " "parity of each received bit string and discard the strings with an invalid " "parity. The parity scheme is often used when 7-bit characters are exchanged. " "In this case, the eighth bit is often a parity bit. The table below shows " "the parity bits that are computed for bit strings containing three bits." msgstr "" #: ../../principles/reliability.rst:429 msgid "3 bits string" msgstr "" #: ../../principles/reliability.rst:429 msgid "Odd parity" msgstr "" #: ../../principles/reliability.rst:429 msgid "Even parity" msgstr "" #: ../../principles/reliability.rst:431 #: ../../principles/reliability.rst:448 msgid "000" msgstr "" #: ../../principles/reliability.rst:431 #: ../../principles/reliability.rst:432 #: ../../principles/reliability.rst:433 #: ../../principles/reliability.rst:434 #: ../../principles/reliability.rst:435 #: ../../principles/reliability.rst:436 #: ../../principles/reliability.rst:437 #: ../../principles/reliability.rst:438 #: ../../principles/reliability.rst:452 #: ../../principles/reliability.rst:453 #: ../../principles/reliability.rst:454 #: ../../principles/reliability.rst:455 msgid "1" msgstr "" #: ../../principles/reliability.rst:432 #: ../../principles/reliability.rst:449 msgid "001" msgstr "" #: ../../principles/reliability.rst:433 #: ../../principles/reliability.rst:450 msgid "010" msgstr "" #: ../../principles/reliability.rst:434 #: ../../principles/reliability.rst:451 msgid "100" msgstr "" #: ../../principles/reliability.rst:435 #: ../../principles/reliability.rst:452 msgid "111" msgstr "" #: ../../principles/reliability.rst:436 #: ../../principles/reliability.rst:453 msgid "110" msgstr "" #: ../../principles/reliability.rst:437 #: ../../principles/reliability.rst:454 msgid "101" msgstr "" #: ../../principles/reliability.rst:438 #: ../../principles/reliability.rst:455 msgid "011" msgstr "" #: ../../principles/reliability.rst:441 msgid "" "The parity bit allows a receiver to detect transmission errors that have " "affected a single bit among the transmitted `N+r` bits. If there are two or " "more bits in error, the receiver may not necessarily be able to detect the " "transmission error. More powerful error detection schemes have been defined. " "The Cyclical Redundancy Checks (CRC) are widely used in datalink layer " "protocols. An N-bits CRC can detect all transmission errors affecting a " "burst of less than N bits in the transmitted frame and all transmission " "errors that affect an odd number of bits. Additional details about CRCs may " "be found in [Williams1993]_." msgstr "" #: ../../principles/reliability.rst:443 msgid "" "It is also possible to design a code that allows the receiver to correct " "transmission errors. The simplest `error correction code` is the triple " "modular redundancy (TMR). To transmit a bit set to `1` (resp. `0`), the " "sender transmits `111` (resp. `000`). When there are no transmission errors, " "the receiver can decode `111` as `1`. If transmission errors have affected a " "single bit, the receiver performs majority voting as shown in the table " "below. This scheme allows the receiver to correct all transmission errors " "that affect a single bit." msgstr "" #: ../../principles/reliability.rst:446 msgid "Received bits" msgstr "" #: ../../principles/reliability.rst:446 msgid "Decoded bit" msgstr "" #: ../../principles/reliability.rst:458 msgid "" "Other more powerful error correction codes have been proposed and are used " "in some applications. The `Hamming Code `_ is a clever combination of parity bits that provides error " "detection and correction capabilities." msgstr "" #: ../../principles/reliability.rst:461 msgid "" "Reliable protocols use error detection schemes, but none of the widely used " "reliable protocols rely on error correction schemes. To detect errors, a " "frame is usually divided into two parts :" msgstr "" #: ../../principles/reliability.rst:463 msgid "" "a `header` that contains the fields used by the reliable protocol to ensure " "reliable delivery. The header contains a checksum or Cyclical Redundancy " "Check (CRC) [Williams1993]_ that is used to detect transmission errors" msgstr "" #: ../../principles/reliability.rst:464 msgid "a `payload` that contains the user data" msgstr "" #: ../../principles/reliability.rst:466 msgid "" "Some headers also include a `length` field, which indicates the total length " "of the frame or the length of the payload." msgstr "" #: ../../principles/reliability.rst:468 msgid "" "The simplest error detection scheme is the checksum. A checksum is basically " "an arithmetic sum of all the bytes that a frame is composed of. There are " "different types of checksums. For example, an eight bit checksum can be " "computed as the arithmetic sum of all the bytes of " "(both the header and trailer of) the frame. The checksum is computed by the " "sender before sending the frame and the receiver verifies the checksum upon " "frame reception. The receiver discards frames received with an invalid " "checksum. Checksums can be easily implemented in software, but their error " "detection capabilities are limited. Cyclical Redundancy Checks (CRC) have " "better error detection capabilities [SGP98]_, but require more CPU when " "implemented in software." msgstr "" #: ../../principles/reliability.rst:552 msgid "" "To solve this problem, datalink protocols associate a `sequence number` to " "each data frame. This `sequence number` is one of the fields found in the " "header of data frames. We use the notation `D(x,...)` to indicate a data " "frame whose sequence number field is set to value `x`. The acknowledgments " "also contain a sequence number indicating the data frames that it is " "acknowledging. We use `OKx` to indicate an acknowledgment frame that " "confirms the reception of `D(x,...)`. The sequence number is encoded as a " "bit string of fixed length. The simplest reliable protocol is the " "Alternating Bit Protocol (ABP)." msgstr "" #: ../../principles/reliability.rst:567 msgid "" "The initial state of the sender is `Wait for D(0,...)`. In this state, the " "sender waits for a `Data.request`. The first data frame that it sends uses " "sequence number `0`. After having sent this frame, the sender waits for an " "`OK0` acknowledgment. A frame is retransmitted upon expiration of the " "retransmission timer or if an acknowledgment with an incorrect sequence " "number has been received." msgstr "" #: ../../principles/reliability.rst:569 msgid "" "The receiver first waits for `D(0,...)`. If the frame contains a correct " "`CRC`, it passes the SDU to its user and sends `OK0`. If the frame contains " "an invalid CRC, it is immediately discarded. Then, the receiver waits for `D" "(1,...)`. In this state, it may receive a duplicate `D(0,...)` or a data " "frame with an invalid CRC. In both cases, it returns an `OK0` frame to allow " "the sender to recover from the possible loss of the previous `OK0` frame." msgstr "" #: ../../principles/reliability.rst:579 msgid "Dealing with corrupted frames" msgstr "" #: ../../principles/reliability.rst:581 msgid "" "The receiver FSM of the Alternating bit protocol discards all frames that " "contain an invalid CRC. This is the safest approach since the received frame " "can be completely different from the frame sent by the remote host. A " "receiver should not attempt at extracting information from a corrupted frame " "because it cannot know which portion of the frame has been affected by the " "error." msgstr "" #: ../../principles/reliability.rst:584 msgid "" "The figure below illustrates the operation of the alternating bit protocol." msgstr "" #: ../../principles/reliability.rst:675 msgid "" "The Alternating Bit Protocol can recover from transmission errors and frame " "losses. However, it has one important drawback. Consider two hosts that are " "directly connected by a 50 Kbits/sec satellite link that has a 250 " "milliseconds propagation delay. If these hosts send 1000 bits frames, then " "the maximum throughput that can be achieved by the alternating bit protocol " "is one frame every :math:`20+250+250=520` milliseconds if we ignore the " "transmission time of the acknowledgment. This is less than 2 Kbits/sec !" msgstr "" #: ../../principles/reliability.rst:685 msgid "Go-back-n and selective repeat" msgstr "" #: ../../principles/reliability.rst:693 msgid "Pipelining improves the performance of reliable protocols" msgstr "" #: ../../principles/reliability.rst:695 msgid "" "`Pipelining` allows the sender to transmit frames at a higher rate. However " "this higher transmission rate may overload the receiver. In this case, the " "frames sent by the sender will not be correctly received by their final " "destination. The reliable protocols that rely on pipelining allow the sender " "to transmit `W` unacknowledged frames before being forced to wait for an " "acknowledgment from the receiving entity." msgstr "" #: ../../principles/reliability.rst:703 msgid "The sliding window" msgstr "" #: ../../principles/reliability.rst:712 msgid "Sliding window example" msgstr "" #: ../../principles/reliability.rst:715 msgid "" "In practice, as the frame header includes an `n` bits field to encode the " "sequence number, only the sequence numbers between :math:`0` and " ":math:`2^{n}-1` can be used. This implies that, during a long transfer, the " "same sequence number will be used for different frames and the sliding " "window will wrap. This is illustrated in the figure below assuming that `2` " "bits are used to encode the sequence number in the frame header. Note that " "upon reception of `OK1`, the sender slides its window and can use sequence " "number `0` again." msgstr "" #: ../../principles/reliability.rst:722 msgid "Utilisation of the sliding window with modulo arithmetic" msgstr "" #: ../../principles/reliability.rst:727 msgid "" "Unfortunately, frame losses do not disappear because a reliable protocol " "uses a sliding window. To recover from losses, a sliding window protocol " "must define :" msgstr "" #: ../../principles/reliability.rst:729 msgid "a heuristic to detect frame losses" msgstr "" #: ../../principles/reliability.rst:730 msgid "a `retransmission strategy` to retransmit the lost frames" msgstr "" #: ../../principles/reliability.rst:737 msgid "" "The figure below shows the FSM of a simple `go-back-n` receiver. This " "receiver uses two variables : `lastack` and `next`. `next` is the next " "expected sequence number and `lastack` the sequence number of the last data " "frame that has been acknowledged. The receiver only accepts the frame that " "are received in sequence. `maxseq` is the number of different sequence " "numbers (:math:`2^n`)." msgstr "" #: ../../principles/reliability.rst:757 msgid "" "The operation of `go-back-n` is illustrated in the figure below. In this " "figure, note that upon reception of the out-of-sequence frame `D(2,c)`, the " "receiver returns a cumulative acknowledgment `C(OK,0)` that acknowledges all " "the frames that have been received in sequence. The lost frame is " "retransmitted upon the expiration of the retransmission timer." msgstr "" #: ../../principles/reliability.rst:763 msgid "Go-back-n : example" msgstr "" #: ../../principles/reliability.rst:766 msgid "" "The main advantage of `go-back-n` is that it can be easily implemented, and " "it can also provide good performance when only a few frames are lost. " "However, when there are many losses, the performance of `go-back-n` quickly " "drops for two reasons :" msgstr "" #: ../../principles/reliability.rst:768 msgid "the `go-back-n` receiver does not accept out-of-sequence frames" msgstr "" #: ../../principles/reliability.rst:769 msgid "" "the `go-back-n` sender retransmits all unacknowledged frames once it has " "detected a loss" msgstr "" #: ../../principles/reliability.rst:776 msgid "" "`Selective repeat` is a better strategy to recover from losses. Intuitively, " "`selective repeat` allows the receiver to accept out-of-sequence frames. " "Furthermore, when a `selective repeat` sender detects losses, it only " "retransmits the frames that have been lost and not the frames that have " "already been correctly received." msgstr "" #: ../../principles/reliability.rst:778 msgid "" "A `selective repeat` receiver maintains a sliding window of `W` frames and " "stores in a buffer the out-of-sequence frames that it receives. The figure " "below shows a five-frame receive window on a receiver that has already " "received frames `7` and `9`." msgstr "" #: ../../principles/reliability.rst:784 msgid "The receiving window with selective repeat" msgstr "" #: ../../principles/reliability.rst:786 msgid "" "A `selective repeat` receiver discards all frames having an invalid CRC, and " "maintains the variable `lastack` as the sequence number of the last in-" "sequence frame that it has received. The receiver always includes the value " "of `lastack` in the acknowledgments that it sends. Some protocols also allow " "the `selective repeat` receiver to acknowledge the out-of-sequence frames " "that it has received. This can be done for example by placing the list of " "the correctly received, but out-of-sequence frames in the acknowledgments " "together with the `lastack` value." msgstr "" #: ../../principles/reliability.rst:788 msgid "" "When a `selective repeat` receiver receives a data frame, it first verifies " "whether the frame is inside its receiving window. If yes, the frame is " "placed in the receive buffer. If not, the received frame is discarded and an " "acknowledgment containing `lastack` is sent to the sender. The receiver then " "removes all consecutive frames starting at `lastack` (if any) from the " "receive buffer. The payloads of these frames are delivered to the user, " "`lastack` and the receiving window are updated, and an acknowledgment " "acknowledging the last frame received in sequence is sent." msgstr "" #: ../../principles/reliability.rst:790 msgid "" "The `selective repeat` sender maintains a sending buffer that can store up " "to `W` unacknowledged frames. These frames are sent as long as the sending " "buffer is not full. Several implementations of a `selective repeat` sender " "are possible. A simple implementation associates one retransmission timer to " "each frame. The timer is started when the frame is sent and canceled upon " "reception of an acknowledgment that covers this frame. When a retransmission " "timer expires, the corresponding frame is retransmitted and this " "retransmission timer is restarted. When an acknowledgment is received, all " "the frames that are covered by this acknowledgment are removed from the " "sending buffer and the sliding window is updated." msgstr "" #: ../../principles/reliability.rst:792 msgid "" "The figure below illustrates the operation of `selective repeat` when frames " "are lost. In this figure, `C(OK,x)` is used to indicate that all frames, up " "to and including sequence number `x` have been received correctly." msgstr "" #: ../../principles/reliability.rst:798 msgid "Selective repeat : example" msgstr "" #: ../../principles/reliability.rst:802 msgid "" "Pure cumulative acknowledgments work well with the `go-back-n` strategy. " "However, with only cumulative acknowledgments a `selective repeat` sender " "cannot easily determine which frames have been correctly received after a " "data frame has been lost. For example, in the figure above, the second `C" "(OK,0)` does not inform explicitly the sender of the reception of `D(2,c)` " "and the sender could retransmit this frame although it has already been " "received. A possible solution to improve the performance of `selective " "repeat` is to provide additional information about the received frames in " "the acknowledgments that are returned by the receiver. For example, the " "receiver could add in the returned acknowledgment the list of the sequence " "numbers of all frames that have already been received. Such acknowledgments " "are sometimes called `selective acknowledgments`. This is illustrated in the " "figure above." msgstr "" #: ../../principles/reliability.rst:811 msgid "" "In the figure above, when the sender receives `C(OK,0,[2])`, it knows that " "all frames up to and including `D(0,...)` have been correctly received. It " "also knows that frame `D(2,...)` has been received and can cancel the " "retransmission timer associated to this frame. However, this frame should " "not be removed from the sending buffer before the reception of a cumulative " "acknowledgment (`C(OK,2)` in the figure above) that covers this frame." msgstr "" #: ../../principles/reliability.rst:817 msgid "" "A reliable protocol that uses `n` bits to encode its sequence number can " "send up to :math:`2^n` successive frames. However, to ensure a reliable " "delivery of the frames, `go-back-n` and `selective repeat` cannot use a " "sending window of :math:`2^n` frames. Consider first `go-back-n` and assume " "that a sender sends :math:`2^n` frames. These frames are received in-" "sequence by the destination, but all the returned acknowledgments are lost. " "The sender will retransmit all frames. These frames will all be accepted by " "the receiver and delivered a second time to the user. It is easy to see that " "this problem can be avoided if the maximum size of the sending window is " ":math:`{2^n}-1` frames. A similar problem occurs with `selective repeat`. " "However, as the receiver accepts out-of-sequence frames, a sending window of " ":math:`{2^n}-1` frames is not sufficient to ensure a reliable delivery. It " "can be easily shown that to avoid this problem, a `selective repeat` sender " "cannot use a window that is larger than :math:`\\frac{2^n}{2}` frames." msgstr "" #: ../../principles/reliability.rst:863 msgid "" "Reliable protocols often need to send data in both directions. To reduce the " "overhead caused by the acknowledgments, most reliable protocols use " "`piggybacking`. Thanks to this technique, a datalink entity can place the " "acknowledgments and the receive window that it advertises for the opposite " "direction of the data flow inside the header of the data frames that it " "sends. The main advantage of piggybacking is that it reduces the overhead as " "it is not necessary to send a complete frame to carry an acknowledgment. " "This is illustrated in the figure below where the acknowledgment number is " "underlined in the data frames. Piggybacking is only used when data flows in " "both directions. A receiver will generate a pure acknowledgment when it does " "not send data in the opposite direction as shown in the bottom of the figure." msgstr "" #: ../../principles/reliability.rst:869 msgid "Piggybacking example" msgstr "" #: ../../principles/reliability.rst:879 msgid "" "The size of the sliding window can be either fixed for a given protocol or " "negotiated during the connection establishment phase. Some protocols allow " "to change the maximum window size during the data transfer. We will explain " "these techniques with real protocols later." msgstr ""