Data Link Control Protocols

7-1

Data Link Control

Protocols

Raj Jain

Washington University

Saint Louis, MO 63131

[email protected]

These slides are available on-line at:

http://www.cse.wustl.edu/~jain/cse473-05/

7-2

Overview

q Flow Control

q Effect of propagation delay, speed, frame size

q Error Recovery

q HDLC

7-3

Flow Control

q Flow Control Goals:

1. Sender does not flood the receiver,

2. Maximize throughput

q Sender throttled until receiver grants permission

7-4

Space

-

Time Diagrams

Space

Time

7-5

Stop and Wait Flow Control

Data

Ack

Data

t

frame

t

prop

=

1

2α + 1

U=

2t

prop

+t

frame

t

frame

α =

t

prop

t

frame

=

Distance/Speed of Signal

Bits Transmitted /Bit rate

=

Distance × Bit rate

Bits Transmitted × Speed of Signal

Light in vacuum

= 300 m/μs

Light in fiber

= 200 m/μs

Electricity

= 250 m/μs

7-6

Utilization: Examples

q Satellite Link: Propagation Delay t

prop

= 270 ms

Frame Size = 500 Bytes = 4 kb

Data rate = 56 kbps ⇒ t

frame

= 4/56 = 71 ms

α = t

prop

/t

frame

= 270/71 = 3.8

U = 1/(2α+1) = 0.12

q Short Link: 1 km = 5 μs,

Rate=10 Mbps,

Frame=500 bytes ⇒ t

frame

= 4k/10M= 400 μs

α=t

prop

/t

frame

=5/400=0.012 ⇒ U=1/(2α+1)=0.98

Note: The textbook uses B for t

prop

and L for t

frame

7-7

Efficiency Principle

q For all protocols, the maximum utilization (efficiency)

is a non-increasing function of α.

α

Max

Utilization

Not Possible

Protocol 1

Protocol 2

Best

possible

α =

t

prop

t

frame

=

Distance × Bit rate

Bits Transmitted ×Speed of Signal

7-8

Sliding Window Protocols

q Window = Set of sequence numbers to send/receive

q Sender window

q Sender window increases when ack received

q Packets in sender window must be buffered at

source

7-9

Sliding Window Diagram

7-10

Sliding Window Example

7-11

Sliding Window Protocol Efficiency

Data

Ack

t

frame

t

prop

U=

W t

frame

2t

prop

+t

frame

=

W

2α+1

1 if W>2α+1

7-12

Effect of Window Size

α

U

q Larger window is better for larger α

7-13

Piggybacking

Data

Data+Ack

t

frame

t

prop

Header Ack Data

Header Data

7-14

Error Control

q Error Control = Deliver frames without error, in the proper

order to network layer

q Error control Mechanisms:

q Ack/Nack: Provide sender some feedback about other end

q Time-out: for the case when entire packet or ack is lost

q Sequence numbers: to distinguish retransmissions from

originals

Timeout

7-15

Stop

-

and

-

Wait ARQ

Automatic

Repeat

reQuest

(ARQ)

7-16

Go

-

Back

-

N ARQ

q Receiver does not cache out-of-order frames

q Sender has to go back and retransmit all frames after

the lost frame

RcvrSender

1

Nack 1

1

0

1

2

3

7-17

Go

-

back

-

N (Cont)

All possible scenarios are handled:

1. Damaged Frame:

q Frame received with error

q Frame lost

q Last frame lost

2. Damaged Ack:

q One ack lost, next one makes it

q All acks lost

3. Damaged Nack:

q Maximum Window = 2

n

-1

with n-bit sequence numbers

7-18

Selective Reject ARQ

q Receiver caches out-of-order frames

q Sender retransmits only the lost frame

RcvrSender

1

Nack 1

1

0

1

2

4

3

5

7-19

Selective Reject: Window Size

0

1

2

3

4

5

6

7

0

Ack

Sequence number space > 2 window size

Window size <

2

n-1

Timeout

7-20

Performance: Maximum Utilization

q Stop and Wait Flow Control: U = 1/(1+2α)

q Window Flow Control:

q Stop and Wait ARQ: U = (1-P)/(1+2α)

q Go-back-N ARQ:

q Selective Reject ARQ:

U =

1W>2α+1

W/(2α+1) W< 2α+1

{

U =

(1-P)/(1+2αP) W> 2α+1

W(1-P)/[(2α+1)(1-P+wP)] W< 2α+1

{

U =

(1-P) W> 2α+1

W(1-P)/(2α+1) W< 2α+1

{

7-21

Performance Comparison

1.0

0.8

0.6

0.4

0.2

0.0

0.1 1 10 100 1000

α

Utilization

Stop-and-wait

W= 127 Go-back-N

W=7 Go-back-N &

W= 7 Selective-reject

W= 127 Selective-reject

More bps or longer distance

7-22

HDLC Family

q Synchronous Data Link Control (SDLC): IBM

q High-Level Data Link Control (HDLC): ISO

q Link Access Procedure-Balanced (LAPB): X.25

q Link Access Procedure for the D channel (LAPD): ISDN

q Link Access Procedure for modems (LAPM): V.42

q Link Access Procedure for half-duplex links (LAPX): Teletex

q Point-to-Point Protocol (PPP): Internet

q Logical Link Control (LLC): IEEE

q Advanced Data Communications Control Procedures (ADCCP): ANSI

q V.120 and Frame relay also use HDLC

7-23

q Primary station: Issue commands

q Secondary Station:Issue responses

q Combined Station: Both primary and secondary

q Unbalanced Configuration: One or more secondary

q Balanced Configuration: Two combined station

q Normal Response Mode (NRM): Response from secondary

q Asynchronous Balanced Mode (ABM): Combined Station

q Asynchronous Response Mode (ARM): Secondary may respond before

command

HDLC

7-24

HDLC Frame Structure

Frame

Format

Control Field Format

Extended Address Field

Extended Control Field

......

0 N(S) P/F N(R)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

1 2 3 4 5 6 7 8

1 0 S 0 0 0 0 P/F N(R)

Information

Supervisory

N(S)= Send sequence number N(R)= Receive sequence number

S= Supervisory function bits M= Unnumbered bits P/F= Poll/final bit

I: Information

S: Supervisory

U: Unnumbered

8

8n 16 or 32 8

Address Control INFORMATION FCS FLAG

Extendable Extendable

0 N(S) P/F N(R)

1 0 S P/F N(R)

1 1 M P/F M

0

1

8n

Flag

8

bits

7-25

111111111111011111101111110

After bit-stuffing

1111101111101101111101011111010

Bit Stuffing

q HDLC Flag = 01111110

q Every where else in the frame:

Replace 11111 with 111110

Original Pattern

7-26

(b) An inverted bit splits a frame in two

Transmitted

(c) An inverted bit merges two frames

Transmitted

Bit inverted

Flag

Flag Flag

Flag

FlagFlag

Received

Bit Stuffing (Cont)

7-27

HDLC Frames

q Information Frames: User data

q Piggybacked Acks: Next frame expected

q Poll/Final = Command/Response

q Supervisory Frames: Flow and error control

q Go back N and Selective Reject

q Final ⇒ No more data to send

q Unnumbered Frames: Control

q Mode setting commands and responses

q Information transfer commands and responses

q Recovery commands and responses

q Miscellaneous commands and responses

7-28

HDLC Commands and Responses

Name

Information (I)

Supervisory (S)

Receive Ready (RR)

Receive Not Ready (RNR)

Reject (REJ)

Selective Reject (SREJ)

Unnumbered (U)

Set Normal Response /

Extended Mode (SNRM / SNRME)

Set Asynchronous Response /

Extended Mode (SARM / SARME)

Set Asynchronous Balanced /

Extended Mode (SABM / SABME)

Set Initialization Mode (SIM)

Function

C/R

C

Description

Exchange user data

Positive Acknowledgement; ready

to receive I-frame

Positive acknowledgement; not

ready to receive

Negative acknowledgement; go

back N

Negative acknowledgement;

selective reject

Set mode;extended=two-octet control

field

Set mode;extended=two-octet control

field

Set mode;extended=two-octet control

field

Initialize link control functions in

addressed station

7-29

HDLC Commands and Responses (cont)

Name Function Description

Disconnect (DISC)

Unnumbered Acknowledgement (UA)

Disconnect Mode (DM)

Request Disconnect (RD)

Request Initialization Mode (RIM)

Unnumbered Information (UI)

Unnumbered Poll (UP)

Reset (RSET)

Exchange Identification (XID)

Test (TEST)

Frame Reject (FRMR)

C

R

C/R

C

C/R

R

Terminate logical link connection

Acknowledges acceptance of one of the

above set-mode commands

Secondary is logically disconnected

Request for DISC command

Initialization needed; request for SIM

command

Used to exchange control information

Used to solicit control information

Used for recovery; resets N(R), N(S)

Used to request/report identity and

status

Exchange identical information fields

for testing

Reports receipt of unacceptable frame

7-30

Examples of HDLC Operation

SABM

UA

DISC

UA

I,0,0

I,0,1

I,1,1

I,2,1

I,1,3

I,3,2

I,2,4

I,3,4

RR,4

I,3,0

RNR,4

RR,0,P

RNR,4,F

RR,0,P

RR,4,F

I,4,0

Timeout

(a) Link setup and

disconnect

(b) Two-way data

exchange

(c) Busy condition

7-31

Examples of Operation (Cont)

I,3,0

I,4,0

I,5,0

Rej, 4

I,4,0

I,5,0

I,6,0

I,2,0

RR,3

I,3,0

RR,0,P

RR,3,F

I,3,0

RR,4

(d) Reject Recovery (e) Timeout Recovery

*

Timeout

7-32

Summary

q Flow Control: Stop and Wait, Sliding window

q Effect of propagation delay, speed, frame size

q Piggybacking

q Error Control: Stop and wait ARQ, Go-back-N, Selective

Reject

q HDLC: Primary and secondary stations, NRM, ABM, ARM

q HDLC Frames: Flag, Bit stuffing, I-Frame, RR, RNR

7-33

Reading Assignment

q Read Chapter 7 and Appendix 7A of 7

th

edition of

Stallings.

q Do the following Exercise from the textbook:

7.8 (maximum link utilizations)

q There is no need to submit the answers.

Next Monday is the first mid-term.