Enhancing TCP Fairness in Ad Hoc Wireless Networks Using Neighborhood RED
B.OBUIRAJ
ABSTRACT Significant TCP unfairness in ad hoc wireless networks has been reported during the past several years. This unfair- ness results from the nature of the shared wireless medium and location dependency. If we view a node and its in- terfering nodes to form a “neighborhood”, the aggregate of local queues at these nodes represents the distributed queue for this neighborhood. However, this queue is not a FIFO queue. Flows sharing the queue have different, dynamically changing priorities determined by the topology and traf- fic patterns. Thus, they get different feedback in terms of packet loss rate and packet delay when congestion occurs. In wired networks, the Randomly Early Detection (RED) scheme was found to improve TCP fairness. In this paper, we show that the RED scheme does not work when running on individual queues in wireless nodes. We then propose a Neighborhood RED (NRED) scheme, which extends the RED concept to the distributed neighborhood queue. Sim- ulation studies confirm that the NRED scheme can improve TCP unfairness substantially in ad hoc networks. More- over, the NRED scheme acts at the network level, without MAC protocol modifications. This considerably simplifies its deployment.
Categories and Subject Descriptors C.2.0 [Computer-Communication Networks]: General— data communications
General Terms Algorithms, Design ∗This work was supported in part by Office of Naval Research (ONR) ”MINUTEMAN” project under contract N00014-01-C-0016 and TRW under a Graduate Student Fel- lowship. †This research was supported in part by the National Nat- ural Science Foundation of China (NSFC) under grant No. 90104015.
Permission to make digital or hard copies of all or part of this work for personal or classroom use 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 the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. MobiCom’03, September 14–19, 2003, San Diego, California, USA. Copyright 2003 ACM 1-58113-753-2/03/0009…$5.00.
Keywords TCP Fairness, Ad Hoc Network, Neighborhood RED, NRED
1. INTRODUCTION In this paper we address TCP performance within a mul- tihop wireless ad hoc network. This has been an area of active research recently, and progress has been reported in several directions. Three different types of challenges are posed to TCP design by such networks. First, as the topol- ogy changes, the path is interrupted and TCP goes into re- peated, exponentially increasing time-outs with severe per- formance impact. Efficient retransmission strategies have been proposed to overcome such problems [4, 5, 9]. The second problem has to do with the fact that TCP perfor- mance in ad hoc multihop environment depends critically on the congestion window in use. If the window grows too large, there are too many packets (and ACKs) on the path, all competing for the same medium. Congestion builds up and causes “wastage” of the broadcast medium with con- sequent throughput degradation [7]. The third problem is significant TCP unfairness which has been revealed and re- ported through both simulations and testbed measurements recently [17, 18, 19]. This paper focuses on the third problem, namely, enhanc- ing TCP fairness in ad hoc networks. Previous work on this topic mostly dealt with the underlying factors causing TCP unfairness. So far, no successful attempts on TCP fairness restoration have been reported. Many specific factors have been identified as the triggers of TCP unfairness, such as: channel capture, hidden and exposed terminal conditions, and the binary exponential backoff of IEEE 802.11 MAC etc [18, 19]. Most of the factors can be traced back to the unfairness of the IEEE 802.11 MAC protocol. However, the “greedy” behavior of TCP and its poor interaction with the MAC layer further exacerbate the unfairness situation [18]. In this paper we argue that two unique features of ad hoc wireless networks are the key to understand unfair TCP be- haviors. One is the spatial reuse constraint; the other is the location dependency. The former implies that space is also a kind of shared resource. TCP flows, which do not even tra- verse common nodes, may still compete for “shared space” and thus interfere with each other. The latter, location de- pendency, triggers various problems mentioned above, which are often recognized as the primary reasons for TCP un- fairness. TCP flows with different relative positions in the bottleneck may get different perception of the bottleneck sit- uation in terms of packet delay and packet loss rate. Since
16
getting correct feedback of the bottleneck is critical to the fairness of TCP congestion control, limited information of the bottleneck situation causes significant unfairness (e.g. some flows experience more packet loss and thus tend to re- duce their congestion window more frequently than others). If we view a node and its interfering neighbors to form a neighborhood, the local queues at these nodes can be con- sidered to form a distributed queue for this neighborhood. This distributed queue is not a FIFO queue. Flows sharing this queue have different and dynamic priorities determined by the topology and traffic patterns due to channel capture, hidden and exposed terminal situations etc. Thus, they get different feedback in terms of packet loss rate and packet de- lay when congestion happens. The uneven feedback makes TCP congestion control diverge from the fair share. Similar situations may occur in wired networks when a buffer is full and drop tail queue management scheme is used. The Ran- domly Early Detection (RED) [6] scheme can improve TCP fairness under such situations by keeping the queue size rel- atively small and dropping or marking packets roughly pro- portional to the bandwidth share of each flow through the gateway. In this paper, we propose a Neighborhood RED (NRED) scheme, which extends the original RED scheme to operate on the distributed neighborhood queue. As RED does, each node keeps estimating the size of its neighborhood queue. Once the queue size exceeds a certain threshold, a drop prob- ability is computed by using the algorithm from the original RED scheme. Since a neighborhood queue is the aggregate of local queues at neighboring nodes, this drop probabil- ity is then propagated to neighboring nodes for cooperative packet drops. Each neighbor node computes its local drop probability based on its channel bandwidth usage and drops packets accordingly. The overall drop probability will realize the calculated drop probability on the whole neighborhood queue. Thus, the NRED scheme is basically a distributed RED suitable for ad hoc wireless networks. The rest of the paper is organized as follows. We briefly review previous work in section 2 and describe in short re- lated protocols as well as the simulation environment in section 3. Section 4 presents the concept of the neighbor- hood of a node and its distributed queue. We then give the detailed algorithms of the NRED scheme in section 5. Section 6 gives verification of our queue size estimation al- gorithm and guidelines for setting configurable parameters. The usefulness of NRED is also evaluated under simple but fundamental scenarios in this section. Further performance evaluations under more general scenarios are performed in section 7. Some related issues and future work are discussed in section 8 and we conclude the paper in section 9.
2. RELATED WORK Recently, several techniques have been proposed to im- prove TCP performance in ad hoc networks. Most of these techniques address mobility, link breakages and routing al- gorithm failures. Schemes such as ELFN [9], TCP-F [4], Fixed-RTO [5], and TCP-DOOR [22] belong to this cate- gory. Together, this work gives reasonable understanding on mobility related TCP inefficiencies. There is, however, another important problem area in wireless ad hoc networks, namely TCP unfairness. This area has received less atten- tion in the past, although the problem is significant. As shown in section 3, 6 and 7, substantial unfairness and even
flow starvation exists. This unfair behavior may seriously delay or even lock out a critical application. Some efforts have addressed the TCP fairness issue in ad hoc networks. In [8, 17], Tang and Gerla et al investigated TCP fairness over different MAC protocols, namely CSMA, FAMA, MACAW and IEEE 802.11. In all the investigated scenarios, IEEE 802.11 always came on top in terms of both throughput and fairness. However, even IEEE 802.11 could not achieve acceptable fairness in the ring and grid topolo- gies with TCP congestion window size allowed to grow larger than 1 packet. A simple MAC layer technique was proposed by the authors. An additional yield time was used to restrain the node that used the channel last. It shows improved fair- ness under the ring topology. In [19, 20], Xu et al investigated TCP fairness over IEEE 802.11 MAC in ad hoc wireless networks. Their work pro- vides a good understanding of the underlying reasons that trigger TCP unfairness. No remedy, however, is proposed in that work. In [18], Gerla et al investigated TCP unfairness on a path across a wired and multihop wireless network. Again, they found that the problem resides in the wireless segment. More precisely, they identified hidden and exposed terminals and the interaction of IEEE MAC and TCP con- gestion control as the key factors that prevent TCP from stabilizing at fair-share. Most of the prior work is focused on channel and MAC protocol features in an attempt to identify the factors trig- gering TCP unfairness. However, so far, no complete solu- tion to this problem has yet been reported. In this paper, we attack the problem at the network layer. We explore the relationship between TCP unfairness and early network con- gestion. RED was helpful in detecting congestion in wired networks and in enhancing fairness. We wish to extend the RED scheme into mobile multihop ad hoc networks. Such an extension is not trivial as ad hoc wireless networks have very unique features such as location dependency.
3. RELATED PROTOCOLS AND SIMULA- TION PLATFORM
3.1 Random Early Detection (RED) The proposed NRED scheme is an extension of the RED [6] scheme developed for the wired Internet. RED is an active queue management scheme for congestion avoidance. It monitors the average queue size at each buffer. Once the average queue size exceeds a predefined threshold, it will start dropping or marking packets with given proba- bility. RED has two independent algorithms. One is for computing the average queue size and the other is to cal- culate the drop probability as a function of average queue size. Suppose current queue size is q, then the average queue size is computed as avg = (1− wq) ∗ avg + wq ∗ q, where wq is called “queue weight” for smoothing the av- erage queue size and tolerating burstness. Upon a packet arrival, the drop probability is calculated according to the minimum threshold minth and maximum threshold maxth as pb = maxp(avg − minth)/(maxth − minth) andpa = pb/(1−count∗pb). Here maxp is the maximum packet drop probability and count is the number of packets arrived since last packet drop. When the average queue size is larger than maxth, the drop probability is set to 1. RED was shown to improve network performance by avoiding heavy
17
congestion, eliminating global synchronization etc. It also improves fairness by dropping packets proportional to a con- nection’s share of buffers and thus bandwidth. 3.2 Simulation Environment This paper and the evaluation of the proposed NRED scheme rely heavily on simulation experiments. Unless ex- plicitly mentioned, all the simulation experiments in this paper use the configurations described here. The simulation platform we used is the QualNet simulator [15], which is the successor of the previous GloMoSim simulation library [21]. Most configuration parameters of the protocol stack in our simulations use the default values. The channel bandwidth is 2Mbps, channel propagation model is the two-ray ground reflection model [16], transmission range is 367m. IEEE 802.11 MAC DCF is adopted. TCP NewReno is used with Maximum Segment Size set to 512 Bytes. The buffer size at each node is 66 packets. Static routing is used in most sce- narios. In most of the simulations, TCP connections start at 10s and end at 130s. The simulation time is 150s.
4. TCPUNFAIRNESSANDREDINADHOC NETWORKS
4.1 Why RED does not Work? We first tested whether the original RED scheme can help improving TCP unfairness in ad hoc networks. The simula- tion scenario is shown in Figure 1. This scenario is very sim- ilar to those scenarios used in the wired networks for testing RED scheme. However, it is a wireless specific scenario. The 3 FTP/TCP connections in Figure 1 do not share any com- mon node. However they still contend with each other for the medium. The implementation of RED used in our exper- iments follows the algorithm presented in [6]. The minimum and maximum queue size thresholds (minth and maxth) are set to 5 packets and 15 packets. The queue weight (e.g. wq) is 0.002. We vary the maximum drop probability maxp from 0.02 to 0.2. In all the simulations, we found that FTP 2 is always starved. Typical results are given in Figure 2, where the throughput of the 3 connections at the end of simulation is plotted. As a contrast, we also show the throughput when the default “drop tail” queue management scheme is used. Apparently, no visible advantage in terms of improving TCP unfairness can be found when RED is adopted. However one interesting point we observe is that RED still manages to improve the TCP throughput in ad hoc networks. Since this paper mainly focuses on TCP fairness, further discussion of this point is deferred to a follow up study. Detailed analysis of the results shows that there are 3 major factors that impede RED from improving TCP un- fairness in the ad hoc environment. First, a TCP connection which is penalized in channel contention may experience a queue buildup. However, dropping packets of the penalized flow may actually increase the unfairness. Second, conges- tion does not happen in a single node, but in an entire area involving multiple nodes. The queue at any single node can- not completely reflect the network congestion state. Third, since multiple nodes are involved in the congestion, they should coordinate their packet drops, rather than act inde- pendently. Thus, an appropriate RED scheme for ad hoc wireless networks should consider an aggregate of multiple queues in the bottleneck.
4.2 Neighborhood and Its Distributed Queue In ad hoc wireless networks, there is no pre-defined link between any two nodes. Instead, nodes, which share the same space, compete for the channel under the control of the MAC protocol. Thus, the congestion in an ad hoc network cannot be traced to a specific node, but to the entire space around it. We refer to this space as the “neighborhood” of a node. A more formal definition follows.
Neighborhood: A node’s neighborhood consists of the node itself and the nodes which can interfere with this node’s signals.
Apparently, a node’s neighborhood includes both its 1- hop neighbors and 2-hop neighbors. Interference between a node and its 1-hop neighbors is straightforward. For 2-hop neighbors, they may also interfere with the node when they are transmitting to any 1-hop neighbor since collisions may happen at the 1-hop neighbor. Thus 2-hop neighbors indi- rectly interfere with the node. If we consider the fact that interference range is usually much larger than the transmis- sion range, nodes more than 2-hops away from a node may also be involved in its neighborhood. In this paper, we sim- plify the problem by ignoring such situations. In the RED scheme, the early congestion is detected by monitoring the queue size of each outgoing buffer. Similarly, the queue size of a neighborhood reflects the degree of local network congestion. But, where is the queue of a node’s neighborhood? In the wired net, there is at least one buffer for each outgoing interface. The queue size can be measured by counting the number of packets in the buffer. However,
Outgoing Queue Incoming Queue
a node’s neighborhood includes multiple nodes each with its local queue. The neighborhood queue should account for all those packets whose transmissions will affect the channel usage within this neighborhood. We view all nodes partic- ipating in a node’s neighborhood form a distributed queue of that neighborhood with packets scattered among these nodes. The concepts of a node’s neighborhood and its dis- tributed queue are illustrated in Figure 3. In Figure 3, not all packets in the local queue of each node can be considered as packets in the neighborhood queue. Let us examine in detail which packet should be counted. Clearly, the packets in the queues of node A and its 1-hop neighbors are in the distributed queue of node A’s neigh- borhood. Packets in the queues of node A’s 2-hop neighbors may or may not be in this distributed queue. More pre- cisely, only the packets directed to a 1-hop neighbor of node A should be considered as a contribution to node A’s neigh- borhood queue size.
4.3 A Simplified Neighborhood Queue Model The distributed queue illustrated in Figure 3 has 2-hop neighbors involved. Only some packets in the queues of the 2-hop neighbors should be counted. This distributed queue model is not easy to implement and evaluate since it is difficult to get information of 2-hop neighbors without in- troducing significant communication overhead. We simplify this model to the one illustrated in Figure 4, which only in- cludes 1-hop neighbors. We move those packets in the 2-hop neighbors that are directed to a 1-hop neighbor, to the cor- responding 1-hop neighbor. Thus, now each node has two queues. One is its original queue of outgoing packets. The other one is an incoming queue that represents the packets from 2-hop neighbors. The original queue at a node is now referred to as the outgoing queue.
We treat the distributed queue of a neighborhood in an ad hoc network the same way as we would on a single link queue in the wired net and apply RED to it - after proper modifi- cations. This is the basic idea behind the proposed Neigh- borhood RED scheme. Here, we point out several unique characteristics of the distributed neighborhood queue.
(i) A neighborhood queue consists of multiple queues lo- cated at the neighboring nodes that are part of the same spatial reuse constraint set.
(ii) The distributed queue is not a FIFO queue due to loca- tion dependency. Instead, multiple sub-queues forming it have different relative priorities in terms of acquiring the wireless channel due to various factors including MAC unfairness, channel capture, hidden and exposed terminal etc.
(iii) The priority of a sub-queue may change dynamically due to topology or traffic pattern changes .
With the concepts of a node’s neighborhood and its dis- tributed queue, we can now model TCP unfairness from a transport layer view. As suggested in the previous subsec- tion, multiple TCP flows actually share a distributed queue with different but dynamic priorities. This feature will make TCP diverge from fair-share since they get different feedback in terms of packet drop rate and delay from the congested neighborhood.
5. NEIGHBORHOODRANDOMEARLYDE- TECTION Recognizing the underlying reasons why TCP cannot con- verge to the fair share, the proposed solution for reestab- lishing TCP fairness is how to feed the contending flows with the same congestion feedback from the bottleneck (e.g. packet drop probability and packet delay proportional to the share of bandwidth used by each TCP flow). Some form of TCP unfairness, although by far not as dramatic as in the multihop case, manifests itself also in the wired Inter- net when drop tail queue management scheme is used. The RED active queue management scheme solves that problem by keeping the queue size relatively small and dropping or marking packets of a flow proportionally to its buffer occu- pancy and thus bandwidth share. This has prompted us to apply a RED-like scheme to the distributed neighborhood queue, which we call Neighborhood Random Early Detec- tion (NRED). To do so, we need to solve 3 problems. 1) How to detect the early congestion of a neighborhood? More precisely, how to compute the average queue size of the dis- tributed neighborhood queue? 2) When and how does a node inform its neighbors about the congestion? 3) How do the neighbor nodes calculate their local drop probabilities so that they add up to the targeted overall drop probabil- ity? Correspondingly, three sub-schemes are then proposed, namely Neighborhood Congestion Detection (NCD), Neigh- borhood Congestion Notification (NCN), and Distributed Neighborhood Packet Drop (DNPD), which are explained in the next subsections.
5.1 Neighborhood Congestion Detection A direct way to monitor the neighborhood queue size is to let every node broadcast a control packet throughout its
19
neighborhood to announce its queue size (and destinations of queued packets) upon each packet arrival or departure. By this method, a node can count its neighborhood queue size precisely. However, in a mobile ad hoc wireless network the topology and traffic pattern may continually change. Even if there is no mobility, queue size changes are frequent. A lot of control overhead will be caused by this propagation of queue size information. It is counterproductive to monitor congestion by triggering a lot of extra traffic overhead, which actually worsens the congestion. Instead of actively advertising queue size information, we opt for a passive measurement technique. Moreover, instead of measuring queue size, we choose an alternate measure re- lated to queue size - namely, channel utilization - which is much easier to monitor than “neighborhood queue size”. Naturally, there is a relationship between channel utilization and the size of both outgoing and incoming queues. When these queues are busy, channel utilization around the node is more likely to increase. Now, the trick is to figure out how to measure and account for the various components of chan- nel utilization. To this end, let us carefully examine node A’s neighborhood queue shown in Figure 4. When a packet in any outgoing queue is transmitted, node A will detect the medium as busy. If a packet is received to any incoming queue, node A can also learn this through the CTS packet (we assume IEEE 802.11 MAC layer). These two measure- ments can derive inputs needed for NRED implementation. More precisely, a node will monitor five different radio states 1) Transmitting, 2) Receiving, 3) Carrier sensing busy, 4) Virtual carrier sensing busy (e.g. deferral to RTS, CTS etc.), and 5) Idle (i.e., no activity on the channel). These radio states can be divided into 3 categories. States 1) and 2) are the contribution of the current node to the total chan- nel utilization within its neighborhood. States 3) and 4) are the contribution of the node’s neighbors to the channel uti- lization. We will assume state 5 means empty queue. This assumption is slightly optimistic, since an idle channel state may also mean all nodes are in backoff stage. In the future, we will improve the scheme by considering more channel statistics such as the collision rate. By monitoring the five radio states, a node can now esti- mate 3 channel utilization ratios, namely total channel uti- lization ratio (Ubusy), transmitting ratio (Utx) and receiving ratio (Urx). Accordingly, a node constantly monitors the channel condition and records the time period in each of the five radio states. Let Ttx, Trx, Tcs, Tvcs and Tidle represent the time period spent at each state during last time period Tinterval. Then the three utilization ratios are defined as:
Ubusy =Tinterval −Tidle Tinterval
(1)
Utx =Ttx Tinterval
(2)
Urx =Trx Tinterval
(3)
Here, Tinterval = Ttx + Trx + Tcs + Tvcs + Tidle. Ubusy re- flects the size of the neighborhood queue. Utx and Urx re- flect the channel bandwidth usage of the outgoing queue and incoming queue at current node. Later, the local drop prob- ability will be calculated proportional to a node’s channel bandwidth usage. When the total channel utilization ratio (Ubusy) exceeds a certain threshold, we define the neighbor- hood to be in early congestion.
To facilitate the implementation of the RED algorithm, which is based on packet queue lengths rather than chan- nel utilization, we translate the channel utilization into an index of the queue size. Assume the channel bandwidth is W bps and the average packet size is C bits. We translate the Ubusy to the queue size index as q = Ubusy∗W C . The variable q is not dimensionally correct, as it is expressed in pkts/sec rather than packets as the queue length should be. However, q is an index that tracks the average queue length, and allows us to manipulate channel utilizations using the conventional RED algorithms. The average packet size C is a constant. Its actual value is irrelevant, as it is only a scal- ing factor that affects the choice of the values for minimum and maximum threshold (minth and maxth). In the rest of the paper, we may still use the term “number of packets” for ease of explanation, where we actually mean this “queue size index”. We translate the Utx and Urx into indices qtx and qrx using the same equation as Ubusy. After this transformation, we now can apply the original RED scheme. We start by computing the average queue size as avg = (1−wq)∗avg + wq ∗q. The initial value of avg is 0. Similarly, we can also get avgtx and avgrx using qtx and qrx. avgtx and avgrx are the average queue size of the outgoing queue and incoming queue (see Figure 4) at current node, which will be used in next two subsections. The estimation algorithm is independent of the other com- ponents of the NRED scheme. Unlike the original RED scheme, which samples queue size on each packet arrival, our scheme samples utilization, and thus “queue size index”, periodically. The accuracy of the estimation is controlled by the time interval Tinterval.
5.2 Neighborhood Congestion Notification Under NRED, a node checks the estimated average queue size avg periodically and compares it with a minimum thresh- old minth. If queue is larger than threshold, early congestion is detected. Then the node calculates a drop probability pb based on the average queue size and broadcasts it to its neighbors. Here, we present the algorithm for calculating pb using pseudocode. The algorithm is based on the original scheme of RED [6].
Algorithm 5.1: CalculatePb()
comment: Procedure to calculate Drop Probability pb Saved Variables: avg: average queue size Fixed Parameters: minth: minimum threshold for queue maxth: maximum threshold for queue maxp: maximum value for pb TNCN: time interval for performing this action
for each TNCN avg ← estimatedQueueSize() if minth ≤ avg < maxth pb ← maxp ∗(avg −minth)/(maxth −minth) normalizePb ← pb/avg else if maxth ≤ avg pb ← 1 normalizedPb ← 1
20
In the above pseudocode, function estimatedQueueSize() gets the estimated neighborhood queue size from channel utilization as discussed in the previous subsection. We also define normalized pb referred as normalizedPb by dividing pb by average queue size avg. ThisnormalizedPb is the probability which will be broadcasted to neighbor nodes. Based on it, they will compute their local drop probabilities. If pb is larger than 0, the neighborhood of this node is in early congestion. In principle, the node should immediately notify the neighbors. However, to avoid “overreaction”, we put several conditions before a node broadcasts a congestion notification. These conditions include
(i) The calculated pb is larger than 0.
(ii) Current node must be on the path of one or more flows. If no traffic goes through it, it should not take any action.
(iii) Current node is suffering in channel contention. We as- sume mobile nodes are cooperative, yet selfish. Thus, the suffering nodes must speak out to ask neighbors for cooperation. This is realized by comparing the (avgtx + avgrx) (see subsection 5.1) with a certain threshold. If (avgtx + avgrx) is small, it means cur- rent node is suffering in terms of channel contention.
(iv) Current node didn’t receive any congestion notification packet in the past interval which contained a larger normalizedPb. Otherwise, that neighbor node’s neigh- borhood is more congested. No need for this node to broadcast a notification since congestion situation may change after some packets are dropped.
Only when all above conditions are met, will a node broad- cast a Neighborhood Congestion Notification (NCN) packet to inform neighbors about its congestion situation. The NCN packet must contain enough information for a neighbor node to calculate its local drop probability. In our imple- mentation, the NCN packet includes 3 fields as <packetType, normalizedPb, lifeTime>. ThepacketType field indicates that this packet is a NCN packet. normalizedPb is used for neighbors to calculate their local drop probabilities. The lifetime field indicates the effective duration of this conges- tion notification. In the NRED scheme, no explicit packet is needed to notify neighbors that congestion has been cleared. A node will simply stop dropping packets after lifetime pe- riod. This effective period should be at least twice the NCN broadcast interval TNCN to ensure that a new NCN packet will reach the neighbor nodes if congestion persists. Once a node receives a NCN packet, it will record the normalizedPb and lifetime fields of the NCN packet. If multiple NCN packets from different nodes are received, only the packet with the largest normalizedPb is stored. Both fields are updated when a new NCN packet from the same node as the last stored NCN packet is received. The stored normalizedPb will be cleared to 0 after lifetime period, if no new NCN packet comes. From our experiments, we found that broadcast is unre- liable when congestion builds up. Thus, it is very likely that the node that is abusing the channel may not receive the NCN packet successfully. To improve the chance that the NCN packet can reach every neighbor successfully, the sender randomly selects a neighbor and “unicasts” the packet to it. Assuming that nodes run in promiscuous mode, all the
neighbors can overhear this packet. By using this simple technique, the propagation of NCN packets is much more reliable than with conventional broadcast with more than 20% improvement.
5.3 Distributed Neighborhood Packet Drop In this sub-scheme, we explain how neighboring nodes co- operatively drop packets to realized the expected drop prob- ability pb over the distributed neighborhood queue. The key is to calculate a node’s local share of this overall drop prob- ability according to its channel bandwidth usage, which has been translated into equivalent queue size for our compu- tational convenience. Suppose a node has received a NCN packet with normalizedPb larger than 0. Then the local share of pb at this node should be proportional to its contri- bution to the average neighborhood queue size avg, which is given as (avgtx + avgrx). Thus the share of pb at this node can be calculated as pb ∗(avgtx + avgrx)/avg. Recall that normalizedPb = pb/avg, so the local drop probability is calculated as normalizedPb ∗(avgtx + avgrx). In our simplified neighborhood queue model, there are two queues at each node, the outgoing queue and incom- ing queue. Packet drop probabilities will be computed and implemented separately on the two queues. The detailed ac- tions performed on the outgoing queue upon a packet arrival from upper layer is given in pseudocode as below.
Algorithm 5.2: RandomDrop()
comment: Actions performed at the outgoing queue
Saved Variables: counttx: outgoing pkts arrived since last drop avgtx: average outgoing queue size Other Parameters: pa: current packet dropping probability
for each packet arrival counttx ← counttx +1 if normalizedPb < 1 pb ← normalizedPb ∗avgtx pa ← pb/(1−counttx ∗pb) else pa ← 1 if pa > 0 aRandomNumber ← random([0,1]) if aRandomNumber ≤ pa drop the arriving pkt counttx ← 0else counttx ←− 1
In the above pseudocode, random([0,1]) is a function which generates a random number between 0 and 1. When normalizedPb is equal to 1, it means the average queue size avg has exceeds the maximum threshold. pa should be 1 no matter what the value counttx is since the drop probability on the neighborhood queue is 1 according to the original RED scheme. The actions performed at the incoming queue are the same as in the pseudocode above, except that avgtx and counttx are replaced by avgrx and countrx. It may be a little con- fusing that we drop packets from the incoming queue, as the original RED only drops outgoing packets. Referring back to the neighborhood queue model in Figure 3 and its simplified expression in Figure 4, we recall that the incom-
21
1 2 3
4 5 6
7 8 9
(0,0) (350,0) (700,0)
(0,350) (350,350) (700,350)
(0,700) (350,700) (700,700)
TCP 1
TCP 2
TCP 3
TCP 4 TCP 5 TCP 6
ing queue at a 1-hop neighbor is actually moved from the 2-hop neighbors. Thus, dropping packets in the incoming queue represents the packet drops at corresponding 2-hop neighbors. Since there is no real incoming queue, the ac- tions are triggered each time a packet is received. Dropping incoming packets at the 1-hop neighbors wastes some band- width since those packets have consumed bandwidth. To avoid this, a better way would be also propagate the con- gestion notification to 2-hop neighbors and ask them drop packets correspondingly. However, as we mentioned in sec- tion 4.3, coordinating 2-hop neighbors requires non-trivial overhead. First, all 1-hop neighbors must re-broadcast the NCN packets to 2-hop neighbors, much more bandwidth is consumed by such broadcasts. Second, to properly drop packets, a 2-hop neighbor has to know a complete list of 1- hop neighbors of the congested node since it only needs to drop packets intended to the congested area. Propagation of such information will also bring much overhead. Thus, in our NRED scheme, we propose to drop incoming packets at 1-hop neighbors rather than asking 2-hop neighbors to drop them.
6. VERIFICATIONANDPARAMETERTUN- ING In the proposed NRED scheme, there are several param- eters which may affect the performance. In this section, we try to determine their optimal values. Moreover, our scheme for estimating the average queue size of the neighborhood queue is realized by estimating the channel utilization. In this section, we also want to verify that it can indeed ap- proximate the real average queue size. Also in this section, performance of NRED in simple scenarios is investigated.
6.1 Verification of Queue Size Estimation Recall that NRED is based on channel utilization rather than queue size. In fact, we believe that channel utiliza- tion is a more appropriate measure than queue size for our problem. Nevertheless, we are still interested to verify that channel estimation is a good approximation to the real queue size. We did a series of simulation experiments to verify and validate our queue estimation algorithm. Also, at the same time, we determined the optimal values of parameters re- lated to the estimation. Major parameters are Tinterval and
0
50
100
150
200
250
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140
Queue size (# of pkts)
Time (s)
Estimated avg. queue Size Real avg. queue size
FTP/TCP connections.
0
50
100
150
200
250
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140
Queue size (# of pkts)
Time (s)
Estimated avg queue size Real avg queue size
HTTP/TCP connections.
wq (see subsection 5.1). The topology of the experiments is given in Figure 5. 9 wireless nodes are involved in the scenario with their coordinates as given in the figure. 6 TCP connections are established. The first TCP connection starts at 20s. The rest of them start one after the other 10s apart. All connections end at 120s and the simulation time is 150s. We record in real time the estimated queue size of Node 5’s neighborhood queue. We also record the queue size changes of the local queue at each node and calculate the corresponding real average queue size of Node 5’s neigh- borhood. By comparing the estimated average queue size and the real value, we can then verify the accuracy of our estimation algorithm. To find the optimal values of Tinterval and wq, experi- ments with different values of Tinterval and wq were per- formed using the same scenario described above. The values of Tinterval ranged from 1ms to 1s and wq ranged from 0.02 to 0.8. 20 scenarios were generated using different random seeds, although the figures are not reported in this paper. The conclusion drawn from the experiments is that the op- timal values of Tinterval lie between 100ms and 1s. If it is too short (e.g. shorter than the transmission time of a packet), the estimation is too rugged. If it is too long, it cannot react to channel changes promptly. In practice, this parameter can be set based on the frequency of topology and traffic pattern changes. A smaller value is preferred if the mobility speed is high. The estimation results are not very
22
sensitive to wq. The best values are found from 0.1 to 0.4. Larger wq has better adaption to sudden channel utilization changes caused by mobility or new flows. Smaller values give more smoothly estimation. In our future simulations, we set Tinterval as 100ms and wq as 0.2. Figure 6 and Figure 7 plotted the typical simulation re- sults with Tinterval and wq as 100ms and 0.2 respectively. In the simulation of Figure 6, the 6 TCP connections are FTP flows. Since FTP tends to utilize all bandwidth, the neighborhood queue quickly builds up and keeps in a high level during the rest of time. We clearly observe a limitation of our estimation algorithm. After the real average queue size exceeds a certain threshold (e.g. after passed the dotted time line in Figure 6), the estimation cannot reflect future increase of the queue size. Except for this limitation, the estimation algorithm approximately matches the real val- ues. Note, the absolute magnitude of the estimated queue size is meaningless, since we translate the channel utilization to number of packets by dividing it by a fixed packet size. The absolute value only affects the values of the minimum threshold (minth) and maximum threshold (maxth). Since in the FTP case, queue size does not change much. To further verify that our estimation algorithm adaptive to frequent queue size changes, we replaced the FTP flows with HTTP flows. The simulation results are shown in Figure 7. When HTTP traffic is used, the average queue size is small and changes frequently. We observe that our estimation still matches the real values quite well. Two problems must be justified here. First, channel uti- lization ratio is past information. Queue size is current state. That means we are estimating the current state based on historical information. Second, when the queue size is too large and channel is fully utilized, further increase of the queue size has no any effect to the channel utilization ratio as observed in Figure 6. Thus, our estimation is bounded to a upper threshold of the queue size. The first problem is not an issue for NRED scheme, as only the average queue size is needed, not the exact current queue size. The orig- inal RED scheme also uses a “low pass filter” to average the queue size. For the second problem, it is true that our scheme has this limitation. However, the purpose of NRED is to detect early congestion and keep running the network below heavy congestion by keep the queue size small. Under such conditions, our estimation algorithm should be precise enough.
6.2 Parameter Tuning with Basic Scenarios In previous subsection, we have verified our queue size estimation algorithm and have tuned related parameters. In this subsection, we focus on another important part of NRED scheme, the calculation of packet drop probability. Once early congestion is detected, the suffering node will notify its neighbor nodes for cooperative packet drops to re- lieve congestion. The related configuration parameters here are the maximum packet drop probability maxp, minimum threshold minth and maximum threshold maxth. We choose the values of minth and maxth based on results in the pre- vious subsection. We observe that when there is heavy con- gestion, the estimated queue size goes around 240 packets. Thus, we choose maxth as 240. To get smooth drop proba- bility, we set minth as 100. We then use simulation experi- ments to decide the optimal values of maxp.
FTP 2 1 2 3 4 FTP 1 (100, 0) (100, 350) (100, 700) (100, 1050)
Figure 8: The hidden terminal scenario, where Node 2 is hidden by transmission from node 4 to node 3 and Node 3 is hidden by transmission from node 1 to node 2.
FTP 2 1 2 3 4 FTP 1
(100, 0) (100, 350) (100, 700) (100, 1050)
Figure 9: The exposed terminal scenario, where node 2 is exposed to transmissions from node 3 to node 4.
Another purpose of this subsection is to identify how well the NRED scheme can solve the TCP unfairness problem under simple, yet fundamental, scenarios. Besides the sce- nario in Figure 1 in section 4, another two basic scenarios used are the hidden terminal and exposed terminal topolo- gies as shown in Figure 8 and 9. These two scenarios are first reported in the early MACAW research [3] as basic topologies causing unfairness at the MAC layer. They later are also identified as the major situations where significant TCP unfairness is observed [18, 19]. Thus, any solution for improving TCP fairness should be examined on these basic scenarios. All the TCP flows start at the same time and last 120 seconds. The simulation time is 150 seconds. The values of maxp tested here is ranging from 0.01 to 0.3. Typi- cal metrics we selected are 1) The overall throughput of each TCP flow. 2) The fairness index and 3) The instan- taneous throughput of each flow. The overall throughput is calculated by the TCP receiver at the end of simula- tion. The fairness index we adopted here is the MaxMin fairness index [2, 10]. Assuming the overall throughput of the two flows are X1 and X2, the fairness index is defined as F(X1,X2)= (X1+X2)2 2(X2 1+X2 2) . The MaxMin fairness index is bounded between 0 and 1. The higher the fairness index, the better the fairness. The instantaneous throughput is defined as X(t)=Dt ∆t , whereDt denotes the data success- fully received during time period [t → t +∆ t]. ∆t in our simulations is 1 second. The fairness index and the overall throughput of the two flows under different values of maxp are given in Figure 10 (hidden terminal scenario) and Figure 11 (exposed terminal scenario). In each figure, the upper diagram is the fairness index and the lower one is the aggregated throughput, which is the sum of the overall throughput of the two flows. Before NRED is applied, the two scenarios show very significant un- fairness consistent to results reported in the literature [18, 19]. In the hidden terminal scenario, one of the two flows usually achieves much higher throughput (e.g. more than 700Kbps) than the other one (e.g. below 100Kbps). Which one wins the channel is not deterministic. Usually the one which starts slightly earlier wins the channel since its con- gestion window has chance to grow larger. The unfairness is even more severe in the exposed terminal scenario, where flow 2 always captures the channel and drives the through- put of flow 1 to nearly zero. Detailed analysis of why hidden
23
0.4
0.5
0.6
0.7
0.8
0.9
1
0 0.05 0.1 0.15 0.2 0.25 0.3
Fairness Index
maxp
Fairness index w/ NRED Fairness index w/o NRED
200
300
400
500
600
700
800
0 0.05 0.1 0.15 0.2 0.25 0.3
Aggregated Throughput (Kbps)
maxp
Aggr. throughput w/ NRED Aggr. throughput w/o NRED
Figure 10: Performance of NRED scheme under the hidden terminal situation with various maxp values
0.4
0.5
0.6
0.7
0.8
0.9
1
0 0.05 0.1 0.15 0.2 0.25 0.3
Fairness Index
maxp
Fairness index w/ NRED Fairness index w/o NRED
200
300
400
500
600
700
800
0 0.05 0.1 0.15 0.2 0.25 0.3
Aggregated Throughput (Kbps)
maxp
Aggr. throughput w/ NRED Aggr. throughput w/o NRED
Figure 11: Performance of NRED scheme under the exposed terminal situation with various maxp values
0
200
400
600
800
1000
1200
0 10 20 30 40 50 60 70 80 90 100 110 120 130
Throughput (Kbps)
Time (s)
FTP 1 FTP 2
Figure 12: Instantaneous throughput of the two TCP connections under the exposed terminal sit- uation when NRED is applied
and exposed terminal situations cause significant unfairness can be found in [3, 18, 19]. After NRED is applied, we observe that the fairness in- dices under the both scenarios are improved quickly along with the increase of maxp. For the hidden terminal scenario, the fairness index is close to 1 (the highest value) after maxp is larger than 0.1. For the exposed terminal scenario, fair- ness index is also above 0.95 when maxp is larger than 0.14. In general, fairness index is increased along with the increase of maxp. This is because larger maxp will punish the flows overusing channel quickly. Along with the increase of maxp, the aggregated through- put of the two flows is decreased. The throughput loss comes from two reasons. First, before a packet is dropped by NRED, it may have used the channel. Dropping such pack- ets certainly wastes some bandwidth. Second, the NRED scheme tends to keep the wireless channel slightly underuti- lized. Thus, a small fraction of bandwidth is also sacrificed. To achieve good fairness without too much throughput loss, from above simulation experiments, we conclude that the optimal values of maxp are between 0.1 and 0.2. In later experiments, we set maxp as 0.14. To further demonstrate how fairly the two flows share the channel when NRED scheme is applied, we plot the instan- taneous throughput of the two flows in the exposed terminal scenario with maxp as 0.14 in Figure 12. Results of the hid- den terminal scenario are very similar. From Figure 12 we can see that the two flows interlace very well with no any flow continuously uses the channel for long period. Note, only one of the flows can transmit at any time, which ex- plains the up and down of instantaneous throughput. We then further investigate how the NRED performs un- der the scenario in Figure 1 in section 4, where the original RED scheme does not help much in terms of improving fair- ness. The overall throughput of the 3 flows with and with- out NRED scheme is shown in Figure 13. The fairness is very clear. The starved flow 2 now gains good throughput. Figure 14 further gives the instantaneous throughput of the 3 flows. We can see that short-term fairness is also good (Note, flow 1 and flow 3 can transmit at the same time. But when flow 2 is transmitting, both of them should be quiet.). Through Figure 13 we also observe that the aggregated throughput of the 3 flows is decreased by 42% when the fairness is improved. This is an interesting point of the
24
0
100
200
300
400
500
600
700
800
No NRED NRED
Throughput (Kbps)
FTP 1 FTP 2 FTP 3 Aggr. throughput
0
100
200
300
400
500
600
700
0 10 20 30 40 50 60 70 80 90 100 110 120 130
Throughput (Kbps)
Time (s)
FTP 1 FTP 2 FTP 3
tradeoff between fairness and throughput. Only half the total throughput is achieved during the period of flow 2’s transmissions due to the spatial reuse constraint. Thus, to achieve the best network-wide throughput, we should totally starve flow 2. However, this is extremely unfair to flow 2. To achieve fairness among the 3 flows, decreasing the ag- gregated throughput is unavoidable. More discussion about trade off between fairness and overall network throughput can be found in [12].
7. PERFORMANCEEVALUATIONOFNRED In this section, we further evaluate the proposed NRED scheme under more realistic scenarios such as considering multiple bottlenecks as well as mobility. The major config- uration parameters of NRED are set as wq =0 .2, minth = 100 packets, maxth = 240 packets and maxp =0 .14.
7.1 Multiple Congested Neighborhood In the previous section, most investigated scenarios only contain one bottleneck neighborhood. However, in the ad hoc network, it is highly possible that a TCP flow will tra- verse several congested neighborhoods, although the degree of congestion may be different. In this experiment, we evalu- ate how NRED performs under such situations. The experi- ment scenario is illustrated in Figure 15. The grid topology is used and 6 FTP/TCP connections are established as in the figure. The vertical and horizontal distance between neighboring nodes is 350m. Each TCP connection traverses
FTP 1 FTP 2 FTP 3
FTP 4
FTP 5
FTP 6
.
0
50
100
150
200
No NRED NRED
Throughput (Kbps)
FTP 1 FTP 2 FTP 3 FTP 4 FTP 5 FTP 6
4 hops. In this topology, several bottleneck neighborhoods may be present at the same time. In the figure, 3 possible bottlenecks of TCP 5 are shown as gray shaded circles. All 6 TCP connections start at 10s and finish at 130s. The overall throughput of each flow is given in Figure 16. As we can observe from Figure 16, TCP 2 and TCP 5 are starved originally but gain visible throughput when NRED is applied. The improvement of fairness is obvious. However, TCP 2 and TCP 5 will always achieve less throughput since they have interfering flows on both sides.
7.2 Performance under Mobility In this experiment, we consider the adaptation of NRED to mobility. Two parameters of NRED scheme control its adaptability to topology changes. The first one is the chan- nel estimation interval Tinterval which controls how quickly the algorithm can react to sudden channel utilization changes. The second parameter is the lifetime of a NCN packet. Once a node moves out from a congested neighborhood, it will not receive a new NCN packet. But it will continue to mark or drop packets until the lifetime of the old NCN packet expires. The scenario of this experiment is illustrated in Figure 17. 5 nodes are involved and two FTP/TCP connections are used as shown in the figure. Only node 5 is moving — up and down between positions (200, 600) and (200, 400). Its initial position is (200, 600). The mobility speed is 10m/s. The node stays at each position for around 20s and then continues to move.
25
Node 5 moving up and down
FTP 11
2
3
FTP 2 4 6 5
(0, 0)
(200, 150)
(400, 0)
(0, 650)
(200, 600)
(400, 650)
5'(200, 400)
0
200
400
600
800
1000
1200
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140
Throughput (Kbps)
Time (s)
FTP 1 FTP 2
Figure 18: Instantaneous throughput dynamics un- der mobility without NRED.
Figure 18 (without NRED) and 19 (with NRED) show the dynamics of the two connections by plotting the instan- taneous throughput of each flow. From Figure 18, we ob- serve that when node 5 moves down, the two connections are out of interference with each. Then they both can use the channel well. However, when node 5 moves up, the two connections start interfering with each other. The FTP 1 tends to capture the channel because when node 5 moves up, its distance to node 4 and node 6 is larger. Thus, the transmissions among them are not as robust as the trans- missions of FTP 1. Thus it has disadvantages in competing the channel. When the NRED scheme is applied, node 5 now can de- tect the congestion after moving close to node 2. From Fig- ure 19, we clearly observe that now the two flows can share the channel fairly when they are close enough to interfere with each other. In the experiment of Figure 19, the esti- mation interval Tinterval is set to 100ms and the lifetime of a NCN packet is 2 seconds. The scenario of this ex- periment is very simple and artificial. However, it clearly demonstrates that the NRED scheme is indeed can adapt to mobility. We didn’t evaluate our scheme under random mo- bility since such situations may distract the main point of the paper. For example, link breaks (path failures) caused by mobility will also result in very low throughput of some TCP flows. However, such low throughput should not be recognized as unfairness (at least not the unfairness issues targeted in this paper).
0
200
400
600
800
1000
1200
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140
Throughput (Kbps)
Time (s)
FTP 1 FTP 2
0
50
100
150
200
250
300
No NRED NRED
Throughput (Kbps)
FTP 1 FTP 2 FTP 3 FTP 4 FTP 5
7.3 More Realistic Scenario In all simulations above, the topology is simple and specif- ically selected. The well controlled scenarios allow us to clearly demonstrate the problems and the usefulness of the NRED scheme. However, it is also interesting to take a look at the performance of NRED under more realistic scenarios. In this experiment, both random topology and random traf- fic are used. More precisely, totally 50 nodes are randomly deployed in a 1000m by 1000m field and 5 FTP/TCP con- nections are randomly selected. The TCP connections start and end at the same time and last 120 seconds. AODV routing protocol [14] is used here and nodes are not mo- bile. Different random seeds are used for multiple simulation runs. The results of a typical simulation run are plotted in Figure 20. Other simulations give similar results, but not similar numbers of each specific flow since the traffic pattern is changed due to change of the random seed. From Figure 20 we can observe that NRED scheme is still able to improve fairness in general, especially reflected by throughput of flow 2 and flow 3. In conclusion, we would like to point out that good fairness does not mean the same throughput for all the participating TCP connections. Two important factors must be considered. First, TCP through- put is highly affected by the number of hops from senders to receivers. It is a well known bias that TCP flows with shorter RTT are usually favored. This bias is strengthened even more in ad hoc wireless networks. The maximum achiev-
26
able throughput of a 2-hop flow is only 1/2 of that of a 1-hop flow. Similarly, a 3-hop flow can only achieve at most 1/3. This feature is due to the spatial reuse constraint, which has been discussed in detail in [7] and [?]. The sec- ond factor is that interference is location dependent. Even two flows may contend with each other in a certain location, they are facing different interfering constraints from other locations. In other words, we have the multiple bottleneck effect. It is thus reasonable that flows with fewer interfer- ing flows (i.e., less constraining bottlenecks) achieve higher throughput, which should not be recognized as unfairness. To sum up, the investigation of TCP fairness in arbitrary topologies and scenarios is extremely complex, especially when nodes are mobile. The NRED method appears to have general applicability in above preliminary experiments. The proper evaluation of NRED in general, multi-bottleneck sce- narios requires the definition of new performance measures such as a wireless specific fairness index suitable for multi- hop ad hoc networks and will be subject of future studies.
8. DISCUSSION AND FUTURE WORK TCP fairness in multihop wireless networks is closely re- lated to the underlying MAC protocols. Fairness of the MAC protocol has been an active research area in the past several years. Several schemes for improving the fairness of MAC protocols have been proposed in the literature [1, 13]. Although little work has been done to investigate TCP fair- ness under such fair MAC protocols, we believe improving fairness of the MAC protocol will certainly improve TCP fairness as well. Naturally, a major problem of MAC layer fairness solu- tions is implementation difficulty. As the IEEE 802.11 stan- dard has been widely accepted by the industry and IEEE 802.11 wireless radios are becoming the de facto standards for ad hoc testbeds, it is clearly desirable to solve TCP un- fairness problems at the network or transport layers. An- other important consideration is incremental deployment. Usually, an ad hoc network requires that all involved wire- less nodes have a consistent MAC protocol. Thus, any mod- ification of the MAC protocol requires update at all nodes. The NRED scheme proposed in this paper is a network layer solution that can be incrementally deployed. In the worst case, a NCN packet arriving at a non-NRED node will be dropped silently. And as long as some nodes capturing the channel recognize the NCN packet, the unfairness can be improved to some degree. If we view TCP connections as general traffic flows, TCP fairness is essentially a multihop fair scheduling problem as discussed in [12]. Thus fair scheduling at the network layer for ad hoc networks is quite close to our work in this paper. However, fair scheduling schemes tend to require topology information, in most cases even the global information is needed, for scheduling decisions, which requires additional overhead and is not robust to mobility. Besides, multihop fair scheduling itself is still an active research area without any satisfactory practical solution. In this paper, we utilize the features of TCP congestion control to achieve fairness by reacting to early neighborhood congestion. Compared to fair scheduling, our scheme doesn’t need any topology informa- tion. It is totally localized with little overhead. We only fo- cus on the bottleneck neighborhood and only the congested nodes need to broadcast a small NCN control packet. In general, fair scheduling will be used for QoS flows, while our
scheme is suitable for fairness among best-effort flows. For example, although fair scheduling schemes and QoS schemes probably can solve all problems that RED can, RED gate- ways still find their important positions in the wired net- works due to their simplicity and low overhead. In current design of NRED scheme, packets of the ag- gressive TCP flows are randomly dropped at the congested neighborhood. This is not maximally efficient for overall network throughput since those packets have consumed some bandwidth before they reach the congested area. This is also one reason that the aggregated throughput of TCP flows decreases in our experiments when the NRED scheme is ap- plied. An alternative choice would be to explicitly notify the TCP sender to freeze or reduce its congestion window. For example, nodes in the congested neighborhood can mark the Explicit Congestion Notification (ECN) bit of the ongo- ing TCP packets instead of dropping them. However, such schemes require support from TCP senders and receivers. Directly dropping some packets is the simplest way to no- tify traffic sources. In this paper, we mostly evaluated NRED scheme under relatively long-lived TCP flows such as FTP connections transferring a medium or large size file. This is because TCP unfairness issues are more serious to such TCP traffic. If a TCP connection finishes its transfer in seconds, NRED may not have enough time to detect the network congestion and perform proper actions. However, for short-lived TCP flows, even if it captures the channel, it will not hurt other flows too much since it ends very quickly anyway. Although NRED scheme is targeting improving the fair- ness of TCP traffic, similar unfairness issues may also hap- pen to non-TCP traffic such as multimedia streaming. The NRED scheme requires the transport protocol to be re- sponsive to network congestion indicated by packet loss. Many TCP friendly or congestion controlled transport pro- tocols have been proposed for ad hoc networks recently. The NRED scheme will also work well with such transport pro- tocols. Our future research directions include: investing new algo- rithms for estimating queue size, comparing different choices for congestion notification, investigating fairness among TCP flows and multimedia streaming as well developing an ana- lytical model for neighborhood queue.
9. CONCLUSION TCP performance is critical to the broad acceptance of multihop wireless networks. In this paper, we proposed a scheme called Neighborhood RED, which is an extension of the RED originally developed in the wired network to ad hoc wireless networks. By detecting early congestion and drop- ping packets proportionally to a flow’s channel bandwidth usage, the NRED scheme is able to improve TCP fairness. The major contributions of this work are the concept of a distributed neighborhood queue (without which the RED scheme does not work) and the design of a network layer solution that does not require MAC modification.
10. ACKNOWLEDGMENTS We thank our shepherd, Dr. David Maltz (CMU), for helping revise and improve this paper. We also thank the anonymous MobiCom reviewers for providing helpful com- ments and recommendations.
27
11. REFERENCES
[1] B. Bensaou, Y. Wang, and C. C. Ko. Fair medium access in 802.11 based wireless ad-hoc networks. Proceedings of ACM MobiHoc’00, Aug. 2000. [2] D. Bertsekas and R. Gallager. Data Networks. Prentice Hall, second edition, 1996. [3] V. Bharghavan, A. Demers, S. Shenker, and L. Zhang. MACAW: A media access protocol for wireless LANs. Proceedings of the SIGCOMM’94, Aug. 1994. [4] K. Chandran, S. Raghunathan, S. Venkatesan, and R. Prakash. A feedback-based scheme for improving TCP performance in ad hoc wireless neworks. IEEE Personal Communications Magazine, 8(1), Feb. 2001. [5] T. D. Dyer and R. V. Boppana. A comparison of TCP performance over three routing protocols for mobile ad hoc networks. Proceedings of ACM MobiHoc’01, Oct. 2001. [6] S. Floyd and V. Jacobson. Random early detection gateways for congestion avoidance. IEEE/ACM Transactions on Networking, 1(4), Aug. 1993. [7] Z. Fu, P. Zerfos, H. Luo, S. Lu, L. Zhang, and M. Gerla. The impact of multihop wireless channel on TCP throughput and loss. IEEE INFOCOM’03, Mar. 2003. [8] M. Gerla, R. Bagrodia, L. Zhang, K. Tang, and L. Wang. TCP over wireless multihop protocols: Simulation and experiments. Proceedings of IEEE ICC’99, June 1999. [9] G. Holland and N. H. Vaidya. Analysis of TCP performance over mobile ad hoc networks. Proceedings of ACM MobiCom’99, Aug. 1999. [10] R. Jain, D. M. Chiu, and W. Hawe. A quantitative measure of fairness and discrimination for resource allocation in shared systems”. DEC Technical Report DEC-TR-301, 1984. [11] J. Li, C. Blake, D. Couto, H. Lee, and R. Morris.
Capacity of ad hoc wireless networks. Proceeding of ACM MobiCom’01, Jul. 2001. [12] H. Luo, S. Lu, and V. Bharghavan. A new model for packet scheduling in multihop wireless networks. ACM Mobicom’00, Aug. 2000. [13] T. Nandagopal, T. Kim, X. Gao, and V. Bharghavan. Achieving MAC layer fairness in wireless packet networks. Proceedings of ACM MobiCom’00, Aug. 2000. [14] C. E. Perkins and E. M. Royer. Ad-hoc on-demand distance vector routing. Proceedings of IEEE WMCSA’99, Feb. 1999. [15] QualNet. Network simulator. Available at http://www.qualnet.com, 2003. [16] T. Rappaport. Wireless Communications: Principles and Practice. Prentice Hall, New Jersey, 1996. [17] K. Tang and M. Gerla. Fair sharing of MAC under TCP in wireless ad hoc networks. Proceedings of IEEE MMT’99, Oct. 1999. [18] K. Xu, S. Bae, S. Lee, and M. Gerla. TCP behavior across multihop wireless networks and the wired internet. Proceedings of ACM WoWMoM’02, Sep. 2002. [19] S. Xu and T. Saadawi. Does the IEEE 802.11 MAC protocol work well in multihop wireless ad hoc networks? IEEE Communications Magazine, 39(6), Jun. 2001. [20] S. Xu and T. Saadawi. Revealing TCP unfairness behavior in 802.11 based wireless multi-hop networks. Proceedings of IEEE PIMRC’01, Oct. 2001. [21] X. Zeng, R. Bagrodia, and M. Gerla. GloMoSim: a library for parallel simulation of large-scale wireless networks. Proceedings of PADS’98, May 1998. [22] Y. Zhang and F. Wang. Improving TCP performance over mobile ad-hoc networks with out-of-order detection and response. Proceedings of ACM MobiHoc’02, June 2002.
28
