WIXLIB

routing table is used to store the node from which a querymessage has been received as next hop on the reverse path.Thus, a node is able to return responses to the enquiring nodewithout explicit route discovery. The file routing table is a datastructure that stores alternative next hops for file transfersbased on the file identifier. ORION updates both the responserouting table and the file routing table during query processing.The memory consumption for both routing tables is controlledby limiting the maximum size and applying the Least RecentlyUsed (LRU) replacement policy.message to node A. Because node B has already forwardedresponses for files 2 and 3, the new RESPONSE message onlycontains the identifier of file 4 (see Figure 4). Note that node Bnot only stores node C as next hop for file 3, but also node D,adding redundancy to the file routing table without additionaltransmission cost. After the query phase, node A may choseone of the four matching documents for download.For the query phase, ORION defines two types ofmessages. A QUERY message contains a query string, whichconsists of one or more keywords. A message of typeRESPONSE contains unique identifiers of one or more filesmatching a query. To enable controlled message forwarding,each ORION message contains a field SRC, representing theunique identifier of the mobile device that generated theoriginal message. Furthermore, a field SEQ contains asequence number unique and strictly increasing for eachmobile device. The rollover of SEQ numbers is handled as in[9]. When a mobile device relays a message as describedbelow, SRC and SEQ are preserved. Thus, storing the largestSEQ entry received from each source device can preventrelaying a message more than once.A. Basic OperationAs first building block, the ORION transfer protocolutilizes the routes given by the file and response routing tablesfor transmission of control- and data packets. Recall that thefile routing table may store several redundant paths to copies ofthe same file. Due to changing network conditions, the senderof a file might change during a file transfer. Therefore, it isessential to keep the complete control over the transfer on thereceiver side. Thus, opposed to TCP the ORION transferprotocol does not maintain an end-to-end semantic. Fortransfer, a file is split into several blocks of equal size. Sincethe maximum transfer unit of the mobile network is assumed tobe equal between all neighboring nodes, the block size can beselected such that the data blocks fit into a single packet. Thereceiver sends a DATA REQUEST message for one of theblocks along the path given by the file routing tables. Once theDATA REQUEST reaches a node storing the file in the localrepository, the node responds with a DATA REPLY message,containing the requested block of the file. This message isrouted back to the requesting node via the same path as theRESPONSE message in the query phase. After receiving theDATA REPLY message, the receiver continues with a requestfor the next block until the complete file has been transferred.A scheduling mechanism described in Section IV.C preventsORION from waiting indefinitely for lost packets.To illustrate the operation of the ORION search algorithm,we consider the four-node scenario shown in Figures 1 to 4.There, mobile nodes are shown as circles. Nodes are connectedby a line when located in each others wireless transmissionrange. The rectangles near the nodes show parts of the localrepository and the file routing table, respectively. Assume nodeA issues a query matching files 1, 2, 3 and 4 (Figure 1). TheQUERY message is distributed by link-layer flooding, i.e.,application data is piggybacked on a link-layer broadcastmessage. This technique is borrowed from the simple multicastand broadcast protocol for MANET. On its way through thenetwork the QUERY message sets up reverse paths to node Ain the response routing tables of all intermediate nodes. Thistechnique is borrowed from the route discovery process inAODV, in which the flooded route request message sets up thereverse route for the route reply message.After searching the local repository, node B sends aRESPONSE message containing the identifiers of files 1 and 2to the next hop in node A’s direction, i.e., directly to node A(see Figure 2). Additionally, node C sends a RESPONSEmessage with the identifiers of files 1, 2, and 3 in node A’sdirection, i.e., to node B. Before forwarding the message tonode A, node B examines the contained result. File 3 is so farunknown to node B. Therefore, node C is stored as feasiblenext hop for this file in the file routing table. Node C is notstored as next hop for files 1 and 2, because node B stores thesefiles itself. Therefore, node B will never request any of thesetwo files from node C. Instead of relaying the completeRESPONSE message to node A, node B sends a reducedRESPONSE message to node A containing only the new fileidentifiers (see Figure 3). Similar to node C, node D answersthe query with the identifiers of matching local files with aRESPONSE message to the next hop in the direction to nodeA, i.e., to node B. As before, node B stores node D’s files inthe file routing table and sends an own additional RESPONSE0-7803-7954-3/03/ 17.00 2003 IEEE.IV.THE ORION TRANSFER PROTOCOLTo illustrate the operation of the file transfer mechanism,suppose node A in Figure 4 decides to download the file withthe file identifier 3. The DATA REQUEST message for thefirst part of the file is sent to the next hop in direction to thenode storing file 3, i.e., node B. Node B cannot deliver the fileitself, so it relays the request to the best-suited next hoptowards a node storing file 3. From node B’s point of view,node C is best suited, because in the query phase node C hasresponded first to the query message. Node C stores a copy offile 3 and, thus, sends a DATA REPLY message containingthe requested part of file 3 to the next hop in direction to nodeA as identified by the response routing table. Node B relays theDATA REPLY message to node A. Subsequently, node Asends a DATA REQUEST for the next block of file 3. Thisprocess continues until the complete file has been transferred tonode A. In this (ideal) scenario, the file transfer implicitly usesthe optimal route without any overhead for retransmissions dueto route failures.B. Maintenance of File Transfer RoutesORION transfers control and data packets on the bestsuited route chosen from a set of redundant routes. Selecting analternative route provides an efficient mechanism to locallyresolve link failures. Consider again the example in Figure 4.2760Authorized licensed use limited to: IEEE Xplore. Downloaded on February 9, 2009 at 01:26 from IEEE Xplore. Restrictions apply.

and loss-recovery mechanism as third building block. In theremainder of this paper, we demonstrate the generalapplicability of the file transfer protocol and do not elaborateon performance and fairness optimization using sophisticatedflow control and congestion avoidance as for example providedby the transmission control protocol, TCP [2]. Recall that TCPtries to transmit data packets with a small delay jitter as acontinuous stream. In a file sharing application, it does notmatter in which order the blocks of a file are received, as longas each block is received at least once. Therefore, ORIONmaintains a list of pending blocks, which is initialized with allblocks of a particular file. The blocks are requested in a roundrobin fashion, until they are successfully transmitted. Todetermine the minimal request rate, the receiver keeps track ofthe average round trip time, i.e., the time elapsed betweensending a DATA REQUEST and receiving the correspondingDATA REPLY. The time between two successive requests isequal to the average round trip time, unless a DATA REPLYis received before. That is, if a packet is lost or delayed, thenext packet will be requested at most one round trip time later.Due to the round-robin selection of blocks, the ORION transferprotocol re-requests a lost or delayed block after all otherpending blocks have been requested. Therefore, a delayedblock will reach the receiver with high probability before it isrequested a second time.Suppose the link between node B and node C fails during thefile transfer, e.g., because node C moves out of node B’stransmission range. As soon as B recognizes the link failure, itdeletes node B in its routing tables and forwards subsequentDATA REQUEST messages to the now best-suited next hopto a node possessing file 3, i.e. node D. Thus, the link failurecan locally be resolved by node B without involving othernodes. Note that opposed to ORION, reactive MANET routingprotocols as AODV and DSR recover from link failure byinitiating a global route discovery, i.e., they will use globalfailure recovery. We will show in Section V.C that local failurerecovery outperforms global recovery in terms of transmissionoverhead for a P2P file sharing application.The timely recognition of link failures is necessary to avoiddelays and unnecessary data transmissions. ORION usesfeedback from the link layer as the second building block foran efficient file transfer. Feedback can be provided by linklayer notification if available, e.g., as in IEEE 802.11.Otherwise, packet receipt must be acknowledged by sendingexplicit application layer packets. In the case of a send failureon the link layer, the ORION application is notified and canimmediately chose an alternative next hop as described above.As a further feature, the route maintenance algorithmutilizes ROUTE ERROR messages. These ROUTE ERRORmessages indicate that a node could not forward aDATA REQUEST message, because there are no next hopentries for the requested file left in its file routing table. Toillustrate the usage of ROUTE ERROR messages, we referagain to Figure 4. Suppose that node B looses the link layerconnections to both node C and node D and receives furtherDATA REQUEST messages from node A. In that case, nodeB sends a ROUTE ERROR message for file 3 to node A.Subsequently, node A deletes node B as next hop for file 3 inits files routing table. If node A’s file routing table containsanother next hop for file 3, subsequent DATA REQUESTs aresent to this node. Otherwise node A can either cancel the filetransfer or start a special search phase called re-query. Opposedto an ordinary query, a re-query does not search for keywords,but for a file identifier. The messages transmitted during a requery are equal to the messages during an ordinary query, thusupdating the routing tables for the specific file.V.A. Simulation EnvironmentIn this section, we compare the performance of both theORION search algorithm and the ORION transfer protocolwith an off-the-shelf approach using a P2P system for thewired internet, TCP and a MANET routing protocol.Performance results were obtained using the NetworkSimulator ns-2 [3]. We used an IEEE 802.11 standard MAClayer [4], and a standard physical layer using two-ray groundpropagation as radio propagation model. With a transmissionpower of 17.6125 mW, the simulated mobile nodes provide atransmission range of approximately 115m.We assume that N Nodes mobile devices move in an area of1000 m 1000 m according to the random waypoint mobilitymodel, which is commonly used to model the movement ofindividual pedestrians. The speed of the device is chosenuniformly at random from [ 0, smax ] . When a device reaches arandomly chosen destination, it pauses for a fixed amount oftime Thold , before it continues to move to the next destination.C. Packet Scheduling and Loss RecoveryRecall that the ORION transfer protocol as described inSection IV.A will not continue a file transfer, if aDATA REQUEST or DATA REPLY message is lost. Thus,the ORION transfer protocol incorporates a packet schedulingParameterValueTransmission RangeNumber of NodesN Nodes401000 m 1000 mSimulation AreaMaximum Speed115 msmax2 m/sTholdTCP Timeout TTCPRest Time0-7803-7954-3/03/ 17.00 2003 IEEE.50 s60 sTransmitted Volume (MB)0.5DEFAULT PARAMETERS.Fraction of ResponsesTABLE I.Off-the-ShelfORION0.40.30.20.100PERFORMANCE RESULTS2040Number Of NodesFigure 5. Search accuracy vs. 2040Number of NodesFigure 6. Protocol overhead vs. size2761Authorized licensed use limited to: IEEE Xplore. Downloaded on February 9, 2009 at 01:26 from IEEE Xplore. Restrictions apply.60

If not stated otherwise, all fixed parameters are set according toTable 1. We calculated 99% confidence intervals for thesimulation results and indicate them as bars for each data pointin a performance curve.B. Search PerformanceTo illustrate the effectiveness of ORION’s searchalgorithm, we compare its performance with an off-the-shelfapproach utilizing a P2P system for the wireline Internet, TCP,and a state-of-the-art MANET routing protocol. Since almostall known P2P file sharing systems use static connections tobuild an overlay network we consider Gnutella [7] as examplefor such P2P systems. For the off-the-shelf approach, weemploy TCP-SACK as transport layer protocol on top of theMANET routing protocol Dynamic Source Routing (DSR, [5]).We label corresponding curves as ORION and Off-the-Shelf,respectively.An important performance measure from the user’s point ofview is the quality of the results received in response to a sentquery. Therefore, we consider search accuracy, i.e., the fractionof received unique files in relation to the number of all filesmatching a query. In Figure 5, we plot search accuracy as afunction of number of nodes participating in the mobile filesharing application. We find that search accuracy for bothapplications increase with the number of nodes. This is clearlydue to the increasing connectivity. However, the off-the-shelfapproach has searching performance worse than ORION andalso shows decreasing search accuracy for more than 40 mobilenodes.To evaluate the overhead generated by both approaches, weinvestigate the accumulated volume of transmitted messagesfor an increasing number of nodes. Figure 6 shows, thatORION outperforms the off-the-shelf approach by more thanone order of magnitude for a MANET with a large number ofnodes. we conclude that P2P file sharing systems based on astatic application-layer connections are not applicable even forenvironments with few nodes, while ORION easily scales tolarge scenarios.Figure 7 gives insight in the composition of messagescontributing to the overall message volume generated by bothapproaches. Message volume in the off-the-shelf approach isdominated by control traffic from MAC, routing and transportlayers. Only 5% of the overall traffic is used for exchange ofquery and response messages (payload), which should be themain purpose of the search algorithm in a P2P application. Incontrast, the fraction of this type of traffic exceeds 79% of thetotal message volume for ORION. Since the amount of payloadis similar in both approaches, this experiment clearly shows25020010027.5One of the most important performance measures for dataintensive applications running on mobile devices is thetransmitted data volume, due to scarce bandwidth and energyresources. In a P2P file sharing application, a trivial lowerbound for the volume generated by a file transfer is the size ofthe file. This bound holds under the assumption that ure 7. Breakdown to message types0-7803-7954-3/03/ 17.00 2003 IEEE.150100Off-the-ShelfORION50000Off-the-ShelfIn a P2P file sharing system, an important feature forachieving user satisfaction is the number of successful filetransfers. We analyze this performance measure in Figure 8.For the off-the-shelf approach, a download is considered as“failed”, if none of the nodes responding to the original queryremains reachable. In the case of ORION, a download isconsidered as “failed” when the inquiring node runs out ofalternative paths after a single re-query. Note that ORION isable to implicitly discover file holders that are unreachablewhen issuing the original query. Figure 8 shows that due to lowconnectivity in systems with a low number of nodes, bothapproaches are able to complete only a small number of filetransfers. For a growing number of nodes, ORION is able tocomplete up to 40% more transfers, based on the file-orientedre-query process. We conclude that ORION can provide highuser satisfaction by completing a large fraction of file transfers.80MAC & otherConnection ControlPayload15050C. Transfer PerformanceFor evaluating the performance of the ORION transferprotocol, we compare it with an off-the-shelf file transferapproach using TCP as transport layer protocol on top of DSRand AODV, respectively. We found that TCP throughput isroughly the same for DSR and AODV. Therefore, in thissection we present the performance results for TCP with DSRand omit corresponding results for AODV. We refer to theconsidered transfer protocols as ORION and Off-the-Shelf,respectively. For each point in the performance curves, weperformed 20,000 queries and successive file transfers. Eachtransferred file has a size of 3 MB, reflecting the average sizeof an MP3 file. The degree of replication is 0.1 in allexperiments, i.e., 10% of the participating nodes store copies ofa given document.Overhead (%)643.1Successful Transfers (%)Message Volume (MB)300that the main deficiency of the off-the-shelf approach is not theinefficient query mechanism but the overhead of maintainingstatic overlay connections. Therefore we argue that the resultsobtained with the off-the-shelf-approach are also valid for anyP2P file sharing systems using static overlay connections, notonly for Gnutella. We conclude from Figure 7 that the off-theshelf approach fails to make efficient use of networkbandwidth, while ORION utilizes network resourceseffectively.2040Number of Nodes60Figure 8. Successful transfers vs. size02040Number of NodesFigure 9. Overhead vs. size2762Authorized licensed use limited to: IEEE Xplore. Downloaded on February 9, 2009 at 01:26 from IEEE Xplore. Restrictions apply.60

network route used for the transfer spans only a single hop andthat there is no overhead for packet headers, flow control andpacket retransmissions. However, the transmission mightexperience significant overhead due to network routesspanning more than one hop as well as due to retransmissionsof lost or delayed packets.We investigate the average overhead for a successful filetransmission in percent of the total file size of 3 MB. Figure 9plots the overhead as a function of the number of nodes. Forfew nodes, in most cases files are transferred between directneighboring nodes. In this case, most overhead is controloverhead. We find that the off-the-shelf approach transmitsmore than twice the file size over the wireless medium. Asshown by an analysis of the ns-2 trace files, the main reason forthis are retransmissions of packets delayed by the routemaintenance of DSR, as well as longer transfer routes. Routelength increases if a direct connection between the sending andreceiving node fails, while a longer route via an intermediatenode exists. Recall that in this case, DSR will recover fromroute failure globally, using the longer route. The schedulingalgorithm of ORION reduces the amount of retransmissions ofdelayed packets. Furthermore, in case of route failure, ORIONwill resume the transmission from another nearby node usingthe file routing table. These features lead to a total overheadbelow 50% for few nodes. For a growing number of nodes,overhead increases for both the off-the-shelf approach andORION, as the average length of a network route increases.However, ORION stays superior to the off-the-shelf for thesame reasons. From Figure 9 we conclude that ORIONprovides a file transfer mechanism that is highly efficient inbandwidth usage.In further experiments, we compared the throughput of theORION transfer protocol to the off-the-shelf approach. Theexperiments show that the throughput is comparable for bothapproaches. Note that a congestion control mechanism for theORION transfer protocol is subject to future work, thus we didnot consider cross traffic in our experiments. Due to spacelimitations, we do not discuss the results in detail.VI.CONCLUSIONIn this paper, we presented the Optimized RoutingIndependent Overlay Network (ORION), a special-purposeapproach for P2P file sharing tailored to

P2P file sharing tailored to MANET denoted Optimized Routing Independent Overlay Network (ORION). ORION comprises of an algorithm for construction and maintenance of an application-layer overlay network that enables routing of all types of messages required to operate a P2P file sharing system, i.e., queries, responses, and file transmissions.