- Back -

Logical Design of New Protocol

Network Simulator Modular Design

The design of the Network Simulator (NS-2) uses a paradigm called shared object design. This means that the system is programmed in two languages. In both languages there is a corresponding hierarchy of network objects, but the objects in one are accessible in the other. There are also objects accessible to only one part of the system. NS is written in Object Oriented Tcl and C++. This is mainly for an efficiency reason. NS separates the data path implementation from control path implementations. In order to reduce packet and event processing time, the event scheduler and the basic network component objects in the data path are written and compiled using C++.

Figure Corresponding Object Hierarchy between C++ and oTCL

These compiled objects are made available to the OTcl interpreter through an OTcl linkage. This OTcl linkage creates a matching OTcl object for each of the C++ objects and also makes the configurable control variables specified by the C++ object act as member functions and variables of the corresponding OTcl object. In this way, the controls of the C++ objects are given to OTcl. This makes it possible to change linked C++ variables from a TCL script. It is also possible to add member functions and variables to a C++ linked OTcl object. Of course some objects in C++ that do not need to be controlled in a simulation or internally used by another object do not need to be linked to OTcl. Figure 6 shows an object hierarchy example in C++ and OTcl. One thing to note is that for C++ objects that have an OTcl linkage forming a hierarchy, there is a matching OTcl object hierarchy very similar to that of C++.

Architecture Overview

Figure 7 shows the general architecture of NS. A general user (not an NS developer) can be thought of standing at the left bottom corner, designing and running simulations in Tcl using the simulator objects in the OTcl library. As you move from this corner to the right hand top corner more knowledge and understanding of NS as a whole is needed. The event schedulers and most of the network components are implemented in C++ and available to OTcl through an OTcl linkage that is implemented using tclcl. The whole diagram together makes NS, which is an Object Oriented extended Tcl interpreter with network simulator libraries.

The network can be freely designed in a scenario and it is written in OTcl. The scenario contains descriptions for some or all of the elements of simulation described below.

Elements of Simulation

In this section the elements of simulation in ns are described.
 Nodes in ns handle packet forwarding and can be both receivers and routers at the same time. There are both unicast and multicast nodes available in the simulator.
 Links basically interconnect two nodes.
 Packets work as events in the event driven simulation. Receiving or sending a packet is essentially an event. There are functions for creating, accessing and changing both the packets and the headers of the packets as will be discussed later.
 Queues can be connected to links. The type of dropping/forwarding procedure can be chosen from several different types.
 Error models are used to introduce packet losses in the simulation. Thus simulating link failures/congestion etc. This is useful as it creates a controllable aspect of introducing packet losses or congestion simulation.
 Agents represent the endpoints for network layer packets in the simulation. They are responsible for creation and destruction of these types of packets. There are several agents already implemented in NS, for example UDP, TCP etc. It is the goal of this project to add an agent to the NS hierarchy.
 Applications are above the agents. There are two types of applications; traffic generators and simulated applications. The traffic generators generate traffic in a predefined pattern. Simulated applications are for example FTP and telnet where the generated traffic is made as similar to the real applications traffic as possible.
3.2 Requirements

In this section the logical requirements of the new protocol that is being added will be discussed. The basic requirements are as follows.
 Reliability
 Retransmission
 Use Datagram to transport data
 HOL blocking absent
 Minimal Congestion Control

Reliability

When creating a protocol which will be aimed for VoIP signalling or possibly multimedia applications such as video conferencing one of the most basic functionality that’s expected is reliable transport. For example if two users were using a multimedia application on the network such as a voice call or a videoconference it is vital that the data sent gets delivered successfully. If the data being sent does not arrive at its desired location the quality of the call/conference is deeply impacted for example voices become unrecognisable or video stalls. This is because the application on the receiving end is missing vital information that was lost over the network. This loss of data can be due to various reasons that are common in the Internet. It should also be noted that the receiver might have got the data but when it checked the data and found that the data has been corrupted (may be due to transmission errors) the receiver sent a retransmission request.

Providing data reliability consists of two basic components.
 Loss detection
 Loss Recovery.

Loss Detection
One of the fundamental issues to be dealt with when designing a reliable protocol is how does the receiver get to know that it has lost a packet that it should have received. Similarly how does the sender know that a packet it sent did not arrive at the destination? There are many approaches to handle this. Now let’s try to understand the various techniques which illustrate how the loss could be detected.
If the data from the sender is a set of packets with sequence numbers then the loss of a packet will be detected when the receiver receives a packet whose sequence numbers are not contiguous. Say the receiver received a packet with sequence number 1 and another with the sequence number of 3, its pretty clear that the receiver has missed packet with number 2. But one thing to note here is that we are assuming in order delivery of packets, which we do not want to enforce. In the case of out of order delivery of packets, it could very well be the case that the packet with the sequence number 6 was not lost but is on its way to the receiver. So in cases like these the receiver cannot simply ask the sender to retransmit just because the packet has not arrived in order.
One method would be to take the workload off the receiver and for the sender to figure out if a packet was lost in the network. If all packets sent included a sequence number this could be possible. When the receiver receives a packet of sequence number X it sends a small packet called an acknowledgement also with sequence number X back to the sender, informing the sender that the packet has not been lost. This may seem like a potential solution but it does not cater with all the possible events. If the acknowledgement was lost in the network, the sender would believe that packet also to be lost in the network. If the sender could record the packets sent in a buffer. On receiving an acknowledgement the sender could then remove the acknowledged packet from the buffer. Thus leaving the buffer full of packets that were lost in the network or packets whose acknowledgements were lost in the network.

Loss Recovery
As the name suggests this function deals with how the sender responds when it has detected a packet loss. Basically when the receiver receives a packet it sends an acknowledgement back to the sender, at this point the sender knows if a packet or the corresponding Acknowledgement has been lost.

Figure 8 illustrates the various possible situations where either the Datagram packet or the Acknowledgement gets lost in the network. As already mentioned the sender has a buffer of sent packets, which is really a buffer of unacknowledged packets. Thus the sender can use this buffer to judge which packets need to be retransmitted. The issue of retransmission is dealt with in the next section.

Figure 8 RelUDP protocol performance, illustrating when a Packet gets sucessfully Acknowledged, when the Packet gets lost, and when the Acknowledgement Packet gets lost.

Retransmission

In order for this protocol to be reliable, it must retransmit packets that have not been acknowledged successfully.

Deciding which packets to retransmit
Basically as well as packets that have not been acknowledged successfully there is another circumstance that would require retransmission of a packet. Given the nature of the protocol, if the packets were delayed an excessive amount of time on the network before being received it could have negative effect on the applications/programs using the protocol. For instance, in a videoconference it is very important to receive the information as fast as possible, so that the video is visually comprehensible and audible. If some information for this conference was to arrive late it would have adverse effects on the conference, causing what is known as a jitter (late information basically disrupting the performance of some application). Therefore it is also vital to retransmit packets that have been delayed excessively.
The next issue is how to determine whether a packet is late or not. What variable of time would determine this? A static variable would only work under a certain situations, for example the delay from sending a packet from Ireland to the USA will be significantly larger than the delay sending a packet across the college campus. Having an adaptive variable which adapts to the networks current delay is a possibility, but seemed inadequate as networks can come congested quite quickly, leaving the protocol with a variable time which is too low, and thus resending quite a large amount of packets. In this protocol a fixed maximum delay time was defined (the maximum RTT), which would represent the requirements of the application using the protocol. This simply means that the application would only accept packets if they had a delay time less than half (RTT/2) this fixed variable.
A further possibility would be to have a random element choosing the maximum delay time, between two values. This would introduce a real life random delay on the packets. When groups of delayed packets are resent together (due to a node failure etc), they tend to congest the network even more so. Therefore the random element would deal with this problem.

Thus concluding that the new protocol should retransmit packets if
 The packet got dropped/lost in the network
 The packet got delayed excessively in the network

Use Datagram to transport data

One very important requirement of this protocol is fast delivery of packets. This might seem like an uncontrollable requirement at first but with greater inspection there are various techniques to produce this. When the functionality and performance of the two most used protocols are studied (UDP and TCP), the desired functionality of our protocol becomes clearer. It has already been noted that the reliability of TCP was desired, but unfortunately TCP has large overhead in dealing with data (sending and receiving), it requires a connection which takes time to setup which is undesirable in the new protocol. UDP on the other hand uses small packets “datagrams” that would be ideal for the new protocol. They are small, therefore they can be sent faster. Datagrams also are mostly independent of each other, so can be treated individually.

Header size
If the application that is using our reliable protocol deals with messages of large sizes, then the amount of time that it will take for the application to retransmit the message will be large and in that case it is very likely that loss is due to congestion. The retransmission of large packets into a congested network will in fact make the situation worse by congesting the network even more so. Consequently it is essential that the packet size used in our protocol is as small as possible. Comparing header sizes in UDP and TCP illustrates that UDP’s header size is significantly smaller than TCP’s header size.
Figure 9 RelUDP Packet Structure

The proposed header of the new protocol is shown in Figure 9. The source id is needed so that protocols will know where the packet is coming from. The sequence number is the identifier to tell packets apart from each other. The datagram packet size will be small, similar to the packet used by UDP.

Connectionless and Stateless

As already mentioned one of the main differences between TCP and UDP is whether a connection needs to be created at the start of a connection, and also whether a State has to be maintained. Both of these features are not required in the new protocol.
No Connection Setup needed
Before it starts to transfer data TCP uses a three-way handshake to set up a connection. UDP on the other hand just sends data without any formal preliminaries. Thus UDP is free from the delay required to establish a connection. If a connection was needed to be created before the transfer of data, the resulting delay would be unsuitable for applications where speed is a must. Therefore the new protocol will be connectionless
No Connection State needed
Some protocols like TCP maintain a connection state in the end systems. This connection state involves keeping track of the logical state of the protocol, for example whether the protocol is connected, closed, waiting for acknowledgement etc. UDP does not maintain connection state. Applications can process quite a lot more packets/ information if it does not have to process extra data associated with the state. Therefore the new protocol will be designed to be Stateless similar to UDP.

Absent of HOL blocking

As already mentioned the phenomenon known as Head of the Line (HOL) blocking occurs when sending independent messages over an order preserving TCP connection. This in turn causes the delivery of messages sent later to be delayed within a receiver's transport layer buffers until an earlier lost message are retransmitted and arrive.

Figure 10 Illustrating HOL Blocking

Figure 10 shows how the phenomenon occurs. This diagram shows that Packet 2 was delayed in the Network, therefore the Packets 3,4 and 5 will stay in the Transport buffer until the delayed Packet 2 arrives. The application will not receive Packet 3,4 or 5 until the delayed packet arrives, which will result in the applications service being effected.
This can have undesirable effects on the connection and is definitely undesirable with the new protocol as a will be aimed for VoIP signalling or possibly multimedia applications. Therefore when designing the new protocol, order preserving will not implemented. If packets get slightly delayed, and arrive out of order the receiver accepts the packets and will not wait until the packets are in order.

Minimal Congestion Control

Congestion is basically when there are very high amounts of traffic on the network, which in turn effects the performance of applications running on the network by creating a greater delay and a larger amount of packets getting dropped or lost throughout the network. One of the main reasons why the receiver might have lost the message from the sender and the reason for retransmission is because the network is congested.
In some situations congestion management and control is imperative in order to allow the network to recover from congestion and operate in a state of low delay and high throughput (number of packets being sent). In situations like this TCP would be an ideal protocol to use as it uses various congestion control mechanisms. The basic TCP congestion control (Tahoe) causes TCP to reduce its sending rate when congestion is encountered along the network path as evidenced by dropped packets.
On the other hand there are situations where congestion control would not suit the applications running on the network and prove to be counterproductive. For some applications, retransmitted data may be outdated by the time it is received so that retransmissions would not be effective. Furthermore, the majority of congestion control mechanisms reduce the sending rate by a large amount in response to a single lost packet. This is a good way to avoid or reduce congestion in the network, but some applications may not be able to cope with such an abrupt rate reduction. Applications like audio (VoIP) and video transmissions. As the new protocol is aimed for VoIP signalling or possibly multimedia applications congestion control would be counterproductive. Thus no congestion control will be implemented in the new protocol.