\section{TCP Implementation}\label{3-TCP Implementation}
We have implemented our version of TCP based on the authors description provided in the RFC793 protocol standard specification~\cite{1} and our own experience in the field of ad hoc wireless networks, with routing provided by the Dynamic Source Routing (DSR). The choice of the underlying DSR was based on the availability of an already implemented version of this routing protocol for the used wireless sensor hardware, developed by our team in an earlier stage of the seminar (we refer to its technical report for further information related with its functionality ~\cite{7}). Actually, given that the main goal of this work was to analyze TCP's performance when confronted with a multi hop ad hoc network in a real environment, any of the proposed routing protocols in the literature would have sufficed. This section offers an overview of the key features and particular parameters present in our TCP protocol implementation, as well as an analysis of the advantages and possible drawbacks of our design decisions with respect to the original protocol specifications.

As previously explained, our adapted TCP implementation for ad hoc wireless networks does not fully support the vast number of features of the original protocol functionality, mainly as a consequence of development time constraints. Nonetheless, the basic mechanisms and reliable connection-oriented philosophy that constitute the core of this transport protocol have been preserved. Table I presents a list of the most relevant constants used in our implementation of the protocol.

Our protocol design implements the basic procedures related with the connection management and control in a reliable fashion -connection establishment, ordered data transfer and termination-, whereas additional TCP features such as the congestion control mechanisms, transmission window scaling or checksumming were finally left out of our design scope. The lack of support of these procedures, some of which are included as a constituent part of the original TCP specification, certainly has a direct repercussion in the performance of our protocol version that will be lately discussed within this section. It is to be noted as well that our implementation closely follows the full description of the TCP finite state machine provided by the protocolīs authors, which describes the different life stages of a TCP connection. Appendix I provides an overview of the different states of a TCP connection in our protocol version, as well as an indication of the main events that occur in each state, along with their corresponding actions and transitions.

A first fundamental aspect of our implementation to be highlighted is the support of multiple simultaneous data streams through the use of connection multiplexing. The original TCP makes use of the notion of port numbers and socket binding to allow many processes within a single host to make use of the TCP functionality at the same time. For the sake of simplicity, our transport protocol version does not closely follow this principle, being a TCP socket composed only by the layer 3 network address -specifically, the assigned node address in the underlying DSR implementation used-, without concatenating it with a certain port identifier. The fact that our TCP version lacks of port identifiers that can be uniquely associated to local processes leads consequently to limitations regarding the multiplexing functionality provided by the protocol. As no further information is available uniquely binding processes to their corresponding connections, TCP cannot determine to which process an arriving segment belongs, and therefore our implementation is able to support a single active process per node communicating at a time.

However, even though our TCP version cannot support multiple active processes communicating simultaneously in a node, it is to be noted that each single process is able to maintain an open connection with several different peers at a time. This is achieved through the use of the TCB data structure, which allows the protocol to maintain certain status information relevant to the separate administration of every active connection in each device. Table II provides an overview of the main fields contained in a Transmission Control Block.
\begin{table*}
\begin{center}
    \textbf{Table II. }Transmission Control Block fields
\end{center}
\centering
\begin{tabular}{l|l}
\hline
\textbf{Field}&\textbf{Description}\\ \hline
Destination ID&Destination node address\\ \hline
TCP state&Connection state\\ \hline
Transmission Window&Current transmission window size\\ \hline
ACK&Next expected ACK number\\ \hline
SEQ&Next SEQ number to be used\\ \hline
TCB List Size&10\\ \hline
Connection establishment counter&Number of conn. establishment attempts\\ \hline
\end{tabular}
\end{table*}
\begin{figure*}
\centering
\includegraphics[width=3in]{figure2}
\begin{center}
     \textbf{Figure I.} TCP segment format
\end{center}
\end{figure*}

In our version of the protocol, the required data structure utilized to handle and administrate the differenct active connections of a device was implemented as a static table with a predefined fixed number of entries, named TCB list. Each entry of the defined TCB list corresponds to a different TCB containing all the important information required for TCP to maintain control over the connection and data transfer process (such as the current sliding window size or the following sequence number to be used at transmission). One of the main limitations of defining the TCB list as a static structure with a pre-established maximum number of entries is that there is a risk of overflowing should a high number of connections be opened at the same time. As a consequence, the maximum number of simultaneous connections that can be supported by our TCP protocol is directly determined by the size of the TCB list, which in our case was set to a value of 10, thus constituting a clear limitation in terms of the multiplexation functionality provided by the implementation.

Furthermore, the TCP segment structure definition follows the functional specification provided by the authors, containing the main information fields of the header format required by the protocol in order to operate (see Figure I). One of the implementation decisions followed was to define the TCP segments as static structures with a pre-established fixed payload size (30 bytes). Such an approach has as main advantage that it enables a simplified management of the information during the data transfer process.

As it can be observed, our definition of the TCP segment does not include the checksum field, which is defined as an integral part of the original specifications. The introduction of error detection/correction capabilities in the transport protocol constitutes an issue of great importance specially when referring to wireless scenarios, where the use of a shared uncontrolled medium -in which undesirable propagation effects frequently take place- leads to a data link layer with typically high bit error rates. Even though the 16-bit long cyclic redundancy check (CRC) mechanism constitutes a quite weak approach by modern standards -the implementation of a more robust 32-bit CRC algorithm would be better suited, though it would incur in higher protocol overhead-, TCP is still able to detect a high proportion of the errors introduced along the transmission process. Furthermore, the weak CRC detection algorithm is in most cases partially compensated by the common use of a better integrity check at the data link layer -below both TCP and the routing protocol- such as the ones implemented in PPP or the Ethernet frame. The lack of such redundancy information prevents our protocol from being able to assure correctness in the transmission process, e.g. it is not possible to detect the introduction of errors in the received segments.

A further relevant aspect of our implementation to be highlighted is the one regarding the synchronization procedure performed during the establishment of a TCP connection. We explained in section 2 that for a connection to be initialized, the two TCP sides must synchronize on each other's initial sequence numbers (ISN) during the three-way-handshake mechanism. According to the authors' specifications, these ISNs should be randomly obtained through the use of a generator which is continuously incremented, cycling approximately every 4.55 hours. However, our implementation does not implement such a procedure, and as a consequence each device assumes that the connection is started by assigning to the first data byte the sequence number 1. Figure II provides an example of the message exchange that takes place throughout the different phases of a standard connection in our implementation. The problem with starting off each connection with a non-aleatory sequence number resides in that it introduces the possibility of segments from different instances of a connection getting mixed up, shall for example one of sides of the TCP connection crash and lose all knowledge of the sequence numbers it had been previously using. We can conclude that the lack of a procedure to generate the ISNs in a random fashion in the connection establishment prevents our TCP implementation from being able to identify segments from previous instances of a connection, thus making it susceptible to the mentioned segment duplication problems in the communication process.
\begin{figure*}
\centering
\includegraphics[width=3in]{figure0}
\begin{center}
     \textbf{Figure II.} Example of TCP connection life cycle in 3 phases: connection establishment, data transfer (3 segments) and connection termination.
\end{center}
\end{figure*}
As it was previously stated in section II, one of TCPs main tasks is to provide a communication service that ensures that the data can be transferred reliably and in order, regardless of any fragmentation, disordering, or packet loss that may occur during transmission. This is achieved in our protocol version on the one side by the use of sequence numbers, and on the other side through the temporary storage and retransmission of the information. Additionally, it is to be highlighted the acknowledgement procedure followed in our wireless-oriented TCP implementation. Even though the original TCP specification refers to each data byte individually, and uses sequence numbers to keep track of which bytes have been sent and received, we decided to follow a more optimized approach by assigning a sequence number to each transmitted data segment. Since the payload field of each transmitted TCP segment can contain up to 30 data bytes, by using a single sequence number per segment each ACK segment informs of the correct delivery of a complete range of bytes. Such optimized procedure allows our implementation to significantly reduce the number of acknowledgements sent back to the receiver, thus decreasing the overall overhead generated by the our protocol and leading in last term to a more efficient use of the shared wireless media.

Our TCP version provides the reception device a mechanism to govern the amount of segments originated by the sender by implementing a simplified sliding window algorithm in which the maximum transmission window size that can be achieved is limited to one segment. Given that the window size admits only the transmission of a single segment before reaching a size of 0, the sender must stop sending further data after each transmission until it has received the acknowledgement of the previously sent segment (see Figure II).

Such an approach leads in last term to a transmission schema in which the sender is just able to transmit a single data segment at a time, thus limiting the overall data communication throughput. However, a clear advantage of implementing this single-sized sliding window alternative is that it greatly simplifies many aspects of the protocol design: issues such as holding variables that keep track of the current segments received and acknowledged or the ones received but not yet acknowledged can be therefore avoided. A further positive aspect of this schema is the fact that it provides an inherent mechanism to ensure an ordered data delivery service. Additionally, our TCP version does not require the implementation of a reception buffer for temporary data storage, as each received segment can be directly handed out to the upper application layer without any further processing needs.

It is to be noted that as a consequence of the followed sliding window procedure TCP automatically performs the data transmission in an autonomous fashion as further data acknowledgements are received. Whenever a data transmission request from the application layer arrives, a copy of the message is temporarily stored in a Retransmission Buffer. Prior to the transmission of the newly income data segment, the window size as well as the Retransmission Buffer has to be examined, to check if it is currently possible to transmit further data and no previous segments are already waiting to be sent, respectively.\begin{table*}
\begin{center}
    \textbf{Table III. }TCP Retransmission buffer entry fields
\end{center}
\centering
\begin{tabular}{l|l}
\hline
\textbf{Field}&\textbf{Description}\\ \hline
Destination ID&Destination node address\\ \hline
Segment number&Retransmission queue identifier\\ \hline
SEQ&Next SEQ number to be used\\ \hline
Payload&Data waiting to be sent\\ \hline
Retransmission counter&Number of segment retransmissions\\ \hline
\end{tabular}
\end{table*} If that is the case, it means that the data segment can be immediately transmitted, and therefore TCP will assign a sequence number and initialize a timer, waiting for the other end to acknowledge its correct reception to be deleted from the buffer. Otherwise, the segment will have to wait at the Retransmission Buffer until all the previous data has been properly delivered and acknowledged.

The aspects of correctness or interoperability are not affected by the selection of a certain data structure organization for the Retransmission Buffer, which affects only local performance for each node. The use of segments with a predefined static payload size saves our TCP implementation from having to deal with issues in the wireless nodes such as dynamic memory management of the Retransmission Buffer entries as new data transfer petitions are received from the application layer.

The aspects of correctness or protocol interoperability are not affected by the selection of a certain data structure organization for the Retransmission Buffer, which influences only local performance for each node. The use of segments with a predefined static payload size saves our TCP implementation from having to deal with issues in the wireless nodes such as dynamic memory management of the Retransmission Buffer entries as new data transfer petitions are received from the application layer. In our version of the protocol the Retransmission Buffer was implemented as a static table with a predefined fixed number of entries. Each Retransmission Buffer entry corresponds to an unacknowledged data segment, and contains information related with the destination node address, the assigned sequence number, the segment payload data waiting to be acknowledged, as well as a counter that refers to the number of times a data retransmission has been performed. Table III provides a description of the fields in a Retransmission Buffer entry.

One of the clear limitations of implementing the Retransmission Buffer as a static structure with a pre-established maximum number of entries is that there is risk of overflowing should a data transfer burst coming from a higher protocol take place -e.g. if FTP performs the transmission of a bulky file at a high data rate, thus requiring to send a high number of segments in a short period of time to a given destination. Buffer overflowing is an extremely undesirable situation that should be prevented by our protocol, given that the data packets that cannot be stored will be directly discarded before being previously transmitted, being perceived by the upper layer transport protocols as packet delivery failures. This drawback can become critical if the transport protocol is deployed in wireless nodes that present severe storage memory limitations -e.g. the IdwaRF~\cite{9}, developed by the german company chip45~\cite{10}, or the BTNode rev. 3.22 Bluetooth, released by the Swiss Federal Institute. In such scenarios, the undesireable situation in which a segment must be dropped at the transport layer due to lack of free entries at the temporary buffer can become frequent, leading in last term to important data loss ratios and serious performance problems that put at stake the reliable data-stream service to be provided by TCP.

Note that to ensure an ordered delivery protocol service it is required to handle the Retransmission Buffer as a queue in which the first data segment to be stored must be the first to be transmitted afterwards by the transport layer. This was achieved by adding an identifier field to each buffer entry which refers to the order in which the segment was stored as it arrived from the higher level protocol. This segment identifier serves as a means for TCP to determine which segment should be next transmitted among the ones waiting at the Retransmission Buffer as further ACK segments are received, thus being able to provide an ordered data delivery service.

An additional critical important factor that greatly influences the performance of our transport protocol is the configuration of the required timeouts -in TCP the most relevant ones are those addressing the connection establishment and termination phases, as well as the segment retransmission timeout in the normal data transfer stage. Given the variability of the networks that compose an internetwork system and the wide range of uses of the TCP connections, the retransmission timeout must be determined taking into account the specifications and characteristics of the underlying routing protocol. As it was previously explained, we have implemented our TCP version running over an already implemented version of DSR, developed by our team in an earlier stage of the seminar. DSR is a reactive on demand protocol which uses soft-state source routing instead of hop-by-hop routing to fulfill the forwarding of packets between source and destination within a multi hop wireless ad hoc network.

In order to perform an estimation of the required retransmission timeout in our TCP implementation, it was required to determine an upper bound for the time it takes to DSR to perform an individual segment transmission (we recommend the reader to make use of the DSR technical report to acquire a better understanding of the protocol specific features~\cite{7}). For that purpose, it was necessary to calculate the maximum time in order to dynamically discover a route between sender and destination throughout the wireless network -Route Discovery delay- and then add to this time value an estimation of the data packet forwarding time once the wished path information has been successfully acquired. With this premise, and considering significant established parameters of the used DSR version -which refer to the maximum number Route Discovery reattempts (3) and to the retransmission timeout (3sec)- we obtained an estimation of the TCP retransmission timeout, as follows:
\begin{center}
    $RDD   = RTO_{DSR} * Max.Rtx=3 * 3 = 9 sec$
$RTO_{TCP} = RDD + Fw.Delay     = 9 + 3= 12 sec$
\end{center}

As it can be observed, the use of high retransmission timeout (RTO) values in the underlying DSR protocol leads consequently to a remarkably upper bound for the RTO estimation of 12 seconds. The utilization of such a high segment retransmission timeout in our TCP implementation will undoubtedly have a great impact in the protocol performance, especially regarding the achieved delivery ratio and transmission throughput. As it has been previously explained in this section, our version of the DSR protocol implements the Retransmission Buffer -where the data segments are temporarily stored until the required acknowledgement confirming their correct delivery is received- as a static structure with a predefined limited number of entries. Given that our implementation makes use of a single-sized sliding window, once a segment transmission to a given destination has been performed, the successive data segments to be delivered to the same target node are directly stored in the Retransmission Buffer. By making use of a high value for the retransmission timeout, the average lapse of time until new data entries are successfully sent -and thus deleted from the Retransmission Buffer- is expected to be consequently long as well, which in last term leads to frequent overflows in case the upper application layer attempts to transmit data at a high data rate. Therefore, we can conclude that the establishment of such a high TCP RTO will have a negative effect in the throughput and segment delivery ratio achieved by our TCP implementation when the protocol is confronted with more demanding multi-hop scenarios where there is greater probability that a single transmission fails.

Even though it constitutes a simplified version of the specified features, we believe that our DSR implementation preserves the reactive philosophy that lies behind this transport protocol. In the following section, we evaluate the performance of our version of the DSR protocol under varying testbed conditions.







