Topics

Lecture 4 Data Link Layer

Dr. Thaier Hayajneh h h Department of Computer Engineering The Hashemite University 408450 Computer Networks, Fall 2011/2012 http://www.hlms.hu.edu/

Introduction Flow control

Error detection

Stop and wait Sliding window

Error h dli E handling

Parity Checksums Cyclic redundancy check (CRC) Error correction Retransmission (Automatic Repeat Request ARQ)
Stop and wait Go-back-N Selective reject (selective repeat)

Data Link Layer: Background

Flow Control: Assumptions and Problems

Initial Finite capacity in the buffer of the receiver. Need for flow control Stop-n-Wait protocol - Sender sends a frame and waits for a signal in the form of a dummy frame No seq no. is o o. s required since the line is still error free The channel is noisy, frames may be damaged or lost y g Good scene : data frame reaches intact, ack sent back and received, next frame sent received Bad scene : Data frame damaged or lost hence no ack sender times out and resends .. No problems Data frame reaches intact but Ack lost .. Times out ..resends.. Receiver resends receives duplicate frames. Problem!!

Physical layer provides means to transfer frames over a link: Physical medium Data transmission with electromagnetic waves
Synchronization Remaining problems to be solved Adapt sender to receiver rate E Errors in frames and l i f d lossage of f

Line coding (low-pass channel) Modulation (band-pass channel) ( p )

detected and managed ...

f frames should b h ld be

Simplex Protocol Infinite buffer capacity with the receiver Error free transmission Network layer at the senders end is always ready with data No need for flow control 8-bit flag
4

8-bit flag

Header address and control

Data

Trailer error control

Solution : Keep a sequence number for each frame to distinguish between the new frame and a duplicate frame.

Data Link Layer: Background

Line Discipline

Data link layer is responsible for hop-to-hop packet y p p pp delivery (local responsibility). Flow Control and error control are the main functions of the data link layer.

Line Discipline

ENQ/ACK

Determine the direction of communication Make sure that receiver is ready to accept or signal the sender to start Two ways: y

Enquiry / Acknowledgment (ENQ/ACK) Dedicated line between hosts Poll S l P ll / Select Multipoint connections

Dedicated line between hosts, no problem of addressing g Coordinates which device may start transmission, and if the receiver is ready and enabled If both hosts have equal ranks, either can initiate the process Otherwise, only higher-ranked h t is allowed t Oth i l hi h k d host i ll d to start the transmission request Can be run in either half-duplex or full-duplex modes half duplex full duplex

ENQ/ACK
Host A
ENQ Establishment ACK Data ACK Data Transfer

Poll / Select
Host B

Data ACK EOT Termination

Establishment: Host B responds either with ACK or NAK Host A tries to send ENQ three times before concluding that Host B is down

Multipoint connections One primary and multiple secondary hosts Communication between secondary devices go over the primary Select mode is used when primary has something to send to a secondary (downstream) Poll mode is used to solicit transmissions from a secondary to the primary (upstream) y p y( p ) Address must be contained in all packets

10

Poll / Select
Primary
SEL ACK

Poll / Select
Sec. A Sec. B

Data ACK

11

Data ACK

Select mode SEL packet contains address of B B can response either by ACK or y NAK Primary sends one or more data d t packets, which are ACKed by B y

Primary

Sec. A Sec. B

Poll NAK Poll Data

ACK

Poll mode Poll packet contains address of recipient If the intended secondary has no data to send, replies p with NAK Data is ACKed by the i th primary

12

Why Flow Control?

Flow Control

Problem: Sender can overload receiver Frames arrive too fast

Control mechanisms

In many cases, the receiver is more complicated than the sender Error detection, frame/packet analysis, address lookup

Stop and wait Sliding window

Frames are stored in a buffer before they are processed F d b ff b f h d

(We dont worry about frame errors and losses for now)

Receiver buffers can overflow and frames be lost

Prevent loss of frames Combined mechanisms for flow control and error control Based on retransmission

13

14

Stop and Wait

Link Utilization
Sender sends one frame

U
Tttr
Frame

Waits for acknowledgement Next frame sent after acknowledgement When ready to receive next frame

Ttr Ttot

Receiver sends acknowledgement

Ttot
Acknowledgement

Ttr Ttot

Frame

Transmission time Time between first and last bit of a frame Frame length (bits) divided by link capacity Total time Time from first bit is sent until acknowledgement arrives How long before sender can start sending again Assumptions A i Zero transmission time for acknowledgements Zero processing time in sender and receiver

Ttr

Acknowledgement

Ttr
Sender Receiver

Transmission time Total time

Ttot

Link Utilization
U
Tttr
F Ttot T pr
Acknowledgement
A T pr

Utilization

Ttr F A Ttr T pr T pr
Frame

Propagation time

How large part of the total time (Ttot) is used for transmission? Ttr is the time to send a frame (transmission time)

Time for one bit to p p g propagate over the link

Time between first and last bit of the frame Given by the frame length (bits) divided by the link capacity (b/s) Time to distribute a bit over the link Given by the link length divided by the signal propagation speed y g y g p p g p

Link length divided by propagation speed

Tpr is the propagation time of the link

Approximately speed of light U = Ttr /Ttot = Ttr /( Ttr+ 2Tpr) = 1 / (1 + 2a) ( ( )

Ttr

Frame

Link is characterized by the parameter a= Tpr / Ttr Large a means poor link utilization

F Ttot T pr

F Tpr

A Tpr

Acknowledgement

F Tpr

Propagation time for frame Propagation time for acknowledgement

19

Sender

Receiver

A Tpr

Link UtilizationSymmetrical Links

For symmetrical links:
F A Tpr T pr Tpr

Utilization
Tpr < Ttr (a < 1): max one frame fits on the link
a 0,01 to 0,1 , , 10-5 0,48 U 0,98 to 0,83 , , 0,99998 0,51 Situation LANs Modem, 100m Modem, 5000km

T pr Ttr 1 , where a Ttr 2T pr 1 2a Ttr

The parameter a is the relation between length of link and length of p g g frame (in meters) f (i ) Length of a bit: Link capacity divided by signal propagation speed Speed of light in optical fiber is about 2 108 m/s

Tpr > Ttr ( >1) multiple f (a >1): lti l frames on the link th li k
a 3 ,8 8 U 0,12 S it u a t i o n 4k b fram e on 5 6 k b p s s ate llite lin k 4k b fram e on 3 2 M b p s s ate ll ite lin k

1 kb/s: 200 km 1 Mb/s: 200 m 1 Gb/s: 20 cm

2160

0,00 0 23 1

Sliding Window

Sliding Window
Increase utilization b sending N f I ili i by di frames before waiting

Frame are numbered Sequence number The sender may send N frames before receiving an acknowledgment

Ttr Ttot Ttr Ttr Ttr Ttot Ttr Ttr

Sender

Need flow control mechanism

N is the window size An acknowledgement means that the receiver is prepared to receive N more frames, starting from the sequence number specified in the acknowledgement Optimization: acknowledge multiple frames with the same acknowledgement

To prevent buffer overflow at the receiver

The receiver acknowledges frames by sending the sequence number of the next expected frame

N is window size Frame sequence numbers Acknowledgements contain sequence numbers n mbers Sequence number of the next

Receiver

frame the receiver is ready to accept

24

How Does it Work? At the sender (N = 4) ( )

Frames that may be sent Last frame sent

At the reciever
Receiver window:

01234567

Shrink from left as frames are received Expand from right as ACKs are sent

Shrinks when frames are sent

Grows when acknowledgements arrive

25

26

Sender Sliding Window

Receiver Sliding Window

Example (N = 3)
Window 01234567 01234567 01234567 01234567 01234567 01234567 01234567 01234567 F0 F1 F2 ACK2

F3 ACK3 ACK4

27

28

Sender

Receiver

Example (N = 6)
Window 0-5 1-5 15 2-5 3-5 3-7 4-7 4-8 4-9 F0 F1 F2 ACK2

Utilization
U = NTttr / Tttott = NTttr /( Tttr+ 2Tpr) = N / (1 + 2a)
where

a = Tpr / Ttr

F3 ACK3 ACK4

NTtr> Ttr+2Tpr U > 1 Sender receives acknowledgement before window is closed Sender may send without stopping (Although true utilization can never be more than 100%) NTtr< Ttr+2Tpr U < 1

Window closes after N Ttr Sender must stop and wait for acknowledgement Utilization is the fraction of the time when the sender does not wait

29

Sender

Receiver

31

Sliding Window Utilization

U NTtr N Ttr 2Tpr 1 2a p

How Large Window?

Ttr Ttr Ttr Ttr Ttr Ttr

Sender

T pr

U>1 Sender receives acknowledgement before window is closed Sender may send without stopping (Although true utilization can never be more than 100%) b th U<1

N = 1 stop-and-wait p Small a small N Local area network: N = 8 3 bits Large a l L large N

Window closes after N frames Sender must stop and wait for acknowledgement Utilization is the fraction of the time when the sender does not wait

TCP uses 32-bit sequence number

Byte number

Receiver
33

Acknowledgements

Sliding Window Protocols

Types of acknowledgements

Positive

ACK (acknowledgement)

HDLC: RR (receiver ready)

Negative

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

NACK (negative acknowledgement)

HDLC: RNR (receiver not ready)

Indicates sequence number of next expected frame When and how is the acknowledgement sent?

As a separate frame Together with data from the receiver to the sender

Piggybacking

34

35

Automatic Repeat Request (ARQ)

Stop and wait Stop-and-wait ARQ

Error controlwhen frames or acknowledgements are lost g

Positive acknowledgements ACK Problem: acknowledgements can be lost or delayed Therefore the acknowledgements are numbered

Based on flow control

Stop-and-wait Stop and wait flow control

Indicates the sequence number of the next expected frame

Stop-and-wait ARQ Alternating Bit Protocol

Alternating Bit Protocolsequence numbers 0 and 1

Two sequence numbers0 and 1

Sliding window flow control

Go-back-N ARQ Selective reject Selective-reject ARQ

37

36

Stop and wait Stop-and-wait ARQ

Stop-and-wait ARQ: Lost Acknowledgement

Sender
S=0

Sender Variable S: sequence number of last frame sent Keeps a copy of last frame sent Starts a timer when a frame is sent Stops timer when ACK is received Retransmits if time out (and restarts timer) Receiver

Receiver

Sender

Receiver

F0 ACK1

R=0 R=1

No ACK for F1 Sender time out

S=0

F0 ACK1

R=0 R=1

Retransmission
S=1

S=1

F1

Time out

Receiver receives wrong sequence number

F1 ACK0
R=0

Variable R: next expected sequence number When a frame is received, sends an ACK with next expected sequence number Drops received packet if wrong sequence number
S=0

Discards f Di d frame Sends ACK with expected sequence number (0) q ( )

Time out

F1 ACK0 F0
R=0

F1 ACK0
S=0

Sender may send next frame

F0
R=1

Continuous ARQ

Go back N Go-back-N ARQ

Stop and wait Stop-and-wait ARQ is simple but inefficient Continuous ARQ (multiframe ARQ)

Sequence numbers with sliding window ACK and NACK Time out

Based on sliding window flow control g Sender May send N frames without acknowledgement Copies of all unacknowledged frames are kept in a buffer Time out: retransmit all unacknowledged frames Receiver Discards frames with unexpected sequence numbers

40

41

Example: Lost Acknowledgement (N = 3)

Sender Receiver

Window Size Versus Sequence Numbers

Sender With k-bit sequence numbers, k bit window size can be at most 2k-1 For example: Sequence numbers q 0-3 (k = 2) Window size 2k = 4 (incorrectly)

F0 F1 F2 ACK3 Time out Ti F0 F1 F2 ACK3 F3

42

F0 F1 F2 F3 ACK0 F0 F1 F2 F3 ACK0

Receiver

Time out

Duplicates!

Selective Repeat ARQ

Selective Repeat ARQ

Sometimes also called Selective Reject ARQ (SREJ) Only retransmit frames that are lost Negativ acknowledgement NAK (SREJ) Time out Receiver has a receive window Only frames with sequence number within receive window are accepted Advantage Minimizes the number of retransmissions More suitable for noisy links Disadvantages More buffering at receiver N d to keep out-of-order frames in a buffer Needs k f d f b ff Window size cannot be larger than one-half the number of sequence numbers

46

47

Window Size in Selective Repeat ARQ

Transmission Errors

Lost frame

Framing error

Corrupted frame (bit errors) Single bit error Burst errors B

Whole sequences of bits are corrupted External noise

48

49

Error DetectionBasic Idea Detection Basic

Parity Check
1001010 1
Parity bit (even parity)

f(Data)

Data

Simple parity check: extra bit (parity bit) is added to the data unit

Add extra (redundant) information for detecting errors Parity check Checksum Cyclic redundancy check (CRC) Sender computes function over data, and appends result Receiver computes same function, and compares the results function If the results differ, there was an error

Numbers of 1s in the unit is always even (even parity) or odd ( even parity ) (odd parity) Receiver checks number of 1s Simple: P= 1 0 0 1 1 0 for even parity Inexpensive: cost is one extra bit per data unit p p Only detects single bit errors, and burst errors with odd number of bit errors
51

Advantages

Disadvantage

50

Two dimensional Two-dimensional Parity

Cyclic Redundancy Check (CRC)

The data M is treated as a sequence of bits Predefined binary word P (generator) of length n+1 Sender generates M by adding n CRC bits to M Such that M is evenly divided by P M M is sent Receiver receives M If remainder of M divided by P is zero then M = M y Otherwise: bit error detected, discard the data

52

53

CRC Calculation Using Binary Division

CRC Control at Receiver

Append 00 to M pp Binary subtraction (xor) of 3 bits

If first bit is 1

subtract P (Put 1 in quotient) Copy down next bit subtract 000 (Put 0 in quotient) Copy down next bit py

If first bit is 0

Append remainder to data as checksum

10110 101 1001100 101 011 000 111 101 100 101 010 000 10

n=2 P = 101 M = 10011 M = 1001110

Divide received data with P If remainder is 00, data is OK Strip off CRC bits Otherwise discard data

10110 101 1001110 101 011 000 111 101 101 101 000 000 00

n=2 P = 101 M = 10011 M = 1001110

54

55

Generator Polynomials

CRC

Binary numbers can be represented as polynomials (CRC is a called polynomial code checksum) Bit value is coefficient of a term Exponent indicates the bit position, starting at 0 p p g Example: 100111 P(X) = 1 X5 + 0 X4 + 0 X3 + 1 X2 + 1 X + 1 X0 P(X) = X5 + X2 + X + 1 ( ) Standard polynomials ITU-16: X16 + X12 + X5 + 1 ITU 32: ITU-32: X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X + 1

Effective error detection

All burst errors that affect an odd number of bits All burst errors of length less than or equal to g q degree of polynomial With high probability longer errors Shift register circuit CRC often appended t th data (t il ) ft d d to the d t (trailer)

Simple implementation in hardware

56

57

Checksum

Checksum

Treat the data as a sequence of integer numbers in binary format Divide data into k units, with n bits in each Compute the sum of all k units using ones complement arithmetic Complement the sum and append the result to the data Receiver Compute the sum over the data p Complement the sum If the result equals zero, the data is accepted (otherwise j ) rejected)

Less effective than CRC L ff h

Easier to implement in software all errors involving an odd number of bits Most errors involving an even number of bits Two opposite bit inversions may balance out each other

Detects

58

60

Correction of Errors

Data Link Example: HDLC

Forward Error Correction (FEC) Error-correcting codes Replace CRC, checksum etc with a code that can automatically correct the error Needs more redundancy bits Retransmission (ARQ) R t i i Can be used both for bit errors and frame loss A frame with bit errors is dropped (lost)

High-level Data Link Control Half-duplex Half duplex and full duplex full-duplex Point-to-point and multipoint links Normal response mode (NRM) and asynchronous balance mode (ABM)

61

62

HDLC Normal Response Mode

HDLC Asynchronous Balanced Mode

Unbalanced Point-to-point and multipoint links

64

Three HDLC Frame Types

HDLC Frame Format

Information frames (I-frames) User data Acknowledgements

Piggybacking

Supervisory frames (S-frames) S i f (S f ) Control information related

RRReceive Ready (ACK) RNRReceive not Ready ( y (ACK, receiver busy) , y) REJReject (REJ)(NACK, Go-back-N) SREJSelective Reject (NACK, Selective-repear ARQ) Link setup and tear-down

to user data

Unnumber frames (U-frames) S stem mana ement System management

Setting transmission mode, etc

Flag Start and end Binary 01111110 y 7E16 Address Of secondary

Control Information U User data d t Management information FCS field 2- or 4-byte CRC y

65

66

HDLC Bit Stuffing

Data Link Example: (PPP)

Data may contain flag pattern 01111110 Sender: insert (stuff) an extra 0 after five 1s Receiver: remove 0 after five 1s

Point-to-point Protocol Control and management of data transfer over physical (pointto-point) links Dedicated link with two stations Traditional modem, DSL, etc Based on HDLC frame format

PPP Protocol Family

PPP Example

Link Control Protocol (LCP) Establish, disconnect link Negotiate optionsmaximum receive unit, authentication, compression Authentication Password Authentication Protocol (PAP) Challenge Handshake Authentication Protocol (CHAP) Network Control Protocol (NCP) Internetwork Protocol Control Protocol (IPCP) ( )

69

70

Summary

Reading Instructions

Behrouz A. Forouzan, Data Communications and Networking,

Flow control

Bit error detection

Stop and wait Sliding window Parity control P l Checksum Cyklic redundancy check (CRC)

Detecting frame loss: sequence numbers Error control: retransmision (ARQ)

Two examples:

Stop and wait ARQ Go-back-N ARQ Selective reject ARQ

10 Error Detection and Correction 10.1 Types of errors 10.2 Detection 10.3 Error correction 11 Data Link Control and Protocols 11.1 Flow and error control 11.2 Stop-and-wait ARQ p 11.3 Go-back-N ARQ 11.4 Selective Repeat ARQ 11.5 HDLC 12 Point-to-point access: PPP

HDLC PPP

71

72