Communication Networks/Error Control, Flow Control, MAC

Introduction

Data Link Layer is layer 2 in OSI model. It is responsible for communications between adjacent network nodes. It handles the data moving in and out across the physical layer. It also provides a well defined service to the network layer. Data link layer is divided into two sub layers. The Media Access Control (MAC) and Logical Link Control (LLC).

Data-Link layer ensures that an initial connection has been set up, divides output data into data frames, and handles the acknowledgements from a receiver that the data arrived successfully. It also ensures that incoming data has been received successfully by analyzing bit patterns at special places in the frames.

In the following sections data link layer's functions- Error control and Flow control has been discussed. After that MAC layer is explained. Multiple access protocols are explained in the MAC layer section.

Error Control

Network is responsible for transmission of data from one device to another device. The end to end transfer of data from a transmitting application to a receiving application involves many steps, each subject to error. With the error control process, we can be confident that the transmitted and received data are identical. Data can be corrupted during transmission. For reliable communication, error must be detected and corrected.

Error control is the process of detecting and correcting both the bit level and packet level errors.

Types of Errors

Single Bit Error

The term single bit error means that only one bit of the data unit was changed from 1 to 0 and 0 to 1.

Burst Error

In term burst error means that two or more bits in the data unit were changed. Burst error is also called packet level error, where errors like packet loss, duplication, reordering.

Error Detection

Error detection is the process of detecting the error during the transmission between the sender and the receiver.

Types of error detection

• Parity checking
• Cyclic Redundancy Check (CRC)
• Checksum

Redundancy

Redundancy allows a receiver to check whether received data was corrupted during transmission. So that he can request a retransmission. Redundancy is the concept of using extra bits for use in error detection. As shown in the figure sender adds redundant bits (R) to the data unit and sends to receiver, when receiver gets bits stream and passes through checking function. If no error then data portion of the data unit is accepted and redundant bits are discarded. otherwise asks for the retransmission.

Parity checking

Parity adds a single bit that indicates whether the number of 1 bits in the preceding data is even or odd. If a single bit is changed in transmission, the message will change parity and the error can be detected at this point. Parity checking is not very robust, since if the number of bits changed is even, the check bit will be invalid and the error will not be detected.

1. Single bit parity
2. Two dimension parity

Moreover, parity does not indicate which bit contained the error, even when it can detect it. The data must be discarded entirely, and re-transmitted from scratch. On a noisy transmission medium a successful transmission could take a long time, or even never occur. Parity does have the advantage, however, that it's about the best possible code that uses only a single bit of space.

Cyclic Redundancy Check

CRC is a very efficient redundancy checking technique. It is based on binary division of the data unit, the remainder of which (CRC) is added to the data unit and sent to the receiver. The Receiver divides data unit by the same divisor. If the remainder is zero then data unit is accepted and passed up the protocol stack, otherwise it is considered as having been corrupted in transit, and the packet is dropped.

Sequential steps in CRC are as follows.

Sender follows following steps.

• Data unit is composite by number of 0s, which is one less than the divisor.
• Then it is divided by the predefined divisor using binary division technique. The remainder is called CRC. CRC is appended to the data unit and is sent to the receiver.

Receiver follows following steps.

• When data unit arrives followed by the CRC it is divided by the same divisor which was used to find the CRC (remainder).
• If the remainder result in this division process is zero then it is error free data, otherwise it is corrupted.

Diagram shows how to CRC process works.

[a] sender CRC generator [b] receiver CRC checker

Checksum

Check sum is the third method for error detection mechanism. Checksum is used in the upper layers, while Parity checking and CRC is used in the physical layer. Checksum is also on the concept of redundancy.

In the checksum mechanism two operations to perform.

Checksum generator

Sender uses checksum generator mechanism. First data unit is divided into equal segments of n bits. Then all segments are added together using 1’s complement. Then it is complemented ones again. It becomes Checksum and sends along with data unit.

Exp:

If 16 bits 10001010 00100011 is to be sent to receiver.

So the checksum is added to the data unit and sends to the receiver. Final data unit is 10001010 00100011 01010000.

Checksum checker

Receiver receives the data unit and divides into segments of equal size of segments. All segments are added using 1’s complement. The result is complemented once again. If the result is zero, data will be accepted, otherwise rejected.

Exp:

The final data is nonzero then it is rejected.

Error Correction

This type of error control allows a receiver to reconstruct the original information when it has been corrupted during transmission.

Hamming Code

It is a single bit error correction method using redundant bits.

In this method redundant bits are included with the original data. Now, the bits are arranged such that different incorrect bits produce different error results and the corrupt bit can be identified. Once the bit is identified, the receiver can reverse its value and correct the error. Hamming code can be applied to any length of data unit and uses the relationships between the data and the redundancy bits.

Algorithm:

1. Parity bits are positions at the power of two (2 r).
2. Rest of the positions is filled by original data.
3. Each parity bit will take care of its bits in the code.
4. Final code will sends to the receiver.

In the above example we calculates the even parities for the various bit combinations. the value for the each combination is the value for the corresponding r(redundancy)bit. r1 will take care of bit 1,3,5,7,9,11. and it is set based on the sum of even parity bit. the same method for rest of the parity bits.

If the error occurred at bit 7 which is changed from 1 to 0, then receiver recalculates the same sets of bits used by the sender. By this we can identify the perfect location of error occurrence. once the bit is identified the receiver can reverse its value and correct the error.

Flow Control

Flow Control is one important design issue for the Data Link Layer that controls the flow of data between sender and receiver.

In Communication, there is communication medium between sender and receiver. When Sender sends data to receiver then there can be problem in below case :

1) Sender sends data at higher rate and receive is too sluggish to support that data rate.

To solve the above problem, FLOW CONTROL is introduced in Data Link Layer. It also works on several higher layers. The main concept of Flow Control is to introduce EFFICIENCY in Computer Networks.

Approaches of Flow Control

1. Feed back based Flow Control
2. Rate based Flow Control

Feed back based Flow Control is used in Data Link Layer and Rate based Flow Control is used in Network Layer.

Feed back based Flow Control

In Feed back based Flow Control, Until sender receives feedback from the receiver, it will not send next data.

Types of Feedback based Flow Control

A. Stop-and-Wait Protocol

B. Sliding Window Protocol

1. A One-Bit Sliding Window Protocol
2. A Protocol Using Go Back N
3. A Protocol Using Selective Repeat

A. A Simplex Stop-and-Wait Protocol

In this Protocol we have taken the following assumptions:

1. It provides unidirectional flow of data from sender to receiver.
2. The Communication channel is assumed to be error free.

In this Protocol the Sender simply sends data and waits for the acknowledgment from Receiver. That's why it is called Stop-and-Wait Protocol.

This type is not so much efficient, but it is simplest way of Flow Control.

In this scheme we take Communication Channel error free, but if the Channel has some errors then receiver is not able to get the correct data from sender so it will not possible for sender to send the next data (because it will not get acknowledge from receiver). So it will end the communication, to solve this problem there are two new concepts were introduced.

1. TIMER, if sender was not able to get acknowledgment in the particular time than, it sends the buffered data once again to receiver. When sender starts to send the data, it starts timer.
2. SEQUENCE NUMBER, from this the sender sends the data with the specific sequence number so after receiving the data, receiver sends the data with that sequence number, and here at sender side it also expect the acknowledgment of the same sequence number.

This type of scheme is called Positive Acknowledgment with Retransmission (PAR).

B. Sliding Window Protocol

Problems Stop –wait protocol In the last protocols sender must wait for either positive acknowledgment from receiver or for time out to send the next frame to receiver. So if the sender is ready to send the new data, it can not send. Sender is dependent on the receiver. Previous protocols have only the flow of one sided, means only sender sends the data and receiver just acknowledge it, so the twice bandwidth is used.

To solve the above problems the Sliding Window Protocol was introduce.

In this, the sender and receiver both use buffer, it’s of same size, so there is no necessary to wait for the sender to send the second data, it can send one after one without wait of the receiver’s acknowledgment.

And it also solve the problem of uses of more bandwidth, because in this scheme both sender and receiver uses the channel to send the data and receiver just send the acknowledge with the data which it want to send to sender, so there is no special bandwidth is used for acknowledgment, so the bandwidth is saved, and this whole process is called PIGGYBACKING.

Types of Sliding Window Protocol

i. A One-Bit Sliding Window Protocol

ii. A Protocol Using Go Back N

iii. A Protocol Using Selective Repeat

i. A One-Bit Sliding Window Protocol

This protocol has buffer size of one bit, so only possibility for sender and receiver to send and receive packet is only 0 and 1. This protocol includes Sequence, Acknowledge, and Packet number.It uses full duplex channel so there is two possibilities:

1. Sender first start sending the data and receiver start sending data after it receive the data.
2. Receiver and sender both start sending packets simultaneously,

First case is simple and works perfectly, but there will be an error in the second one. That error can be like duplication of the packet, without any transmission error.

ii. A Protocol Using Go Back N

The problem with pipelining is if sender sending 10 packets, but the problem occurs in 8th one than it is needed to resend whole data. So the protocol called Go back N and Selective Repeat were introduced to solve this problem.In this protocol, there are two possibility at the receiver’s end, it may be with large window size or it may be with window size one.

The window size at the receiver end may be large or only of one. In the case of window size is one at the receiver, as we can see in the figure (a), if sender wants to send the packet from one to ten but suppose it has error in 2nd packet, so sender will start from zero, one, two, etc. here we assume that sender has the time out interval with 8. So the time out will occur after the 8 packets, up to that it will not wait for the acknowledgment. In this case at the receiver side the 2nd packet come with error, and other up to 8 were discarded by receiver. So in this case the loss of data is more.

Whether in the other case with the large window size at receiver end as we can see in the figure (b) if the 2nd packet comes with error than the receiver will accept the 3rd packet but it sends NAK of 2 to the sender and buffer the 3rd packet. Receiver do the same thing in 4th and 5th packet. When the sender receiver the NAK of 2nd packet it immediately send the 2nd packet to the receiver. After receiving the 2nd packet, receiver send the ACK of 5th one as saying that it received up to 5 packet. So there is no need to resend 3rd , 4th and 5th packet again, they are buffered in the receiver side.

iii. A Protocol Using Selective Repeat

Protocol using Go back N is good when the errors are rare, but if the line is poor, it wastes a lot of bandwidth on retransmitted frames. So to provide reliability, Selective repeat protocol was introduced. In this protocol sender starts it's window size with 0 and grows to some predefined maximum number. Receiver's window size is fixed and equal to the maximum number of sender's window size. The receiver has a buffer reserved for each sequence number within its fixed window.

Whenever a frame arrives, its sequence number is checked by the function to see if it falls within the window, if so and if it has not already been received, it is accepted and stored. This action is taken whether it is not expected by the network layer.

Here the buffer size of sender and receiver is 7 and as we can see in the figure (a), the sender sends 7 frames to the receiver and starts timer. When a receiver gets the frames, it sends the ACK back to the sender and it passes the frames to the Network Layer. After doing this, receiver empties its buffer and increased sequence number and expects sequence number 7,0,1,2,3,4,5. But if the ACK is lost, the sender will not receive the ACK. So when the timer expires, the sender retransmits the original frames, 0 to 6 to the receiver. In this case the receiver accepts the frames 0 to 5 (which are duplicated) and send it to the network layer. In this case protocol fails.

To solve the problem of duplication, the buffer size of sender and receiver should be (MAX SEQ + 1)/2 that is half of the frames to be send. As we can see in fig(c ), the sender sends the frames from 0 to 3 as it's window size is 4. Receiver accepts the frames and sends acknowledgment to the sender and passes the frames to the network layer and increases the expected sequence number from 4 to 7. If the ACK is lost than sender will send 0 to 3 to receiver again but receiver is expecting to 4 to 7, so it will not accept it. So this way the problem of duplication is solved.

MAC

The data link layer is divided into two sublayers: The Media Access Control (MAC) layer and the Logical Link Control (LLC) layer. The MAC sublayer controls how a computer on the network gains access to the data and permission to transmit it. The LLC layer controls frame synchronization, flow control and error checking.

Mac Layer is one of the sublayers that makeup the datalink layer of the OSI reference Model.

MAC layer is responsible for moving packets from one Network Interface card NIC to another across the shared channel

The MAC sublayer uses MAC protocols to ensure that signals sent from different stations across the same channel don't collide.

Different protocols are used for different shared networks, such as Ethernets, Token Rings, Token Buses, and WANs.

1. ALOHA

ALOHA is a simple communication scheme in which each source in a network sends its data whenever there is a frame to send without checking to see if any other station is active. After sending the frame each station waits for implicit or explicit acknowledgment. If the frame successfully reaches the destination, next frame is sent. And if the frame fails to be received at the destination it is sent again.

Pure ALOHA ALOHA is the simplest technique in multiple accesses. Basic idea of this mechanism is a user can transmit the data whenever they want. If data is successfully transmitted then there isn’t any problem. But if collision occurs than the station will transmit again. Sender can detect the collision if it doesn’t receive the acknowledgment from the receiver.

In ALOHA Collision probability is quite high. ALOHA is suitable for the network where there is a less traffic. Theoretically it is proved that maximum throughput for ALOHA is 18%.

                     P (success by given node) = P(node transmits) . P(no other node transmits in [t0-1,t0] . P(no other node transmits in [t0,t0 +1] 
                                               = p . (1-p)N-1 . (1-p)N-1

                 P (success by any of N nodes) = N . p . (1-p) N-1 . (1-p)N-1 
                                               … Choosing optimum p as N -->  infinity...
                                               = 1 / (2e) = .18 
                                               =18%

Slotted ALOHA

In ALOHA a newly emitted packet can collide with a packet in progress. If all packets are of the same length and take L time units to transmit, then it is easy to see that a packet collides with any other packet transmitted in a time window of length 2L. If this time window is decreased somehow, than number of collisions decreases and the throughput increase. This mechanism is used in slotted ALOHA or S-ALOHA. Time is divided into equal slots of Length L. When a station wants to send a packet it will wait till the beginning of the next time slot.

Advantages of slotted ALOHA:

• single active node can continuously transmit at full rate of channel
• highly decentralized: only slots in nodes need to be in sync
• simple

Disadvantages of slotted ALOHA:

• collisions, wasting slots
• idle slots
• clock synchronization

Efficiency of Slotted ALOHA:

• Suppose there are N nodes with many frames to send. The probability of sending frames of each node into the slot is p.
• Probability that node 1 has a success in getting the slot is p.(1-p)N-1
• Probability that every node has a success is N.p.(1-p)N-1
• For max efficiency with N nodes, find p* that maximizes Np(1-p)N-1
• For many nodes, take limit of Np*(1-p*)N-1 as N goes to infinity, gives 1/e = .37

The clear advantage of slotted ALOHA is higher throughput. But introduces complexity in the stations and bandwidth overhead because of the need for time synchronization.

2. Carrier Sense Multiple Access protocols (CSMA)

With slotted ALOHA, the best channel utilization that can be achieved is 1/e. Several protocols are developed for improving the performance.

Protocols that listen for a carrier and act accordingly are called carrier sense protocols. Carrier sensing allows the station to detect whether the medium is currently being used. Schemes that use a carrier sense circuits are classed together as carrier sense multiple access or CSMA schemes. There are two variants of CSMA. CSMA/CD and CSMA/CA

The simplest CSMA scheme is for a station to sense the medium, sending packets immediately if the medium is idle. If the station waits for the medium to become idle it is called persistent otherwise it is called non persistent.

a. Persistent

When a station has the data to send, it first listens the channel to check if anyone else is transmitting data or not. If it senses the channel idle, station starts transmitting the data. If it senses the channel busy it waits until the channel is idle. When a station detects a channel idle, it transmits its frame with probability P. That’s why this protocol is called p-persistent CSMA. This protocol applies to slotted channels. When a station finds the channel idle, if it transmits the fame with probability 1, that this protocol is known as 1 -persistent. 1 -persistent protocol is the most aggressive protocol.

b. Non-Persistent

Non persistent CSMA is less aggressive compared to P persistent protocol. In this protocol, before sending the data, the station senses the channel and if the channel is idle it starts transmitting the data. But if the channel is busy, the station does not continuously sense it but instead of that it waits for random amount of time and repeats the algorithm. Here the algorithm leads to better channel utilization but also results in longer delay compared to 1 –persistent.

CSMA/CD

Carrier Sense Multiple Access/Collision Detection a technique for multiple access protocols. If no transmission is taking place at the time, the particular station can transmit. If two stations attempt to transmit simultaneously, this causes a collision, which is detected by all participating stations. After a random time interval, the stations that collided attempt to transmit again. If another collision occurs, the time intervals from which the random waiting time is selected are increased step by step. This is known as exponential back off.

Exponential back off Algorithm

1. Adaptor gets datagram and creates frame
2. If adapter senses channel idle (9.6 microsecond), it starts to transmit frame. If it senses channel busy, waits until channel idle and then transmits
3. If adapter transmits entire frame without detecting another transmission, the adapter is done with frame!
4. If adapter detects another transmission while transmitting, aborts and sends jam signal
5. After aborting, adapter enters exponential backoff: after the mth collision, adapter chooses a K at random from {0,1,2,…,2m-1}. Adapter waits K*512 bit times (i.e. slot) and returns to Step 2
6. After 10th retry, random number stops at 1023. After 16th retry, system stops retry.

CSMA/CA

CSMA/CA is Carrier Sense Multiple Access/Collision Avoidance. In this multiple access protocol, station senses the medium before transmitting the frame. This protocol has been developed to improve the performance of CSMA. CASMA/CA is used in 802.11 based wireless LANs. In wireless LANs it is not possible to listen to the medium while transmitting. So collision detection is not possible.

In CSMA/CA, when the station detects collision, it waits for the random amount of time. Then before transmitting the packet, it listens to the medium. If station senses the medium idle, it starts transmitting the packet. If it detects the medium busy, it waits for the channel to become idle.

When A wants to transmit a packet to B, first it sends RTS (Request to Send) packet of 30 bytes to B with length L. If B is idle, it sends its response to A with CTS packet (Clear to Send). Here whoever listens to the CTS packet remains silent for duration of L. When A receives CTS, it sends data of L length to B.

There are several issues in this protocol

1. Hidden Station Problem
2. Exposed Station Problem

1. Hidden Station Problem (Figure a)

When a station sends the packet to another station/receiver, some other station which is not in sender’s range may start sending the packet to the same receiver. That will create collision of packets. This problem is explained more specifically below.

Suppose A is sending a packet to B. Now at the same time D also wants to send the packet to B. Here D does not hear A. So D will also send its packets to B. SO collision will occur.

2. Exposed Station Problem (Figure b)

When A is sending the packet, C will also hear. So if station wants to send the packet D, still it won’t send. This will reduce the efficiency of the protocol. This problem is called Exposed Station problem.

To deal with these problems 802.11 supports two kinds of operations.

1. DCF (Distributed Coordination Function)
2. PCF (Point Coordinated Function)

DCF

DCF does not use and central control. It uses CSMA/CA protocol. It uses physical channel sensing and virtual channel sensing. Here when a station wants to send packets, first it senses the channel. If the channel is idle, immediately starts transmitting. While transmitting, it does not sense the channel, but it emits its entire frame. This frame can be destroyed at the receiver side if receiver has started transmitting. In this case, if collision occurs, the colliding stations wait for random amount of time using the binary exponential back off algorithm and tries again letter.

Virtual sensing is explained in the figure given below.

Here, A wants to send a packet to B. Station C is within A’s Range. Station D is within B’s range but not A’s range. When A wants to send a packet to B, first it sends the RTS (30 bytes) packet to B, asking for the permission to send the packet. In the response, if B wants to grant the permission, it will send the CTS packet to A giving permission to A for sending the packet. When A receives its frame it starts ACK timer. When the frame is successfully transmitted, B sends ACK frame. Here if A’s ACK time expires before receiving B’s ACK frame, the whole process will run again. Here for the stations C and D, when station A sends RTS to station B, RTS will also be received by C. By viewing the information provided in RTS, C will realize that some on is sending the packet and also how long the sequence will take, including the final ACK. So C will assert a kind of virtual channel busy by itself, (indicated by NAV (network Allocation Vector) in the figure above).remain silent for the particular amount of time. Station D will not receive RTS, but it will receive CTS from B. So B will also assert the NAV signal for itself.

If the channel is too noisy, when A send the frame to B and a frame is too large then there are more possibilities of the frame getting damaged and so the frame will be retransmitted. C and D, both stations will also remain silent until the whole frame is transmitted successfully. To deal with this problem of noisy channels, 802.11 allows the frame to be fragmented into smaller fragments. Once the channel has been acquired using CTS and RTS, multiple segments can be sent in a row. Sequence of segments is called a fragmentation burst. Fragmentation increases the throughput by restricting retransmissions to the bad fragments rather than the entire frame.

PCF

PCF mechanism uses base station to control all activity in its cell. Base station polls the other station asking them if they have any frame to send. In PCF, as it is centralized, no collision will occur. In polling mechanism, the base station broadcasts a beacon frame periodically (10 to 100 times per second). Beacon frame contains system parameters such as hopping sequences, dwell times, clock synchronization etc. It also invites new station to sign up. All signed up stations are guaranteed to get a certain fraction of the bandwidth. So in PCF quality of service is guaranteed.

All implementations must support DCF but PCF is optional. PCF and DCF can coexist within one sell. Distributed control and Centralized control, both can operate at the same time using interframe time interval. There are four interval defined. This four intervals are shown in the figure given below.

• SIFS - Short InterFrame Spacing
• PIFS – PCF InterFrame Spacing
• DIFS – DCF InterFrame Spacing
• EIFS – Extended Inter Frame Spacing

More about this has been explained in section 3 of Data Link Layer.

Taking Turns MAC protocols

Polling

In Polling, master node invites slave nodes to transmit in nodes. Single point of failure (master node failure), polling overhead, latency are the concerns in polling.

Bit map Reservation

In Bit map reservation, stations reserves contention slots in advance. Polling overhead and latency are the concerns in this protocol.

Token Passing

In this protocol, token is passed from one node to next sequentially. Single point of failure (token), token overhead, latency are the concerns in token passing.

Problems

1. Explain hidden station and exposed station problem.
2. Explain Binary Exponential Backoff Algorithm.
3. Two CSMA/C stations are trying to transmit long files. After each frame is sent, they contend for the channel using binary exponential backoff algorithm. What is the probability that the connection ends on round k?
4. In CRC , if th data unit is 101100 the divisor 1010 and the reminder is 110 what is the dividend at the receiver? (Ans: )

Further reading

• Serial Programming:Error Correction Methods