EventHelix.com: CASE Tools; Real-time and Embedded System Design; Object Oriented Design
  Home  |  EventStudio System Designer 4.0  |  VisualEther Protocol Analyzer 1.0  |  Real-time Mantra  |  Contact Us

Home > Real-time Mantra > Design Patterns > Transmit Protocol Handler Pattern
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 
00008 
00008 
00009 #ifndef TRANSMIT_PROTOCOL_HANDLER_H
00010 #define TRANSMIT_PROTOCOL_HANDLER_H
00011 
00012 #include "Retransmission_Buffer.h"
00013 #include "Packet_Queue.h"
00014 
00023 
00024 class Transmit_Protocol_Handler
00025 {
00026     enum {L2_HEADER_LENGTH=8};
00027 
00029     int m_next_Transmit_Sequence_Number;
00030 
00033     int m_next_Receive_Sequence_Number;
00034 
00036     Retransmission_Buffer m_retransmission_Buffer;
00037 
00039     Packet_Queue<Datagram> m_transmit_Queue;
00040 
00042     Protocol_Layer *m_p_Layer;
00043 
00055 
00056     void Transmit_Packet(Datagram *p_Packet)
00057     {
00058         // Add header and sequence numbers
00059         p_Packet->Add_Header(L2_HEADER_LENGTH);
00060 
00061         p_Packet->Set_Receive_Sequence_Number(m_next_Receive_Sequence_Number);
00062 
00063         // Fill the transmit sequence number and inform
00064         // retransmission queue if the packet is not
00065         // an acknowledgement packet
00066         if (p_Packet->GetType() != Datagram::ACKNOWLEDGEMENT)
00067         {
00068             p_Packet->Set_Transmit_Sequence_Number(m_next_Transmit_Sequence_Number);
00069             Modulo_Increment(m_next_Transmit_Sequence_Number);
00070             // Inform retransmission queue about the packet
00071             m_retransmission_Buffer.Add_Packet(p_Packet);
00072         }
00073 
00074         // Pass on the message for transmission to the lower layer. A pointer to the lower
00075         // layer is obtained from the parent layer.
00076         Protocol_Layer *p_Lower_Layer = m_p_Layer->Get_Lower_Layer();
00077         if (p_Lower_Layer)
00078         {
00079             p_Lower_Layer->Transmit(p_Packet);
00080         }
00081     }
00082 
00083 public:   
00084 
00093 
00094     Transmit_Protocol_Handler(Protocol_Layer *p_Layer) :
00095       m_p_Layer(p_Layer), m_retransmission_Buffer(p_Layer)
00096       {
00097       }
00098 
00106 
00107       void Handle_Transmit_Request(Datagram *p_Packet)
00108       {
00109           // Check for space in window
00110           if (m_retransmission_Buffer.Get_Window_Room() == 0)
00111           {
00112               // No space, window is full. The message waits
00113               // in the queue
00114               m_transmit_Queue.Add(p_Packet);
00115           }
00116           else
00117           {
00118               // If the window is open, transmit packet immediately
00119               Transmit_Packet(p_Packet);
00120           } 
00121       }
00122 
00133 
00134       void Handle_Send_Ack_Request(int new_Receive_Sequence_Number)
00135       {
00136           // Copy the new receive sequence number
00137           // to acknowledge a packet
00138           m_next_Receive_Sequence_Number = new_Receive_Sequence_Number;
00139 
00140           // If there are no more pending messages,
00141           // send an explicit acknowledgement message. If messages
00142           // are pending, ack can be piggy backed.
00143           if (m_transmit_Queue.Get_Length() == 0)
00144           {
00145               // No messages are pending transmission.
00146               // Send explicit ack
00147               Transmit_Packet(new Datagram(Datagram::ACKNOWLEDGEMENT));
00148           }
00149       }
00150 
00163 
00164       void Handle_Received_Ack_Notification(int acknowledged_Sequence_Number)
00165       {
00166           Datagram *p_Packet;
00167 
00168           // Delegate ack processing to Retransmission Buffer
00169           m_retransmission_Buffer.Handle_Received_Ack_Notification(acknowledged_Sequence_Number);
00170 
00171           // Check if the transmit window has opened up. If there is is room in
00172           // the window, transmit packets waiting in the transmit queue
00173           int windowRoom = m_retransmission_Buffer.Get_Window_Room();
00174           for (int i=0; i < windowRoom && m_transmit_Queue.Get_Length(); i++)
00175           {
00176               p_Packet = m_transmit_Queue.Remove();
00177               Transmit_Packet(p_Packet);
00178           }
00179       }
00180 
00181 };
00182 #endif

 

Retransmission Buffer 
00008 
00009 #ifndef RETRANSMISSION_BUFFER_H
00010 #define RETRANSMISSION_BUFFER_H
00011 
00012 #include "Datagram.h"
00013 #include "Protocol_Layer.h"
00014 
00015 int Modulo_Increment(int& i);
00016 int Modulo_Difference(int seq_1, int seq_2);
00017 int Modulo_Add(int seq_1, int seq_2);
00018 
00029 
00030 class Retransmission_Buffer
00031 {
00032     enum { WINDOW_SIZE = 512 };
00033 
00034     Datagram *m_p_Pending_Packets[WINDOW_SIZE];
00035     int m_last_Transmitted_Sequence_Number;
00036     int m_last_Acknowledged_Sequence_Number;
00037     Protocol_Layer *m_p_Layer;
00038 
00039     void Restart_Await_Ack_Timer();
00040     void Stop_Await_Ack_Timer();
00041 
00042 public:
00043 
00051 
00052     Retransmission_Buffer(Protocol_Layer *p_Layer) : m_p_Layer(p_Layer)
00053     {
00054     }
00055 
00066 
00067     void Add_Packet(const Datagram *p_Packet)
00068     {
00069     
00070        m_last_Transmitted_Sequence_Number = p_Packet->Get_Transmit_Sequence_Number();
00071        
00072        // Make a copy of the packet for the retransmission buffer
00073        m_p_Pending_Packets[m_last_Transmitted_Sequence_Number] = new Datagram(p_Packet);
00074 
00075        // Restart the ack timer. Timer is started if its not running
00076        Restart_Await_Ack_Timer();       
00077     }
00078     
00090 
00091     void Handle_Received_Ack_Notification(int new_Acknowledged_Sequence_Number)
00092     {
00093         // Delete the buffers allocted to retransmission buffers 
00094         // for all allocated packets.
00095         for (int i=m_last_Acknowledged_Sequence_Number; i != new_Acknowledged_Sequence_Number; 
00096                                                      Modulo_Increment(i))
00097         {
00098            delete m_p_Pending_Packets[i];
00099            m_p_Pending_Packets[i] = NULL; 
00100         }
00101         
00102         // Save the new sequence number as the last acknowledged seq num
00103         m_last_Acknowledged_Sequence_Number = new_Acknowledged_Sequence_Number;
00104         
00105         // If all packets have been acknowledged, stop timer
00106         if (m_last_Transmitted_Sequence_Number == m_last_Acknowledged_Sequence_Number)
00107         {
00108            Stop_Await_Ack_Timer();
00109         } 
00110     }
00111     
00119 
00120     int Get_Window_Room() const
00121     {
00122        // Return the room in window by determining the current count of messages
00123        // awaiting acknowledgement
00124        return (WINDOW_SIZE - 
00125            Modulo_Difference(m_last_Transmitted_Sequence_Number, m_last_Acknowledged_Sequence_Number));
00126     }
00127 
00137     void Handle_Await_Ack_Timeout()
00138     {       
00139         Datagram *p_Packet;
00140 
00141         // Initiate retransmission of all unacknowledged packets by 
00142         // looping from the last unacknowledged sequence number to 
00143         // the sequence number of the last transmitted message
00144         for (int i=Modulo_Add(m_last_Acknowledged_Sequence_Number, 1); 
00145              i != m_last_Transmitted_Sequence_Number; Modulo_Increment(i))
00146         { 
00147 
00148            // Get the packet corresponding to the sequence number i
00149            p_Packet = m_p_Pending_Packets[i];
00150 
00151            // Pass on the message for transmission on the serial port
00152            (m_p_Layer->Get_Lower_Layer())->Transmit(p_Packet);                
00153         }
00154         
00155         // Now restart the timer
00156         Restart_Await_Ack_Timer();
00157     }
00158 };
00159 #endif

Known Uses

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

Related Patterns

Explore More...

 

  Home  |  EventStudio System Designer 4.0  |  VisualEther Protocol Analyzer 1.0  |  Real-time Mantra  |  Contact Us
Copyright © 2000-2008 EventHelix.com Inc. All Rights Reserved.