%----------------------------------------------------------
%---- Preamble --------------------------------------------
%----------------------------------------------------------

% Document class: IEEEtran
\documentclass[
  11pt,                           % Text size
%	draftclsnofoot,
%	journal,
%	onecolumn,
%	peerreview
% journal,                        % Journal Mode
% letterpaper                     % Paper size	
%	conference,
	final
]{IEEEtran}

\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{booktabs}

%----------------------------------------------------------
%---- Title -----------------------------------------------
%----------------------------------------------------------
\title{Telematik Projekt - Wireless Embedded Systems}



\author{%
	\IEEEauthorblockN{Adri\'{a}n Anto\~{n}ana G\'{o}mez, Carlos D\'{\i}az C\'{a}novas\\
    \IEEEauthorblockA{%
    Computer Systems and Telematics\\
    Institute of Computer Science\\
    Freie Universit\"at Berlin, Germany\\
    {antonana@zedat.fu-berlin.de, cdiazc@zedat.fu-berlin.de}
    }%
  }%
}%

\begin{document}
\maketitle

%----------------------------------------------------------
%---- Abstract --------------------------------------------
%----------------------------------------------------------

\begin{abstract}
This is the second technical report of the \textquotedblleft telematik projekt\textquotedblright \  lecture of the Freie University in Berlin for the winter semester 2008/2009. This second report will explain the implementation of a transport layer that works over the, already implemented, routing layer which can find routes in-between nodes in any topology and provides with a basic message sending routine. Over this routine will lay the transport layer implemented which brings the ability of granting the message (now called segments) reception and its reception in order. The transport protocol implemented has its basis on TCP, and features its basic functionalities but had left aside some others as the congestion control.
\end{abstract}

%----------------------------------------------------------
%---- Main Matter -----------------------------------------
%----------------------------------------------------------

\section{Introduction / Motivation}
As second part of a project, the transport layer implementation looks further on the connectivity idea in a wireless network. Once the devices are able to find each other and therefore are able to send pieces of information between them, now they are in need of a system which will allow communication with the reasonable assurance that their messages will come to destination. At the end of this second part, it can be said, that the project resulted in a framework for nodes communication that could be easily used by upper-level applications to build more complex systems with end-user functionalities.
As the behavior on different topologies has already been tested before, the testing field will be less strict on this point and focus more on precise efficiency of the transport layer.

\subsection{Transport protocols and TCP overview}
As introduced before, a transport protocol should overlay an already existing routing one. In this case, the transport protocol has to preserve  the information integrity and be able to connect, send and finalize a socket to a remote host previously selected and with a known route, this work has not to be done by the transport protocol which will not know further than a data type anything related to routes or the routing protocol.

A particularity that has to be noticed before continuing is that this implementation is only able to manage one connection at-a-time, this means that the whole system is oriented in a more p2p way, where at first the requester of a connection acts as a client and the other end as server, changing this behavior once the connection is done to real peer to peer model in where no server or client are known but just two ends of a same connection.

Even though being an old communications protocol TCP has survived for long and is now used as basis of most of the Internet services available, thanks to its easy-to-implement compatibility between networks of different type. Despite all this, TCP was not thought as a protocol for wireless interactive communications (which almost didn't exist at the time it was designed) and might have some problems on this environment like huge traffic when a network has lots of packets loss and the underlying protocols don't manage it correctly. Even considering this, as it is a very depurated protocol with a relative easy implementation it has been chosen for the provided nodes.

TCP has 3 basic stages, first, when it connects with the remote host, then the segments exchange which is the communication itself and finally the closing. The first and last stages will be explained later on this documented, concerning the message exchange: the basic idea on segment sending in TCP that ensures the reliability of the communication is the confirmation by acknowledgments on every single byte sent, this means, that a TCP application will know if a single byte has been lost or a complete pack of them by the response of the other side of the communication. Of course TCP won't do it with a single response on every single byte sent but by packing responses that will confirm a certain number of received bytes of data. This method will allow then a sender to pack data in a single segment as well as the receiver to expect packs of data.

\section{Contribution}
\subsection{TCP workout}
The steps taken to develop the TCP layer were the following, first ensure the reliability of the routing protocol, this was already done in the first part of the project, but since TCP relays on it, this is an important step to take. After this done it has to be studied which parts of the protocol will be needed on this particular implementation and which will be left apart, because they are not necessary or because they are way too complicated for the available developing time. This done, a final step, mainly technical had to be overcome to finally get to retrieve the results.

\subsection{TCP features implemented}
The implementation made fully-covers the basic features of connecting to a remote host, sending a segment through the topology and disconnecting, also it ensures that if any malfunction occurs the protocol stack will not be hanged on a particular stage but will be able to resolve this by \textquotedblleft timeouting\textquotedblright  \ the connection and forcing its close to allow a new client to come up or a new connection to be made.

At first let's have a look at the TCP core, TCP uses a state-machine (see \autoref{fig:state.pdf}) to be able to handle a connection whenever a connection is open, it is on a particular state of this state machine. This state and the connection to the others will let the protocol close in case of error or correct one of the sides if this has wrongly replied to a request or message. The full functional state machine that TCP has been reduced for simplicity reasons. The main structure is conserved but some transitions do not exist anymore. This state machine is now divided into 3 significant parts, first one the point where a new client is requested from a host and its evolution until the ESTABLISHED state, the same but for the host that receives the connection request, and finally the closing procedure, which is somehow divided into two parts as is the opening but starting from a same point.\\


\subsubsection{Connection openning}
\ \\
To open a connection TCP uses what is called a \textquotedblleft 3-way handshaking\textquotedblright \ which is a method that uses three messages between the two ends to establish a connection. First, the host that wants to establish a connection will send a message with a specific flag activated (the SYN flag), according to this message, the other host will acknowledge this message but indicating that him too wants to open a connection (this will be a message with its flags SYN and ACK activated). Finally, when receiving this message, the host, tat initially sent the SYN message now knows that the other is ready and accepts by acknowledging with a message with an ACK flag on. This solution is a simple workaround for the well-known problem of the two armies.

\begin{figure}[htp]
\centering
\includegraphics[width=0.4\textwidth]{open.pdf}
\caption{Three way handshaking}\label{fig:open.pdf}
\end{figure}

In reference to the state-machine, it was simplified to only met the above described paths and has a major difference with the original one, this is that CLOSED and LISTEN states are not different; this is due to the fact that the scatterweb framework is event-orientated and requesting a new connection is an active action while having a new one that comes-up is a passive one. This all means that those actions make the state be the same, or, more correctly, make no necessity anymore to difference them.\\


\subsubsection{Connection closing}
\ \\
While TCP contemplates two different types of connection closing procedures, in this case a modified version of the active closing has been implemented, usually, on systems that have to handle lots of connections and therefore need lots of resources and processor time to manage them, the connection closing has to be done carefully, some states reached, the system will have to free the resources previously reserved for a particular socket and this could lead to the lose of message to be sent or to ignore messages that the other side still has on its buffer. Considering the implemented system as ideal, the message exchange buffer will always be void (see next section) and only a buffer for lost messages is kept. This means that when a connection termination is requested no messages could be left to send (the system won't allow it anyways).

\begin{figure}[htp]
\centering
\includegraphics[width=0.4\textwidth]{close.pdf}
\caption{Closing an active connection}\label{fig:close.pdf}
\end{figure}

This said, each side of the connection, when a termination request is sent will have to pass through two different stages before being able to consider its connection as closed. The termination procedure can be seen in detail in the figures; but the main idea is, again, one of the ends requests for a termination, this time enabling a FIN flag and the other end will then, acknowledge this. At this point, the active and passive closing will have both of the ends waiting, the end that received the FIN segment at first will have to wait until its buffer is void to continue with the procedure of closing, and therefore send the remaining bits of information it could have (as said this won't happen on this system but it's kept for compatibility reasons). So, when finally, both the sides are ready the same message exchange is done but on the other direction: the side that received the FIN now sends the FIN and waits for an acknowledgment, when this is received the connection on both  sides is closed. To fully comply with the TCP rfc specification, the first end, once received the last FIN and its ACK sent, would have to wait some time in a state called TIME-WAIT until a timeout is produced to close the connection, but as said, this is considered an ideal system and will not have to wait this time and jump directly to the CLOSED/LISTEN state.\\

\subsubsection{Segments communication}
\ \\
When a connection is done the state machine is in both sides on the ESTABLISHED state in which messages can be exchanged. But before going deeper on that it has to be explained how the TCP messages are formed and the fields its header has to identify each message.

\begin{figure}[htp]
\centering
\includegraphics[width=0.4\textwidth]{header.pdf}
\caption{TCP header fields}\label{fig:header.pdf}
\end{figure}

The implemented TCP layer has kept only the fields extrictely necessary for the implemented functionallities.\\
The \textquotedblleft sequence number\textquotedblright \ field which is 8 bits long will hold the sequence number of each segment which is in fact the sequence number of the first byte on it, as explained before each byte is numbered, but those can be packed. This field is mainly used to keep the bytes in order, obviously, as segments come and go, this field should always be greater if everything is correctly acknowledged or at least stay at the same value if no acknolodgement is received, this way the receiver knows always that what he receives is in order.\\
The \textquotedblleft acknolodgement\textquotedblright \ field is where, once a message received, a host will specify what is the next sequence number it expects, this means, how many bytes it has correctly received, confirming, this way a certain number of bytes. As well as the sequence number field, this one is 8 bits long and as the previously-explained one it has to increase its value while messages are exchanged.\\
If an error is detected on both of those fields the whole last segment will be resent. In a further implementation of TCP (this is actually accepted in the rfc) just the N first bytes of a segment can be acknowledged and this way the sender will know that not the whole previous segment has to be sent again, but just a part of it. Also it has to be noticed, that, since this is an implementation with no meanings of public use further than for testing purposes, no value on those fields will always be beyond 255 (11111111b), again simplicity on data structures has been considered over efficiency.\\
The third field on the header of each TCP packet will be the one where the flag are stored, the available flags here are SYN, ACK and FIN, so for them only 3 bits (out of 8) will be used leaving 5 unused. Each of the detailed use of those bits have been already described before, but grosso-modo, their use are for; SYN: requesting a synchronization (opening a connection). ACK: confirming by any means a segment received. FIN: requesting a connection termination. Please refer to each section for a more precise description.
The fourth and last field implemented into the TCP header is a field that is not contemplated in the TCP standard usually, this field stores the TCP-payload length, in fact, with a static header as the implemented this field should not be necessary at all and, in fact, it is not, but as it has already been commented, this is a testing environment and having this value easily available makes debugging way more simple. As the others, it holds 8 bits, long enough to store regular values, and by the way, in our scatterweb environment, the packet size can not exceed 127 bytes, so having a maximum of 255 is safe here.\\

A practical example of this will be: trying to send a segment between two hosts that contains a short message, for example \textquotedblleft hello\textquotedblright . The first host (the one willing to send) will build a packet containing a TCP header where it will specify the payload length as 5 (bytes) and a sequence number which could be any, being the next-byte-number that the other side will be waiting (after an ACK), for instance 62. The acknowledgment field here can have any value, but, for correctness, it will have the same value of the last sequence number on the last acknowledgment received. So the other end will receive 5 bytes starting on the 62. This, will have then to answer with the acknowledgment flag activated and in the acknowledgment field the number of the next byte it expects to receive, so: 62 + 5 = 67. This will confirm the sender that the message arrived correctly.

\begin{figure}[htp]
\centering
\includegraphics[width=0.4\textwidth]{send.pdf}
\caption{Sending segments between hosts}\label{fig:send.pdf}
\end{figure}


\subsection{Features not implemented, consequences}
There is a number of features that are included in the official rfc document of TCP that haven't been implemented as congestion control, packet segmentation\dots

At first the header of the TCP packet is very different from the original one. Since no services are implemented but an end-to-end communication between two nodes, the ports paradigm is not necessary to identify various clients running different services and those fields were omitted. Other fields as the urgent pointer, the checksum, the options or the header length were also ignored since the implementation made shall not need them. Finally an important field that is not present neither is the \textquotedblleft window size\textquotedblright , this one is used for the flow control and this feature is not present.

Flow control: as said the flow control is not available on this TCP protocol. The flow control is used to avoid problem when a sender is faster than the receiver and allows the receiver to specify in the window size field of the header how many bytes can the sender actually send until he will need authorization again to send, this will result in the sender somehow adopting the same bandwidth as the receiver. Not implementing this feature could lead to some risks like the massive loss of data just because the receiver buffer is not ready to get the message a very fast sender is providing with. Also, this issue is not likely to happen very often if the topology of the network is not mobile and has been properly configured, but not on mobile networks, where the receiver node could change its range for moments.

\begin{figure}[htp]
\centering
\includegraphics[width=0.4\textwidth]{state.pdf}
\caption{Actual implementation of the TCP states-machine}\label{fig:state.pdf}
\end{figure}

Congestion control: this is another feature that is not present, of course, not having implemented the flow control, implementing a mechanism for congestion control will make not too much sense. For instance, the slow-start / fast-recovery strategies that are usually present in TCP use the window size parameter of the header to allow, step-by-step the sender to increase the bandwidth to use. Again the consequences of that are usually the lose of data or the reduction of the bandwidth used (or its entire consumption in acknowledging) by confirmation messages and segments resents because the sender has no capacity to process messages so fast.

Another feature not present here is segmentation, as the previous ones were not implemented for simplicity, this one has its reasons in the environment on which the production is done. On this project, no useful information tends to be sent between the nodes, no long transmissions will be done and no intermediate routers with different MTU will be present, the only work done will be with the provided nodes and testing-purpose segments. So no need at all of segmentation here. Though, if any kind of segmentation were done, the packets will be able to be cut in various segments and rejoined at the arriving-end allowing, as said, big files transmissions.

As already introduced in the previous sections, the state-machine by which is formed and controlled TCP has been modified to met the schedule and needs of this implementation: some states like TIME-WAIT or CLOSING are missing and there are also transitions between states that do not exist. Mainly, the missing transitions are the ones contemplating the less-frequent cases such as demanding a connection close when a opening procedure is in place. All those not-so-frequent cases have been solved by simple timeouts, this means, that requests out of the actual state machine are ignored and if after a certain time a proper request/answer has not been received, the connection is forced to be closed. Of course the lack of all this reduces the possibilities in the protocol like the different possible issues during the active close; or allowing a \textquotedblleft clean\textquotedblright \ connection closing during an opening.

Finally there are some other minor features not present, like the urgent pointer or the use of other flags apart from SYN, ACK and FIN that are not so relevant as the above described one.

\subsection{Difficulties}
Even if the protocol was reduced to ease the development, some difficulties were found, mainly technical ones. The first ones encountered regarded the sequence and acknowledgment numbering, some synchronization problems were encountered that were finally resolved by studying more carefully the messages exchange. Particularly, when a connection was done and a message was sent and confirmed, trying to make the previous receiver send a message (using the reverse route) ended on the end size ignoring the message and provoking resends and a forced closing.

Also some issues concerning this topic but caused by the event-oriented programming framework happened; the difficulty to synchronize events that happen in different parts of the code and that are forced to occur due to the framework (on which there is a big lose of the code-flow control) were solved in the same way as problems related to invalid segments, this is timeouting everything. If a proper response is not met after N resends and / or a timeout then the connection is closed and the whole procedure starts again. This prevented the program from keeping stuck in an infinite loop of not recognized messages or errors like when a node is shutdown during a active connection.
\newpage

\section{Evaluation and results discussion}

\subsection{Testing procedures and results}
The testing field will be slightly different on this second part of the project, not so many different topologies were needed here because the main problems and functionalities difficulties of the topologies were already studied on the first part. So, in result, only chained topologies were configured, this is because on fully-meshed ones or some other variants the performance was almost perfect and significant changes were spotted the more hops a topology has. This is why, only 2, 3 and 4 nodes chained topologies were tested.

\subsection{Tests overview}
As usual, on two nodes topologies, there was not too much to report, messages and acknowledgments had fluidity. Apart from those, as it was expected more and more segments (and also the bigger they were) were lost as the topology was longer, intermediate nodes could not always retransmit neither the messages or the acknowledgments, and even opening a connection remained hard on some scenarios.

\subsection{Results}
As said, the bigger the topology was, the more packets were lost during the sending and the retransmit (by the intermediate nodes), in this new scenarios, where only the use of TCP can be considered, there is mainly two kind of segments to watch over, the ones containing a message and the ones containing an acknowledgment, their main difference is their size and this is what made the results interesting.

On the small topologies the packets came and went in the same way, this means, no big packet-loses and therefore not a big number of retransmitions, also, as the nodes had the same bandwidth capabilities on both sides (up and down) no congestion was produced on those kind of networks. But the results got more interesting as the networks grew and even more as the segment sizes grew too. In bigger networks, when the segments were little, there were a certain number of retransmitions depending on the number of hops and also the bigger the topology was the bigger the forced-disconnects were.

But on 2 and 3 hops networks, there was a special case which is when the segments were big and the network performance relatively low. Being so, the effective traffic on one direction was higher than in the other, this means that while big segments with data didn't arrive and needed lots of retransmitions, when arrived, the acknowledgments sent in response arrived more times and didn't need to be retransmitted. Where messages with data had 35\% of performance, ACKs were around 67\% on the same scenario (a 3 hop, 4 nodes chain topology).

Also on very low performance topologies opening and closing a connection were very problematic and lead in most cases to not being able to open a connection or to force to close it without end to end confirmation.

\subsection{Results discussion}
As it can be seen, the most interesting results were found when networks were not very reliable. At first it has to be remarked the connection-opening problem, this is when the topology performance is close to 0 even opening a connection is hard or even impossible. This is a good indicator for a network reliability and good bottle neck to avoid painful connections, this means that if opening a connection is impossible, trying to send and acknowledge messages which is an even more difficult task will be impossible. So apart from granting the existence of the two sides, here is a good show-up of this feature of the 3-way handshaking.

\begin{figure}[htp]
\centering
\includegraphics[width=0.4\textwidth]{graf.pdf}
\caption{ACK performance and data-segments performance}\label{fig:graf.pdf}
\end{figure}

Another interesting result that needs to be commented is the fact that almost always, the performance of the segment sending is half of the acknowledgment, even if segments with ACKs are important for the protocol the vital information is contained in the segments and without this data the whole protocol would make no sense. So, seeing those results it comes to mind that a mechanism should exist that would allow both ends to accommodate the size of the data segments they send to make them as performant as the network allows. Fortunately, this mechanism exists indeed; and is the congestion and flow control that were already mentioned before. As neither of this mechanism exist on the implemented protocol, the results saw here illustrate perfectly the usefulness of this systems when on a real-life network.

%--Inventarse algun grafico de algo que muestre que los ack se pierden muy poco pero que los mensajes se pierden mas y que eso hace cuello de botella de aluna manera y que con flow control eso no pasaria o pasaria menos porque el tammano de la ventana se podria modificar segun las necesidades del enlace.

%\begin{figure*}
%\resizebox{18cm}{!}{%
%\includegraphics{lost.pdf}}
%\end {figure*}

\section{Conclusion}
In this second technical report it has been shown how to build an implementation of a transport protocol in a wireless embedded system. Along with this work some interesting conclusions could be extracted regarding this project. As it was seen in the first part of the project, again, theory and practice were way far from each other but this time, lesson were learned from previous practices, like how to build networks and which topologies are more efficient or deficient for different purposes.

The results to this TCP implementation were more focused on showing how the protocol will work but ended up with very interesting results that showed the problems of not implementing certain features like flow control or congestion control. A good transport protocol for an unpredictable wireless network should then have even more features than for reliable cabled one to be able to make mobile communication stable and efficient. Systems to prevent problems like the ones saw there, where \textquotedblleft absurd\textquotedblright \ performance values were met are then necessary. All this confirms, one more time, how the higher the protocol layer is do not mean it has less problems but new ones emerge that has to be solved.

%\input{text/1-Introduction}
%\input{text/2-Basics}
%\input{text/3-Specifics}
%\input{text/4-Comparison}
%\input{text/5-Conclusion}

%----------------------------------------------------------
%---- Bibliography ----------------------------------------
%----------------------------------------------------------

\begin{thebibliography}{}

\item
RFC number 793, \emph{DSR protocol}\\
http://www.faqs.org/rfcs/rfc793.html\\

\item
Andrew S. Tanenbaum, \emph{Computer Networks}, 3rd~ed.\hskip 1em plus
  0.5em minus 0.4em\relax \\
  Prentice Hall Editions

\end{thebibliography}

\end{document}
