See discussions, stats, and author profiles for this publication at: [Link]

net/publication/221242398

Fairness and Optimal Stochastic Control for Heterogeneous Networks

Conference Paper in IEEE/ACM Transactions on Networking · January 2005

DOI: 10.1109/TNET.2007.900405 · Source: DBLP

CITATIONS READS
424 1,467

3 authors, including:

Michael J. Neely Chih-ping Li

University of Southern California Massachusetts Institute of Technology
46 PUBLICATIONS 6,494 CITATIONS 21 PUBLICATIONS 1,361 CITATIONS

SEE PROFILE SEE PROFILE

All content following this page was uploaded by Chih-ping Li on 14 March 2014.

The user has requested enhancement of the downloaded file.

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 16, NO. 2, APRIL 2008, PP. 396-409 1

Fairness and Optimal Stochastic Control

for Heterogeneous Networks
Michael J. Neely , Eytan Modiano , Chih-ping Li

Abstract— We consider optimal control for general networks B

with both wireless and wireline components and time varying A C
channels. A dynamic strategy is developed to support all traffic 8 5
0 1
whenever possible, and to make optimally fair decisions about 6
(3)
which data to serve when inputs exceed network capacity. The λ9 9
strategy is decoupled into separate algorithms for flow control, 4 2
routing, and resource allocation, and allows each user to make 3
(1)
decisions independent of the actions of others. The combined λ9 7
strategy is shown to yield data rates that are arbitrarily close to
the optimal operating point achieved when all network controllers (8) (2)
are coordinated and have perfect knowledge of future events. The λ4 λ4
cost of approaching this fair operating point is an end-to-end (5) (5)
(5) R3 (t) U3 (t)
delay increase for data that is served by the network. λ3
Index Terms— Wireless Networks, Stochastic Optimization, valve node 3
Queueing Analysis, Distributed Computing, Satellite Networks

Fig. 1. (a) A heterogeneous network with wireless and wireline data links,
and (b) a close-up of one node, illustrating the internal queues and the storage
I. I NTRODUCTION reservoir for exogenous arrivals.

Modern data networks consist of a variety of heterogeneous

components, and continue to grow as new applications are
developed and new technologies are integrated into the existing model with slots normalized to integral units t ∈ {0, 1, 2, . . .}.
communication infrastructure. While network resources are Channels hold their state for the duration of a timeslot, and
expanding, the demand for these resources is also expanding, potentially change states on slot boundaries. For simplicity of
and it is often the case that data links are loaded with more exposition, we assume there are a finite (but arbitrarily large)
traffic than they were designed to handle. In order to provide number of possible channel state vectors, and that the vectors
high speed connectivity for future personal computers, hard- ~
S(t) are independent and identically distributed (i.i.d.) over
ware devices, wireless units, and sensor systems, it is essential timeslots. We note that the algorithms we design under this
to develop fair networking techniques that take full advantage i.i.d. assumption can be applied to yield similar performance
of all resources and system capabilities. Such techniques must for systems with general ergodic channel state variations.
be implemented through simple, localized message passing For each channel state S, ~ let Γ ~ denote the set of link
S
protocols between neighboring network elements. transmission rates available for resource allocation decisions
In this paper, we design a set of decoupled algorithms ~
when S(t) ~ In particular, every timeslot t the network
= S.
for resource allocation, routing, and flow control for general controllers are constrained to choosing a transmission rate
networks with both wireless and wireline data links and time vector µ ~ (t) ∈ ΓS(t)
~ (t) = (µ1 (t), . . . , µL (t)) such that µ ~
varying channels. Specifically, we treat a network with N (where µl (t) is the transmit rate over link l and has units
nodes and L links. The condition of each link at a given time t of bits/slot). Use of this abstract set of transmission rates
~ = (S1 (t), . . . , SL (t)),
is described by a link state vector S(t) ΓS~ maintains a simple separation between network layer and
where Sl (t) is a parameter characterizing the communication physical layer concepts, yet is general enough to allow network
channel for link l. For example, if l is a wireless link, Sl (t) control to be suited to the unique capabilities of each data link.
may represent the current attenuation factor or noise level. We assume all sets ΓS~ are compact (closed and bounded).
In an unreliable wired link, Sl (t) may take values in the As an example, consider the heterogeneous network of Fig.
two-element set {ON, OF F }, indicating whether link l is 1 consisting of three separate groups of links A, B, and C:
available for communication. We consider a slotted system Set A represents a wireless sensor system that connects to
a wired infrastructure through two uplink access points, set
Michael J. Neely is with the Department of Electrical Engineering,
University of Southern California, Los Angeles, CA 90089 USA (email: B represents the wired data links, and set C represents the
mjneely@[Link], web: [Link] two downlink channels of a basestation that transmits to two
E. Modiano is with the Laboratory for Information and Decision Systems, different users 1 and 2. For a given channel state S, ~ the set
Massachusetts Institute of Technology, Cambridge, MA 02139 USA (email:
modiano@[Link]). C. Li is with the Department of Electrical Engineering, of feasible transmission rates ΓS~ reduces to a product of rates
University of Southern California. corresponding to the three independent groups:
This work was presented in part at the IEEE INFOCOM conference,
March 2005, and is based in part on the Ph.D. dissertation of the first author
(Massachusetts Institute of Technology, 2003). ΓS~ = ΓA
S
B C
~ × Γ × ΓS
~ (1)
A C
IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 16, NO. 2, APRIL 2008, PP. 396-409 2

Set ΓA ~A might contain a continuum of link rates associated

S
optimization could in principle be solved if the arrival rates
(c)
with the channel interference properties and power allocation (λn ) and the capacity region Λ were known in advance, and
options of the sensor nodes, and depends only on the link all users could coordinate by sending data according to the
states S ~A of these nodes. Set ΓB might contain a single optimal solution. However, the capacity region depends on
vector (C1 , . . . , Ck ) representing the fixed capacities of the the channel probabilities, which are unknown to the network
k wired links. Set ΓC S~C might represent a set of two vectors controllers and to the individual users. Furthermore, the in-
{(φS1 , 0), (0, φS2 )}, where φSi is the rate available over link i dividual users do not know the data rates or utility functions
if this link is selected to transmit on the given timeslot t when of other users. In this paper, we develop a practical dynamic
(c)
Si (t) = Si . We further note that the ground network shown in control strategy that yields a resulting set of throughputs (rn )
the figure can be augmented to include a collection of satellite that are arbitrarily close to the optimal solution of (2)-(4). The
nodes, increasing route diversity and enabling connectivity to distance to the optimal solution is shown to decrease like 1/V ,
other sub-networks. where V is a control parameter affecting a tradeoff in average
Data is transmitted from node to node over potentially delay for data that is served by the network.
multi-hop paths to reach its destination. Data arrives to the Previous work on network fairness and optimization is
network according to random processes with well defined time found in [5]-[17]. Utility optimization problems similar to (2)-
(c) (3) are considered for static wireless downlinks with infinite
average rates, and we let λn represent the long term average
rate of new exogenous arrivals to source node n intended for backlog in [5], and for static multi-hop wireless networks in
(c) [8]. Further static resource allocation problems for wireless
destination node c (in units of bits/slot). Let (λn ) be the
matrix of exogenous arrival rates. The network layer capacity and wireline systems are treated in [6]-[17]. Much of this work
region Λ is defined as the closure of the set of all arrival ma- uses convex optimization and Lagrangian duality to achieve a
trices that are stably supportable by the network, considering fixed resource allocation that is optimal with respect to various
all possible multi-hop routing and resource allocation policies utility metrics. In [12] [13], distributed pricing mechanisms are
(possibly those with perfect knowledge of future events). We used to provide proportional fairness in static flow networks.
emphasize that, while the channel states may change from slot Control laws based on continuous time differential equations
to slot, the set Λ is fixed and depends only on the steady state are used in [13] [16] to ensure flows converge to a utility
channel probabilities and the link transmission rate sets ΓS~ [1] optimal operating point, and dual sub-gradient methods are
[28]. considered in [14]. The relationship between duality theory,
The set Λ can be shown to be compact and convex [1]. In utility optimization, and classical internet congestion control
[28], a routing and power allocation policy was developed to techniques is explored in [17].
stabilize a general wireless network whenever the rate matrix We note that fixed allocation solutions may not be ap-
(c)
(λn ) is within the capacity region Λ. The purpose of our propriate in cases when optimal control involves dynamic
current paper is to treat heterogeneous networks and develop resource allocation. Dynamic policies might be required for
distributed algorithms for flow control, routing, and resource optimality even when the underlying network is static [19].
allocation that provide optimal fairness in cases when arrival The capacity of a multi-user wireless downlink with randomly
rates are either inside or outside the network capacity region. varying channels is established in [34], and utility optimization
(c)
Specifically, we define a set of utility functions gn (r), in a similar system is treated in [18]. These formulations do
representing the “satisfaction” received by sending data from not consider stochastic arrivals and queueing, and the resulting
node n to node c at a time average rate of r bits/slot. The utility algorithms are developed and analyzed under the assumption
functions are assumed to be non-decreasing and concave. The that channel probabilities are fully known.
(c) The design of dynamic controllers to stabilize stochastic
goal is to support a fraction of the traffic demand matrix (λn )
(c) wireless and wireline networks is considered in [20]-[28]
to achieve long term throughputs (rn ) that maximize the sum
using a powerful theory of Lyapunov drift. However, this
of user utilities. The optimal sum utility is thus defined by the
work primarily addresses queueing stability and does not
following optimization problem:
provide methods for achieving both stability and performance
P (c) (c) optimization, as required to solve the general fairness problem
Maximize: n,c gn (r n ) (2)
(c)
(2)-(4) for stochastic networks. Dynamic algorithms for fair
Subject to: (rn ) ∈ Λ (3) scheduling in wireless downlinks are addressed in [30] [31]
(c) (c)
0≤ rn ≤ λn for all (n, c) (4) [32], but do not yield optimal performance for all input rates,
as discussed in the next section. A special case solution of
Inequality (3) is the stability constraint and ensures that the (2)-(4) is developed in [33] for a class of wireless downlinks
long term admitted rates are stabilizable by the network. with linear utility functions and ON/OFF channels.
Inequality (4) is the demand constraint that ensures the rate The main contribution of our work is the development
provided to session (n, c) is no more than the incoming traffic of a novel control policy that yields optimal performance
rate of this session. for general stochastic networks and general fairness metrics.
(c)
Because the functions gn (r) are non-decreasing, it is clear The policy does not require knowledge of channel statistics,
(c)
that if (λn ) ∈ Λ, then the above optimization is solved by the input rates, or the global network topology. Our analysis
∗(c) (c) (c) ∗(c)
matrix (rn ) = (λn ). If (λn ) ∈ / Λ, then the solution (rn ) establishes a new and important Lyapunov drift technique that
will lie somewhere on the capacity region boundary. The above enables stability and performance optimization to be achieved
IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 16, NO. 2, APRIL 2008, PP. 396-409 3

simultaneously, extending the stability results developed in fairness). We evaluate three well known algorithms with
[20]-[28]. This work presents a fundamental approach to respect to this fairness metric: The Borst algorithm [30], the
stochastic network optimization [1] [2] [3] [4]. We note ‘proportionally fair’ Max µi /ri algorithm [31] [32], and the
that alternative optimization approaches have recently been MWM policy [21].
considered in [29] [35] using fluid limit models, and in [36] The Borst algorithm chooses the non-empty channel i with
using stochastic gradient theory (see, for example, [37]). Our the largest µi (t)/µi index, where µi (t) is the current transmis-
Lyapunov optimization technique is related to the theory of sion rate offered over channel i, and µi is the average of µi (t).
static and stochastic gradients (see Chapters 4.7-5.7 of [1]). This algorithm is shown in [30] to provide optimal fairness
However, our techniques were developed within the framework for wireless networks with an “infinite” number of channels,
of Lyapunov stability theory for queueing systems, and yield where each incoming packet is destined for a unique user with
explicit network utility and delay guarantees. its own channel. Although the algorithm was not designed for
In the next section, we illustrate the challenges of stochastic the 2-queue downlink described above, it is closely related
network optimization with a simple downlink example. In to the Max µi /ri policy, and it is illuminating to evaluate its
Section III we develop a fair scheduling algorithm for general performance in this context. Applied to the 2-queue downlink,
networks under the special case when all active input reser- the Borst algorithm reduces to serving the non-empty ON
voirs are “infinitely backlogged.” In Section V we construct a queue with the largest value of 1/pi . Because p1 < p2 , this
modified algorithm that yields optimal performance without algorithm effectively gives packets destined for channel 1 strict
the infinite backlog assumption. This is another important priority over channel 2 packets. Thus, the service of queue 1 is
contribution of our paper, and our solution illuminates the independent of the state of channel 2, and conditioning on the
differences between optimizing an expectation and optimizing event that a packet is served from channel 1 during a particular
a concave function of an expectation. Example simulations for timeslot does not change the probability that channel 2 is ON.
wireless networks and N × N packet switches are presented It follows that the rate of serving channel 1 packets while
in Section VI, and distributed implementation strategies for channel 2 is ON is given by λ1 p2 (assuming queue 1 is stable
wireless networks are discussed in Section VII. so that all λ1 traffic is served). Thus, the stability region of
the Borst algorithm is given by:
II. A S ATELLITE D OWNLINK E XAMPLE λ 1 ≤ p1 , λ 2 ≤ p2 − λ 1 p2 (5)
Consider a satellite node (or wireless basestation) that which is a strict subset of the capacity region (see Fig. 2).
transmits data to two downlink users 1 and 2 over two different Consider now the related policy of serving the non-empty
channels (as illustrated by considering only the triangle-node queue with the largest value of µi (t)/ri (t), where ri (t)
of the network in Fig. 1). Time is slotted and packets for is the empirical throughput achieved over channel i. This
each user arrive to the basestation according to independent differs from the Borst algorithm in that transmission rates
Bernoulli processes with rates λ1 and λ2 . Let U1 (t) and are weighted by the throughput actually delivered rather than
U2 (t) represent the current backlog of packets waiting for the average transmission rate that is offered. This Max µi /ri
transmission to user 1 and user 2, respectively. Channels policy is proposed in [31] [32] and shown to have desirable
independently vary between ON and OFF states every slot proportional fairness properties when all queues of the down-
according to Bernoulli processes, with ON probabilities p1 and link are infinitely backlogged. To evaluate its performance for
p2 , and we assume that p1 < p2 . Every timeslot, a controller arbitrary traffic rates (λ1 , λ2 ), suppose the running averages
observes the channel states and chooses to transmit over either r1 (t) and r2 (t) are accumulated over the entire timeline, and
channel 1 or channel 2. We assume that a single packet can be suppose the system is stable so that r1 (t) and r2 (t) converge
transmitted if a channel is ON and no packet can be transmitted to λ1 and λ2 . It follows that the algorithm eventually reduces
when a channel is OFF, so that the only decision is which to giving channel 1 packets strict priority if λ1 < λ2 , and
channel to serve when both channels are ON. giving channel 2 packets strict priority if λ2 < λ1 . Thus, if
The capacity region Λ for this system is described by the λ1 < λ2 then these rates must also satisfy the inequalities
set of all rates (λ1 , λ2 ) that satisfy: (5), while λ2 < λ1 implies the rates must satisfy the inverted
λ1 ≤ p1 , λ2 ≤ p2 , λ1 + λ2 ≤ p1 + (1 − p1 )p2 inequalities λ2 ≤ p2 and λ1 ≤ p1 − λ2 p1 . Thus, at first glance
it seems that the stability region of this policy is a subset of the
These conditions are necessary for stability because the long stability region of the Borst algorithm. However, its stability
term output rate from any channel i is at most pi , and the region has the peculiar property of including all feasible rate
maximum sum rate out of the system is p1 + (1 − p1 )p2 . pairs (λ, λ) (see Fig. 2).
Furthermore, it is shown in [21] that the ‘Maximum Weight In Fig. 2 we consider the special case when p1 = 0.5, p2 =
Match’ (MWM) policy of serving the ON queue with the 0.6, and plot the achieved throughput of the Borst, Max
largest backlog achieves stability whenever input rates are µi /ri , and MWM policies when the rate vector (λ1 , λ2 ) is
strictly interior to the above region. scaled linearly towards the vector (0.5, 1.0), illustrated by the
Now define g1 (r) = g2 (r) = log(r), and consider the pro- ray in Fig. 2(a). One hundred different rate points on this
portional fairness control objective of maximizing log(r1 ) + ray were considered (including example points a - e), and
log(r2 ), where r1 and r2 are the delivered throughputs over simulations were performed for each point over a period of 5
channels 1 and 2 (see [12] for a discussion of proportional million timeslots. Fig 2(a) illustrates the resulting throughput
IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 16, NO. 2, APRIL 2008, PP. 396-409 4

MWM path
λ2 e λ2 e"
about routing, scheduling, and resource allocation in reaction
d d to current channel state and queue backlog information. The
0.5 c proportionally 0.5 c
µ/r path objective is to deliver all data to its proper destination,
fair point
d' d'
e'
potentially by routing over multi-hop paths.
b e' b
It is often useful to restrict routing options so that data
0.3 Borst path 0.3
follows a particular path or set of paths to the destination. To
a a
enforce this constraint, for each commodity c ∈ {1, . . . , N }
0.1
Borst Stability
Region 0.1
µ/r Stability
Region
we define Lc as the set of all data links l that are acceptable
for commodity c data to traverse. As a general algorithm
λ1 λ1 might schedule multiple commodities to flow over the same
0.1 0.3 0.5 0.1 0.3 0.5 (c)
link on a given timeslot, we define µl (t) as the rate offered
Fig. 2. The downlink capacity region Λ and the stability regions of the Borst to commodity c traffic along link l during timeslot t.1 The
policy and the Max µi /ri policy. Input rates (λ1 , λ2 ) are pushed toward point transmission rates and routing variables are chosen by a
(0.5, 1.0), and the simulated throughputs under the Borst, Max µi /ri , and dynamic scheduling and routing algorithm. Specifically, the
MWM policies are illustrated.
network makes the following control decisions every slot:
• Resource (Rate) Allocation: Choose a transmission rate

of the Borst algorithm, where we have included example points vector µ ~ (t) ∈ ΓS(t)
~ (t) = (µ1 (t), . . . , µL (t)) such that µ ~
d0 and e0 corresponding to input rate points d and e. Note • Routing/Scheduling: For each link l and each commodity
(c)
that the Borst algorithm always results in throughput that is c, choose µl (t) to satisfy the following constraints:
strictly interior to the capacity region, even when input rates X (c)
µl (t) ≤ µl (t) (6)
are outside of capacity. Fig. 2(b) illustrates performance of
c
the Max µi /ri and MWM policies. Note that the MWM (c)
policy supports all (λ1 , λ2 ) traffic when this rate vector is µl (t) = 0 if l ∈
/ Lc (7)
within the capacity region. However, when traffic is outside We note that defining all sets Lc to be equal to the set of all
of the capacity region the achieved throughput moves along network links effectively removes the routing cosntraints (7)
the boundary in the wrong direction, yielding throughputs and reduces to the case of unconstrained routing. This creates
that are increasingly unfair because it favors service of the the most options, although it is often useful to constrain routes
higher traffic rate stream. Like the Borst policy, the Max µi /ri via the Lc sets to ensure more predictable performance and
policy leads to instability for all (stabilizable) input rates on maintain FIFO or near FIFO delivery. For example, in cases
the ray segment c-d, and yields throughput that is strictly where the network topology is fixed and it is desirable to route
interior to the capacity region even when inputs exceed system all data associated with a particular source-destination pair
capacity (compare points e and e0 ). However, the throughput over a single path, then the sets Lc can be defined as a tree of
eventually touches the capacity region boundary, reaching links from each source to the destination c. In cases where it
the proportionally fair point (0.4, 0.4) when input rates are is preferred to have two or more different sources of the same
sufficiently far outside of the capacity region. commodity use paths that cross but do not merge, then this
It is clear from this simple downlink example that there single “commodity” can be re-defined as several commodities
is a need for a universally fair algorithm, one that performs to distinguish the different source-destination pairs (which also
well regardless of whether inputs are inside or outside of the (c)
increases the total number of distinct queues Un (t) in the
capacity region. For this example, such an algorithm would network).
yield throughput that increases toward the point d of the figure, A set of flow controllers act at every node to limit the
and then moves on the boundary of the capacity region toward new data admitted into the network layer. Specifically, new
the fair operating point thereafter. In the following, we develop data of commodity c that arrives to source node n is first
such an algorithm for general multihop networks. placed in a transport layer storage reservoir (n, c). A control
(c)
valve determines the amount of data Rn (t) released from this
III. C ONTROL OF H ETEROGENEOUS N ETWORKS (c)
reservoir on each timeslot (see Fig. 1). The Rn (t) process
(c)
Consider a heterogeneous network with N nodes, L links, acts as the exogenous arrival process to the queue Un (t).
and time varying channels S(t)~ (see example in Fig. 1). Each Endogenous arrivals consist of commodity c data transmitted
link l ∈ {1, . . . , L} represents a directed communication to node n from other network nodes. Define Ωn as the set of
channel for transmission from one node to another, and we all links l such that tran(l) = n, and define Θn as the set
define tran(l) and rec(l) as the corresponding transmitting of all links such that rec(l) = n. Every timeslot the backlog
(c)
and receiving nodes, respectively. Each node of the network Un (t) changes according to the following queueing law:
maintains a set of output queues for storing data according to (c)
h
(c) P (c)
i
its destination. All data (from any source node) that is destined Un (t + 1) ≤ max Un (t) − l∈Ωn µl (t), 0
for a particular node c ∈ {1, . . . , N } is classified as commodity P (c) (c)
(c) + l∈Θn µl (t) + Rn (t) (8)
c data, and we let Un (t) represent the backlog of commodity
c data currently stored in the network layer at node n (see 1 We find that the capacity achieving solution needs only route a single
Fig. 1). A network layer control algorithm makes decisions commodity over any given link during a timeslot.
IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 16, NO. 2, APRIL 2008, PP. 396-409 5

The expression above is an inequality rather than an equal- In [1] [28], the network capacity region Λ is characterized
ity because the endogenous arrivals may be less than for the special case of unconstrained routing, where the
P (c)
l∈Θn µl (t) if nodes have little or no commodity c data to
constraints (7) are removed. It is not difficult to extend this
transmit. The above dynamics hold for all node pairs n 6= c. result to include routing constraints (7). We thus state the
Data leaves the network when it reaches its destination, and following modified version of the network capacity theorem
(n) M
so we define Un (t)= 0 for all n and all t. from [1] [28], omitting the proof for brevity.
(c)
Let An (t) represent the new commodity c data arriving Theorem 1: (Network Capacity) If channels S(t) ~ are i.i.d.
(c) (c)
to the system at source node n during slot t, and let Ln (t) over slots, a fixed input rate matrix (rn ) is in the capacity
(c)
represent the current backlog in the flow control reservoir at region Λ if and only if rn = 0 for all (n, c) ∈ / D and there
(c)
time t. The control decision variables Rn (t) are chosen every exists a stationary randomized resource allocation algorithm
∗(c)
timeslot according to the following restrictions: that chooses particular transmission rates µl (t) based only
(c) ~
on the current channel state S(t), and satisfies for all slots t:
• Flow Control: Choose Rn (t) such that:
( )
Rn(c) (t) ≤ L(c) (c) X ∗(c) X ∗(c)
n (t) + An (t) for all t E µl (t) − µl (t) | U (t) = rn(c) ∀n 6= c
X
Rn(c) (t) ≤ Rnmax for all t l∈Ωn l∈Θn
∗(c)
c µl (t) = 0 if tran(l) = c or if l ∈
/ Lc
where the constants Rnmax are chosen to be positive and (c)
where U (t) = (Un (t)) represents the matrix of current queue
suitably large, to be made precise in the development of our
backlogs.
two different flow control strategies CLC1 and CLC2. The
The above expectation is taken over the probability distri-
first flow control constraint ensures that admitted data is less ~
bution of the current channel state S(t) and the distribution
than or equal to the actual data available, and the second is
of the randomized resource allocation decisions that depend
important for limiting the burstiness of the admitted arrivals.
on this channel state. Because channels are i.i.d., the above
expectation is the same every slot t, and does not depend on
A. The Network Capacity Region U (t). The expectation is intentionally conditioned on U (t) as
the existence of a policy that satisfies this exact equality will be
Due to the routing constraints (7), some commodities might
used later. It can be shown that the capacity region Λ depends
never be able to visit certain nodes. Further, some nodes might
only on the steady state channel probability distribution [1]
only be associated with destinations, and hence these nodes
[28], and hence the region Λ described by Theorem 1 is
do not keep any internal queues. Hence, we define Kn as
unchanged if actual channels are non-i.i.d. but are ergodic with
the number of internal queues kept by node n, where Kn ∈
the same steady sate distribution as in the i.i.d. case.
{0, 1, . . . , N − 1}. Define D as the set of all node-commodity
The capacity region Λ can be shown to be compact and
pairs (n, c) associated with internal queues in the network, and
convex with D effective dimensions (see [1] for a similar
let D represent the number of such queues:
result). It shall be useful to define the parameter µsym to be the
N
X largest rate that is simultaneously supportable by all sessions
M (c) (c)
D= Kn (n, c) ∈ D, so that (µsym 1n ) ∈ Λ (where 1n is equal
n=1 to 1 if (n, c) ∈ D, and zero else). Geometrically, the value
The integer D defines the relative dimension of the network. µsym represents the edge size of the largest D-dimensional
We assume that all active traffic sessions are within the set D, hypercube that can be fit into the capacity region Λ, and is
(c) M (c) M
so that Rn (t)= 0, gn (r)= 0 for all (n, c) ∈
/ D. We further a value that unexpectedly arises in our analysis. We assume
(c) M throughout that µsym > 0.
define Un (t)=0 for all t when (n, c) ∈ / D.
Suppose the admitted traffic from each flow
control valve (n, c) has a well defined time average B. Dynamic Control for Infinite Demand
(c) M 1
Pt−1 n (c) o
rn = limt→∞ t τ =0 E Rn (τ ) . The network layer Here we develop a practical control algorithm that stabilizes
capacity region Λ is the set of all time average rate matrices the network and ensures that utility is arbitrarily close to
(c) optimal, with a corresponding tradeoff in network delay. Recall
(rn ) that the network can stably support, considering all
(c)
possible routing and resource allocation algorithms that that functions gn (r) represent the utility of supporting rate r
(c)
satisfy the constraints (6)-(7) and the queueing dynamics (8) communication from node n to node c (we define gn (r) = 0
described above. Stability of a queue with general arrival and if there is no active session of traffic originating at node n and
transmission rate processes is defined as follows: destined for node c). To highlight the fundamental issues of
Definition 1: A queue U (t) with general stochastic arrival routing, resource allocation, and flow control, in this section
and transmission rate processes is strongly stable if: we assume that all active sessions (n, c) have infinite backlog
(c)
t−1
in their corresponding reservoirs, so that flow variables Rn (t)
1X can be chosen without first establishing that this much data is
lim sup E {U (τ )} < ∞
t→∞ t available in the reservoir. Flow control is imperative in this
τ =0
That is, we define strong stability (hereafter called “stability”) infinite backlog scenario, and the resulting problem is simpler
in terms of a finite time average backlog. as it does not involve the demand constraint (4). A modified
IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 16, NO. 2, APRIL 2008, PP. 396-409 6

algorithm is developed in Section V for the general case of each node i knows the backlog levels of its P neighbors. The
(c)
finite demand matrices (λn ) and finite buffer reservoirs. resource allocation strategy of maximizing l Wl∗ (t)µl (t) is
The following control strategy is decoupled into separate the most complex part of the algorithm, but can be distributed
algorithms for resource allocation, routing, and flow control. over the independent portions of the network (as in (1)), or
The strategy combines a novel flow control technique together can be approximated as described in Section VII.
with a generalization of the Dynamic Routing and Power
Control (DRPC) strategy of [28]. C. Intuitive Description of the Policy
Cross-Layer Control Algorithm 1 (CLC1):
The flow control policy (9) uses a parameter V that de-
• Flow Control — (algorithm FLOW) Every timeslot, the
termines the extent to which utility optimization is empha-
flow controller at each node n observes the current level
(c) sized. Indeed, if V is large relative to the current backlog
of queue backlogs Un (t) for each commodity c ∈ (c)
(c) in the source queues, then the admitted rates Rn (t) will be
{1, . . . , N }. It then chooses Rn (t) as the solution of an
(c) large, increasing the time average utility while consequently
optimization problem. Specifically, it chooses Rn (t) = increasing congestion. This effect is mitigated as backlog
(c) (c)
xn , where the xn values solve the following: grows at the source queues and flow control decisions become
N h
X i more conservative. The routing and scheduling algorithm uses
Maximize : V gn(c) (x(c) (c) (c)
n ) − 2xn Un (t) (9) backpressure from neighboring nodes to route in directions
c=1 of the largest differential backlog. Below we show that the
N
X algorithm can be used to drive network utility arbitrarily
Subject to: (x(c)
n )≥0 , x(c) max
n ≤ Rn (10) close to optimal by suitably increasing the V parameter, with
c=1 a corresponding increase in network congestion. Intuitively,
where V > 0 is a chosen constant that affects the congestion grows because more “learning time” is required
performance of the algorithm. to achieve a finer and finer optimization. The queue backlogs
and backlog differentials will help the controllers learn “good”
• Routing and Scheduling — Each node n observes directions to route and “good” amounts of data to admit, and
the backlog in all neighboring nodes j to which it is the “noise” of fluctuating queues will have less influence when
connected by a link l (where tran(l) = n, rec(l) = j). queue sizes are large. We note that in our more recent work
(c) (c) (c)
Let Wl (t) = Utran(l) (t) − Urec(l) (t) represent the [38], we characterize the fundamental tradeoff between utility
differential backlog of commodity c data. Define and delay.
M (c)
Wl∗ (t)= max[c| l∈Lc ] {Wl (t), 0} as the maximum
differential backlog over link l (maxed with 0), and D. Algorithm Performance
let c∗l (t) represent the maximizing commodity. Data of
To analyze the performance of the above CLC1 algorithm,
commodity c∗l (t) is selected for (potential) routing over
we define the maximum transmission rates out of and into a
link l whenever Wl∗ (t) > 0.
given node n as follows:
• Resource Allocation — The current channel state S(t) ~ is µout M
X
µl , µin M
X
max,n = max max,n = max µl
observed, and a Ptransmission rate vector µ~ (t) is selected ~ µ∈Γ ~ ]
[S,~ ~ µ∈Γ ~ ]
[S,~
S l∈Ωn S l∈Θn
by maximizing l Wl∗ (t)µl (t) subject to the constraint
We assume that each node n knows its own value of
~ (t) ∈ ΓS(t)
µ ~ . The resulting transmission rate of µl (t) is
µout
max,n , which is reasonable as nodes would typically have
offered to commodity c∗l (t) data on link l (provided that
a pre-specified set of modulation and coding strategies to
Wl∗ (t) > 0). If any node does not have enough bits of
choose from, with a well defined maximum. Assume that the
a particular commodity to send over all outgoing links
flow control constants Rnmax are selected to satisfy Rnmax ≥
requesting that commodity, null bits are delivered.
µout
max,n for all n. As Rn
max
is only used at node n, it can
The flow control algorithm is decentralized, where the (c)
easily be set to satisfy this inequality. Assume utilities gn (r)
control valves for each node n require knowledge only of
are non-negative, non-decreasing, and concave, and define
the queue backlogs in node n. We note that the constraint M P (c) (c)
P (c) max Gmax = max[P r(c) ≤Rmax ∀n] n,c gn (rn ). Define the con-
c Rn (t) ≤ Rn (for all n) in the flow control optimiza- c n n

tion (9) can be replaced with the simpler and less restrictive stant B as follows:
(c) N
constraint Rn (t) ≤ Rnmax (for all (n, c)), allowing for each M 1 X  max
(Rn + µin 2 out 2

(c)
Rn (t) value to be obtained by maximizing a concave function B= max,n ) + (µmax,n ) (11)
N n=1
of one variable. However, this would increase the delay bound
(presented in Theorem 2 of the next subsection) roughly by Theorem 2: If channel states are i.i.d. over timeslots and
a factor equal to the largest number of distinct commodities all active reservoirs have infinite backlog, then for any flow
that are sourced at any single node. An appropriate value to parameter V > 0 the CLC1 algorithm stabilizes the network
assign the Rnmax constant is discussed in Section III-D. and yields the following performance bounds:2
The routing and scheduling algorithm acts according to 2 The algorithms developed in this paper yield similar results for general
a differential backlog strategy similar to the backpressure ergodic channel processes, where the B parameter in (12) and (13) is increased
strategy developed in [20], and is decentralized provided that by an appropriate factor T related to steady state “mixing times” [1] [28].
IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 16, NO. 2, APRIL 2008, PP. 396-409 7

and Chapter 4.3.6 of [1]). It is also closely related to a

X (c) BN + V Gmax similar “imperfect scheduling” result developed for utility
Un ≤ (12)
n,c
2µsym optimization in [15] from a convex programming perspective.

X X BN E. Maximum Throughput and the Threshold Rule

lim inf gn(c) (r(c)
n (t)) ≥ gn(c) (rn∗(c) ) − (13) (c) (c)
t→∞ V Suppose utilities are linear, so that gn (r) = αn r for
n,c n,c (c)
some non-negative weights αn . The resulting objective is
∗(c)
where (rn ) is the optimal solution of (2) subject to constraint to maximize the weighted sum of throughput, and the re-
(3), and where: sulting FLOW algorithm has a simple threshold form, where
t−1
" # some commodities receive as much of the Rnmax delivery
X (c)
M 1 X X n (c) o rate as possible, while others receive none. In the special
Un = lim sup E Un (τ )
t→∞ t case where the user at node n desires communication with
n,c τ =0 n,c
(c)
t−1 a single destination node cn (so that gn (r) = 0 for all
M 1 X n (c) o c 6= cn ), the flow control algorithm (9) reduces to maximizing
r(c)
n (t) = E Rn (τ ) (14)
t τ =0 (c ) (c )
V αn n r −2Un n r subject to 0 ≤ r ≤ Rnmax , and the solution
The above result holds for all V > 0. Thus, the value of is the following threshold rule:
V can be chosen so that BN/V is arbitrarily small, resulting (
(c ) V α(cn )
in achieved utility that is arbitrarily close to optimal. This Rn(cn ) (t) = Rnmax if Un n (t) ≤ 2n
performance comes at the cost of a linear increase in network 0 otherwise
congestion with the parameter V . By Little’s theorem [39], The qualitative structure of this flow control rule is intu-
average queue backlog is proportional to average bit delay, itive: When backlog in the source queue is large, we should
and hence performance can be pushed towards optimality with refrain from sending new data. The simple threshold form is
a corresponding tradeoff in end-to-end network delay. qualitatively similar to the threshold scheduling rule developed
The proof of Theorem 2 follows from a novel Lyapunov in [33] for server scheduling in a downlink with ON/OFF
drift argument, where the utility metric is incorporated into channels and deterministic constraints on the channel states
the drift condition so that stability and utility optimization and packet arrivals.
can be simultaneously achieved. This analysis is provided in
Section IV. Below we present a simple corollary that is useful F. Proportional Fairness and the 1/U Rule
in characterizing the performance of CLC1 under suboptimal (c)
Consider now utility functions of the form gn (r) = log(1+
resource allocations (proved at the end of Section IV). (c)
Corollary 1: If the resource allocation policy of CLC1 is βrn ) (for some constant β > 0). It is shown in [12] that
replaced with any (potentially randomized) resource allocation maximizing a sum of such utilities over any convex set Λ
policy µ~ (t) that satisfies the following for all slots t: leads to proportional fairness.3 In the special case when there
! is only one destination cn for each user n, the flow control
(c )
X
∗
X
∗ algorithm reduces to maximizing V log(1 + βr) − 2Un n r
Wl (t)E {µl (t) | U (t)} ≥ θ max Wl (t)µl − C subject to 0 ≤ r ≤ Rnmax , which leads to the following ‘1/U ’
~ ∈ΓS(t)
µ ~
l l
flow control function:
for some fixed constants θ and C such that 0 < θ ≤ 1 and " " # #
V 1 max
C ≥ 0, then Rncn (t) = min max (c )
− , 0 , Rn
2Un n (t) β
X (c) 2C + BN + V Gmax
Un ≤ (15) Here we see that the flow control valve restricts flow according
n,c
2µsym θ
to a continuous function of the backlog level at the source
queue, being less conservative in its admission decisions when
X X 2C + BN backlog is low and more conservative when backlog is high.
lim inf gn(c) (r(c)
n (t)) ≥ gn(c) (r̃n∗(c) ) − (16)
t→∞
n,c n,c
V One drawback of this 1/U policy is that the resulting flow
(c)
∗(c)
control variables Rn (t) are real numbers (not necessarily
where (r̃n ) is the optimal solution to the following opti- integers or integer multiples of a given packet length), and
mization: hence it is implicitly assumed that packets can be fragmented
P (c) (c) for admission to the network. The CLC2 algorithm presented
Maximize: n,c gn (rn ) (17)
in Section V overcomes this issue.
(c)
Subject to: (rn ) ∈ θΛ 3 Strictly speaking, the proportionally fair allocation seeks to maximize
(c) (c) ∗(c) (c)
0 ≤ rn ≤ λ n P
n,c
(c)
log(rn ), leading to
P
n,c
r n −rn
∗(c) ≥ 0 for any other operating
rn
That is, allocating resources to come within a factor θ of (c)
point (rn ) ∈ Λ. We use non-negative utilities log(1+βr) and thereby obtain
the optimal solution of the CLC1 resource allocation yields a ∗(c)
a proportionally fair allocation with respect to the quantity r n + 1/β, lead-
utility that is close to the optimal utility with respect to a θ ∗(c) (c)
ing to n,c rn∗(c)−rn ≥ 0. This can be used to approximate proportionally
P
scaled version of the capacity region. The above corollary is rn +1/β
fair scheduling for large β. Alternatively, it can be used with β = 1, yielding
related to similar “sub-optimal” Lyapunov scheduling results a utility function log(1 + r) which is different from proportionally fair utility
presented for stability analysis (see, for example, [40] [41], but still has many desirable fairness properties.
IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 16, NO. 2, APRIL 2008, PP. 396-409 8

IV. P ERFORMANCE A NALYSIS The utility bound (21) is proved similarly. Indeed, we again
Here we prove Theorem 2. We first develop a novel Lya- rearrange (22) and divide by M V to yield:
punov drift result enabling stability and performance optimiza- X 1 M −1 n
X o B + E {L(U (0))} /M
tion to be performed using a single drift analysis. E gn(c) (Rn(c) (τ )) ≥ g ∗ −
n,c
M τ =0
V
A. Lyapunov Drift with Utility Metric (c)
(c)
By concavity of gn (r) togethern with Jensen’s o
Let U (t) = (Un (t)) represent a process of queue backlogs inequality, it follows that M 1
PM −1
E g
(c)
(R
(c)
(τ )) ≤
n n
that evolves according to some probability law, and define  P n o τ =0
(c) 2 (c) (c) 1 M −1 (c)
gn M τ =0 E Rn (τ ) . Using this fact in the left
P
the Lyapunov function L(U ) = n,c (Un ) . Let Rn (t)
represent an input process affecting the system, and suppose hand side of the above inequality and taking the lim inf as
P (c) (c) M → ∞ yields the result.
these values are bounded so that n,c gn (Rn (t)) ≤ Gmax
for all t (for some value Gmax ). Assume utility functions The above lemma suggests that a good control strategy is
(c) to greedily minimize the following drift metric every timeslot:
gn (r) are non-negative and concave, and let g ∗ represent a
“target utility” value. For a given queue backlog vector U (t), X n o
we define the conditional Lyapunov drift ∆(U (t)) as follows: ∆(U (t)) − V E gn(c) (Rn(c) (t)) | U (t)
n,c
M
∆(U (t))= E {L(U (t + 1)) − L(U (t)) | U (t)} (18) This is indeed the principle behind our control algorithm. To
where the conditional expectation is with respect to the random begin, we first develop an expression for Lyapunov drift from
one-step queueing dynamics given the current backlog U (t). the queueing dynamics (8). First note that any general queue
Lemma 1: (Lyapunov Optimization) If there are positive with backlog U (t) and queueing law U (t + 1) = max[U (t) −
constants V, , B such that for all timeslots t and all unfinished µ(t), 0] + A(t) has a Lyapunov drift given by:
work matrices U (t), the Lyapunov drift satisfies: 
E U 2 (t + 1) − U 2 (t) | U (t) ≤ µ2max + A2max
n o
(c) (c)
−2U (t)E {µ(t) − A(t) | U (t)} (23)
P
∆(U (t)) − V n,c E gn (Rn (t)) | U (t) ≤ B
(c)
− n,c Un (t) − V g ∗ (19) where Amax and µmax are upper bounds on the arrival
P
and server variables A(t) and µ(t). This well known fact
then time average utility and congestion satisfies: follows simply by squaring the queueing equation and taking
t−1 expectations. Applying the general formula (23) to the specific
1 X X n (c) o B + V Gmax
lim sup E Un (τ ) ≤ (20) queueing law (8) for queue (n, c) and summing the result over
t→∞ t τ =0 n,c  all (n, c) pairs yields the following expression for Lyapunov
X
∗ B drift (see [1] [28] for details):
lim inf gn(c) (r(c)
n (t)) ≥ g − (21)
t→∞
n,c
V X
(
X (c)
∆(U (t)) ≤ N B − 2 Un(c) (t)E µl (t)
(c)
where rn (t) is defined in (14). n,c l∈Ωn
Proof: Assume that (19) [Link] expectations over
)
(c)
X
the distribution of U (t) and using the definition of ∆(U (t)) − µl (t) − Rn(c) (t) | U (t) (24)
in (18) together with the law of iterated expectations yields: l∈Θn

where B is defined in (11).

n o
P (c) (c)
E {L(U (t + 1)) − L(U (t))} − V n,c E gn (Rn (t)) ≤
n o Now define the flow function Ψ(U (t)) and the network
(c)
B −  n,c E Un (t) − V g ∗ function Φ(U (t)) as follows:
P
X n o
M
The above holds for all timeslots t. Summing over t ∈ Ψ(U (t))= E V gn(c) (Rn(c) ) − 2Un(c) Rn(c) | U (25)
{0, 1, . . . , M − 1} yields: n,c
( )
(c) (c)
X X X
M
E {L(U (M ))} − E {L(U (0))} Φ(U (t))= 2 Un(c) E µl − µl |U (26)
PM −1 P n o
(c) (c) n,c l∈Ωn l∈Θn
−V τ =0 n,c E gn (R n (τ )) ≤ BM
(c) (c)
PM −1 P n o where we have represented U (t), µl (t),
and Rn (t) as
(c)
− τ =0 E U (τ ) − V M g ∗ (22) (c) (c)
U , µl , and Rn for notational
n convenience. o Subtracting the
n,c n
P (c) (c)
Using non-negativity of the Lyapunov function and the utility utility component V n,c E gn (R n ) | U from both sides
(c) (c)
functions as well as the fact that n,c gn (Rn (τ )) ≤ Gmax , of (24) yields:
P
we rearrange the terms of (22) and divide by M  to yield: P n
(c) (c)
o
∆(U (t)) − V n,c E gn (Rn (t)) | U ≤
M −1
1 X X n (c) o E {L(U (0))} B + V Gmax N B − Φ(U (t)) − Ψ(U (t)) (27)
E Un (τ ) − ≤
M τ =0 n,c M 
Given a particular U (t) matrix at time t, the CLC1 policy
Taking the lim sup as M → ∞ yields the backlog bound (20). is designed to greedily minimize the right hand side of (27)
IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 16, NO. 2, APRIL 2008, PP. 396-409 9

over all possible routing, resource allocation, and flow control as a solution to the following optimization problem:4
options. We therefore have the following lemma: P (c) (c)
Maximize : n,c gn (rn ) (32)
Lemma 2: The Ψ(U (t)) and Φ(U (t)) functions satisfy:
(c)
Subject to: (rn ) ∈ Λ
Xh i
(c) (c)
ΨCLC1 (U (t)) ≥ V gn(c) (rn∗(c) ) − 2Un(c) (t)rn∗(c) (28) rn ≤ λn for all (n, c)
n,c
( This optimization differs from the optimization in (2)-(4) in
Φ CLC1
(U (t)) ≥ 2
X
Un(c) (t)E
X ∗(c)
µl (t)− that the set Λ is replaced by the set Λ .
n,c l∈Ωn
Lemma 3: (Continuity of Near-Optimal Solutions) If utility
(c)
) functions gn (r) are non-negative and concave, and if there
∗(c) is a positive scalar µsym such that (µsym ) ∈ Λ, then:
X
µl (t) | U (t) (29)
X X
l∈Θn
gn(c) (rn∗(c) ()) → gn(c) (rn∗(c) ) as  → 0 (33)
n,c n,c
∗(c)
where (rn ) are any particular values that satisfy (10) for all Proof: The proof uses convexity of the capacity region Λ,
∗(c) and is given in Chapter 5.5.2 of [1].
n, and (µl (t)) are any particular (potentially randomized)
routing and resource allocation decisions at time t.
That the CLC1 flow control strategy (9) maximizes Ψ(U (t)) C. Derivation of Theorem 2
(c)
over all feasible choices of the Rn (t) values follows immedi- The proof of Theorem 2 relies on the following two in-
ately by comparing (9) and (25). That the routing and resource equalities:
allocation policy of CLC1 maximizes Φ(U (t)) is proven in Xh i
[1] [28], and can be understood by switching the sums in the ΨCLC1 (U (t)) ≥ V gn(c) (rn∗(c) ()) − 2Un(c) (t)rn∗(c) ()
n,c
definition of Φ(U (t)): X
X X n (c) oh i ΦCLC1 (U (t)) ≥ 2 Un(c) (t)(rn∗(c) () + ) (34)
(c) (c)
Φ(U (t)) = 2 E µl (t) | U Utran(l) − Urec(l) n,c

l c ∗(c)
(30) where (rn ()) is the optimal solution of problem (32). The
∗(c) ∗(c)
Therefore, if ΦCLC1 (U (t)) represents the above function first inequality follows from (28) by using rn = rn (),
(c) noting that these are valid flow control choices because 1)
when the rates µl (t) are chosen at time t according to
∗
CLC1, and if Φ (U (t)) represents the above Φ(U (t)) function all reservoirs are infinitely backlogged and so it is always
∗(c) (c) ∗(c)
when any alternate feasible rates µl (t) are chosen at time possible to choose Rn (t) = rn (), and 2) the matrix
∗(c) P ∗(c)
t (possibly via randomization), then from (30) we have: (rn ()) is within Λ and hence c rn () ≤ Rnmax for all
∗(c)
n. Inequality (34) follows by plugging the particular µl (t)
n
∗(c)
o ∗(c) (c)
policy of Theorem 1 (for (rn () + 1n ) ∈ Λ) into (29).
XX
Φ∗ (U (t)) ≤ 2 E µl (t) | U (t) Wl∗ (t)
l c Plugging the above two inequalities directly into the drift
≤ ΦCLC1 (U (t)) (31) expression (27) yields the following for algorithm CLC1:
X n o
(c) (c)
∆(U (t)) − V E gn(c) (Rn(c) (t)) | U ≤ N B
where Wl∗ (t) = max[Utran(l) (t) − Urec(l) (t), 0]. n,c
X
−2 Un(c) (t)(rn∗(c) () + )
n,c
B. A Near-Optimal Operating Point
X X
−V gn(c) (rn∗(c) ()) +2 Un(c) (t)rn∗(c) ()
n,c n,c
In order to use the Lyapunov drift result to establish the
performance of the CLC1 algorithm, it is important to first Canceling common terms yields:
compare performance to the utility of a near-optimal solution X n o
∆(U (t)) − V E gn(c) (Rn(c) (t)) | U ≤ N B
to the optimization problem (2)-(4). Specifically, for any  > 0,
n,c
we define the set Λ as follows: X X
−2 Un(c) (t) − V gn(c) (rn∗(c) ())
n o
M n,c n,c
Λ = (rn(c) ) | (rn(c) + 1(c) (c)
n ) ∈ Λ, rn ≥ 0 for all (n, c)
The above drift expression is in the exact form specified by
(c) Lemma 1. Thus, network congestion satisfies:
where 1n is equal to 1 whenever (n, c) ∈ D, and zero X (c)
else. Thus, the set Λ can be viewed as the resulting set Un ≤ (N B + V Gmax )/(2) (35)
of rate matrices within the network capacity region when n,c
an “-layer” of the boundary is stripped away from the D (c) (c)
4 Note that the final constraint (r
effective dimensions. Note that this set is compact and non- n ) ≤ (λn ) is satisfied automatically
in the case of infinite traffic demand. We include the constraint here as this
empty whenever  ≤ µsym (where µsym is defined in Section optimization is also important in the treatment of general traffic matrices
∗(c) (c)
III-A). The near-optimal operating point (rn ()) is defined (λn ) in Section V.
IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 16, NO. 2, APRIL 2008, PP. 396-409 10

(c)
and time average performance satisfies: Define flow state variables Zn (t) for each reservoir (n, c),
(c)
X X and fix Zn (0) = V Rnmax /2 for all (n, c) (any initial condi-
lim inf gn(c) (r(c)
n (t)) ≥ gn(c) (rn∗(c) ()) − N B/V (36)
t→∞ tion can be used, this one works well experimentally). For
n,c n,c (c)
each flow control process Rn (t), we define a new process
The performance bounds in (35) and (36) hold for any (c)
Yn (t) as follows:
value  such that 0 <  ≤ µsym . However, the particular
M max
choice of  only affects the bound calculation and does Yn(c) (t)=Rn − Rn(c) (t) (37)
not affect the CLC1 control policy or change any sample (c) (c)
and note that ≥ 0 for all t. The
Yn (t) Yn (t)
variables
path of system dynamics. We can thus optimize the bounds
represent the difference between the maximum value and
separately over all possible  values. The bound in (36)
the actual value of admitted data on session (n, c). The
is clearly maximized by taking a limit as  → 0, so that (c)
P (c) ∗(c) Zn (t) state variables are updated every slot according to the
the right hand side converges to n,c gn (rn ) − N B/V
following ‘queue-like’ iteration:
(using (33)). Conversely, the bound in (35) is minimized as
(c)
Zn(c) (t + 1) = max[Zn(c) (t) − γn(c) (t), 0] + Yn(c) (t) (38)
P
 → µsym , yielding: n,c Un ≤ (N B + V Gmax )/(2µsym ).
This proves Theorem 2.  (c)
where {γn (t)}are additional flow control decision variables.
Define the ‘cost’ function:
The proof of Corollary 1 follows by noting that the sub-
M (c)
optimal allocation bound changes inequality (29) into: h(c) max
n (γ)=gn (Rn ) − gn(c) (Rnmax − γ) (39)
(
(c)
CLC1
X
(c)
X ∗(c) Let γn
represent the time average value of the decision
Φ (U (t)) ≥ −2C + 2 Un (t)E θµl (t)− (c)
n,c
variables γ n (t). We design a policy to stabilize the network
l∈Ωn (c) (c)
) queues Un (t) and the flow state ‘queues’ Zn (t) while mini-
X ∗(c) P (c) (c)
θµl (t) | U (t) mizing the cost n,c hn (γ n ). The intuitive interpretation of
(c)
l∈Θn this goal is as follows: If the Zn (t) queues are stabilized, it
which thus changes inequality (34) into: must be the case that the time average of the ‘server process’
(c)
X γn (t) is greater than or equal to the time average of the
ΦCLC1 (U (t)) ≥ −2C + 2θ Un(c) (t)(rn∗(c) () + ) (c) (c) (c)
‘arrival process’ Yn (t): Y n ≤ γ n . From (37), this implies
n,c (c) (c)
rn ≥ Rnmax − γ n , and hence:
The proof then proceeds exactly as before, as noted in [1].  X X X
h(c) (c)
n (γ n ) = gn(c) (Rnmax ) − gn(c) (Rnmax − γ (c)
n )
V. S CHEDULING WITH A RBITRARY I NPUT R ATES n,c n,c
X
n,c
X
The algorithm CLC1 assumes there is always an amount ≥ gn(c) (Rnmax ) − gn(c) (r(c)
n )
(c)
of data Rn (t) available in reservoir (n, c), where the flow n,c n,c
(c)
variable Rn (t) is chosen only with respect to the Rnmax Thus, minimizing P h(c) (γ (c) ) over all feasible γ (c) values
n,c n n n
constraint. Here we assume that all transport layer storage P (c) (c)
reservoirs have a finite (possibly zero) buffer, and let Ln (t)
(c) is intimately related to maximizing n,c gn (r n ) over all
(c)
represent the current backlog in the reservoir buffer. The flow feasible rn values.
control decisions are now subject to the additional constraint Cross Layer Control Policy 2 (CLC2): Let η be any fixed
Rn (t) ≤ Ln (t) + An (t) (where An (t) is the amount of constant such that(c)0 < η ≤(c)1. Every timeslot and for each
(c) (c) (c) (c)

new commodity c data exogenously arriving to node n at slot node n, choose Rn (t) = xn to solve:
t). Any arriving data that is not immediately admitted to the P (c) (c) (c)
Maximize: c [ηZn (t) − Un (t)]xn (40)
network is stored in the reservoir, or dropped if the reservoir P (c) max
has no extra space. Subject to: c xn ≤ Rn
(c) (c) (c) (c)
Assume the An (t) arrivals are i.i.d. over timeslots with xn ≤ Ln (t) + An (t)
(c) (c)
arrival rates λn = E{An (t)}. It can be shown that for (c)
(c) Additionally, the flow controllers at each node n choose γn (t)
any matrix (λn ) (possibly outside of the capacity region),
for each session (n, c) to solve:
modifying the CLC1 flow algorithm to maximize (9) subject
to the additional reservoir backlog constraint yields the same (c) (c) (c) (c)
Maximize: V gn (Rnmax − γn ) + 2ηZn (t)γn (41)
performance guarantees (12) and (13) when utility functions (c)
Subject to: 0≤ γn ≤ Rnmax
are linear [1]. For nonlinear utilities, such a strategy can be
P (c) (c) (c)
shown to maximize the time average of n,c E{gn (Rn (t))} The flow states Zn (t) are then updated according to (38).
over all strategies that make immediate admission/rejection Routing and resource allocation within the network is the same
decisions upon arrival, but may not necessarily maximize as in CLC1.
P (c) (c) (c)
n,c gn (E{Rn (t)}), which is the utility metric of interest. The optimization of Rn (t) in (40) is solved by a simple
We solve this problem with a novel technique of defining ad- ‘bang-bang’ control policy, where no data is admitted from
(c) (c) (c)
ditional flow state variables Zn (t). The result can be viewed reservoir (n, c) if Un (t) > ηZn (t), and otherwise as much
as a general framework for stochastic network optimization. data as possible is delivered from the commodities of node n
IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 16, NO. 2, APRIL 2008, PP. 396-409 11

(c) (c)
with the largest non-negative values of [ηZn (t) − Un (t)], arrival) yields the same performance guarantees. We further
subject to the Rnmax constraint. These bang-bang decisions note that it is possible to use the same proof to show that
(c)
also enable the strategy to be implemented optimally in if the input rate matrix (λn ) is in the relative interior of
(c) (c)
systems where admitted data is constrained to integral units, the capacity region Λ (so that (λn + δ1n ) ∈ Λ for some
a feature that CLC1 does not have. δ > 0), then the same utility bound of Theorem 3 holds, but
(c)
The γn (t) variable assignment in (41) involves maximizing the congestion can be bounded by a constant that depends on
a concave function of a single variable, and can be solved the proximity to the boundary of the capacity region, but does
(c)
easily by finding the critical points over 0 ≤ γn ≤ Rnmax . not depend on V (we omit these details for brevity). This
(c)
For example, if gn (r) = log(1 + βr), it can be shown that: is intuitively satisfying, as we know from the results of [1]
" " # # [28] that the DRPC algorithm (without flow control) bounds
(c) 1 max V max average congestion by a similar constant whenever input rates
γn = min max + Rn − (c)
, 0 , Rn
β 2ηZn (t) are interior to the capacity region.
Suppose channels and
o arrivals are i.i.d. over timeslots, and
VI. S IMULATION R ESULTS
n
(c) (c) (c)
let λn = E An (t) . We assume that λn = 0 whenever
(n, c) ∈/ D. For simplicity of exposition, we further assume Here we simulate the CLC2 policy for three simple network
that new arrivals to node n are deterministically bounded by examples. We assume throughout that η = 1/N . We begin
P (c) with the 2-queue downlink example of Section II. Packets
Rnmax , so that c An (t) ≤ Rnmax every slot.
(c) arrive from each stream according to Bernoulli processes, and
Theorem 3: For arbitrary rate matrices (λn ) (possibly
we assume there are no transport layer storage reservoirs,
outside of the capacity region), for any V > 0, and for
so that all arriving data is either immediately admitted or
any reservoir buffer size (possibly zero), the CLC2 algorithm
dropped.5 As before, we assume channel probabilities are
stabilizes the network and yields a congestion bound:
given by p1 = 0.5, p2 = 0.6, and consider one hundred
N B + 2ηN n (Rnmax )2 + V Gmax
P
X (c) different rate pairs (λ1 , λ2 ) that are linearly scaled towards
Un ≤ the point (0.5, 1.0). For each point we simulate the CLC2
n,c
2µsym
algorithm for 3 million timeslots, using V = 10000, Rnmax =
Further, the time average utility satisfies: 2, and g1 (r) = g2 (r) = log(1 + r). Note that in this case, we
X X have µin out
max = 0, µmax = 1, so by (11) we have B = 5. Thus,
lim inf gn(c) (r(c)
n (t)) ≥ gn(c) (rn∗(c) ) for V = 10000 we are ensured by Theorem 3 that the resulting
t→∞
n,c n,c
utility associated with each rate vector (λ1 , λ2 ) differs from
N B + 2ηN n (Rnmax )2
P
− the optimum utility by no more than (5 + 8)/V = 0.0013
V (note that N = 1 for this simple example, as there is only 1
Proof: Define the Lyapunov function L(U , Z) =
P (c) 2 P (c) 2 transmitting node). The simulation results are shown in Fig.
n,c (Un ) + η n,c (Zn ) . The drift expression for this 3(a), where the achieved throughput increases to the capacity
(c)
function is given by summing the drift of the Un (t) queues boundary and then moves directly to the fair point (0.4, 0.4).
(c)
and the Zn (t) queues using the general formula (23), where In Fig. 3(b) we treat the same situation with the exception
the queueing laws are given by (8) and (38): that utility for user 2 is modified to 1.28 log(1 + r). This
X n o illustrates the ability to handle priority service, as user 2 traffic
∆(U (t), Z(t)) + V E h(c)
n (γn
(c)
(t)) | U , Z ≤ is now given favored treatment. From the figure, we see that as
n,c
X input rates are increased the resulting throughput reaches the
N B + 2ηN (Rnmax )2 − Φ(U (t)) capacity boundary and then moves in a new direction, settling
X n n
o and remaining on the new optimal operating point (0.23, 0.57)
+2 E Un (t)Rn (t) + ηYn(c) (t)Zn(c) (t) | U , Z
(c) (c) once input rates dominate this point.
n,c Note that for this example, we have µsym = 0.4 and
X n o Gmax = 0.784. Thus, by Theorem 3, we know:
− E 2ηZn(c) (t)γn(c) (t) − V h(c) (c)
n (γn (t)) | U , Z (42)
n,c 13 + 0.784V
U1 + U2 ≤ (43)
where we have addedn to both sides of the oabove expression the 0.8
P (c) (c)
cost term n,c V E hn (γn (t)) | U , Z . The CLC2 policy The above bound holds for any input rate vector (λ1 , λ2 ),
including vectors that are far outside of the capacity region.
is designed to minimize the right hand side of the above
We next keep the same utility as in Fig. 3(b) but fix the
expression over all possible policies. Thus, similar to the proof
input rate to (λ1 , λ2 ) = (0.5, 1.0), which dominates the
of CLC1, plugging particular policies gives bounds for which
optimal operating point (0.23, 0.57) (so that utility optimal
the Lyapunov Optimization Lemma (Lemma 1)ncan be applied,
(c)
o control should achieve this point). In Fig. 3(c) we plot the
proving stability of all queues, proving that E Zn (t) /t → resulting average queue congestion as V is varied from 1
0, and leading to the result (see [2] for details). to 104 , together with the bound (43). As suggested by the
We note that the transport layer storage reservoir does bound, the delay grows linearly with V . In Fig. 3(d) we see
not impact the above result, and hence a size-zero reservoir
(in which all data is immediately accepted or dropped upon 5 Simulations for infinite transport reservoirs yield almost identical results.
IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 16, NO. 2, APRIL 2008, PP. 396-409 12

(a) Throughput region (b) Throughput region

Rates (λij ) Throughput (rij ) Backlog (U ij )
0.6 Proportional 0.6 Optimal point .45 .1 .4 .450 .100 .399 3.3 2.4 3.6
0.5
fair point 0.5
.1 .7 .15 .100 .695 .148 2.4 2.9 2.7
λ 0.4 λ 0.4
2 2
0.3 0.3 .4 .15 .4 .399 .149 .400 3.6 2.7 3.4
0.2 0.2 (a) Simulation of a switch with feasible traffic
0.1 0.1

0 0
Rates (λij ) Throughput (rij ) Backlog (U ij )
0 0.1 0.2 0.3 0.4 0.5 0 0.1 0.2 0.3 0.4 0.5
λ1 λ1 .9 .2 .3 .598 .100 .298 31.6 45.3 32.1
10
5
(c) Average backlog v.s. V
0.7
(d) Throughput region
0 .4 .2 0 .399 .200 0 14.1 .29
10
4
0.6
V=1000 0 .5 0 0 .500 0 0 14.2 0
E(U1+U2) (log scale)

V=100
3 V=10 (b) Simulation of an overloaded switch
10 Theoretical bound
λ 0.5 Optimal point
2

10
2
V=1000 0.4 Fig. 4. Simulation results for the CLC2 algorithm with V = 100 and zero
1 V=100 reservoir buffers. Simulations were run over four million timeslots.
10 0.3
V=10
0
10 0.2
0 1 2 3 4 0.1 0.2 0.3 0.4 0.5
10 10 10 10 10
V (log scale) λ1
in the figure, and is almost indistinguishable from the utility
Fig. 3. Simulation of CLC2: (a) Linearly increasing (λ1 , λ2 ) to (0.5, 1.0) maximizing solution of the optimization problem (2)-(4). The
for V = 10000 and g1 (r) = g2 (r) = log(1 + r). (b) Modifying utility average backlog in each queue is no more than 45.3 packets.
2 to: g2 (r) = 1.28 log(1 + r). (c)-(d) Fixing (λ1 , λ2 ) = (0.5, 1.0) and
illustrating delay and throughput versus V .
B. Heterogeneous Multi-hop Networks
Here we consider the multi-hop network of Fig. 1, consist-
how the achieved throughput of CLC2 approaches the optimal ing of wireless sensor nodes (nodes {6, 7, 8, 9}), a wireline
operating point (0.23, 0.57) as V is increased. network, and a wireless basestation that transmits to two
mobile users. All packets have fixed lengths. The wireline links
A. Packet Switches are bidirectional and can transmit 3 packets in each direction
during a single slot. The basestation node 0 can transmit to
Here we consider a simple 3 × 3 packet switch with a
only one mobile user per slot, and the downlinks to each user
crossbar switch fabric [23] [26]. Packets arrive from three
independently vary between ON and OFF states according to
different input ports, and each packet is destined for one of
Bernoulli processes, with equal likelihood of being ON or
three output ports. We let λij represent the rate of packets
OFF. The wireless links of the sensor network are always ON,
arriving to input i and destined for output j. All packets are
and can support one packet transfer per slot. However, due to
stored in virtual input queues according to their destinations,
interference between the various sensor nodes, we assume that
and we let Uij (t) represent the current number of backlogged
only one sensor link can be activated per slot (including the
packets waiting at input i to be delivered to output j. The
outgoing wireless links of the access nodes 4 and 5).
system is timeslotted, and the crossbar fabric limits scheduling
We assume there are four independent sessions using the
decisions to permutation matrices, where no input can transfer
network: Two sessions originate from node 9 and consist of
more than one packet per slot, and no output can receive
packets destined for nodes 3 and 1, and two sessions originate
more than one packet per slot. Thus, the following feasibility
from node 4 and consist of packets destined for nodes 8 and
constraints are required for stability:
2. All arrival processes are i.i.d. and Bernoulli, with arrival
3 3
X X rates λ93 = λ91 = λ48 = λ42 = 0.7.
λij ≤ 1 ∀j ∈ {1, 2, 3} , λij ≤ 1 ∀i ∈ {1, 2, 3} These arrival rates are not supportable by the network.
i=1 j=1
Indeed, note that all packets originating at node 9 must travel
We consider i.i.d. Bernoulli arrivals, and apply the CLC2 over at least 2 sensor links before reaching a wireline access
algorithm using log(1 + r) utility functions, V = 100, and node. Likewise, all data from the λ48 stream requires at least
Rmax = 3 (the maximum number of arrivals to a single input two hops through the sensor network. Because at most one
during a slot). In this example we assume that all reservoirs sensor link can be activated on any timeslot, it follows that
have zero buffers, so that admission/rejection decisions must 2r93 + 2r91 + 2r48 ≤ 1 is a necessary condition for network
be made immediately upon packet arrival. Resource allocation stability, where rij is the throughput of (i, j) traffic. The
for CLC2 in this context is equivalent to Maximum Weight basestation places the following additional constraints on the
Matching. In Fig. 4(a) we present simulation results for a case network flows: r91 ≤ 1/2, r42 ≤ 1/2, and r91 + r42 ≤ 3/4.
when the sum rate to every input port and every output port is It is not difficult to verify that these necessary conditions
exactly 0.95. Note that average queue backlog is kept very low, describe the feasible flows for the network, as the wired
while the resulting throughput is almost identical to the input links do not impose further constraints. Assuming that all
rate. This illustrates that the CLC2 algorithm accepts almost sessions have identical utility functions gij (r) = log(1 + r),
∗ ∗ ∗
all packets into the system, and accomplishes this without a- the optimally fair flows are thus given by r91 = r93 = r48 =
∗
priori knowledge that the input traffic is feasible. 1/6 = 0.1667, r42 = 0.5.
We next apply the same CLC2 algorithm to a switch where We implement CLC2 for this network, using V = 1000,
input port 1 and output port 2 are overloaded, as shown in Fig. Rmax = 2, and assuming infinite buffer reservoirs. Note that
4(b). The resulting throughput from the simulation is given sensor link activations are determined every slot by choosing
IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 16, NO. 2, APRIL 2008, PP. 396-409 13

the link with the largest differential backlog. The resulting to activate that comes within a factor of Kmax of the optimal
average queue length, summed over all queues in the system, solution (see [43] for a simlar result). A simpler random
is 858.9 packets. The throughputs are: r91 = 0.1658, r93 = access scheme that uses a collision model and requires only
0.1662, r48 = 0.1678, r42 = 0.5000. We note that this one contention round is as follows: Each link independently
performance is not possible unless almost all packets take their attempts activation with probability 1/Kmax . If a link has no
optimal 2-hop paths through the sensor network, and hence the contenders, then it is successfully activated. Else, it remains
backpressure routing learns the optimal routes. idle. This random access scheme is similar to the distributed
random access scheme specified in [1] [28]. It is clear that this
scheme satisfies:
VII. D ISTRIBUTED C ONTROL FOR W IRELESS N ETWORKS
∗
P
Theorem 2 and its corollary demonstrate that itP is important l Wl (t)E {µl (t) | U (t)} ≥
Kmax
to allocate resources in an effort to maximize l Wl∗ (t)µl ,
 
∗ 1 1
P
l Wl (t)E {bl (t) | U (t)} Kmax 1 − Kmax
even if implementation complexity precludes realization of the
full maximum (this is also highlighted in Chapter 4.3.6 of and hence the left hand side is within a factor of (1/Kmax )(1−
[1]). Indeed, it is often difficult to achieve the full maximum, 1/Kmax )Kmax of the sum of weights over all links in the
especially in distributed networks with interference. However, network. Hence, the expectation is certainly within this same
there are several basic network models for which it is possible factor of the optimal solution (which must conform to valid
to come within a constant factor of optimality using simplified link activation sets). Note that 1/Kmax (1 − 1/Kmax )Kmax ≈
scheduling techniques, and this is an area of recent active 1/(Kmax e) (for large Kmax ), and hence the factor 1/e can
interest [15] [42] [43]. roughly be viewed as the cost of using this single-round
For example, consider a wireless network where every node random access scheme in comparison to the multi-round
transmits over an orthogonal frequency band. Assume nodes greedy approach. The solution can further be improved by
can transmit or receive from at most one link at a time, using multiple random access rounds and/or by restricting
and nodes cannot simultaneously transmit and receive. Such a attempts that lead to obvious contentions (such as attempting
model is recently considered in [15] [42]. Let bl (t) represent to activate two outgoing links from the same node).
the rate that link l can transmit data during slot P
t if it is chosen
for transmission. The problem of maximizing l Wl∗ (t)µl in VIII. C ONCLUSIONS
this case amounts to finding a maximum weight match (MWM)
in the underlying network graph. Such matchings are important We have presented a fundamental approach to stochastic
for network stability problems (see [20] [23]), although they network control for heterogeneous data networks. Simple
are difficult to compute in a distributed manner because the strategies were developed that perform arbitrarily close to
matching constraints couple all decisions throughout the net- the optimally fair throughput point (regardless of the input
work. However, it is well known that a simple contention based traffic matrix), with a corresponding tradeoff in end-to-end
algorithm for greedily selecting a matching comes within a network delay. The strategies involve resource allocation and
factor of two of the optimal solution. routing decisions that are decoupled over the independent
Specifically, the contention scheme goes through several portions of the network, and flow control algorithms that are
rounds before finalizing a set of links to activate. In the decoupled over independent control valves at every node. Flow
first round, each node attempts to activate its largest weight controllers require knowledge only of the queue backlog in
outgoing link. Any resulting contentions are resolved locally their respective source nodes. We note that this technique
by (tentatively) selecting the links with the largest weight of implementing flow control only at the sources is crucial
among all competitors, breaking ties arbitrarily. The next to ensure no network resources are wasted transmitting data
round proceeds by having each non-selected node attempt to that will eventually be dropped. It is remarkable that the
activate its largest weight link that does not contend with any overall strategy does not require knowledge of input rates,
selected link of equal or larger weight. Contentions are again channel statistics, or the global network topology. Although
resolved locally, placing the largest weight contenders in the i.i.d. assumptions were made to simplify exposition, the same
“selected” group and removing any lesser weight contenders policies can be shown to offer similar performance (with
previously selected. Proceeding this way, it is easy to see that modified delay expressions) for arbitrary ergodic arrivals and
each round of contention permanently adds at least one new channels, and are robust to cases when channel probabilities
link, and so after at most N rounds the algorithm converges or arrival rates change over time [1] [4]. We believe that such
to a matching in which all non-active links are adjacent to at theory-driven networking strategies will impact the design and
least one active link with equal or larger weight. It can be operation of future data networks.
shown that this matching is within a factor of 2 of optimality,
so that the condition of Corollary 1 holds with θ = 1/2. R EFERENCES
A more general interference model is recently considered [1] M. J. Neely. Dynamic Power Allocation and Routing for Satellite
in [43], where each link l has a set of Kl “competitor and Wireless Networks with Time Varying Channels. PhD thesis,
links” that cannot be activated if link l is transmitting. Define Massachusetts Institute of Technology, LIDS, 2003.
M [2] M. J. Neely, E. Modiano, and C. Li. Fairness and optimal stochastic
Kmax = maxl Kl . It can be shown that, within N rounds, a control for heterogeneous networks. Proc. IEEE INFOCOM, March
similar greedy contention scheme finds a feasible set of links 2005.
 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 16, NO. 2, APRIL 2008, PP. 396-409 14

[3] M. J. Neely. Energy optimal control for time varying wireless networks. [32] H. Kushner and P. Whiting. Asymptotic properties of proportional-
Proc. IEEE INFOCOM, March 2005. fair sharing algorithms. Proc. of 40th Annual Allerton Conf. on
[4] L. Georgiadis, M. J. Neely, and L. Tassiulas. Resource allocation and Communication, Control, and Computing, 2002.
cross-layer control in wireless networks. Foundations and Trends in [33] V. Tsibonis, L. Georgiadis, and L. Tassiulas. Exploiting wireless channel
Networking, vol. 1, no. 1, pp. 1-149, 2006. state information for throughput maximization. Proc. IEEE INFOCOM,
[5] J. W. Lee, R. R. Mazumdar, and N. B. Shroff. Downlink power allocation April 2003.
for multi-class cdma wireless networks. Proc. IEEE INFOCOM, 2002. [34] L. Li and A. Goldsmith. Capacity and optimal resource allocation for
[6] R. Berry, P. Liu, and M. Honig. Design and analysis of downlink utility- fading broadcast channels: Part i: Ergodic capacity. IEEE Trans. Inform.
based schedulers. Proc. of 40th Allerton Conf. on Communication, Theory, pp. 1083-1102, March 2001.
Control, and Computing, Oct. 2002. [35] A. Stolyar. Maximizing queueing network utility subject to stability:
[7] P. Marbach and R. Berry. Downlink resource allocation and pricing for Greedy primal-dual algorithm. Queueing Systems, vol. 50, pp. 401-457,
wireless networks. Proc. IEEE INFOCOM, 2002. 2005.
[8] M. Chiang. Balancing transport and physical layer in wireless multihop [36] J. W. Lee, R. R. Mazumdar, and N. B. Shroff. Opportunistic power
networks: Jointly optimal congestion control and power control. IEEE scheduling for dynamic multiserver wireless systems. IEEE Transactions
J. Sel. Area Comm., vol. 1, no. 23, pp. 104-116, Jan. 2005. on Wireless Communications, vol. 5, no.6, pp. 1506-1515, June 2006.
[9] L. Xiao, M. Johansson, and S. Boyd. Simultaneous routing and resource [37] P. Kall and S. W. Wallace. Stochastic Programming. Wiley, 1994.
allocation for wireless networks. Proc. of the 39th Annual Allerton Conf. [38] M. J. Neely. Super-fast delay tradeoffs for utility optimal fair scheduling
on Comm., Control, Comput., Oct. 2001. in wireless networks. IEEE Journal on Selected Areas in Commu-
[10] B. Krishnamachari and F. Ordonez. Analysis of energy-efficient, fair nications, Special Issue on Nonlinear Optimization of Communication
routing in wireless sensor networks through non-linear optimization. Systems, vol. 24, no. 8, pp. 1489-1501, Aug. 2006.
IEEE Vehicular Technology Conf., Oct. 2003. [39] D. P. Bertsekas and R. Gallager. Data Networks. New Jersey: Prentice-
[11] P. Marbach. Priority service and max-min fairness. Proc. IEEE Hall, Inc., 1992.
INFOCOM, 2002. [40] D. Shah and M. Kopikare. Delay bounds for approximate maximum
[12] F. Kelly. Charging and rate control for elastic traffic. European weight matching algorithms for input queued switches. Proc. IEEE
Transactions on Telecommunications, vol. 8, pp. 33-37, 1997. INFOCOM, June 2002.
[13] F.P. Kelly, [Link], and D. Tan. Rate control for communication [41] M. J. Neely, E. Modiano, and C. E. Rohrs. Tradeoffs in delay guarantees
networks: Shadow prices, proportional fairness, and stability. Journ. of and computation complexity for n × n packet switches. Proc. of Conf.
the Operational Res. Society, 49, p.237-252, 1998. on Information Sciences and Systems (CISS), Princeton, March 2002.
[14] S. H. Low and D. E. Lapsley. Optimization flow control, i: Basic [42] X. Wu and R. Srikant. Regulated maximal matching: A distributed
algorithm and convergence. IEEE/ACM Transactions on Networking, scheduling algorithm for multi-hop wireless networks with node-
vol. 7(6): 861-75, Dec. 1999. exclusive spectrum sharing. IEEE Proc. Conf. on Decision and Control,
[15] X. Lin and N. B. Shroff. The impact of imperfect scheduling on cross- 2005.
layer rate control in wireless networks. Proc. IEEE INFOCOM, 2005. [43] P. Chaporkar, K. Kar, and S. Sarkar. Throughput guarantees through
[16] B. A. Movsichoff, C. M. Lagoa, and H. Che. Decentralized optimal maximal scheduling in wireless networks. Proc. of 43rd Annual Allerton
traffic engineering in connectionless networks. IEEE Journal on Selected Conf. on Communication Control and Computing, September 2005.
Areas in Communications, vol. 23(2), pp. 293-303, Feb. 2005.
[17] S. H. Low. A duality model of tcp and queue management algorithms.
IEEE Trans. on Networking, vol. 11(4), August 2003.
[18] X. Liu, E. K. P. Chong, and N. B. Shroff. A framework for opportunistic
scheduling in wireless networks. Computer Networks, vol. 41, no. 4, pp.
451-474, March 2003.
[19] R. Cruz and A. Santhanam. Optimal routing, link scheduling, and power
control in multi-hop wireless networks. Proc. IEEE INFOCOM, April
2003.
[20] L. Tassiulas and A. Ephremides. Stability properties of constrained
queueing systems and scheduling policies for maximum throughput in
multihop radio networks. IEEE Transacations on Automatic Control,
vol. 37, no. 12, pp. 1936-1949, Dec. 1992.
[21] L. Tassiulas and A. Ephremides. Dynamic server allocation to parallel
queues with randomly varying connectivity. IEEE Transactions on
Information Theory, vol. 39, pp. 466-478, March 1993.
[22] P.R. Kumar and S.P. Meyn. Stability of queueing networks and
scheduling policies. IEEE Trans. on Automatic Control, vol.40,.n.2,
pp.251-260, Feb. 1995.
[23] N. McKeown, V. Anantharam, and J. Walrand. Achieving 100%
throughput in an input-queued switch. Proc. IEEE INFOCOM, 1996.
[24] N. Kahale and P. E. Wright. Dynamic global packet routing in wireless
networks. Proc. IEEE INFOCOM, 1997.
[25] M. Andrews, K. Kumaran, K. Ramanan, A. Stolyar, and P. Whiting.
Providing quality of service over a shared wireless link. IEEE Commu-
nications Magazine, vol. 39, no.2, pp.150-154, 2001.
[26] E. Leonardi, M. Mellia, F. Neri, and M. Ajmone Marsan. Bounds on
average delays and queue size averages and variances in input-queued
cell-based switches. Proc. IEEE INFOCOM, 2001.
[27] M. J. Neely, E. Modiano, and C. E. Rohrs. Power allocation and routing
in multi-beam satellites with time varying channels. IEEE Transactions
on Networking, vol. 11, no. 1, pp. 138-152, Feb. 2003.
[28] M. J. Neely, E. Modiano, and C. E Rohrs. Dynamic power allocation and
routing for time varying wireless networks. IEEE Journal on Selected
Areas in Communications, vol. 23, no. 1, pp. 89-103, January 2005.
[29] A. Eryilmaz and R. Srikant. Fair resource allocation in wireless networks
using queue-length-based scheduling and congestion control. Proc. IEEE
INFOCOM, March 2005.
[30] S. Borst. User-level performance of channel-aware scheduling algo-
rithms in wireless data networks. Proc. IEEE INFOCOM, 2003.
[31] D. N. Tse. Optimal power allocation over parallel broadcast channels.
Proc. of Int. Symp. on Information Theory (ISIT), June 1997.

View publication stats