Data Link Layer Protocol

Flow Control
Stop-and-Wait Data Link Protocols

• Such elementary protocols are also called PAR (Positive Acknowledgment with Retransmission)

or ARQ (Automatic Repeat reQuest).

• Data frames are transmitted in one direction (simplex protocols ) where each frame is individually

acknowledge by the receiver by a separate acknowledgment frame.

• The sender transmits one frame, starts a timer and waits for an acknowledgment frame from the

receiver before sending further frames.

• A time-out period is used where frames not acknowledged by the receiver are retransmitted automatically

by the sender.

• Frames received damaged by the receiver are not acknowledged and are retransmitted by the sender

when the expected acknowledgment is not received and timed out.

• A one bit sequence number (0 or 1) is used to distinguish between original data frames and duplicate

retransmitted frames to be discarded .

• Such protocols result in a substantial percentage of wasted bandwidth

and may fail under early time-out situations.

Simplex Stop-and-Wait Protocol

Simplex Positive Acknowledgment with Retransmission (PAR) Protocol

Simplex PAR Protocol (Effect of Errors)

Data Link Layer: Flow Control

(Sliding Window Protocols)

• These protocols allow both link nodes (A, B) to send and receive data and

acknowledgments simultaneously.

• Acknowledgments are piggybacked into an acknowledgment field in the
data frame header not as separate frames.

• If no new data frames are ready for transmission in a specified time, a
separate acknowledgment frame is generated to avoid time-out.
• Each outbound frame contains a sequence number ranging from 0 to
2 n-1 (n-bit field). N = 1 for stop-and-wait sliding window protocols.
• Sending window: A set of sequence numbers maintained by the sender
and correspond to frame sequence numbers of frames sent out but not
acknowledged.

• The maximum allowed size of the sending window w correspond to the
maximum number of frames the sender can transmit before receiving
any acknowledgment without blocking (pipelining).

• All frames in the sending window may be lost or damaged and thus must

be kept in memory or buffers until they are acknowledged.

Sliding Window Data Link Protocols

• Receiving window: A set of sequence numbers maintained by the receiver and
indicate the frames sequence numbers it is allowed to receive and acknowledge.

• The size of the receiving window is fixed at a specified initial size.

• Any frame received with a sequence number outside the receiving window is
discarded.

• The sending window and receiving window may not have the same upper or
lower limits or have the same size.

• When pipelining is used, an error in a frame is dealt with in one of two ways:

- Go back n:

• The receiver discards all subsequent frames and sends no acknowledgments.

• The sender times out and resends all the discarded frames starting with faulty frame.

- Selective repeat:

• The receiving data link stores all good frames received after a bad frame.

• Only the bad frame is retransmitted upon time-out by the sender.

Working of Sliding Window Protocol


Difference


Data Transmission

Channel Utilization & Data Throughput
For Sliding Window Protocols

b = Channel bandwidth or transmission rate bits/sec

FS = Frame size = # of data bits + # overhead bits = d + h

R = Channel round trip time

N = Send/receive window size

p = Probability frame a data frame is lost or damaged

• Ignoring errors, condition to maximize Utilization/Throughput:

Time to transmit N frames Round trip time

FS/b * N = (d + h)/b * N  R

Under this condition:

Maximum channel utilization  data size/frame size = d/(d + h)

Maximum data throughput  d/FS = d/(d + h ) * b

• Including the effect of errors only on data frame; assuming selective
repeat:

On the average p data frames have to be retransmitted

Under these condition: Total Data Frame overhead = h + p * FS

Maximum channel utilization  d/[(1 + p)*FS ]

Maximum data throughput  d/[(1 + p)*FS] * b

Operation Sequences for Sliding Window Protocol

Effect of Errors:

Finite State Machine Protocol Models

• A protocol may be represented by a finite state machine (protocol machine).

• States are chosen when the protocol machine is waiting for the next event (i.e

sending or receiving a protocol data unit PDU).

• The state of the complete protocol is the combination of the state of the two

protocol machines and the channel.

• The state of the channel depends on its content.

• Each state may have one or more transitions to other states when protocol events

occur.

• Incomplete state machine specification.

• Deadlock states.

Data Link Protocol Example:

HDLC - High-Level Data Link Control

• Bit-oriented protocol derived from IBM’s SNA data link
protocol SDLC (Synchronous Data Link Control).

• Frame Types: Information, Supervisory, Unnumbered.

• Uses sliding window with 3-bit sequence numbers.

• Uses CRC-CCITT for error control.

• Protocol commands include:

- DISC (DISConnect) used to disconnect a machine from the line. - SNRM (Set Normal Response

Mode) brings a machine online and sets one machine as channel master and the other as slave ( was
used for dumb terminals when connected to mainframes).

- SABM (Set Asynchronous Balanced Mode).

- FRMR (FRaMe Reject) rejects a frame with correct checksum with impossible structure.

Internet Data Link Protocols:

Serial Line IP (SLIP) RFC 1055

• Send raw IP packets with a flag byte (0xC0) at the end for framing with character

stuffing (data 0xC0 replaced with 0xDB 0xDC).

• Recent versions use header compression by omitting header fields in consecutive

packets and frames.

• Does not include any form of error detection or correction.

• Supports only one network protocol: IP (Internet Protocol).

• Dynamic IP address assignment not supported.

• Lacks any form of authentication.

Internet Data Link Protocols:

Point-to-Point Protocol (PPP)

• Uses standard HDLC framing byte (01111110) with error detection.

• Uses Link Control Protocol (LCP) for brining lines up, option negotiation, and to bring

lines down.

• Network layer options and configurations are negotiated independent of the network layer

used by utilizing different

NCPs (Network Control Protocol) packets for each supported network layer.

• Support for several packet types by using a protocol field:
- Network protocols (protocol field starts with 0): IP, IPX, AppleTalk etc.

- Negotiating protocols (protocol field starts with 1): LCP, NCP.

• PPP is used for both dial-up network access and for router-to- router communication in subnets.

PPP Frame Format