Transcript 13. Example Data Link Protocols

Lecture #13: Example
Data Link Protocols.
Contents
Types of services provided by DLL protocols
7
Flow control functions
Flow control protocols
4
9
Stop-and-Wait protocols
11
Sliding window protocols
19
Go-back-n
12
Selective Repeat/Reject
21
Performance comparison
23
HDLC
24
Internet DLL protocols
27
1
Communication Functions
according to the OSI
Model
Application layer
User application 1
Presentation layer
Session layer
Encryption/
decryption
Session
control
Session
synch.
...
compression/
expansion
Choice of
syntax
Session to transport
mapping
Session
management
Transport layer
Layer and flow
control
Error
recovery
Multiplexing
Network layer
Connection
control
Routing
Addressing
Link layer
Data link
establishment
Error
control
Physical layer
Access to
transm. media
Physical and
electrical interface
Flow
control
Synch
Framing
Activation/
deactivation of con.
 Framing: considers frame format/ length issues (incl. error
detection/correction implementation
 Flow control: SAW, Sliding Window
 Error control: correction, detection, recovery (ARQ: SAW, GBN, SR)
2
Data link layer




The data link layer provides functional and
procedural means to establish, maintain and
release data link connections among network
entities and to transfer data link service data
units.
A data link connection is built upon one or
several physical-connections.
The data link layer detects and possibly corrects
errors which may occur in the physical layer.
In addition, the data link layer enables the
network layer to control the interconnection of
data circuits within the physical layer.
3
DLL Services

Types of DLL services:
–Unacknowledged connectionless service
• frames are sent independently (connectionless)
• no recovering of the lost/damaged frames (unack.)
• for reliable links or upper levels recovery architecture
–Acknowledged connectionless service
• possible implementation of damaged/lost frames
–Connection-oriented services
• correct and in-order frame delivery
4
DLL Services

Services provided to the network layer by
the data link layer are:
– data-link-connection;
– data-link-connection-endpoint-identifiers;
– sequencing;
– error notification;
– flow control;
– quality of service parameters.
5
Data Link Layer Functions

Functions within the data link layer
– data-link-connection establishment and
release;
– delimiting and synchronization;
– sequence control;
– error detection;
– error recovery;
– flow control;
– identification and parameter exchange;
– control of data-circuit interconnection;
– data link layer management.
6

Terminology
Flow Control
– Simplex: Signal flows always in one direction (e.g., computer - to - printer)
– Half Duplex: Alternating one-way. Signal flows in both directions not
simultaneously but alternatively.
– Full Duplex: Signal flow is in both directions simultaneously

Logical Connectivity:
– Peer-to-Peer: Either station can initiate a call
– Primary-Secondary: Only the Primary may initiate a call. There is no
Secondary-to-Secondary calls initiated separately.

Connection Phases: Apply to both logical connectivity
types: Peer - to - Peer, Primary - Secondary
– Connection Establishment: Determines which station transmits, which
receives, and whether the receiver is ready to receive.
– Data Transfer: Data are transferred in one or more acknowledgment blocks
– Connection Termination: Terminates the logical connection, physical
connection upon which that logical connection was based may remain
connected

Frame transmission models:
– Error free transmission
– Transmission with errors or losses
13/1
7
Flow Control

Flow Control (Physical Connectivity Possibilities)
 Point-to-Point (P-P)
Logical Connectivity: Can use either Peer-to-Peer or
Primary-Secondary depending on whether a Primary station
has been designated or not
Addressing: No addressing is required.
 Multipoint
Logical Connectivity
 Peer-to-Peer: Uses contest access methods
 Primary-Secondary: Uses Poll (The primary request
data from the secondary) and Select (The primary
has data to send to the secondary)
Addressing:
 Peer-to-Peer: Two addresses required (transmitter
and receiver)
 Primary-Secondary: One address needed, to identify
8
the secondary
Flow Control Protocols
Network Layer

synchronous transmission,
Virtual packet transfer
dedicated service, simplex error-
DLL
TrmTimer
ToPhL
TrmCount
ToNL
RcvTimer
free channel …
PackBuff
FromNL
Time-Driven Control (for

SAW: for asynchronous
transmission, multiple service,
half-duplex error-free channel …
FromPhL

FrameBuff
Virtual frame transfer
Event-Driven Control (some
Event-Driven Control with
Timeouts (SAW, PAR/ARQ,
sliding window: for
asynchronous transmission,
Physical Layer
multiple service, full-duplex
channel with losses/errors …
Physical bit transfer (signaling)
9
Examples of Flow Control Protocols
SAW (Stop And Wait protocols)
PAR/ARQ (Positive Acknowledge with Retransmission
[of the non-acknowledged frames]/Automatic Repeat
reQuest)
sliding window protocols

Applicable mechanisms:
– piggybacking employs the outgoing traffic for
carrying frame receive acknowledgements; timeout
control over the delayed acknowledgments in case of
no outgoing data frames.
– pipelining: sequential frame transmission upon the
new Network Layer’s requests prior to
acknowledgement for the frames already sent.
Outstanding frames form so called sender window.
10
Stop-And-Wait Protocols

SAW Protocol (Idle ARQ)
– Algorithm
3/12
13/5
 Send frame
 Wait for an ACK before sending the next frame ( good for half duplex
links)
– Channel Utilization, U:
–
–
0>U>1
U depends on the channel length D:
U = Tfr/Tt
Bit Error Rate BER:
BER = nerr/nt
(1)
where Tfr is the frame transmission time and Tt is the total transmission time
including Tfr, Tp (propagation delay), TACK (acknowledgement generation,
propagation and transmission) , Tproc (frame processing time). Approximation for
error-free channel (BER-->0):
channel bit rate [b/S]
Tt = Tfr + 2 Tp
(2)
Tp = (D/2)10-8 [S] (by signal speed = 2.108m/S in copper)
a = Tp / Tfr = (sfr/Drb)c [non-dimensional]
(3)
relative channel length [with respect to the frame duration]
(1), (2) and (3) yield U=1/(1+2a) i.e. Ua
13/2
EM-waves’ speed
(4)
11
Sliding Window Protocols

Duplex (bi-directional) data connection based on pipelining

Event-driven synchronization with system of timeouts.
Timers are required for each frame being tracked.

ACKs are usually “piggybacked” onto the forward traffic from
receiver

Cyclic sequenced numbering of the outgoing frames; cycle
length L = 2n - 1  1


Sender window SW keeps the numbers of frames that are to
be transmitted
Receiver window RW keeps the numbers of frames that are to
be received and acknowledged
cont ...
12
… cont.

Sliding Window Protocols
Buffers are required for each frame being transmitted (received)
– Frames are buffered in seq_number order at the sender for
possible retransmission
– Frames are buffered in seq_number order at the receiver for
delivery to the Network Layer when Selective Repeat error
handling is applied

Sliding window protocols guarantee the number and the order of
the transmitted frames thus simulating connection-oriented
transmission

SW and RW can differ in the limits and window-size

Important performance and robust parameters are the
maximal sender/receiver window size wS/R and the timeouts in
context to the actual throughput and the frame round-trip transit
13
time.
Sliding Window Protocols
First frame
waiting
transmission
Sender Window
Last frame
waiting
transmission
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3
Transmitted frames zone
Trailing edge
shrinks as
frames are sent
First frame that
might be
accepted
Receiver Window
Leading edge
expands as ACKs
are received
Last frame that
might be
accepted
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3
Acknowledged frames zone
Trailing edge
shrinks as frames
are received
Leading edge
expands as
ACKs are sent
14
Sliding Window Protocols
Step 1.
1
0
A ready to
transmit 7 frames
beginning with
frame 0; B ready
to receive 7
frames beginning
with frame 0
7
A
Sender
6
5
4
3
2
1
0
Sliding
windows
6
5
4
3
2
1
0
B
Rec-er
Step 2.
1
0
A have sent 3
frames, sender
window shrinks to
4 frames
A
7
Sender
6
5
4
3
2
1
0
6
5
4
3
2
1
0
B
Rec-er
15
Sliding Window Protocols
Step 3.
1
0
B received 3
frames; receiver
window shrinks to
4 frames too
7
A
Sender
6
5
4
3
6
5
4
3
B
Rec-er
2
1
0
Step 4.
1
B transmits
acknowledge for
frames 0-2 which
causes receiver
window to expand
back
Ack3
0
A
8
Sender
6
5
4
3
6
5
4
3
B
Rec-er
16
Sliding Window Protocols
Step 5.
Ack3
1
1
0
7
6
5
4
3
0
Sender window
expands with 3
positions when
the acknowledgement for the 3
frames is received
A
7
Sender
6
5
4
3
B
Rec-er
Step 6.
A has transmitted
frame 3 and then
frames 4, 5 and
6; B processed
frame 3, 4, 5 and
6 and transmits
Ack4
A
Sender
4
3
2
1
0
7
6
1
0
8
7
6
5
Ack4
B
Rec-er
4
3
17
Sliding Window Protocols
Step 7.
4
3
Receiver window
expands with 1
position upon the
departure of the
acknowledgement for the 4
frames.
Ack4
A
2
Sender
1
0
7
2
1
0
7
6
B
Rec-er
5
Step 8.
4
A window expands
with a position upon
the receiving of the
Ack4;
B processes frames
5 and 6
Ack4
A
3
Sender
2
1
0
7
2
1
0
7
B
Rec-er
18
Sliding Window Protocols Go-back-n


Sender window size wS  n (but still wS  L-1)
Receiver window size wR= 1
3/15a



13/6
13/6
Sender may send multiple frames up to wS
Receiver buffers only one received frame. It cannot
receive frames out of order. Frames are passed in order
to the NL.
Damaged Frame:
– B detects error in frame (i): B sends REJ(i). When A receives REJ(i) it must
resend (i) and all subsequent frames.
– B does not detect frame (i) (frame is lost) and A already sent (i+1): B
receives (i+1) out of order and sends REJ(i)
– Frame (i) is lost and A does not send anything after frame (i): A timeouts
and resend (i).
19
cont ...
Sliding Window Protocols cont …
Go-backn
Damaged ACK

– ACKs (Receiver Ready, RRs) are cyclic-cumulative. If an ACK (i)
get lost and:
• a subsequently higher ACK (i+n) is received: this ACK will account for
intervening ACKs
• peer A timeouts without ACK: A requests retransmission of the cumulated
ACK
13/6


Damaged NACK (REJ): peer A timeouts.
Performance
More complex than SAW: wS buffers/timers at the transmitter,
1
buffer/timer at receiver
More efficient that SAW - allows for pipelining, but inefficient for
noisy channels

Channel utilization (only by “error free” assumption!):
{
U=
1, wS  (2a+1)
wS/(2a+1), wS  (2a+1)
wS is greater than the number of frames that can fit into the
channel; peer A can transmit frames without pausing
20
Sliding Window Protocols Selective Repeat/Reject
3/15b

wS = wR - the receiver buffers all the received frame. It can
receive frames out of order and only NACKed frames are
retransmitted. Frames are passed in order to the NL.

Channel utilization (only by BER-->0!) is the same as
for GBN ARQ.

Performance
 More complex than GBN:
wS buffers/timers both at the
transmitter and receiver
 More efficient than GBN for noisy channels
21
Sliding Window Protocols Performance Effect of the Window Size

Mb/S
100 Mb/S Ethernet LAN
24

20
16
12
10 Mb/S Ethernet LAN
8
Effect of saturation
when wS becomes
greater than the
number of frames that
can fit into the channel
Possible effect (for
LANs and other
multiple access
systems) of
degradation if
receiver’s buffer is
overloaded
4
4
8
12
16
20
24
wS
22
DLL Protocols Performance Comparison
• Single bit error probability (or bit error rate) BER= nERR/nt
• Frame error probability
Pfr=1-(1-BER)Sfr  [for BER-1>>Sfr]  SfrBER (where Sfr is the
frame size)
• Channel utilization as a function of the relative channel
length a and frame error probability Pfr :
– SAW: U = (1 - Pfr) / (1 + 2a)
wS  2a+1
– GBN: U = (1 - Pfr,) / (1+2a Pfr) ;
wS (1 - Pfr) / ((2a+1)(1- Pfr +wS Pfr)); wS  2a+1
{
1-P ;
– SR: U = { w (1 - P ) / (2a+1);
fr
S
13/10
fr
wS  2a+1
wS  2a+1
23
Example DLL Protocols - HDLC


HDLC - High-level Data Link Control
Widely applied standard
– LLC in IEEE802.2 (Upper part of DLL in LANs/MANs)
– LAPB (Link Access Protocol - Balanced) in X.25
– LAPD (Link Access Protocol of the D-channel) in ISDN



Bit-oriented protocol - with bit stuffing
Applies sliding window algorithms (GBN or SR)
HDLC-defined station types:
– primary (link establishment and control - issues commands)
– secondary (controlled by primary - issues responses)
– combined

Link configuration: balanced (P-P only)/unbalanced (P-P
and multi-P operations; obsolete - terminal complexes)
24
HDLC - frame format

13/7
Address field (8 b extendible to 16): contains destination by
multi-P configuration; in P-P mode this field distinguish
commands and responses

Information - variable data length

FCS - CCITT-CRC

Control field - distinguish 3 types of frames:
–
Information frames:
• N(S) field (3b) sequence number of the frame being sent i.e. the
sliding window may contain up to 7 outstanding frames
• N(R) field (3b) sequence number of the next frame expected
• Poll/Final bit: primary invites secondary to send data with a P/F set to P;
the secondary data frames also have P/F=P but the last of them has
P/F=F ; (somewhere used to suspend piggybacking ACK delays)
–
Supervisory frames - protocol (sliding window) control frames :
• S field (2b) for supervisory function: ACK (RR), NACK (REJ), RNR
(receiver not ready) and SR (Selective Retransmission)
cont …
25
HDLC - frame format

Control field types cont.:
– unnumbered frames for control and specific data
transfer:
• M (5b, split by the P/F bit) field - up to 32 command/info
codes including:
– connection mode setting (peer A: SABM “Set Asynchronous
Balanced Mode”, “Disconnect”…, B: UA “Unnumbered ACK” for
acknowledgement of control frames etc.)
– information commands and responses (ID exchange, test,
provide day time, setup link …)
– recovery commands and responses for untypical problems (e.g.
long data field, invalid control field …)

Example HDLC operations
13/8
26
Internet DLL

Internet P-P architectures:
– leased lines to the Internet communication
subnets
3/26 – dial-up lines to time-sharing shell account or
router

Internet DLL protocols - SLIP and PPP
– SLIP (Serial Line IP)
• character stuffing
• no error handling
• IP support only (not Novel IPX...)
• static IP addressing
• not approved as Internet standard
27
Internet DLL

PPP (Point-to-Point Protocol) - RFC 1661;
provides 3 mechanisms
 Framing Method providing also error control.
 A Link Control Protocol (LCP) which brings line up, tests it,
negotiates options, and brings lines down in the end.
 Negotiation of the NL options (independence of the
network protocol being used). The method used is to have a
different NCP (Network Control Protocol) for each network
layer used.

3/28
Phases of data link setup/termination in Internet
– Dead - no physical layer present
– Establish a Physical Connection: (The user’s PC first calls the
provider’s router via a modem
– Authenticate - Establish a Link Connection: (PPP next sends
a series of LCP packets to configure the data link layer.)
•
LCP provides a mechanism (proposal - acceptance/rejection between
28
the two sides) to negotiate link options
Internet DLL
– Authenticate - Establish a Link Connection: (PPP next sends a
series of LCP packets to configure the data link layer.)
•
•
LCP provides a mechanism (proposal - acceptance/rejection between the
two sides) to negotiate link options
Options may include
–
–
–
–
setting the maximum payload size for data frames
enabling authentication to be conducted
choosing a protocol to use
LCP also allows for testing of the line (Echo - types)
– Network - Establishes the Network Connection: (PPP next sends
a series of NCP packets to configure the network layer.)
•
•
Typically this is the TCP/IP protocol stack (so an IP address is needed)
Each Internet provider manages a block of addresses, (one of which is
dynamically assigned at login time).
– Open - The PC is now an internet host (and is permitted to send
and receive IP packets.)
– Terminate - Procedure is reversed at the end of the session •
•
•
Disestablish Network Connection - release IP address
Disestablish the Data Link Connection - release the logical connection
Disestablish Physical Connection - release the TP line
29

PPP Frame
3/27
Internet DLL
– Similar to HDLC (except it is based on eight-bit
word size - character stuffing is used)
– Preamble - HDLC flag byte (0111 1110) (Character
stuffed if it occurs within the frame)
– Address Field - All 1’s
– Control Field - used to indicate that PPP is using
unnumbered frames. (I.e., no seq-nums, ACKs -therefore is an unreliable CLS)
– Protocol - used to indicate which Data Link or
Network Layer Protocol is being used.
– Payload (variable length)
– Checksum (2 or 4 bytes)
30
31
32
33
34
35
36
37
U
38
Sender
Receiver
39
40
41
42
43