Share

Transmit Protocol Handler Pattern

Intent

Provide a common framework for transmit direction sliding window protocol implementation.

Also Known As

  • Send Protocol Design Pattern
  • Sender Pattern
  • Sliding Window Transmitter Pattern

Motivation

Different sliding window protocols have a lot of similarity. This similarity can be captured in a common design pattern for their implementation. Here we will focus on the transmit side of the protocol. 

Applicability

Transmit Protocol Handler Pattern can be used to implement protocols at any layer.

Structure

This pattern provides a framework for implementing a sliding window protocol. The Transmit Protocol Handler receives a packet from the higher layer and transmits it to the lower layer after assigning a sequence number. The packet is also stored in an internal retransmission buffer. The packet is removed from the retransmission queue if the remote end acknowledges the packet. The Transmit Protocol Handler retransmits the packet if it times out for an acknowledgement.

Participants

The key actors of this design pattern:

  • Transmit_Protocol_Handler: Class that manages the transmit end of the protocol. This class interfaces with the receive end and the retransmission queue.
  • Transmit_Queue: Enqueues messages that wait for transmission when the window is full.
  • Retransmission_Buffer: Manages buffers until an acknowledgement is received from the other end. The messages are retransmitted If no ack is received, .

Collaboration

The following diagram shows the relationship and collaboration between various classes involved in the Transmit Protocol Handler Pattern. 

Transmit Protocol Handler

Consequences

Using this pattern simplifies the implementation of transmit end point of a sliding window protocol. The design is flexible enough to adjust to any protocol.

Implementation

The following scenarios are supported by the Transmit Protocol Handler:

Packet added to queue when window has room

  1. Handle Transmit Request method of the Transmit Protocol Handler is invoked.
  2. Since the transmit window is not full, packet transmission is initiated.
  3. Protocol processing is performed on the packet. This involves the following steps:
    1. Protocol header is added to the packet
    2. Transmit sequence number is assigned to the packet and then incremented for the next time
    3. Receive sequence number is initialized to the last transmit sequence number of the last received packet (from the other end)
  4. Packet is added to the Retransmission Buffer at the transmit sequence number in the packet.
  5. Retransmission Buffer restarts AwaitAck timer.
  6. Packet is passed to the serial port transmit queue 

Packet added when window is full

  1. Handle Transmit Request method of the Transmit Protocol Handler is invoked.
  2. Since the transmit window is full, no further action is needed, unless the transmit window opens.

"Send Ack" request from Receive Protocol Handler

  1. Receive Protocol Handler detects a change in the received transmit sequence number, it requests Transmit Protocol Handler to acknowledge the received packets. (The new received transmit sequence number is passed)
  2. Transmit Protocol Handler takes the following action:
    • If the transmission queue is empty or the transmit window is full, explicit acknowledgement is scheduled.
    • If transmission is pending, the acknowledgement will be piggybacked in the data packet.

"Received Ack" Notification from Receive Protocol Handler

  1. Whenever the Receive Protocol Handler detects a change in the received receive sequence number, it informs Transmit Protocol Handler so that it can process the sequence number change as acknowledgements from the other end.
  2. Transmit Protocol Handler takes the following action:
    1. Retransmission Buffer is informed about the acknowledged sequence numbers.
    2. Retransmission Buffer loops through from the last acknowledged sequence number to the new sequence number and frees up the buffers as they have been acknowledged.
    3. If no more packets are present in the retransmit buffer, AwaitAck timer is stopped.
    4. If the window was full and has now been opened up, check the Transmit Queue for any messages that might be waiting for the window to open up.  

Timeout for acknowledgement

  1. Await Ack timer times out.
  2. Retransmission Buffer loops through all the packets that are still pending acknowledgement and initiates retransmission.

Sample Code and Usage

Here we present the code for a typical implementation of this pattern. Code is provided for the Transmit Protocol Handler and the Retransmission Buffer classes. Transmit Queue can be implemented using the message queue pattern.

Transmit Protocol Handler

#ifndef TRANSMIT_PROTOCOL_HANDLER_H
#define TRANSMIT_PROTOCOL_HANDLER_H

#include "Retransmission_Buffer.h"
#include "Packet_Queue.h"


class Transmit_Protocol_Handler
{
    enum {L2_HEADER_LENGTH=8};

    int m_next_Transmit_Sequence_Number;

    int m_next_Receive_Sequence_Number;

    Retransmission_Buffer m_retransmission_Buffer;

    Packet_Queue<Datagram> m_transmit_Queue;

    Protocol_Layer *m_p_Layer;


    void Transmit_Packet(Datagram *p_Packet)
    {
        // Add header and sequence numbers
        p_Packet->Add_Header(L2_HEADER_LENGTH);

        p_Packet->Set_Receive_Sequence_Number(m_next_Receive_Sequence_Number);

        // Fill the transmit sequence number and inform
        // retransmission queue if the packet is not
        // an acknowledgement packet
        if (p_Packet->GetType() != Datagram::ACKNOWLEDGEMENT)
        {
            p_Packet->Set_Transmit_Sequence_Number(m_next_Transmit_Sequence_Number);
            Modulo_Increment(m_next_Transmit_Sequence_Number);
            // Inform retransmission queue about the packet
            m_retransmission_Buffer.Add_Packet(p_Packet);
        }

        // Pass on the message for transmission to the lower layer. A pointer to the lower
        // layer is obtained from the parent layer.
        Protocol_Layer *p_Lower_Layer = m_p_Layer->Get_Lower_Layer();
        if (p_Lower_Layer)
        {
            p_Lower_Layer->Transmit(p_Packet);
        }
    }

public:   


    Transmit_Protocol_Handler(Protocol_Layer *p_Layer) :
      m_p_Layer(p_Layer), m_retransmission_Buffer(p_Layer)
      {
      }


      void Handle_Transmit_Request(Datagram *p_Packet)
      {
          // Check for space in window
          if (m_retransmission_Buffer.Get_Window_Room() == 0)
          {
              // No space, window is full. The message waits
              // in the queue
              m_transmit_Queue.Add(p_Packet);
          }
          else
          {
              // If the window is open, transmit packet immediately
              Transmit_Packet(p_Packet);
          } 
      }


      void Handle_Send_Ack_Request(int new_Receive_Sequence_Number)
      {
          // Copy the new receive sequence number
          // to acknowledge a packet
          m_next_Receive_Sequence_Number = new_Receive_Sequence_Number;

          // If there are no more pending messages,
          // send an explicit acknowledgement message. If messages
          // are pending, ack can be piggy backed.
          if (m_transmit_Queue.Get_Length() == 0)
          {
              // No messages are pending transmission.
              // Send explicit ack
              Transmit_Packet(new Datagram(Datagram::ACKNOWLEDGEMENT));
          }
      }


      void Handle_Received_Ack_Notification(int acknowledged_Sequence_Number)
      {
          Datagram *p_Packet;

          // Delegate ack processing to Retransmission Buffer
          m_retransmission_Buffer.Handle_Received_Ack_Notification(acknowledged_Sequence_Number);

          // Check if the transmit window has opened up. If there is is room in
          // the window, transmit packets waiting in the transmit queue
          int windowRoom = m_retransmission_Buffer.Get_Window_Room();
          for (int i=0; i < windowRoom && m_transmit_Queue.Get_Length(); i++)
          {
              p_Packet = m_transmit_Queue.Remove();
              Transmit_Packet(p_Packet);
          }
      }

};
#endif

Retransmission Buffer

#ifndef RETRANSMISSION_BUFFER_H
#define RETRANSMISSION_BUFFER_H

#include "Datagram.h"
#include "Protocol_Layer.h"

int Modulo_Increment(int& i);
int Modulo_Difference(int seq_1, int seq_2);
int Modulo_Add(int seq_1, int seq_2);


class Retransmission_Buffer
{
    enum { WINDOW_SIZE = 512 };

    Datagram *m_p_Pending_Packets[WINDOW_SIZE];
    int m_last_Transmitted_Sequence_Number;
    int m_last_Acknowledged_Sequence_Number;
    Protocol_Layer *m_p_Layer;

    void Restart_Await_Ack_Timer();
    void Stop_Await_Ack_Timer();

public:


    Retransmission_Buffer(Protocol_Layer *p_Layer) : m_p_Layer(p_Layer)
    {
    }


    void Add_Packet(const Datagram *p_Packet)
    {
    
       m_last_Transmitted_Sequence_Number = p_Packet->Get_Transmit_Sequence_Number();
       
       // Make a copy of the packet for the retransmission buffer
       m_p_Pending_Packets[m_last_Transmitted_Sequence_Number] = new Datagram(p_Packet);

       // Restart the ack timer. Timer is started if its not running
       Restart_Await_Ack_Timer();       
    }
    

    void Handle_Received_Ack_Notification(int new_Acknowledged_Sequence_Number)
    {
        // Delete the buffers allocted to retransmission buffers 
        // for all allocated packets.
        for (int i=m_last_Acknowledged_Sequence_Number; i != new_Acknowledged_Sequence_Number; 
                                                     Modulo_Increment(i))
        {
           delete m_p_Pending_Packets[i];
           m_p_Pending_Packets[i] = NULL; 
        }
        
        // Save the new sequence number as the last acknowledged seq num
        m_last_Acknowledged_Sequence_Number = new_Acknowledged_Sequence_Number;
        
        // If all packets have been acknowledged, stop timer
        if (m_last_Transmitted_Sequence_Number == m_last_Acknowledged_Sequence_Number)
        {
           Stop_Await_Ack_Timer();
        } 
    }
    

    int Get_Window_Room() const
    {
       // Return the room in window by determining the current count of messages
       // awaiting acknowledgement
       return (WINDOW_SIZE - 
           Modulo_Difference(m_last_Transmitted_Sequence_Number, m_last_Acknowledged_Sequence_Number));
    }

    void Handle_Await_Ack_Timeout()
    {       
        Datagram *p_Packet;

        // Initiate retransmission of all unacknowledged packets by 
        // looping from the last unacknowledged sequence number to 
        // the sequence number of the last transmitted message
        for (int i=Modulo_Add(m_last_Acknowledged_Sequence_Number, 1); 
             i != m_last_Transmitted_Sequence_Number; Modulo_Increment(i))
        { 

           // Get the packet corresponding to the sequence number i
           p_Packet = m_p_Pending_Packets[i];

           // Pass on the message for transmission on the serial port
           (m_p_Layer->Get_Lower_Layer())->Transmit(p_Packet);                
        }
        
        // Now restart the timer
        Restart_Await_Ack_Timer();
    }
};
#endif

Known Uses

  • Datalink layer sliding window protocol implementation
  • Higher layer sliding window protocol implementation

Related Patterns