MODULE 2: DATA LINK LAYER AND MEDIUM ACCESS SUB LAYER Error
Detection and Error Correction - Fundamentals, Block coding, Hamming Distance, CRC; Flow Control and
Error control protocols - Stop and Wait, Go back – N ARQ, Selective Repeat ARQ, Sliding Window
MODULE 2: DATA LINK LAYER AND MEDIUM ACCESS SUB LAYER
1.1Error Detection and Error Correction
Networks must be able to transfer data from one device to another with acceptable accuracy.
For most applications, a system must guarantee that the data received are identical to the
data transmitted. Any time data are transmitted from one node to the next, they can become
corrupted in passage. Many factors can alter one or more bits of a message. Some
applications require a mechanism for detecting and correcting errors.
Note: Data can be corrupted during transmission. Some applications require that errors be
detected and corrected.
Some applications can tolerate a small level of error. For example, random errors in audio or
video transmissions may be tolerable, but when we transfer text, we expect a very high level
of accuracy.
1.1.1Fundamentals
Types of Errors
Whenever bits flow from one point to another, they are subject to unpredictable changes
because of interference. This interference can change the shape of the signal. In a single-bit
error, a 0 is changed to a 1 or a 1 to a 0. In a burst error, multiple bits are changed. For
example, a 11100 s burst of impulse noise on a transmission with a data rate of 1200 bps
might change all or some of the12 bits of information.
Fig 2.1: Types of error
1.1.2Block coding
In block coding, we divide our message into blocks, each of k bits, called datawords. We add
r redundant bits to each block to make the length n = k + r. The resulting n-bit blocks are
called codewords. How the extra r bits is chosen or calculated is something we will discuss
later. For the moment, it is important to know that we have a set of datawords, each of size k,
and a set of codewords, each of size of n. With k bits, we can create a combination of 2k
datawords; with n bits, we can create a combination of 2n codewords. Since n > k, the
number of possible codewords is larger than the number of possible datawords. The block
coding process is one-to-one; the same dataword is always encoded as the same codeword.
This means that we have 2n - 2k codewords that are not used.
Fig 2.2: Datawords and codewords in block coding
Error Detection
How can errors be detected by using block coding? If the following two conditions are met,
the receiver can detect a change in the original codeword.
1.The receiver has (or can find) a list of valid codewords.
2.The original codeword has changed to an invalid one.
Fig 2.3 Process oferror detection in block coding
The sender creates codewords out of datawords by using a generator that applies the rules
and procedures of encoding (discussed later). Each codeword sent to the receiver may change
during transmission. If the received codeword is the same as one of the valid codewords, the
word is accepted; the corresponding dataword is extracted for use. If the received codeword
is not valid, it is discarded. However, if the codeword is corrupted during transmission but the
received word still matches a valid codeword, the error remains undetected. This type of
coding can detect only single errors. Two or more errors may remain undetected.
Error Correction
As we said before, error correction is much more difficult than error detection. In error
detection, the receiver needs to know only that the received codeword is invalid; in error
correction the receiver needs to find (or guess) the original codeword sent. We can say that
we need more redundant bits for error correction than for error detection. Figure 2.4 shows
the role of block coding in error correction. We can see that the idea is the same as error
detection but the checker functions are much more complex.
Fig 2.4 Structure of encoder and decoder in error correction
1.1.3Hamming Distance
One of the central concepts in coding for error control is the idea of the Hamming distance.
The Hamming distance between two words (of the same size) is the number of differences
between the corresponding bits. We show the Hamming distance between two words x and y
as d(x, y).
The Hamming distance can easily be found if wc apply the XOR operation on the two words
and count the number of Is in the result. Note that the Hamming distance is a value greater
than zero.
Note: The Hamming distance between two words is the number of differences between
corresponding bits.
Example 10.4
Let us find the Hamming distance between two pairs of words.
1.The Hamming distance d(OOO, 011) is 2 because 000 (XOR) 011 is 011 (two Is).
2. The Hamming distance d(10101, 11110) is 3 because 10101 (XOR) 11110 is 01011
(three Is).
Minimum Hamming Distance
Although the concept of the Hamming distance is the central point in dealing with error
detection and correction codes, the measurement that is used for designing a code is the
minimum Hamming distance. In a set of words, the minimum Hamming distance is the
smallest Hamming distance between all possible pairs. We use dmin to define the minimum
Hamming distance in a coding scheme. To find this value, we find the Hamming distances
between all words and select the smallest one.
Note: The minimum Hamming distance is the smallest Hamming distance between all
possible pairs in a set of words.
1.1.4CRC
Linear block code is a code in which the exclusive OR (addition modulo-2) of two valid
codewords creates another valid codeword.
Cyclic codes are special linear block codes with one extra property. In a cyclic code, if a
codeword is cyclically shifted (rotated), the result is another codeword. For example, if
1011000 is a codeword and we cyclically left-shift, then 0110001 is also a codeword. In this
case, if we call the bits in the first word ao to a6' and the bits in the second word b0 to b6, we
can shift the bits by using the following:
In the rightmost equation, the last bit of the first word is wrapped around and becomes the
first bit of the second word.
The cyclic redundancy check (CRC) is used in networks such as LANs and WANs.
Table 2.1 A CRC code with C(7, 4)
Fig 2.5 CRC encoder and decoder
In the encoder, the dataword has k bits (4 here); the codeword has n bits (7 here).
The size of the dataword is augmented by adding n - k (3 here) Os to the right-hand side of
the word. The n-bit result is fed into the generator. The generator uses a divisor of size n - k +
I (4 here), predefined and agreed upon. The generator divides the augmented dataword by the
divisor (modulo-2 division). The quotient ofthe division is discarded; the remainder (r2rl ro)
is appended to the dataword to create the codeword.
The decoder receives the possibly corrupted codeword. A copy of all n bits is fed to the
checker which is a replica of the generator. The remainder produced by the checker is a
syndrome of n - k (3 here) bits, which is fed to the decision logic analyzer. The analyzer as a
simple function. If the syndrome bits are all as, the 4 leftmost bits of the codeword are
accepted as the dataword (interpreted as no error); otherwise, the 4 bits are discarded (error).
Decoder
The codeword can change during transmission. The decoder does the same division
process as the encoder. The remainder of the division is the syndrome. If the syndrome
is all Os, there is no error; the dataword is separated from the received codeword and
accepted. Otherwise, everything is discarded. Figure 2.6 shows two cases: The
lefthand figure shows the value of syndrome when no error has occurred; the
syndrome is
000. The right-hand part of the figure shows the case in which there is one single error.
The syndrome is not all Os (it is OIl).
Also we can say that
CRC is a different approach to detect if the received frame contains valid data. This
technique involves binary division of the data bits being sent. The divisor is generated using
polynomials. The sender performs a division operation on the bits being sent and calculates
the remainder. Before sending the actual bits, the sender adds the remainder at the end of the
actual bits. Actual data bits plus the remainder is called a codeword. The sender transmits
data bits as codewords.
Fig 2.6 CRC
At the other end, the receiver performs division operation on codewords using the same CRC
divisor. If the remainder contains all zeros the data bits are accepted, otherwise it is
considered as there is some data corruption occurred in transit.
1.2Flow Control and Error control protocols –
Flow Control: When a data frame (Layer-2 data) is sent from one host to another over a
single medium, it is required that the sender and receiver should work at the same speed.
That is, sender sends at a speed on which the receiver can process and accept the data. What
if the speed (hardware/software) of the sender or receiver differs? If sender is sending too
fast the receiver may be overloaded, (swamped) and data may be lost.
Note: Flow control refers to a set of procedures used to restrict the amount of data
that the sender can send before waiting for acknowledgment.
Error Control
Error control is both error detection and error correction. It allows the receiver to
inform the sender of any frames lost or damaged in transmission and coordinates the
retransmission of those frames by the sender. In the data link layer, the term error control
refers primarily to methods of error detection and retransmission. Error control in
the data link layer is often implemented simply: Any time an error is detected in an
exchange, specified frames are retransmitted. This process is called automatic
repeat request (ARQ).
Note: Error control in the data link layer is based on automatic repeat request, which is the
retransmission of data.
Two types of mechanisms can be deployed to control the flow:
1.2.1Stop and Wait
This flow control mechanism forces the sender after transmitting a data frame to stop and
wait until the acknowledgement of the data-frame sent is received.
In this flow control mechanism, both sender and receiver agree on the number of data-frames
after which the acknowledgement should be sent. As we learnt, stop and wait flow control
mechanism wastes resources, this protocol tries to make use of underlying resources as much
as possible.
Requirements for error control mechanism:
Error detection: The sender and receiver, either both or any, must ascertain that there is some
error in the transit.
Positive ACK: When the receiver receives a correct frame, it should acknowledge it.
Negative ACK: When the receiver receives a damaged frame or a duplicate frame, it sends a
NACK back to the sender and the sender must retransmit the correct frame.
Retransmission: The sender maintains a clock and sets a timeout period. If an
acknowledgement of a data-frame previously transmitted does not arrive before the timeout,
the sender retransmits the frame, thinking that the frame or its acknowledgement is lost in
transit.
There are three types of techniques available which Data-link layer may deploy to
control the errors by Automatic Repeat Requests (ARQ):
Stop and Wait ARQ’s (Error Control)
The following transition may occur in Stop-and-Wait ARQ:
●The sender maintains a timeout counter.
●When a frame is sent, the sender starts the timeout counter.
●If acknowledgement of frame comes in time, the sender transmits the next frame in queue.
● If acknowledgement does not come in time, the sender assumes that either the frame
or its acknowledgement is lost in transit. Sender retransmits the frame and starts the timeout
counter.
●If a negative acknowledgement is received, the sender retransmits the frame.
1.2.2Go back – N ARQ
Stop and wait ARQ mechanism does not utilize the resources at their best. When the
acknowledgement is received, the sender sits idle and does nothing. In Go-Back-N ARQ
method, both sender and receiver maintain a window.
The sending-window size enables the sender to send multiple frames without receiving the
acknowledgement of the previous ones. The receiving-window enables the receiver to
receive multiple frames and acknowledge them. The receiver keeps track of incoming
frame’s sequence number. When the sender sends all the frames in window, it checks up to
what sequence number it has received positive acknowledgement. If all frames are positively
acknowledged, the sender sends next set of frames. If sender finds that it has received NACK
or has not receive any ACK for a particular frame, it retransmits all the frames after which it
does not receive any positive ACK.
1.2.3Selective Repeat ARQ
In Go-back-N ARQ, it is assumed that the receiver does not have any buffer space for its
window size and has to process each frame as it comes. This enforces the sender to retransmit
all the frames which are not acknowledged.
In Selective-Repeat ARQ, the receiver while keeping track of sequence numbers, buffers the
frames in memory and sends NACK for only frame which is missing or damaged. The
sender in this case, sends only packet for which NACK is received.
1.2.4Sliding Window
In this flow control mechanism, both sender and receiver agree on the number of data-frames
after which the acknowledgement should be sent. As we learnt, stop and wait flow control
mechanism wastes resources, this protocol tries to make use of underlying resources as much
as possible.
A sliding window algorithm places a buffer between the application program and the
network data flow. For TCP, the buffer is typically in the operating system kernel, but this is
more of an implementation detail than a hard-and-fast requirement.
Data received from the network is stored in the buffer, from where the application can read at
its own pace. As the application reads data, buffer space is freed up to accept more input
from the network. The window is the amount of data that can be "read ahead" - the size of the
buffer, less the amount of valid data stored in it. Window announcements are used to inform
the remote host of the current window size.
Sender sliding Window: At any instant, the sender is permitted to send frames with sequence
numbers in a certain range (the sending window)
Receiver sliding Window: The receiver always maintains a window of size 1 as shown
in Fig. 3.3.4. It looks for a specific frame (frame 4 as shown in the figure) to arrive in
a specific order. If it receives any other frame (out of order), it is discarded and it
needs to be resent.
However, the receiver window also slides by one as the specific frame is received and
accepted as shown in the figure. The receiver acknowledges a frame by sending an
ACK frame that includes the sequence number of the next frame expected. This also
explicitly announces that it is prepared to receive the next N frames, beginning with
the number specified. This scheme can be used to acknowledge multiple frames. It
could receive frames 2, 3, 4 but withhold ACK until frame 4 has arrived. By returning
an ACK with sequence number 5, it acknowledges frames 2, 3, 4 at one time. The
receiver needs a buffer of size 1.
On the other hand, if the local application can process data at the rate it's being
transferred; sliding window still gives us an advantage. If the window size is larger
than the packet size, then multiple packets can be outstanding in the network, since the
sender knows that buffer space is available on the receiver to hold all of them. Ideally,
a steadystate condition can be reached where a series of packets (in the forward
direction) and window announcements (in the reverse direction) are constantly in
transit. As each new window announcement is received by the sender, more data
packets are transmitted. As the application reads data from the buffer (remember, we're
assuming the application can keep up with the network), more window announcements
are generated. Keeping a series of data packets in transit ensures the efficient use of
network resources.