ch_11_edited.ppt you are you in the office and I will be there

Design

1. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Chapter 11
Data Link
Control
and
Protocols

2. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.1 Flow and Error Control11.1 Flow and Error Control
Flow Control
Error Control

3. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Flow control refers to a set of Flow control refers to a set of
procedures used to restrict the amount procedures used to restrict the amount
of data that the sender can send before of data that the sender can send before
waiting for acknowledgment.waiting for acknowledgment.
NoteNote::

4. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Error control in the data link layer is Error control in the data link layer is
based on automatic repeat request, based on automatic repeat request,
which is the retransmission of data. which is the retransmission of data.
NoteNote::

5. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.1 Flow and Error Control Mechanisms11.1 Flow and Error Control Mechanisms
» Stop-and-Wait ARQ
» Go-Back-N ARQ
» Selective-Repeat ARQ
» These are some times also referred as protocols.

6. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.2 Stop-and-Wait ARQ11.2 Stop-and-Wait ARQ
» Simplest Flow and Error Control Mechanism.
» The Sender has always a copy of the last frame, until it receives
acknowledgement from the receiver.
» For identification both data frames and acknowledgement (ACK) frames are
numbered alternatively 0 and 1.
» A data 0-Frame is acknowledged by an ACK-1 frame; indicating that data
0-Frame is received and receiver is ready for data 1-Frame. And vice versa.
» This numbering also allows for identification of data frames in case of
duplicate transmission.
» At receiver a damage or last frame is treated same as rejected frame and
so NO acknowledgement is sent to sender.
» The sender has a control Variable, called S, which holds the number of the
recently sent frame (0 or 1), Similarly receiver has also a control variable R.
that holds the number of next frame expected (0 or 1)

7. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.2 Stop-and-Wait ARQ11.2 Stop-and-Wait ARQ
» The sender has a timer, when it sends a frame the timer start functioning
and after a set time, when no acknowledgement is received it RESENDS.
» The receiver sends only POSITIVE acknowledgements for frames. So NO
acknowledgement means the FRAME is LOST.

8. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
In the transmission of frame we have In the transmission of frame we have
four situations:four situations:
Normal OperationNormal Operation
The frame is lostThe frame is lost
The Acknowledgement is lostThe Acknowledgement is lost
The acknowledgement is delayed The acknowledgement is delayed
STOP-AND-WAIT ARQ operationSTOP-AND-WAIT ARQ operation

9. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
STOP-AND-WAIT ARQ: Normal OperationSTOP-AND-WAIT ARQ: Normal Operation
» The sender sends frame 0 and waits for ACK-1.
» When ACK-1 is received the frame-1 is sent and
again waits for ACK-0.
» When ACK-0 is received means that frame 1 is
received successfully, frame-0 is sent.

10. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.1 Normal operation

11. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
STOP-AND-WAIT ARQ: Lost or Damage FrameSTOP-AND-WAIT ARQ: Lost or Damage Frame
» When receiver receives a damage frame it discards it and NO
acknowledgement is sent to sender.
» Also when frame is lost and sender receives no ACK, it is same as
frame is lost.
» The receiver in both cases keeps the value of R variable.
» After the timer at sender expires the sender resends the expected
value to the receiver.

12. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.2 Stop-and-Wait ARQ, lost frame

13. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
STOP-AND-WAIT ARQ: Lost AcknowledgementSTOP-AND-WAIT ARQ: Lost Acknowledgement
» The damage ACK is discarded by the sender.
» Sender resends the frame (which has successfully received) to
receiver.
» At receiver which has already the copy of the frame present
discards the duplicate and resends acknowledgement.

14. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.3 Stop-and-Wait ARQ, lost ACK frame

15. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
In Stop-and-Wait ARQ, numbering In Stop-and-Wait ARQ, numbering
frames prevents the retaining of frames prevents the retaining of
duplicate frames.duplicate frames.
NoteNote::

16. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
STOP-AND-WAIT ARQ: Delayed AcknowledgementSTOP-AND-WAIT ARQ: Delayed Acknowledgement
» The ACK can be delayed due some problem with the link.
» e.g. Frame 0 is sent and ACK-1 is received after the timer is expired
and Frame 0 is resent.
» The receiver in this case has tow copies of Frame 0 so it will
discard the duplicate frame-0 and resends ACK-1.
» The sender on the other hand now has two Acknowledgements so
it’ll discard one and sends Frame-1, accordingly.

17. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.4 Stop-and-Wait ARQ, delayed ACK

18. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Numbered acknowledgments are Numbered acknowledgments are
needed if an acknowledgment is needed if an acknowledgment is
delayed and the next frame is lost. delayed and the next frame is lost.
NoteNote::

19. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
STOP-AND-WAIT ARQ: Bi-directional TransmissionSTOP-AND-WAIT ARQ: Bi-directional Transmission
» We can have bi-directional Transmission if the two parties have two
separate channels for full-duplex transmission, or share the same
channel for half-duplex transmission.
» In this case each party needs both S and R variables to track frames
sent and expected.

20. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
PiggybackingPiggybacking
» It is a method to combine a data-frame with and Acknowledgement.
» e.g. Station A and B both have data to send.
» Instead of sending separate data and ACK frames, station A sends
a data frame that includes an ACK. And station B behaves in a
similar manner.

21. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.5 Piggybacking

22. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
PiggybackingPiggybacking
ADVANTAGE
» piggybacking can save bandwidth, because the overhead from a
data frame and an ACK frame, (addresses, CRC etc) can be
combined in just one frame.

23. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.3 Go-Back-N ARQ11.3 Go-Back-N ARQ
We can send W frames before worrying about
Acknowledgement , we keep a copy of
theses frames until acknowledgement
arrives. This procedure requires additional
features to be added to STOP-AND-WAIT
ARQ.

24. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.3 Go-Back-N ARQ11.3 Go-Back-N ARQ
Sequence Number
Sender and Receiver Sliding Window
Control Variables and Timers
Acknowledgment
Resending Frames
Operation

25. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
GO-BACK-N ARQ: Sequence NumbersGO-BACK-N ARQ: Sequence Numbers
» Frames from the sending station are numbered sequentially.
» Because we need to include the sequence number in the header,
so we need to set a limit.
» If the header of a frame allows m bits for sequence number then,
the sequence numbers range is between 0 to 2
m
-1.
» If we take m=3 then the sequence numbers are:
»0,1,2,3,4,5,6,7, 0,1,2,3,4,5,6,7, 0,1,2,3,4,5,6,7, 0,1,…

26. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
GO-BACK-N ARQ: Sender Sliding WindowGO-BACK-N ARQ: Sender Sliding Window
» On the sender side to hold the outstanding frames until they are
acknowledged, a window concept is used.
» We imagine all frames are in a buffer, the outstanding frames are in
a window, which can slide.
» The frames on the left side of the window are that have already
been acknowledged and can be purged.
» The frames on the right side of the window cannot be sent until the
window slides over them.
» The size of the window is at most 2
m
-1, because of frame size
limitations.
» The size of the window is fixed here in this protocol, however it can
be varying in other protocols such as TCP.
» The windows slides to include new unset frames when correct
acknowledgements are received.

27. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.6 Sender sliding window

28. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
GO-BACK-N ARQ: Receiver Sliding WindowGO-BACK-N ARQ: Receiver Sliding Window
» The size of the window at receiver side is always 1.
» The receiver is always looking for a specifics frame to arrive
in a specific order.
» Any frame is arriving out of order is discarded and needs to
be resent.

29. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.7 Receiver sliding window

30. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
GO-BACK-N ARQ: Control VariablesGO-BACK-N ARQ: Control Variables
» The sender has three control variables, S S
F
and S
L
» S= holds sequence number of recently sent frames.
» S
F
= holds the sequence number of the first frame in the window.
» S
L
= holds the sequence number of the last frame in the window.
» The windows size W= S
L
- S
F
+ 1.
» The receiver has one variable, R, that holds the sequence number
of the frame it expects to receive.
» If the sequence number of the frame is same as the value of R then
it is received then it is accepted, else rejected.

31. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.8 Control variables

32. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
GO-BACK-N ARQ: TimersGO-BACK-N ARQ: Timers
» The sender sets a timer for each frame sent, The receiver has no
timers.

33. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
GO-BACK-N ARQ: AcknowledgementGO-BACK-N ARQ: Acknowledgement
» The receiver sends positive acknowledgements if a frame has
arrived safe and sound and in order.
» If a frame is damaged or received out of order, the receiver is
silent and will discard all subsequent frames until it receives the
the one it is expecting.
» The silence of the receiver causes the timer of the unacknowledged
frame to expire.
» This in turns, causes the sender to go-back and resends the all the
frames, beginning with the one which causes the timer to expire.
» The receiver doesn’t have to acknowledge each frame received, it
can send cumulative acknowledgement for several frames.

34. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
GO-BACK-N ARQ: Resending FramesGO-BACK-N ARQ: Resending Frames
» When a frame is damaged, the sender goes back and sends a set of
frames starting from the damage one up to last one sent.
» e.g. The sender has sent frame 6, but the timer has expires for
frame-3, means, sender goes back and sends frame 3,4,5,6 again.
» This is why the protocol is called Go-BACK-N ARQ.

35. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
GO-BACK-N ARQ: Normal OperationGO-BACK-N ARQ: Normal Operation
» The sender keeps track of the outstanding frames and updates
the variables and windows as the acknowledgements arrive.

36. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.9 Go-Back-N ARQ, normal operation

37. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
GO-BACK-N ARQ: Damaged or Lost FrameGO-BACK-N ARQ: Damaged or Lost Frame
» When a frame is damaged, it is discarded by receive and the
receiver window expected the next frames as well.
» At receiver the timer expires and the frames form the damaged or
lost frame are resent.

38. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.10 Go-Back-N ARQ, lost frame

39. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
GO-BACK-N ARQ: Damaged or lost AcknowledgementGO-BACK-N ARQ: Damaged or lost Acknowledgement
» If the acknowledgement is damaged or lost, we have two situations:

» If the next ACK arrives before the expiration of any timer, there is no
need of the retransmission of frames because acknowledgements
are cumulative in this protocol. (ACK-4 means ACK-1 to ACK-4).

» If the next ACK arrives after the time-out , the frame and all the
frames after that are resent.
» The receiver never re-sends an ACK.

40. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
GO-BACK-N ARQ: Delayed AcknowledgementGO-BACK-N ARQ: Delayed Acknowledgement
» A delayed acknowledgment also triggers the resending of frames.

41. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
GO-BACK-N ARQ: Sender Window SizeGO-BACK-N ARQ: Sender Window Size
» The window size MUST be less than 2
m
.
» e.g, we choose m=2 which means the size of the window can be
2
m
-1 i.e. 3
» Now we compare a window size of 3 and 4.

42. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.11 Go-Back-N ARQ: sender window size

43. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
In Go-Back-N ARQ, the size of the In Go-Back-N ARQ, the size of the
sender window must be less than 2m; sender window must be less than 2m;
the size of the receiver window is the size of the receiver window is
always 1.always 1.
NoteNote::

44. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Bi-directional Transmission and PiggybackingBi-directional Transmission and Piggybacking
» Go-BACK-N ARQ can also be bi-directional.
» piggybacking can also be used to improve the efficiency of the
transmission.
» However each side needs both a sender window and receiver
window.

45. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.4 Selective-Repeat ARQ11.4 Selective-Repeat ARQ
» GO-BACK-N ARQ is not good for noisy link as with the high
probability of damage and errors the resending of MULTIPLE
frames uses up the bandwidth and slows down of transmission.
» For a noisy link another mechanism is used which only resends the
faulty frame instead of N frames from the faulty frame.
» This mechanism is called the Selective-Repeat ARQ.
» It is more efficient at noisy links but the processing at the receiver
is more complex.

46. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.4 Selective-Repeat ARQ11.4 Selective-Repeat ARQ
Sender and Receiver Windows
Operation
Sender Window Size
Bidirectional Transmission
Pipelining

47. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Selective-Repeat ARQ: Sender and Receiver WindowsSelective-Repeat ARQ: Sender and Receiver Windows
» The configuration of sender and its control variables for
Selective-Repeat ARQ are same as GO-BACK-N ARQ.
» The size of the window must be at most one-half of the value 2
m
.
» The receiver window size must also be of the this size.
» This window, however, specifies the range of accepted received
frames.
» In other words in GO-BACK-N, the receiver is looking for one
specific sequence number; in selective repeat , the receiver is
looking for a range of sequence numbers.
» The receiver has two control variables R
F
and R
L
to define
boundaries of the window.

48. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.12 Selective Repeat ARQ, sender and receiver windows

49. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Selective-Repeat ARQ: NEGative AcknowledgementSelective-Repeat ARQ: NEGative Acknowledgement
» The Selective-Repeat ARQ also defines a negative acknowledgment
(NAK) that reports the sequence number of a damaged frame before
the timer expires.

50. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Selective-Repeat ARQ: LOST frameSelective-Repeat ARQ: LOST frame
» e.g. Frame 0 and 1 are accepted when received because they are
in a range specified by the receiver window.
» When frame-3 is received, it is also accepted for the same reason.
» However the receiver sends a NAK-2 means that the frame-2 is not
received.
» When the senders receives the NAK-2 it only resends Frame-2,
which is then accepted, because it is in the range of window.

As shown in Figure 11.13…

51. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.13 Selective Repeat ARQ, lost frame

52. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Selective-Repeat ARQ: Sender Window SizeSelective-Repeat ARQ: Sender Window Size
» The size of the window MUST be at most one-half of 2
m
.
» e.g. we choose m=2, means the size of window should be 2
m
/2 or 2.
» Now we compare the window size 2 with window size 3 in figure
11.14.

53. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.14 Selective Repeat ARQ, sender window size

54. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
In Selective Repeat ARQ, the size of In Selective Repeat ARQ, the size of
the sender and receiver window must the sender and receiver window must
be at most one-half of 2be at most one-half of 2
mm
. .
NoteNote::

55. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Bi-directional Transmission and PiggybackingBi-directional Transmission and Piggybacking
» Selective-Repeat ARQ can also be bi-directional.
» piggybacking can also be used to improve the efficiency of the
transmission.
» However each side needs both a sender window and receiver
window.

56. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Example 1Example 1
In a Stop-and-Wait ARQ system, the bandwidth of the line is 1 Mbps, and 1 bit
takes 20 ms to make a round trip. What is the bandwidth-delay product? If the
system data frames are 1000 bits in length, what is the utilization percentage of
the link?
SolutionSolution
The bandwidth-delay product is
1  10
6
 20  10
-3
= 20,000 bits
The system can send 20,000 bits during the time it takes for the data to go
from the sender to the receiver and then back again. However, the system
sends only 1000 bits. We can say that the link utilization is only
1000/20,000, or 5%. For this reason, for a link with high bandwidth or long
delay, use of Stop-and-Wait ARQ wastes the capacity of the link.

57. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Example 2Example 2
What is the utilization percentage of the link in Example 1 if the link uses Go-
Back-N ARQ with a 15-frame sequence?
SolutionSolution
The bandwidth-delay product is still 20,000. The system can send up to 15
frames or 15,000 bits during a round trip. This means the utilization is
15,000/20,000, or 75 percent. Of course, if there are damaged frames, the
utilization percentage is much less because frames have to be resent.

58. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.5 HDLC11.5 HDLC
High-level Data Link Control is an actual protocol
designed to support both half-duplex and
full-duplex communication over point-to-point
and multipoint links. It implements the ARQ
mechanisms.

59. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.5 HDLC11.5 HDLC
Configurations and Transfer Modes
Frames
Frame Format
Examples
Data Transparency

60. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
HDLC: Configurations and Transfer ModesHDLC: Configurations and Transfer Modes
» HDLC provides two communication and transmission modes;
NRM and ABM.

61. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
HDLC: Configurations and Transfer Modes: NRMHDLC: Configurations and Transfer Modes: NRM
» Normal Response Mode
» The station configuration is un-balanced.
» We have one primary station and multiple secondary stations.
» Primary Station: Which can sends commands.
» Secondary Station: It can only responds.
» The NRM is used both point-to-point and multiple-point links.

62. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.15 NRM

63. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
HDLC: Configurations and Transfer Modes: ABMHDLC: Configurations and Transfer Modes: ABM
» Asynchronous Balanced Mode.
» The configuration is balanced.
» Each station can function as primary and a secondary.
» The link is point to point.

64. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.16 ABM

65. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
HDLC: FramesHDLC: Frames
» HDLC defines three types of frames.
» Information-Frames (I-Frames): Used to transport user data and control
information relating to user data (piggybacking).

»Supervisory Frames (S-Frames): Used only to transport control
information.
» Unnumbered Frames (U-Frames): Reserved for system management.
Information carried by U-Frames is intended for managing the link itself.

66. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.17 HDLC frame
» Each frame in HDLC constrains up to 6 fields as shown in Fig. 11.17
» In multi frame transmission the ending flag of one frame can serve
as the beginning flag of next frame.

67. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.17 HDLC frame Fields
FLAG FIELD:
» 8 bit sequence with a bit pattern 01111110 that identifies both the
beginning and end of a frame.
» Synchronization pattern for the receiver.
ADDRESS FIELD:
» Contains the address of the secondary station.
» If primary station creates a frame, it contains TO address.
» If secondary station creates a frame, it contains FROM address.
» It can be 1 byte or several bytes long.
» 1 byte can identify 128 stations (1 remaining bit for some
other purpose)
» If address is 1 byte long, last bit is always 1.
» If more than 1 byte, all bytes but the last one ends with 0,last
one ends with 1.
» Ending each intermediate byte with 0, indicates the receiver
that there are more address bytes to come.

68. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.17 HDLC frame Fields
CONTROL FIELD:
» 1 or 2 byte long used for flow and error control.
» Interpretation of bits in this field is different for different frame
types.
INFORMATION FIELD:
» Contains the user’s data from the network layer or network
management information.
» Its length can vary from one network to another but in a single
network its network in fixed.
FCS FIELD:
» Frame Check Sequence (FCS).
» HDLC’s error detection field.
» It can contain either a 2-or4 byte ITU-T CRC.

69. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.18 HDLC frame types
» HDLC defines three types of frames, show below in Fig 11.18

70. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.19 I-frame
» Carry user data from the network layer.
» Can also include flow and error control information. (piggybacking).
» Formant of the control field in I-Frame is shown below in Fig 11.19.

71. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.19 I-frame: Control Field
» First bit 0 means I-Frame.
» Next 3 bits called N/S, defines sequence number. (0 to 7),
the value of this field corresponds value of Control variable S, as
described in three ARQ mechanisms earlier.
» Next bit is P/F bit. Its is dual purpose bit. When it is set (1), it can
mean poll (frame is sent by primary station) or final (frame is
sent by secondary station).
» Next three bits , called N(R), corresponds to the value of ACK,
when piggybacking is used.

72. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.20 S-frame control field in HDLC
» Used for flow and error control, whenever piggybacking is either
impossible or inappropriate.
» It do not have information fields.
» The format of control field is shown in Fig 11.20 below.

73. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.20 S-frame control field in HDLC
» First two bits are 10 means S-Frame.
» The second two bits is a CODE that defines the four types of
S-Frames;
» Receiver Ready (RR): CODE=00, this acknowledges a safe and
sound frame or group of frames.
» Receiver Not Ready (RNR): CODE=10, it is RR-Frame with additional
duties. It acknowledges the receipt of a frame or group of frames,
it announces that receiver is busy and cannot receive more frames.
It also acts as congestion control mechanism by asking the sender
to slow down.
» Reject (REJ): CODE=01, this is NAK frame as in Go-Back-N ARQ not
NAK is selective-Repeat ARQ, it improves the efficiency of the
process in Go-Back-N ARQ by informing the sender, before timer
expires that last frame is lost or damaged.

74. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.20 S-frame control field in HDLC
» Selective Reject (SREJ): CODE= 11. this is a NAK frame used in
selective-Repeat ARQ,
» HDLC protocol uses the term selective reject instead of
selective repeat.
»The Fifth bit if P/F bit, its process is same as in I-Frame.
» The next three bits are N(R), corresponds to the ACK or NAK value.

75. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.21 U-frame
» Used to exchange session management and control information
between connected devices.
» Its information field is only meant for system management
information.
» Most of the information is U-Frame is in codes, included in
Control Field.
» U-Frames codes are divided into two sections.
» 2-bits pre-fix before the P/F bit and 3-bits suffix after P/F bit.
» Together these 5 bits can be used to create up-to 32 different
types of U-Frames.

76. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.21 U-frame control field in HDLC and
some most common U-Frames

77. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Table 11.1 U-frame control command and responseTable 11.1 U-frame control command and response
Command/response Meaning
SNRMSNRM Set normal response mode
SNRMESNRME Set normal response mode (extended)
SABMSABM Set asynchronous balanced mode
SABMESABME Set asynchronous balanced mode (extended)
UPUP Unnumbered poll
UIUI Unnumbered information
UAUA Unnumbered acknowledgment
RDRD Request disconnect
DISCDISC Disconnect
DMDM Disconnect mode
RIMRIM Request information mode
SIMSIM Set initialization mode
RSETRSET Reset
XIDXID Exchange ID
FRMRFRMR Frame reject

78. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Example 3Example 3
Figure 11.22 shows an exchange using piggybacking where is no
error. Station A begins the exchange of information with an I-
frame numbered 0 followed by another I-frame numbered 1.
Station B piggybacks its acknowledgment of both frames onto an I-
frame of its own. Station B’s first I-frame is also numbered 0 [N(S)
field] and contains a 2 in its N(R) field, acknowledging the receipt
of A’s frames 1 and 0 and indicating that it expects frame 2 to
arrive next. Station B transmits its second and third I-frames
(numbered 1 and 2) before accepting further frames from station A.
Its N(R) information, therefore, has not changed: B frames 1 and 2
indicate that station B is still expecting A frame 2 to arrive next.

79. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.22 Example 3

80. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Example 4Example 4
In Example 3, suppose frame 1 sent from station B to
station A has an error. Station A informs station B to
resend frames 1 and 2 (the system is using the Go-Back-
N mechanism). Station A sends a reject supervisory frame
to announce the error in frame 1. Figure 11.23 shows the
exchange.

81. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.23 Example 4

82. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Data Transparency
» Data Field in HDLC frame can carry text as well as non-textual
information such as video, audio, graphics or other bit sequences.
» But some messages can create problems during data-transmission.
» e.g. If the data field contains a pattern that is same as the sequence
reserved for the flag filed 01111110, the receiver interprets the
sequence as the ending flag.
» The rest of the bits are assumed to be part of next frame.
» This phenomenon is called lack of data transparency.
» When data are transparent, all data are recognized as data and
control information is recognized as control information, without
any ambiguity.

83. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Bit Stuffing
» To guarantee that the flag field sequence does not appear
inadvertently anywhere else in the frame HDLC uses a process
called bit stuffing.
» Every time sender wants to transmit a bit sequence having more
than five consecutive 1s, it inserts (stuffs) one redundant 0 after
fifth 1.
» e.g. the sequence 011111111000 becomes 0111110111000.
» This redundant 0 is dropped at receiver.

84. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Bit stuffing is the process of adding Bit stuffing is the process of adding
one extra 0 whenever there are five one extra 0 whenever there are five
consecutive 1s in the data so that the consecutive 1s in the data so that the
receiver does not mistake the receiver does not mistake the
data for a flag.data for a flag.
NoteNote::

85. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.24 Bit stuffing and removal

86. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
11.25 Bit stuffing in HDLC