Error Detection and Correction

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.

Data can be corrupted during transmission.

Some applications require that errors be detected and corrected.

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 O. 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 the 12 bits of
information.

Single-Bit Error
The term single-bit error means that only 1 bit of a given data unit
(such as a byte, character, or packet) is changed from 1 to 0 or from 0 to
1.

Figure10.1 Single-biterror

ochanged to I

Sent Received

Burst Error
The term burst error means that 2 or more bits in the data unit have
changed from 1 to 0

or from 0 to 1.
 A burst error means that2 or more bits in the data unit have changed.
Burst error oflength8

Length of burst error (8 bits)

The central concept in detecting or correcting errors is redundancy. To

be able to detect or correct errors, we need to send some extra bits with
our data. These redundant bits are added by the sender and removed by
the receiver. Their presence allows the receiver to detect or correct
corrupted bits.

To detect or correct errors, we need to send redundant(extra) bits with data.

Error Detection
Errors in the received frames are detected by means of Parity Check and Cyclic Redundancy
Check (CRC). In both cases, few extra bits are sent along with actual data to confirm that bits
received at other end are same as they were sent. If the counter-check at receiver’ end fails,
the bits are considered corrupted.

Parity Check
One extra bit is sent along with the original bits to make number of 1s either even in case of
even parity, or odd in case of odd parity.

The sender while creating a frame counts the number of 1s in it. For example, if even parity is
used and number of 1s is even then one bit with value 0 is added. This way number of 1s
remains [Link] the number of 1s is odd, to make it even a bit with value 1 is added.
The receiver simply counts the number of 1s in a frame. If the count of 1s is even and even
parity is used, the frame is considered to be not-corrupted and is accepted. If the count of 1s
is odd and odd parity is used, the frame is still not corrupted.

If a single bit flips in transit, the receiver can detect it by counting the number of 1s. But
when more than one bits are erro neous, then it is very hard for the receiver to detect the
error.

Cyclic Redundancy Check (CRC)

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.

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 some data corruption occurred in transit.

Error Correction Techniques:

Hamming Code:

Parity bits: A bit that is added to the original binary data to make sure the total number of 1s
is even or odd (in case of even or odd parity respectively).
 ad
Even parity: To check for even parity, if the total number of 1s is even, the parity bit value is
0. If the total number of occurrences of 1s is odd, the parity bit value is 1.
Odd Parity: To test for odd parity, if the total number of 1s is even, the parity bit value is 1.
If the total number of 1s is odd, the parity bit value is 0.
To produce d+r, an information of ‘d’ bits is added to the redundant bits ‘r’.

Each (d+r) digit’s position is assigned a decimal value.

The ‘r’ bits are assigned to locations 1, 2,….2k-1.

The parity bits are recalculated at the receiving end. The position of an error is determined by
the decimal value of the parity bits.

Example: If the data to be transmitted is 1011001

Number of data bits = 7

Thus, number of redundancy bits = 4

Total bits = 7+4 = 11

Redundant bits are always placed at positions that correspond to the power of 2, so the
redundant bits will be placed at positions: 1,2,4 and 8.

Redundant bits will be placed here:

ad
Thus now, all the 11 bits will look like this:

Here, R1, R2, R4 and R8 are the redundant bits.

Determining the parity bits:

R1:

We look at bits 1,3,5,7,9,11 to calculate R1. In this case, because the number of 1s in these
bits together is even, we make the R1 bit equal to 0 to maintain even parity.

R2:

ad
We look at bits 2,3,6,7,10,11 to calculate R2. In this case, because the number of 1s in these
bits together is odd, we make the R2 bit equal to 1 to maintain even parity.

R4:

We look at bits 4,5,6,7 to calculate R4. In this case, because the number of 1s in these bits
together is odd, we make the R4 bit equal to 1 to maintain even parity.

R8:

We look at bits 8,9,10,11 to calculate R8. In this case, because the number of 1s in these bits
together is even, we make the R8 bit equal to 0 to maintain even parity.

Thus, the final block of data which is transferred looks like this:
Channel Allocation
When there are more than one user who desire to access a shared network
channel, an algorithm is deployed for channel allocation among the
competing users. The network channel may be a single cable or optical fiber
connecting multiple nodes, or a portion of the wireless spectrum. Channel
allocation algorithms allocate the wired channels and bandwidths to the
users, who may be base stations, access points or terminal equipment.
Channel allocation problem can be solved by two schemes: Static Channel
Allocation in LANs and MANs, and Dynamic Channel Allocation.

These are explained as following below.

Static channel allocation

Frequency Division Multiplexing

In FDM, the total bandwidth is divided to a set of frequency bands that do not overlap. Each
of these bands is a carrier of a different signal that is generated and modulated by one of the
sending devices. The frequency bands are separated from one another by strips of unused
frequencies called the guard bands, to prevent overlapping of signals.

The modulated signals are combined together using a multiplexer (MUX) in the sending end.
The combined signal is transmitted over the communication channel, thus allowing multiple
independent data streams to be transmitted simultaneously. At the receiving end, the
individual signals are extracted from the combined signal by the process of demultiplexing
(DEMUX).

Example
The following diagram conceptually represents multiplexing using FDM. It has 4 frequency
bands, each of which can carry signal from 1 sender to 1 receiver. Each of the 4 senders is
allocated a frequency band. The four frequency bands are multiplexed and sent via the
communication channel. At the receiving end, a demultiplexer regenerates the original four
signals as outputs.
Time Division Multiplexing
In TDM, the data flow of each input stream is divided into units. One unit may be 1 bit, 1
byte, or a block of few bytes. Each input unit is allotted an input time slot. One input unit
corresponds to one output unit and is allotted an output time slot. During transmission, one
unit of each of the input streams is allotted one-time slot, periodically, in a sequence, on a
rotational basis. This system is popularly called round-robin system.

Example
Consider a system having four input streams, A, B, C and D. Each of the data streams is
divided into units which are allocated time slots in the round – robin manner. Hence, the time
slot 1 is allotted to A, slot 2 is allotted to B, slot 3 is allotted to C, slot 4 is allotted to D, slot 5
is allocated to A again, and this goes on till the data in all the streams are transmitted.
4.1.2 Dynamic channel allocation

Several assumptions are used in dynamic channel allocation.

Station model. There are N independent stations, each with a program or user that generates
frames for transmission.

Single channel. A single channel is available, all stations can transmit on it and receive from
it. As far as the hardware is concerned all stations are equal, although protocol software may
assign priorities to them.

Collision. If two frames are transmitted simultaneously, the resulting signal is garbled. All
stations can detect collisions.

Time. With continuous time, frame transmission can begin at any instant. With slotted time,
time is divided into discrete intervals called slots, frame transmission always begin at the start
of a slot. A slot may contain 0 (idle), 1 (successful transmission) or more (a collision) frames.

Carrier sense. Stations can either tell if the channel is in use or not. If they can, they do not
send when the carrier is in use. If they can not, they just go ahead and send. LAN's usually
have carrier sense possibilities.

4.2.1 ALOHA

ALOHA, devised in the 1970's, used ground based radio broadcasting, its MAC protocol
provided basic idea's applicable to many broadcast systems.

In pure ALOHA users transmitted whenever they had data to send. There will be of course
collisions and the colliding frames are corrupted. However, due to the feedback property of
broadcasting, a sender can always find out whether or not its frame was destroyed by
listening to the channel, the same way other users do. If the frame was destroyed, the sender
just waits a random amount of time and sends again. The waiting time must be random or the
same frames will collide over and over, in lockstep.
The maximum throughput S per frame time, occurs at G=0.5, giving S = 1/2e = 0.184, thus a
channel utilization of only 18%.

In slotted ALOHA, stations only transmit at the beginning of a slot, which has the length of a
frame time. Thus if a station has something to send, it waits until the beginning of the next
slot. A possibility to determine the beginning of slots, would be to have one special station
which emits a short signal.

The vulnerable period is now reduced to 1 frame time, thus S=Ge-G. The maximum
throughput S is now 37%.

Carrier Sense Multiple Access Protocols

Persistent and Nonpersistent CSMA

In 1-persistent CSMA, if a station has data to send, it first listen to the channel to see if
someone else is transmitting at that moment. If not, it starts transmitting, else it keeps
listening until the channel becomes free. If a collision occurs, the station waits a random
amount of time and than starts listening to the channel again. This protocol is called 1-
persistent because a station transmits with probability 1 whenever it finds the channel idle.

In non-persistent CSMA the stations are not so greedy. If a station detects that the channel is
occupied, it waits a random amount of time before it looks again to the channel. Intuitively
this will lead to a better channel utilization, but also to longer wait times for a station
(specially when the load is low), than 1-persistent CSMA.

With slotted channels also p-persistent CSMA can be used.

1. When a station is ready to send, it senses the channel. If it is idle, it transmits with a
probability of p.
2. With a probability q=1-p it defers to the next slot. If that slot is idle, it either transmit
or defers again with probabilities p and q.
 3. This is repeated until either the frame has been send or another station has begun
transmitting. In the latter case it acts as there has been a collision, it waits a random
time and starts again. If the station initially senses the channel busy, it waits until the
next slot and applies the above algorithm.

Here stations abort their transmissions as soon as they detect a collision. After a transmission
is finished at point t0, any other station having something to send may now attempt to do so.
If two or more stations decide to do so, a collision occurs.
CSMA with Collision Detection (CSMA/CD)
Carrier Sense Multiple Access with Collision Detection (CSMA/CD) is a network protocol
for carrier transmission that operates in the Medium Access Control (MAC) layer. It senses
or listens whether the shared channel for transmission is busy or not, and defers transmissions
until the channel is free. The collision detection technology detects collisions by sensing
transmissions from other stations. On detection of a collision, the station stops transmitting,
sends a jam signal, and then waits for a random time interval before retransmission.

Algorithms
The algorithm of CSMA/CD is:

 When a frame is ready, the transmitting station checks whether the channel is idle or
busy.
 If the channel is busy, the station waits until the channel becomes idle.
 If the channel is idle, the station starts transmitting and continually monitors the
channel to detect collision.
 If a collision is detected, the station starts the collision resolution algorithm.
 The station resets the retransmission counters and completes frame transmission.

The algorithm of Collision Resolution is:

 The station continues transmission of the current frame for a specified time along with
a jam signal, to ensure that all the other stations detect collision.
 The station increments the retransmission counter.
 If the maximum number of retransmission attempts is reached, then the station aborts
transmission.
 Otherwise, the station waits for a backoff period which is generally a function of the
number of collisions and restart main algorithm.

Flow Control
Stop and Wait ARQ
 Characteristics

 Used in Connection-oriented communication.

 It offers error and flow control
 It is used in Data Link and Transport Layers
 Stop and Wait ARQ mainly implements Sliding Window Protocol
concept with Window Size 1
simple Stop and Wait
Sender:
Rule 1) Send one data packet at a time.
Rule 2) Send next packet only after receiving acknowledgement for previous.
Receiver:
Rule 1) Send acknowledgement after receiving and consuming of data
packet.
Rule 2) After consuming packet acknowledgement need to be sent (Flow
Control)
Stop and Wait ARQ (Automatic Repeat Request)
Above 3 problems are resolved by Stop and Wait ARQ (Automatic Repeat
Request) that does both error control and flow control.

1. Problem of Lost Data Packet-

 Time out timer helps to solve the problem of lost data packet.
 After sending a data packet to the receiver, sender starts the time out timer.
 If the data packet gets acknowledged before the timer expires, sender stops the
time out timer.
 If the timer goes off before receiving the acknowledgement, sender retransmits
the same data packet.
 After retransmission, sender resets the timer.
 This prevents the occurrence of deadlock.
Lost Acknowledgement-

 Sequence number on data packets help to solve the problem of delayed

acknowledgement.
 Consider the acknowledgement sent by the receiver gets lost.
 Then, sender retransmits the same data packet after its timer goes off.
 This prevents the occurrence of deadlock.
 The sequence number on the data packet helps the receiver to identify the
duplicate data packet.
 Receiver discards the duplicate packet and re-sends the same
acknowledgement.
Delayed Acknowledgement-

 Sequence number on acknowledgements help to solve the problem of delayed

acknowledgement.
Damaged Packet-

 If receiver receives a corrupted data packet from the sender, it sends a negative
acknowledgement (NAK) to the sender.
 NAK requests the sender to send the data packet again.
Go-Back-N ARQ Protocol
To improve the efficiency of transmission (filling the pipe), multiple frames
must be in transition while waiting for acknowledgment. In Go-Back-N
Automatic Repeat Request, we can send several frames before receiving
acknowledgments; we keep a copy of these frames until the
acknowledgments arrive.

Sequence Numbers

Frames from a sending station are numbered sequentially. If the header of

the frame allows m bits for the sequence number, the sequence numbers
range from 0 to 2m- 1. For example, if m is 4, the only sequence numbers
are 0 through 15 inclusive. However, we can repeat the sequence. So the
sequence numbers are
0, 1,2,3,4,5,6, 7,8,9, 10, 11, 12, 13, 14, 15,0, 1,2,3,4,5,6,7,8,9,10, 11, ...

In other words, the sequence numbers are modulo-2 m.

Sliding Window
In this protocol (and the next), the sliding window is an abstract concept
that defines the range of sequence numbers that is the concern of the
sender and receiver. In other words, the sender and receiver need to deal
with only part of the possible sequence numbers. The range which is the
concern of the sender is called the send sliding window; the range that is
the concern of the receiver is called the receiver sliding window.
The send window is an imaginary box covering the sequence numbers of
the data frames which can be in transit. In each window position, some of
these sequence numbers define the frames that have been sent; others
define those that can be sent. The maximum size of the window is 2 m – 1.
The size can be fixed and set to the maximum value. The following figure
shows a sliding window of size 15 (m =4).

The receive window makes sure that the correct data frames are received
and that the correct acknowledgments are sent. The size of the receive
window is always I. The receiver is always looking for the arrival of a
specific frame. Any frame arriving out of order is discarded and needs to
be resent. The following figure shows the receive window.

Window size for Go-Back-N ARQ

  We choose m = 2, which means the size of the window can be 2 m - 1, or 3. We can now
show why the size of the send window must be less than 2m.

 If the size of the window is 3 (less than 2 2) and all three acknowledgments are lost, the
frame 0 timer expires and all three frames are resent.

 The receiver is now expecting frame 3, not frame 0, so the duplicate frame is correctly
discarded. On the other hand, if the size of the window is 4 (equal to 2 2) and all
acknowledgments are lost, the sender will send a duplicate of frame O.

 However, this time the window of the receiver expects to receive frame 0, so it accepts
frame 0, not as a duplicate, but as the first frame in the next cycle. This is an error.

Cumulative Acknowledgments for Go-Back-N ARQ

 This is an example of a case where the forward channel is reliable, but the reverse is
not. No data frames are lost, but some ACKs are delayed and one is lost.

 After initialization, there are seven sending events. There is no time-out event here
because all outstanding frames are acknowledged before the timer expires. Note
that although ACK 2 is lost, ACK 3 serves as both ACK 2 and ACK3.

 We can say that the Stop-and-Wait ARQ Protocol is actually a Go-Back-N ARQ in which
there are only two sequence numbers and the send window size is 1.

 In other words, m = 1, 2m - 1 = 1. In Go-Back-N ARQ, we said that the addition is modulo-

2m; in Stop-and-Wait ARQ it is 2, which is the same as 2m when m = 1.

 Stop-and-Wait ARQ is a special case of Go-Back-N ARQ in which the size of the
send window is 1.
Selective Repeat Automatic Repeat Request

 Go-Back-N ARQ simplifies the process at the receiver site. The receiver keeps track of
only one variable, and there is no need to buffer out-of-order frames; they are simply
discarded. However, this protocol is very inefficient for a noisy link. In a noisy link a
frame has a higher probability of damage, which means the resending of multiple
frames.

 This resending uses up the bandwidth and slows down the transmission. For noisy links,
there is another mechanism that does not resend N frames when just one frame is
damaged; only the damaged frame is resent.

 This mechanism is called Selective Repeat ARQ. It is more efficient for noisy links, but
the processing at the receiver is more complex.

Selective Repeat Protocol : Send window and receive window

 First, the size of the send window is much smaller; it is 2 m-1. Second, the receive window
is the same size as the send window.

 For example, if m = 4, the sequence numbers go from 0 to 15, but the size of the
window is just 8 (it is 15 in the Go-Back-N Protocol).

 The smaller window size means less efficiency in filling the pipe, but the fact that there
are fewer duplicate frames can compensate for this. The protocol uses the same
variables as we discussed for Go-Back-N.
  The receive window in Selective Repeat is totally different from the one in GoBack-N.
First, the size of the receive window is the same as the size of the send window 2 m-1.

 The Selective Repeat Protocol allows as many frames as the size of the receive window
to arrive out of order and be kept until there is a set of in-order frames to be delivered to
the network layer.

 Because the sizes of the send window and receive window are the same, all the frames
in the send frame can arrive out of order and be stored until they can be delivered .
We need, however, to mention that the receiver never delivers packets out of order to the
network layer.

Selective Repeat Protocol: Working

 Here, each frame sent or resent needs a timer, which means that the timers need to be
numbered (0, 1, 2, and 3).

 The timer for frame 0 starts at the first request, but stops when the ACK for this frame
arrives. The timer for frame 1 starts at the second request, restarts when a NAK arrives,
and finally stops when the last ACK arrives.

 At the second arrival, frame 2 arrives and is stored and marked (colored slot), but it
cannot be delivered because frame 1 is missing. At the next arrival, frame 3 arrives and
is marked and stored, but still none of the frames can be delivered because frame 1 is
still missing.

 Only at the last arrival, when finally a copy of frame 1 arrives, can frames 1, 2, and 3 be
delivered to the network layer. There are two conditions for the delivery of frames to the
network layer: First, a set of consecutive frames must have arrived. Second, the set
starts from the beginning of the window.
 Another important point is that a NAK is sent after the second arrival, but not after the
third, although both situations look the same. The reason is that the protocol does not
want to crowd the network with unnecessary NAKs and unnecessary resent frames.

 The second NAK would still be NAKI to inform the sender to resend frame 1 again; this
has already been done. The first NAK sent is remembered (using the nakSent variable)
and is not sent again until the frame slides. A NAK is sent once for each window
position and defines the first slot in the window.

 The next point is about the ACKs. Notice that only two ACKs are sent here. The first one
acknowledges only the first frame; the second one acknowledges three frames. In
Selective Repeat, ACKs are sent when data are delivered to the network layer. If the
data belonging to n frames are delivered in one shot, only one ACK is sent for an of
them.