Data Link Layer

Protocols
Underlying Assumptions of the models
► The physical layer, data link layer, and network layer are independent
processes that communicate by passing messages back and forth.
► Machine A wants to send a long stream of data to machine B, using a reliable,
connection-oriented service. Later, we will consider the case where B also
wants to send data to A simultaneously.
► A is assumed to have an infinite supply of data ready to send and never has to
wait for data to be produced.
► Machines do not crash.
► A frame consists of an embedded packet, some control information (in the
header), and a checksum (in the trailer).
► We assume that there exist suitable library procedures to physical layer to
send a frame and from physical layer to receive a frame. These procedures
compute and append or check the checksum so that it not part of the
protocols we develop.
The Setup
► Initially, the receiver has nothing to do. It just sits around waiting for
something to happen.
► The procedure call wait for event(&event) is used by the data link layer. This
procedure only returns when something has happened (e.g., a frame has
arrived).
► Upon return, the variable event tells what happened.
► When a frame arrives at the receiver, the checksum is recomputed. If the
checksum in the frame is incorrect (event = cksum err) else (event = frame
arrival)
► The data link layer acquires an undamaged frame, checks the control
information in the header, and, if everything is all right, passes the packet
portion to the network layer.
► Under no circumstances is a frame header ever given to a network layer.
Data Structures Employed
► boolean - an enumerated type and can take on the values true and false
► seq nr - a small integer used to number the frames, takes values 0 to MAX SEQ
► packet - the unit of information exchanged between the network layer and
the data link layer, size is MAX PKT bytes
► frame kind – Type of frame like data frame or control frame or ack frame
► frame - composed of four fields: kind, seq, ack, and info,
► the first three of which contain control information are collectively called the
frame header.
► The seq and ack fields are used for sequence numbers and acknowledgements,
respectively;
► The info field of a data frame contains a single packet; the info field of a
control frame is not used.
Data Structures Employed
Library Routines Employed
► wait for event : sits in a tight loop waiting for an event to happen.
► to network layer and from network layer: are used by the data link layer to
pass packets to the network layer and accept packets from the network layer,
respectively.
► from physical layer and to physical layer: deal with the interface between
layers physical and data link layers.
► start timer and stop timer: turn the timer on and off in DLL
► start ack timer and stop ack timer: control an auxiliary timer used to
generate acknowledgements under certain conditions.
► enable network layer and disable network layer : are used in the more
sophisticated protocols, where we no longer assume that the network layer
always has packets to send.
► macro inc : increments sequence number of frames mostly in circular manner.
Library Routines Employed
Library Routines Employed
Elementary Protocols
Elementary Data Link Protocols

► An Unrestricted Simplex Protocol or A Utopian Simplex Protocol

► A Simplex Stop-and-Wait Protocol for an Error-Free Channel
► A Simplex Stop-and-Wait Protocol for a Noisy Channel
Unrestricted Simplex Protocol
► Data are transmitted in one direction only.
► Both the transmitting and receiving network layers are always ready.
► Processing time can be ignored.
► Infinite buffer space is available.
► The communication channel between the data link layers never damages or
loses frames.
► The protocol consists of two distinct procedures, a sender and a receiver.
► The sender runs in the data link layer of the source machine, and the receiver
runs in the data link layer of the destination machine.
► No sequence numbers or acknowledgements are used here, so MAX SEQ is not
needed.
► The only event type possible is frame arrival (i.e., the arrival of an
undamaged frame).
Unrestricted Simplex Protocol - Sender

► The sender is in an infinite while loop just pumping data out onto the line as
fast as it can.
► The body of the loop consists of three actions:
► go fetch a packet from the network layer
► construct an outbound frame using the variable s,
► send the frame.
► Only the info field of the frame is used by this protocol, because the other
fields have to do with error and flow control and there are no errors or flow
control restrictions here.
Unrestricted Simplex Protocol - Receiver

► The receiver waits for something to happen, the only possibility being the
arrival of an undamaged frame.
► Eventually, the frame arrives and the procedure wait for event returns, with
event set to frame arrival (which is ignored anyway).
► The call to from physical layer removes the newly arrived frame from the
hardware buffer and puts it in the variable r, where the receiver code can get
at it.
► Finally, the data portion is passed on to the network layer, and the data link
layer settles back to wait for the next frame.
Unrestricted Simplex Protocol
Unrestricted Simplex Protocol
Simplex Stop-and-Wait Protocol for an
Error-Free Channel
► Tackles the problem of preventing the sender from flooding the receiver with frames
faster than the latter is able to process them.
► Solution to this problem is to have the receiver provide feedback to the sender.
► The receiver sends a acknowledgement frame back to the sender which gives the
sender permission to transmit the next frame.
► After having sent a frame, the sender is required to wait until the acknowledgement
frame arrives.
► Protocols in which the sender sends one frame and then waits for an
acknowledgement before proceeding are called stop-and-wait.
► Though data traffic in this example is simplex, going only from the sender to the
receiver, frames do travel in both directions.
► The communication channel between the two data link layers needs to be capable
of bidirectional information transfer.
► However, this protocol entails a strict alternation of flow. A half-duplex physical
channel would suffice here.
Simplex Stop-and-Wait Protocol for an
Error-Free Channel
► The sender starts out by fetching a packet from the network layer, using it to
construct a frame, and sending it on its way.
► The sender must wait until an acknowledgement frame arrives before looping
back and fetching the next packet from the network layer.
► The sending data link layer need not even inspect the incoming frame as
there is only one possibility. The incoming frame is always an
acknowledgement.
► The receiver after delivering a packet to the network layer sends an
acknowledgement frame back to the sender before entering the wait loop
again.
► Because only the arrival of the frame back at the sender is important, not its
contents, the receiver need not put any particular information in it.
Simplex Stop-and-Wait Protocol for a
Noisy Channel
► Frames may be either damaged or lost completely.
► Solution 1:
► The sender sends a frame
► The receiver would send an acknowledgement frame only if the data were
correctly received.
► If a damaged frame arrived at the receiver, it would be discarded and no ack. will
be sent to the sender
► After a while the sender would time out and send the frame again.
► This process would be repeated until the frame finally arrived intact.
► Adding a timer to the earlier model looks sufficient.
Simplex Stop-and-Wait Protocol for a
Noisy Channel
1. The network layer on A gives packet 1 to its data link layer. The packet is
correctly received at B and passed to the network layer on B. B sends an
acknowledgement frame back to A.
2. The acknowledgement frame gets lost completely. It just never arrives at all.
3. The data link layer on A eventually times out. Not having received an
acknowledgement, it (incorrectly) assumes that its data frame was lost or
damaged and sends the frame containing packet 1 again.
4. The duplicate frame also arrives intact at the data link layer on B and is
unwittingly passed to the network layer there. If A is sending a file to B, part
of the file will be duplicated (i.e., the copy of the file made by B will be
incorrect and the error will not have been detected). In other words, the
protocol will fail.
Simplex Stop-and-Wait Protocol for a
Noisy Channel
► Adding a sequence number solves this issue.
► The only ambiguity in this protocol is between a frame, m, and its direct successor, m + 1.
► If frame m is lost or damaged, the receiver will not acknowledge it, so the sender will keep trying
to send it.
► Once it has been correctly received, the receiver will send an acknowledgement to the sender.
► Depending upon whether the acknowledgement frame gets back to the sender correctly or not, the
sender may try to send m or m + 1.

► A 1-bit sequence number (0 or 1) is therefore sufficient.

► At each instant of time, the receiver expects a particular sequence number next.
► When a frame containing the correct sequence number arrives, it is accepted and passed to the
network layer, then acknowledged. Then the expected sequence number is incremented modulo 2
(i.e., 0 becomes 1 and 1 becomes 0).
► Any arriving frame containing the wrong sequence number is rejected as a duplicate.
► However, the last valid acknowledgement is repeated so that the sender can eventually discover
that the frame has been received.
Simplex Stop-and-Wait Protocol for a
Noisy Channel
► Protocols in which the sender waits for a positive acknowledgement before advancing to
the next data item are often called ARQ (Automatic Repeat reQuest) or PAR (Positive
Acknowledgement with Retransmission).
► The sender remembers the sequence number of the next frame to send in next frame to
send; the receiver remembers the sequence number of the next frame expected in frame
expected.
► After transmitting a frame and starting the timer, the sender waits
► an acknowledgement frame arrives undamaged - the sender fetches the next packet from its
network layer, puts it in the bufferand advances the sequence number.
► a damaged acknowledgement frame staggers in, or the timer expires - neither the buffer nor the
sequence number is changed so that a duplicate can be sent.

► When a valid frame arrives at the receiver, its sequence number is checked to see if it is a
duplicate.
► If not, it is accepted, passed to the network layer, and an acknowledgement is generated.
► If duplicate or damaged data not passed to the network layer, but acknowledgement of last
correctly received frame is sent to the sender.
Sliding Window Protocols
Need for Sliding Window Protocols
► There is a need to transmit data in both directions.

► Solution 1: The data frames from A to B are intermixed with the ack. frames
from A to B.

► Solution 2: The technique of temporarily delaying outgoing acks. so that they

can be hooked onto the next outgoing data frame is known as piggybacking.

► Advantage of using piggybacking: better use of the available channel

bandwidth.

► Complication: How long should the data link layer wait for a packet onto
which to piggyback the acknowledgement?

► If a new packet arrives quickly, the acknowledgement is piggybacked onto it.

Otherwise, if no new packet has arrived by the end of this time period, the
data link layer just sends a separate acknowledgement frame.
Sliding Window Protocols – Basic
Assumptions
► Each outbound frame contains a sequence number, ranging from 0 up to some
maximum.
► The stop-and-wait sliding window protocol uses n = 1, restricting the
sequence numbers to 0 and 1.
► The sender maintains a set of sequence numbers corresponding to frames it is
permitted to send. These frames are said to fall within the sending window.
► The receiver also maintains a receiving window corresponding to the set of
frames it is permitted to accept.
One-bit Sliding Window Protocol

A sliding window of size 1, with a 3-bit sequence number.

(a) Initially. (b) After the first frame has been sent. (c) After the first
frame has been received. (d) After the first acknowledgement has been
received.
One-bit Sliding Window Protocol
One-bit Sliding Window Protocol
One-bit Sliding Window Protocol –
Normal Scenario
► Assume that computer A is trying to send its frame 0 to computer B and that B is
trying to send its frame 0 to A.
► Suppose that A sends a frame to B, but A’s timeout interval is a little too short.
► Consequently, A may time out repeatedly, sending a series of identical frames, all
with seq = 0 and ack = 1.
► When the first valid frame arrives at computer B, it will be accepted and frame
expected will be set to a value of 1.
► All the subsequent frames received will be rejected because B is now expecting
frames with sequence number 1, not 0.
► Furthermore, since all the duplicates will have ack = 1 and B is still waiting for an
acknowledgement of 0, B will not go and fetch a new packet from its network layer.
► After every rejected duplicate comes in, B will send A an frame containing seq = 0
and ack = 0. Eventually, one of these will arrive correctly at A, causing A to begin
sending the next packet.
► No combination of lost frames or premature timeouts can cause the protocol to
deliver duplicate packets to either network layer, to skip a packet, or to deadlock.
The protocol is correct.
One-bit Sliding Window Protocol –
Normal Scenario
The notation is (seq, ack, packet number).
One-bit Sliding Window Protocol –
Abnormal Scenario
The notation is (seq, ack, packet number). A and B simultaneously initiate the
communication.
Pipelining
► Eliminating the assumption that, transmission time required for a frame to
arrive at the receiver plus the transmission time for the acknowledgement to
come back is negligible.
► This is achieved by eliminating the rule requiring a sender to wait for an
acknowledgement before sending another frame.
► Solution is allowing the sender to transmit up to w frames before blocking,
instead of just 1.
► With a large enough choice of w the sender will be able to continuously
transmit frames since the acknowledgements will arrive for previous frames
before the window becomes full, preventing the sender from blocking.
► This technique of keeping multiple frames in flight is an example of
pipelining.
► What happens if a frame in the middle of a long stream is damaged or lost?
Error in Pipelining
► Two basic approaches are available for dealing with errors in the presence of
pipelining
► go-back-n

► selective repeat
Go back N

► The data link layer refuses to accept any frame except the next one it must
give to the network layer.
► If the sender’s window fills up before the timer runs out, the pipeline will
begin to empty.
► Eventually, the sender will time out and retransmit all unacknowledged
frames in order, starting with the damaged or lost one.
► This approach can waste a lot of bandwidth if the error rate is high.
► When an acknowledgement comes in for frame n, frames n − 1, n − 2, and so
on are also automatically acknowledged.
► This type of acknowledgement is called a cumulative acknowledgement.
Selective Repeat

► A bad frame that is received is discarded, but any good frames received after
it are accepted and buffered.
► When the sender times out, only the oldest unacknowledged frame is
retransmitted.
► If that frame arrives correctly, the receiver can deliver to the network layer,
in sequence, all the frames it has buffered.
► This is often combined with having the receiver send a negative
acknowledgement (NAK) when it detects an error.
► NAKs stimulate retransmission before the corresponding timer expires and
thus improve performance.
Restriction on max. no. of outstanding
frames – Go back N
► The maximum number of frames that may be outstanding at any instant is not the
same as the size of the sequence number space.
► For go-back-n, MAX SEQ frames may be outstanding at any instant, even though
there are MAX SEQ + 1 distinct sequence numbers (which are 0, 1, .. ., MAX SEQ).
► Consider the following scenario with MAX SEQ = 7:
1. The sender sends frames 0 through 7.
2. A piggybacked acknowledgement for 7 comes back to the sender.
3. The sender sends another eight frames, again with sequence numbers 0 through 7.
4. Now another piggybacked acknowledgement for frame 7 comes in.
► Did all eight frames belonging to the second batch arrive successfully, or did all
eight get lost (counting discards following an error as lost)?
► In both cases the receiver would be sending frame 7 as the acknowledgement. The
sender has no way of telling.
► For this reason the maximum number of outstanding frames must be restricted to
MAX SEQ.
Timers – Go back N
► Multiple outstanding frames, it logically needs multiple timers, one per
outstanding frame.
► Each frame times out independently of all the other ones.
A Protocol Using Selective Repeat
► The selective repeat protocol, is to allow the receiver to accept and buffer the
frames following a damaged or lost one.
► Both sender and receiver maintain a window of outstanding and acceptable
sequence numbers, respectively.
► The sender’s window size starts out at 0 and grows to some predefined maximum.
► The receiver’s window, in contrast, is always fixed in size and equal to the
predetermined maximum.
► The receiver has a buffer reserved for each sequence number within its fixed
window.
► Associated with each buffer is a bit (arrived ) telling whether the buffer is full or
empty.
► Whenever a frame arrives, its sequence number is checked to see if it falls within
the window.
► If so and if it has not already been received, it is accepted and stored.
Restriction on max. no. of outstanding
frames – Selective repeat
► Non-sequential receive introduces further constraints on frame sequence numbers
compared to protocols in which frames are only accepted in order.
► Suppose that we have a 3-bit sequence number, so that the sender is permitted to
transmit up to seven frames before being required to wait for an acknowledgement.
► The sender now transmits frames 0 through 6. The receiver’s window allows it to
accept any frame with a sequence number between 0 and 6 inclusive.
► All seven frames arrive correctly, so the receiver takes them and advances its
window to allow receipt of 7, 0, 1, 2, 3, 4, or 5. All seven buffers are marked
empty.
► The sender eventually times out and retransmits frame 0.
► When this frame arrives at the receiver, a check is made to see if it falls within the
receiver’s window.
► Unfortunately, frame 0 is within the new window, so it is accepted as a new frame.
The receiver also sends a (piggybacked) acknowledgement for frame 6, since 0
through 6 have been received.
Restriction on max. no. of outstanding
frames – Selective repeat
► The sender is happy to learn that all its transmitted frames did actually arrive
correctly, so it advances its window and immediately sends frames 7, 0, 1, 2, 3, 4,
and 5.
► Frame 7 will be accepted by the receiver and its packet will be passed directly to
the network layer.
► Immediately thereafter, the receiving data link layer checks to see if it has a valid
frame 0 already, discovers that it does, and passes the old buffered packet to the
network layer as if it were a new packet.
► Consequently, the network layer gets an incorrect packet, and the protocol fails.
► The essence of the problem is that after the receiver advanced its window, the new
range of valid sequence numbers overlapped the old one.
► Consequently, the following batch of frames might be either duplicates (if all the
acknowledgements were lost) or new ones (if all the acknowledgements were
received).
Restriction on max. no. of outstanding
frames – Selective repeat
► The way out of this dilemma lies in making sure that after the receiver has
advanced its window there is no overlap with the original window.
► To ensure that there is no overlap, the maximum window size should be at
most half the range of the sequence numbers.
► With 3 bits, the sequence numbers range from 0 to 7. Only four
unacknowledged frames should be outstanding at any instant.
► That way, if the receiver has just accepted frames 0 through 3 and advanced
its window to permit acceptance of frames 4 through 7, it can unambiguously
tell if subsequent frames are retransmissions (0 through 3) or new ones (4
through 7).
► In general, the window size for protocol 6 will be (MAX_SEQ + 1)/2.
Restriction on max. no. of outstanding
frames – Selective repeat
Buffers and Timers – Selective Repeat
► The number of buffers needed is equal to the window size, not to the range
of sequence numbers.
► The number of timers needed is equal to the number of buffers, not to the
size of the sequence space.
► Protocol 6 also relaxes the implicit assumption that the channel is heavily
loaded.
► An auxiliary timer is started by start ack timer after an in-sequence data
frame arrives.
► If no reverse traffic has presented itself before this timer expires, a separate
acknowledgement frame is sent.
► It is essential that the timeout associated with the auxiliary timer be shorter
than the timeout used for timing out data frames.
► To avoid making multiple requests for retransmission of the same lost frame,
the receiver should keep track of whether a NAK has already been sent for a
given frame.