- Back -

Physical Implementation of New Protocol

This chapter will deal with the physical implementation of the protocol. The stages of implementation will be illustrated in each section below, a different section for each extra functionality or requirement added.
Figure 11 Illustrating where the new protocol will sit in the DoD four layer model

The first question is at which network layer will the protocol sit on? Figure 11 shows an updated diagram of the DoD four layer network model that includes the new protocol. The protocol will be on the same level as TCP and UDP as it too is a transport protocol.

Figure 12 Object Hierarchy of the Network Simulator

Figure 12 shows the object Hierarchy in NS. As the new agent that is being added is in the transport layer it is also on the same level (Transport Layer) as UDP and TCP in the Object hierarchy.
4.1.1 Naming the new protocol

The protocol was called “RelUDP”, as it is similar to UDP in the way it uses small packets/Datagrams, but has added functionality such as reliability. Thus RelUDP basically stands for Reliable User Datagram Protocol.

The requirements for the new RelUDP protocol were discussed in the last chapter. Here is a list reviewing these requirements
 Reliability
 Retransmission
 Use Datagram to transport data
 HOL blocking absent
 Minimal Congestion Control

These requirements were not implemented all at once. The process of adding functionality to the protocol was a long and tedious one. Each function or requirement was first designed, then implemented and finally tested and possibly redesigned if necessary. Therefore the whole Development can be seen as a series of stages.

The first goal or stage of implementation was to get a basic Datagram protocol coded and working, similar to UDP. The protocol was implemented as a two-way agent. A two-way agent is symmetric in the sense that it represents both a sender and receiver.
The first thing done was to create a packet header. This is basically a structure in C++ that represents the packet object that the protocol uses.

The fundamental unit of exchange between protocols in simulations is an object called a Packet. This packet object that is written in C++ provides enough information to link a packet on to a queue, figure out where the packet is being sent, where it is coming from etc. When designing a new protocol it is good practice to define a new packet header or maybe extend existing headers with additional fields to suit the protocols needs.
New packet headers are created by
 Defining a new C++ structure with the needed fields.
 Defining a static class to provide OTcl linkage.
 Modifying the simulator initialisation code to assign a byte offset that points to where the new header is to be located in the packet relative to others.

The next task is to design a new packet header that will be used with the new protocol “RelUDP”.

Figure 13 shows the Packet header designed for the new protocol.
The RelUDP header will require a source identifier field and a sequence number field. This structure shown, hdr_RelUDP defines the basic layout of the RelUDP packet header. It defines the fields are needed and how big they are. The compiler uses this structure to compute byte offsets of the fields. One important thing to note is that there is no objects of this structure type are ever directly allocated. The member functions shown provide a layer of abstraction that is used by other network objects wishing to read or modify the header fields of packets. Another important thing to note regarding the Packet object is that when a packet is created it has every possible packet type (including the packet type’s header fields) in the object. Thus the static class variable offset_ is used to locate the byte offset at which the new header is located. Two methods are provided to utilise this variable to access this header in any packet. These methods are offset() and access().
offset() is used by the packet header management class and should seldom be used.
access() is used to access a particular header in a packet; for example hdr_RelUDP::access(p) accesses the packet header of the RelUDP header.

Now that the new header is defined the next step is to create the basic functionality that the protocol needs which will be implemented in the RelUDP protocol file (RelUDP.cc).
The fundamental functionality of a Basic Datagram Protocol would include the ability to send a packet of a certain set size, segmenting if necessary and also to receive the packet on the other end. This basic functionality is implemented in the functions sendmsg() and recv() respectively. Before the implementation of these two methods is described, the TclClass Hierarchy and the oTCL linkage must be explained.

The base class called TclClass is a pure virtual class. Any classes derived from this base class provide the following two functions:
1. They construct the interpreted class hierarchy to mirror the compiled class hierarchy.
2. They provide methods to instantiate new TclObjects.
The mirrored Object hierarchy has already been discussed in earlier chapters.
Each such derived class is associated with a particular compiled class in the compiled class hierarchy, and can instantiate new objects in the associated class. For the new protocol, a static class derived from the base TclClass is needed to create this mirrored hierarchy.

Figure 14 Creation of the RelUDPAgentClass

Figure 14 illustrates the creation of this static class “RelUDPAgentClass”, and is associated with the class RelUDPAgent. This class will instantiate new objects in the class RelUDPAgent.

Figure 15 shows the compiled class hierarchy for RelUDPAgent is that it derives from Agent that in turn roughly derives from TclObject. Concentrating on Figure 14 again, this shows the static class “RelUDPAgentClass”. This class defines the constructor,

Figure 15 Tcl Class Hierarchy

and one additional method, to create instances of the associated TclObject.

Figure 16 The Tcl Object create() returning Tcl objects in the class RelUDPAgent

When the Simulator is first started, it will execute the RelUDPAgentClass constructor for the static variable class_RelUDP_agent, which in turn sets up the appropriate methods and the interpreted class hierarchy. This class is associated with the class RelUDPAgent, thus it creates new objects in this associated class. Another thing to note is that the RelUDPAgentClass::create() method returns TclObjects in the class RelUDPAgent. Therefore when a user is writing a Tcl script to run a simulation includes the new protocol ( new Agent/RelUDP), the method RelUDPAgentClass::create() is invoked.

As already mentioned in a previous chapter, it is possible to link variables between the two languages used (C++ and oTcl). This allows C++ variables to be accessible through Tcl during the simulation, which allows greater flexibility and control of the simulation. This is accomplished in the class's constructor:

Figure 17 Variable Linkage

As Figure 17 depicts the linking of C++ variable size_ and OTcl instance variables packetSize_, this grants the user the ability to adjust the packet size during simulation.
4.2.1.4 sendmsg() method

This method is the most complicated method of the simple Datagram protocol that is being implemented. The main aim of this method is to send a Datagram to the destination. sendmsg() takes in three parameters.
 int nbytes specifies the number of bytes that is being sent to the destination
 AppData* data allows the user to attach user application data in the packet.
 const char* flags allows the user to include optional string flags that could be used by an application

Figure 18 RelUDP sendmsg() method

Figure 18 shows the implementation of this method. Firstly the method performs some simple error checking at the start of the method. The size_ variable is the current size of the packet, i.e. the number of bytes that the packet can hold. This is checked to be greater than zero, or basically if the variable has been set. If this variable has been set, it calculates how many segments if any that the data must be sent in. It then checks if the user has included data that it will fit in the packet. Segmentation is dealt with here if necessary. If the data must be segmented, the while loop sends n packets, n being the number of segments needed. The actual process of sending a packet is quite simple. First a packet p, which has already been declared at the start of the method, is allocated space and created. Then the packet type is selected. This is where we are using the packet header that was created earlier. The size of the packet is set, the sequence number is incremented and finally the packet is sent. It is the target_->recv(p); which actually simulates the sending of a packet. What it is actually doing is calling the recv method of target_. The target_ variable is a pointer to the destination protocol/node. After any segmentation is needed, the remainder of the data (if any) is sent exactly the same way described above.
4.2.1.5 recv() method

As already mentioned the most complicated method in the Basic Datagram protocol that is being implemented was the sendmsg() method. The recv() method is quite simple. Firstly it takes in two parameters;
 Packet* pkt, the packet that is being received
 Handler* the handler which handles the event

Figure 19 RelUDP recv() method

Figure 19 shows the implementation of the recv() method. Firstly the method checks whether the user added user application data in the packet, and if so it passes it to the application to process the data. If on the other hand the user did not add any application data to the packet, the packet is freed from memory and dropped.

The majority of the basic Datagram protocol was explained above. The functionality of the protocol was very basic. It simply sends data in Datagram packet and segments the data if necessary. The next goal is to add reliability to the protocol implementation.

The basic Datagram Protocol described in the last section is a simple but effective one. As it is it is lacking functionality that is needed in the new Protocol. One of the basic functions or services that must be added is reliability. The importance of having a reliable Protocol is described in the last chapter.
Providing data reliability consists of two basic components.
 Loss detection
 Loss Recovery
The oncoming sections deal with these two basic components in more detail.
4.2.2.1 Loss Detection
In the basic Datagram Protocol there is no way of knowing whether a Datagram packet actually got delivered to the destination node. The Protocol basically sends the Datagram Packets and hopes for the best. The first aim is to detect a Packet loss.
In order to do this a new Packet must be created. This Packet is called an Acknowledgement packet. Is basic purpose is to inform the sender that a certain Packet has been delivered successfully. The size of an Acknowledgement is considerably smaller than a regular Datagram Packet, thus Acknowledgements have little effect on Congestion. The first goal is to design a new Packet Header similar to the Datagram Packet header that was designed earlier.

Figure 20 RelUDP Acknowledgement Packet Structure

Figure 20 shows the Acknowledgement Packet header designed for the new protocol. This header will be very similar to the RelUDP header that was designed earlier. It also will require a source identifier field and a sequence number field. This sequence number field will be used to match a Packet sent to an Acknowledgement Packet received.
As the Acknowledgement Packet Header is now designed the next goal is to modify the revc() method in the Basic Datagram Protocol so that when it receives a packet, it sends an Acknowledgement Packet back to the original sender, thus acknowledging the Packet. The modifications to the recv() method must enable the protocol to receive both regular RelUDP Packets and RelUDPAck Packets and to differentiate between them.

Figure 21 Revised RelUDP recv() method

Figure 21 shows the modifications needed to the recv() method so that it can handle basic RelUDP Packets. Basically what is needed in this recv() method is the ability to reply by sending an Acknowledgement Packet, when a RelUDP Datagram Packet is received. The first thing that is done in this method is to check the type of the incoming Packet. If the packet type is RelUDP, then the method must send an Acknowledgement back to the node that sent the RelUDP Packet. This is done as follows. First a new Packet is created (np) and its size is set to 12 bytes. Note that this is considerably smaller than a regular Datagram Packet size. The IP header fields are then accessed to figure out where the Packet has come from. Then the new Packets IP header destination address is set to the incoming packets source address, thus switching the direction of the Packet. The packet type is set to RelUDPAck as it is an Acknowledgement and finally the sequence number of the incoming packet is copied to the sequence number of the new Acknowledgement Packet. The acknowledgement is sent.

At the moment the protocol will send a Datagram, and on receiving a Datagram will send an acknowledgement back to the sender. The issue of Packet loss detection is quite not fully implemented. The next step is to implement a mechanism that records the packets sent in a buffer. Thus this buffer could be used with the incoming Acknowledgements to figure out which Packets indeed were lost in the network and require retransmission.

Figure 22 RelUDP recordPacket() method

Figure 22 shows the implementation of the recordPacket() method. The basic aim of this method is to record the Packet pkt in the buffer. The buffer is actually a packet array called packetsSent. One thing that must be explained is the packetIndex_ variable. This variable keeps count of the amount of Packets in the buffer. It is a public class variable, thus each instance of the protocol that is created contains this variable. The copy() method is used to copy the contents of the packet into a Packet array ( buffer). This method is called when a RelUDP packet is being sent. Thus all Datagram packets sent are recorded in the buffer. It is with the help of this method that the protocol can detect packet loss.

As all packets being sent are recorded in the buffer, one possibility of detecting Packet loss would be to remove the corresponding (same sequence number) Packet when an Acknowledgement arrives. If the protocol was implemented in this manner, it is deducible the Packets left in the buffer are the Packets that were lost or the packets who’s Acknowledgements were lost.

In order to implement loss detection a number of methods have to be added to the protocol. The basic theory is to remove a Packet from the buffer if the Packet has been acknowledged successfully. This theory seems viable at first but on closer inspection it lacks efficiency. Removing a Packet from the buffer would require copying every other Packet in the old array into a new array, which would be computationally expensive. A slightly different approach was taken which produces the same outcome without the efficiency problem. Instead of removing the acknowledged packet altogether, the packet is marked for deletion. Then when the buffer fills up, a method is called which basically removes the Packets that are market for removal, and copies the remainder into a new buffer. Two implementation issues must be discussed here.

Firstly the Packets are marked for deletion by setting the sequence number of the Packet to –2. Thus any Packets in the buffer that do not have a sequence number of –2 must be retransmitted.

Figure 23 Revised RelUDP recv() method
Figure 23 shows the rest of the recv method, which deals with receiving acknowledgements. The first loop simply searches through the buffer for a matching Packet with the same sequence number. Then if a Packet is found it is marked for deletion by simply setting its sequence number to –2, as explained previously.

Secondly the implementation of the method that removes the Acknowledged Packets must be explained.

Figure 24 RelUDP removeAckdPackets() method

Figure 24 shows the implementation of the removeAckdPackets() method. This method takes in a parameter newBufferSize, which is simply the size of the new buffer that is going to be produced by this method. This new buffer will contain all the packets in the previous buffer that weren’t marked for removal/deletion. The method first creates a temporary Packet array of newBufferSize size, then it simply searches through the original buffer for any Packets who’s sequence number is not –2, or in other words who have not been marked for removal. If it does find such Packets, it copies them into the temporary array. It then copies the Packets from the temporary array into the new buffer array, and deletes the temporary array. This method is quite efficient, as it gives the opportunity of resizing the buffer array only when necessary, thus keeping memory consumption at a minimum.

Therefore the protocol now is capable of detecting Packet loss. The next issue to deal with is Loss Recovery, which basically will implement functionality to recover form the lost Packet, or retransmit the Packet in other words.

As the protocol can now detect lost Packets a method is needed to retransmit these Packets.

Figure 25 RelUDP checkBufferLoop()

Figure 25 shows the implementation of the method checkBufferLoop() which is used to retransmit lost Packets. The method simply searches through the buffer for any packets that are not marked for removal, and resends the packet. When it resends the packet it sets the original packet in the buffer for removal, and records a new packet in the buffer. There are two important things to note about this implementation. The method does not search through the last four elements in the array, as they are most likely the packets that are currently being sent (an improved version will be discussed later). Secondly the main issue is from where to call this method. It should be called regularly to ensure that lost packets would be retransmitted quickly. The reliability of the protocol is effected depending on from where this method is called. If it is called form the
 sendmsg() method then there is a possibility that a Packet could get lost after this method was called for the last time in the simulation. For example is a Packet was sent, and the checkBufferLoop() method resends any Packets needed at that time but if the Packet gets lost after that it will never be resent. This would make the protocol unreliable.
 recv() method a similar problem would arise. If the last packet being sent got lost in the Network, the final recv() method would never be called because no Acknowledgement would have been sent. Thus this Packet would never be resent, which also transforms the protocol to an unreliable one.
Therefore it is clear that a new mechanism is needed so that this method can be called regularly to ensure reliability. Luckily the Network Simulator provides a TimeHandler class which solves this problem.

In the Network Simulator Timers may be implemented in C++ or OTcl. The new protocol will need a timer implemented in C++, which is based on an abstract base class (defined in timer-handler.h). The TimerHandler gives the ability to create, schedule, reschedule or cancel a timer. When a timer is scheduled (by using the sched(delay) method) to expire delay seconds in the future. When the timer expires an event is created, which can be handled. Then handling of this event can call the checkBufferLoop() method. This will ensure that the method is called regularly, thus making the protocol reliable.

Figure 26 Defination of the CheckBufferTimer() method

Figure 26 shows the definition of the timer used in the new protocol. The method void CheckBufferTimer::expire(Event*) will be called when the timer expires. The timer must be rescheduled at the end of the checkBufferLoop() method by the code timername.resched(next_time).
At this point the protocol can be stated to be reliable. The protocol sends Datagram packets, replies with Acknowledgement packets, records the packets it sends, and resends the packets that do not get acknowledged. There is still the issue of retransmission of delayed packets. This is discussed in the next section.

Enforcing a maximum Time Delay

The importance of Packets arriving below a certain delay is discussed in detail in the last chapter. The basic reason is that if the packets are arriving too late, the information might be out of date, and consequently disrupt the performance of multimedia applications. The new protocol is designed with aim of using it in multimedia applications and related areas, therefore it is important to enforce this in the new protocol. The next goal is to implement added functionality to the existing protocol that would retransmit packets if their RTT (Round Trip Time) is greater than a fixed variable or if they have been in the buffer longer than a fixed variable. To recap the Round Trip Time is the amount of time taken between the sending of a Packet and the receiving of an Acknowledgement for that Packet. A number of adjustments need to be made to the protocol to implement this.
Firstly the buffer must be extended.
Figure 27 RelUDP Protocol Buffer

As Figure 27 illustrates, the concept of the buffer must hold a packet array that holds the actual packets, and a corresponding integer array that holds the time that the corresponding Packet was sent at.
The next adjustment to the existing protocol is to the methods recordPacket() and removeAckdPackets(). The changes to these methods are as expected and can be seen in the final version of the protocol. The method which requires substantial change would be the checkBufferLoop()

Figure 28 Revised RelUDP checkBufferLoop() method

Figure 28 shows the changes made to the method checkBufferLoop. Note the timer code is also shown. This method now searches through the buffer for packets that have not been marked for removal and that have not been in the buffer greater than a variable (MAXDELAY) amount of time. If it finds any packets that satisfy these requirements, it resends those packets.

This is a problem that can occur in the Protocol design as it is currently designed. The basic problem is that at any time it is possible to have duplicate acknowledgement Packets (acknowledging the same Packet) in the Network.

Figure 29 Duplicate Acknowledgement problem

This happens as follows, (see Figure 29) first when a Packet (sequence number 1) is sent by the Protocol and is successfully delivered at its destination, an acknowledgement Packet (sequence number 1) is sent in response. If the network is congested and the acknowledgement has not returned in the MAXDELAY amount of time, the protocol resends Packet 1 as it believes the Packet was lost or delayed in the network. Shortly afterwards the delayed acknowledgement arrives, consequently the protocol believes this to be the acknowledgement of the second retransmitted Packet. Therefore the Protocol will mark a delayed Packet off the buffer that should have been retransmitted.

Figure 30 Revised RelUDP Packet Structure

To overcome this problem, a secondary sequence number is needed in both the RelUDP and the RelUDPAck Packet headers. This will make it possible for the Protocol to differentiate between different retransmissions of the same packet. Figure 30 shows the revised RelUDP/RelUDPAck Packet header.

Figure 31 Overcoming Duplicate Acknowledgements with revised RelUDP header.

Figure 31 shows how the new header field overcomes this problem. The protocol is able to differentiate between different retransmissions of the same packet.

Figure 32 Modifications made to RelUDP header

Figure 32 illustrates the modifications made to the header field of the RelUDP packet header. Note the same changes are needed in the RelUDPAck header. The secondary sequence number variable is called retryCount_. A member function is also implemented to access this variable.
Slight modifications must be made to the Protocol to implement this new secondary sequence number scheme. When a Packet is retransmitted, the new recorded Packet’s retryCount_ Header field is incremented. Also when an acknowledgement arrives it must satisfy all three conditions to remove the corresponding Packet form the buffer/to prove that the Packet has arrived on time.
1. The acknowledgements sequence number must be the same as the corresponding Packets sequence number in the buffer.
2. The acknowledgement’s retryCount_ value must be the same as the corresponding Packet’s retryCount_ value in the buffer.
3. The Packets RTT must be below the MAXDELAY variable time.

When implementing the extra functionality on to the Protocol, one final design issue remains. This issue arises with the option of Packet retransmission. Two different designs were created which retransmit Packets at different times and through different methods.
The first design will be discussed here, and the second design is the design chosen for the final end version of the Protocol. The fundamental difference between the two designs is basically when to retransmit lost or delayed packets.

Figure 33 Functionality of the RelUDP Protocol Version 1

The first version employs the functionality shown in figure 33. First when a packet is sent by the protocol that arrives successfully at the destination an acknowledgement is sent in return. The main difference is what the protocol does when an acknowledgement is received. It first checks through the buffer for a Packet matching the sequence number and the retryCount value. If it finds such a Packet, it checks the Packets Round Trip Time to be less than the MAXDELAY static variable.
 If it less than the MAXDELAY value is it sets that packet for removal in the buffer
 If it is not less than the MAXDELAY value it simply leaves it up to the checkBufferLoop() method to retransmit the packet. This method is called continuously by the timer ever 25miliseconds.
The checkBufferLoop() method checks through the buffer for Packets that have not been marked for removal and that have been in the buffer greater than MAXDELAY amount of time. Finding any Packets that satisfy these conditions, the method will send a copy of the Packet, record it in the buffer and finally set the original packet for removal.
The main reasons against this version were both logical and physical ones. Firstly the new Protocol should retransmit lost/delayed Packets as quickly as possible, to avoid the performance of the application using the protocol to be hindered. Therefore when the acknowledgement Packet is received, it should retransmit the Packet then rather than leaving it for the checkBufferLoop method to retransmit the Packet later. Another point is that this protocol will retransmit Packets in groups which is generally undesirable as it could possibly worsen congestion in the Network.
The physical issues concern the Network simulator itself. When testing this version of the protocol under highly congested networks, it was found that as the checkBufferLoop method is running at the same time as the protocol. This was seen to produce undesirable results or segmentation faults as the two processes were accessing the same information, for example Packets in the buffer.
The final version of the Protocol deals with these issues and is discussed later in this chapter.

The protocol provides reliability, but does not enforce in order delivery. By avoiding this functionality, HOL blocking is avoided.

As the new protocol is aimed for VoIP signalling or possibly multimedia applications congestion control would be counterproductive. Thus no congestion control was be implemented in the new protocol. Thus if the network does get highly congested, the protocol does not adjust in any way to deal with the congestion; it simply keeps sending Datagram at the same rate.

The protocol was designed from a series of stages, each stage adding new functionality bring the Protocol closer to the final result. As quite a lot of the details have already been discussed in previous stages, this section will give a brief overview of the workings of the Final version of the Protocol explaining any changes as they appear.

Figure 34 Functionality of the RelUDP Protocol Final Version

Figure 34 shows the functionality and the workings of the Protocol. There are two basic improvements that the Final version of the Protocol makes.

Figure 35 Additions to recv() method

The first is what the Protocol does when an acknowledgement is received. Unlike the previous version of the Protocol this version retransmits the Packet as soon as it figures out that it is delayed. Figure 35 illustrates this point. It shows a fragment of the code from the recv() method.
The second improvement is that the timer does not call checkBufferLoop every 25miliseconds. Instead it is called in the receive method, which eliminates the problem of segmentation faults. Every time the method is called it reschedules itself to be called 600 milliseconds later. This in fact only calls the method when the Protocol has finished sending Packets. Thus providing guaranteed reliability, even to the last packet sent.

Including a Random Element

One possible addition that could be added to the Protocol would be to change the static variable MAXDELAY to a random variable between 450 and 500 milliseconds. When a node (router) or link fails, quite a large amount of packets are lost or delayed. This in turn causes these packets to be resent at the same time, which congests the network even more so. Adding this random element will lessen the effect of this problem.

Including Fragmentation

The protocol as it is does not implement fragmentation. Fragmentation is simply a process to overcome the problem of heterogeneous Maximum Transmission Units. Nodes on the Network store the Packets/Datagrams to be sent in memory; when sending the Datagram it is put in an IP frame suitable for the network. Each hardware technology specifies the maximum amount of data that a frame can carry. For example some links on the Network will only be able to transfer a certain amount of data; this is called the Maximum Transmission Unit (MTU).

Figure 36 Fragmentation

The problem occurs when a Datagram that is larger than the MTU of the network is sent over the network; the solution is that the Datagram is divided into smaller “fragments” which are each sent separately. This is called Fragmentation. Figure 36 illustrates this.