The Data Link Layer

Unit-2

Data Link Protocols

1. Directly connected, wire-like
2. Losses & errors, but no out-of-sequence frames
3. Applications: Direct Links; LANs; Connections across WANs

Data Links Services

• Framing
• Error control
• Flow control
• Multiplexing
• Link Maintenance
• Security: Authentication & Encryption

​

Examples

• PPP
• HDLC
• Ethernet LAN
• IEEE 802.11 (Wi Fi) LAN

Data Link Layer Services:

​

1. Unacknowledged Connectionless Service
2. Acknowledged Connectionless Service
3. Acknowledged Connection Oriented Service

Framing Methods:

• Character Count
• Starting and Ending characters with character stuffing
• Starting and Ending flags with bit stuffing
• Physical Layer coding violations

​

​

1.3

Framing

1. Mapping stream of physical layer bits into frames
2. Mapping frames into bit stream
3. Frame boundaries can be determined using:
1. Character Counts
2. Control Characters
3. Flags
4. CRC Checks

​

Example Data Link Protocols

• HDLC – High-Level Data Link Control
• The Data Link Layer in the Internet

Data Link Sublayers

• Logical Link Control (LLC) - This IEEE 802.2 sublayer communicates between the networking software at the upper layers and the device hardware at the lower layers. It places information in the frame that identifies which network layer protocol is being used for the frame. This information allows multiple Layer 3 protocols, such as IPv4 and IPv6, to use the same network interface and media.
• Media Access Control (MAC) – Implements this sublayer (IEEE 802.3, 802.11, or 802.15) in hardware. It is responsible for data encapsulation and media access control. It provides data link layer addressing and it is integrated with various physical layer technologies.
• The MAC sublayer provides data encapsulation:
• Frame delimiting - The framing process provides important delimiters to identify fields within a frame. These delimiting bits provide synchronization between the transmitting and receiving nodes.
• Addressing - Provides source and destination addressing for transporting the Layer 2 frame between devices on the same shared medium.
• Error detection - Includes a trailer used to detect transmission errors.

​

1.6

Error:

Data transmitted in the network

The data can be corrupted during transmission

Transmission error

For reliable communication, errors must be detected and corrected.

Error detection and correction are implemented either at the data link layer or the transport layer of the OSI model

1. Types of Errors:

Errors can be classified into different types. They are

1. Content Error
2. Flow Integrity Error

Content Error:

These errors are nothing but errors in the content of a message.

Ex: ‘0’ may received as ‘1’ & vice-versa.

These errors may occurred due to noise added into the data signal during transmission.

Flow Integrity Errors:

It means the missing the blocks of data. It is possible that data block may be loss in the network as it has been delivered to the wrong destination

1.19

Depending upon the number of bits errors can be classified into 2 types. They are

1. Single-bit error
2. Burst error

Single-bit error:

The term single-bit error consists of only one bit get corrupted in parallel transmission.

Burst error:

More than 1 bit get corrupted in serial transmission due to occurrences of noise. A byte changed from 1 to 0 or from 0 to 1 then burst errors are occurred.

The length of the burst is measured from first corrupted bit to the last corrupted bit.

​

1.20

Error:

​

CODES

How to Detect the Errors?

1. Error detection means to decide whether the received data is correct or not without having a copy of the original message.
2. To detect or correct errors, we need to send some extra bits with the data.
3. The extra bits are called as redundant bits.

Error Correction :

It can be handled by two ways:

1. Receiver can have the sender retransmit the entire data unit.
2. The receiver can use an error- correcting code, which automatically corrects certain errors

​

​

1.28

Codeword:

• A n-bit codeword: a frame of m-bit data plus k-bit redundant check bits (n = m + k)

Message bit + Parity bit = Codeword

Code Rate: It is defined as the ratio of the number of message bits(m) to the total number of bits(n).

r= m/n

Code Efficiency:

It is defined as the ratio of message bits to the number of transmitted bits per block.

Code efficiency = Code rate= m/n

Party bits or Check bits or Redundant bits:

Parity bits means extra bits are added to data. By using parity bit, we can correct & detect the errors.

​

​

​

​

​

​

​

​

​

​

Error Detection Techniques:

• Simple parity check or VRC (Vertical Redundancy Check)
• Two-Dimensional parity check
• Check sum Error Detection
• Cyclic Redundancy Check (CRC)

​

• Simple Parity Bits:

​

​

​

​

P- Parity bit

D6-D0= Data Bits

1.30

1.31

Single Parity Check

1. Append an overall parity check to k information bits

• All codeword's have even # of 1s
• Receiver checks to see if # of 1s is even
• Parity bit used in ASCII code

Example of Single Parity Code

1. Information (7 bits): (0, 1, 0, 1, 1, 0, 0)
2. Parity Bit: b₈ = 0 + 1 +0 + 1 +1 + 0 = 1
3. Codeword (8 bits): (0, 1, 0, 1, 1, 0, 0, 1)

​

• If single error in bit 3 : (0, 1, 1, 1, 1, 0, 0, 1)
1. # of 1’s =5, odd
2. Error detected

​

• If errors in bits 3 and 5: (0, 1, 1, 1, 0, 0, 0, 1)
• # of 1’s =4, even
• Error not detected

Simple Parity Check:

• The most common and least expensive mechanism for error detection is the simple parity check. In this technique , a redundant bit called parity bit is appended to every data unit.
• Generally the MSB of 8-bit word is used as the parity bit and the remaining 7 bits are used as data bits / message bits.
• The parity of the 8-bit transmitted word can be either even parity / odd parity.
• Even parity means no of 1’s in the given word including the parity should be even(2,4,6,…)
• Odd parity means no of 1’s in the given word including the parity should be odd(1,3,5,7, …)

​

1.34

1. Limitations of simple parity check:

It is not suitable for detection of multiple errors

Ex:(2,4,6)

Parity checking method cannot reveal the location of error

bits and it cannot be corrected.

Two-Dimensional Parity Check:

• Data is in the form of rows and columns. It is applicable for only 2 errors.
• It is used for only detecting error. It doesn’t correct the error.
• It is one of the important method of error detection.
• When large no of binary words are transmitted or received i.e a block of data with rows & columns.

1.35

Two-Dimensional Parity Check

1. More parity bits to improve coverage
2. Arrange information as columns
3. Add single parity bit to each column
4. Add a final “parity” column

1 0 0 1 0 0

0 1 0 0 0 1

1 0 0 1 0 0

1 1 0 1 1 0

1 0 0 1 1 1

Bottom row consists of check bit for each column

Last column consists of check bits for each row

1. Limitations of 2-D parity check:

Multiple errors in rows and columns can only be detected but they cannot be corrupted.

Check Sum for Error Detection:

• To overcome the limitations of 2-D parity check by using check sum detection method.
• In this method, a check sum is transmitted along with every block of data bytes & 8-bit accumulator is used to add a 8-bit block of data to find the check sum byte.
• The carry of the MSB are ignored while finding out the check sum byte.

​

1.37

1. Sender side

Word A: 1 0 1 1 0 1 1 1

Word B: 0 0 1 0 0 0 1 0

Sum: 1 1 0 1 1 0 0 1

Checksum: 0 0 1 0 0 1 1 0 ( 1’s complement)

​

Receiver side:

Word A: 1 1 0 1 1 0 0 1

Word B: 0 0 1 0 0 1 1 0

sum: 1 1 1 1 1 1 1 1

Checksum: 0 0 0 0 0 0 0 0 (1’s complement)

Ex: 10110001, 10101011, 00110101,10100001 Find the checksum of the following message

1.38

Sol: Receiver Data

1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1

1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1

1 0 1 0 1 1 1 0 0 1 0 1 0 1 1 1 0 0

1 1

0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1

0 0 1 1 0 1 0 1 0 0 1 1 0 1 0 1

1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0

1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1

1 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1

1 1

Sum 0 0 1 1 0 1 0 0 1 1 1 1 1 1 1 1

Check sum 1 1 0 0 1 0 1 1 Check Sum 0 0 0 0 0 0 0 0

​

​

​

​

1.39

1. CRC is a block of code that was invented by Wesley Peterson in 1961. It is most commonly used technique to detect the errors in data transmission.
2. CRC is a type of polynomial code in which a bit stream is represented in the form of polynomial with coefficients of 0 & 1 only.
3. In CRC code, the sender and receiver should agree upon a generator polynomial [g(x)]. A codeword generated for a given data word. Polynomial [m(x)] with the help of long binary division.
4. CRC is based upon binary division.
5. A sequence of redundant bits is called CRC remainder is appended at the end of the data unit such as byte.

​

​

​

Cyclic Redundancy Check

1. The resulting data unit after adding CRC remainder becomes exactly divisible by another pre-determined binary number.
2. At the receiver, this data unit is divided by the same binary number. If the result is 0 , then there is no error in the data bit.

1.41

CRC Idea - Checkbits & Error Detection

Generator

Polynomial

Generator

Polynomial

Procedure for CRC Generation:

• Append a string of n i.e 0’s to the data unit where n is 1 less than no of bits in a predefined device.
• Divide the newly generated data unit in step 1 by the divisor using binary division.
• The remainder is obtained after division in step-2, the n-bit CRC.
• The CRC will replace the no’s appended to the data unit in step-1 to get the code-word to be transmitted.

In CRC, check sum method, the transmitted message is 1101011011 & the generator polynomial is g(x)= x^4+x+1. So what is the dividend at the receiver.

Sol: g(x)= x^4+x+1-> 10011

X^3+1=1001 X^5+x+1=100011

​

1.43

An Example – Step-by-Step

An Example – Step 1

An Example – Step 2

An Example – Step 3

An Example – Step 4

An Example – Step 5

An Example – Step 6

An Example – Step 7

An Example – Step 8

An Example – Step 9

An Example – Step 10

Overall

Hamming Code:

1. Hamming code was invented by Richard Hamming in 1950.
2. These codes are linear block codes. It is a set of error correction codes that can be used to detect and correct bit error that can be occur when computer data is moved or stored.
3. It can detect up to two simultaneous bit errors and is capable of correcting single bit error.
4. Structure of Hamming Code:

7-Bit Hamming code

4 –Data Bits , 3 –Parity Bits

1.56

1. 15-bit Hamming Code:

​

​

​

The Parity bits are inserted at each 2^n bit where n=0,1,2,3---

(i.e) P1 is 2^0=1 at first bit P2 is 2^1=2

Selection of Parity Bits:

Selection of P1: P1 is adjusted to ‘0’ or ‘1’. So establish even parity over bits 1,3,5,7(i.e P1,D3,D5,D7).

Selection of P2: P2 is adjusted to ‘0’ or ‘1’. So establish even parity over bits 2,3,6,7(i.e P2,D3,D6,D7).

Selection of P4: P1 is adjusted to ‘0’ or ‘1’. So establish even parity over bits 4,5,6,7(i.e P4,D5,D6,D7).

​

​

​

1.57

1. A Bit word 1011 is to be transmitted. Construct the even parity 7-bit Hamming code for the data.

D7 D6 D5 P4 D3 P2 P1

​

​

i) Decide P1:

P1 may be (0 or 1) i.e P1 => 1, 3, 5, 7 => 1 1 1 1 => To become even parity ‘1’ is substituted.

ii) Decide P2:

P2 may be ( 0 or 1) i.e P2=> 2, 3, 6, 7 => 0 1 0 1 => It is in even parity So P2= 0.

iii) Decide P4:

P4 may be (0 or 1) i.e P4 => 4, 5 ,6, 7 => 1 0 1 0 => To make even parity P4 should be ‘0’

​

1.58

1. Decide P1:

D7 D6 D5 P4 D3 P2 P1

​

​

1. Decide P2:

D7 D6 D5 P4 D3 P2 P1

​

​

1. Decide P4:

D7 D6 D5 P4 D3 P2 P1

D7 D6 D5 P4 D3 P2 P1

1.59

1. If the 7-bit Hamming code received by a receiver is 1011011.Assuming the even parity, state whether the received codeword is correct or wrong. If wrong locate the bit in error.

D7 D6 D5 P4 D3 P2 P1

​

​

Step 1: Analyze bits 4,5,6,7 i.e P4 1 1 0 1 (Odd Parity) . Error exist here

Hence we put P4=1 in the 4^th position of the error word.

Step 2: Analyze bits 2,3,6,7 i.e P2 1 0 0 1 (Even Parity) . No error

Hence we put ‘0’ in P2 i.e P2 = 0

Step 3: Analyze bits 1,3,5,7 i.e 1 0 1 1 (Odd Parity). Error exists here

Hence we put P1 = 1 in the 1^st position of the error word.

Step 4: Write the error word

Error word E =>

​

E= = (5)10

​

1.60

1. Here , bit 5 of the transmitted codeword is in error.

​

​

​

​

Incorrect bit

Step 5: Correct the error . Correct codeword is given below

​

​

​

• A 7-bit Hamming code is received as 1110101. what is the correct codeword. Assuming the even parity, state whether codeword is Wright/ wrong

1.61

Pulse Code Modulation & Delta Modulation:

1. In Physical Layer, It moves the data in the form of electro-magnetic signals across the transmission medium. The signals can be either Analog (or) Digital.
2. Analog Signal:

The term “Analog” refers to the information i.e continuous. Analog signals can have an infinite number of values in a ray.

Ex: Analog clock that has hours, minutes, seconds gives information in a continuous form.

Digital Signal:

The term “Digital” refers to information that has discrete states. Digital signals can have only a limited number of values.

Ex: Digital clock that repeats hours, minutes change suddenly from 8:05 pm to 8:06 pm.

​

1.62

1.63

1. Period:

It refers to amount of time in seconds signal needs to complete one cycle.

• Frequency:

It refers to number of periods in one second.

Period is the inverse of frequency and vice versa

F = 1 / T

Period is expressed in seconds. Frequency is expressed in Hertz.

​

Transmission Impairments:

There are 3 factors for impairment. They are

1. Attenuation
2. Distortion
3. Noise

​

1.64

1. Attenuation:

It means a loss of energy. When a signal i.e simple or composite travels through a medium, it loses some of its energy in overcoming the resistance of the medium.

1. Distortion:

The signal changes its shape. It occur in composite signal made of different frequencies.

1. Noise:

External energy that corrupts the signal is called noise. Several types of noises are: Thermal noise, Induced noise, Impulse noise, and Cross Talk noise may corrupt the signal.

1. Bandwidth:

The bandwidth of a composite continuous sine wave signal is the difference between the highest and lowest frequencies contained in the signal.

Composite means a signal is made up of many simple sign waves

​

1.65

1. Base Band Transmission:

It means sending a digital signal over a channel without changing the digital signal to the analog signal.

1. Signal to Noise Ratio:

SNR = Average Signal Power/ Average Noise Power

SNRdB =10 log10SNR

​

1. Noise Less Channel( Nyquist Bit Rate):

It defines the maximum bit rate.

​

Bit rate = 2 * Band width * log2l

Where l is number of signal levels represent data.

Bit rate- Number of bits per second

1.66

The Maximum Data Rate of a Channel

1. Nyquist’s theorem

​

​

• Shannon’s formula for capacity of a noisy channel

​

​

​

​

1.67

1. Consider a noise less channel with a bandwidth of 3000HZ transmitting a signal with two signal levels. The maximum bit rate can be calculated as?

Ans: Bandwidth = 3000 Hz

Level l= 2

Bit rate = 2 * bandwidth * logl2

= 2 * 3000 * log22

= 6000

1. Consider a noise less channel with a bandwidth of 3000HZ transmitting a signal with four signal levels. The maximum bit rate can be calculated as?

Ans: Bandwidth = 3000 Hz

Level l= 4

Bit rate = 2 * bandwidth * logl2

= 2 * 3000 * log42

= 12000

​

1.68

Analog to Digital Conversion:-��Pulse Code Modulation:

1.69

1.70

1.71

1. The Most common technique to change an analog signal to digital data is called pulse code modulation(PCM). It consists of 3 components.

i) Transmitter ii) Transmission Path iii) Receiver

The operations on the transmitter in PCM system are:

i) Sampling ii) Quantizing iii) Encoding

Sampling:

It is defined as process of measuring instaneous values of continuous time signal into discrete form (or) the discretization of analog signal called sampling.

Quantizing:

The method of sampling chooses a few points on the analog signal and then these points are jointed to round of the value to the nearest stabilized value. Such process is called quantizing or quantization.

Encoding:

It means to convert body of information from one system to another system in the form of codes.

​

1.72

1. PCM was originally developed for telephone communication system. This is used in digital audio formats such as audio CD’s , DVD’s & Blue Ray disks.

Delta Modulation:

• It is an analog to digital and digital to analog signal conversion technique. It is used for transmission of voice information.
• Delta modulation is the simplest form of Differential Pulse Code Modulation (DPCM).
• In PCM system no of binary digits are transmitted for quantized sample. Hence the signaling rate and bandwidth of the transmission channel are very large. These disadvantages are overcome by Delta Modulation.
• DM transmits only one bit per sample instead of n bits transmitted in PCM.
• If the step is reduced, 0 is transmitted and if the step is increased , 1 is transmitted.

​

​

​

1.73

1.74

1. Modulator:

It is used to covert the analog signal to digital signal.

De-Modulator:

It is used to covert the digital signal to analog signal.

Transmission Modes:

Data transmission can be done in two ways . They are

1. Parallel 2. Serial

Parallel Transmission:

• We can send the data n-bits at a time instead of 1-bit is called parallel transmission .
• Use n-wires to send n-bits at one-time.

Dis-advantages:

Parallel transmission requires n-communication lines to transmit the data stream because this is expensive for short distances.

​

1.75

1. Serial Transmission:

In this mode one bit follows another . So we need only one communication channel rather than to transmit the data between 2 connected devices.

There are different types in serial transmission

1. Synchronous ii) Asynchronous iii) Isochronous

Synchronous Transmission:

• In this type the data flows in full-duplex mode in form of blocks of frames. In Synchronous requires a clock signal between sender and receiver so as to inform the receiver about a new byte.
• It is efficient and reliable and is used for transferring a large amount of data.

Ex: Chat rooms, Video conferencing, Telephone Conversation.

Asynchronous Transmission:

• In this mode data flows in half-duplex mode i.e 1 byte or a character at a time.
• It transmits the data in continuous stream of bytes.

​

1.76

1. It doesn’t require a clock for synchronization .

Ex: Letters , emails, forums, televisions and radios.

​

Q) How many 8-bits can be transmitted per second over a 9600 baud serial communication link using asynchronous mode of transmission with one start bit, 8 data bits , 2 stop bits & 1 parity bit.

Ans: Data sent = 1 bit (start) + 8 (char size) + 2 bits (stop) + 1 bit (parity)

=12 bits.

No of characters that can be transmitted per seconds = 9600/12=

= 800 bits

Q) Assume that each character code consists of 8 bits the no of characters that can be transmitted per second through an synchronous serial line at 2400 baud rate with 2 stop bits.

Ans: Data sent = 8 bits

No of characters that can be transmitted per second = 2400/8= 300 bits

1.77

Multiplexing

1. Multiplexer allows a line to carry frames to/from multiple terminals
2. Frames are buffered at multiplexer until line becomes available, i.e. store-and-forward
3. Header carries other control information for framing

Frame

1. Multiplexing:

In multiplexing system , n input lines given to the system , it gives only one output.

1. De-multiplexing:

In this system one input line is given to the system, it gives n output lines.

There are 3 types of techniques:

1. FDM (Frequency Division Multiplexing)
2. TDM (Time Division Multiplexing)
3. WDM (Wavelength Division Multiplexing)

FDM (Frequency Division Multiplexing):

• In the FDM technique no of signals are transmitted at the same time, and each source transfer it signals in the allotted frequency range.
• There is suitable frequency gap between the two adjacent signals to avoid overlapping.
• The signals are transmitted in allotted time. So this decreases the probability of collision.

1.79

1. The frequency spectrum is divided into several logical channels. Each channel have separate frequency band to each signal.
2. It is used in Radio broad casting & Telecommunication.

​

TDM(Time Division Multiplexing):

When data transmission rate of media is greater than of the source and each signal is allotted a definite amount of time.

In FDM, all the signals operate at the same time using different frequencies, but in TDM all the signals operate with same frequency with different time.

TDM is divided into 2 types.

1. Asynchronous TDM ii) Synchronous TDM

Asynchronous TDM: The slots are dynamically assigned depending on the speed of the source.

Synchronous TDM: The time slots are pre-assigned and fixed. It statistically allocates the time slots according to different i/p channel needs.

1.80

1.81

Bandwidth

• Bandwidth is the capacity at which a medium can carry data. Digital bandwidth measures the amount of data that can flow from one place to another in a given amount of time. Bandwidth is typically measured in kilobits per second (kbps), megabits per second (Mbps), or gigabits per second (Gbps). 
• Bandwidth Terminology the quality of bandwidth include:
• Latency
• Throughput
• Goodput

Latency: Latency refers to the amount of time, including delays, for data to travel from one given point to another.

Throughput: Throughput is the measure of the transfer of bits across the media over a given period of time.

Goodput:

1. There is a third measurement to assess the transfer of usable data; it is known as goodput. Goodput is the measure of usable data transferred over a given period of time. 

​

1.82

Types of Wireless Media

• Wi-Fi (IEEE 802.11) - Wireless LAN (WLAN) technology, commonly referred to as Wi-Fi. WLAN uses a contention-based protocol known as carrier sense multiple access/collision avoidance (CSMA/CA). The wireless NIC must first listen before transmitting to determine if the radio channel is clear. If another wireless device is transmitting, then the NIC must wait until the channel is clear. Wi-Fi is a trademark of the Wi-Fi Alliance. Wi-Fi is used with certified WLAN devices based on the IEEE 802.11 standards.
• Bluetooth (IEEE 802.15) - This is a wireless personal area network (WPAN) standard, commonly known as “Bluetooth.” It uses a device pairing process to communicate over distances from 1 to 100 meters.
• WiMAX (IEEE 802:16) - Commonly known as Worldwide Interoperability for Microware Access (WiMAX), this wireless standard uses a point-to-multipoint topology to provide wireless broadband access.
• Zigbee (IEEE 802.15.4) - Zigbee is a specification used for low-data rate, low-power communications. It is intended for applications that require short-range, low data-rates and long battery life. Zigbee is typically used for industrial and Internet of Things (IoT) environments such as wireless light switches and medical device data collection.

​

1.83

Data Link Layer Flow Control Protocols:

​

Protocols

​

​

​

​

Noise Less Channel Noisy Channel

Simplest (utopia) 1-bit Stop-and Wait

Go-Back-N ARQ

Stop-and-wait Selective Repeat ARQ

Elementary Data Link Protocols

• An Unrestricted Simplex Protocol
• A Simplex Stop-and-Wait Protocol
• A Simplex Protocol for a Noisy Channel

​

1. Unrestricted Simplest Protocol:

This protocol is the simplest possible protocol. The transmission of data takes place in only one direction.

• It is unidirectional protocol.
• It is assumed that n/w layer of sender and receiver are always ready. It is also assumed that processing time can be ignored and infinite buffer space is available.
• The communication channel is noisy free. So it does not damage or loss any frame.
• No sequence number and acknowledgements are used.

Sender Side Algorithm for the simplest Protocol:

​

While(true) // Repeat forever

{

waitforEvent(); // sleep until an event oocur

if( Event(RequestToSend)) // There is a packet to send

{

GetData();

MakeFrame();

SendFrame(); // send frame

}

}

Receiver side Algorithm for the simplest protocol:

​

While(true) //Repeat forver

{

WaitforEvent(); //sleep until an event occurs

if(Event (Arrival Notification)) // Data frame arrived

{

Receiver Frame();

Extract Data();

Deliver Data(); // Deliver data to network layer

}

}

Protocol Definitions

Continued 🡪

Some definitions needed in the protocols to follow. These are located in the file protocol.h.

Unrestricted �Simplex �Protocol

Stop-and-wait protocols:

• Stop-and-wait protocol is a DLL protocol for transmission of frames over noise less channels.
• It provides unidirectional data transmission with flow control facilities but without error control facilities.
• The idea of stop-and-wait protocol is straight forward.
• After transmitting one frame the sender waits for an acknowledgement before transmitting the next frame.
• In stop-and-wait protocol a small dummy frame is send back from receiver to transmitter, to indicate that it can send the next frame. The transmitter sends one frame and waits for dummy frame is called acknowledgement.
• Once the acknowledgement is received it sends the next frame. Hence the name is called stop-and-wait. In this every incoming is always have an acknowledgement.

Sender Side Algorithm:

While(true) //Repeat forever

Cansend=true // Allow the first frame togo

{

waitforEvent();

if(Event(Request to send() and Can send)

{

GetData();

MakeFrame();

SendFrame(); //send frame

CanSend= False; //cannot send until ACK arrives

}

WaitforEvent(); // Sleep until an event occurs

if(Event(Arrival Notification)) // An ack has arrived

{

ReceiverFrame(); // Receive the frame

Cansend= True;

}}

​

Receiver Side Algorithm:

While(true) // Repeat forver

{

WaitforEvent(); // sleep until an event occur

if(Event(Arrival Notification)) // Data frame arrives

{

Receiver Frame();

Extract Data();

Deliver Data(); //Deliver data to n/w layer

Send Frame(); //send an Ack frame

}

}

​

Simplex Stop-and-Wait Protocol

A Simplex Protocol for a Noisy Channel

A positive acknowledgement with retransmission protocol.

Continued 🡪

A Simplex Protocol for a Noisy Channel (ctd.)

A positive acknowledgement with retransmission protocol.

Piggy Backing:

• Let A and B are the users. Then the data frames from A to B are inter mixed with acks from A to B. When the data frames arrives at the receiver the receiver waits does not sends the control frame (ACK) back immediately.
• The receiver waits until its n/w layer passes in the next data packet. The ack is then attached to the outgoing data frame. This technique in which the outgoing ack is delayed temporarily is called piggybacking.

Advantages:

It is better use of available channel bandwidth.

Disadvantages:

Additional system complexity

Sliding Window Protocols

• A One-Bit Sliding Window Protocol
• A Protocol Using Go Back N
• A Protocol Using Selective Repeat

​

Sliding Window Protocols (2)

A sliding window of size 1, with a 3-bit sequence number.

(a) Initially.

(b) After the first frame has been sent.

(c) After the first frame has been received.

(d) After the first acknowledgement has been received.

1-Bit Stop-and-Wait ARQ Protocol:

• This protocol is also called 1-bit protocol because the maximum window size here i.e n=1. It uses stop-and-wait technique.
• The sender sends one frame and waits to get its acknowledgement . Only after receiving the acknowledgment, it transmit the next frame. Because of this 1-bit sliding window protocol is also called as stop-and-wait protocol.

Operation of Protocol:

• In this method, the transmitter transmits one frame of data and waits for an acknowledgement from the receiver. If it receives +ve acknowledgment (ACK), it transmits the next frame. If it receive

–ve acknowledgement (NAK) it retransmits the same frame.

When retransmission necessary?

1. If the received frame is damaged.
2. If the transmitted frame is lost.
3. If the acknowledgement from the receiver is lost.

​

Drawbacks of Stop-and-Wait ARQ Protocol:

It is very inefficient. At any one moment, only one frame is transmitted . The sender will have to wait at-least one round trip time before sending next frame.

Sender Side Algorithm:

Sn=0; // frame 0 should be sent first

Cansend=true; //allow the first request to go

While(true) // repeat forever

{

WaitforEvent(); // sleep until an event occurs

if(Event(RequestToSend)AND cansend)

{

GetData();

MakeFrame(Sn); // the seqno is Sn

StoreFrame(Sn); // Keep copy

​

SendFrame(Sn);

StartTimer();

Sn=Sn+1;

}

WaitforEvent()

if(Event(ArrivalNotification))

{

ReceiveFrame(ackno);

if(notCorrupted AND ackno==S0)

{

Stoptimer();

PurgeFrame(Sn-1); // Duplicate frame copy is not allowed

Cansend=true;

}

}

​

​

​

if(Event (Timeout))

{

StartTimer();

ResendFrame(Sn-1);

}

}

​

Receiver Side Algorithm:

​

Rn=0; // Frame 0 expected to arrive first

While(true)

{

WaitforEvent(); //sleep until an event occurs.

if(Event(Arrival Notification)) // data frame arrives

{

Receive Frame();

if(corrupted (frame))

sleep();

if(seqno==Rn) // Valid data frame

{

Extract Data();

Deliver Data(); // Deliver data

Rn= Rn+ 1;

}

SendFrame(Rn); //send an ACK

}

}

​

​

​

Sliding Window Protocol :

• It sends multiple frames at a time.
• Number of frames to be sent is based on window size.
• Each frame is numbered -> Sequence number

A Protocol Using Go Back N

Pipelining and error recovery. Effect on an error when

(a) Receiver’s window size is 1.

(b) Receiver’s window size is large.

• GO-Back-N ARQ uses the concept of protocol i.e the sender can send multiple frames before receiving the acknowledgment of first frame.
• There are finite number of frames, and the frames are numbered in a sequential frame
• The number of frames that can be sent depends upon the window size of the sender.
• If the acknowledgement of a frame is not received within an agreed upon time period, all frames in the current window are transmitted.
• The size of the sending window determines the sequence number of outbound frames.
• For example , if the sending window size is 4 (2^2) , then the sequence numbers will be 0,1,2,3,0,1,2,3,0,1 and so on
• The number of bits in the sequence number is 2 to generate the binary sequence 00,01,10,11.

Go-Back-N ARQ protocol is used to overcome the ineffiency of stop-and-wait ARQ by allowing the transmitter to continuously sending the frames. So that the channel is kept busy. In this method, if one frame is damaged or lost, all frames are send. Since last frame acknowledged or retransmitted.

Principle of Go-Back-N ARQ:

• The major difference b/w stop-and-wait ARQ and Go-Back-N ARQ is that the sender does not wait for acknowledgement signal for the transmission of next frame.
• It transmits the frames continuously as long as it does not receive the –Ve Acknowledgment (NAK) .
• When the receiver detects an error in the 3^rd frame as shown in above fig.
• The receiver sends NAK signal back to the sender. But the signal takes some time to reach the transmitter. By that time the transmitter has transmitted upto 7 frames.

• On the reception of NAK signal the transmitter will retransmits all the frames from 3^rd frame onwards.
• The receiver discard all the frames it has received after frame 3 i.e 3 to 7. It will then receive all the frames that are retransmitted by the transmitter.

Sliding Window Protocol Using Go Back N

Continued 🡪

Sliding Window Protocol Using Go Back N

Continued 🡪

Sliding Window Protocol Using Go Back N

Continued 🡪

Sliding Window Protocol Using Go Back N

Selective Repeat ARQ Protocol:

• In Selective Repeat ARQ, only the erroneous or lost frames are retransmitted, while correct frames are received and buffered.
• 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 will send / retransmit packet for which NACK is received.

​

A Sliding Window Protocol Using Selective Repeat

Continued 🡪

A Sliding Window Protocol Using Selective Repeat (2)

Continued 🡪

A Sliding Window Protocol Using Selective Repeat (3)

Continued 🡪

A Sliding Window Protocol Using Selective Repeat (4)

A Sliding Window Protocol Using Selective Repeat (5)

(a) Initial situation with a window size seven.

(b) After seven frames sent and received, but not acknowledged.

(c) Initial situation with a window size of four.

(d) After four frames sent and received, but not acknowledged.

1) Station A needs to send a message consisting of 9 packets to station B using a sliding window (window size 3) and go-back-n error control strategy. All packets are ready and immediately available for transmission. If every 5^th packet that A transmits gets lost (but no Acks from B ever get lost) , then what is the number of packets that A will transmit for sending the message to B? [GATE CS 2006]

A) 12 B) 14 C) 16 D) 18

​

2) Host A wants to send 10 frames to host B. The hosts agreed to go with Go-Back-4 . How many number of frames are transmitted by Host A if every 6^th frame that is transmitted by host A is either corrupted or lost?

​

A) 12 B) 14 C) 17 D) 18

​

Introduction To Data-Link Layer

Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.

9.145

9.9.3 Two Categories of Links

Although two nodes are physically connected by a transmission medium such as cable or air, we need to remember that the data-link layer controls how the medium is used.

​

We can have a data-link layer that uses the whole capacity of the medium; we can also have a data-link layer that uses only part of the capacity of the link.

​

In other words, we can have a point-to-point link or a broadcast link.

9.146

9.9.4 Two Sublayers

To better understand the functionality of and the services provided by the link layer,

​

we can divide the data-link layer into two sublayers:

• data link control (DLC) and
• media access control (MAC).

9.147

Figure 9.3: Dividing the data-link layer into two sublayers

9.148

5-4 LINK-LAYER ADDRESSING

IP addresses as the identifiers at the network layer.

However, in a internetwork such as the Internet we cannot make a datagram reach its destination using only IP addresses.

The source and destination IP addresses define the two ends but cannot define which links the packet should pass through.

9.149

9.2.1 Three Types of addresses

Some link-layer protocols define three types of addresses:

• unicast
• multicast
• broadcast

Media Access Control

(MAC)

Chapter 5: Outline

12.1 RANDOM ACCESS

​

�

12.2 CONTROLLED ACCESS

​

�

12.3 CHANNELIZATION

​

�

​

​

�

• The first section discusses random-access protocols. Four protocols, ALOHA, CSMA, CSMA/CD, and CSMA/CA, are described in this section. These protocols are mostly used in LANs and WANs.

• The second section discusses controlled-access protocols. Three protocols, reservation, polling, and token-passing, are described in this section. Some of these protocol are used in LANs, but others have some historical value.

• The third section discusses channelization protocols. Three protocols, FDMA, TDMA, and CDMA are described in this section. These protocols are used in cellular telephony.

Multiple Access Protocols:

• If there is a dedicated link between the sender and the receiver then data link control layer is sufficient, however if there is no dedicated link present then multiple stations can access the channel simultaneously.
• Hence multiple access protocols are required to decrease collision & avoid crosstalk.

Random Access Protocols:

• The name itself indicates any station can send the data at any time.
• In this all stations have same superiority that is no station has more priority than another station. Any station can send data depending on medium’s state (idle or busy).
• In random access method each station has the right to the medium without being controlled by any other station.

​

​

12.153

1. If more than one station tries to send there is an access conflict (collision) and the frames will be either destroyed or modified.
2. To avoid access conflict each station follows procedure.
1. When can the station access the medium?
2. What can the station do if the medium is busy?
3. How can the station determine the success or failure of the

transmission?

• What can the station do if there is an access conflict?

Controlled Access Protocols:

• In controlled access the stations consult one another to find which station has the right to send.
• A station cannot send unless it has been authorized by other stations.

​

​

12.154

Channelization Protocols:

• Channelization is a multiple-access method in which the available bandwidth of a link is shared in time, frequency, or through code, between different stations.

12.155

12.156

Figure 12.1: Taxonomy of multiple-access protocols

Classification of Multiple Access Protocols

12.158

Media Access Control Protocol

​

When nodes or stations are connected and use a common link, called a multipoint or broadcast link.

​

we need a multiple-access protocol to coordinate access to the link.

​

Many protocols have been devised to handle access to a shared link.

​

All of these protocols belong to a sub layer in the data-link layer called media access control (MAC).

​

12.159

RANDOM ACCESS

​

​

In random-access or contention no station is superior to another station and none is assigned control over another.

​

At each instance, a station that has data to send uses a procedure defined by the protocol to make a decision on whether or not to send.

​

This decision depends on the state of the medium (idle or busy).

​

Also called contention-based access

12.160

Two features give this method its name.

​

First:

there is no scheduled time for a station to transmit.

Transmission is random among the stations.

That is why these methods are called random access.

​

Second:

no rules specify which station should send next.

Stations compete with one another to access the medium.

​

if more than one station tries to send, there is an access conflict-collision-and the frames will be either destroyed or modified.

12.161

each station follows a procedure that answers the following questions:

• When can the station access the medium?
• What can the station do if the medium is busy?
• How can the station determine the success or failure of the

transmission?

• What can the station do if there is an access conflict?

​

12.162

ALOHA

• ALOHA, the earliest random access method, was developed at the University of Hawaii in early 1970.

​

• It was designed for a radio (wireless) LAN, but it can be used on any shared medium.

​

• It is obvious that there are potential collisions in this arrangement.

​

• The medium is shared between the stations. When a station sends data, another station may attempt to do so at the same time.

​

• The data from the two stations collide and become garbled.

ALOHA Network

12.164

Pure ALOHA

​

• The original ALOHA protocol is called pure ALOHA.

​

• This is a simple but elegant protocol.

​

• The idea is that each station sends a frame whenever it has a frame to send (multiple access).
• However, since there is only one channel to share, there is the possibility of collision between frames from different stations.

​

12.165

• The pure ALOHA protocol relies on acknowledgments from the receiver. When a station sends a frame, it expects the receiver to send an acknowledgment. If the acknowledgment does not arrive after a time-out period, the station assumes that the frame (or the acknowledgment) has been destroyed and resends the frame.
• A collision involves two or more stations. If all these stations try to resend their frames after the time-out, the frames will collide again.
• Pure ALOHA dictates that when the time-out period passes, each station waits a random amount of time before resending its frame.
• The randomness will help avoid more collisions. We call this time the back-offtime T_B.
• If the first bit of a new frame overlaps with just the last bit of a frame almost finished, both the frames will be totally destroyed and both will have to be transmitted later.

​

​

12.166

Figure 12.2: Frames in a pure ALOHA network

Pure Aloha

12.168

Figure 12.3: Procedure for pure ALOHA protocol

12.169

Figure 12.4: Vulnerable time for pure ALOHA protocol

Vulnerable time:

Let us find the vulnerable time, the length of time in which there is a possibility of collision.

12.170

Throughput:

Let us call G the average number of frames generated by the system during one frame transmission time.

Then it can be proven that the average number of successfully transmitted frames for pure ALOHA is S = G x e^-2G. The maximum throughput S_max is 0.184, for G = 1/2.

​

12.171

Slotted ALOHA:

​

• Slotted ALOHA was invented to improve the efficiency of pure ALOHA.

​

• This is so because there is no rule that defines when the station can send.
• A station may send soon after another station has started or just before another station has finished.
• In slotted ALOHA we divide the time into slots of T_fr seconds and force the station to send only at the beginning of the time slot.
• Pure ALOHA has a vulnerable time of 2 x T_fr .

​

​

12.172

Figure 12.5: Frames in a slotted ALOHA network

Slotted ALOHA

12.174

Figure 12.6: Vulnerable time for slotted ALOHA protocol

Slotted ALOHA vulnerable time=T_fr

12.175

Throughput

It can be proven that the average number of successful transmissions for slotted ALOHA is S = G x e^-G.

The maximum throughput S_max is 0.368, when G = 1.

​

Pure ALOHA

• Any station can transmit the data at any time.
• The time is continuous and not globally synchronized.
• Vulnerable time in which collision may occur= 2*Tfr
• Probability of successful transmission of data packet is

G*e^-2G

• Maximum efficiency = 18.4 %
• Simplicity in implementation

Slotted ALOHA

1. Any station can transmit the data at the beginning of anytime slot.
2. The time is discrete and globally synchronize.
3. Vulnerable time in which collision may occur = Tfr
4. Probability of successful transmission of data packet.

= G * e ^-G

• Maximum efficiency = 36.8% occurs at G.
• It reduces the number of collisions to half and doubles the efficiency of pure aloha.

12.176

12.177

CSMA

• To minimize the chance of collision and, therefore, increase the performance, the CSMA method was developed.

​

• The chance of collision can be reduced if a station senses the medium before trying to use it.

​

• Carrier sense multiple access (CSMA) requires that each station first listen to the medium (or check the state of the medium) before sending.

​

• In other words, CSMA is based on the principle “sense before transmit” or “listen before talk.”

​

• CSMA can reduce the possibility of collision, but it cannot eliminate it.

12.178

Figure 12.7: Space/time model of a collision in CSMA

12.179

Figure 12.8: Vulnerable time in CSMA

Vulnerable Time

The vulnerable time for CSMA is the propagation time Tp. This is the time needed for a signal to propagate from one end of the medium to the other. When a station sends a frame and any other station tries to send a frame during this time, a collision will result.

12.180

Persistence Methods

​

What should a station do if the channel is busy?

What should a station do if the channel is idle?

​

Three methods have been devised to answer these questions:

• 1-persistent method
• nonpersistent method
• p-persistent method.
• O-p-persistent method.

​

​

12.181

Figure 12.9: Behavior of three persistence methods

12.182

1-Persistent CSMA:

• Before sending the data, the station first listens to the channel to see if anyone else is transmitting the data at the moment.
• If the channel is idle, the station transmits a frame.
• If busy, then it senses the transmission medium continuously until becomes idle.
• Since the station transmits the frame with the probability of 1 when the carrier or channel is idle, this scheme of CSMA is called l-persistent CSMA.
• The l-persistent method is simple and straightforward. In this method, after the station finds the line idle, it sends its frame immediately (with probability 1).
• The propagation delay has an important effect on the performance of the protocol.
• The longer the propagation delay, the more important this effect becomes, and the worse the performance of the protocol.

​

​

12.183

Non-persistent CSMA

​

• Before sending, a station senses the channel. If no one else is sending the station begins doing so itself.
• However, if the channel is already in use, the station does not continually sense it for the purpose of seizing it immediately upon detecting the end of the previous transmission.
• Instead, it waits a random period of time and then repeats the algorithm. Consequently, the algorithm leads to better channel but longer delays than 1-persistent CSMA
• In the nonpersistent method, a station that has a frame to send senses the line.

If the line is idle, it sends immediately.

If the line is not idle, it waits a random amount of time and then senses the line again.

​

​

P-Persistent CSMA

• It applies to slotted channels
• When station becomes ready to send, it senses the channel.
• If it is idle, it transmits with probability P.
• With a probability Q=1-P. It defers until the next slot.
• If that slot is also idle, it either transmits or defers again with probabilities P and Q.
• This process is repeated until either the frame has been transmitted or another station has begun transmitting.
• If the station initially senses the channel busy. It waits until the next slot and applies the above algorithm.
• O-Persistent CSMA :
• Each node is assigned a transmission order by a supervisory node.

12.184

12.185

Figure 12.10: Flow diagram for three persistence methods

12.186

CSMA

• Principle of CSMA: “sense before transmit” or “listen before talk”.
• Carrier busy = transmission is taking place.
• Carrier idle= no transmission currently taking place.
• The CSMA method does not specify the procedure following a collision.
• Carrier sense multiple access with collision detection (CSMA/CD) augments the algorithm to handle the collision.
• In this method, a station monitors the medium after it sends a frame to see if the transmission was successful.
• If so, the station is finished.
• If, however, there is a collision, the frame is sent again.

12.187

CSMA/CD:

• If two stations sense the channel to be idle and begin transmitting simultaneously, then will both detect the collision almost immediately.
• Rather than finish transmitting their frames, which are irretrievably grabbled anyway, they should abruptly stop transmitting as soon as the collision is detected.
• Quickly terminating damaged frames saves time and bandwidth.
• This protocol, known as CSMA/CD is widely used on LANs in the MAC sublayer.
• Access method used by ethernet: CSMA/CD

To better understand CSMA/CD, let us look at the first bits transmitted by the two stations involved in the collision.

​

1. The Carrier Sense Multiple Access/ Collision Detection protocol is used to detect a collision in the media access control (MAC) layer.
2. Once the collision was detected, the CSMA/CD immediately stopped the transmission by sending the signal so that the sender does not waste all the time to send the data packet.
3. Suppose a collision is detected from each station while broadcasting the packets. In that case, the CSMA/CD immediately sends a jam signal to stop transmission and waits for a random time context before transmitting another data packet.
4. If the channel is found free, it immediately sends the data and returns it.

12.188

1. Advantages of CSMA/CD:
1. It is used for collision detection on a shared channel within a very short time.
2. CSMA/CD is better than CSMA for collision detection.
3. CSMA/CD is used to avoid any form of waste transmission.
4. When necessary, it is used to use or share the same amount of bandwidth at each station.
5. It has lower CSMA/CD overhead as compared to the CSMA /CA.

​

1. Disadvantage of CSMA/CD
1. It is not suitable for long-distance networks because as the distance increases, CSMA/CD efficiency decreases.
2. It can detect collision only up to 2500 meters, and beyond this range, it cannot detect collisions.
3. When multiple devices are added to a CSMA/CD, collision detection performance is reduced.

​

12.189

12.190

Figure 12.11: Collision of the first bits in CSMA/CD

12.191

At time t1, station A has executed its persistence procedure and starts sending the bits of its frame.

At time t2, station C has not yet sensed the first bit sent by A. Station C executes its persistence procedure and starts sending the bits in its frame, which propagate both to the left and to the right.

The collision occurs sometime after time t2' Station C detects a collision at time t3 when it receives the first bit of A's frame.

Station C immediately (or after a short time, but we assume immediately) aborts transmission.

Station A detects collision at time t4 when it receives the first bit of C's frame; it also immediately aborts transmission.

​

12.192

Figure 12.12: Collision and abortion in CSMA/CD

Time durations for the two transmissions, in a complete graph

12.193

Figure 12.13: Flow diagram for the CSMA/CD

12.194

Figure 12.14: Energy level during transmission, idleness, or collision

12.195

12.1.4 CSMA/CA

Carrier sense multiple access with collision avoidance (CSMA/CA) was invented for wireless networks.

​

Collisions are avoided through the use of CSMA/CA’s three strategies:

• Interframe space
• Contention window
• Acknowledgments.

​

CSMA/CA

• CSMA/CA stands for Carrier Sense Multiple Access with Collision Avoidance.
• It means that it is a network protocol that uses to avoid a collision rather than allowing it to occur, and it does not deal with the recovery of packets after a collision.
• It is similar to the CSMA CD protocol that operates in the media access control layer. In CSMA CA, whenever a station sends a data frame to a channel, it checks whether it is in use.
• If the shared channel is busy, the station waits until the channel enters idle mode. Hence, we can say that it reduces the chances of collisions and makes better use of the medium to send data packets more efficiently.

​

12.196

Advantages of CSMA/CA:

1. When the size of data packets is large, the chances of collision in CSMA/CA is less.
2. It controls the data packets and sends the data when the receiver wants to send them.
3. It is used to prevent collision rather than collision detection on the shared channel.
4. CSMA/CA avoids wasted transmission of data over the channel.
5. It is best suited for wireless transmission in a network.
6. It avoids unnecessary data traffic on the network with the help of the RTS/ CTS extension.

Disadvantage of CSMA/CA

1. Sometime CSMA/CA takes much waiting time as usual to transmit the data packet.
2. It consumes more bandwidth by each station.
3. Its efficiency is less than a CSMA/CD.

​

12.197

12.198

Interframe Space (IFS).

​

First, collisions are avoided by deferring transmission even if the channel is found idle. When an idle channel is found, the station does not send immediately.

​

It waits for a period of time called the interframe space or IFS.

​

Even though the channel may appear idle when it is sensed, a distant station may have already started transmitting. The distant station's signal has not yet reached this station.

12.199

The IFS time allows the front of the transmitted signal by the distant station to reach this station.

​

After waiting an IFS time, if the channel is still idle, the station can send, but it still needs to wait a time equal to the contention window.

​

The IFS variable can also be used to prioritize stations or frame types.

​

For example, a station that is assigned a shorter IFS has a higher priority.

12.200

Contention Window

​

The contention window is an amount of time divided into slots.

A station that is ready to send chooses a random number of slots as its wait time.

The number of slots in the window changes according to the binary exponential backoff strategy.

This means that it is set to one slot the first time and then doubles each time the station cannot detect an idle channel after the IFS time.

12.201

Acknowledgment

​

With all these precautions, there still may be a collision resulting in destroyed data.

​

In addition, the data may be corrupted during the transmission.

​

The positive acknowledgment and the time-out timer can help guarantee that the receiver has received the frame.

12.202

Figure 12.15: Flow diagram for CSMA/CA

12.203

Figure 12.16: Contention window

12.204

Figure 12.17: CMACA and NAV

CSMA/CD

• CSMA/CD means Carrier Sense Multiple Access and Collision Detection
• It is the type of CSMA to detect the collision on a shared channel.
• It is the collision detection protocol
• It is used in 802.3 Ethernet network cable.
• It works in wired networks.
• It is effective after collision detection on a network.
• Whenever a data packet conflicts in a shared channel, it resends the data frame.
• It minimizes the recovery time.
• The efficiency of CSMA/CD is high as compared to CSMA.
• It is more popular than the CSMA/CA protocol.

CSMA/CA

1. CSMA/CA means Carrier Sense Multiple Access and Collision Avoidance

​

• It is the type of CSMA to avoid collision on a shared channel..
• It is the collision avoidance protocol.
• It is used in the 802.11 wireless network.

​

• It works in wireless networks
• It is effective before collision detection on a network.
• Whereas the CSMA/CA waits until the channel is busy and does not recover after a collision.
• It minimizes the risk of collision.
• The efficiency of CSMA/CA is similar to CSMA.
• It is less popular than CSMA/CD.

12.205

12.206

Collision During Handshaking

​

What happens if there is a collision during the time when RTS or CTS control frames are in transition, often called the handshaking period?

​

Two or more stations may try to send RTS frames at the same time. These control frames may collide.

​

However, because there is no mechanism for collision detection, the sender assumes there has been a collision if it has not received a CTS frame from the receiver.

​

The backoff strategy is employed, and the sender tries again.

12.207

Hidden-Station Problem

​

The solution to the hidden station problem is the use of the handshake frames (RTS and CTS).

​

Figure also shows that the RTS message from B reaches A, but not C.

​

However, because both B and C are within the range of A, the CTS message, which contains the duration of data transmission from B to A, reaches C.

​

Station C knows that some hidden station is using the channel and refrains from transmitting until that duration

is over.

12.208

CSMA/CA and Wireless Networks

​

CSMA/CA was mostly intended for use in wireless networks.

​

The procedure described above, however, is not sophisticated enough to handle some particular issues related to wireless networks, such as hidden terminals or exposed terminals.

12.209

12-2 CONTROLLED ACCESS

​

In controlled access, the stations consult one another to find which station has the right to send.

​

A station cannot send unless it has been authorized by other stations.

​

We discuss three controlled-access methods.

12.210

12.2.1 Reservation

• In the reservation method, a station needs to make a reservation before sending data.

​

• Time is divided into intervals. In each interval, a reservation frame precedes the data frames sent in that interval.
• If there are N stations in the system, there are exactly N reservation mini slots in the reservation frame.
• Each mini slot belongs to a station.
• When a station needs to send a data frame, it makes a reservation in its own mini slot.
• The stations that have made reservation can send their data frames after reservation frame.

12.211

Figure 12.18: Reservation access method

12.212

12.2.2 Polling

• Polling works with topologies in which one device is designated as a primary station and the other devices are secondary stations.
• The polling protocol requires one of the nodes to be designated as a Master node (primary station)
• The master node polls each of the nodes in a round-robin fashion.
• In particular , The master node first sends a message to node 1, saying that it (node 1) can transmit up to some maximum number of frames.
• After node 1 transmit some frames , the master node tells node 2 it (node 2) can transmit up to the maximum number of frames.
• The master node can determine when a node has finished sending its frames by observing the lack of a signal on the channel

​

1. The procedure continues in this manner, with the master node polling each of the nodes in a cyclic manner.
2. The polling protocol eliminates the collision
3. This allows polling to achieve higher efficiency
4. The first drawback is that the protocol introduces a polling delay-the amount of time required to notify a node that it can transmit.
5. The second drawback which is potentially more serious , is that if the master node fails, the entire channel becomes inoperative.
6. Poll Functions:

Poll function: If the primary wants to receive data, it asks the secondaries if they have anything to send.

Select Function:

If the primary wants to send data, it tells the secondary to get ready to receive.

12.213

12.214

Figure 12.19: Select and poll functions in polling-access method

12.215

12.2.3 Token Passing

• In the token-passing method, the stations in a network are organized in a logical ring.

​

• In other words, for each station, there is a predecessor and a successor.

​

• The predecessor is the station which is logically before the station in the ring; the successor is the station which is after the station in the ring.
• There is no master node
• A small, special-purpose frames known as a token is exchanged among the nodes in some fixed order.

​

1. If a node does have frames to transmit when it receives the token, it sends up to a maximum number of frames and then forwards the token to the next node.
2. Token passing is decentralized and highly efficient. But it has problems as well.
3. For example, the failure of one node can crash the entire channel or if a node accidentally neglects to release token, then some recovery procedure must be invoked to get the token back in circulation.
4. Performance of Token Passing:

S= 1/1+a/N : for a<1

S = 1/ (a(1+1/N) : for a>1

a = Tp/Tt

S= Throughput N= No of stations Tp= Propagation Delay Tt= Transmission delay

12.216

Token Ring

Predecessor : Station which is logically before the station in Ring.

Successor : Station which is logically after the station in Ring.

Token :

A special packet , which circulates in Ring.

Possession of Token gives right to station of accessing Link and sending Data

12.218

Figure 12.20: Logical ring and physical topology in token-passing

access method

12.219

12-3 CHANNELIZATION

Channelization (or channel partition, as it is sometimes called) is a multiple-access method in which the available bandwidth of a link is shared in time, frequency, or through code, among different stations.

​

In this section, we discuss three protocols:

• FDMA
• TDMA
• CDMA.

12.220

12.3.1 FDMA

In frequency-division multiple access (FDMA), the available bandwidth is divided into frequency bands.

​

Each station is allocated a band to send its data. In other words, each band is reserved for a specific station, and it belongs to the station all the time.

​

Each station also uses a bandpass filter to confine the transmitter frequencies.

12.221

Figure 12.21: Frequency-division multiple access (FDMA)

12.222

12.3.2 TDMA

In time-division multiple access (TDMA), the stations share the bandwidth of the channel in time.

​

Each station is allocated a time slot during which it can send data.

​

Each station transmits its data in its assigned time slot. Figure shows the idea behind TDMA.

12.223

Figure 12.22: Time-division multiple access (TDMA)

12.224

12.3.3 CDMA

Code-division multiple access (CDMA) was conceived several decades ago.

​

Recent advances in electronic technology have finally made its implementation possible.

​

CDMA differs from FDMA in that only one channel occupies the entire bandwidth of the link.

​

It differs from TDMA in that all stations can send data simultaneously; there is no timesharing.

12.225

Figure 12.23: Simple idea of communication with code

12.226

Figure 12.24: Chip sequences

12.227

Figure 12.25: Data representation in CDMA

12.228

Figure 12.26: Sharing channel in CDMA

12.229

Figure 12.27: Digital signal created by four stations in CDMA