\section{Protocol Implementation}\label{3-Protocol Implementation}
We have implemented DSR based on the specifications from the last currently available published description provided by the authors of the protocol [1] and our own experimentation with them. In this section the particular parameters and key implementation features our implementation are highlighted, and the advantages and limitations of our design decisions with respect to the original specifications are thoroughly discussed.\newline As we previously mentioned, our version of the protocol does not fully implement the DSR functionality, mainly due to the limitations in the available development time. However, the main features and basic philosophy that lie behind the idea of this reactive on demand routing protocol have been preserved. Table I lists the constants used in our implementation of the DSR protocol.
\begin{table*}
\begin{center}
\textbf{Table I} Constants used in the DSR implementation    
\end{center}
\centering
\begin{tabular}{l|l}
\hline
Maximum number of ROUTE REQUEST retransmissions&3 \\ \hline
Network Diameter & 10\\ \hline
Time To Live (TTL) &10\\ \hline
Time between ROUTE REQUEST retransmissions&3s\\ \hline
Number of Send Buffer entries&40\\ \hline
\end{tabular}
\end{table*}
  Our design of the DSR protocol implements the Route Discovery mechanism, whereas the Route Maintenance operation and the use of a Route Cache were finally left out of our design scope. The absence of these basic mechanisms that are originally described as part of the original DSR specifications has undoubtfully repercussions in the protocol performance that will be lately discussed in this section. We defined the different packet structures following the conceptual propositions offered by the authors, thus containing the main data fields required by the different DSR protocol mechanisms(see Tables II, III and IV).


\begin{table*}
\begin{center}
\textbf{Table II} REQUEST PACKET structure
\end{center}
\centering
\begin{tabular}{l | l}
\hline
\textbf{\centering Field} &\textbf{Description}\\ \hline    
Destination ID &Destination node address\\ \hline
Route Record&Node sequence between sender and destination \\ \hline
Pointer&Indicator of nest hop in Route record\\ \hline
TTL&Time To Live\\ \hline
\end{tabular}
\end{table*}
\begin{table*}
\begin{center}
\textbf{Table III} REPLY PACKET structure 
\end{center}
\centering
\begin{tabular}{l|l}
\hline
Field & Description\\ \hline
Source ID &Source node address\\ \hline
Route Record&Node sequence between sender and destination\\ \hline
TTL&Time To Live\\ \hline
\end{tabular}
\end{table*}
\begin{table*}[t]
\begin{center}
\textbf{Table IV} DATA PACKET structure
\end{center}
\centering
\begin{tabular}{l | l}
\hline
Field & Description\\ \hline
Destination ID &Destination node address\\ \hline
Route Record&Node sequence between sender and destination\\ \hline
Payload&Data to be sent\\ \hline
TTL&Time To Live\\ \hline
\end{tabular}
\end{table*}
  We decided to implement the packets as static structures with a pre-established maximum number of entries in the Route Record list, which was set to the defined network diameter. This approach enables a simplified management of the packets, as it is not necessary to deal with aspects such as memory management in the wireless nodes as the messages are forwarded -e.g.: when the intermediate nodes append their own addresses to the Route Record of a Route Request packet in the Route Discovery. However, this simplification in the packet forwarding process leads at the same time to a non-optimized generation of routing overhead in our protocol. Given that the Route Record field cannot be dynamically increased as the route to a destination is discovered, the protocol incurs in the same overhead no matter how long the sequence of hops is. The most extreme example of routing overhead inefficiency is the Route Request packet originated by the node whenever a Route Discovery is initiated. In this case, the initiator broadcasts a packet with an almost empty list containing only its own address, and nevertheless the transmitted number of bytes is the same as if the message contained a complete route to the destination. Although the Route Record contained in each packet distributes valuable information throughout the network, it adds as well more than 10 bytes to each packet header. This can be a proportionately small overhead when transmitted within a large packet, but it is a very high routing overhead for real-time interactive applications, where the typical packet size tends to be small.

 The Time to Live field is utilized in every defined protocol message as a means to have control over the maximum number of intermediate nodes allowed to forward that copy of the packet. A variety of algorithms can be implemented using this hop limit in order to control the propagation of the packets throughout the network, especially during a Route Discovery attempt -such as the non-propagating Route Request or the expanding ring search. In our implementation, the TTL value is decremented as the packet is forwarded, and the message is discarded if its value reaches zero before being received by the target.

 An important aspect to be highlighted is that in our implementation the Request Packet lacks of the identification field originally defined by the protocol authors. This identification is a unique value originated by the initiator of the Route Request, for example making use of a counter that automatically increments its value after a new request is transmitted. Without this field, an intermediate node of the network will not able to determine whether it has already previously received a copy of a Route Request from the same initiator node or not. Therefore, as a node cannot distinguish between a fresh first copy of a Route Request packet and the subsequent ones, it is not possible to develop a propagation control mechanism by which the received repeated copies of the same Route Request are discarded at the intermediate nodes. As a consequence, our version of DSR will generate in average a higher routing overhead than the original protocol specification, as several copies of the same Route Request coming from different paths will be forwarded by the intermediate nodes, thus leading in last term to an increase of the network congestion.

 The performance of DSR against other ad hoc network routing protocols has been extensively analysed in a number of detailed simulation studies [6, 7] and testbed implementations, showing a significantly better performance in terms of packet delivery ratio and routing overhead. As it has been pointed out by the protocol authors, the advantage of DSR relies mainly on two fundamental factors: on the one hand, the fact that each data packet carries the complete path description that not only indicates the sequence of nodes through which it has to be forwarded, but also makes it possible for many nodes to acquire additional information about the network topology; on the other hand, the aggressive use of the cached routes reduces the need for new Route Discoveries, thereby limiting the overhead incurred by the protocol.

  The lack of route caching in our implementation has therefore a direct influence in the behaviour of the routing process, as the nodes are not able to learn and store temporary information about reachable neighbours in the neighbour acquired either in response to a single route discovery or overhearing routing messages from other nodes. As no support for multiple possible routes to a given destination is provided, our protocol will not be able to react so quickly to routing changes. If an acquired route should fail it is necessary to start again a Route Discovery, given that the sending node does not have additional cached routes to try to the wished target node, limiting thus the reaction capacity of the original DSR specifications. Additionally, without the implementation of a route cache the routing overhead is in average higher, as it is not possible for a node with several alternative routes to a destination to avoid performing a new Route Discovery each time a route in use breaks.
\begin{table*}[t]
\begin{center}
\textbf{ Table V} Send Buffer entry fields
\end{center}
\centering
\begin{tabular}{l | l}
\hline
\textbf{Field}&\textbf{Description}\\ \hline
Destination ID &Destination node address\\ \hline
Payload&Data waiting to be sent\\ \hline
Retransmission counter&Number of initiated Route Discoveries\\ \hline
\end{tabular}
\end{table*}
 
  It is to be noted that the use of the Route Maintenance mechanism is mainly of interest if coupled with a Route Cache, as the main purpose of this procedure is to detect broken links in the network in order to determine which routes are no longer valid among the set of active paths used during the routing process by a node. Without route caching, it is of little use to implement such a mechanism, as all the routes are discovered "on the fly" whenever data has to be send between a pair of nodes. However, without the Route Maintenance our protocol is not able to determine if a recently discovered route has become a broken path, as no acknowledgements are used to provide confirmation that a link is capable of carrying data. Once a route to a given destination node is acquired after a successful Route Discovery, all the packets waiting for the corresponding route are transmitted by the initiator node, which does not have any knowledge whether the data packets have been correctly delivered.

  As mentioned in Section 2, DSR requires the use of a Send Buffer whenever a Route Discovery is initiated in order to temporarily store the data packets to be sent until a route to the corresponding destination node is discovered. The selection of a certain data structure organization for the Send Buffer does not affect either aspects of correctness or interoperability, and affects only local performance for each node. In our version of the protocol the Send Buffer was implemented as a static table with a predefined fixed number of entries. Each Send Buffer entry contains the destination node to which a route has not yet been established, the packet payload data waiting to be sent, as well as a counter that refers to the number of times a new Route Discovery has been initiated for the entry destination address. Table V provides a description of the fields in a Send Buffer entry.

  One of the main limitations of defining the Send Buffer as a static structure with a predefined limited number of entries is that there is risk of overflowing should a packet burst occur -e.g, if the upper layer requires sending a high number of packets in a short period of time to several destinations. This drawback can be especially problematic if the protocol is deployed in wireless nodes that present important restrictions in storage memory -e.g. the BTNode rev. 3.22 Bluetooth, developed by the Swiss Federal Institute, or the IDwaRF [9], released by the german company chip45 [10].

  In order to prevent the generation of additional routing overhead in the network, our version of the protocol implements a modified version of the Route Discovery so that a new ROUTE REQUEST to a given destination node is initiated only if there are no current petitions started to that same node. For that purpose our protocol implementation makes use of a Route Request Table, where each node stores information that refers to each one of the Route Discoveries that have been previously initialized in order to acquire a route through the network. The Request Table serves as a means to reduce the number of Route Request packets sent by a node to discover a route to a given target, and in last term to decrease the overall routing overhead generated by the protocol.

  Prior to starting a new Route Discovery, the Route Request Table is examined to check if there is already an entry with the same destination node address. If that is the case, it means that a Route Discovery process has already been initiated for the required destination address, and therefore the data packet can be directly stored as a new entry in the Send Buffer without beginning another route request procedure. As a consequence, our protocol implementation allows only a single active Route Discovery per destination node, being possible to have several Send Buffer entries addressed to the same destination node waiting for a single ROUTE REPLY.

  The ROUTE REQUEST retransmission counter present in each Send Buffer entry is used to limit the number of times the initiator node starts a Route Discovery for a given destination address. As it has been explained in Section 2, DSR must implement a mechanism on order to limit the rate at which new Route Discoveries are initiated for the same target node, given that it is possible that the destination node is not currently reachable. If a route is not discovered after a certain pre-established retransmission timeout -set in our protocol implementation to 3s, see Table II-, the sending node initiates a new route request procedure and increments the counter of the corresponding Send Buffer entry. The Route Discovery process will then be restarted until a ROUTE REPLY containing a sequence of hops to the destination is received or the retransmission limit is reached. If the node successfully acquires a route to the given target node before reaching the limit of Route Discovery attempts, all the entries waiting at the Send Buffer must be sent using the discovered sequence of intermediate nodes. After the transmission of the last data packet to the destination node, its corresponding entry must be deleted as well from the Route Request table. However, in case the number of Route Discovery retransmissions reaches the maximum established, all the entries that were waiting for a route to the corresponding node must be removed, not only from the Send Buffer but also from the Route Request table. Once an entry to a target node has been removed, if afterwards the node requires sending additional packets a new Route Discovery will be performed and the procedure restarted.\newline The avoidance of additional request-reply exchanges is reflected in last term in a drastic reduction of the network traffic load and node energy consumption. Furthermore, such an approach ensures a more optimized use of the shared media, preventing situations of network congestion and collisions during transmission. However, a significant drawback of restricting the number of active Route Discovery procedures to one per destination node is that the successful delivery of many data packets can be dependent on a single Route Discovery - e.g. in case a data burst takes place where a great amount of packets to the same destination are required to be sent in a short period of time. In such a situation, the transmission of the waiting data entries relies solely on the Route Discovery initiated by the first data packet. Therefore if this procedure fails it won't be possible to deliver a high number of data packets, as they will be discarded from the Send Buffer, thus having a negative impact in the packet delivery ratio.
  In conclusion, by avoiding the additional Route Request transmissions for successive data packets to the same destination, our protocol saves a great deal of routing overhead, but at the same time becomes less robust against more demanding topology scenarios. A possible enhancement that could be tested in future versions of our protocol would be to allow initiating a new Route Discovery for a given destination after a certain number of entries have been stored in the Send Buffer.This solution would lead to higher robustness, as the impact of a failure when discovering a route to a destination node is limited to a pre established maximum number of packets. Furthermore, such an approach would increase the rate at which new Route Discoveries to the same destination node are performed, but only in case a data burst to a given destination node occurs, otherwise the routing overhead generated by our protocol would remain invariant with respect to the original implementation.

  Although the DSR protocol provides support of unidirectional routes, we implemented DSR to discover only routes composed of bidirectional links by requiring that a node makes use of the reversal path over which the ROUTE REQUEST packet came in order to return all ROUTE REPLY messages from the destination to the initiator. As a consequence, if the route built up by a ROUTE REQUEST contained unidirectional links, then the corresponding ROUTE REPLY won't be able to reach the sending node, thus not being possible to learn the unidirectional link route. This approach is especially useful for MAC protocols that require bidirectional frame exchange as part of their standard, such as IEEE 802.11, where a link-layer acknowledgement - RTS/CTS/Data/Ack exchange- is returned after each unicast packet is sent as a part of the basic access method of the Distributed Coordination Function (DCF) mechanism. The use of a MAC protocol that provides feedback about the successful delivery of packets ensures that the established route is bidirectional before the sender starts using the path and at the same time saves the routing overhead produced by initiating a second Route Discovery.

  It is to be noted as well that we implemented the Route Discovery mechanism to guarantee loop-free routes by avoiding duplicate hops in the sequence of nodes. When a node receives a Route Request packet, it inspects the Route Record to check if its own address is already contained in the sequence of hops. If that is the case, it means that the request was previously been received by the same node, which already appended and forwarded the message, and therefore the packet must be discarded to avoid the occurrence of a loop.

  One of the main advantages of our approach is that it greatly simplifies the design and implementation process in many aspects, such as Route Cache entries management, best route selection procedure, route shortening, broken link detection or Route Errors' processing- while preserving the on-demand nature and source-routing behaviour of the original DSR protocol.

  Furthermore, as it has been observed by Feeney [8], although the use of the Route Cache may lead to a decrease in the number of Route Discoveries initiated in the network -and therefore to lower the overall routing overhead-, given that the standard specification does not contemplate load balancing issues, it might also happen that the network traffic concentrates only onto a reduced amount of routes. Like most on demand routing protocols, DSR tends to perform discovering a single path amidst the cloud of wireless nodes, becoming a sort of backbone in the network. This behaviour can be desirable in terms of efficiency, given that the number of active routes is reduced and the traffic is routed using the shortest path along the network. However, using the Route Cache has as a counterpart that the traffic load is concentrated in just some machines, leading to disproportionately greater battery consumption in the backbone nodes -as they have to forward more traffic- and a bottleneck effect.

  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 ad hoc routing protocol. Routes between sender and target nodes are established on demand as they are needed, without requiring the periodic transmission of packets of any kind at any layer within the network. Any changes in the communication conditions that don't affect the presently used routes do not lead to any reaction procedures in our protocol.

  In the following section, we evaluate the performance of our version of the DSR protocol under varying testbed conditions.  
