1832
`
`IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 17, NO. 6, DECEMBER 2009
`
`Measurement and Modeling of the Origins of
`Starvation of Congestion-Controlled Flows in
`Wireless Mesh Networks
`
`Omer Gurewitz, Member, IEEE, Vincenzo Mancuso, Member, IEEE, Jingpu Shi, Member, IEEE, and
`Edward W. Knightly, Fellow, IEEE
`
`Abstract—Significant progress has been made in understanding
`the behavior of TCP and congestion-controlled traffic over CSMA-
`based multihop wireless networks. Despite these advances, how-
`ever, no prior work identified severe throughput imbalances in the
`basic scenario of mesh networks, in which a one-hop flow contends
`with a two-hop flow for gateway access. In this paper, we demon-
`strate via real network measurements, testbed experiments, and an
`analytical model that starvation exists in such a scenario; i.e., the
`one-hop flow receives most of the bandwidth, while the two-hop
`flow starves. Our analytical model yields a solution consisting of
`a simple contention window policy that can be implemented via
`standard mechanisms defined in IEEE 802.11e. Despite its sim-
`plicity, we demonstrate through analysis, experiments, and simu-
`lations that the policy has a powerful effect on network-wide be-
`havior, shifting the network’s queuing points, mitigating problem-
`atic MAC and transport behavior, and ensuring that TCP flows
`obtain a fair share of the gateway bandwidth, irrespective of their
`spatial location.
`Index Terms—Experimental, fairness, IEEE 802.11, mesh, TCP.
`
`I. INTRODUCTION
`
`M ESH deployments are expected to provide broadband
`
`low-cost mobile access to the Internet. The prevailing
`architecture for large-scale deployments is a multitier architec-
`ture in which an access tier connects end-user PCs and mobile
`devices to mesh nodes and a backhaul tier forwards traffic to and
`from a few high-speed gateway nodes. Different from WLANs,
`the mesh backhaul tier topology is multihop; i.e., some of the
`traffic traverses more than one wireless link before reaching the
`
`Manuscript received March 25, 2008; revised November 06, 2008; approved
`by IEEE/ACM TRANSACTIONS ON NETWORKING Editor A. Kumar. First pub-
`lished July 14, 2009; current version published December 16, 2009. This re-
`search was supported by NSF Grants CNS-0331620 and CNS-0325971 and by
`the Cisco Collaborative Research Initiative.
`O. Gurewitz is with the Department of Communication Systems Engineering,
`Ben Gurion University of the Negev, Beer Sheva 84105, Israel (e-mail: gure-
`witz@cse.bgu.ac.il; gurewitz@gmail.com).
`V. Mancuso is with the Department of Electrical, Electronic and Telecom-
`munication Engineering, Università di Palermo, Palermo 90133, Italy (e-mail:
`vincenzo.mancuso@dieet.unipa.it).
`J. Shi was with the Department of Electrical and Computer Engineering, Rice
`University, Houston, TX 77005 USA. He is now with Quantlab Financial LLC,
`Houston, TX 77006 USA (e-mail: jingpushi@yahoo.com).
`E. W. Knightly is with the Department of Electrical and Computer Engi-
`neering, Rice University, Houston, TX 77005 USA (e-mail: knightly@ece.rice.
`edu).
`Color versions of one or more of the figures in this paper are available online
`at http://ieeexplore.ieee.org.
`Digital Object Identifier 10.1109/TNET.2009.2019643
`
`wired network. Clearly, for mesh networks to be successful, it is
`critical that the available bandwidth be distributed fairly among
`users, irrespective of their spatial location and regardless of their
`hop distance from the wired gateway.
`Significant progress has been made in understanding the be-
`havior of TCP and congestion-controlled traffic over wireless
`networks. Moreover, previous work showed that severe unfair-
`ness and even complete starvation can occur in multihop wire-
`less networks using CSMA-based MAC (e.g., IEEE 802.11a/b/g
`MAC), and solutions have been proposed correspondingly (see
`Section VI for a detailed discussion of related work). However,
`despite these advances, no prior work has identified the basic
`scenario in which congestion-controlled flows contending for a
`shared gateway yields starvation.
`In this paper, we analytically and experimentally show that
`starvation (i.e., long-term and severe throughput imbalance)
`occurs in a scenario in which two-hop flows share the same
`gateway with one-hop flows. Interestingly, we also show that
`the starvation phenomenon is not significantly affected by the
`number of TCP flows involved, either one-hop or two-hop
`flows, therefore resulting in a dramatic performance impair-
`ment of all two-hop flows as soon as at least one one-hop flow
`comes into play. Because the occurrence of such a combination
`of flows cannot be avoided in a mesh network, we refer to this
`fundamental scenario as the basic scenario. Moreover, this
`scenario exists with both single-radio and multiradio architec-
`tures (see the discussion in Section III). Note that starvation
`of two-hop flows precludes the use of the mesh architecture,
`which employs multihop paths by definition. Our contributions
`are as follows.
`First, we describe the protocol origins of starvation as a com-
`pounding effect of three factors: 1) the MAC protocol induces
`bistability in which pairs of nodes alternate in capturing system
`resources; 2) despite the inherent symmetry of MAC bistability,
`the transport protocol induces asymmetry in the time spent in
`each state and favors the one-hop flow; and 3) most critically,
`the multihop flow’s transmitter often incurs a high penalty in
`terms of loss, delay, and consequently, throughput, in order to
`recapture system resources.
`Second, we perform experiments in the technology for all
`(TFA) mesh network, an operational network deployed in a
`densely populated urban area. We demonstrate the existence
`of starvation under saturation conditions and show that only a
`one-hop TCP flow in competition with a two-hop TCP flow is
`sufficient to induce starvation.
`IPR2015-01973
`SIPCO, LLC
`Exhibit 2006
`
`Authorized licensed use limited to: Barbara Lange. Downloaded on December 27, 2009 at 23:02 from IEEE Xplore. Restrictions apply.
`
`1063-6692/$26.00 © 2009 IEEE
`
`

`
`GUREWITZ et al.: ORIGINS OF STARVATION OF CONGESTION-CONTROLLED FLOWS
`
`1833
`
`Third, we develop an analytical model both to study starva-
`tion and to devise a solution to counter starvation. The model
`omits many intricacies of the system (TCP slow start, fading
`channels, channel coherence time, etc.) and instead focuses
`on the minimal elements needed such that starvation mani-
`fests. Namely, the model uses a discrete-time Markov chain
`embedded over continuous time to capture a fixed end-to-end
`congestion window, a carrier sense protocol with or without
`RTS/CTS, and all end-point and intermediate queues.
`The model enlights counter-starvation policy, in which only
`the gateway’s directly connected neighbors should increase
`their minimum contention window to a value significantly
`greater than that of other nodes. This policy can be realized via
`mechanisms in standard protocols such as IEEE 802.11e [2].
`The model also characterizes why the policy is effective in that
`it forces all queuing to occur at the gateway’s one-hop neigh-
`bors rather than elsewhere. Because these nodes have a perfect
`channel view of both the gateway and their neighbors that are
`two hops away from the gateway, bistability is eliminated such
`that the subsequent penalties are not incurred.
`Finally, we experimentally demonstrate that the counter-star-
`vation policy completely solves the starvation problem. In
`particular, we realize this policy by employing the IEEE
`802.11e mechanism that allows policy-driven selection of con-
`tention windows. We redeploy a manageable set of MirrorMesh
`nodes on site (mirroring a subset of the TFA mesh nodes) and
`perform extensive experiments. We extend our investigation to
`a broader set of scenarios and show that the counter-starvation
`policy enables TCP flows to fairly share the gateway bandwidth
`in more general scenarios.
`In the remainder, we present an experimental demonstration
`of starvation in Section II, an analysis of starvation’s cross-
`layer protocol origins in Section III, an analytical model and a
`counter-starvation policy in Section IV, the experimental evalu-
`ation of such a policy in Section V, related work in Section VI,
`and a conclusion in Section VII.
`
`II. STARVATION IN URBAN MESH NETWORKS
`In this section, we describe the basic topology for mesh net-
`works and experimentally demonstrate the existence of starva-
`tion in this basic topology.
`
`A. Basic Topology
`The basic topology of any mesh network is shown in Fig. 1,
`in which two mesh nodes,
`and
`, are located two and one
`hops away from the gateway,
`, respectively. Mesh nodes
`and
`do not sense each other’s transmission— i.e., they are
`forwards all the traffic between nodes
`hidden—and node
`and
`. In particular, we consider the case of upstream TCP
`traffic, in which both
`and
`transmit a TCP flow to
`.
`Since downstream traffic is expected to be at least as important
`as upstream traffic, we will show in Section V-D that similar re-
`sults as the ones shown for upstream traffic also apply to down-
`stream traffic, i.e., the same basic topology in which the gateway
`transmits two TCP flows to A and B.
`Note that this topology is necessarily embedded in any larger
`mesh network topology given that mesh networks are defined
`as multihop wireless networks with gateways. In general, nodes
`
`Fig. 1. The traffic matrix in the basic topology. Mesh nodes A and GW do not
`sense each other’s transmission. Packet exchanges between mesh nodes A and
`GW are forwarded by mesh node B.
`
`within a two-hop distance according to the adopted routing pro-
`tocol, e.g.,
`and
`in Fig. 1, can be either in transmission
`range or not. In this paper, we consider the relevant case in
`which those nodes cannot coordinate their transmissions; i.e.,
`nor
`defers its transmission when the other is
`neither
`transmitting. Throughout this paper whenever conducting mea-
`surements on the basic topology (TFA network and MirrorMesh
`and
`are indeed hidden.
`network), we verified that nodes
`The set of experiments that we performed included the scan of
`and node
`to verify
`wireless signals detected by both node
`that neither one of them could see the other. We also verified be-
`and
`can
`fore and after setting each experiment that nodes
`transmit to two different receivers simultaneously and achieve
`about the same throughput that can be achieved by each flow
`and
`do not interfere
`while transmitting alone; therefore,
`with each other—i.e., they are hidden nodes.
`
`B. Measurements in TFA
`
`Here, we experimentally demonstrate the potential for starva-
`tion in the TFA network. TFA network is an operational mesh
`network that provides Internet access in a densely populated
`urban neighborhood in Houston, TX [1]. For each scenario ex-
`perimentally examined in TFA network, we selected relevant
`nodes that complied with the topology studied, artificially gen-
`erated the required traffic (TCP or UDP) using Iperf v.1.7.0,
`and measured the achieved throughput on each of the observed
`nodes. Since all experiments on TFA took place in the presence
`of the network’s normal user traffic, and in order to minimize
`the interference with TFA users, we performed the experiments
`during off-peak hours (3:00–6:00 a.m), when TFA user traffic
`was negligible. Moreover, before and after each experiment, we
`ensured that the links under investigation were fully operational
`and that full throughput could be achieved when each link was
`used alone; e.g., we generated traffic only from one node and
`measured the end-to-end throughput achieved (achievable TCP
`throughput). Throughout this paper, we only show experimental
`results in which all participating links can reach about the same
`TCP (UDP) throughput when isolated. In order to further under-
`stand the channel activity throughout each experiment, we used
`tcpdump v.3.4 and Kismet v.2006.04.R1 to collect MAC-level
`traces at selected network nodes.
`In the set of results presented in this section, the measurement
`intervals used are 120 s, the maximum PHY rate is 11 Mbps, and
`the radio band is channel 6 of the 2.4-GHz ISM band. Informa-
`tion regarding TFA network, including the connectivity map,
`and the specific nodes used for each experiment can be found in
`[19].
`In the basic set of experiments, we chose two TFA nodes
`, which in addition to the gateway (
`), complied with
`the basic topology as described in Section II-A. As explained in
`
`Authorized licensed use limited to: Barbara Lange. Downloaded on December 27, 2009 at 23:02 from IEEE Xplore. Restrictions apply.
`
`

`
`1834
`
`IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 17, NO. 6, DECEMBER 2009
`
`Fig. 2. TCP behavior in the basic topology, with (a) RTS/CTS disabled and
`with (b) RTS/CTS enabled. Each pair of bars represents the achievable TCP
`throughput and the TCP throughput resulting from flow contention for the
`one-hop flow (B ! GW ) and the two-hop flow (A ! GW ), respectively.
`
`,
`
`and
`Section II-A, we experimentally verified that nodes
`were hidden from one another. Furthermore, by observing the
`routing table throughout the experiments, we verified that all of
`’s packets to and from the gateway were forwarded by node
`,
`and no other node was involved in the data forwarding. We si-
`multaneously generated a TCP flow from the two-hop node
`and a TCP flow from the one-hop node
`to the gateway
`and measured the TCP throughput attained by each flow.
`Fig. 2 depicts the throughput of the two flows with and
`without contention. As can be seen in the figure, the achievable
`and
`are about the
`throughputs on links
`same; hence, the two-hop flow’s achievable TCP throughput
`is about half of the one-hop flow’s one. Nonetheless, although
`the two-hop flow can receive considerable throughput when
`singly active, severe starvation occurs when the RTS/CTS
`mechanism is off [Fig. 2(a)] as well as when the RTS/CTS is
`enabled [Fig. 2(b)]. In particular, the one-hop TCP flow from
`dominates, whereas the two-hop TCP flow from node
`node
`receives nearly zero throughput in all experiments. Since we
`verify that other network activities during our experiment are
`negligible—i.e., we measured only a few kbps of control and
`data traffic—the starvation observed in Fig. 2 can be only due
`,
`, and
`, i.e., due to the high
`to the activity of nodes
`collision probability experienced by ’s TCP DATA and
`’s
`TCP ACKs (or by their RTS frames).
`A comprehensive measurement study was conducted in TFA
`including diverse combinations of user activity and protocol
`set. Due to space limitations, those experiments are omitted
`from this manuscript and are fully reported in [19]. Nonethe-
`less, the outcome of this set of experiments verifies that the basic
`topology starvation is neither solely due to topology and MAC
`behavior (hidden terminal problem), nor a straightforward con-
`sequence of the traffic matrix, but rather the compounding effect
`of topology, medium access mechanisms, and the behavior of a
`connection-oriented transport protocol, that are required to in-
`duce starvation.
`
`III. STARVATION’S PROTOCOL ORIGINS
`
`Here, we describe how the protocol mechanisms of medium
`access and congestion control mechanisms interact to cause star-
`vation in the basic scenario shown in Fig. 1. We analytically
`model this scenario in Section IV.
`
`Fig. 3. TCP DATA and TCP ACK contending for channel access. Nodes A and
`GW cannot sense one another. Hence, collisions are possible at node B, either
`involving the MAC frames carrying TCP packets or the respective RTS frames,
`if the RTS/CTS handshake is enabled.
`
`A. Protocol Origins
`Medium Access and Bistability: The collision avoidance
`mechanism in CSMA/CA causes bistability, in which node
`and
`alternate in transmission of multiple
`pairs
`packet bursts. In particular, the system alternates between a
`and
`jointly capture the system resources for
`state in which
`is idle, and a state in which
`multiple transmissions while
`and
`transmit while
`is idle.
`In order to understand the bistability, we first examine the be-
`havior of two flows in the scenario shown in Fig. 3, where the
`and two-hop node
`contend for transmit-
`gateway node
`ting TCP ACK and TCP DATA, respectively.
`are back-
`and
`Assume the transmission queues of
`logged at a given time, and both nodes are in the minimum con-
`and
`, are
`tention stage. Since the two senders, namely
`hidden from each other, a transmission from one sender suc-
`ceeds only when it fits within the other sender’s backoff interval.
`Note that when the packet size of one sender is comparable to
`or larger than the contention window of the other sender, the
`probability of collision between the two senders is very high.
`For example, in IEEE 802.11b with default parameters, the col-
`lision probability between two RTS transmissions from the two
`senders is 0.7, assuming that both transmitters are in the first
`backoff stage. The collision probability for data packets with
`RTS/CTS off is even higher (e.g., nearly 1 for packets larger
`than 750 bytes in 802.11b). Thus, when both nodes are in an
`early backoff stage, the system is likely to experience collisions.
`After a series of collisions, the backoff window of both nodes
`will become sufficiently large such that one of the nodes will
`successfully transmit a packet, as shown in Fig. 4(a).
`finally suc-
`Assume, without loss of generality, that node
`ceeds in transmitting a packet. After this successful transmis-
`resets its contention window back to its min-
`sion, node
`keeps a high contention window. In
`imum size, while node
`to succeed in its next transmission attempt,
`order for node
`,
`it must fit its packet in a small backoff interval of node
`which is an unlikely event. After a resulting collision, the prob-
`ability to succeed for each node is asymmetric because the con-
`is much smaller than that of
`. This
`tention window of
`man-
`process can recur many times such that only node
`ages to transmit packets, while node
`keeps increasing its con-
`is high,
`tention window. When the contention window of
`can transmit multiple packets between two consecutive trans-
`, as depicted in Fig. 4(b).
`mission attempts by
`To summarize, when mesh node
`wins the channel,
`it enters a success state in which it transmits a burst of packets,
`enters a fail state in which it does not succeed
`while
`in transmitting any packets. The success state can terminate for
`
`Authorized licensed use limited to: Barbara Lange. Downloaded on December 27, 2009 at 23:02 from IEEE Xplore. Restrictions apply.
`
`

`
`GUREWITZ et al.: ORIGINS OF STARVATION OF CONGESTION-CONTROLLED FLOWS
`
`1835
`
`Illustration of the multipacket capture of the channel by either node A
`Fig. 4.
`or GW . (a) Small contention window results in collision with high probability.
`(b) Node GW succeeds to transmit a packet and resets its contention window.
`It may transmit multiple packets due to the high contention window of node A.
`(c) When node A reaches its maximum retry limit, it still collides with high
`probability due to the minimum contention window of node GW ; hence, it
`drops the packet and resets its contention window. Note that GW increases its
`contention window due to the collision, which leaves high probability to node A
`to succeed in its next transmission.
`
`Illustration of bistability with alternation of (A; B) and (B; GW )
`Fig. 5.
`transmissions. Whenever A (GW ) enters in the success state, a burst of
`packets is transmitted by A (GW ) and B. The length of the burst depends
`on the value of the MAC maximum retry limit and on the backlog of the
`transmission queue on A (GW ).
`
`three reasons: 1) the probability of the node with higher con-
`tention window to win is low but not zero; 2) the losing node
`drops the packet and resets its contention window after it reaches
`its maximum retry limit, as illustrated in Fig. 4(c); 3) the trans-
`mission queue of the winning node is emptied.
`,
`and
`is in sensing range of both
`Note that since node
`it contends fairly with the node that is in the success state and
`interleaves its packets with the burst generated from this node.
`This bistability is depicted in Fig. 5.
`Asymmetry Induced by Sliding Window: TCP causes the
`system to spend dramatically different times in the two stable
`states. Specifically, TCP’s sliding window mechanism creates a
`closed-loop system between each sender–receiver pair in which
`the transmission of new packets is triggered by the reception
`of acknowledgments. The basic scenario contains two nested
`transport loops, one for each flow. We term the one-hop and the
`two-hop loops as the inner loop and outer loop, respectively,
`as depicted in Fig. 6(a). When in the stable state reported in
`bursts and
`is in the fail state,
`Fig. 6(b), in which
`’s
`both the outer and inner loops are broken, and hence,
`burst length is upper-bounded by ’s TCP congestion window.
`Conversely, when
`bursts, as in Fig. 6(c), only the
`outer loop is broken, and the inner loop is self-sustaining due
`to the loop’s own ACK generation. Consequently, the duration
`and
`to jointly capture the channel is not bounded.
`for
`As a result, the system spends much more time in the state in
`
`Illustration of multiple control loops and a shared medium. (a) Two
`Fig. 6.
`overlapping TCP congestion control loops are formed by TCP flows generated
`by A (outer loop), and B (inner loop). (b) When A enters the success state,
`mesh nodes A and B can transmit TCP DATA, but they cannot receive TCP
`ACKs from the destination GW . Hence, both control loops are open. (c) When
`B enters the success state, only the outer loop is open, and the inner loop is
`self-sustaining thanks to the TCP ACKs transmitted by node GW .
`
`which
`
`captures the channel than in the state in which
`captures the channel.
`In order to demonstrate the asymmetry between the two
`and
`. We
`states, we positioned two sniffers next to nodes
`used Kismet to capture all transmission attempts by the two
`nodes. We distinguish between transmissions initiated by trans-
`port-layer (TCP) and link-layer transmissions originated by
`the MAC. Accordingly, TCP transmissions include all new as
`well as retransmitted segments due to TCP timeout expiration,
`which are passed from the TCP layer to the MAC for trans-
`mission. MAC transmissions include all transmission attempts
`(successful and unsuccessful) by the MAC. In the following
`figures, each TCP segment transmission will be represented by
`the first MAC attempt to transmit that segment.
`Fig. 7(a) shows the progress of TCP segment transmission
`and
`, over
`(new and retransmitted segments) from nodes
`a 120-s experiment. The -axis depicts the segment sequence
`number, and the
`-axis describes the corresponding time each
`segment was transmitted. It can be seen in the figure that new
`segments from flow are continuously transmitted over time,
`while segments from flow are intermittently transmitted, in-
`cluding few long idle intervals. Fig. 7(b) depicts solely TCP re-
`transmissions from the two nodes. As can be seen in the figure,
`flow suffers from frequent TCP retransmissions, while flow
`experiences only three TCP retransmissions within the 2-min
`experiment. Note that since node
`is within transmission range
`and
`, all three retransmissions are due to
`of both nodes
`’s MAC. The asymmetry between the
`TCP ACK-drop at
`two flows in terms of both successful as well as unsuccessful
`segment transmissions is clearly depicted by the two figures.
`Severe Transition Penalties: Due to asymmetric bistable
`and
`experience different fail-state duration,
`states, nodes
`leading to a severe penalty only for the TCP flow originating
`. We described the three possible ways a node can
`from node
`is in the fail state, node
`exit its fail state. However, when
`’s limited burst is not likely to drive
`to drop a packet.
`will most likely exit its fail state by case 3); i.e.,
`Hence,
`the transmission queue of
`is emptied. The penalty that node
`
`Authorized licensed use limited to: Barbara Lange. Downloaded on December 27, 2009 at 23:02 from IEEE Xplore. Restrictions apply.
`
`

`
`1836
`
`IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 17, NO. 6, DECEMBER 2009
`
`Fig. 7. TCP segment transmissions (new segment transmissions plus TCP re-
`transmissions due to TCP timeout expiration) as captured by the sniffers next
`to nodes A and B. MAC retransmissions (due to MAC timeouts expiration) are
`not reported in the figures. (a) All TCP segment transmissions and retransmis-
`sions. (b) Only TCP retransmissions.
`
`Fig. 8. A sample of node A’s TCP (re)transmissions as captured by the sniffer
`next to node A. The severe penalty incurred by node A, due to MAC packet
`drop, can be seen in long idle periods due to long TCP timeouts for every TCP
`retransmission. Note that this idle period is exponentially increased for multiple
`drops of the same TCP segment because TCP timeouts are doubled after each
`drop.
`
`incurs is small due to short duration of its fail state. Fur-
`thermore, this penalty is shared by both TCP flow and TCP
`is in the fail state, the
`flow . On the other hand, when node
`inner loop is self-sustaining; hence, the gateway queue is rarely
`empty. Consequently, node most likely exits its fail state by
`case 2), i.e, by dropping the packet. The penalty node
`incurs
`is high, including both the long duration of its fail state (MAC
`penalty) and TCP timeout, a duration that grows exponentially
`with multiple drops of the same TCP segment. This penalty is
`only paid by TCP flow .
`Fig. 8 presents a sample of the TCP segment transmissions
`and retransmissions (excluding retransmissions initiated by
`MAC layer due to MAC timeouts). The severe penalty incurred
`due to MAC packet drop can be observed in the
`by node
`figure. For example, segment 318048 was retransmitted by the
`transport layer four times, which induced long TCP timeouts
`that resulted in long idle periods (in the order of seconds) due
`to small TCP congestion window.
`
`B. Broader Topology
`A variation of the basic topology is shown in Fig. 9(a), where
`and
`transmit a two-hop TCP flow and a one-hop TCP flow
`, respectively. In this case, although
`to the gateway node
`does not forward traffic for node
`, the same reasoning
`node
`of starvation origins applies. The gateway
`and
`are out of
`
`Fig. 9. Two-branch scenario and experimental TCP throughput with con-
`tending flows. (a) The scenario is composed of two branches: A ! B ! GW
`and includes a two-hop loop, and C ! GW , characterized by a one-hop
`control loop. (b) Despite the RTS/CTS handshake mechanism, a severe TCP
`throughput imbalance occurs between a two-hop flow on the two-hop branch
`and the one-hop flow on the other branch.
`
`and
`carrier sense range, yielding bistable behavior. When
`obtain the channel, the one-hop loop is self-sustaining. When
`and
`obtain the channel,
`is in fail state, and both loops
`is limited by its
`are broken. Consequently, the burst size of
`congestion window.
`To verify starvation in the scenario shown in Fig. 9(a), in TFA,
`besides nodes
`,
`, and
`we select another one-hop node
`[19]. As depicted in Fig. 9(a), two TCP flows are active on the
`and
`. Fig. 9(b) de-
`two branches,
`picts the result of the experiment and shows that starvation does
`persist in this two-branch topology. As expected, the behavior
`and
`is strictly
`of the TCP flow pair
`and
`analogous to the behavior of the pair
`discussed above.
`
`C. Discussion
`
`In mesh networks, the basic topology shown in Fig. 1 or its
`variation shown in Fig. 9(a) is necessarily embedded in larger
`scenarios such as long-chain and broad-tree topologies. In these
`larger scenarios, although there are other factors that affect the
`behavior of the contending flows, since all flows finally con-
`verge to the gateway, the embedded basic scenario plays an im-
`portant role in determining the throughput of each flow. Indeed,
`as shown later in Section V, our extensive experiments demon-
`strate it in a large set of scenarios, where one-hop flows starve
`multihop flows.
`Finally, we comment on the number of radios used in each
`mesh node. In our work, we consider one backhaul radio with
`or without a second access radio, thereby covering commercial
`architectures of Tropos, Cisco, Nortel, and others. Neverthe-
`less, with multiple radios, if the number of radios is not suffi-
`cient to allocate orthogonal channels to every interfering wire-
`less link, the results of this work are still pertinent. In fact, based
`on the previous subsection, whenever a two-hop transmitter is
`assigned the same channel with a one-hop transmitter, starva-
`tion can occur.
`
`IV. ANALYTICAL MODEL AND STARVATION SOLUTION
`
`Our proof of starvation in the basic topology is tiered. In
`Section II, we experimentally demonstrated the existence of
`TCP starvation in the basic topology. A more thorough measure-
`ment study of the starvation occurrence can be found in [19],
`where we experimentally isolate the originating starvation fac-
`tors by eliminating alternate explanations such as background
`
`Authorized licensed use limited to: Barbara Lange. Downloaded on December 27, 2009 at 23:02 from IEEE Xplore. Restrictions apply.
`
`

`
`GUREWITZ et al.: ORIGINS OF STARVATION OF CONGESTION-CONTROLLED FLOWS
`
`1837
`
`We assume that a node maintains a separate queue for each
`maintains three queues: two separate
`subflow; e.g., node
`queues for uplink TCP DATA originating from and locally
`generated by
`and a third queue for downlink TCP ACKs to
`. The resulting queuing system in the basic topology is
`node
`shown in Fig. 10. We modeled a round-robin scheduling disci-
`pline without memory constraints by assuming that each time a
`node gains channel access, backlogged queues are served with
`equal probability. We will show that while this system model
`omits many aspects of our experimental system, it nonetheless
`captures the behavior of the system and predicts the severe
`fairness imbalance between one-hop flows and two-hop flows.
`
`B. Model Description
`
`With the assumptions stated in Section IV-A, the system evo-
`lution can be modeled as a Markov chain embedded over con-
`tinuous time at the mini-slot boundaries in which the channel is
`idle from any transmission. Note that these time epochs char-
`acterize the beginning of eight different channel activity states,
`including three DATA transmission states occupied by an up-
`stream transmission on link 1, 2, or 3; three ACK transmission
`states occupied by a TCP ACK transmission on link 4, 5, or 6;
`one collision state for collisions between frames transmitted by
`and
`; and finally one idle state in which all the nodes
`count down their backoff counters and no transmission occurs.
`A schematic illustration of different channel activity states is
`given in Fig. 11, where the embedded time epochs in which we
`sample the system are pointed by arrows placed below the tem-
`poral axis. Note that the idle states last exactly one mini-slot as
`the next mini-slot defines a new state. Also, note that our model
`captures the behavior of CSMA with RTS/CTS handshake en-
`abled as well as without RTS/CTS; the difference between the
`two will be in the duration the system spends in each state.
`We label a transmission state using the index of the link on
`which this transmission occurs. For example, channel activity
`state 4 refers to transmission on link 4. We denote the duration
`of the transmission states, the collision state, and the idle state
`,
`, and
`, respectively.
`by
`We denote the length of the transmission queue for link as
`. Let
`denote the aggregate queue length at
`and
`be the fixed congestion windows
`node
`and
`, respectively. Note that
`for flows
`and
`are constant values. Because the middle node is in radio
`range of the two other nodes, the collision probability between
`the middle node and one of the other two nodes is very small,
`and
`.1 We
`compared to the collision probability between
`therefore assume that the middle node never doubles its backoff
`. Finally, the length of
`,
`,
`counter; i.e.,
`can be expressed with
`as
`and
`follows:
`
`, and let
`
`1To collide, the middle node has to send the first packet of a data transmission
`within the propagation delay of one of the outer nodes, given that both nodes
`choose to transmit on the same mini-slot.
`
`(1)
`
`Fig. 10. Queues at different mesh nodes and links in the basic topology.
`Node A only transmits TCP DATA to B using queue Q and link 1. Node B
`maintains two different queues for the TCP DATA packets generated by A
`(queue Q , forwarding on link 2), and by B (queue Q , transmitting on link 2),
`plus a queue for TCP ACKs to be forwarded to node A (queue Q , forwarding
`on link 6). Node GW uses two different queues, Q and Q , to transmit TCP
`ACKs on links 4 and 5 to nodes B and A, respectively.
`
`congestion and topology (hidden terminals with UDP traffic will
`not lead to starvation). In Section III, we logically explained
`the origins of starvation in the basic topology. In this section,
`we complete the validation of the starvation causes by analyt-
`ically proving the compounding effects of medium access and
`congestion control on TCP starvation in the same scenario in
`which UDP has been shown to behave fairly [9]. Mor