iDocSlide.Com

Free Online Documents. Like!

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Share

Description

Beyond Proportional Fairness: A Resource Biasing Framework for Shaping Throughput Profiles in Multihop Wireless Networks

Tags

Transcript

Beyond Proportional Fairness: A Resource BiasingFramework for Shaping Throughput Proﬁles inMultihop Wireless Networks
Sumit Singh, Upamanyu Madhow and Elizabeth M. Belding
University of California, Santa BarbaraEmail:
{
sumit@ece, madhow@ece, ebelding@cs
}
.ucsb.edu
Abstract
—Throughput performance of multihop wirelessnetworks is governed by how the network’s transport capacity(in bit-meters per second) is partitioned among differentnetwork ﬂows. Max-min fair allocation leads to poor throughputperformance for all ﬂows because connections traversing a largenumber of hops consume a disproportionate share of resources.While proportional fair allocation provides a signiﬁcantimprovement, we point out here that there is a much richerspace of resource allocation strategies for introducing a controlledbias against resource-intensive long connections in order tosigniﬁcantly improve the performance of shorter connections. Wepresent an analytical model that gives insight into the impact of aparticular resource allocation strategy on network performance,in a manner that captures the effect of ﬁnite network sizeand spatial trafﬁc patterns. Our simulation results demonstratethat it is possible to provide signiﬁcantly better performanceto shorter connections than max-min fair or proportional fairresource allocations, with minimal impact on the performanceof long connections, using
mixed bias
strategies blending “fair”allocations with a strong bias against long connections.
I. I
NTRODUCTION
We consider the problem of resource allocation in staticmultihop wireless networks. For a ﬁxed link rate and uniformtrafﬁc distribution where each node randomly chooses adestination, the number of hops and hence the amount of network resources required per-connection scales with network size. This spatial trafﬁc distribution results in obtainable per-connection throughput diminishing approximately as
O
(
1
√
N
)
because the network transport capacity only increases as
O
(
√
AN
)
[1], where
N
is the number of nodes and
A
is thenetwork deployment area. Implicit in this estimate of per-ﬂowthroughput, however, is the assumption that the resourceallocation to each connection is throughput-fair across thenetwork, which implies that connections that traverse a largernumber of hops (longer connections) consume signiﬁcantlymore network resources than those traversing fewer hops(shorter connections) to achieve the same end-to-end through-put. If we sidestep this fundamental assumption by biasingnetwork resource allocation against longer connections, thenshorter connections can achieve signiﬁcantly higher through-put at the cost of controlled performance degradation forlonger connections. In this paper, we introduce a rich class of resource allocation strategies based on this design philosophy.An existing strategy that falls within our framework is proportional fairness [2], in which, roughly speaking,a connection’s throughput is inversely proportional to thenumber of hops it traverses. As shown in our paper, however, itis possible to design the resource allocation strategy to choosefrom among a much larger class of ﬂow throughput proﬁles(i.e., ﬂow throughput versus the number of hops it traverses)while maintaining efﬁcient network utilization. For example,it is possible to signiﬁcantly improve the performance of shorter connections beyond that attained by proportionalfairness, while minimally degrading the performance of longer connections. Alternatively, the throughput for bothshort and long connections can be improved relative toproportional fairness, at the expense of slightly smallerthroughput for ﬂows traversing a moderate number of hops.A key contribution of this paper, which enables thepreceding ﬂexibility in shaping throughput proﬁles, is theintroduction of
mixed-bias
strategies, in which a fractionof the total available network resource is allocated via aresource allocation strategy that is strongly biased againstlong connections, with the remainder allocated in an unbiased(e.g., max-min fair) or mildly biased (e.g., proportional fair)manner. Note that such mixing is critical: a na¨ıve approachthat strongly biases against long connections can lead to poorperformance in a large network with spatially uniform trafﬁc.Another contribution of this paper is an analytical modelthat provides quick estimates of the throughput proﬁleachieved by a given resource allocation strategy. This providesa mechanism for the exploration of the rich design space of mixed bias strategies in trading off the performance seen byshort and long connections. Underlying our analytical frame-work is a two-scale model for multihop wireless networks.At the
global
scale, we observe that wireless plays a funda-mental role only in inﬂuencing the network topology: we areconstrained to use short distance hops due to considerations of power and spatial reuse. At this scale, elementary ﬂow calcula-tions treating node bandwidth shares (or data transfer capacity)as bit pipes sufﬁce to analyze the impact of various resourceallocation strategies. While our approach is based on ﬂowbalance at a “typical” node in a large network, it is also reﬁnedto account for the effect of ﬁnite network size and spatial trafﬁcpatterns. The effective node data transfer capacities used inthe preceding “wired-equivalent” global scale calculations areobtained from a detailed analysis of the wireless medium at the
local
scale, which takes into account contention among nodes.
Related Work:
Most prior work on resource allocation isbased on a utility function framework: a ﬂow attaining rate
r
obtains utility
U
(
r
)
, where
U
(
·
)
is concave, and the goal of resource allocation is to maximize the sum of the utilities overﬂows, subject to network resource constraints. Reference [3]proposes a class of utility functions that incorporates thecommonly used resource allocation policies including max-min fairness [4], proportional fairness [2], potential delay min-imization [5], and total throughput maximization. Our startingpoint is quite different, in that we explicitly assume that theresource allocation for a ﬂow is proportional to a speciﬁcdecreasing function of the number of hops traversed by a ﬂow,and then compute the proportionality constant via ﬂow bal-ance. However, our biasing strategies appear to be consistentwith a utility function framework, and we intend to explore thisconnection further in future work. Other relevant prior work includes a discussion of the tradeoff between network capacityand fairness for heterogeneous multihop wireless networks [6],which concludes with advocacy of proportional fairness asa reasonable compromise between rate efﬁciency andfairness, and also observes that max-min fairness yields poorperformance because all ﬂows obtain essentially the same rateas the minimum rate ﬂow. Reference [7] presents a realizationof proportional fairness based on end-to-end rate control fora connection based on the number of hops it traverses.II. R
ESOURCE
A
LLOCATION
F
RAMEWORK
We ﬁrst discuss the global scale analysis, which essentiallyinvolves ﬂow balance in a wired-equivalent network whosecapacities would be set by a local scale analysis. For auniform trafﬁc model, each node generates a persistent ﬂow,choosing a destination at random from among all othernodes. Our framework also accommodates spatially localizedtrafﬁc distributions in which the probability of choosing adestination depends on its number of hops from the source.The biased resource allocation problem is to assign bandwidthto each ﬂow as a function of its resource requirements (e.g.,number of hops it traverses) such that node data transfercapacity constraints are honored. Since it is intractable toidentify bottleneck links for randomized trafﬁc patterns, weapply an averaged analysis at the global scale to do ﬂowbalance for a “typical” node of the following form:
C
≥
h
max
h
=1
n
(
h
)
c
(
h
)
,
(1)where
C
is the available data transfer capacity of a node(in bits per-second),
n
(
h
)
is the average number of
h
-hopconnections traversing the node,
c
(
h
)
is the capacity assignedto
h
-hop ﬂows, and
h
max
is the maximum number of hops.For an
N
-node network,
h
max
=
O
(
N
)
for a linear topology,and
h
max
=
O
(
√
N
)
for a two-dimensional grid.For a uniform trafﬁc model, a typical node is more likelyto see a longer ﬂow (since such a ﬂow traverses more hops),so that
n
(
h
)
increases with
h
. It therefore makes sense tomake
c
(
h
)
a decreasing function of
h
, in order to ensurethat the sum in (1) converges even as the network size (andhence
h
max
) becomes large. A throughput proﬁle refers tothe dependence of
c
(
h
)
with
h
. Our goal is to explore thedesign space of throughput proﬁles that are feasible, in termsof meeting the link balance condition (1). For simplicity of exposition, we ﬁrst illustrate our framework with some quick global scale computations for a one-dimensional network in Section II-A. We then provide a more comprehensiveanalysis for a two-dimensional network which models theIEEE 802.11 network to be simulated.
A. Computations for a One-Dimensional Network
Consider a linear network with
N
nodes (arranged as aring to avoid edge effects) and
C
= 1
. For uniform trafﬁc,the probability of a connection initiated by any given nodetraversing
h
hops is
p
(
h
) =
1
N
−
1
,
h
= 1
,...,N
−
1
, since anyof the other
N
−
1
nodes in the network can be chosen withequal probability. The average number of
h
-hop connectionstraversing a node is
n
(
h
) =
hp
(
h
)
, so that ﬂow balance at atypical node becomes (assuming full utilization):
N
−
1
h
=1
hp
(
h
)
c
(
h
) = 1
(2)
Max-min fair allocation:
For max-min fair allocation, thebandwidth allocated to an
h
-hop connection is independent of
h
, so that
c
(
h
) =
λ
. Solving (2), we obtain
c
(
h
) =
λ
≈
2
N
.The sum throughput
T
sum
=
N
h
c
(
h
)
p
(
h
)
, summed overall connections, is approximately 2.
Proportional fair allocation:
Now consider the case when thebandwidth assigned to a connection is inversely proportional tothe number of hops it traverses; i.e.,
c
(
h
) =
λh
. Here
λ
denotesthe maximum allowed source application data rate (in bits per-second). This allocation can easily be shown to be proportionalfair [7]. Plugging this into (2), we obtain that
λ
≈
1
, so that
c
(
h
)
≈
1
h
. The sum throughput
T
sum
≈
log
N
. Thus, we havesigniﬁcantly improved both the sum throughput and the perfor-mance of shorter connections, with only a factor of two loss inthe throughput obtained by the longest connections. One canshow using typical link ﬂow analysis that the throughput of a
h
-hop connection is approximately
1
h
, with the sum throughputof
log
N
, and
λ
=
O
(1)
. Comparing with the max-min fairallocation, we realize that biasing against the long connectionsvia proportional fairness results in a win-win strategy: it leadsto far better performance for the shorter connections, whilereducing the throughput attained by the long connections onlyby roughly a factor of two. The cumulative effect of this isthe improvement of the total throughput by a factor of
log
N
2
compared to the max-min fair allocation.
The pitfalls of na¨ıve biasing:
Given the improvedperformance tradeoff offered by proportional fairness, it isnatural to ask if we can get still larger improvements bybiasing even more severely against the long connections.Consider a more severely biased allocation
c
(
h
) =
λh
2
.Substituting into (2), it can be shown that there is indeed again in sum throughput, but we require that
λ
=
O
(
N
log(
N
)
)
.
That is, the maximum ﬂow throughput must scale up withnetwork size, which is clearly not compatible with the ﬁnitecapacity of one. Basically, there are not enough short ﬂowsto take advantage of the transport capacity released by sucha strong bias. If we now impose the constraint that
λ
cannotscale up with
N
, we ﬁnd (details are provided for a two-dimensional model later) that the network is poorly utilized.
The promise of mixed biasing:
The problem with the pre-ceding biasing strategy was that the short connections wouldhave to send at too high a rate (more than the available link capacity) to take advantage of the bias. However, if we onlyallocate a small fraction of the available capacity to this biasingstrategy, then we can eliminate this problem. For example,consider a
mixed bias
strategy of the form
c
(
h
) =
λ
1
+
λ
2
h
2
; thismixes max-min fairness with a bias stronger than proportionalfairness. Let us assume that we use a proportion
α
1
of the nodedata transfer capacity to implement max-min fairness, and aproportion
α
2
= 1
−
α
1
to implement the stronger bias suchthat ﬂow balance decomposes into two separate equations:
N
−
1
h
=1
hp
(
h
)
λ
1
=
α
1
,
and
N
−
1
h
=1
hp
(
h
)
λ
2
h
2
=
α
2
.
Now, by choosing
α
2
to scale down with
N
, we can prevent
λ
2
from scaling up with
N
. Speciﬁcally, we can set
α
2
=
a
log
N N
,which will result in
λ
2
≈
a
, which no longer scales up with
N
.The resulting throughput proﬁle
c
(
h
)
is a convex combinationof the throughput proﬁles from the two different strategies:
c
(
h
)
≈
ah
2
+
1
−
a
log
N N
2
N .
(3)(Here we constrain
a
≤
1
so that the maximum throughputdoes not exceed the node/link capacity of one). We note that(3) provides a very different throughput proﬁle than eithermax-min fairness or proportional fairness. In particular, thethroughput seen by long connections is almost as good as thatof max-min fairness (and hence is a factor of two better thanthat obtained from proportional fairness), while the throughputseen by short connections does not scale down as a functionof
N
(and hence is better than max-min fairness). In short,mixed bias strategies open up a large design space not coveredby existing resource allocation strategies. We shall explore thisin more detail in our discussion of two-dimensional networks.
B. Two-Dimensional Networks
We now consider two-dimensional
N
node regular gridtopology networks where the inter-node distance is such thatdirect communication is only possible between immediateneighbors on the grid. The hop distance
h
(
i,j
)
betweentwo nodes
i
and
j
equals the number of hops along theshortest path between the nodes. We consider a power-lawtrafﬁc model [8], in which the probability that a node
i
will communicate with a node
j
,
h
hops away, is given by
p
i,j
=
ah
k
, where
0
< a <
1
. Thus, the probability
p
H
(
h
)
that a pair of communicating nodes are
h
hops apart is givenby
p
H
(
h
) =
m
(
h
)
/
(
h
k
h
max
r
=1
m
(
r
)
r
k
)
, where
m
(
h
)
is thenumber of
h
-hop ﬂows in the network. For
k >
0
, this trafﬁcdistribution models a spatially localized trafﬁc pattern. Weconsider uniformly distributed trafﬁc (
k
= 0
) to study theeffect of different resource biasing policies.We focus on allocation of the available data transfer capacity
C
of a typical network node using link ﬂow analysis toobtain the expected per-connection throughput. The underlyingmedium access control (MAC) layer (e.g., IEEE 802.11) im-plements max-min fair bandwidth allocation among contend-ing nodes. The bias weight function
w
(
h
)
is deﬁned as
w
(
h
) =
1
h
b
, where the bias exponent
b
≥
0
determines the degree of bias. Let
n
(
h
)
denote the average number of
h
-hop ﬂows pass-ing through or initiated by a typical network node. We have
C
≥
h
max
h
=1
n
(
h
)
λh
b
.
(4)Thus, the required
λ
for maximum utilization of the availablecapacity is given by
λ
=
C/
h
max
h
=1
n
(
h
)
h
b
. We ﬁrst consider asymmetric, regular grid (i.e., a 2-d torus) topology to avoidedge effects, and focus on how the required
λ
scales with in-creasing network size as a function of the trafﬁc model and thebias weight function. For a symmetric regular grid topology,
p
H
(
h
) = 1
/
(
h
(
k
−
1)
h
max
r
=11
r
(
k
−
1)
)
. Using
n
(
h
) =
hp
H
(
h
)
,
λ
=
C
h
max
h
=1
hp
H
(
h
)
/h
b
=
C
h
max
h
=1
1
/h
(
k
−
1)
h
max
h
=1
1
/h
(
k
+
b
−
2)
.
(5)For uniform trafﬁc distribution (
k
= 0
), we infer that withunbiased resource allocation (
b
= 0
),
λ
=
O
(1
/
√
N
)
; forproportional fairness (
b
= 1
), we have
λ
=
O
(1)
; andfor
b
= 2
,
λ
=
O
(
√
N
)
. Further calculations show that therequired
λ
grows with the network size
N
for
b >
1
. However,since
λ
cannot exceed the maximum stable data rate
s
of anode, this means that after the network size increases to acertain limit for
b >
1
, a node cannot fully utilize its fair shareof bandwidth because the stronger bias prevents long ﬂowsfrom using the leftover capacity from the short ﬂows. As inthe linear network case, we infer that with proportional fairresource allocation, the per-ﬂow throughput will be higher thanthe unbiased resource allocation for any
N
since the required
λ
is
O
(1)
. The preceding analysis also applies to inﬁniteregular grid topologies where edge effects can be neglected.We now consider ﬁnite, regular grid topologies where thecontention at the network edges is less than the core becausethere are fewer contending nodes at the edges; also, with auniform trafﬁc model where every node randomly picks adestination among other network nodes, it is easy to show thatthe trafﬁc volume increases towards the core of the network.Therefore, the network core acts as a bottleneck for network ﬂows in most cases. Hence, we focus on the network-coreto avoid offsets from the edge effects. We expect that theﬂow throughput results obtained from analysis of the network core are pessimistic estimates of the actual ﬂow throughputs,especially for smaller networks (e.g.,
N <
50
) where the edgeeffect dominates. Based on these observations, we modify (4)as follows:
C
≥
h
max
h
=1
n
c
(
h
)
min
(
λh
b
,s
)
,
(6)
where
n
c
(
h
)
denotes the average number of
h
-hop ﬂowspassing through or initiated by a typical network-core node.We evaluate
n
c
(
h
)
by averaging the values obtained fromMatLab simulations of trafﬁc instances over the network for5000 seed values. Thus, we can calculate the maximum
λ
that satisﬁes (6) for a given bias exponent
b
. This
λ
value canbe used to estimate the average per-ﬂow throughput
T
of thenetwork as a function of the network size, trafﬁc distributionand the resource allocation policy as follows:
T
=
h
max
h
=1
p
H
(
h
)
min
(
λh
b
,s
)
.
(7)
Mixed Bias Resource Allocation Policy:
The underlying ideais to allocate a portion of the total available capacity at a nodevia a strongly biased policy, and allocate the rest employing afairer policy. Assume that, of the total available node capacity
C
, we allocate
αC
via a resource allocation policy determinedby weight function
w
1
(
h
) =
1
h
b
1
, and allocate the remainingbandwidth via weight function
w
2
(
h
) =
1
h
b
2
. We calculate themaximum
λ
1
and
λ
2
that satisfy the following inequalities:
αC
≥
h
max
h
=1
n
c
(
h
)
min
(
λ
1
h
b
1
,s
)
,
(8)
C
≥
h
max
h
=1
n
c
(
h
)
min
(
λ
1
h
b
1
+
λ
2
h
b
2
,s
)
.
(9)The average per-ﬂow throughput in this case is given by:
T
=
h
max
h
=1
p
H
(
h
)
min
(
λ
1
h
b
1
+
λ
2
h
b
2
,s
)
.
(10)The parameters
α
,
b
1
and
b
2
allow us to span a large designspace of resource allocation strategies, trading off throughputperformance versus fairness.III. A
PPLICATION TO AN
IEEE 802.11 N
ETWORK
We now apply our resource allocation framework to anIEEE 802.11 multihop network to illustrate how to determineglobal-scale parameters from local-scale analysis, which takesinto account physical layer technology and medium accesscontrol (MAC). We then employ simulations to determinehow well the design prescriptions obtained by analysis work.For our local-scale analysis, Bianchi’s saturation throughputanalysis [9] is used to determine the data transfer capacity
S
of a contention region in an IEEE 802.11 network. Based on theobservation that the IEEE 802.11 MAC protocol implementsan approximation to max-min fair bandwidth allocation amongcontending neighbors [6], [10], a typical node’s share of singlehop capacity can be estimated as
C
=
S/n
c
, where
n
c
is theaverage number of contending nodes in a contention regionat the network core. This value of
C
is now used in (6) in theglobal-scale analysis to estimate
λ
. This is then plugged into(7) to obtain the average per-ﬂow throughput. Fig. 1 illustratesthe predicted average per-ﬂow throughput for an examplemixed bias allocation with
b
1
= 5
,
b
2
= 1
(proportionalfairness) and
α
=
0.2, for the individual allocation policies in
050100150200250050100150200250300350Number of nodes
A v e r a g e p e r − f l o w t h r o u g h p u t ( K b p s )
Mixed bias (
α
= 0.2)b
1
= 5b
2
= 1 (Proportional fairness)Max−min fairness
Fig. 1. Average per-ﬂow throughput for mixed bias with
b
1
= 5
,
b
2
= 1
,and
α
=
0.2 from analysis.
0 50 100 150 200 250 300 350 0 50 100 150 200 250
A v e r a g e p e r - f l o w t h r o u g h p u t ( K b p s )
Number of nodesMixed bias (
α
= 0.2)b
1
= 5b
2
= 1 (Proportional fairness)Max-min fairness
Fig. 2. Average per-ﬂow throughput for mixed bias with
b
1
= 5
,
b
2
= 1
,and
α
=
0.2 from simulations.
the mixture and also for max-min fair allocation. We observethat the mixed bias allocation has a higher average ﬂowthroughput as compared to proportional fair and max-minfair allocations. Evaluation for different
α
values showsthat increasing
α
to a higher value emphasizes strong biaswhereas decreasing
α
to a smaller value such as 0.2 sways thethroughput more towards the fairer allocation in the mixture.We now employ simulations to obtain ﬂow throughputproﬁles, and to evaluate the beneﬁts of mixed bias strategiesrelative to the individual strategies in the mixture, as wellas to proportional fairness. We use the QualNet Network Simulator [11] over regular grid topology networks withIEEE 802.11 MAC in basic access mode. We present ourresults with static routing in order to isolate the effects of routing overhead on throughput. The results are averaged over20 different seeds. Our application model comprises CBRﬂows of packet size of 1000 bytes, with data rates determinedanalytically for a given biasing strategy, as in Section II-Band enforced using source data rate control. Destinations arechosen at random based on the uniform trafﬁc model.While we ﬁx the offered rate based on the analyticalmodel in order to compare different resource allocationstrategies, an important topic for future work is to allownodes to dynamically tune their ﬂow rates while imple-menting a biased resource allocation strategy. This can beused to alleviate congestion, to exploit spatial reuse op-portunities, and more broadly, to react to speciﬁc network topologies and trafﬁc patterns. Embedding mixed-bias re-source allocation strategies within a utility function frame-work may provide the ﬂexibility needed to arrive at decen-
0.01 0.1 1 10 100 1000 10000 0 5 10 15 20 25
F l o w t h r o u g h p u t ( K b p s )
Number of hopsb = 1
(a) Proportional fairness (
b
= 1
).
0.01 0.1 1 10 100 1000 10000 0 5 10 15 20 25
F l o w t h r o u g h p u t ( K b p s )
Number of hopsb = 5
(b)
b
= 5
.
0.01 0.1 1 10 100 1000 10000 0 5 10 15 20 25
F l o w t h r o u g h p u t ( K b p s )
Number of hopsMixed bias (
α
= 0.2)
(c) Mixed (
b
1
= 5
, b
2
= 1
, α
= 0
.
2
).
-2-1 0 1 2 3 4 0 5 10 15 20 25
F l o w t h r o u g h p u t ( l o g
1 0
( K b p s ) )
Number of hopsMixed bias (
α
= 0.2)
(d) Mixed (
b
1
= 5
, b
2
= 0
, α
= 0
.
2
).Fig. 3. Scatterplots of ﬂow throughputs for a 144-node network for mixed bias allocations, proportional fairness and severe bias (
b
= 5
).
tralized adaptive implementations that achieve the precedinggoals.Fig. 2 illustrates the per-ﬂow throughput performance forthe example mixed bias allocation considered in Section II-B(
b
1
= 5
,b
2
= 1
,α
= 0
.
2
) and compares it with that of the single bias policies in the mixture and also max-minfair allocation. The results are consistent with the analyticalprediction that the mixed bias allocation provides higheraverage ﬂow throughput than max-min fair or proportionalfair allocations. However, the average ﬂow throughput valuesare lower, and decay faster with network size, than theanalytical predictions shown in Fig. 1. This is because ﬂowsincur higher packet loss probabilities as they traverse a largernumber of hops in a larger network, which results in anincrease in the amount of wasted network resources. Anotherfactor causing performance degradation that is not explicitlymodeled in the analysis is the waste of medium access timedue to the interaction between the IEEE 802.11 backoff mechanism and multihop packet forwarding [12].Fig. 3 presents the scatterplots of individual ﬂow through-puts as functions of the number of hops for a 144-nodenetwork over all simulation seeds. We consider a mixed biasstrategy, mixing a strong bias with proportional fairness. Thestrategy leads to signiﬁcantly higher throughput for shorterconnections than proportional fairness, while incurring virtu-ally no degradation for the longer connections. Other desirablemixed bias strategies that, for example, provide better perfor-mance for long connections than proportional fairness, can beobtained by mixing a strongly biased strategy with max-minfairness (e.g., Fig. 3(d)). Note that the strongly biased strategyshuts out the long connections, and is therefore not a feasiblechoice on its own. The choice of the capacity fraction
α
andthe strength
b
of the bias are other parameters at the disposalof the system designer to craft a desirable throughput proﬁle.IV. C
ONCLUSIONS
Our resource biasing framework opens up a rich designspace for sharing transport capacity in multihop wirelessnetworks that goes beyond existing paradigms such asmax-min fairness and proportional fairness. The simpletwo-scale model provides quick performance estimates fordifferent biasing strategies, providing a tool that allows systemdesigners to tune parameters so as to shape throughput proﬁleswhile maintaining network efﬁciency. For 802.11 networkswith ﬁxed link speeds, the global scale, wired-equivalentmodel provides predictions of throughput proﬁles that matchtrends obtained by simulation. Important topics for futureresearch include generalization of the framework to allowfor multiple raw link speeds (which may complicate theinteraction between the local-scale and global-scale models),and the design of efﬁcient protocols for implementing theseresource allocation strategies in a manner that adapts to thenetwork topology and trafﬁc pattern. In particular, embeddingour strategies within a utility function framework may leadto simple decentralized implementations (e.g., via end-to-endrate control), analogous to the approach of Kelly [2].A
CKNOWLEDGMENTS
This work was supported in part by NSF Grant CCF-0431205, ONR Grant N00014-06-1-0066, NSF Career AwardCNS-0347886 and NSF NeTS Award CNS-0435527.R
EFERENCES[1] P. Gupta and P. R. Kumar, “The Capacity of Wireless Networks,”
IEEE Trans. Inform. Theory
, vol. 46, no. 2, pp. 388–404, 2000.[2] F. Kelly, A. Maulloo, and D. Tan, “Rate Control In CommunicationNetworks: Shadow Prices, Proportional Fairness and Stability,”
J. Op-erational Research Soc.
, vol. 49, pp. 237–252, 1998.[3] J. Mo and J. Walrand, “Fair End-to-End Window-based CongestionControl,”
IEEE/ACM Trans. Netw.
, vol. 8, no. 5, pp. 556–567, 2000.[4] L. Tassiulas and S. Sarkar, “Max-Min Fair Scheduling in WirelessNetworks,” in
Proc. IEEE INFOCOM’02
, New York City, NY, June2002, pp. 763–772.[5] L. Massouli and J. Roberts, “Bandwidth Sharing: Objectives and Algo-rithms,”
IEEE/ACM Trans. Netw.
, vol. 10, no. 3, pp. 320–328, 2002.[6] B. Radunovic and J.-Y. L. Boudec, “Rate Performance Objectives of Multihop Wireless Networks,”
IEEE Trans. Mob. Comput.
, vol. 3, no. 4,pp. 334–349, 2004.[7] A. Velayutham, K. Sundaresan, and R. Sivakumar, “Non-pipelined RelayImproves Throughput Performance of Wireless Ad-Hoc Networks.” in
Proc. IEEE INFOCOM’05
, Miami, FL, March 2005, pp. 477–490.[8] N. Zhou, H. Wu, and A. A. Abouzeid, “The Impact of Trafﬁc Patternson the Overhead of Reactive Routing Protocols,”
IEEE J. Sel. AreasCommun.
, vol. 23, no. 3, pp. 547–560, Mar. 2005.[9] G. Bianchi, “Performance Analysis of the IEEE 802.11 DistributedCoordination Function,”
IEEE J. Sel. Areas Commun.
, vol. 18, no. 3,pp. 535–547, March 2000.[10] M. Heusse, F. Rousseau, G. Berger-Sabbatel, and A. Duda, “Perfor-mance Anomaly of 802.11b,” in
Proc. IEEE INFOCOM’03
, vol. 2, SanFrancisco, CA, March-April 2003, pp. 836–843.[11] (2005) Qualnet Network Simulator, version 3.9. [Online]. Available:http://www.scalable-networks.com[12] J. Li, C. Blake, D. S. J. De Couto, H. I. Lee, and R. Morris, “Capacityof ad hoc wireless networks,” in
Proc. Mobicom’01
, Rome, Italy, July2001, pp. 61–69.

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks