CSE3133 Data and Telecommunications

Chapter 11: Data Link Control

Sumaya Kazary
Assistant Professor
Department of Computer Science and Engineering
Dhaka University of Engineering & Technology, Gazipur

Acknowledgement
Thanks to the authors of all the books and online tutorials used in this slide.
  This study deals with the algorithms for achieving
reliable &efficient communication.
2
3
4
 11-1 FRAMING

The Data Link Layer needs to pack bits into frames,

so that each frame is distinguishable from another.

 Our postal system practices a type of framing.

The simple act of inserting a letter into an

envelope separates one piece of information from
another; the envelope serves as the delimiter.

5
 11-1 FRAMING

6
7
8
9
10
 Example : Byte stuffing

11
 Figure 11.2 Byte stuffing and unstuffing

Sx

Rx

12
 Note

Byte stuffing is the process of adding 1

extra byte whenever there is a flag or
escape character in the text.

13
 (0x7E)

Figure 11.3 A frame in a bit-oriented protocol

14
 Note

Bit stuffing is the process of adding one

extra 0 whenever five consecutive 1s
follow a 0 in the data, so that the
receiver does not mistake
the pattern 01111110 for a flag.

15
 Figure 11.4 Bit stuffing and unstuffing

Sx

Rx

16
 11-2 FLOW AND ERROR CONTROL

 The most important responsibilities of the data link

layer are flow control and error control. Collectively,
these functions are known as data link control.

Flow control is a speed control mechanism.

Flow control coordinates the amount of data that

can be send before receiving an acknowledgement.

17
18
19
 11-3 PROTOCOLS

 Now let us see how the data link layer can combine
framing, flow control, and error control to achieve the
delivery of data from one node to another.
 The protocols are normally implemented in
software by using one of the common programming
languages.
 To make our discussions language-free, we have
written in pseudocode a version of each protocol that
concentrates mostly on the procedure instead of
delving into the details of language rules.

11.20
 Figure 11.5 Taxonomy of protocols discussed in this chapter

11.21
 11-4 NOISELESS CHANNELS

Let us first assume we have an ideal channel in which

no frames are lost, duplicated, or corrupted. We
introduce two protocols for this type of channel.

Topics discussed in this section:

Simplest Protocol
Stop-and-Wait Protocol

11.22
23
 Figure 11.6 The design of the simplest protocol with no flow or error control

11.24
 Algorithm 11.1 Sender-site algorithm for the simplest protocol

Algorithm 11.2 Receiver-site algorithm for the simplest protocol

11.25
26
 2.

27
 Stop-and-wait Protocol

Sender Receiver

Data

Acknowledgement
Data

Acknowledgement
Data

Acknowledgement

28
 Problems of Stop-and-wait Protocol
1. Due to lost data !!!

Sender Receiver

Data

29
 Problems of Stop-and-wait Protocol
2. Due to lost Acknowledgement !!!
Sender waits for an infinite amount of time
for ack.
Sender Receiver
Data

Acknowledgement

30
 Figure 11.8 Design of Stop-and-Wait Protocol

11.31
32
 11-5 NOISY CHANNELS

Although the Stop-and-Wait Protocol gives us an idea

of how to add flow control to its predecessor, noiseless
channels are nonexistent. We discuss three protocols
in this section that use error control.

Topics discussed in this section:

Stop-and-Wait Automatic Repeat Request
Go-Back-N Automatic Repeat Request
Selective Repeat Automatic Repeat Request

11.33
1. Stop-and-Wait ARQ Overview
 Sender waits “reasonable” amount of time for ACK
 Thus Sender needs a countdown timer

 Start the timer when a packet is sent

 retransmits if no ACK received within the timeout

period
 If Frame (or ACK) just delayed (not lost):
 retransmission will create duplicate packet

 Thus it requires packet sequence number and ack

number to be used
 Only two numbers are used: 0, 1

 Receiver’s Ack number is what he is expected next

 After receiving Pkt 0, sends back ACK 1

 After receiving Pkt 1, sends back ACK 0

35
 Figure 11.10 Design of the Stop-and-Wait ARQ Protocol

11.36
 Example 11.3
Figure 11.11 shows an example of Stop-and-Wait ARQ. Frame 0 is sent and
acknowledged. Frame 1 is lost and resent after the time-out. The resent frame 1
is acknowledged and the timer stops. Frame 0 is sent and acknowledged, but the
acknowledgment is lost. The sender has no idea if the frame or the
acknowledgment is lost, so after the time-out, it resends frame 0, which is
acknowledged.

11.37
Stop-and-wait operation
sender receiver
first packet bit
transmitted, t = 0

first packet bit arrives

RTT last packet bit arrives, send ACK

ACK arrives, send next

packet, t = RTT + L / R

L: packet bit length

R: link bandwidth (bps)

Utilization = L/R / (RTT+L/R)

 Example 11.4

Assume that, 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. If the system data frames are 1000 bits
in length, what is the utilization percentage of the link?
Solution

L = 1000 bits, R = 1Mbps, RTT = 20ms

Utilization = 1/ 21 = 4.8%

For this reason, for a link with a high bandwidth or long

delay, the use of Stop-and-Wait ARQ wastes the capacity of the link.

11.39
40
41
42
43
44
 Cumulative ACK
ACK(n): ACKs all frames up to and include sequence #(n-1)
have been received may receive duplicate ACKs (see receiver)
 A single timer for the oldest transmitted but UNACK frames

 Timeout: retransmit all frames in window (up to N frame)

45
46
 Out-of-order frame:
discard (don’t buffer) -> no receiver buffering!
Re-ACK frame with highest in-order seq #

Stop-and-Wait ARQ is a special case of

Go-Back-N ARQ in which the size of the
send window is 1.

47
 Example 11.6
Figure 11.16 shows an example of Go-Back-N. This is an example of a case
where the forward channel is reliable, but the reverse is not. No data frames
are lost, but some ACKs are delayed and one is lost. The example also shows
how cumulative acknowledgments can help if acknowledgments
are delayed or lost.

Stop Timer

Start Timer

Cumulative acknowledgments can help if acknowledgments are delayed or lost

 Example 11.7
Figure 11.17 shows what happens when a frame is lost. Frames 0, 1, 2,
and 3 are sent & frame 1 is lost.

Stop Timer

Start Timer
 Figure 11.17 shows that because of one packet
lost, all following packets will need to be
retransmitted, even if they have arrived at the
destination
 A great waste of bandwidth

Better protocol: selective repeat ARQ

50
Selective Repeat ARQ
 Problem with Go-back-N:
 Sender: resend many packets with a single lose
 Receiver: discard many good received (out-of-order) packets
 Very inefficient when N becomes bigger (in high-speed network)
 Solution: Receiver individually acknowledges all correctly
received pkts
 buffers pkts, as needed, for eventual in-order delivery to upper
layer
 sender only resends pkts for which ACK not received
 sender keeps timer for each unACKed pkt
 sender window
 N consecutive seq #’s
 again limits seq #s of sent, unACKed pkts
52
53
 Figure 11.18 Send window for Selective Repeat ARQ

11.54
55
 Figure 11.19 Receive window for Selective Repeat ARQ

In Selective Repeat ARQ, the size of the

sender and receiver window
must be at most one-half of 2m.

56
Example 11.8
This example is similar to Example 11.3 in which frame 1 is lost. We show
how Selective Repeat behaves in this case. The following shows the
situation.

Figure 11.23
58
Q&A