Data Link Layer Data Link Layer

 Data link layer is the 2nd layer in the internet model.  The job of the data linker is to transmit to the destination machine
 Data link layer providing services to the network layer & utilizes the and handover to the network layer.
services of physical layer.  The data link layer receives packets from the network layer and
 Data link layer organize data in the form of frames. encapsulate them in to frames for transmission.
Design Issues  The data link layer at the receiver side, extract packet from the
1. Providing well-defined service interface to the network layer. frame, forward to the network layer.
2. Framing  how to organize group of bits?  The following diagram shows the relationship between packet &
3. Error control  how to detect & correct errors? frame.
4. Flow control  how much data may be sent? Packet Packet
5. Access control  who should send now ?
 The primary duty of the data link layer is to transfer data from the Header payload tail Frame Header payload tail
network layer source machine to network layer on the destination
machine.
 The source machine entity, called process on the network layer
handover some bits(packet) to data link layer for transmission.
JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

Data Link Layer Data Link Layer

 The following diagrams shows the follow of data between the  The data linker providing various services to the network layer.
systems. Host B Host A Host B  The reasonable services are
Host A
Application Application Application Application
1. Unacknowledged connectionless service.
2. Acknowledged connectionless service.
Transport Transport Transport Transport
3. Acknowledged connection-oriented service.
Network Network Network Network Framing
 To provide services to the network layer, it uses the services of
Data Link Data Link Data Link Data Link
physical layer.
Physical Physical Physical Physical  Physical layer delivers stream bits from source to destination.
 The bit stream is not guaranteed to be error free.
 This is up to the DLL to detect, if necessary correct errors.
Virtual Communication
Actual Communication  For this purpose DLL break the bit stream into discrete frames
and compute the checksum.
 When a frame arrives to the destination, the checksum is
recomputed.
JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

1
 Data Link Layer Data Link Layer
 If newly computed checksum is differ from the one contained in Character Count
the frame indicates error in the frame.  In this mechanism first filed in the frame specify the number of
 Breaking the bit stream into frames is the more complex task. characters in the frame.
 One way to achieve this framing is to insert time gap between the  At the destination, DLL receives based on the count in the header.
frames, like gap between words in text.  The following diagram shows character count method.
 It is very difficult to maintain proper time gap between the Character count

systems.
5 1 2 3 4 5 6 7 8 9 8 0 1 2 3 4 5 6 7 7 8 9 0 1 2
 There four different other methods
1. Character Count.
2. Flag byte with byte Stuffing. Frame 1 Frame 2 Frame 3 Frame 4
5 characters 5 characters 8 characters 7 characters
3. Starting & ending flags with bit Stuffing.
4. Physical Layer Coding Violations.

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

Data Link Layer Data Link Layer

 The problem with this method is that count can be garbled during Byte Stuffing
transmission .  In this method each frame start & end with special bytes.
 The following diagram shows the damage in the frame during  The starting and ending byte of each frame is flag byte.
transmission.  In this mechanism receiver never loses synchronization.
Error  Two consecutive flag bytes indicates the end of the frame and start
of the next frame.
5 1 2 3 4 7 6 7 8 9 8 0 1 2 3 4 5 6 7 7 8 9 0 1 2  A serious problem occurred with this method, there is a possibility
of flag byte sequence in the part of data.
 To overcome this problem by adding special escape byte(ESC)
Frame 1 Frame 2 Now a Character just before each flag byte in the part of the data.
5 characters wrong Count
 The adding of extra byte to the data is called Byte Stuffing.
 Next Question hers is
 How handle ESC sequence in the part of the data.
 Two consecutive ESC sequences are used.

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

2
 Data Link Layer Data Link Layer
 The following examples shows the Byte Stuffing  The major disadvantage of this framing method is that of using 8-
Original Data After Stuffing bit characters.
 Not all character codes are 8-bit, for example UNICODE uses 16-
A FLAG B A ESC FLAG B
bit characters.
Bit Stuffing
A ESC B A ESC ESC B  It defines to insert extra bits in frame, instead of extra characters.
 Each frame begin with bit sequence 01111110(flag) and end with
flag.
A ESC FLAG B A ESC ESC ESC FLAG B
 Whenever the senders data encounters the five consecutive 1’s , it
automatically stuffs a 0 bit in the out going stream.
 When the receiver sees five consecutive incoming 1 bits followed
A ESC ESC B A ESC ESC ESC ESC B
by a o bit, it automatically destuffs the 0 bit.
 Consider the following example, the original data is
0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

Data Link Layer Data Link Layer

 Data during the transmission are Error Detection & Correction
0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 01 1 1 1 1 0 1 0 0 1 0  Data can be corrupted during transmission.
 Most of the applications require that errors to be detected & also
Stuffed Bits
to be corrected.
 Some other applications can tolerate errors up to some level.
 Computer networks, errors are broadly divided into two types
 The data at the receiver side
1. Single bit error 2. Burst error.
 The term single bit error means only one bit is damaged in the
0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0
given data.
 The last method(code violation) belongs to physical layer no  Damage means, 1 is altered to 0 (or) 0 is altered to 1.
longer in use.  Most likely in serial transmission.

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

3
 Data Link Layer Data Link Layer
Burst Errors Error Detection
 Two or more bits in data unit are in error, not necessarily  Need to detect before a message is processed.
consecutive in order  Redundancy may be used in the message for error control
 Most likely in parallel/serial transmissions.
 Process (error detection) must be handled at the destination.
 Number of bits affected depend on data rate and noise duration.
Redundancy
 Extra bits added to the frame is called redundancy bits.
 The redundancy bits added by the sender and are removed by the
receiver.
 The following diagram shows the redundancy bits in that data
during transmission.

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

Data Link Layer Data Link Layer

 Redundancy bits The error detection methods are
1. Parity Check
2. Cyclical Redundancy Check (CRC)
3. Checksum
 Parity and CRC are performed by data link layer, checksum
performed by higher-layer (Transport layer).
Parity Check
 Most common and least expensive.
 The parity check are of two types.
 Vertical Redundancy Check (VRC)
 Longitudinal Redundancy Check (LRC)
 VRC are of two types
 1. even parity check 2. odd parity check.
JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

4
 Data Link Layer Data Link Layer
 In even-parity, a redundant bit (parity bit) is appended to every For Ex:
data unit so total number of 1 bits is even; odd-parity – total 1 bits  Suppose the sender wants to send the following data
should be odd.  1110111 1101111 1110010 1101100 1100100
 The following shows the actual bits sent
 11101110 11011110 11100100 11011000 11001001
 Suppose receiver receives with out corruption.
 11101110 11011110 11100100 11011000 11001001
 The receiver counts the 1s in each character and comes up with
even numbers (6, 6, 4, 4, 4). The data are accepted.
 Now suppose corrupted during transmission.
 11111110 11011110 11101100 11011000 11001001
 The receiver counts the 1s in each character and comes up with
even and odd numbers (7, 6, 5, 4, 4). The receiver knows that the
data are corrupted and discards them.

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

Data Link Layer Data Link Layer

Performance 3. We then calculate the Parity bit for each column and create a new
 Can detect all single-bit errors row of 8 bits which are the parity bits for the whole block
 May detect all burst errors as long as total number of bits changed 4. Note that the first parity bit in the 5th row is calculated based on
is odd all the first bits.
 Cannot detect errors when total number of bits changed is even 5. The second parity bit is calculated based on all the second bits
since parity check will pass even though errors had occurred . and so on.
6. We then attach the 8 parity bits to the original data and send them
Longitudinal Redundancy Check(LRC). to the receiver.
1. In LRC, a block of bits is organized in a table (rows and
columns)
2. For example instead of sending 32 bits, we organize them in a
table made of 4 rows and 8 columns

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

5
 Data Link Layer Data Link Layer
Performance  These bits are later used in calculations to detect whether or not an
 Burst errors can be detected more often. error had occurred.
 As shown in the example, an LRC of ‘n, bits can easily detect a  At its destination, the data unit is divided by the same number.
burst error of ‘n’ bits  At this step, remainder is zero, the incoming data unit is assumed
 If two bits in one data unit are changed and two bits in exactly the to be intact and is therefore accepted.
same place in another data unit are also damaged, it unable to  A remainder is non zero. indicates that a data unit has been
detect. damaged and therefore must be rejected.
Cyclic Redundancy Check Deriving the CRC
 Most powerful of checking techniques  A string of 0s is appended to the data unit, n is one less than
 VRC and LRC are based on Addition number of bits in predetermined divisor.
 CRC is based on Binary Division  New data unit is divided by the divisor using binary division,
 A sequence of redundant bits called CRC or CRC remainder is remainder is CRC
appended to the end of the data unit.  CRC of n bits replaces appended 0s at end of data unit.

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

Data Link Layer Data Link Layer

 The following diagram shows the CRC Generator & Checker. CRC Generator
 It uses modulo-2 division
 Resulting remainder is the CRC.
 For Ex:
 1 0 0 1 0 0 is the data.
 1 1 0 1 is the predetermined divisor.
 Append 0 0 0 to the data.
 The following diagram shows the CRC Calculation.

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

6
 Data Link Layer Data Link Layer
 CRC Calculation  Data during transmission are
 100 100001
CRC Checker
 Performed by receiver.
 Data is appended with CRC.
 Same modulo-2 division.
 If remainder is 0, data are accepted.
 Otherwise, an error has occurred.

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

Data Link Layer Data Link Layer

 The following diagram shows the receiver task. Polynomials
 CRC generator ( the divisor) is most often represented not as a
string of 1’s and 0’s but as an algebraic polynomial.
 The polynomial format is useful for two reasons: –It is short –Can
be used to prove the concept mathematically.
Selection of a Polynomial
 A polynomial should have the following properties: –It should not
be divisible by ‘x’ –It should not be divisible by ‘x+1’.
 The first condition guarantees that all burst errors of a length equal
to the degree of the polynomial are detected
 And The 2 guarantees that all burst errors affecting an odd number
of bits are detected.

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

7
 Data Link Layer Data Link Layer
Selecting divisor from the polynomial. CRC Performance
 Can detect all burst errors affecting an odd number of bits
 Can detect all burst errors of length less than or equal to degree of
polynomial
 Can detect with high probability burst errors of length greater than
degree of the polynomial

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

Data Link Layer Data Link Layer

Checksum  Checksum process at the receiver side(Checksum Checker)
 It uses various protocols for error detection(not DLL protocols).
are
 Its performs end-end error detection.
 The checksum process at the sender side are(checksum  Receiver subdivides data unit in k sections of n bits.
Generator).
 Sections are added together using one’s complement to get
 At sender, checksum generator subdivides data unit into k equal
segments of n bits. the sum.
 Segments are added together using one’s complement arithmetic
 Sum is complemented.
to get the sum.
 Sum is complemented and becomes the checksum, appended to  If result is zero, data are accepted; otherwise, rejected.
the end of the data.

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

8
 Data Link Layer Data Link Layer
 The following diagram shows the checksum process Ex: the following data to be sent
1000 0110 0101 1110 1010 1100 0110 0000 0111 0001 0010 1010
1000 0001 1011 0101.
 The data is divided into 4 units each with 16 bits
 1000 0110 0101 1110
 1010 1100 0110 0000
 0111 0001 0010 1010
 1000 0001 1011 0101
 Its sum are
 0010 0101 1001 1111
 Its 1’s compliment are
 1101 1010 0110 0000
 The data to be transmitted are
JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

Data Link Layer Data Link Layer

 1000 0110 0101 1110 1010 1100 0110 0000 0111 0001 0010 1010 Error Correction
1000 0001 1011 0101 1101 1010 0110 0000  Error correction requires more number of redundancy bits.
 At the receiver side data is divided into 5 sections and each with  We must know not only that an error had occurred, but where the
16 bits error occurred in order to correct it.
 1000 0110 0101 1110  Correction simply involves flipping the bit
 1010 1100 0110 0000  Error correction are of two types
 0111 0001 0010 1010 1. Single bit Error correction.
 1000 0001 1011 0101 2. Burst Error correction.
 First one more simple than the second one.
 1101 1010 0110 0000
 Hamming code may be applied to identify location where error
 Its sum are
occurred by strategically placed redundancy bits.
 1111 1111 1111 1111 1. Single bit error correction.
 Its 1’s compliment are  the number of redundancy bits are calculated using minim
 0000 0000 0000 0000, so data are accepted. hamming distance method.
JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

9
 Data Link Layer Data Link Layer
 The minimum hamming distance method are  For correct one bit error in 7bits unit requires 4 redundancy bits.
 2r >= m+r+1  The redundancy bits are placed in the part of the data unit
 Where m is no. of bits in data unit. systematically.
 r is the number of bits are required.  The total number of bits are 11.
 r value is calculated using trail & error method.  The redundancy bits are r1,r2,r4 & r8.
 If m = 7  The data bits are d3,d5,d6,d7,d9,d10,d11.
 Assume r = 2  The r1 is placed, if first bit is 1 & remaining are zero.
 22 >= 7+2+1  4 >= 10  The r2 is placed, if second bit is 1 & remaining are zero.
 Assume r = 3  The r4 is placed, if third bit is 1 & remaining are zero.
 23 >= 7 + 3 + 1  8 >= 11  The r8 is placed, if fourth bit is one & remaining are zero.
 Assume r = 4  The d3 to d11 are placed in other positions from right to left.
 24 >= 7 + 4 + 1  16 >= 12  The following diagram shows the position of bits

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

Data Link Layer Data Link Layer

At the sender side r1: r1, d3,d5,d7, d9, d11
 Calculate the values for redundancy bits by using the even parity
mechanism. r2: r2, d3, d6, d7, d10, d11
 Calculate the r1 value by using first bit 1 data units. r3: r4, d5, d6, d7
 Calculate the r2 value by using second bit 1 data units.
 Calculate the r4 value by using third bit 1 data units. r4: r8, d9, d10, d11
 Calculate the r8 value by using fourth bit 1 data units At the receiver side same mechanism applied.
 the following diagram shows the bits of each unit.
r1,r2,r4 & r8 are zero data received correctly.
0010
1000

0100

0001
1010

0110

0011
1001

0101
1011

0111

otherwise, in the respective position an error occurred and it is

going to be toggled.

For Ex:1001101

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

10
 Data Link Layer Data Link Layer
Elementary Data Link Protocols  The flow control & error control protocols are divided into
 Protocol – set of rules governing communication between devices. following categories.
 Data link protocols define the rules to implement data link layer protocols
functions
 Contain rules for flow control and error control etc.
For Noiseless For Noise
 The follow control refers to a set of procedures used to restrict the channel channel
amount of data that the sender can send before waiting for an
acknowledgement. Stop&Wait Go-Back N Selective-
Simplex Stop & Wait ARQ Repeat ARQ
 Error control refers an automatic repeat request, for retransmission ARQ
of data when the frame is lost or damaged.

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

Data Link Layer Data Link Layer

Noiseless Channel  Simplex protocol design.
 Let us assume we have an ideal channel in which no frame lost, Sender Receiver
duplicate frames and corruption etc. Get Data
N/W N/W Deliver Data
 No need of flow control & error control.
Simplex Protocol DLL DLL
 There is no flow control & error control.
 Flow of data is unidirectional. PHY Send Frame PHY Receive Frame
Data Frames
 In this mechanism receiver immediately receives the frame with a Sender:
processing time.  Event : Request from N/W Layer
 DLL of the receiver immediately remove the header & forward to  Repeat forever algorithm for sender site.
upper layer.
Receiver:
 The receiver can never overloaded with incoming frames.
 Repeat forever algorithm for receiver site.
 The following diagram shows the design of simplex protocol.
 Event : Notification from physical Layer.
JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

11
 Data Link Layer Data Link Layer
 The following diagram of simplex protocol Stop-and-Wait Protocol
sender Receiver  If frames arrive faster than they can be processed.
Request  The frames must be store until the their use.
 Normally receiver does not have enough storage space.
Arrival
Request  This may results discard of frames.
Arrival  To prevent the discarding of frames, somehow need to tell the
Request
sender to slow down.
 There must be a feedback from receiver to sender.
Arrival
 The stop-and-wait protocol send one frame, stop until it receives
time time conformation (ACK) from receiver.
 The following diagram shows the design of stop-and-wait
protocol.

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

Data Link Layer Data Link Layer

 Stop-and-wait design Receiver
Sender Receiver  Repeat algorithm for receiver site.
Get Data Deliver Data  Event: notification from physical layer.
N/W N/W
 Event: generate Ack.
Receive send
DLL frame DLL  Flow Diagram of stop-and-wait
frame sender Receiver
Request Frame
Send
PHY PHY Arrival
Frame Data Frames Receive Frame
ACK
Request
Sender: ACK Arrival
 Event: Request from network Layer. Request
 Repeat forever algorithm for sender site.
Arrival
 Event: Notification from physical layer.
time time
JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

12
 Data Link Layer Data Link Layer
Noise Channels  A field added to the frame for holding sequence number of the
 There are three protocols for noise channels. frame.
Stop-and-Wait Automatic Repeat Request(ARQ)  The range of the sequence numbers is depends on number of bits
allocated to it.
 Added simple error control mechanism to the noiseless stop-and-
 If m bits allocated, sequence number from 0 to 2m – 1.
wait protocol.
 Stop-and-Wait ARQ use x as the initial sequence number, we need
 Lost frames are more difficult to handle than damaged frames. x+1 only after that.
 For error correction keep a copy of the frame for retransmission.  Suppose, sender sent a frame with x sequence number and
 When a frame is lost or damage receiver does not respond. received successfully.
 At the time of sending a frame sender starts timer, if the timer  Receiver sent ACK with x+1 Sequence Number.
expires and no ACK for the sent frame, the frame is resent.  Sender sent a frame with x+1 sequence number and received
Sequence Number successfully.
 The frames are numbered using sequence numbers.  Receiver sent ACK with x sequence number.
 Two sequences are required to distinguish the frames, so x is 0
and x+1 is 1.
JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

Data Link Layer Data Link Layer

 So, the sequence numbers are 0 1 0 1 0 1 0 1 and so on. Sender:
 The ACK are also numbered 1 0 1 0 1 0 and so on.  Event: Request from network Layer.
The following diagram shows the design of stop-and-wait ARQ.  Repeat forever algorithm for sender site.
 Event : Time out
Sn next frame to sent Rn next frame to receive
01010101 01010101  Event: Notification from physical layer.
Sender Receiver Receiver
 Repeat algorithm for receiver site.
N/W N/W Deliver Data
Get Data  Event: notification from physical layer.
Receive send  Event: generate Ack.
DLL DLL
frame ACK
Send Receive Frame
PHY Frame PHY
Data Frames

ACK

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

13
 Data Link Layer Data Link Layer
 Flow Diagram of stop-and-wait ARQ Normal Operation  Flow Diagram lost or damaged Frames

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

Data Link Layer Data Link Layer

 Flow Diagram for Lost ACK  Flow Diagram for Delayed ACK.

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

14
 Data Link Layer Data Link Layer
Stop-and-Wait ARQ Performance Bidirectional Transmission
Advantage:
 Simplicity: each frame is checked and ACK’d before next frame is  Possible if two parties have separate channels for full-duplex
sent transmission or share same channel for half-duplex transmission.
 Numbering of frames prevents duplication
 Method of combining data frame and acknowledgement is called
Disadvantage:
 Inefficiency and slow piggybacking.
 Frame and ACKs use entire bandwidth  It saves bandwidth due to combine data & ACK in a single frame.
 If distance is long between devices, waiting time is more.
 In Piggybacking method sender & receiver maintains both S & R
Variables.

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

Data Link Layer Data Link Layer

 The following diagram shows the piggybacking transmission. Sliding Window
 Sender may transmit several frames before waiting an ACK.
 Much more efficient, receiver may use a single ACK to confirm
multiple frames.
 Sliding window refers to upper and lower limit on number of
frames that may be transmitted before ACK is required.
 Frames must be numbered to allow receiver to identify which
frame is acknowledged
 There are two sliding window protocols.
1. go-back N ARQ
2. Selective Repeat ARQ

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

15
 Data Link Layer Data Link Layer
Go-back N ARQ  The range of the sequence numbers is depends on number of bits
 Allows more efficient transmission. allocated to it.
 Sender send multiple frames before waiting for an ACK.  If m bits allocated, sequence number from 0 to 2m – 1.
 Sliding window is an imaginary shadow on the sequence of  For ex: m = 3;
frames.  The sequence numbers are
 The frames right side of the window specifies, cannot be sent.  0 1 2 3 4 5 6 7 0 1 2 3 4 ------
 The frames on the window specifies, frames are sent & wait for an  The sender window of size 2m -1 with three variables namely Sf,
ACK. Sn and Ssize.
 The frames left side of the window specifies, frames already  Sf is sending window first outstanding frame.
ACKed.
 Sn is sending window next frame to send.
Sequence Numbers
 Ssize is the size of the window.
 The frames are numbered using sequence numbers.
 The sender window can slides one or more slots when ACK
 A field added to the frame for holding sequence number of the
arrives.
frame.
JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

Data Link Layer Data Link Layer

 The receiver window size is 1 always with single variable R. Design of go-back N ARQ
 Sequence number left side of the window indicates already
received and acknowledged.
 Sequence number right side of the window indicates cannot be Sf Sn
Rn
received.
0123456701234
 Sequence number on the window indicates frame expected to 0123456701234
Sender Receiver
arrive. Get Data Deliver Data
 Any other frame arrives, receiver simply discard the frame. N/W N/W

 The following diagram shows the sender & receiver windows with Receive send
variables. DLL frame DLL
frame

Send
PHY PHY
Frame Data Frames Receive Frame

ACK

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

16
 Data Link Layer Data Link Layer
Sender: Go-Back-N Operation
 Event: Request from network Layer.  Timers: sender sets a timer for each frame.
 Repeat forever algorithm for sender site.  No timer needed for receiver.
 Event : Time out  Acknowledgement - receiver sends positive ACK when frame
 Event: Notification from physical layer. received successfully.
Receiver  Silent on damaged & lost frames .
 Repeat algorithm for receiver site.  Resending Frames – All the frames.
 Event: notification from physical layer. Note: In go-back-N ARQ size of the sender window must be <= 2m -
 Event: generate Ack. 1 and receiver window must be of size 1.

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

Data Link Layer Data Link Layer

Go-Back N Normal Operation Go-Back N lost or damaged frame

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

17
 Data Link Layer Data Link Layer
 Go-Back N window size must be <= 2m -1. Selective Repeat ARQ
 Go-Back-N is less efficient, all out of order or damaged frames
must be resent in order
 Selective Repeat is a more efficient method but requires more
processing.
 Sender window and control variables are same as Go-Back-N.
 Receiver window is same size of sender.
 Receiver look for range of frames unlike go-back-N.
 Receiver window requires two control variables to define window
boundaries: RF and RL
 It also uses negative acknowledgement (NAK) to report sequence
number of damaged frame.
Note : Window size of sender & receiver must be <= 2m / 2.

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

Data Link Layer Data Link Layer

Design of Selective Repeat ARQ Sender:
 Event: Request from network Layer.
 Repeat forever algorithm for sender site.
Sf Sn Rl
Rf  Event : Time out
0123456701234  Event: Notification from physical layer.
0123456701234
Sender Receiver Receiver
Get Data Deliver Data  Repeat algorithm for receiver site.
N/W N/W
 Event: notification from physical layer.
Receive send
DLL frame DLL  Event: generate Ack.
frame

Send
PHY PHY
Frame Data Frames Receive Frame

ACK or NAK

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

18
 Data Link Layer Data Link Layer
The following diagram shows the sender & receiver windows  The following diagram shows the handling process of lost Frame.

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

Data Link Layer Data Link Layer

Selective Repeat ARQ sender window size must be <= 2m-1 or 2m/2. Comparisons between Go-back-n and Selective-Reject

 Sending only specific damaged or lost frames requires complexity

of sorting and more storage is required in selective-reject

 Go-back-n is typically used due to simplicity

Example DDL Protocols
 There are two popular protocols
 HDLC – High-Level data Link Control Protocol
 PPP – Point-Point Protocol.

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

19
 Data Link Layer Data Link Layer
HDLC PROTOCOL NRM
 High-level Data Link Control – protocol supporting half-duplex  The station configuration is unbalanced.
and full-duplex communication over point-to-point and multipoint  In the network, one primary station and multiple secondary
links stations.
 The old DLL protocols is SDLC(Synchronous data link control)  A Primary Station can send commands.
protocols and is used in IBM mainframes.  The Secondary station can only respond.
 IBM submitted to ANSI and ISO, and ANSI modified to  It is used for both point-point & multipoint links.
ADCCP(Advanced Data Communication Control Protocol).
 The following diagram shows the structure of NRM
 ISO modified to HDLC.
 HDLC supports two common transfer modes and can be used in
any configuration.
1. Normal Response Mode(NRM).
2. Asynchronous Response Mode(ARM).

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

Data Link Layer Data Link Layer

 To provide flexibility & efficient communication HDLC frame is
ARM
divided into three sub-types.
 All stations are equal.
1. Information Frames or I-Frames.
 Stations in point-to-point configurations act as both primary and
2. Supervisory Frames or S-Frames.
secondary.
3. UnNumbered Frames or U-Frames.
HDLC Frame Format
 I-Frames for transmitting both user information & Control
 The general HDLC frame with several fields information (piggybacking).
 It is bit-oriented protocol and are used bit stuffing for data  S-Frames only for control information (ACK)
transparency.  U-Frames for system management purpose like network
 HDLC frame begin with FLAG filed and end with FLAG filed. configuration etc.
 The other fields are  The I-Frame & U Frames contains data filed & S-frame without
Bits: 8 8 8 >=0 16 8 data field, the frame structures are
01111110 Address Control info FCS 01111110

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

20
 Data Link Layer Data Link Layer
Flag filed : defines the beginning & ending of the frame.  The following diagram shows control filed of different frames
Address:
 It always contains the address of the Secondary Station.
 If Primary Station Creates frame, it contains to address.
 If Secondary Station Creates frame, it contains from address.
 Address filed may be 1 byte to several bytes.
Control Field:
 The control filed is either 1 or 2 bytes.
 The systematic interpretation of bits specify the type of the frame.
 The control filed first bit is 0, indicates I-Frame.
 The control field first is 1 and second bit is 0, indicates S-Frame.
 The control filed first is 1 and second bit is 1, indicates U-Frame.

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

Data Link Layer Data Link Layer

Control filed of I-Frames Control Field of S-Frame

 The first bit defines the type.

 The next three bits N(S) defines the sequence number of the  S-Frames are used for flow control & error control whenever
frame. piggybacking is either absent or impossible.
 The last three bits N(R) defines the sequence number of the ACK,  S-Frames do not have information field.
when piggybacking is used.  If the first two bits are 1 0 called S-Frame.
 The P/F is a single bit with a dual purpose.  Last three bits corresponds to acknowledgement number.
 The field always set with 1 and it can be either poll or final.  The code filed indicates the type of the S-Frame itself.
 It means poll, transmission from primary station to secondary.  P/F filed corresponds to poll or final.
 It means final, transmission from secondary to primary.  The two bit code field represents four different S-Frames.

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

21
 Data Link Layer Data Link Layer
Different S-Frames are Control Field of U-Frames

[Link] Code field Frame type Description

1 00 RR Receive ready
2 10 RNR Receive Not Ready  U-Frames are network management frames.
3 01 REJ Reject  U-Frames contains information field, but not for user data.
4 11 SREJ Selective Reject  The U-Frame performs various network management tasks.
 The code fields are used to identify types of U-Frame itself.
 RR indicates receiver ready to accept the next frame, the value of N(R)
is ACK number.  There are 5 code fields and 32 different U-Frames.
 RNR indicates receiver is busy can not receive more frames, the value of  For Ex:
N(R) is ACK number.  00 001  Communication is NRM.
 SREJ indicates NAK for selective repeat ARQ, the value of N(R) is  11 110  Communication Asynchronous (ARM).
damaged frame number or NAK number.
 00 010  Disconnect the Communication.
 REJ indicates NAK, but not like selective repeat ARQ, its for go-back-
N ARQ.
JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

Data Link Layer Data Link Layer

Information Field: Pont to Point Protocol (PPP)
 It contains the data received from the network Layer.  Features of PPP
FCS (Frame Check Sequence) 1. PPP defines the format of the frame to be exchanged b/w devices.
 This filed is used for error detection. 2. PPP defines how two devices can negotiate the establishment of
 It contains CRC. the link and the exchange of the data.
The Data Link Layer in the Internet 3. PPP defines how to devices can authenticate each other.
 The internet consists of individual machines (hosts and routers)  Absent services are
and communication infrastructure. 1. PPP does not provide flow control.
 The home PCs connecting to ISP over point-point link. 2. PPP provide very simple error control mechanism.
 The organization LANs connect to internet through their routers. 3. PPP does not provide mechanism for multipoint links.
 So an individual user or an organization connect to nearest ISP
router through point-point link only.
 The special data link protocol designed for internet, is point to
point protocol (PPP).
JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

22
 Data Link Layer Data Link Layer
Framing Checksum: it is normally 2 or 4 byte filed.
 PPP frame format consist of following fields Following diagram shows PPP communication process

 Flag: Which indicates beginning of the frame.

 Address: does nothing.
 Control: does nothing.
 Protocol: upper layer to which frame must be delivered (eg, PPP-
LCP, IP, PAP,CHAP) etc).
 info/pay load: is a variable length, up to some maximum size.

JPR COMPUTER NETWORKS JPR COMPUTER NETWORKS

23