Computer Networks

Field: SMI - S5

Pr. K. HOUSNI
Faculty of Sciences
Ibn Tofail University

Page 1
 Chapter III

The data link layer

 Chapter III

Definition

Role of the data link layer

The delimitation of data: notion of flag, notion of transparency

The binary error rate
Error detection
Detection by calculated key

Control of the exchange

The basic mechanisms
Flow control
Connection modes
The data link layer protocol
The HDLC protocol
HDLC Frame Structure
The command field
Structure of an HDLC dialogue
 The data link layer

Definition:
The data link layer provides functional means and
necessary procedures for establishment, maintenance, and release
data link connections between network entities.

It detects and corrects, if possible, errors due to the physical medium.

and signals to the network layer the unrecoverable errors.

She supervises the operation of the transmission and defines the structure.
syntax of called messagesframes.

Onetramais a bounded binary sequence containing

data type information and/or control information
necessary to carry out the functions at this level.

Page 4
 Role of the data link layer

While the data circuit (physical layer) is capable of transmitting

binary elements, data link protocols operate on blocks
binary elements (the frames). The frame is the basic unit that is managed by the
data link protocol.

The frame carries the user's data but it also contains some
control information (the header) that is necessary for the protocol for the
smooth running of the dialogue.
Defining a data link protocol involves specifying:
the format of the frames,
the criterion for the start and end of frames,
the error detection technique used,
the place and meaning of the different fields in a frame,
the rules of dialogue: the procedures after error detection or
failure and the supervision of the link.

Page 5
 The delimitation of data: concept of
pennant

During data transmission, it is necessary to identify the beginning and end of the data sequence.
transmit
start bit and stop bit in asynchronous transmission
In synchronous transmission, a flag is used, which is a particular sequence of bits.

Frames are blocks composed of any number of bits and we speak of a bit-oriented protocol.
A flag is used to delimit the frames.
The sequence of binary elements01111110is used as a flag in the case of HDLC protocol.
A transparency mechanism is necessary to prevent the occurrence of the flag sequence inside.
of the frame stuffing bit technique.
It consists, in broadcasting, of inserting a binary element with a value of 0 into the body of the frame after having
I encountered 5 consecutive binary elements with a value of 1.
In reception, if we encounter 5 consecutive binary elements with a value of 1, the automaton looks at the next bit.
:
if it is '1', it is the flag
If it is at '0', the '0' is removed from the sequence (it was introduced into the show)

Page 6
 The delimitation of data: notion of
transparency

The padding bit technique (transmission direction to redo)

With such a mechanism, the emission of more than 5 binary elements of value 1 is therefore prohibited except for
for the delimitation of frames (The flags).
This method has the advantage of allowing the transmission of variable-length frames, without
limitation, but it introduces variations in the duration of user data transmission

Page 7
 Control of the validity of the information

Notion of error

Data circuits can introduce disturbances

(transmission errors), it is necessary to be able to detect these errors.

This is achieved by introducing redundancy into the

transmission and verifying upon receipt that this redundancy
is preserved.

If errors occur, it is necessary to specify some

error correction procedures detected.

Page 8
 The bit error rate

On a finite transmission line, noise can interfere with the signal and be a source of errors.
of transmission.
BER = Bit Error Rate
TEB = Nb bits erronés / Nb bits transmis
Example
The transmitter sends the sequence 0001110101101010
The receiver receives the sequence 0001100101111011
TEB = 3/16 = 0,1875
In practice
Local networks: TEB=10-9
TE generally represents the probability of receiving an erroneous bit.
The probability of correctly receiving a block of N bits is then:
p = (1-TEB)…(1-TEB) = (1-TEB)N
The probability of receiving an erroneous block is then:
p = 1 - (1 - TEB)N
The longer a block is, the lower the probability of correct reception!
Page 9
 Error detection

But: verify the validity of the data received by the recipient

Idée: ajouter une certaine redondance dans l'information transmise
4 techniques:
. echo detection
. detection by repetition
. error detection by calculated key
. error detection and correction by code
echo detection
The receiver returns each received message (echo)
The sender compares the echo to the original message and returns the latter if the two messages are
different
Used by asynchronous terminals
(telnet, minitel, …)
Problems
total redundancy
the echo can itself be erroneous

Page 10
 Error detection

detection by repetition
Each message sent is followed by its own reply
If the two messages are different, the receiver requests a retransmission.

Used in highly disrupted secure environments

real-time applications
Problems
total redundancy
the reply may be erroneous

Page 11
 Key-based detection

error detection by calculated key

The sender adds additional information (key noted CTL - Control -) calculated to
from the original message
The receiver recalculates the key using the same method from the received information and compares it to the key.
received
The receiver ignores the data if the keys are different and may request retransmission.
on error)

The key is sometimes called

CRC : Cyclic Redundancy Check
FCS : Frame Check Sequence
Problem
The key can itself be corrupted.
Page 12
 Detection by calculated key

Technique called parity bit

The parity bit technique consists of adding, to the binary sequence to be protected, a bit, such
that the sum of the transmitted bits set to 1 is even (parity bit) or odd (odd bit).

ASCII characters (7 bits) are protected by the introduction of an 8emebit: the parity bit.
This technique, known as VRC (Vertical Redundancy Check), check
Vertical redundancy only allows for the detection of errors involving an odd number.
of bits.

Page 13
 The detection by calculated key

Techniques called parity bit (Crossed Parity)

In synchronous transmissions, characters are sent in blocks. The parity bit technique is
insufficient, it is complemented by another information: the LRC (Longitudinal Redundancy Check).

A LRC character is added to the transmitted block. Each bit of the LRC character corresponds to the parity of the
bits of each character of the same rank: the first bit of the LRC is the parity of all the 1st bits of each
character, the second of all the 2nd bits...
The character thus formed is added to the message. The LRC itself is protected by a parity bit.
(VRC).

Page 14
 Cross parity: efficiency

Allows to correct all simple errors.

Allows the detection of all errors in 2 or 3 bits
Allows to detect all bursts shorter than the
length of a line
4 bit errors can pass undetected

Page 15
 Detection by calculated key
Cyclic redundancy codes
CRC: Cyclic Redundancy Check
They are also called polynomial codes
based on the treatment of bit sequences as a representation
polynomial with coefficients 0 and 1.
Principle:
we consider a sequence of bits for example: 110111
To this sequence, we associate the following polynomial:
(1.x5+(1.x4+(0.x3+(1.x2) + (1.x1+1 x5+x4+x2+x+1
Remark:Calculations are done in binary (modulo 2: 1+1=0; X+X=0; X=-X)
[for example, (x7+x3)+ (x3+x) = x7+ x ]
Step 1:
A polynomial known to both the transmitter and the receiver is called a polynomial.
generator, let r be its degree:
G(x) = xr+ …. +1; the terms of the two extremes must not be
nuls (xr, x0)
Standardized codes
x16+x12+x5+1 X25 Networks
Page 16
 Key-based detection

Step 2:
let M be the message to be transmitted (of m bits) whose corresponding polynomial is (M(x)) of degree m-1.
We add r bits (called control bits, CRC (or FCS: Frame Check Sequence) to the message M
send a frame P of n bits
(n=m+r) where the corresponding polynomial P(x) of degree n-1 is divisible by G(x)
P(x) is calculated using the following method:
on multiple M(x) by xrwe have the polynomial xr.m(x) This is equivalent to a shift of M(X), by r positions to the
left
we divide xr.M(x) by G(x), namely:
xrM(x) = Q(x)g(x) + C(x)
C(x) is the remainder of this division. By definition, its degree is r-1.

We send the word P (of n=m+r bits) composed of m bits of the message M followed by the r bits of FCS whose
the corresponding polynomial is C(x).

Frame emitted

Message (frame data) CRC (FCS)

M(x) C(x)
P(x)

Page 17
 Keyed detection

In reception:
The receiver performs the division of the received word by G(x). If the result is zero, he concludes that it
There is no mistake.
Problem
Errors that produce a multiple polynomial of G(x) are not detected.
CRC example:
Generator polynomial: x2+x+1Message :110111

Message transmitted: 11011111

Decoding: division of 110111 11 by 111.
We check if the remainder is zero.

Page 18
 Error detection and correction
by code

Hamming code

Hamming Code
The Hamming code is calculated from a measure of dissimilarity between two sequences.
of bits of the same length, called Hamming distance.

Definition (Hamming distance) The Hamming distance between two sequences

m1 and m2 of the same size is the number of bits of the same rank by which these two
sequences differ. It is noted d(m1; m2).

Example :d (1100110; 1010110) = 2. 1100110

V
d ( c ) 1
Property A distant code (C) detected (C) - 1 errors and correct k
2
errors.
The minimum Hamming distance must be as large as possible

Page 19
 Error detection and correction
by code
Hamming code
Structure of a Hamming code
the bits of the message to transmit and the parity control bits.
total length: 2n– 1
length of messages: m = (2n- 1) – n
we talk about code x - y where x = n + m and y = m.
Code efficiency: report y/x

Hamming code example:

a code word - 4 has an efficiency coefficient of 4/7 = 57%,
a code word 15 - 11 has an efficiency coefficient of 11/15 = 73 %
a code word 31 - 26 has an efficiency coefficient of 26/31 = 83 %,

The parity control bits Ciare in position2ipouri=0,1,2,...

1 2 3 4 5 6 7
The bits of the messageDjoccupy the rest of the message
C0 C1 D0 C2 D1 D2 D3

Page 20
 Error detection and correction
by code

Hamming method:

bits numbered from 1 to n

Bits powers of 2 are the r control bits (1,2,4,8...)

the others are the m bits of data (3,5,6,7,9,10...)

control bits = parity calculation on certain data bits: those whose

Decomposition into powers of 2 involves the concerned control bit.

Each data bit is controlled by the control bits that are taken into account in
its decomposition into a sum of powers of 2.

Example: bit 11=8+2+1 is verified by bits 8, 2, and 1.

Page 21
 Error detection and correction
by code
Example

The message to convey a b c d

bits power of 2 are the r control bits (1,2,4,8...)

the others are the m bits of data (3,5,6,7,9,10...)

control bits = parity calculation on certain data bits: those whose

Decomposition into powers of 2 involves the relevant control bit.

1 2 3 4 5 6 7
x y AzB C D

001 010 011 100 101 110 111

x writes a d

x=a+b+d
y=a+c+d
z=b+c+d

Page 22
 Error detection and correction
by code
Find the error in a Hamming word

If the reception control bits C2'C1’C0' valiant 0, there is no error otherwise the
The value of the control bits indicates the position of the error between 1 and 7.

Cibinary sum of the bits used for the calculation of Ci+ Cireceived.
Exercise: is there an error in the following word? 1 0 1 0 1 1 0
indice : 7 6 5 4 3 2 1

Correction
C2' is equal to 1 + 0 + 1 + 0 = 0 (bits at index 7, 6, 5, and 4).

C1' is worth 1 + 0 + 1 + 1 = 1 (bits indexed 7, 6, 3, and 2).

C0' equals 1 + 1 + 1 + 0 = 1 (bits with indices 7, 5, 3, and 1).

C2’C1'C0' ' is worth 011, which means 3 in base 10. Therefore, there is an error in
the index 3 of the word

Page 23
Exercise

Page 24
 Exchange control: mechanisms
of base

The Send & Wait mode

when a frame is well received, the station
receiver sends a frame
of acknowledgment ACK, after receipt of
the ACK the sender can transmit a
new framework.

Problem: the transmitter may get stuck.

indefinitely if M0 or ACK is lost
Solution: The recovery on delay
Time out = timer

Loss of M1

Page 25
 Exchange control: mechanisms
base

The Send & Wait mode

Problem: if the ACK is lost, the data is retransmitted even though it has
already received; the message is then duplicated at the receiver

Loss of the ACK

Page 26
 Exchange control: mechanisms
basic

Solution: Numbering of sent messages

We use 2 counters (Ns in transmission, Nr in reception)
Ns and Nr are initialized to zero
Ns contains the number of the next message to be sent
Nr contains the number of the next block to be received
Ns is transmitted from the transmitter to the receiver.
A message is only delivered on the receiver's side if the received Ns equals the local Nr.
If Ns < Nr, the message has already been received, the receiver 'throws' it away and acknowledges it again.

The numbering of messages prevents duplication and allows for sequencing control.
data received

Page 27
 Exchange control: mechanisms
of base

Problem:
Loss of acquittal

The second M0 received is rejected

Note: the timer must be set correctly.
If the payment deadline is too long

Problem: M1 was never received and

yet he is acquitted
Solution: we should also number the
releases!

Page 28
 Exchange control: mechanisms
basic

Are we waiting to send M?i+1 that MIbe acquitted?

Let us use the Send&Wait mode, we wait
If we don't wait, we must be able to:
the sender stores the unacknowledged messages
number the receipts

Is Ns > Nr possible?
Is it possible to send Mi+1 while Mi is not acknowledged?
The messages do not arrive in the correct order at the receiver.
we either reject messages such as Ns > Nr
either we store the unordered messages on the receiver

Page 29
 Anticipatory protocols
In Send & Wait mode, performance is degraded due to waiting for the ACK before sending a
new message.
Solution: Protocol with anticipation
The transmitter can make several successive transmissions without waiting for the ACK of the previous messages.
All unacknowledged messages on the sender must be stored in 'buffers'.
When an ACK arrives, the sender can release the buffer corresponding to the acknowledged message(s).
If there is no free buffer, the sender must wait for the arrival of an ACK to continue transmitting.
Principle:

Page 30
 The protocols for anticipation

Anticipation window (noted W)

issue credits available to the issuer
Optimal window size when the emission is continuous
(the sender never waits for an ACK)
W optimal = Ta / Tb
RTT: Round Trip Time, round trip time
Tbrepresents the emission time of a block
T:a waiting time, time between the transmission of the first bit
from frame N and the first bit of frame N + 1 in Send and Wait mode,
Sliding window management Send and Wait

Each block is acknowledged. Upon receiving an ACK, the sender releases a buffer and emits
the following block.
Jumping window management
The acquittal is deferred and concerns several messages.
if W=3, M0, M1 and M2 are settled in a single payment
emissions stop when the emission credits are exhausted

Page 31
 Anticipatory protocols

Window management with W=3

Page 32
 The protocols for anticipation

Error recovery policies

Simple rejection
All blocks received out of sequence are rejected.
the protocol is called 'Go Back N'
the transmitter resumes transmission from the
lost message
minimized receiver memory, Wreception = 1

Page 33
 Anticipatory protocols

Error recovery policies

Selective rejection

The receiver stores the messages outside

sequencing
the transmitter only retransmits erroneous messages
W réception = nombre de messages déséquencés
that can be received
optimized transmission - significant memory in
reception

Page 34
 Flow control

The number of buffers (memory buffers) on the receiver is limited, the transmitter must not
emit more data than the receiver can accept, otherwise the packets will be
lost.

Flow control is the mechanism that consists of subordinatingthe emission rateof

the transmitter on the receiver's reception capabilities.

It is calledissue credit (Ct)the number of blocks that the transmitter is allowed to transmit
There are two types of flow control:
Implicit flow control
. the number of credits is set once and for all;
. when the sender has exhausted their credits, they wait for the recipient's authorization to
resume the show.
Explicit or dynamic flow control
. the receiver continuously informs the transmitter about its receiving capabilities;
. the receiver's message contains the new number of available credits.

Page 35
 Flow control

Implicit flow control Explicit or dynamic flow control

Page 36
 Modes of communication

We can distinguish two main modes of communication:

. communication in connected mode (also called 'with connection')
. communication in non-connected mode (also called 'connectionless' or by misuse of language
"datagram"

The offline mode:

1 single phase: data transfer
. each data transfer unit is routed independently
. communicating entities do not store anything ("memoryless").
. the exchanged messages are self-sufficient ("self-content")
The connected mode:
3 phases:
. connection establishment phase
. data transfer phase
. connection release phase
A context (distributed) is shared by the members of the connection.
. allows (facilitates) the control and management of data transfer:
error control, flow control, maintaining sequence, etc.
Page 37
 The HDLC protocol

. HDLC - High Level Data Link Control, OSI Layer 2 Protocol

. First modern protocol, standardized in 1976 by the CCITT (UIT-T)

. Resting on thebit-oriented synchronous transmission.

. Requires a full-duplex synchronous physical link

. It implements a transparency mechanism through a banner.

make the protocol completely independent of the size of the data

. The most well-known variant is the LAP-B mode.

uses a flow control mechanism.
It is balanced or symmetrical: both stations have the same prerogatives.
It uses full-duplex transmission means on an exploited point-to-point link.
in full duplex;

Page 38
 The HDLC protocol

Different modes of HDLC:

Normal or synchronous mode
NRM - Normal Response Mode
or LAP - Link Access Protocol
master/slave relationship
(primary solicitation)
Asynchronous mode
ABM - Asynchronous Balanced Mode
each end is primary in emission
and secondary in reception (balanced mode)
point-to-point link only
full duplex (LAP Balanced - RNIS)

Page 39
 The HDLC protocol

All information is carried in a unique structure: the frame.

The frame is of variable length and is delimited by a flag;
In the absence of data, the flag is sent to maintain synchronization between the
frames;
In the case of consecutive frame emissions, the flag marks the end of one frame and the beginning of the next.
next;
Transparency is ensured by the stuffing bit technique;
Very effective error control by CRC with error recovery.

The entity is said to be primary if it initiates the communication.

protocol based on the binary element ("oriented" bit)
Page 40
 Structure of an HDLC frame

Frame format

Fanion=01111110
The address field spans an octet and identifies one of the ends of the
[Link] designed for multipoint lines. It can support up to 256
terminals by line.
The command field describes the type of the frame: it spans 1 byte but can
to be extended to 2 bytes in the mode called extended mode.
The information field is an optional field containing any number.
binary elements representing user data.
The FCS (Frame Check Sequence) field is a frame check sequence.
(it is obtained by a polynomial control of the generator polynomial
x16 + x12+ x5+ 1).
The left field is the first transmitted, the right field is the last.
Page 41
Structure of an HDLC frame

Page 42
 Structure of an HDLC frame

Types of frames:
There are three types of frames identified by the Command field.
The information frame or frame I: allows the transmission of user data.
Supervision frames or S frames: allow acknowledgment and flow control.
They do not carry data.
Unnumbered frames or U frames: are used for all the
control functions of the link such as initialization, release... They do not
do not transport data.
The field Command:

Page 43
 The command field

The I framework (Information):

Frame I allows for data transmission. It is numbered 'the counter'
It also allows for the acknowledgment of frames exchanged in the direction
inverse thanks to meter No.
. Ns - counter of I frames emitted
. Nr - counter of received frames I
. Nr contains the number of the next expected frame
. Nr = n acquits the (n-1) previous frames

Page 44
 The command field

The frame I (Information):

I(0,0)
I(1,0)

I(0,2)
I(1,2)

I(2,2)
I(3,2)
I(4,2)
I(2,5)

Page 45
 The command field

The S frames (Supervision):

Allow the settlement and indication of the availability status of the stations (capable or not to receive)
new frames).
Used for error control and flow control. Contain a number Nr
The four supervision frameworks are:
The RR (Receiver Ready) frame indicates that the equipment is ready to receive new frames.
Information. The sequence number Nr indicates the number of the next expected frame.
indicate that all the information frames with number Ns strictly less than Nr have been
well received.
the RNR (Receiver Not Ready) frame indicates that the equipment is not able to receive
new information frameworks. The number Nr has the same meaning as for RR.
the REJ (Reject) frame indicates that the equipment requests the immediate cessation of ongoing emissions
information frame and the resumption of transmission. The sequence number Nr indicates where
resume the transmission.
The SREJ (Selective Reject) frame: protection against errors confirms the receipt of frames from
data of no. < N(R)
request the retransmission of the
trame of number = N(R)
not used by LAP-B

Page 46
 The command field
the RR (Receiver Ready) frame the REJ (Reject) frame
I(0,0) I(0,0)
I(1,0) I(1,0)
I(2,0)
S(RR,2)
I(3,0)
I(2,0)
I(4,0)
I(3,0)
S(REJ,1)
S(RR,4) I(1,0)
I(4,0) I(2,0)
I(5,0) I(3,0)

the RNR (Receiver Not Ready) frame The SREJ (Selective Reject) frame
I(0,0) I(0,0)
I(1,0)
I(1,0)
I(2,0)
I(2,0)
S(RNR,2)
I(3,0)
S(RR,2) I(4,0)
I(2,0)
I(3,0) S(SREJ,2)
I(2,0)
I(4,0)
I(5,0)
S(RR,5)
Page 47
 The command field

The frames U (Unnumbered frames):

U frames are used to perform additional link layer control functions:
SABM (Set Asynchronous Balanced Mode) allows for the initialization of operation in balanced mode;
DISC(DISConnect) allows to logically break the connection between two stations;
UA (Unnumbered Acknowledgement) allows for the acknowledgment of SABM or DISC orders;
FRMR (Frame Reject) allows rejecting an invalid order (correct from the perspective of the
error detection but inconsistent with the state of the dialogue;
DM (Disconnect Mode) allows indicating the disconnection state of a station. It is used to
in particular, to respond negatively to a SABM initialization.

Page 48
 The command field

The P/F bit - control bit

. It is referred to as P in a command frame, F in a response frame
. P (Poll) = 1 demande de réponse explicite ou non émise par une station primaire
. F (Final) = 1 indication of an explicit response issued by a secondary station,
following an explicit request made by an elementary school
. P=1 - solicits an explicit response from the secondary
. Response to P=1 by F=1 - the secondary responds with a confirmation
. A station that receives a command frame with the P/F bit = 1 must respond
with P/F=1 P=0
P=0
P=1
F=0
F=0
F=1

P=0

Page 49
HDLC frame

Page 50
 Structure of an HDLC dialogue

Connection and release:

A point-to-point connection occurs in three stages: mode initialization,
exchanges of information frames with error and flow control, and finally
connection closure.
SNRM: Set normal response mode
SABM: Set Asynchronous Balanced Mode
UA: Unnumbered Acknowledgement

DISC: DISConnect
Unnumbered Acknowledgement

Page 51
 Structure of an HDLC dialogue

Recovery rules for mode LAP_B

Overflow (flow control)
. the station that can no longer receive detrames emits an RNR whose Nr indicates the
first frame not accepted
. it emits a frameRR when it is ready to receive new ones again
frames
Transmission error
. Any frame for which the analysis of the FCS indicates a transmission error is ignored.
no other action is taken
Sequence number error Ns
. the frame whose N is not the expected one is ignored along with the following ones
. the station receiving this frame sends a REJ frame whose number Nr indicates the
expected framework
Two timers
. transmission timer (T1) initialized by the transmitter at each emitted frame
. acknowledgment timer (T2) corresponding to the maximum delay after which
the receiver must, if it has no data to send, send an acknowledgment

Page 52
 Structure of an HDLC dialogue

Recovery rules for LAP_B mode

Replay on time-out
. the station that does not receive any acknowledgment of the information frames sent out
At time T1, resumes the transmission of the first unacknowledged frame by positioning
the bitP/F at 1
. the station can continue to broadcast normally the other streams from now on
receipt of a receipt with the bitP/F set to 1

State variables V(s), V(r), and DN(r)

At each station, the implementation of procedures includes the management of control.
timers and state variables called V(s), V(r), and DN(r) defined by:
. V(S): the number (modulo 8) of the next information frame that the station is
ready to issue.
. V(R): number (modulo 8) of the next information frame that the station is
ready to receive.
. number plus one (modulo 8) of the last information frame that the
the station had issued and which was settled by the distant station.

Page 53
Example of data exchange

SABM: Set Asynchronous Balanced Mode

UA: Unnumbered Acknowledgement

Chronogram of a transmission

Page 54
Example of data exchange

Chronogram of a transmission

Page 55
Example of data exchange

Page 56
Example of data exchange

Page 57