Exit Zen
47
../../principles/reliability.rst:204
English
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`".
0/1930 · 193
48
../../principles/reliability.rst:206
English
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.
0/4820 · 482
49
../../principles/reliability.rst:208
English
Bit rate and bandwidth
0/220 · 22
50
../../principles/reliability.rst:210
English
Bit rate and bandwidth are often used to characterize the transmission capacity of the physical service. The original definition of `bandwidth <https://www.merriam-webster.com/dictionary/bandwidth>`_, as listed in the `Webster dictionary <https://www.merriam-webster.com/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.
0/8370 · 837
51
../../principles/reliability.rst:215
English
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.
0/5410 · 541
52
../../principles/reliability.rst:217
English
`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.
0/11800 · 1180
53
../../principles/reliability.rst:220 • ../../principles/reliability.rst:258
English
Original frame
0/140 · 14
54
../../principles/reliability.rst:220 • ../../principles/reliability.rst:258
English
Transmitted frame
0/170 · 17
55
../../principles/reliability.rst:222
English
0001001001001001001000011
0/250 · 25
56
../../principles/reliability.rst:222
English
01111110000100100100100100100001101111110
0/410 · 41
57
../../principles/reliability.rst:223
English
0110111111111111111110010
0/250 · 25
58
../../principles/reliability.rst:223
English
01111110011011111011111011111011001001111110
0/440 · 44
59
../../principles/reliability.rst:224
English
01111110
0/100 · 8
60
../../principles/reliability.rst:224
English
0111111001111101001111110
0/250 · 25
61
../../principles/reliability.rst:228
English
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.
0/3740 · 374
62
../../principles/reliability.rst:231
English
`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.
0/4380 · 438
63
../../principles/reliability.rst:236
English
`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 :
0/7140 · 714
64
../../principles/reliability.rst:238
English
`A` : `1000011` b
0/170 · 17
65
../../principles/reliability.rst:239
English
`0` : `0110000` b
0/170 · 17
66
../../principles/reliability.rst:240
English
`z` : `1111010` b
0/170 · 17