Data Communication and Computer Networks unit 2

dccn

1. UNIT -II
Data link layer
Data link layer: Design issues, framing, Error detection and correction.
Elementary data link protocols: simplex protocol, A simplex stop and wait
protocol for an error-free channel, A simplex stop and wait protocol for noisy
channel.
Sliding Window protocols: A one-bit sliding window protocol, A protocol using
Go-Back-N, A protocol using Selective Repeat, Example data link protocols.
Medium Access sub layer: The channel allocation problem, Multiple access
protocols: ALOHA, Carrier sense multiple access protocols, collision free protocols.
Wireless LANs, Data link layer switching.

2. Introdution of Data link layer
Data-link layer is the second layer after the physical layer
This layer is responsible for the error-free transfer of data frames, over the
physical layer.
The data link layer is divided into two sub-layers :
1. Logical Link Control Sub-layer (LLC) –
Provides the logic for the data link, Thus it controls the synchronization, flow
control, and error checking functions of the data link layer. Functions are –
(i) Error Recovery.
(ii) It performs the flow control operations.
(iii) User addressing.

3. 2. Media Access Control Sub-layer (MAC)
It controls the flow and multiplexing for transmission medium.
Transmission of data packets is controlled by this layer. This layer is responsible
for sending the data over the network interface card.
Functions are –
(i) To perform the control of access to media.
(ii) It performs the unique addressing to stations directly connected to LAN.
(iii) Detection of errors.

4. Design issues(functions) with data link layer are :
1.Services provided to the network layer –
The data link layer act as a service interface to the network layer. The principle service is
transferring data from network layer on sending machine to the network layer on
destination machine. This transfer also takes place via DLL (Data link-layer).
Types of Services
The services are of three types −
•Unacknowledged connectionless service− Sender sends message, receiver is
receiving messages without any acknowledgement both nodes are using
connectionless services.
•Acknowledged connectionless service− Sender sends the message to
receiver, when receiver the message it sends acknowledgement to sender that it
receives the message with connectionless services.
•Acknowledged connection -oriented service− Both sender and receiver are
using connection oriented services, and communication is acknowledged base
communication between the two nodes.

5. 2. Frame synchronization –
The source machine sends data in the form of blocks called frames to the destination machine.
The starting and ending of each frame should be identified so that the frame can be recognized by
the destination machine.
The Frame contains the following −
•Frame Header
•Payload field for holding packet
•Frame Trailer
The following are the types of framing methods that are used in Data Link Layer −
•Byte-oriented framing
•Bit-oriented framing and character count
•The frame is diagrammatically shown below −

6. 3. Flow control –
Flow control is done to prevent the flow of data frame at the receiver end. The source
machine must not send data frames at a rate faster than the capacity of destination machine
to accept them.
Flow control allows the two nodes to communicate with each other and work at different
speeds. The data link layer monitors the flow control so that when a fast sender sends data,
a slow receiver can receive the data at the same speed. Because of this flow control
technique is used.
4. Error control –
Error control is done to prevent duplication of frames. The errors introduced during
transmission from source to destination machines must be detected and correctedat the
destination machine.
Error detection: Errors can be introduced by signal attenuation and noise. Data Link
Layer protocol provides a mechanism to detect one or more errors. This is achieved by
adding error detection bits in the frame and then receiving node can perform an error
check.
Error correction: Error correction is similar to the Error detection, except that receiving
node not only detects the errors but also determine where the errors have occurred in the
frame.

7. FRAMING
Framing is function of Data Link Layer that is used to separate message from
sender to receiver or simply from all other messages to all other destinations just by
adding sender address and receiver address.
The receiver address is simply used to represent where message is to go and
sender address is used to help recipient to acknowledge receipt.
Framing is simply point-to-point connection among two computers or devices that
consists wire in which data is transferred as stream of bits. However, all of these
bits should be framed into visible blocks of information.
Methods of Framing :
There are basically four methods of framing , used to find the start and end
frame.

8. 1. Character Count
2. Flag Byte with Character Stuffing(Byte stuffing)
3. Starting and Ending Flags, with Bit Stuffing
4. Encoding Violations
1. Character Count
The first framing method uses a field in the header to specify the number of
characters in the frame. When the data link layer at the destination sees the
character count, it knows how many characters follow and hence where the end of
the frame is.
The trouble with this algorithm is that the count can be garbled by a transmission
error.

10. 2. Flag Byte with Character Stuffing(Byte stuffing)
Byte -Stuffing− A byte is stuffed in the message to differentiate from the
delimiter. Character stuffing is also known as byte stuffing or character-oriented
framing and is same as that of bit stuffing but byte stuffing actually operates on
bytes.
Ifthepatternoftheflagbyteispresentinthemessagebyte,thereshouldbea
strategysothatthereceiverdoesnotconsiderthepatternastheendoftheframe.
Incharacter–orientedprotocol,themechanismadoptedisbytestuffing.
Inbytestuffing,aspecialbytecalledtheescapecharacter(ESC)isstuffedbefore
everybyteinthemessagewiththesamepatternastheflagbyte.IftheESC
sequenceisfoundinthemessagebyte,thenanotherESCbyteisstuffedbeforeit.

12. 3. Starting and Ending Flags, with Bit Stuffing:
Bit -Stuffing− A pattern of bits of arbitrary length is stuffed in the message to
differentiate from the delimiter. This is also called bit -oriented framing.
•FrameHeader−Itcontainsthesourceandthedestinationaddressesofthe
frame.
•Payloadfield−Itcontainsthemessagetobedelivered.
•Trailer−Itcontainstheerrordetectionanderrorcorrectionbits.
•Flags−Abitpatternthatdefinesthebeginningandendbitsinaframe.Itis
generallyof8-bits.Mostprotocolsusethe8-bitpattern01111110asflag.

14. 4.Physical layer coding violations method
Physical layer coding violations method of framing is only applicable to networks
in which the encoding on the physical medium contains some redundancy.
Some LANs encode each bit of data by using two physical bits that Manchester
coding uses.
Here, Bit 1 is encoded into a high-low (10) pair and Bit 0 is encoded into a low-
high (01) pair.
The scheme means that every data bit has a transition in the middle, making it
easy for the receiver to locate the bit boundaries.
The combinations high-high and low-low are not used for data but are used for
delimiting frames in some protocols.
As a final note on framing, many data link protocols use combination of a
character count with one of the other methods for extra safety. When a frame
arrives, the count field is used to locate the end of the frame. Only if the
appropriate delimiter is present at that position and the checksum is correct is the
frame accepted as valid. Otherwise, the input stream is scanned for the next
delimiter

15. Error Detection
Error
A condition when the receiver’s information does not matches with the sender’s
information. During transmission, digital signals suffer from noise that can
introduce errors in the binary bits travelling from sender to receiver. That means a
0 bit may change to 1 or a 1 bit may change to 0.
Error Detecting Codes (Implemented either at Data link layer or Transport
Layer of OSI Model) Whenever a message is transmitted, it may get
scrambled by noise or data may get corrupted.
To avoid this, we use error-detecting codes which are additional data added
to a given digital message to help us detect if any error has occurred during
transmission of the message.
Basic approach used for error detection is the use of redundancy bits, where
additional bits are added to facilitate detection of errors.

16. Types of error:
There may be three types of errors:
1.Single bit error: In a frame, there is only one bit, anywhere though, which is
corrupt.
2.Multiple bits error:Frame is received with more than one bits in corrupted
state.
3.Burst error: Frame contains more than1 consecutive bits corrupted.

17. Some popular techniques for error detection are:
1. Simple Parity check
2. Two-dimensional Parity check
3. Checksum
4. Cyclic redundancy check (CRC)
1.Simple Parity check
SingleParitycheckingisthesimplemechanismandinexpensivetodetectthe
errors.
Inthistechnique,aredundantbit(either0or1)isalsoknownasaparitybitwhich
isappendedattheendofthedataunitsothatthenumberof1sbecomeseven.
Therefore,thetotalnumberoftransmittedbitswouldbe9bits.
Ifthenumberof1sbitsisodd,thenparitybit1isappendedandifthenumberof
1sbitsiseven,thenparitybit0isappendedattheendofthedataunit.

18. Atthereceivingend,theparitybitiscalculatedfromthereceiveddatabitsand
comparedwiththereceivedparitybit.
Thistechniquegeneratesthetotalnumberof1seven,soitisknownaseven-
paritychecking.
Then, following cases are possible-
•If total number of 1’s is even and even parity is used, then receiver assumes that
no error occurred.
•If total number of 1’s is even and odd parity is used, then receiver assumes
that error occurred.
•If total number of 1’s is odd and odd parity is used, then receiver assumes that no
error occurred.
•If total number of 1’s is odd and even parity is used, then receiver assumes
that error occurred.

19. Parity Check Example-
Consider the data unit to be transmitted is 1001001 and even parity is used
At Sender Side-
Total number of 1’s in the data unit is counted.
Total number of 1’s in the data unit = 3.
Clearly, even parity is used and total number of 1’s is odd.
So, parity bit = 1 is added to the data unit to make total number of 1’s even.
Then, the code word 10010011 is transmitted to the receiver.

20. At Receiver Side-
After receiving the code word, total number of 1’s in the code word is counted.
Consider receiver receives the correct code word = 10010011.
Even parity is used and total number of 1’s is even.
So, receiver assumes that no error occurred in the data during the transmission.

21. Advantage-
This technique is guaranteed to detect an odd number of bit errors (one, three, five
and so on).
If odd number of bits flip during transmission, then receiver can detect by
counting the number of 1’s.
DrawbacksOfSingleParityChecking
Itcanonlydetectsingle-biterrorswhichareveryrare.
Iftwobitsareinterchanged,thenitcannotdetecttheerrors.

22. 2. Two-dimensional Parity check
Performance can be improved by usingTwo-Dimensional Parity Checkwhich
organizes the data in the form of a table.
Parity check bits are calculated for each row, which is equivalent to a simple
parity check bit.
Parity check bits are also calculated for all columns, then both are sent along with
the data. At the receiving end these are compared with the parity bits calculated on
the received data.
Parity check bits are calculated for each row, which is equivalent to a simple
parity check bit. Parity check bits are also calculated for all columns, then both are
sent along with the data. At the receiving end these are compared with the parity
bits calculated on the received data.

23. DrawbacksOf2DParityCheck
Iftwobitsinonedataunitarecorruptedandtwobitsexactlythesamepositionin
anotherdataunitarealsocorrupted,then2DParitycheckerwillnotbeableto
detecttheerror.
Thistechniquecannotbeusedtodetectthe4-biterrorsormoreinsomecases.
3. Checksum
In checksum error detection scheme, the data is divided into k segments each of m
bits.
In the sender’s end the segments are added using 1’s complement arithmetic to get
the sum. The sum is complemented to get the checksum.
The checksum segment is sent along with the data segments.
At the receiver’s end, all received segments are added using 1’s complement
arithmetic to get the sum. The sum is complemented.
If the result is zero, the received data is accepted; otherwise discarded.

25. 4. Cyclic redundancy check (CRC)
Unlike checksum scheme, which is based on addition, CRC is based on binary
division.
In CRC, a sequence of redundant bits, called cyclic redundancy check bits, are
appended to the end of data unit so that the resulting data unit becomes exactly
divisible by a second, predetermined binary number.
At the destination, the incoming data unit is divided by the same number. If at this
step there is no remainder, the data unit is assumed to be correct and is therefore
accepted.
A remainder indicates that the data unit has been damaged in transit and therefore
must be rejected.

27. •The generator polynomial G(x) = x
3
+ 1 is encoded as 1001.
•Clearly, the generator polynomial consists of 4 bits.
•So, a string of 3 zeroes is appended to the bit stream to be transmitted.
•The resulting bit stream is 1010000000.
At sender side CRC=011
•The code word to be transmitted is obtained by replacing the last 3 zeroes of
10011101000with the CRC.
•Thus, the code word transmitted to the receiver = 1010000011.
Now, At receiver side:
•Receiver receives the bit stream = 1010000011.
•Receiver performs the binary division with the same generator polynomial .
From here,
•The remainder obtained on division is a zero value.
•This indicates to the receiver that is no error occurred in the data during the
transmission.
•Therefore, receiver accept the data.

28. Error Correction
Error Correction codes are used to detect and correct the errors when data is
transmitted from the sender to the receiver.
Error Correction can be handled in two ways:
•Backward Error CorrectionWhen the receiver detects an error in the data
received, it requests back the sender to retransmit the data unit.
•Forward Error CorrectionWhen the receiver detects some error in the data
received, it executes error-correcting code, which helps it to auto-recover and to
correct some kinds of errors.

29. A single additional bit can detect the error, but cannot correct it.
For correcting the errors, one has to know the exact position of the error. For
example, If we want to calculate a single-bit error, the error correction code will
determine which one of seven bits is in error. To achieve this, we have to add
some additional redundant bits.
Suppose r is the number of redundant bits and d is the total number of the data
bits. The number of redundant bits r can be calculated by using the formula:
2r >=d+r+1
The value of r is calculated by using the above formula. For example, if the value
of d is 4, then the possible smallest value that satisfies the above relation would be
3.

30. Error Correction Techniques:
1.Hamming Code:
•Paritybits:Thebitwhichisappendedtotheoriginaldataofbinarybitssothat
thetotalnumberof1sisevenorodd.
•Evenparity:Tocheckforevenparity,ifthetotalnumberof1siseven,thenthe
valueoftheparitybitis0.Ifthetotalnumberof1soccurrencesisodd,thenthe
valueoftheparitybitis1.
•OddParity:Tocheckforoddparity,ifthetotalnumberof1siseven,thenthe
valueofparitybitis1.Ifthetotalnumberof1sisodd,thenthevalueofparitybit
is0.

31. •Relationship b/w Error position & binary number.
Let'sunderstandtheconceptofHammingcodethroughanexample:
Supposetheoriginaldatais1010whichistobesent.
Totalnumberofdatabits'd'=4
Numberofredundantbitsr:2
r
>=d+r+1
2
r
>=4+r+1Therefore,thevalueofris3thatsatisfiestheaboverelation
.Totalnumberofbits=d+r=4+3=7;

32. Determiningthepositionoftheredundantbits
•Thenumberofredundantbitsis3.Thethreebitsarerepresentedbyr1,
r2,r4.Thepositionoftheredundantbitsiscalculatedwithcorrespondsto
theraisedpowerof2.Therefore,theircorrespondingpositionsare1,2
1
,
2
2
.
1.Thepositionofr1=1
2.Thepositionofr2=2
3.Thepositionofr4=4
•RepresentationofDataontheadditionofparitybits:
DeterminingtheParitybits
Determiningther1bit
Ther1bitiscalculatedbyperformingaparitycheckonthebit
positionswhosebinaryrepresentationincludes1inthefirstposition.

33. We observe from the above figure that the bit positions that includes 1 in the
first position are 1, 3, 5, 7. Now, we perform the even-parity check at these bit
positions. The total number of 1 at these bit positions corresponding to r1
iseven, therefore, the value of the r1 bit is 0.
Determiningr2bit
Ther2bitiscalculatedbyperformingaparitycheckonthe
bitpositionswhosebinaryrepresentationincludes1inthe
secondposition.

34. We observe from the above figure that the bit positions that includes 1 in the
second position are2, 3, 6, 7. Now, we perform the even-parity check at these bit
positions. The total number of 1 at these bit positions corresponding to r2 isodd,
therefore, the value of the r2 bit is 1.
Determiningr4bit
Ther4bitiscalculatedbyperformingaparitycheckonthebitpositions
whosebinaryrepresentationincludes1inthethirdposition.

35. •We observe from the above figure that the bit positions that includes 1 in
the third position are4, 5, 6, 7. Now, we perform the even-parity check at
these bit positions. The total number of 1 at these bit positions
corresponding to r4 iseven, therefore, the value of the r4 bit is 0.
Data transferred is given below:
Suppose the 4
th
bit is changed from 0 to 1 at the receiving end, then parity
bits are recalculated.
R1bit
•Thebitpositionsofther1bitare1,3,5,7

36. •We observe from the above figure that the binary representation of r1 is
1100. Now, we perform the even-parity check, the total number of 1s
appearing in the r1 bit is an even number. Therefore, the value of r1 is 0.
R2bit
•Thebitpositionsofr2bitare2,3,6,7.
We observe from the above figure that the binary representation of r2 is 1001.
Now, we perform the even-parity check, the total number of 1s appearing in
the r2 bit is an even number. Therefore, the value of r2 is 0.

37. R4bit
•Thebitpositionsofr4bitare4,5,6,7.
Weobservefromtheabovefigurethatthebinaryrepresentationofr4is
1011.Now,weperformtheeven-paritycheck,thetotalnumberof1s
appearinginther4bitisanoddnumber.Therefore,thevalueofr4is1.
Thebinaryrepresentationofredundantbits,i.e.,r4r2r1is100,andits
correspondingdecimalvalueis4.Therefore,theerroroccursina4
th
bit
position.Thebitvaluemustbechangedfrom1to0tocorrecttheerror.

38. PROTOCOLS IN DATA LINK LAYER
Data link protocols can be broadly divided into two categories, depending on
whether the transmission channel is noiseless or noisy.

39. Elementary data link protocols
Elementary Data Link protocols are classified into three categories, as given below −
1. simplex protocol (or) Unrestricted simplex protocol
2. A simplex stop and wait protocol for an error-free channel
3. A simplex stop and wait protocol for noisy channel.
1. simplex protocol (or) Unrestricted simplex protocol
It is very simple protocol.Thesender sends a sequence of frames without even thinking
about the receiver.
Data is transmitted in one direction only.
Both sender & receiver always ready.
Processing time can be ignored.
Infinite buffer space is available at sender side and receiver side.
No errors are occurring that is no damage frames and no lost frames.
which we will nickname ‘‘Utopia,’’ .
The utopia protocol is unrealistic because it does not handle either flow control or
error correction .

40. The data link layer at the sender site gets data from its network layer, makes a frame
out of the data, and sends it. The data link layer(receiver site) receives a frame from its
physical layer, extracts data from the frame, and convey the data to its network layer.
The data link layers of the sender and receiver provide communication/transmission
services for their network layers. The data link layers utilization the services provided by
their physical layers for the physical transmission of bits.

42. Advantages of simplex protocol:
1.It is simple protocol
2.It is highly unrealistic protocol
Disadvantages:
1. Flooding : it means continuous data transmission may cause the
congestion(sender transmit the frames faster than the receiver can accept, it takes
more time) in the network, that is your network may get highly loaded in this
transmission process. Overcome this drawback we are going to see simplex stop-
and-wait protocol.

43. 2. A simplex stop and wait protocol for an error-free channel
Sender:
Rule 1) Send one data packet at a time.
Rule 2) Send the next packet only after receiving acknowledgement for the previous.
Receiver:
Rule 1) Send acknowledgement after receiving and consuming a data packet.
Rule 2) After consuming packet acknowledgement need to be sent (Flow Control)
It is still very simple.
We still have unidirectional communication for data frames, but auxiliary ACK frames
travel from the other direction.
The receiver has finite buffer capacity.
In this, Communication is error free.
The receiver has a finite processing speed, means the receiver is also restricted by
specific speed limit.

45. Problems :
1.Problems due to Lost Data
Sender waits for ACK for an infinite amount of time.
Receiver waits for data for an infinite amount of time.

46. 2. Problem due to Lost Acknowledgement:
Sender waits for ACK for infinite amount of time.
Here ACK is lost due to some problems in the network, so the sender will be
waiting for infinite amount of time.
Here there is no chance for sender to receive a ACK and there is no chance
for sender to send the next frame.


47. 3.Delayed Acknowledgement/Data:After a timeout on the sender side, a long-
delayed acknowledgement might be wrongly considered as acknowledgement of
some other recent packet.
3. A simplex stop and wait protocol for noisy channel(Stop and Wait for
ARQ (Automatic Repeat Request))
The above 3 problems are resolved by Stop and Wait for ARQ (Automatic Repeat
Request).
Working of Stop and Waitfor ARQ:
1)Sender A sends a data frame or packet with sequence number 0.
2)Receiver B, after receiving the data frame, sends an acknowledgement with
sequence number 0 (the sequence number of the next expected data frame or
packet)

48. ItisalsocalledaspositiveACKwithretransmition(PAR)orAtomaticrepeat
requestprotocol(ARQ).
Datatransferisonlyinonedirection.
considerseparatesenderandreceiver.
finiteprocessingcapacityandspeedatthereceiver.
sinceitisanoisychannel,errorsindataframesoracknowledgementframesare
expected.
Everyframehasauniquesequencenumber.
Afteraframehasbeentransmitted,thetimerisstartedforafinitetime.Beforethe
timerexpires,iftheacknowledgementisnotreceived,theframegets
retransmitted.
whentheacknowledgementgetscorruptedorsentdataframesgetsdamaged,how
longthesendershouldwaittotransmitthenextframeisinfinite.

49. The Simplex Protocol for Noisy Channel is diagrammatically represented as
follows −

50. Advantages:
1.Handle lost frames by using timer.
Disadvantages:
1.One frame at a time
2.If the interval is too short unneeded retransmissions occur,
3.If it is too long bandwidth is wasted as the sender waits too long before doing a
retransmission.

51. What is ARQ (Automatic Repeat Request)?
•ARQ stands for Automatic Repeat Request also known as Automatic Repeat
Query.
•ARQ is an error-control strategy used in a two-way communication system.
•It is a group of error-control protocols to achieve reliable data transmission over
an unreliable source or service.
•These protocols reside in Transport Layer and Data Link Layer of the OSI(Open
System Interconnection) model .
•These protocols are responsible for automatic retransmission of packets that are
found to be corrupted or lost during the transmission process.

52. Working Principle of ARQ
The main function of these protocols is, the sender receives an
acknowledgement from the receiver end implying that the frame or
packet is received correctly before a timeout occurs, timeout is a
specific time period within which the acknowledgement has to be sent
by the receiver to the sender.
If a timeout occurs: the sender does not receive the acknowledgement
before the specified time, it is implied that the frame or packet has been
corrupt or lost during the transmission. Accordingly, the sender
retransmits the packet and these protocols ensure that this process is
repeated until the correct packet is transmitted.

53. Sliding Window protocols
Needofslidingwindowprotocol:
Slidingwindowprotocolsaredatalinklayerprotocolsforreliableand
sequentialdeliveryofdataframes.Theslidingwindowisalsousedin
TransmissionControlProtocol.
Inthisprotocol,multipleframescanbesentbyasenderatatimebefore
receivinganacknowledgmentfromthereceiver.Thetermslidingwindow
referstotheimaginaryboxestoholdframes.Slidingwindowmethodisalso
knownaswindowing.
Numberofframestobesentisbasedonwindowsize.So,heresenderand
receiverhaswindowsizebasedonwindowsizetheno.offramestobesent.
Inthisprotocols,eachframehassentfromthesequencenumber.Thesequence
numbersareusedtofindthemissingdatainthereceiverend.Thepurposeofthe
slidingwindowprotocolistoavoidduplicatedata,soitusesthesequence
number.

54. Example
Suppose that we have sender window and receiver window each of size 4. So
the sequence numbering of both the windows will be 0,1,2,3,0,1,2 and so on.
The following diagram shows the positions of the windows after sending the
frames and receiving acknowledgments.

55. Types of Sliding Window Protocols:
1.A one-bit sliding window protocol
2.A protocol using Go-Back-N
3.A protocol using Selective Repeat

56. 1.A one-bit sliding window protocol
•One bit sliding window protocol is based on the concept of sliding
window protocol. But here the window size is of 1 bit for both sides.
So, the sender transmits one frame at a time and waits for its ACK,
then transmit the next frame. It uses the concept of stop-and-wait
protocol.
One bit sliding window protocol is used for delivery of data frames.
Sender has sending window.
Receiver has receiving window.
Sending and receiving windows act as buffer storage.
Here size of windows size is 1.
One bit sliding window protocol usesStop and Wait.
Sender transmit a frame with sequence number.

57. Than sender wait for acknowledgment from the receiver.
Receiver send back an acknowledgement with sequence number.
If sequence number of acknowledgement matches with sequence
number of frame then Sender transmit the next frame, Else sender re-
transmit the previous frame.
Its bidirectional protocol.
This protocol provides for full –duplex communications. Hence, the
acknowledgment is attached along with the next data frame to be sent
that is called piggybacking(PiggybackingIs a bi-directional data
transmission technique)

58. Piggybacking:
The data frames to be transmitted additionally have an ACK
field, ACK field that is of a few bits length.
The ACK field contains the sequence number of the last frame
received without error.
If the sequence number matches with the sequence number of
the frame to be sent, then it is inferred that there is no error and
the frame is transmitted.
Otherwise , it is inferred that there is an error in the frame
and previous frame is retransmitted that is called
piggybacking.
Since this is a bi-directional protocol, the same algorithm
applies to both the communication parties.

59. Example
•Thefollowingdiagramdepictsascenariowithsequencenumbers0,1,2,3,0,1,2
andsoon.Itdepictstheslidingwindowsinthesendingandthereceivingstations
duringframetransmission.

60. Number of Sequence Numbers Required-
For any sliding window protocol to work without any problem,thefollowing
condition must besatisfied-
•Available Sequence Numbers >= Sender Window Size + Receiver Window Size
•Stop and wait ARQ is a one bit sliding window protocol where-
•Sender window size = 1
•Receiver window size = 1
•Minimum number of sequence numbers required= Sender Window Size +
Receiver Window Size
= 1 + 1= 2
Sequence number on acknowledgements help to solve the problem of delayed
acknowledgement.

61. 2.A protocol using Go-Back-N
Go-Back-N ARQ protocol is also known as Go-Back-N Automatic Repeat
Request. It is a data link layer protocol that uses a sliding window method. In this,
if any frame is corrupted, all subsequent frames have to be sent again.
The size of the sender window is N in this protocol. For example, Go-Back-8,
the size of the sender window, will be 8. The receiver window size is always 1.
If the receiver receives a corrupted frame, it cancels it. The receiver does not
accept a corrupted frame. When the timer expires, the sender sends the
correct frame again. The design of the Go-Back-N ARQ protocol is shown
below.

62. •Go-Back-N ARQ uses the concept of protocol pipelining i.ethe sender can send
multiple frames before receiving the ACK for the first frame.
•There are finite number of frames and the frames are numbered in a sequential
manner.
•The number of frames that can be sent depends on the window size of the sender.
•If the ACK of a frame is not received within a agreed upon the time period.all
frames in the current window are retransmitted.
•The size of the sending window determines the sequence number of the outbound
frames. Here N is the senders window size.
Example:
If the sending window size is 4 i.e2 power of 2(this 2 is the number of bits in the
sequence number), 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 is
00,01,10,11

64. Example 2
•a. First, the sender sends the first four frames in the window (here the window
size is 4).
b. Then, the receiver sends the acknowledgment for the 0th frame.

65. c. The receiver then slides the window over and sends the next frame in the queue.
d. Accordingly, the receiver sends the acknowledgement for the 1st frame, and
upon receiving that, the sender slides the window again and sends the next
frame. This process keeps on happening until all the frames are sent successfully.
Whenthetimerexpires,thesenderresendsalloutstandingframes.For
example,supposethesenderhasalreadysentframe6,butthetimerforframe
3 expires. This means that frame 3 has not been acknowledged; thesendergoes
backandsendsframes3,4,5,and6again.That is why theprotocoliscalled Go-
Back-NARQ.

66. ADVANTAGES
The sender can send MANY FRAMES at a time.
Timer can be set for agroupof frames.
Efficiency is more.
Waiting time is low.
We can alter the size of the sender window
DISADVANTAGES
Buffer requirement
Transmitter needs to store the last N packets
Scheme is inefficient when delay is large and data transmission rate is high
Unnecessary Retransmission of many error-free packets

67. 3. A protocol using Selective Repeat
Selective-repeat Automatic Repeat Request (ARQ) is one of the techniques where a data link layer
may deploy to control errors.
Techniques to control ARQ
Generally,therearethreetypesoftechniqueswhichcontroltheerrorsbyAutomaticRepeat
Request(ARQ)theyare−
•Stop-and-wait ARQ
•Go-Back-N ARQ
•Selective Repeat ARQ
Requirements for Error Control
Therearesomerequirementsforerrorcontrolmechanismsandtheyareasfollows−
•Errordetection−Thesenderandreceiver,oranymustascertainthatthereissomeerrorin
thetransit.
•PositiveACK−Wheneverareceiverreceivesacorrectframe,itshouldacknowledgeit.
•NegativeACK−Wheneverthereceiverreceivesadamagedframeoraduplicateframe,it
sendsaNACKbacktothesenderandsendermustretransmitthecorrectframe.
•Retransmission−Thesenderalwaysmaintainsaclockandsetsatimeoutperiod.Ifan
ACKofdata-framepreviouslytransmitteddoesnotarrivebeforethetimeout,thesender
retransmitstheframe,thinkingthattheframeorit’sACKislostintransit

68. Itisusedforerrordetectionandcontrolinthedatalinklayer.
Intheselectiverepeat,thesendersendsseveralframesspecifiedbyawindowsize
evenwithouttheneedtowaitforindividualacknowledgementfromthereceiver
asinGo-Back-NARQ.Inselectiverepeatprotocol,theretransmittedframeis
receivedoutofsequence.
InSelectiveRepeatARQonlythelostorerrorframesareretransmitted,whereas
correctframesarereceivedandbuffered.
Thereceiverwhilekeepingtrackofsequencenumbersbufferstheframesin
memoryandsendsNACKforonlyframeswhicharemissingordamaged.The
senderwillsend/retransmitapacketforwhichNACKisreceived.

70. Explanation
Step1−Frame0sendsfromsendertoreceiverandsettimer.
Step2−Withoutwaitingforacknowledgementfromthereceiveranotherframe,
Frame1issentbysenderbysettingthetimerforit.
Step3−Inthesamewayframe2isalsosenttothereceiverbysettingthetimer
withoutwaitingforpreviousacknowledgement.
Step4−WheneversenderreceivestheACK0fromreceiver,withintheframe0
timerthenitisclosedandsenttothenextframe,frame3.
Step5−wheneverthesenderreceivestheACK1fromthereceiver,withinthe
frame1timerthenitisclosedandsenttothenextframe,frame4.
Step6−Ifthesenderdoesn’treceivetheACK2fromthereceiverwithinthetime
slot,itdeclarestimeoutforframe2andresendstheframe2again,becauseit
thoughttheframe2maybelostordamaged.

71. Example data link protocols.
1.High-level Data Link Control (HDLC) protocol
It is derived from SDLC(Synchronous Data Link Control) earlier it was used
in IBM and it was standardized by ISO organization with some modifications
i.eHDLC protocol.
HDLC(High-Level Data Link Control) is a bit-oriented protocol that is used
for communication over thepoint-to-point and multipoint links.
This protocol implements the mechanism of ARQ(Automatic Repeat Request).
With the help of the HDLC protocol, full-duplex communication is possible.
HDLCis the most widely used protocol and offers reliability, efficiency, and a
high level of Flexibility. Because it provides both flow control and error
control using the techniques either selective repeat or go-back-N that is
depending on the network.

72. Types of HDLC Frames:
There are three types of HDLC frames. The type of frame is determined by the
control field of the frame −
I.Information frame:
I-frames or Information frames carry user data from the network layer. They
also include flow and error control information that is piggybacked on user data.
The first bit of control field of I-frame is 0.
II. Supervisory Frame:
S-frames or Supervisory frames do not contain information field. They are
used for flow and error control when piggybacking is not required. The first
two bits of control field of S-frame is 10.
The control field executes control functions such as acknowledgement of
frames, request for re-transmission, and requests for limited suspension of
frames being sent.

74. III. Unnumbered Frame
This control field format can also be used for control purposes. It can implement link
initialization, link disconnection and other link control services.
It may contain an information field, if required. The first two bits of control field of U-frame
is 11.
HDLC Frame Fields:
Flag−Itisan8-bitsequencethatmarksthebeginningandtheendoftheframe.Thebitpattern
oftheflagis01111110.
Address−Itcontainstheaddressofthereceiver.Iftheframeissentbytheprimarystation,it
containstheaddress(es)ofthesecondarystation(s).Ifitissentbythesecondarystation,it
containstheaddressoftheprimarystation.Theaddressfieldmaybefrom1bytetoseveral
bytes.

75. Control− It is 1 or 2 bytes containing flow and error control information. And it
decide how to control the transmission process. The field includes the commands,
responses and sequences numbers used to support the link's data flow
accountability.
Payload−Thiscarriesthedatafromthenetworklayer.Itslengthmayvaryfrom
onenetworktoanother.
FCS−Itisa2byteor4bytesframechecksequenceforerrordetection.The
standardcodeusedisCRC(cyclicredundancycode)
Advantages of HDLC:
1.This protocol uses bits to stuff flags occurring in the data.
2.This protocol is used for point-to-point as well as multipoint link access.
3.HDLC is one of the most common protocols of the data link layer.
4.HDLC is a bit-oriented protocol.
5.This protocol implements error control as well as flow control.

76. 2. Point to point protocol(PPP)
ThePPPstandsforPoint-to-Pointprotocol.Itisthemostcommonlyused
protocolforpoint-to-pointaccess.Supposetheuserwantstoaccesstheinternet
fromthehome,thePPPprotocolwillbeused.
Itisadatalinklayerprotocolthatresidesinthelayer2oftheOSImodel
Itisusedtoencapsulatethelayer3protocolsandalltheinformationavailablein
thepayloadinordertobetransmittedacrosstheseriallinks.ThePPPprotocolcan
beusedonsynchronouslinklikeISDNaswellasasynchronouslinklikedial-up.
Itismainlyusedforthecommunicationbetweenthetwodevices.

77. •Itisabyte-orientedprotocolasitprovidestheframesasacollectionofbytesor
characters.ItisaWAN(WideAreaNetwork)protocolasitrunsovertheinternet
linkwhichmeansbetweentworouters,internetiswidelyused.
ServicesprovidedbyPPP
•Itdefinestheformatofframesthroughwhichthetransmissionoccurs.
•Itdefinesthelinkestablishmentprocess.Ifuserestablishesalinkwithaserver,
then"howthislinkestablishes"isdonebythePPPprotocol.
•Itdefinesdataexchangeprocess,i.e.,howdatawillbeexchanged,therateofthe
exchange.
•ThemainfeatureofthePPPprotocolistheencapsulation.Itdefineshownetwork
layerdataandinformationinthepayloadareencapsulatedinthedatalinkframe.
•Itdefinestheauthenticationprocessbetweenthetwodevices.Theauthentication
betweenthetwodevices,handshakingandhowthepasswordwillbeexchanged
betweentwodevicesaredecidedbythePPPprotocol.
•Itdoesnotsupportflowcontrolmechanism.

78. FrameformatofPPPprotocol
•TheframeformatofPPPprotocolcontainsthefollowingfields:
•Flag:Theflagfieldisusedtoindicatethestartandendoftheframe.Theflag
fieldisa1-bytefieldthatappearsatthebeginningandtheendingoftheframe.
ThepatternoftheflagissimilartothebitpatterninHDLC,i.e.,01111110.
•Address:Itisa1-bytefieldthatcontainstheconstantvaluewhichis
11111111.These8onesrepresentabroadcastmessage.

79. Control:Itisa1-bytefieldwhichissetthroughtheconstantvalue,i.e.,
11000000.ItisnotarequiredfieldasPPPdoesnotsupporttheflowcontrolanda
verylimitederrorcontrolmechanism.Thecontrolfieldisamandatoryfieldwhere
protocolsupportsflowanderrorcontrolmechanism.
Protocol:Itisa1or2bytesfieldthatdefineswhatistobecarriedinthedata
field.Thedatacanbeauserdataorotherinformation.
Payload:Thepayloadfieldcarrieseitheruserdataorotherinformation.The
maximumlengthofthepayloadfieldis1500bytes.
FCS−Itisa2byteor4bytesframechecksequenceforerrordetection.The
standardcodeusedisCRC(cyclicredundancycode)

80. Medium Access Control sub layer(MACL)
About MACL:
MAC is a sublayer of the data link layer(DLL) in the seven layer OSI network
reference model.
MAC is responsible for the transmission of data packets to and from the
network interface card(NIC), and to and from another remotely shared
channel.
The basic function of MAC is to provide an addressing mechanism and
channel access. So that each node available on a network can communicate with
each other nodes available on the same or other networks.

81. The channel allocation problems
In a broadcast network, the single broadcast channel is to be allocated to one
transmitting user at a time. When multiple users use a shared network and want to
access the same network. Then channel allocation problem in computer networks
occurs.
So, to allocate the same channel between multiple users, some techniques are
used, which are called channel allocation techniques in computer networks.
Channel allocation is a process in which a single channel is divided and allotted
to multiple users in order to carry user specific tasks. There are user’s quantity
may vary every time the process takes place.

82. If there are N number of users and channel is divided into N equal-sized sub
channels, Each user is assigned one portion. If the number of users are small and
don’t vary at times, then Frequency Division Multiplexing(FDM) can be used as it
is a simple and efficient channel bandwidth allocating technique.
Channel allocation problem can be solved by two schemes:
1.Static Channel Allocation in LANs and MANs, and
2.Dynamic Channel Allocation.

83. 1.Static Channel Allocation in LANs and MANs
Instaticchannelallocationscheme,afixedportionofthefrequencychannelis
allottedtoeachuser.ForNcompetingusers,thebandwidthisdividedintoN
channelsusingfrequencydivisionmultiplexing(FDM)andtime-division
multiplexing(TDM),andeachportionisassignedtooneuser.
Inthesemethods,eitherafixedfrequencyorfixedtimeslotisallottedtoeach
user.
Staticchannelallocationisalsocalledfixedchannelallocation.Suchasa
telephonechannelamongmanyusersisareal-lifeexampleofstaticchannel
allocation.
Inthisallocationscheme,thereisnointerferencebetweentheuserssinceeach
userisassignedafixedchannel.However,itisnotsuitableincaseofalarge
numberofuserswithvariablebandwidthrequirements.

84. Advantages
•Itisparticularlysuitableforsituationswherethereareasmallnumberoffixedusershavinga
steadyflowofuniformnetworktraffic.
•Theallocationtechniqueissimpleandsotheadditionaloverheadofacomplexalgorithmneed
notbeincurred.
•Thereisnointerferencebetweentheuserssinceeachuserisassignedafixedchannelwhichis
notsharedwithothers
Disadvantages
•IfthevalueofNisverylarge,thebandwidthavailableforeachuserwillbeveryless.Thiswill
reducethethroughputiftheuserneedstosendalargevolumeofdataonceinawhile.
•Itisveryunlikelythatalltheuserswillbecommunicatingallthetime.However,sinceallof
themareallocatedfixedbandwidths,thebandwidthallocatedtonon-communicatinguserslies
wasted.
•IfthenumberofusersismorethanN,thensomeofthemwillbedeniedservice,evenifthere
areunusedfrequencies.

85. 2. Dynamic Channel Allocation in LANs and MANs
The technique in which channels are not permanently allocated to the users is
called dynamic channel allocation.In this technique, no fixed frequency or fixed
time slot is allotted to the user.
The allocation depends upon the traffic. If the traffic increases, more channels are
allocated, otherwise fewer channels are allocated to the users.
This technique optimizes bandwidth usage and provides fast data transmission.

86. The following are the assumptions in dynamic channel allocation:
1.Station Model:
The model consists of N independent stations (eg.Computers, pc, mobiles..etc), each with a
program or user that generates frames for transmission. Stations are sometimes called terminals.
Once a frame has been generated , the station is blocked and does nothing until the frame has
been successfully transmitted.
2. Single channel assumption:
A single channel is available for all communication. All stations can transmit on it and all can
receive from it.
3. Collision assumption:
If frames are transmitted at the same time by two or more stations, then the collision occurs. and
both frames must re transmitted.

87. 4. Time assumption
It can be divided into Slotted or Continuous time.
A)Continuous time: frame transmission can begin at any instant. There is no
master clock dividing time into discrete intervals.
B)Slotted time:Time is divided into discrete slots. If a slot does not contain any
frame, it is called an idle slot; if it contains a single frame, then the transmission
is successful; if it contains more than one frames, then a collision is said to
occur.

88. 5. A) carrier sense: The stations may or may not be capable of detecting whether the
channel is in use before sending the frames. In algorithms which are based upon carrier
sense, a station sends frame only when it senses that the channel is not busy.
B) no carrier sense: Inalgorithms based upon no carrier sense, the stations transmit a
frame when it is available and later are informed whether successful transmission had
occurred or not.
Advantages
•Dynamicchannelallocationschemesallotschannelsasneeded.Thisresultsinoptimum
utilizationofnetworkresources.Therearelesschancesofdenialofservicesandcall
blockingincaseofvoicetransmission.Theseschemesadjustbandwidthallotment
accordingtotrafficvolume,andsoareparticularlysuitableforburstytraffic.
Disadvantages
•Dynamicchannelallocationschemesincreasesthecomputationalaswellasstorageload
onthesystem.

89. Multiple access protocols
Thedata link layeris used in a computer network to transmit the data
between two devices or nodes. It divides the layer into parts such
asdata link control(logical link control layer)and themultiple
access resolution/protocol(media access layer).
The upper layer(LLC) has the responsibility to flow control and the
error control in the data link layer, and hence it is termed aslogical
of data link control. Whereas the lower sub-layer(MAC) is used to
reduce the collision and handle multiple access on a channel. Hence
it is termed asmedia access controlor the multiple access resolutions.

90. What is a multiple access protocol?
When a sender and receiver have a dedicated link to transmit
data packets, the data link control is enough to handle the
channel.
Suppose there is no dedicated path to communicate or transfer
the data between two devices. In that case, multiple stations
access the channel and simultaneously transmits the data over the
channel. It may create collision and cross talk.Hence, the
multiple access protocol is required to reduce the collision
and avoid crosstalk between the channels.

91. Random Access Protocol(it is a sub part of the multiple access
protocol)
In this protocol, all the station has the equal priority to send the data over a
channel. In random access protocol, one or more stations cannot depend on
another station or any station control another station.
Depending on the channel's state (idle or busy), each station transmits the
data frame. However, if more than one station sends the data over a channel,
there may be a collision or data conflict. Due to the collision, the data frame
packets may be lost or changed. And hence, it does not receive by the
receiver end.
•Following are the different methods of random-access protocols for
broadcasting frames on the channel.
1.Aloha
2.CSMA(carrier sense multiple access)
3.CSMA/CD(carrier sense multiple access/ collision detection)
4.CSMA/CA(carrier sense multiple access/collision avoidance)

92. 1.ALOHA
Aloha is designed for wireless LAN (Local Area Network) but can also be used
in a shared medium to transmit data. In aloha, any station can transmit data to a
channel at any time. It does not require any carrier sensing.
Using this method, any station can transmit data across a network
simultaneously when a data frameset is available for transmission.
Aloha is the random access protocol having two categories that are pure aloha
and slotted aloha.

93. a.Pure ALOHA
Inpure ALOHA, the stations transmit frames whenever they have data to send.
When two or more stations transmit simultaneously, there is collision and the
frames are destroyed.
In pure ALOHA, whenever any station transmits a frame, it expects the
acknowledgement from the receiver.
If acknowledgement is not received within specified time, the station assumes that
the frame (or acknowledgement) has been destroyed.
If the frame is destroyed because of collision the station waits for a random
amount of time called back-off time(Tb) and sends it again. This waiting time
must be random otherwise same frames will collide again and again.
Therefore pure ALOHA dictates that when time-out period passes, each station
must wait for a random amount of time before re-sending its frame. This
randomness will help avoid more collisions.

94. Since different stations wait for different amount of time, the probability of
further collision decreases.
The throughput of pure aloha is maximized when frames are of uniform
length(means fixed size).

95. In fig there are four stations that .contended with one another for access
to shared channel. All these stations are transmitting frames. Some of
these frames collide because multiple frames are in contention for the
shared channel. Only two frames, frame 1.1 and frame 2.2 survive. All
other frames are destroyed.
Whenever two frames try to occupy the channel at the same time, there
will be a collision and both will be damaged. If first bit of a new frame
overlaps with just the last bit of a frame almost finished, both frames
will be totally destroyed and both will have to be retransmitted.

96. b. Slotted ALOHA
The slotted Aloha is designed to overcome the pure Aloha's efficiency
because pure Aloha has a very high possibility of frame
hitting(collision).
In slotted Aloha, the shared channel is divided into a fixed time
interval calledslots. So that, if a station wants to send a frame to a
shared channel, the frame can only be sent at the beginning of the slot,
and only one frame is allowed to be sent to each slot.
And if the stations are unable to send data to the beginning of the slot,
the station will have to wait until the beginning of the slot for the next
time. However, there is still a possibility of collision if two stations try
to send at the beginning of the same time slot .

98. 2. CSMA(carrier sense multiple access)
It is acarrier sense multiple accessbased on media access protocol to
sense the traffic on a channel (idle or busy) before transmitting the data.
It means that if the channel is idle, the station can send data to the
channel. Otherwise, it must wait until the channel becomes idle. Hence,
it reduces the chances of a collision on a transmission medium.
CSMA Access Modes
I.1-Persistent:In the 1-Persistent mode of CSMA that defines each
node, first sense the shared channel and if the channel is idle, it
immediately sends the data. Else it must wait and keep track of the
status of the channel to be idle and broadcast the frame
unconditionally as soon as the channel is idle.

99. II . Non-Persistent:It is the access mode of CSMA that defines before
transmitting the data, each node must sense the channel, and if the
channel is inactive, it immediately sends the data. Otherwise, the station
must wait for a random time (not continuously), and when the channel
is found to be idle, it transmits the frames.
III. P-Persistent:It is the combination of 1-Persistent and Non-
persistent modes. The P-Persistent mode defines that each node senses
the channel, and if the channel is inactive, it sends a frame with
aPprobability. If the data is not transmitted, it waits for a (q = 1-p
probability) random time and resumes the frame with the next time
slot.

101. 2.1. CSMA/ CD
It is acarrier sense multiple access/ collision detectionnetwork
protocol to transmit data frames. The CSMA/CD protocol works with a
medium access control layer. Therefore, it first senses the shared
channel before broadcasting the frames, and if the channel is idle, it
transmits a frame to check whether the transmission was successful.
If the frame is successfully received, the station sends another frame. If
any collision is detected in the CSMA/CD, the station sends a jam/ stop
signal to the shared channel to terminate data transmission. After that, it
waits for a random time before sending a frame to a channel.

102. 2.2. CSMA/ CA
It is acarrier sense multiple access/collision avoidancenetwork
protocol for carrier transmission of data frames.
It is a protocol that works with a medium access control layer. When a
data frame is sent to a channel, it receives an acknowledgment to check
whether the channel is clear. If the station receives only a single (own)
acknowledgments, that means the data frame has been successfully
transmitted to the receiver.
But if it gets two signals (its own and one more in which the collision
of frames), a collision of the frame occurs in the shared channel.
Detects the collision of the frame when a sender receives an
acknowledgment signal.

103. Following are the methods used in theCSMA/ CAto avoid the collision:
•Interframespace: In this method, the station waits for the channel to become
idle, and if it gets the channel is idle, it does not immediately send the data.
Instead of this, it waits for some time, and this time period is called
theInterframespace or IFS. However, the IFS time is often used to define the
priority of the station.
•Contention window: In the Contention window, the total time is divided into
different slots. When the station/ sender is ready to transmit the data frame, it
chooses a random slot number of slots aswait time. If the channel is still busy, it
does not restart the entire process, except that it restarts the timer only to send data
packets when the channel is inactive.
•Acknowledgment: In the acknowledgment method, the sender station sends the
data frame to the shared channel if the acknowledgment is not received ahead of
time.

104. collision free protocols
when more than one station tries to transmit simultaneously via a shared
channel, the transmitted data is garbled. This event is called collision. The
Medium Access Control (MAC) layer of the OSI model is responsible for
handling collision of frames.
Collision –free protocols are devised so that collisions do not occur.
Protocols like CSMA/CD and CSMA/CA the possibility of collisions once
the transmission channel is acquired by any station. However, collision can
still occur during the contention period if more than one stations starts to
transmit at the same time. Collision –free protocols resolves collision in the
contention period and so the possibilities of collisions are eliminated.

105. Types of Collision –free Protocols
1.Bit-Map Protocol
Bit-mapprotocolisacollisionfreeprotocolthatoperatesintheMediumAccess
Control(MAC)layeroftheOSImodel.Itresolvesanypossibilityofcollisions
whilemultiplestationsarecontendingforacquiringasharedchannelfor
transmission.
Inthisprotocol,ifastationwishestotransmit,itbroadcastsitselfbeforethe
actualtransmissioniscalledReservationProtocols.becausetheyreservechannel
ownershipinadvanceandpreventcollisions.
Working Principle
Inthisprotocol,thecontentionperiodisdividedintoNslots,whereNisthetotal
numberofstationssharingthechannel.Ifastationhasaframetosend,itsetsthe
correspondingbitintheslot.
Supposethatthereare10stations.Sothenumberofcontentionslotswillbe
10.Ifthestations2,3,8and9wishtotransmit,theywillsetthe
correspondingslotsto1

106. Once each station announces itself, one of them gets the channel
based upon any agreed criteria.
Generally, transmission is done in the order of the slot numbers.
Each station has complete knowledge whether every other station
wants to transmit or not, before transmission starts. So, all
possibilities of collisions are eliminated.

107. 2. Binary Countdown
Binary countdown protocol is a collision free protocol that operates in the MAC
layer of the OSI model.
When more than one station tries to transmit simultaneously via a shared channel,
the transmitted data is garbled, an event called collision.
Collision free protocols resolves channel access while the stations are contending
for the shared channel, thus eliminating any possibilities of collisions.
A problem with the basic bit-map protocol is that overhead is 1 contention
bit slot per station. We can do better than that by using binary station
addreddes.

108. Working Principle of Binary Countdown
Inabinarycountdownprotocol,eachstationisassignedabinary
address.Thebinaryaddressesarebitstringsofequallengths.Whena
stationwantstotransmit,itbroadcastsitsaddresstoallthestationsin
thechannel,onebitatatimestartingwiththehighestorderbit.
Inordertodecidewhichstationgetsthechannelaccess,theaddresses
ofthestationswhicharebroadcastedareORed.Thehighernumbered
stationgetsthechannelaccess.

109. Example
Supposethatsixstationscontendforchannelaccesswhichhavetheaddresses:
1011,0010,0101,1100,1001and1101.
Theiterativestepsare−
Allstationsbroadcasttheirmostsignificantbit,i.e.1,0,0,1,1,1.Stations
0010and0101sees1bitinotherstations,andsotheygiveupcompetingforthe
channel.
Thestations1011,1100,1001and1101continue.Theybroadcasttheirnextbit,
i.e.0,1,0,1.Stations1011and1001sees1bitinotherstations,andsotheygive
upcompetingforthechannel.
Thestations1100and1101continue.Theybroadcasttheirnextbit,i.e.0,0.Since
bothofthemhavesamebitvalue,bothofthembroadcasttheirnextbit.

110. Thestations1100and1101broadcasttheirleastsignificantbit,i.e.0and1.Since
station1101has1whiletheother0,station1101getstheaccesstothechannel.
Afterstation1101hascompletedframetransmission,orthereisatime-out,the
nextcontentioncyclestarts.
Theprocedureisillustratedasfollows−

111. Wireless LANs
The 802.11 Protocol Stack
•The protocols used by all the 802 variants, including Ethernet,
have a certain commonality of structure.
•The physical layer corresponds to the OSI physical layer fairly
well, but the data link layer in all the 802 protocols is split into
two or more sublayers.
•In 802.11, the MAC (Medium Access Control) sublayer
determines how the channel is allocated, that is, who gets to
transmit next.
•Above it is the LLC (Logical Link Control) sublayer, whose job it
is to hide the differences between the different 802 variants and
make them indistinguishable as far as the network layer is
concerned.

112. The 802.11 Physical Layer
As we know that physical layer is responsible for converting data stream into signals, the bits of 802.11 networks can be
converted to radio waves or infrared waves.
• These are six different specifications of IEEE 802.11. These implementations, except the first one, operate inindustrial,
scientificandmedical (ISM)band. These three banks are unlicensed and their ranges are
1.902-928 MHz
2.2.400-4.835 GHz
3.5.725-5.850 GHz
ThedifferentimplementationsofIEE802.11aregivenbelow:
1.IEEE802.11infrared
•Itusesdiffused(notlineofsight)infraredlightintherangeof800to950nm.
•Itallowstwodifferentspeeds:IMbpsand2Mbps.
•ForaI-Mbpsdatarate,4bitsofdataareencodedinto16bitcode.This16bitcodecontainsfifteenasanda
single1.
•Fora2-Mbpsdatarate,a2bitcodeisencodedinto4bitcode.This4bitcodecontainsthreeOsanda
single1.
•Themodulationtechniqueusedispulsepositionmodulation(PPM)i.e.forconvertingdigitalsignaltoanalog.

113. 2. IEEE 802.11 FHSS
• IEEE 802.11 uses Frequency Hoping Spread Spectrum (FHSS) method for signal generation.
• This method uses 2.4 GHz ISM band. This band is divided into 79 subbandsof 1MHz with some guard
bands.
• In this method, at one moment data is sent by using one carrier frequency and then by some other carrier
frequency at next moment. After this, an idle time is there in communication. This cycle is repeated after
regular intervals.
• A pseudo random number generator selects the hopping sequence.
• The allowed data rates are 1 or 2 Mbps.
• This method uses frequency shift keying (two level or four level) for modulationi.e.for converting digital
signal to analogy.

114. 3.IEEE802.11DSSS
•ThismethodusesDirectSequenceSpreadSpectrum(DSSS)methodforsignalgeneration.Eachbitis
transmittedas11chipsusingaBarkersequence.
•DSSSusesthe2.4-GHzISMband.
•Italsoallowsthedataratesof1or2Mbps.
•Itusesphaseshiftkeying(PSK)techniqueat1Mbaudforconvertingdigitalsignaltoanalogsignal.
4.IEEE802.11aOFDM
•ThismethodusesOrthogonalFrequencyDivisionMultiplexing(OFDM)forsignalgeneration.
•Thismethodiscapableofdeliveringdataupto18or54Mbps.
•InOFDMallthesubbandsareusedbyonesourceatagiventime.
•Ituses5GHzISMband.
•Thisbandisdividedinto52subbands,with48subbandsfordataand4subbandsforcontrolinformation.
•Ifphaseshiftkeying(PSK)isusedformodulationthendatarateis18Mbps.Ifquadratureamplitude
modulation(QAM)isused,thedataratecanbe54Mbps.

115. 5.IEEE802.11bHR-OSSS
•ItusesHighRateDirectSequenceSpreadSpectrummethodforsignalgeneration.
•HR-DSSSissimilartoDSSSexceptforencodingmethod.
•Here,4or8bitsareencodedintoaspecialsymbolcalledcomplementarycodekey(CCK).
•Ituses2.4GHzISMband.
•Itsupportsfourdatarates:1,2,5.5and11Mbps.
•1Mbpsand2Mbpsdataratesusesphaseshiftmodulation.
•The5.5.MbpsversionusesBPSKandtransmitsat1.375Mbaud/swith4-bitCCKencoding.
•The11MbpsversionusesQPSKandtransmitsat1.375Mbpswith8-bitCCKencoding.
6.IEEE802.11gOFDM
•ItusesOFDMmodulationtechnique.
•Ituses2.4GHzISMband.
•Itsupportsthedataratesof22or54Mbps.
•Itisbackwardcompatiblewith802.11b

116. The 802.11 MAC Sublayer Protocol
802.11 supports two modes of operation.
The first, called DCF (Distributed Coordination Function), does not use any kind of central
control (in that respect, similar to Ethernet).
The other, called PCF (Point Coordination Function), uses the base station to control all
activity in its cell.
All implementations must support DCF but PCF is optional.
Distributed Coordination Function:
When DCF is employed, 802.11 uses a protocol called CSMA/CA (CSMA with Collision
Avoidance). In this protocol, both physical channel sensing and virtual channel sensing
are used. Two methods of operation are supported by CSMA/CA. In the first method,
when a station wants to transmit, it senses the channel. If it is idle, it just starts
transmitting. It does not sense the channel while transmitting but emits its entire frame,
which may well be destroyed at the receiver due to interference there. If the channel is
busy, the sender defers until it goes idle and then starts transmitting.

117. If a collision occurs, the colliding stations wait a random time, using the Ethernet binary
exponential backoff algorithm, and then try again later.
The other mode of CSMA/CA operation is based on MACAW and uses virtual channel
sensing.
If A wants to send to B. C is a station within range of A (and possibly within range of B, but
that does not matter). D is a station within range of B but not within range of A.

119. Whenastationwantstotransmit,itsensesthechanneltoseewhetheritis
freeornot.
2.Ifthechannelisnotfreethestationwaitsforbackofftime.
3.Ifthestationfindsachanneltobeidle,thestationwaitsforaperiodoftime
calleddistributedinterframespace(DIFS).
4.Thestationthensendscontrolframecalledrequesttosend(RTS)as
showninfigure.
5.Thedestinationstationreceivestheframeandwaitsforashortperiodof
timecalledshortinterframespace(SIFS).
6.Thedestinationstationthensendsacontrolframecalledcleartosend
(CTS)tothesourcestation.Thisframeindicatesthatthedestinationstationis
readytoreceivedata.
7.ThesenderthenwaitsforSIFStimeandsendsdata.
8.ThedestinationwaitsforSIFStimeandsendsacknowledgementforthe
receivedframe.

120. Collisionavoidance
•802.11standardusesNetworkAllocationVector(NAV)forcollisionavoidance.
•TheprocedureusedinNAVisexplainedbelow:
1.WheneverastationsendsanRTSframe,itincludesthedurationoftimeforwhichthestationwilloccupy
thechannel.
2.Allotherstationsthatareaffectedbythetransmissioncreatesatimercanednetworkallocationvector
(NAV).
3.ThisNAV(createdbyotherstations)specifiesforhowmuchtimethesestationsmustnotcheckthe
channel.
4.Eachstationbeforesensingthechannel,checkitsNAVtoseeifhasexpiredornot.
5.IfitsNAVhasexpired,thestationcansenddata,otherwiseithastowait.
•Therecanalsobeacollisionduringhandshakingi.e.whenRTSorCTScontrolframesareexchanged
betweenthesenderandreceiver.Inthiscasefollowingprocedureisusedforcollisionavoidance:
1.WhentwoormorestationssendRTStoastationatsametime,theircontrolframescollide.
2.IfCTSframeisnotreceivedbythesender,itassumesthattherehasbeenacollision.
3.Insuchacasesender,waitsforbackofftimeandretransmitsRTS.

121. 2.PointCoordinationFunction
•PCFmethodisusedininfrastructurenetwork.InthisAccesspointisusedtocontrolthenetworkactivity.
•ItisimplementedontopoftheDCFandISusedfortimesensitivetransmissions.
•PCFusescentralized,contentionfreepollingaccessmethod.
•TheAPperformspollingforstationsthatwantstotransmitdata.Thevariousstationsarepolledoneafterthe
other.
•TogiveprioritytoPCFoverDCF,anotherinterframespacecalledPIFSisdefined.PIFS(PCFIFS)isshorterthan
DIFS.
•Ifatthesametime,astationisusingDCFandAPisusingPCF,thenAPisgivenpriorityoverthestation.
•DuetothispriorityofPCFoverDCF,stationsthatonlyuseDCFmaynotgainaccesstothechannel.
•Toovercomethisproblem,arepetitionintervalisdefinedthatisrepeatedcontinuously.Thisrepetitioninterval
startswithaspecialcontrolframecalledbeaconframe.
•Whenastationhearsbeaconframe,itstarttheirNAVforthedurationoftheperiodoftherepetitioninterval.

122. The 802.11 Frame Structure:
The 802.11 standard defines three different classes of frames on the wire: data, control,
and management. Each of these has a header with a variety of fields used within the MAC
sublayer.
TheMAClayerframeconsistsofninefields.
1.FrameControl(FC).Thisis2bytefieldanddefinesthetypeofframeandsomecontrolinformation.This
fieldcontainsseveraldifferentsubfields.
2.D.Itstandsfordurationandisof2bytes.Thisfielddefinesthedurationforwhichtheframeandits
acknowledgementwilloccupythechannel.ItisalsousedtosetthevalueofNAVforotherstations.
3.Addresses.Thereare4addressfieldsof6byteslength.Thesefouraddressesrepresentsource,
destination,sourcebasestationanddestinationbasestation.
4.SequenceControl(SC).This2bytefielddefinesthesequencenumberofframetobeusedinflowcontrol.
5.Framebody.Thisfieldcanbebetween0and2312bytes.Itcontainstheinformation.
6.FCS.Thisfieldis4byteslongandcontains‘cRC-32errordetectionsequence.

124. IEEE 802.11 Frame types
Therearethreedifferenttypesofframes:
1.Managementframe
2.Controlframe
3.Dataframe
1.Managementframe.Theseareusedforinitialcommunicationbetweenstationsandaccesspoints.
2.Controlframe.Theseareusedforaccessingthechannelandacknowledgingframes.Thecontrolframes
areRTSandCTS.
3.Dataframe.Theseareusedforcarryingdataandcontrolinformation.

125. 802.11 Addressing
• There are four different addressing cases depending upon the value ofTo DSAnd fromDS subfields of
FC field.
• Each flag can be 0 or 1, resulting in 4 different situations.
1. IfToDS = 0 andFromDS = 0, it indicates that frame is not going to distribution system and is not
coming from a distribution system. The frame is going from one station in a BSS to another.
2. IfToDS = 0 andFromDS = 1, it indicates that the frame is coming from a distribution system. The
frame is coming from an AP and is going to a station. The address 3 contains original sender of the frame
(in another BSS).
3. IfToDS = 1 andFromDS = 0, it indicates that the frame is going to a distribution system. The frame is
going from a station to an AP. The address 3 field contains the final destination of the frame.
4. IfToDS = 1 andFromDS = 1,it indicates that frame is going from one AP to another AP in a wireless
distributed system.

126. The table below specifies the addresses of all four cases.

127. Data link layer Swtching
•Networkswitchingistheprocessofforwardingdataframesorpackets
fromoneporttoanotherleadingtodatatransmissionfromsourceto
destination.DatalinklayeristhesecondlayeroftheOpenSystem
Interconnections(OSI)modelwhosefunctionistodividethestreamof
bitsfromphysicallayerintodataframesandtransmittheframes
accordingtoswitchingrequirements.Switchingindatalinklayeris
donebynetworkdevicescalledbridges.
Bridges
•AdatalinklayerbridgeconnectsmultipleLANs(localareanetworks)
togethertoformalargerLAN.Thisprocessofaggregatingnetworksis
callednetworkbridging.Abridgeconnectsthedifferentcomponents
sothattheyappearaspartsofasinglenetwork.

128. Usesof Bridges
•Before getting into the technology of bridges, let us take a look at some
common situations in which bridges are used.
Example: First, many universities and corporate departments have their
own LANs toconnecttheirownpersonalcomputers,servers,anddevices
suchasprinters.Since the goals of the various departmentsdiffer,
different departmentsmay setup differentLANs, without regard to what
other departmentsare doing.later, though, there is a need for
interaction, so bridges are needed.In this example,multiple LANscome
intoexistencedueto theautonomy of theirowners.

130. Switching by Bridges
•Whenadataframearrivesataparticularportofabridge,thebridgeexaminesthe
frame’sdatalinkaddress,ormorespecifically,theMACaddress.Ifthe
destinationaddressaswellastherequiredswitchingisvalid,thebridgesendsthe
frametothedestinedport.Otherwise,theframeisdiscarded.
•Thebridgeisnotresponsibleforendtoenddatatransfer.Itisconcernedwith
transmittingthedataframefromonehoptothenext.Hence,theydonotexamine
thepayloadfieldoftheframe.Duetothis,theycanhelpinswitchinganykindof
packetsfromthenetworklayerabove.
•BridgesalsoconnectvirtualLANs(VLANs)tomakealargerVLAN.
•Ifanysegmentofthebridgednetworkiswireless,awirelessbridgeisusedto
performtheswitching.
Therearethreemainwaysforbridging−
•simple bridging
•multi-port bridging
•learning or transparent bridging

131. Switching techniques
•Inlargenetworks,therecanbemultiplepathsfromsendertoreceiver.Theswitching
techniquewilldecidethebestroutefordatatransmission.
•Switchingtechniqueisusedtoconnectthesystemsformakingone-to-one
communication.
1.CircuitSwitching
•Circuitswitchingisaswitchingtechniquethatestablishesadedicatedpathbetween
senderandreceiver.
•IntheCircuitSwitchingTechnique,oncetheconnectionisestablishedthenthededicated
pathwillremaintoexistuntiltheconnectionisterminated.
•Circuitswitchinginanetworkoperatesinasimilarwayasthetelephoneworks.
•Acompleteend-to-endpathmustexistbeforethecommunicationtakesplace.
•Incaseofcircuitswitchingtechnique,whenanyuserwantstosendthedata,voice,
video,arequestsignalissenttothereceiverthenthereceiversendsbackthe
acknowledgmenttoensuretheavailabilityofthededicatedpath.Afterreceivingthe
acknowledgment,dedicatedpathtransfersthedata.
•Circuitswitchingisusedinpublictelephonenetwork.Itisusedforvoicetransmission.
•Fixeddatacanbetransferredatatimeincircuitswitchingtechnology.

132. Circuitscanbepermanentortemporary.Applicationswhichusecircuit
switchingmayhavetogothroughthreephases:
•Establishacircuit
•Transferthedata
•Disconnectthecircuit
•Circuit switching was designed for voice applications. Telephone is the best
suitable example of circuit switching. Before a user can make a call, a virtual path
between caller and callee is established over the network.

133. 2. Message Switching
•Thistechniquewassomewhereinmiddleofcircuitswitchingandpacket
switching.Inmessageswitching,thewholemessageistreatedasadataunitandis
switching/transferredinitsentirety.
•Aswitchworkingonmessageswitching,firstreceivesthewholemessageand
buffersituntilthereareresourcesavailabletotransferittothenexthop.Ifthe
nexthopisnothavingenoughresourcetoaccommodatelargesizemessage,the
messageisstoredandswitchwaits.

134. •Thistechniquewasconsideredsubstitutetocircuitswitching.Asin
circuitswitchingthewholepathisblockedfortwoentitiesonly.
Messageswitchingisreplacedbypacketswitching.Messageswitching
hasthefollowingdrawbacks:
•Everyswitchintransitpathneedsenoughstoragetoaccommodate
entiremessage.
•Becauseofstore-and-forwardtechniqueandwaitsincludeduntil
resourcesareavailable,messageswitchingisveryslow.
•Messageswitchingwasnotasolutionforstreamingmediaandreal-
timeapplications.

135. 3. Packet Switching
•Shortcomingsofmessageswitchinggavebirthtoanideaofpacketswitching.
•Thepacketswitchingisaswitchingtechniqueinwhichthemessageissentinone
go,butitisdividedintosmallerpieces,andtheyaresentindividually.
•Themessagesplitsintosmallerpiecesknownaspacketsandpacketsaregivena
uniquenumbertoidentifytheirorderatthereceivingend.
•Everypacketcontainssomeinformationinitsheaderssuchassourceaddress,
destinationaddressandsequencenumber.
•Packetswilltravelacrossthenetwork,takingtheshortestpathaspossible.
•Allthepacketsarereassembledatthereceivingendincorrectorder.
•Ifanypacketismissingorcorrupted,thenthemessagewillbesenttoresendthe
message.
•Ifthecorrectorderofthepacketsisreached,thentheacknowledgmentmessage
willbesent.

136. •The internet uses packet switching technique. Packet switching enables the user to
differentiate data streams based on priorities. Packets are stored and forwarded
according to their priority to provide quality of service.