Improving TCP Performance over Mobile Ad-Hoc Networks with Out-of-Order Detection and Respon
Feng Wang Department of Computer Sciences The University of T exas at Austin wangf@cs.utexas.edu Y ongguang Zhang倒映近义词
∗HRL Laboratories,LLC Malibu,California
ABSTRACT
In a Mobile Ad Hoc Network(MANET),temporary link failures and route changes happen frequently.With the assumption that all packet loss are due to congestion, TCP performs poorly in such environment.While there has been some rearch on improving TCP performance over MANET,most of them require feedback from the network or the lower layer.In this rearch,we explore a new approach to improve TCP performance by detecting and responding to out-of-order packet delivery events,which are the results of frequent route changes.In our simulation study,this ap-proach had achieved on average50%performance improve-ment,without requiring feedback from the network or the lower layer.
Categories and Subject Descriptors
C.2.1[Computer-Communication Networks]:Network Architecture and Design—wireless communication; C.2.2 [Computer-Communication Networks]:Network Pro-tocols—routing protocols;C.4[Performance of Systems]: Performance Attributes;I.6[Computing Methodologies]: Simulation and Modeling
General Terms
Design,Measurement,Performance
Keywords
Mobile ad hoc networks,MANET,TCP,out-of-order
1.INTRODUCTION
A mobile ad-hoc network consists of a collection of“peer”mobile nodes that are capable of communicating with each ∗Dr.Zhang is also an Adjunct Assistant Professor in the Department of Computer Sciences,the University of Texas at Austin
Permission to make digital or hard copies of all or part of this work for personal or classroom u is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on thefirst page.To copy otherwi,to republish,to post on rvers or to redistribute to lists,requires prior specific permission and/or a fee.
MOBIHOC’02,June9-11,2002,EPFL Lausanne,Switzerland. Copyright2002ACM1-58113-501-7/$her without help from afixed infrastructure.The inter-connections between nodes are capable of changing on a con-tinual and arbitrary basis.Nodes within each other’s radio range communicate directly via wireless links,while tho that are far apart u other nodes as relays in a multi-hop routing fashion.
Rearch has shown that the performance of current TCP control mechanisms are inadequate in wireless networks[2]. Designed for wired networks originally,TCP assumes that network congestion has happened whenever a packet is lost. It then invokes appropriate congestion control actions such as reducing window size[10].However,wireless networks poss unignorably high link error rate and TCP often mis-interprets packet loss caud by link errors as congestion. As a result,its performance suffers in wireless networks when TCP unnecessarily invokes congestion control,causing re-duction in throughput and link utilization.
TCP performance is even wor in mobile ad-hoc net-works.In addition to all links being wireless,frequent route failures and route changes due to mobility can cau rious problems to TCP as well.First,route failures can cau packet drops at the intermediate nodes,which will be mis-interpreted as congestion loss.Second,route change can introduce frequent out-of-order delivery too,which will fur-ther confu the current TCP control mechanism.
The ideal solution for the route change problem is for the TCP to freeze its state as soon as the route breaks and re-sume as soon as a new route is found[4,9,13].However, this requires instant notification or feedback from the inter-mediate nodes to all TCP nders,and from the network layer to the transport layer.Such a feedback system can be difficult to implement and expensive to operate.
In this rearch,we explore a new way to make TCP adapt to frequent route changes without relying on feedback from the network.It is bad on TCP detecting out-of-order de-livery events and inferring route changes from the events. We call it Detection of Out-of-Order and Respon(DOOR). Our study has shown that this approach can significantly improve TCP performance over mobile ad-hoc networks. The rest of this paper is organized as follows.Some re-lated work is described in next ction.In ction3,we discuss in detail the TCP-DOOR approach.Th
en we show the simulation results and analyze the performance in c-tions4and5.The route cache problem is also addresd in ction4.Section6summarizes our work.
2.RELATED WORK
There has been much rearch ,[2,1])in im-proving TCP performance over wireless links.However, most of the propod mechanisms are designed for infra-structure-bad networks and depend on the ba stations in distinguishing the error loss from congestion loss.Since mobile ad-hoc networks do not have such infrastructure, the mechanisms cannot apply in mobile ad-hoc networks. Recently,there has also been some rearch on improv-ing TCP performance over mobile ad-hoc networks.Most of the work depend on notification or feedback from the network or a lower layer.They vary in how to obtain feed-back and how to respond accordingly.As we have explained earlier,such feedback may not be feasible or economical, but their respon techniques may be applicable to non-feedback-bad approaches.
TCP-F(TCP-Feedback)[4]relies on the network layer at intermediate hosts to detect the route failures due to the mobility of downstream neighbors along the route.A nder can be in an active state or a snooze state.In the active state,transport is controlled by the normal TCP.As soon as an intermediate
host detects a link failure,it explic-itly nds a route failure notification(RFN)packet to the nder and records this event.After receiving the RFN,the nder goes into the snooze state by stopping nding fur-ther packets and freezing the values of state variables such as retransmission timer and congestion window size.The nder remains in the snooze state until it is notified of the restoration of the route through a route reestablishment no-tification(RRN)packet from an intermediate host.Then it enters the active state again.
ELFN(Explicit Link Failure Notification)[9]is another technique bad on feedback.The objective is to provide the TCP nder with information about link and route failures so that it can avoid responding to the failures as if congestion happened.ELFN is bad upon DSR[12]routing protocol. To implement ELFN message,the route failure message of DSR was modified to carry a payload similar to the“host unreachable”ICMP message.When a TCP nder receives an ELFN,it disables its retransmission timers and enters a“stand-by”mode,which is similar to the snooze state of TCP-F.Instead of using an explicit notice to signal that a route has been reestablished,a packet is nt periodically to probe the network to e if a route has been established. Afterfinding a new route,the nder leaves the stand-by mode,restores its retransmission timers and continues as normal.
A-TCP(Ad hoc TCP)[13]utilizes network layer feed-back too.In addition to the route failures,A-TCP al
so tries to deal with the problem of high bit error rate.The TCP nder can be put into a persist state,congestion control state or retransmit state.In their implementation,standard TCP was not modified so that the compatibility with the standard TCP/IP suite is maintained.Instead,a thin layer called ATCP is inrted between TCP and IP.ATCP listens to the network state information provided by ECN(Explicit Congestion Notification)messages[7]and by ICMP“Des-tination Unreachable”messages and then puts TCP at the nder into the appropriate state.On receiving a“Desti-nation Unreachable”message,the nder enters the persist state.The TCP at the nder is frozen and no packets are nt until a new route is found,so the nder does not invoke congestion control.The ECN is ud as a mechanism to ex-plicitly notify the nder the network congestion along the route being ud.On receipt of an ECN,congestion control is invoked without waiting for a timeout event.If a packet loss happens and the ECNflag is not t,ATCP assumes the loss is due to bit errors and simply retransmits the lost packet.
Thefixed RTO[6]technique does not rely on the feed-back from lower layers.In fact,a heuristic was employed to distinguish route failures and congestion.When timeouts occur concutively,the nder assumes a route failure hap-pened rather than network congestion.The unacknowledged packet is retransmitted again but the RTO is not doubled a cond time.The RTO remainsfixed until the route i
s re-established and the retransmitted packet is acknowledged. This technique complements our out-of-order detection and respon technique.
3.DETECTION OF OUT-OF-ORDER AND
RESPONSE(DOOR)
In this rearch,we explore a new approach to improve the performance of TCP over mobile ad-hoc networks.It is bad on the obrvation that the property of orderly deliv-ery of TCP packets is frequently violated in mobile ad-hoc network.
3.1Out-of-Order Delivery
In an ideal TCP ssion,the packets nt by one end should arrive at the other end in quence and in order. However,there are two cas in which this ideal order can be violated.One ca is retransmissions due to packet loss –a previously transmitted quence number has to be re-peated later.We call this an Out-of-Sequence event.The other ca is Out-of-Order(OOO).It happens when a packet nt earlier arrives later than a subquent packet.
Figure1:A Possible Ca of Route Change OOO often implies route changes in the network.Con-sider two hosts communicating over afixed route in the net-work.Assuming the FIFO queues are ud at every node, all packets should be received in the same order as they are nt.However,if the route changes during the communica-tion ssion so that a later packet P2takes a different path than an earlier packet P1(e Fig.1),and if the new route taken by P2is“faster”or“shorter”than the on
e taken by P1,P2can arrive before P1,therefore OOO delivery can happen.
While we have largely ignored the route change events in a wired network becau they are such an infrequent event,we can no longer do so with mobile ad-hoc networks.In mobile ad-hoc networks,route changes can happen frequently and multiple times during a TCP ssion,especially in a highly dynamic environment.Ignoring OOO delivery can have -rious performance implication in mobile ad-hoc networks. Packet loss caud by route changes are not related to
network congestion.It is therefore not advisable to invoke congestion control to slow down the nding rate.Unfortu-nately in TCP,if a data packet is delivered to the receiver three packets later than a subquent one,a triple-duplicate-ack condition will happen and the nder will halve its con-gestion window size,halve the slow start threshold,and ret the the retransmission timer(RTO).It can be wor,if the data packet is delivered so out-of-order that the nder times out when waiting for the ACK,which will result in a slow start that is more detrimental to TCP throughput.If such OOO events happen multiple times in one TCP ssion,the TCP throughput can become deteriorated.
By detecting the OOO events and responding appropri-ately,we can improve the throughput.Although an OOO delivery may not directly result in triple duplicate ACKs or timeout,the s
ender still can learn about the current net-work state of route changes,and possible performance im-provement action can be taken to avoid unnecessary TCP slowdown.
3.2Detecting Out-of-Order Events
In a TCP ssion,OOO can happen in either direction. Both streams of data packets and ACK packets can be de-livered out of order.Accordingly,OOO detection should be carried out by both ends:nder detecting Out-of-Order ACK packets and receiver detecting Out-of-Order data pack-ets.
3.2.1Sender Detecting Out-of-Order ACK Packets
(D1)
Every TCP ACK packet carries a quence number indi-cating the highest data gment number that the receiver has received concutively so far.Since there are no re-transmissions of an ACK packet(duplicate ACK is not a retransmission),the quence number of an ACK nt later is impossible to be less than any ACK nt earlier.This non-decreasing property of ACK quence numbers makes it sim-ple for the nder to detect OOO delivery of non-duplicate ACK packets:whenever the nder receives an ACK packet, it can compare the quence number it carri
es with the one in the previous ACK,and if the current quence number is smaller,the nder can surely declare OOO.
Detecting OOO delivery of duplicate ACK packets re-quires additional ordering information,becau otherwi two duplicate ACK packets would have the identical content. To achieve this,we propo to add to the TCP ACK header a one-byte TCP option,called ACK duplication quence number(ADSN).When TCP receiver ndsfirst ACK packet for a data gment,the ADSN option is t to zero.When-ever it nds out a duplicate ACK for the same quence number,it increments the ADSN number.Under the ex-tremely rare condition that ADSN ever reaches256,it will be wrapped back to zero.This way,each duplicate ACK will carry a different ADSNfield and the TCP nder can compare thisfield to detect an OOO delivery.
3.2.2Receiver Detecting Out-of-Order Data Packets
(D2)
The method of comparing quence numbers does not ap-ply to detecting OOO data packets,becau TCP retrans-mission can cau a data packet with lower quence number to arrive after one with higher quence number.To reliably detect OOO data packets,we must include
strict ordering information in the TCP data packet.One way to achieve this is to add to the TCP header a two-byte TCP option, called TCP packet quence number(TPSN).Starting from zero,and incremented with every data packet nt(includ-ing retransmissions),this TPSN records the exact order of the data packet stream.This is different from the normal TCP quence number becau the latter refers only to the data gment stream–a retransmitted packet always carries the old data gment quence number.Similar to TCP -quence number wrapping,TPSN wraps around216as well. With TPSN option,the TCP receiver can detect OOO reli-ably.
Another method that can facilitate OOO detection with-out needing a new TCP option is the u of TCP timestamp option[11].When this option is ud,the TCP nder records the preci time each packet is nt in the TCP packet header.Since TCP timestamp option is already ud in many TCP algorithms that operate onfine-grain timers,when it is available,the TCP receiver can compare the timestamp in each packet with the previous one to detect OOO.
3.3Responding to Out-of-Order Events
When OOO events are detected,TCP can respond accord-ingly to avoid the type of performance problems described earlier.Since TCP nder bears the burden of congestion control,the OOO respo
n actions should mainly take place at the nder.Therefore,if TCP receiver detects OOO,it should notify the nder,for example,by tting an OOO-bit in the TCP ACK packet.Once the TCP nder receives such notification,or it detects OOO directly from the ACK stream,it can take the following two respon actions:tem-porarily disabling congestion control and instant recovery during congestion avoidance.
3.3.1Temporarily Disabling Congestion Control(R1) Since we have mentioned that OOO is likely caud by route changes and not by congestion,one way to avoid the undesired congestion control effects is for the TCP nder to temporarily disable congestion control action whenever an OOO condition is detected.That is,for a time period T1after detecting an OOO,TCP nder will keep its state variables constant,such as the retransmission timer(RTO) and the congestion window size.Setting the length for this disabled period is a tradeoff.
3.3.2Instant Recovery during Congestion Avoidance
(R2)
The detection of OOO condition implies that a route change event has just happened.Therefore,if during the past time period T2the TCP nder has suffered from“congestion symptoms”(such as gro
ss timeout or three duplicate ACKs) and entered the congestion avoidance state(such as halving its window size),it should recover immediately to the state before such congestion avoidance action was invoked.(A similar idea wasfirst suggested by Sally Floyd[8].)The ra-tional for this is the following.If the congestion indication event was a gross timeout,it was likely caud by the tem-porary disruption during some route change.The fact that the TCP nder has begun receiving ACK means that the disruption was over and the TCP should quickly resume the pre-route-change state,without going through slow start or linear window recovery.Similarly,if congestion avoidance
was triggered by a three-duplicate-ACK event,the dupli-cate ACKs were likely caud by OOO deliveries or tem-porary route disruption and not by congestion loss.And likewi,this condition would have pasd and TCP should resume its previous state.
4.SIMULATION ENVIRONMENT AND
METHODS
We have implemented our detection and respon mech-anisms and conducted simulations to evaluate their perfor-mance.The purpo is,first,to validate the hypothesis that we can improve the performance by detecting and re-sponding to OOO events,and cond,to determine the best combin
ations and parameters for the mechanisms.
The simulation study was in ns2network simulator[3] (version ns2.1b7a).It included the CMU wireless network extension[5]that implemented a t of ad hoc routing proto-cols(DSR[12],AODV[15],etc.)an802.11MAC layer,and a wireless channel model with a250m transmission range. We have implemented our TCP-DOOR mechanisms as a derivative of the TCP-SACK class(TCP with lective ACK option[14]).Our implementation included both nder de-tection(D1)and receiver detection(D2),and both respon actions,temporarily disabling congestion control(R1)and instantly recovering from congestion avoidance(R2).As the ba of comparison,we ud the standard TCP-SACK as implemented in ns2.
4.1Simulation Configurations and Parame-
ters
To evaluate different ttings for TCP-DOOR,we cho the followingfive configurations for D1,D2,R1,R2:•All:detect OOO with both D1and D2,and take both reactions R1and R2.
•SD:activate nder detection ,no D2),but take both reactions R1and R2.
海的女儿故事
•RD:activate receiver detection ,no D1),but take both reactions R1and R2.
•TD:detect with both D1and D2,but respond with temporary disablement ,no R2).
•IR:detect with both D1and D2,but respond with instant recovery ,no R1).
In addition,we varied the congestion control disabling pe-riod T1to be1,2,4,or8times RTT(retransmission timer), and varied the instant recovery period T2to be1,2,4,or 8times RTT.Note that the RTT value was notfixed;it was dynamically derived from the corresponding ns2vari-able(t rtxcur)at the time when OOO condition was de-tected.Also note that not every combinations made n, for example,T2was irrelevant to TD and T1irrelevant to IR.In summary,we had a total of56different tting com-binations for our TCP-DOOR mechanisms.
The ad-hoc network model ud in this study was a t of20nodes confined to a1000m×750m rectangular area. The nodes moved freely according to the random way-point mobility pattern.A zero pau time was chon to make the nodes move all the time.The moving speed of each node was randomly t between zero and10m/s.The underlying ad-hoc routing protocol was DSR.We varied DSR mode by turning route cache on or off(e the subction below). The work load is a single TCP connection between a spe-cific nder S(node0)and a specific receiver R(node1).An FTPfile tra
nsfer from S to R was conducted over this con-nection for200conds.We measured the goodput of this TCPflow achieved over the200conds.The higher the goodput,the better performance had TCP achieved.For each TCP-DOOR tting,we divided this goodput value by the goodput measured in the“ba TCP”(standard TCP-SACK)ca.
This ratio was the improvement indicator we ek–it measured how much improvement we achieved with TCP-DOOR and its tting(under a given ad-hoc scenario).We repeated the measurement100times over100randomly gen-erated node-mobility scenarios(using the tdest utility in ns2).The results reported later in this paper were bad on the average of the100scenarios.
Finally,we also varied network condition between non-congested and congested cas.For the non-congested con-dition,the single TCP connection described above was the only traffic in this network(besides ad-hoc routing control messages).For the congested condition,this single TCP connection was joined by10CBRflows(2KBps each)that were established among10random pairs of nodes to induce background/cross traffic and congested conditions.
4.2The Inequality Problem with DSR Route
Cache
To achieve a fair comparison under the same ad-hoc net-work scenario,the route lengths/delays should be similar at the same time for different TCP variants.That is,if the route from S to R at time t is three hops under TCP-DOOR but four hops under ba TCP,the performance re-sults would be incomparable.Unfortunately,we found that a feature in DSR called route cache often produced different routes for different TCP variants,even under the same sce-nario.This inequality can significantly affect the fairness in comparison between our TCP-DOOR mechanisms and the ba TCP.
Route cache is often ud in DSR to improve routing per-formance.In DSR,each ad-hoc node can maintain a cache that stores all the routes the node has known and not been invalidated by route error messages yet.Whenever a node needs to nd/forward a packet,itfirst checks its route cache tofind an existing route it has learned before.If the cache hits,it simply us the route without starting a route request.If multiple routes to the specific destination are stored in the cache,it lects the shortest one.The u of the route cache can improve the performance of routing protocols,becau it avoids the high overhead of route dis-covery for every packet even though stale routes can cau performance penalty by forwarding packets to wrong direc-tions.
With route cache,it is possible that,even at the exact same time,S will choo different routes to R if
different TCP variant is ud.This is the result of different TCP algorithms generating different time quences for the out-going packet stream.For example,under TCP1,S may nd one packet at time t1and another one at a later time t2,but under TCP2,S may not nd any packet at t1and only nd one packet at t2.Let’s assume that at t1there is only one route from S to R and it takes4hops,while later at t2there
is another route from S to R that takes 2hops only but the 4-hop route is still valid.Let us further assume that at t 1the route cache for S is empty.So in the ca of TCP1,S will do a route discovery at t 1and find the 4-hop route.The route will be put in cache.At t 2,S will continue to u the valid 4-hop route.However in the ca of TCP2,S will only do a route discovery at t 2and will find the 2-hop route instead.The routes for S are hence different at t 2between the two cas.Since different TCP congestion control al-gorithms will certainly nd TCP gments at different time quences,the route cache make it almost impossible to gen-erate identical route lection.
To ensure fair comparison,we wanted to eliminate this random affect.A simple way was to turn offthe route cache completely.We did this in ns2by disabling all the findRoute()routines that are called to arch routes in the route cache.We called this the DSR-Cache-offmode.Un-der this mode,every time a node nds/forwards a packet,it has to broadcast a new route request to find a valid route.Th
e first route replied will be lected.The advantage is that the routes lected are always the same.Hence,as long as the mobility scenario is the same,the effect of DSR on TCP performance should remain the same no matter which TCP variant is ud.As a comparison,we also repeated the experiments with the original DSR tting,by which we refer as the DSR-Cache-on mode.
5.PERFORMANCE ANALYSIS
As we have predicted earlier,TCP-DOOR can improve the TCP performance by avoiding the unnecessary conges-tion avoidance actions (such as window-size-halving)taken by “ba TCP”.The results from our simulation study have validated this hypothesis.Figure 2illustrates an example ca on how TCP-DOOR out-performs TCP (under a par-ticular scenario and tup).
500
1000
1500
2000
2500
烤金针菇
怎么退出省电模式30003500
4000
020406080100120140160180200
T C P r e c e i v e s e q u e n c e n u m b e r微拍秒拍
Time (cond)
TCP-DOOR
TCP
Figure 2:An example of TCP-DOOR out-performs TCP
As explained in the last ction,we compared the perfor-mance of TCP-DOOR with “ba TCP”under the following four experiments:DSR-Cache-offwith non-congested condi-tion,DSR-Cache-offwith congested condition,DSR-Cache-on with non-congested condition,and DSR-Cache-on with congested condition.The DSR-Cache-offexperiments had the route cache turned offfor fairness and were the focus of
our study.The DSR-Cache-on experiments were for com-parison only.In each experiment,we ran the 56different TCP-DOOR ttings and compared the performance with the “ba TCP”tting.We now report results in terms of the performance improvement ratio:the average and stan-dard deviation over 100different mobility scenarios.
Fig.3illustrates the results from the two DSR-Cache-offexperiments.In each experiment,the first 5charts dis-play respectively the results from the five different simu-lation configurations (plea refer to Section 4.1):All ,SD (nder-detection only),RD (receiver-detection only),TD (temporarily disabling only),and IR (instant recovery only).The charts are 3-D graphs that show the mean improvement ratio (%),and the x-and y-axes are T 1(congestion-control disable period)and T 2(temporary recovery period)respec-tively.Finally,the last chart of each figure tabulates the statistical data in numeric forms,including both mean and standard deviation values.
5.1TCP Performance Improvement Ratio
描写外貌的成语
The performance improvement ratio depicts that how much higher goodput that subject TCP flow had achieved under the new TCP tting,compared with the “ba TCP”.This improvement is contributed to the new TCP-DOOR mech-anisms,and the ratio value reveals the effectiveness of the mechanisms.
We first look at the All ,SD ,and RD charts where we had both OOO-respons mechanisms in place.The data show that the mean improvement ratios were between 45%to 57%.That is,on average,the performance of a TCP flow can be improved by approximately one-half when we temporary disable the (unnecessary)congestion avoidance actions and/or instantly recover from them whenever we de-tect OOO conditions.This result is rather positive.A study of the packet traces generated by ns2has revealed that there were many retransmissions and even timeout events incur-ring congestion control in “ba TCP”,but they were unnec-essary and many of them had been avoided in TCP-DOOR.If we look at the standard deviation numbers of the DSR-Cache-offwith uncongested condition ca (the last chart in Fig.3(a)),we can e that the standard deviation in every data item is very clo to half of the corresponding mean value.Hence,we can say with high confidence that our results have positively validated our TCP-DOOR approach.In fact,if we count the actual improvement ratio samples that were negative,we got under 2%(e Table 1).That is,over 98%of the time,the TCP-DOOR had improved the performance of TCP flows when the network is uncongested.The standard deviation numbers in the congested condi-tion ca (the last chart in Fig.3(b))were slightly wor –about twice as big as the uncongested ca.Still,for most of the ttings we had over 91%positive sample rate (e Table 1).That is,the TCP-DOOR had improved the per-formance over 91%of the time.
5.2Sender Detection vs Receiver Detection
From the All ,SD ,and RD charts we can e that there was no significant difference among the three configurations.This suggests that either nder-detection or receiver-detection of OOO conditions was sufficient.That is,whenever TCP data packets were OOO,it is likely that TCP ACK pack-ets were OOO as well,and vice versa.Therefore,it may not be necessary to have both nder and receiver detect-
condition
(a)DSR-Cache-offwith Uncongested
站长博客
依法行政的意义
(b)DSR-Cache-offwith Congested condition
Figure3:Simulation Results(DSR-Cache-offExperiments)
