Data Communication

Chapter 7

Data Link Control Protocols

Flow Control

• Ensuring the sending entity does not overwhelm the receiving entity
• Preventing buffer overflow
• Transmission time
• Time taken to emit all bits into medium
• Propagation time (a=B/L)
• Time for a bit to traverse the link
• B=R*d/v: length of a link in bits
• L: # of bits\frame

​

2

Model of Frame Transmission

3

Stop and Wait

• Source transmits frame
• Destination receives frame and replies with acknowledgement
• Source waits for ACK before sending next frame
• Destination can stop flow by not sending ACK
• Works well for a few large frames

4

Fragmentation

• Large block of data may be split into small frames
• Limited buffer size
• Errors detected sooner (when whole frame received)
• On error, retransmission of smaller frames is needed
• Prevents one station occupying link for long periods
• Stop and wait becomes inadequate for large data and long distance transmission.

​

5

Stop and Wait Link Utilization

6

Sliding Windows Flow Control

• Allow multiple frames to be in transit
• Receiver has buffer of W frames long
• Transmitter can send up to W frames without ACK
• Each frame is numbered
• ACK includes number of next frame expected
• Sequence number bounded by size of field (k)
• Frames are numbered modulo 2^k

7

Sliding Window Diagram

8

Example Sliding Window

9

Sliding Window Enhancements

• Receiver can acknowledge frames without permitting further transmission (Receive Not Ready: RNR)
• Must send a normal acknowledge to resume
• If duplex, use piggybacking (data frame contains two fields Seq+ACK)
• If no data to send, use acknowledgement frame (RR)
• If data but no acknowledgement to send, send last acknowledgement number again, or have ACK valid flag (TCP)

10

Performance Issues

11

Performance Issues

• See attachment

12

Error Detection

• Additional bits added by transmitter for error detection code
• Parity
• Value of parity bit is such that character has even (even parity) or odd (odd parity) number of ones
• Even number of bit errors goes undetected

13

Cyclic Redundancy Check

• For a block of k bits transmitter generates n bit sequence
• Transmit k+n bits which is exactly divisible by some number
• Receive divides frame by that number
• If no remainder, assume no error
• For math, see Stallings chapter 7

14

Error Control

• Detection and correction of errors
• Lost frames
• Damaged frames
• Automatic repeat request (ARQ)
• Error detection
• Positive acknowledgment
• Retransmission after timeout
• Negative acknowledgement and retransmission

15

Automatic Repeat Request (ARQ)

• Stop and wait
• Go back N
• Selective reject (selective retransmission)

​

16

Stop and Wait ARQ

• Source transmits single frame
• Wait for ACK
• If received frame damaged, discard it
• Transmitter has timeout
• If no ACK within timeout, retransmit
• If ACK damaged,transmitter will not recognize it
• Transmitter will retransmit
• Receive gets two copies of frame
• Use ACK0 and ACK1 to prevent two copies of a frame

17

Stop and Wait -�Diagram

18

Stop and Wait - Pros and Cons

• Simple
• Inefficient

​

19

Go Back N ARQ (1)

• Based on sliding window
• If no error, ACK as usual with next frame expected
• Use window to control number of outstanding frames
• If error, reply with rejection
• Discard that frame and all future frames until error frame received correctly
• Transmitter must go back and retransmit that frame and all subsequent frames

20

Go Back N - Damaged Frame

• Receiver detects error in frame i
• Receiver sends rejection-i
• Transmitter gets rejection-i
• Transmitter retransmits frame i and all subsequent

21

Go Back N - Lost Frame (1)

• Frame i lost
• Transmitter sends i+1
• Receiver gets frame i+1 out of sequence
• Receiver send reject i
• Transmitter goes back to frame i and retransmits

22

Go Back N - Lost Frame (2)

• Frame i lost and no additional frame sent
• Receiver gets nothing and returns neither acknowledgement nor rejection
• Transmitter times out and sends acknowledgement frame with P bit set to 1
• Receiver interprets this as command which it acknowledges with the number of the next frame it expects (frame i )
• Transmitter then retransmits frame i

23

Go Back N - Damaged Acknowledgement

• Receiver gets frame i and send acknowledgement (i+1) which is lost
• Acknowledgements are cumulative, so next acknowledgement (i+n) may arrive before transmitter times out on frame i
• If transmitter times out, it sends acknowledgement with P bit set as before
• This can be repeated a number of times before a reset procedure is initiated

​

​

24

Go Back N - Damaged Rejection

• As for lost frame (2)

25

Go Back N - �Diagram

26

Selective Reject ARQ

• Also called selective retransmission
• Only rejected frames are retransmitted
• Subsequent frames are accepted by the receiver and buffered
• Minimizes retransmission
• Receiver must maintain large enough buffer
• More complex logic in transmitter and receiver.

​

27

Selective Reject -�Diagram

28

High-Level Data Link Control

• HDLC
• ISO 33009, ISO 4335

29

HDLC Station Types

• Primary station
• Controls operation of link
• Frames issued are called commands
• Maintains separate logical link to each secondary station
• Secondary station
• Under control of primary station
• Frames issued called responses
• Combined station
• May issue commands and responses

​

30

HDLC Link Configurations

• Unbalanced
• One primary and one or more secondary stations
• Supports full duplex and half duplex
• Balanced
• Two combined stations
• Supports full duplex and half duplex

​

31

HDLC Transfer Modes (1)

• Normal Response Mode (NRM)
• Unbalanced configuration
• Primary initiates transfer to secondary
• Secondary may only transmit data in response to command from primary
• Used on multi-drop lines
• Host computer as primary
• Terminals as secondary

32

HDLC Transfer Modes (2)

• Asynchronous Balanced Mode (ABM)
• Balanced configuration
• Either station may initiate transmission without receiving permission
• Most widely used
• No polling overhead

​

33

HDLC Transfer Modes (3)

• Asynchronous Response Mode (ARM)
• Unbalanced configuration
• Secondary may initiate transmission without permission form primary
• Primary responsible for line
• rarely used

​

34

HLDC Frame Structure

• Synchronous transmission
• All transmissions in frames
• Single frame format for all data and control exchanges

​

35

Frame Structure

36

Flag Fields

• Delimit frame at both ends
• 01111110
• May close one frame and open another
• Receiver hunts for flag sequence to synchronize
• Bit stuffing used to avoid confusion with data containing 01111110
• 0 inserted after every sequence of five 1s
• If receiver detects five 1s it checks next bit
• If 0, it is deleted
• If 1 and seventh bit is 0, accept as flag
• If sixth and seventh bits 1, sender is indicating abort

37

Bit Stuffing

• Example with �possible errors

38

Address Field

• Identifies secondary station that sent or will receive frame
• Usually 8 bits long
• May be extended to multiples of 7 bits
• LSB of each octet indicates that it is the last octet (1) or not (0)
• All ones (11111111) is broadcast

39

Control Field

• Different for different frame type
• Information - data to be transmitted to user (next layer up)
• Flow and error control piggybacked on information frames
• Supervisory - ARQ when piggyback not used
• Unnumbered - supplementary link control
• First one or two bits of control filed identify frame type
• Remaining bits explained later

​

​

40

Control Field Diagram

41

Poll/Final Bit

• Use depends on context
• Command frame
• P bit
• 1 to solicit (poll) response from peer
• Response frame
• F bit
• 1 indicates response to soliciting command

​

42

Information Field

• Only in information and some unnumbered frames
• Must contain integral number of octets
• Variable length

43

Frame Check Sequence Field

• FCS
• Error detection
• 16 bit CRC
• Optional 32 bit CRC

​

44

HDLC Operation

• Exchange of information, supervisory and unnumbered frames
• Three phases
• Initialization
• Data transfer
• Disconnect

45

Examples of Operation (1)

46

Examples of Operation (2)

47