[Back to Lecture Notes page]

Algorithms for Data Link Layer Protocols

Sub-topic outline:

• Simplex Protocols
• Unrestricted Simplex
• Simplex Stop-and-Wait
• Simplex with Noisy Channel
• Sliding Window Protocols
• One bit Sliding Window
• Sliding Windows with Go Back n
• Sliding Window with Selective Repeat

Some Terminology

• Frame vs Packets
• Frame Headers
• Different kinds of frames: data, acknowledgment – Data frames contains the packets from the Network layer. Acknowledgment frames do not. Acknowledgment frames are generated by the receiving DLL to send back to the sending DLL.

Unrestricted Simplex Protocol

• The simplest case (not very realistic, but it is a starting point for us):
• data transmitted in one direction only (ie. simplex).
• Network layer always ready – no need to wait
• Ignore processing time
• Infinite buffer (memory) space
• No errors in transmission

• Sender will just repeatedly:

1. Get a packet from the Network layer
2. Put the packet into a frame
3. Send the frame off

• Receiver will repeatedly:

1. Wait for frame
2. When a frame arrives, take the packet out
3. Give the packet to the Network layer

Simplex Stop-and-Wait Protocol

• Same as unrestricted simplex, but assume (more realistic)
• the network layer may not always be ready
• the network layer needs time to process
• receiving DLL may not have enough buffer space to store all incoming frames
• One possible solution: slow down the transmission rate
• But result would be bad bandwidth utilization.

• A better solution would be that once the sender sends a frame, it waits for an acknowledgment from the receiver before sending another frame.
• Sender will repeatedly

1. Get a packet from the Network layer
2. Put the packet into a frame
3. Send the frame off
4. Wait for acknowledgment from the receiver

• Receiver will repeatedly:

1. Wait for frame
2. When a frame arrives, take the packet out
3. Give the packet to the Network layer
4. Send an empty acknowledgment frame to the sender

Simplex Protocol with Noisy Channel

• Same as simplex stop-and-wait, but assume frames can get damaged or lost in transmission
• Receiver can detect damaged frames using the checksum.
• Possible solution: have sender keep a timer
• When timer times out, re-send the frame.
• If receiver receives a damaged frame, discard and wait for re-sent frame – if the frame is lost, the receiver won’t even get it, so will wait for the re-sent frame anyway.
• Problem: what happens if an acknowledgment frame gets lost? Sender times-out, re-send frame, and receiver will think this re-sent frame is a new frame!
• A better solution: have sender keep a timer, AND put sequence numbers in the frame as well so the receiver will know if a frame is a duplicate one.
• Sender will repeatedly

1. Get a packet from the Network layer
2. Put the packet into a frame, put a sequence number in the frame
3. Start timer and send the frame off
4. Wait for acknowledgment from the receiver
5. If time-out then, go back to 2 and send again
6. If acknowledgment with the correct sequence number arrives, increment the current sequence number.

• Receiver will repeatedly:

1. Wait for frame
2. When a frame arrives, check the sequence number is not one already received.
   If it is, send acknowledgment frame with the received sequence number (the sender obviously didn’t get the previous acknowledgment), and go back to 1.
   If not, go to 3.
3. Take the packet out
4. Give the packet to the Network layer
5. Send an acknowledgment frame with the current sequence number to the sender. Increment the current sequence number.

• We only really need the sequence number to alternate between 0 and 1 - this means that the sender will not send a new frame unless the last frame is acknowledged by the receiver. Both sender and receiver will start with the same sequence number. Incrementing the sequence number will be modulo 2 (ie. incrementing 1 will get (1+1) mod 2 = 0, and incrementing 0 will get (0+1) mod 2 = 1).
• This scheme is also called Positive Acknowledgment with Retransmission (PAR) or Automatic Repeat reQuest (ARQ).

Sliding Window Protocols

• In simplex protocols, all transmission is in one direction – at any single time, we consider a machine either as a sender or a receiver. We never consider the situation where a machine may be communicating with another machine by sending and receiving frames at the same time – that is, where the sent frames are interspersed with the receiving frames in the same channel.
• For full-duplex (two directions, data going in either direction at any time) transmission, we use the same channel to mix the data and acknowledgment frames to and from A to B – better channel utilization. So the algorithms from now on will not be separated into the sender and receiver parts. The algorithm must expect either a new packet from the network layer to send, or a frame received from another machine, through the physical layer. The reason this is better is that if the machine is idle in certain aspects (eg. waiting for an acknowledgment), it can spent the time and the channel for something else (eg. receiving a frame from the other machine).

• An added strategy to improve channel utilization: piggybacking – piggybacking is the idea where instead of sending an acknowledgment in a frame by itself, we wait for the next data frame that this receiver wants to send to the sender, and add a few bits to it to store the acknowledgment. This way, we only incur the overhead of creating one frame as oppose to two.
• Consideration: How long to wait for a new packet from the network layer for piggybacking?

• Simplex methods can fail under certain conditions when time-outs occur too early (try and construct a situation where the Simplex algorithm with Noisy Channel above doesn’t work – see Assignment 2). Sliding window protocols work under any conditions of damaged frames, lost frames and premature timeouts.
• The basis behind all sliding windows protocols:
• Each frame has a sequence number.
• At any time, sender keeps a range of sequence numbers (the sending window) it is permitted to send
• If a new packet comes from the network layer, it is given the next available number in the window and sent off.
• If an acknowledgment is received for a sequence number AT THE BEGINNING of the window, the window is moved up by 1.

• If all the sequence numbers in the window is being used, then no the algorithm cannot receive any new packets from the network layer.
• The sending window basically contains

1. the sequence numbers sent but not acknowledged
2. the sequence numbers remaining that can still be used to send new frames

• At any time, receiver keeps a range of sequence numbers (the receiving window) it is permitted to receive
• Similar to a sender’s the sending window
• The receiving window basically contains sequence numbers for the frames it hasn’t already received, and is prepared to store when received.
• If the sequence number received is AT THE BEGINNING of the window, it can send the packet straight up to the network layer without storing, because the frame is precisely the next one it is expecting. If not, it has to store it, since it is an out-of-sequence frame.
• Under what conditions will a receiver receive a sequence number pass the end of its window – see Assignment 2).
• The window is wrapped at a certain window size – so the sequence numbers go back to 0 once it reaches a certain maximum. This window size can be different for the sender and the receiver.

One-Bit Sliding Window Protocol

• The sending and receiving windows are size 1 – so the valid sequence numbers can only be either 0 or 1. The "one-bit" refers to the sequence numbers having one bit, so two possible values 0 or 1.
• All frames will have a number seq for the sequence number of the data frame. It will also have a number ack for the piggybacked acknowledgment frame. Some frames which only contain data will have a meaningless ack number. Some frames which are only acknowledgments will have a meaningless seq number.
• Algorithm:

A Peculiar Situation with One-Bit Sliding Window Protocol

• If both sides happen to send an initial frame before receiving anything, the piggybacked ack numbers can get out of synch. See Figure 3.14 in the textbook.

• Many duplicate data frames can be generated.

• This situation arises because the protocol uses piggybacking to send an acknowledgment USING THE SAME FRAME which contains data

• This situation doesn’t occur if one side receives a frame first before sending out its own – in that situation, the synchronization of using a data frame with a piggybacked acknowledgment works perfectly.

Pipelining

• One-bit Sliding Window: very bad channel utilization since a sender has to wait for a frame to be acknowledged before sending another – most of the time, the channel is idle.

• Solution: have sending window size larger than 1.

• So sender keeps sending out frames even if the initial ones aren’t acknowledged.

• Calculate the maximum window size based on round trip time of a frame (the time taken for a frame to get from sender to receiver + time for the acknowledgment frame to get back to sender) – so when the windows gets full, it’s just about time for the first acknowledgment to get back to the sender.

• This type of sliding window protocols is called pipelining – at any time, the sender has a pipeline of frames already sent out, which it is waiting for acknowledgments for.

Sliding Window with Go Back n

• What happens when a frame has errors or is lost?

• Have the receiver discard all frames after an error frame, and discard which are not in sequence – ie. the receiving window is size 1.

• The sender will time out and retransmit
• This idea is good if there are few errors, and round-trip times for frames are low – because all frames after an error frame will have to be retransmitted. Having small round-trip times means that the sender will not have sent out to many frames in a sequence before timing out on a particular frame and realising it has to retransmit all the frames following the one which timed out.

Sliding Window with Selective Repeat

• Also uses pipelining
• Difference with Go Back n:
• Receiver has a receiving window larger than 1.
• Buffers as many frames which are not the next in sequence as possible - when the frame that is in sequence does arrive without error, it can pass that on with the rest it has already buffered up.

Figure 3.15b

• The sender does not need retransmit as many frames in cases of errors.
• Useful when there are many errors, and round-trip times for frames are high – a long time before sender times out and realises a frame sent is not received properly.
• The available sequence numbers for the receiver MUST be at least twice as many as its window size – this is to prevent the situation such as eg: The receiver has window size 4, and sequence number 0-5. The receiver receives a batch of frame numbered 0,1,2,3. It sends off the acknowledgments for 0,1,2,3 and moves the window forward to 4,5, 0, 1 (it wraps around 5). Now all the acknowledgments happen to get lost, and the sender retransmit 0,1,2,3. When the receiver get 0 and 1, since it is in its valid receiving window (4,5,0,1), it will think it is a proper NEW frame, instead of an old one If I have sequence numbers 0-8, this will not happen.
• The sender and receiver need as many buffers as their window sizes. The sender also needs as many timers as it has buffers.
• Choice between Selective Repeat and Go Back n have to consider:
• Selective Repeat uses a lot more buffer space to store the frames, but generates a lot less traffic
• Go Back n is the opposite

[Back to Lecture Notes page]