Exit Zen
147
../../principles/reliability.rst:466
English
Some headers also include a `length` field, which indicates the total length of the frame or the length of the payload.
0/1190 · 119
148
../../principles/reliability.rst:468
English
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.
0/7420 · 742
153
../../principles/reliability.rst:552
English
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).
0/6060 · 606
156
../../principles/reliability.rst:567
English
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.
0/3920 · 392
157
../../principles/reliability.rst:569
English
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.
0/4480 · 448
159
../../principles/reliability.rst:579
English
Dealing with corrupted frames
0/290 · 29
160
../../principles/reliability.rst:581
English
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.
0/3790 · 379
161
../../principles/reliability.rst:584
English
The figure below illustrates the operation of the alternating bit protocol.
0/750 · 75
164
../../principles/reliability.rst:675
English
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 !
0/5140 · 514
165
../../principles/reliability.rst:685
English
Go-back-n and selective repeat
0/300 · 30
167
../../principles/reliability.rst:693
English
Pipelining improves the performance of reliable protocols
0/570 · 57
168
../../principles/reliability.rst:695
English
`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.
0/4140 · 414
170
../../principles/reliability.rst:703
English
The sliding window
0/180 · 18
172
../../principles/reliability.rst:712
English
Sliding window example
0/220 · 22
173
../../principles/reliability.rst:715
English
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.
0/5290 · 529
174
../../principles/reliability.rst:722
English
Utilisation of the sliding window with modulo arithmetic
0/560 · 56
175
../../principles/reliability.rst:727
English
Unfortunately, frame losses do not disappear because a reliable protocol uses a sliding window. To recover from losses, a sliding window protocol must define :
0/1590 · 159
176
../../principles/reliability.rst:729
English
a heuristic to detect frame losses
0/340 · 34
177
../../principles/reliability.rst:730
English
a `retransmission strategy` to retransmit the lost frames
0/570 · 57
179
../../principles/reliability.rst:737
English
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`).
0/3850 · 385