Tutorials Data Link Layer Protocols

Stop-and-Wait ARQ
Piggybacking
• Piggybacking is a method
that combines the data and
the ACK in one frame
• It is useful in bidirectional
communications
• Stations can send their data
along with ACK to data
previously received
• Piggybacking is faster and
saves bandwidth
COE 341 – Dr. Marwan Abu-Amara 4

Stop-and-Wait Efficiency
• It is common to ignore TProc and TACK because
they are negligible compared to other times TX RX
• In which case the utilization becomes: Tf

• U = (Tf)/(Tf +2Tprop) = 1/(1 + 2a)
• Where: a = Tprop/Tf Tprop
• a is called the “length of the link in bits”: length of
medium in bits compared to frame length (Lf) Tproc
• Notice that for very small a (i.e. when 1st
transmitted bit reaches RX, source will still be
transmitting), U 100% Tprop
• Notice that for very big a (i.e. frame transmission is

completed before 1st bit reaches destination), TACK
U 0%
• Efficient for links where a << 1 (long frames
on a short link, i.e. fills link)
Stop and Wait Efficiency:
Example
• Compare the efficiency of stop-and-wait error control for two links
using the parameter ‘a’:
• Fame size, L = 1000 characters of 8 bits each, = 8000 bits
 Satellite link between 2 ground stations  200-m optical fiber link
 d = 2 x 36,000 km, Data rate, R = 1 Mbps  Data rate, R = 1 Gbps
 Typical wave velocity, V = 3 x 108 m/s  Typical wave velocity, V = 2 x 108 m/s
d 2 �36 �106 T prop d 200
T prop 8
3 �10 = 30 V 2 �108 = 0.125
a= = V = a= =
L
=
8000
Tf L 8000 Tf
R 1�10 6 R 1�109
 Frame TX time, tf = L/R = 8000/(1x106)  Frame TX time, tf = L/R = 8000/(1x109)
= 8 ms = 8 ms
 Propagation time, tprop = d/V  Propagation time, tprop = d/V
= 2x36x106/(3x108) = 240 ms = 200/(2x108) = 1 ms
 End of first frame reaches RX after  End of first frame reaches RX after
8+240 = 248 ms from start 8+1 = 9 ms from start
 ACK takes 240 ms more to reach TX,  ACK takes 1 ms more to reach TX,
which sends 2 frame after 488 ms
nd
which sends 2nd frame after 10 ms
 Utilization = 8/488 = 1.6% (=1/(2a+1))  Utilization = 8/10 = 80% (=1/(2a+1))
Example: Sliding Window
Two neighboring nodes (A and B) use a sliding-window
protocol with a 3-bit sequence number. As the ARQ
mechanism, go-back-N is used with a window size of 4.
Assuming A is transmitting and B is receiving, show the
window positions for the following succession of events:
a) Before A sends any frames
b) After A sends frame 0, 1, 2 and B acknowledges 0, 1 and
the ACKs are received by A
c) After A sends frames 3, 4, and 5 and B acknowledges 4
and the ACK is received by A

Example: - Solution
W
a)
• • • 0 1 2 3 4 5 6 7 0 • • •
b) W
• • • 0 1 2 3 4 5 6 7 0 • • •
c) W
• • • 0 1 2 3 4 5 6 7 0 • • •


Sliding Window Protocol -
Efficiency
• Refer to Appendix A
• When window size is W (for error free), link utilization, U, is given by
� 1 W �(2a + 1)
�
U = �W
� W < (2a + 1)
�2a + 1
where a = Tprop/Tf (i.e. length of link in bits)
• Sliding window protocol can achieve 100% utilization if W  (2a + 1)
• The smaller the W needed the better! (Why?)
• To get high value for U, small value for a is needed as well !!

Sliding Window Efficiency:
Example
• Compare the efficiency of Sliding Window flow control for two links
using the parameter ‘a’:
• Fame size, L = 1000 characters of 8 bits each, = 8000 bits
 Satellite link between 2 ground stations  200-m optical fiber link
 d = 2 x 36,000 km, Data rate, R = 1 Mbps  Data rate, R = 1 Gbps
 Typical wave velocity, V = 3 x 108 m/s  Typical wave velocity, V = 2 x 108 m/s
 Frame TX time, tf = L/R = 8 ms  Frame TX time, tf = L/R = 8 ms
 Propagation time, tprop = d/V = 240 ms  Propagation time, tprop = d/V = 1 ms
 a = tprop / tf = 30  a = tprop / tf = 0.125
 100 % link utilization is achieved with  100 % link utilization is achieved with
window size W: window size W:
W  (2 a+1)  (2 x 30 +1)  61 W  (2 a+1)  (2 x 0.125 +1)  1.25
W = 61, k = 6 bit i.e. W = 2 (A window of just 2 frames)
(Large window and buffer sizes)
 For k = 3 bits, W = 7:
Utilization U = W/(2a+1) = 7/(61)
= 11.5% > 1.6% for Stop and wait.
High-Level Data Link Control Protocol
(HDLC)
 One of the most important data link control protocols and
it is the basis for many data link control protocols.
 The job of the HDLC layer (Link Layer, Layer 2) is to ensure
that data passed up to the next layer has been received
exactly as transmitted (i.e error free, without loss and in
the correct order)
 Another important job is flow control, which ensures that
data is transmitted only as fast as the receiver can receive
it.
11
(HDLC)
To satisfy a variety of applications, HDLC defines three types
of stations, two link configurations, and three types of data
transfer modes of operation.
Station types:
• Primary Station (PS):
Responsible for controlling the operation of the link
Frames issued by the PS are called commands
• Secondary Station (SS): Frames issued by the SS are called
responses – operates under the control of a primary station
• Combined Station: issues commands and responses
Link configurations:
• Unbalanced: one primary plus one or more secondary
• Balanced: two combined stations
12
(HDLC)
Transfer modes:
• Normal Response Mode (NRM) – used in unbalanced config.;
secondary may only tx data in response to a command from
primary
• Asynchronous Response Mode (ARM) – used in unbalanced
config.; Secondary may initiate data tx without explicit
permission; primary still retains line control (initialization,
error recovery, …)
• Asynchronous Balanced Mode (ABM) – used in balanced
config.; either combined station may tx data without
receiving permission from other station
13
HDLC ABM
14
HDLC Bit Stuffing & Removal
15
HDLC Frames
• HDLC uses Synchronous transmission
• HDLC defines three types of frames
• Information frames (I-frames)
• Used to transport user data and user control information relating
to the user data (e.g. piggybacking)
• Supervisory frames (S-frames)
• Used to transport control information only
• Unnumbered frames (U-frames)
• Used in the link management
16
HDLC Generic Frame Format
Indicates that the first
transmitted field is the Header
flag, then the address, then the
control…
Header Trailer
17
HDLC I, S & U Frames Format
18
HDLC I-Frames
• I-frames are designed to carry user data from Network-layer
• They can include flow & error control information
(piggybacking)
• The bits of the I-frame Control field are:
• First bit is always “0”. It means it is an I-frame
• Next 3-bits, called N(S), define the sequence of the frame
• So possible sequences are 0,1,2,3,4,5,6,7
• Next bit is called P/F (Poll or Final)
• When a primary station polls other stations, it sets this bit to 1
• When a secondary station responds to a poll, it sets this bit to 1
• Next 3-bits, called N(R), define the value of the ACK when
piggybacking is used
19
HDLC Example: Piggybacking w/o
Errors
• Next slide shows an exchange using piggybacking when there 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’s frame 2 to arrive next
20
HDLC Example: Piggybacking w/o
Errors
21
HDLC Example: Piggybacking with
Errors
• 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
• Next slide shows the exchange
22
HDLC Example: Piggybacking with Errors
23
NOTION OF SLOT TIME
• Consider the case where each channel transmits 1 unit every 3T
seconds
• Combined signal transmits unit every T seconds

NOTION OF SLOT TIME
• Frames are required in such a transmission. With framing, if there are
N conversations then each communication is sent in a fixed time-slot
modulo N. For example if N = 6 then the following figure refers to the
frames involved.

Tutorials Data Link Layer Protocols

Uploaded by

Copyright:

Available Formats

Tutorials Data Link Layer Protocols

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Tutorials Data Link Layer Protocols

Uploaded by

Copyright:

Available Formats

Stop-and-Wait ARQ

COE 341 – Dr. Marwan Abu-Amara 4

• In which case the utilization becomes: Tf

• Notice that for very big a (i.e. frame transmission is

COE 341 – Dr. Marwan Abu-Amara 7

COE 341 – Dr. Marwan Abu-Amara 8

COE 341 – Dr. Marwan Abu-Amara 9

• Combined signal transmits unit every T seconds

You might also like