[SNO HOME] [M. J. NEELY HOME] [ADDITIONAL LINKS]

Stochastic Network Optimization:
This page links to papers that develop a theory of modern networking, particularly treating stochastic networks with wireless and/or wireline components, randomly arriving traffic, and time varying channels with possible disconnections and user mobility.

The first set of papers describe how a general network can be modeled as a queueing system with transmission rate options that depend on resource allocation decisions and time varying channel states. Control decisions of routing, resource allocation, and flow control must be made to achieve joint optimal performance. These papers introduce the mathemetical tools of Lyapunov drift and Lyapunov optimization for networks, and derive important techniques of backpressure routing, maximum weight scheduling, and constrained optimization via virtual queues. The Lyapunov optimization papers in particular provide performance tradeoffs in the form of utility-delay and energy-delay curves. A brief history is given to illustrate the contributions of each paper. The extended Foundations and Trends article is also provided in reference 7, which contains a detailed and unified treatment of this material. PowerPoint Slides from a UCSD ITA Short Course based on the article are here: PowerPoint Slides from ITA Short Course.

The page also has representative papers in different categories, and contains a link to an Editable Bibliography list for posting.


Papers on Stochastic Network Optimization:
  1. L. Tassiulas and A. Ephremides, "Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks," IEEE Transactions on Automatic Control, vol. 37, no. 12, pp. 1936-1949, Dec. 1992.

    This paper models a multi-hop wireless network as a multi-queue system with transmission options described by a collection of link activation sets. It is the first to introduce Lyapunov drift for proving stability in a general multi-hop network. It introduces the important concepts of backpressure routing and maximum weight matching. This paper can be viewed as a foundation for scheduling for stability and maximum throughput in a data network.

  2. L. Tassiulas and A. Ephremides, "Dynamic Server Allocation to Parallel Queues with Randomly Varying Connectivity," IEEE Transactions on Information Theory, vol. 39, no. 2, pp. 466-478, March 1993.

    This paper uses the Lyapunov drift technique to address a network with time varying channels. Specifically, it looks at a wireless downlink with ON/OFF channels and demonstrates stability and throughput optimality of the Longest Connected Queue (LCQ) algorithm. It also uses a stochastic coupling technique to prove delay optimality of LCQ in a special "symmetric" case when all rates and channel probabilities are identical. This paper can be viewed as a foundation for channel-aware scheduling (also called "opportunistic scheduling").

  3. E. Leonardi and M. Mellia and 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.

    This paper shows how the Lyapunov drift technique can be modified in a very simple way to provide average delay analysis. The application considered is a NxN packet switch.

  4. 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, Special Issue on Wireless Ad-Hoc Networks, vol. 23, no. 1, pp. 89-103, Jan. 2005. [Slides from INFOCOM 2003]

    This paper extends the backpressure and max weight techniques of Tassiulas 92, 93 (references 1 and 2) to a general multi-hop network with time varying channels. It focuses in particular on ad-hoc mobile networks with arbitrary ergodic arrival and mobility processes. Joint optimal routing and resource allocation algorithms are derived to achieve stability, maximum throughput, and average end-to-end delay guarantees.

  5. M. J. Neely, E. Modiano, and C. Li, "Fairness and Optimal Stochastic Control for Heterogeneous Networks," IEEE INFOCOM Proceedings, March 2005. [ Slides from INFOCOM 2005] [ Journal Version, Transactions on Networking, April 2008] [ Neely thesis 2003]

    This paper extends the mathematical tool of Lyapunov drift to include both stability and performance optimization in networks. It applies this extended theory to treat the previously unsolved problem of maximizing a concave function of throughput in a network with stochastic channels (for cases when input rates are either inside or outside of the network capacity region). It provides an explicit tradeoff beteen utility and average end-to-end network delay for a general multi-hop network, showing that utility can be pushed arbitrarily close to optimality at the expense of increased delay. The paper is a writeup of chapter 5 of my phd thesis and contains an additional theory of "flow state queues" that is not in the thesis. The journal version includes extended results on distributed approximations.

  6. M. J. Neely, "Energy Optimal Control for Time Varying Wireless Networks," IEEE Transactions on Information Theory, vol. 52, no. 7, pp. 2915-2934, July 2006. [Slides from INFOCOM 2005]

    This paper introduces the important technique of virtual power queues for ensuring average power constraints. The concept of virtual power queues (or more general "virtual cost queues") are important in the theory of stochastic network optimization with constraints. Such virtual queues can be viewed as a "stochastic" version of a Lagrange multiplier (being a time varying process, not a scalar) for optimimizing performance metrics subject to general stochastic averaging constraints. This paper is the first to construct dynamic algorithms to minimize average power subject to network stability, or maximize throughput subject to average power constraints, for stochastic wireless networks. An explicit energy-delay tradeoff is provided, showing how network delay is affected by algorithms that get closer and closer to optimality.

  7. L. Georgiadis, M. J. Neely, L. Tassiulas, "Resource Allocation and Cross-Layer Control in Wireless Networks," Foundations and Trends in Networking, Vol. 1, no. 1, pp. 1-144, 2006. [ITA Short Course Slides].

    This is an extended article (and can also be purchased as a book) that treats the theory described in the above papers in a unified manner, particularly focusing on network optimization with general penalties/rewards and general constraints. This article is used as the textbook for the USC course "Stochastic Network Optimization," and some links to course handouts are found here.

  8. M. J. Neely and R. Urgaonkar, Opportunism, Backpressure, and Stochastic Optimization with the Wireless Broadcast Advantage," Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA, Oct. 2008. [PowerPoint Slides].

    This is a 7-page summary of the stochastic network optimization techniques from the above NOW Foundations and Trends article. It emphasizes minimization of general network penalties subject to general network constraints. It also presents the theory of delay improvement via place holder bits, from the "Data Compression" paper [Neely, Sharma 08] below.

  9. M. J. Neely and A. Sharma, "Dynamic Data Compression with Distortion Constraints for Wireless Transmission over a Fading Channel," arXiv:0807.3768v1, July 24, 2008. [ Conference version (CISS 2008)] [ PowerPoint Slides (CISS 2008)]

    This paper applies the techniques of Lyapunov Optimization to energy and distortion aware data compression and transmission. It also introduces an important technique of "place holder bits" to improve delay in stochastic problems with average cost minimization. The place holder bit concept can also be used to improve delay in other contexts, such as in the EECA algorithm of reference 6 above (Neely IT 2006).


Optimal Tradeoff Theory
  1. R. Berry and R. Gallager, "Communication over Fading Channels with Delay Constraints," IEEE Transactions on Information Theory, vol. 48, no. 5, pp. 1135-1149, May 2002.

    This paper treats a single wireless link with random arrivals and fading channels. It derives an optimal energy-delay tradeoff curve, showing that any algorithm that drives average power expenditure towards optimality must incur delay that grows according to a fundamental square root curve. It proposes a buffer-partitioning algorithm to achieve the tradeoff, provided that full channel probability information is known. Caveat from Mike: While this is an important and inspiring paper, the given proof for the proposed algorithm incorrectly treats an edge probability. However, the algorithm can still be shown to achieve the tradeoff to within a logarithmic factor (see discussion in Section IV.A of [Neely IT 2007] in next reference below).

  2. M. J. Neely, "Optimal Energy and Delay Tradeoffs for Multi-User Wireless Downlinks," IEEE Transactions on Information Theory, vol. 53, no. 9, pp. 3095-3113, Sept. 2007. [Conference Version INFOCOM 06] [PowerPoint Slides].

    This paper extends the Berry-Gallager square root law to a multi-user downlink, and derives an algorithm to achieve the optimal square-root tradeoff to within a logarithmic factor. The algorithm can be implemented in real time without knowledge of arrival/channel statistics, and overcomes a complexity explosion using an enhanced Lyapunov theory together with a "drift steering" technique. A "super-fast" logarithmic tradeoff, superior to the square-root Berry-Gallager bound, is shown to be achievable in the exceptional case when power curves are piecewise linear.

  3. M. J. Neely, "Super-Fast Delay Tradeoffs for Utility Optimal Fair Scheduling in Wireless Networks," IEEE Journal on Selected Areas in Communications (JSAC), Special Issue on Nonlinear Optimization of Communication Systems, vol. 24, no. 8, pp. 1489-1501, Aug. 2006. [SLIDES from INFOCOM 2006]

    This paper derives the optimal utility-delay tradeoff curve for flow control in wireless downlinks with input rates that are outside of the capacity region. The optimal curve is described by a "super-fast" logarithmic rule. Specifically, network utility can be pushed within O(1/V) of the optimal operating point (where V is an arbitrary control parameter), at the expense of average network delay growing like O(log(V)). This is superior to the [O(1/V), O(V)] utility-delay curve derived previously in [Neely thesis 2003, Neely Infocom 2005] for more general networks.

  4. M. J. Neely, "Intelligent Packet Dropping for Optimal Energy-Delay Tradeoffs in Wireless Downlinks," Proc. of 4th Int. Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt), April 2006. [ PowerPoint Slides from WiOpt 2006]

    This paper shows that the square-root energy-delay tradeoff of the Berry-Gallager bound can be improved to a logarithmic tradeoff if we allow a small fraction of packets to be dropped (for any arbitrarily small drop rate constraint). This demonstrates a simple "reverse queue" idea for achieving the optimal logarithmic tradeoff. The upcoming journal version (Transactions on Automatic Control, to appear) contains an extended technique of threshold adaptation for achieving a better multiplicative coefficient of the O(log(V)) delay.

  5. Note also that Capacity and Delay Tradeoffs for Ad-Hoc Mobile Networks, using the idea of redundant packet transfers to improve delay, is another topic of interest (using a completely different set of theoretical tools). Papers on that topic are found below (see also here).


Alternative Stochastic Optimization Techniques
    The technique of extending Lypaunov drift analysis to include stability and performance optimization was developed in [ Neely thesis 2003][Neely INFOCOM 2005] for application to joint flow control and scheduling for multi-hop wireless networks with time varying channels. The related work below treats similar problems using alternative fluid model techniques.

  1. A. Eryilmaz and R. Srikant, "Fair Resource Allocation in Wireless Networks using Queue-Length-Based Scheduling and Congestion Control," Proc. IEEE INFOCOM, March 2005.

    This paper treats a one-hop wireless downlink and uses a fluid model technique to reduce the stochastic problem to a corresponding static convex program. If the queue backlogs are assumed to converge to correct Lagrange multipliers, then the technique is similar to optimizing a dual problem and therefore achieves near-optimal performance.

  2. A. Stolyar, "Maximizing Queueing Network Utility subject to Stability: Greedy Primal-Dual Algorithm," Queueing Systems, vol. 50, pp. 401-457, 2005.

    This paper treats a multi-hop wireless network and uses a related alternative fluid model technique to reduce the stochastic problem to a static convex program. It emphasizes optimization of general penalty functions.

  3. J. W. Lee, R. R. Mazumdar and N. B. Shroff, "Opportunistic Power Scheduling for Dynamic Multiserver Wireless Systems," IEEE Transactions on Wireless Communications, vol. 5, no. 6, pp. 1506-1515, June 2006.

    This paper treats a related problem using stochastic gradient theory.


Related Work on Static Network Optimization
  1. F. P. Kelly, A. Maulloo, and D. Tan, "Rate Control for Communication Networks: Shadow Prices, Proportional Fairness, and Stability," Journal of the Operational Research Society, vol. 49, pp. 237-252, 1998.

    This paper shows how a set of static flows can be computed that optimize a concave utility metric in a wireline network. It utilizes convex optimization techniques and a differential equation analysis with a different type of Lyapunov argument.

  2. S. H. Low and D. E. Lapsley, "Optimization Flow Control, I: Basic Algorithm and Convergence," IEEE/ACM Transactions on Networking, vol. 7, no. 6, pp. 861-875, Dec. 1999.

    This paper addresses a wireline network problem similar to Kelly 98, and shows how convex programming and dual subgradient algorithms can be used to compute the optimal set of static flows.

  3. L. Xiao, M. Johansson, and S. Boyd, "Simultaneous Routing and Resource Allocation via Dual Decomposition," IEEE Transactions on Communications, vol. 52, no. 7, July 2004.

    This paper computes an optimal operating point, involving a static set of flows together with a set of power allocations, to maximize a network utility problem in a wireless network with orthogonal channels. Duality and convex programming techniques are used for distributed implementation.

  4. R. Cruz and A. Santhanam, "Optimal Routing, Link Scheduling, and Power Control in Multi-Hop Wireless Networks," Proc. IEEE INFOCOM, April 2003.

    This paper computes a set of flows and a link schedule for supporting those flows and minimizing average power expenditure in a static wireless network with interference, assuming a low-SINR regime. Under this low-SINR regime, it is shown that time-varying scheduling using "extreme point" power allocations are optimal.

  5. M. Chiang, "Balancing Transport and Physical Layer in Wireless Multihop Networks: Jointly Optimal Congestion Control and Power Control," IEEE Journal on Selected Areas in Communications, vol. 1, no. 23, pp. 104-116, Jan. 2005.

    This paper computes a set of flows and a static power allocation operating point to support those flows for throughput-utility optimization in a multi-hop wireless network, assuming a high-SINR regime where geometric programming can be applied. Geometric programs are problems that become convex programs under a logarithmic change of variables. The high-SINR regime leads to optimality of a static power allocation vector that never changes. This is quite different from the solution structure for the low-SINR regime, where time varying link schedules are required.

  6. M. Chiang, Geometric programming for communication systems, Foundations and Trends in Communications and Information Theory, vol. 2, no. 1-2, pp. 1-154, August 2005.

    This manuscript explains the technique of geometric programming and its use in communication systems. Geometric programs are opitmization problems that can be turned into convex problems through a logarithmic change of variables.

  7. M. Chiang, S. H. Low, A. R. Calderbank, and J. C. Doyle, "Layering as optimization decomposition: A mathematical theory of network architectures," Proceedings of the IEEE, vol. 95, no. 1, pp. 255-312, January 2007.

    This paper discusses optimization theory used in networks, where separability of the optimization problem often natural leads to layering structures.

Imperfect Scheduling and Maximal Matchings
    Using Lyapunov theory, one can show that the maximum throughput algorithms based on max-weight principles extend to constant-factor optimality results when the controller implements an algorithm that achieves only a constant factor of the max-weight rule every slot [ F&T]. The following papers consider sub-optimal strategies using a different type of maximal scheduling that is very simple and requires only knowledge of which queues have data (not requiring the actual backlog amount):

  1. X. Lin and N. B. Shroff, "The Impact of Imperfect Scheduling on Cross-Layer Rate Control in Wireless Networks," Proc. IEEE INFOCOM, March 2005.

    This paper considers a wireless network with link activation sets defined by matching constraints (called the "node exclusive spectrum sharing model"), and derives a greedy maximal matching scheduling policy shown to be within a factor of 2 for optimality of network utility.

  2. P. Chaporkar, K. Kar, and S. Sarkar, "Throughput Guarantees Through Maximal Scheduling in Wireless Networks," Proc. of 43rd Annual Allerton Conference on Communication , Control, and Computing, Sept. 2005.

    This paper considers a more general interference model for wireless networks based on interference sets S_z, where S_z represents the set of links that cannot be simultaneously activated when link z is active. It shows that greedy maximal scheduling achieves rate stability when arrival rates are within a constant factor of the capacity region boundary.

  3. X. Wu, R. Srikant, and J. R. Perkins "Scheduling Efficiency of Distributed Greedy Scheduling Algorithms in Wireless Networks," IEEE Transactions on Mobile Computing, June 2007.

    This paper considers the same interference model as the Chaporkar, Kar, Sarkar work, but uses a Lyapunov drift argument that uses a queue grouping technique to prove strong stability (so that means are finite), a stronger form of stability than rate stability. They also address multi-hop networks using regulation queues at each hop.

  4. M. J. Neely, "Delay Analysis for Maximal Scheduling in Wireless Networks with Bursty Traffic," Proc. IEEE INFOCOM, Phoenix, AZ, April 2008. [PowerPoint Slides]

    This paper analyzes the delay of the maximal scheduling algorithm for packet switches and 1-hop wireless networks, using the general interference model of references 2 and 3 above (Chaporkar et al. 2005, Wu et. al. 2007). It shows that delay is order-optimal, in the sense that it is O(1) and does not grow with the size of the network (see also the "order-optimal" category below). Delay results for bursty Markov arrivals (such as ON/OFF processes) are also obtained in terms of the auto-correlations of arrivals at each source.


Scheduling for Order Optimal Delay
    Network delay is difficult to analyze, and minimum-delay algorithms are very rare. The following papers consider 1-hop networks and develop "order optimal" delay results, where average delay is independent of the network size. (This topic is also related to the capacity/delay tradeoff results developed for multi-hop ad hoc mobile networks.) For other multi-hop queueing networks, see also the exact queueing analysis (with order optimal delay) for tree networks and tandems.

  1. M. J. Neely, E. Modiano, and Y.-S. Cheng, "Logarithmic Delay for N x N Packet Switches Under the Crossbar Constraint," IEEE Transactions on Networking, Vol. 15, No. 3, pp. 657-668, June 2007. [Slides from HPSR 2004]

    This paper considers an NxN packet switch and improves the (previously best-known) O(N) average delay result developed for MWM scheduling in [Leonardi et. al 2001] to an O(log(N)) delay result for a simple frame-based scheduling algorithm. This is the currently best known (and provable) delay scaling for packet switches with traffic anywhere inside the capacity region (i.e., any rho < 1). It is unknown if O(1) average delay is achievable, although this can be achieved for rho < 1/2 (see references 4 and 5 below, Deb et. al. 2006 and Neely 2008). The paper also shows that average delay that is sublinear in N can only be achieved if queue-aware scheduling is used.

  2. L. Tassiulas and A. Ephremides, "Dynamic Server Allocation to Parallel Queues with Randomly Varying Connectivity," IEEE Transactions on Information Theory, vol. 39, no. 2, pp. 466-478, March 1993.

    This paper uses the Lyapunov drift technique to address a network with time varying channels. Specifically, it looks at a wireless downlink with ON/OFF channels and demonstrates stability and throughput optimality of the Longest Connected Queue (LCQ) algorithm. It also uses a stochastic coupling technique to prove delay optimality of LCQ in a special "symmetric" case when all rates and channel probabilities are identical. This can be viewed as a foundation for channel-aware "opportunistic scheduling." We note that optimal delay results for systems without related symmetry assumptions are non-existant.

  3. E. M. Yeh and A. S. Cohen, "Optimal Coding and Minimal Delay in Multiaccess Communications", Proc. of 12th Yale Workshop on Adaptive and Learning Systems. Invited paper. New Have, CT, May 2003.

    This paper generalizes the Tassiulas-Ephremides 93 result for delay optimality in symmetric ON/OFF systems to scheduling in a Gaussian multiple access system. For a system with symmetric traffic and chanenls, it develops a delay optimal algorithm for scheduling rate vectors as a function of queue backlog.

  4. A. Ganti, E. Modiano, and J. N. Tsitsiklis, "Optimal Transmission Scheduling in Symmetric Communication Models with Intermittent Connectivity," IEEE Transactions on Information Theory, vol. 53, no. 3, March 2007.

    This paper generalizes the Tassiulas-Ephremides 93 result to ON/OFF channels with multiple servers. It again uses symmetric channels and symmetric traffic. It also shows that doubling the number of queues N does not double delay, which can be interpreted as an O(1) order-optimal delay result for symmetric traffic.

  5. M. J. Neely, "Order Optimal Delay for Opportunistic Scheduling in Multi-User Wireless Uplinks and Downlinks," IEEE/ACM Transactions on Networking, vol. 16, no. 5, pp. 1188-1199, Oct. 2008. [Allerton 2006 PowerPoint Slides]

    This looks at the classic opportunistic scheduling scenario as above, where there is a single server, N queues, and ON/OFF channels. It shows that queue-aware scheduling must be used to achieve delay that is sublinear in N. It then uses a queue-grouping technique to prove that O(1) average delay can be achieved under a "Largest Connected Group" algorithm. Traffic and channels can be asymmetric, although there are some "balanced" constraints that require no arrival rate to be significantly larger than any other.

  6. M. J. Neely, "Delay Analysis for Max Weight Opportunistic Scheduling in Wireless Systems", Proc. 46th Annual Allerton Conf. on Communication, Control, and Computing, Monticello, IL, Sept. 2008. [PowerPoint Slides][Arxiv Tech Report v2]

    This looks at the opportunistic scheduling scenario as above, but shows that O(1) average delay can also be achieved by the simpler "max-weight" (Longest Connected Queue) algorithm. It treats general (possibly non-uniform) traffic and achieves an O(1/(1-rho)^2) delay result, and then uses a different queue-grouped symmetric Lyapunov function to obtain a stronger O(1/(1-rho)) delay result for more "balanced" traffic. The Arxiv tech report (v2, Dec. 2008) has extensions to multi-rate systems, showing that O(1) delay is often not possible due to "residual" packets in queues with fewer than mu_max packets. It is important to note that my original Arxiv pre-print (v1) had a mistake in the multi-rate section, where I incorrectly claimed that O(1) average delay is also possible for multi-rate systems. That is corrected in v2, with a discussion of the issues.

  7. S. Deb, D. Shah, and S. Shakkottai, "Fast Matching Algorithms for Repetitive Optimization: An Application to Switch Scheduling," Proc. of 40th Annual Conf. on Information Sciences and Systems (CISS), Princeton, NJ, March 2006.

    This paper looks at maximal scheduling in a NxN packet switch, where rho < 1/2 (so that stability is achieved when input rates are within a 50% reduced capacity region). It shows such maximal matching yields order-optimal O(1) average delay for iid traffic.

  8. M. J. Neely, "Delay Analysis for Maximal Scheduling in Wireless Networks with Bursty Traffic," Proc. IEEE INFOCOM, Phoenix, AZ, April 2008. [PowerPoint Slides]

    This looks at maximal scheduling in 1-hop networks with general interference constraints and bursty (time correlated) traffic. It develops order optimal O(1) average delay results provided that the arrival rates are within a reduced capacity region associated with the maximal scheduling.

Heavy Traffic Theory and Delay Exponents
  1. A. L. Stolyar, "MaxWeight Scheduling in a Generalized Switch:State Space Collapse and Workload Minimization in Heavy Traffic," Annals of Applied Probability, Vol. 14, no. 1, pp. 1-53, 2004.

    This paper looks at scheduling to minimize a weighted workload vector in a switch, in an asymnptotic heavy traffic limit. It uses a fluid model approach and requires a pre-computation to establish a correct set of weights to use. The paper below uses a similar approach in a related problem, but does not require the pre-computation.

  2. S. Shakkottai, R. Srikant, and A. Stolyar, Pathwise Optimality of the Exponential Scheduling Rule for Wireless Channels," Advances in Applied Probability, Dec. 2004.

    This paper looks at scheduling many users over a time varying wireless channel. It develops a policy that minimizes queue length under a heavy traffic limit. It uses an analysis based on fluid and diffusion timescales, similar to above, but the policy does not require the pre-computation required above.

  3. A. Stolyar, "Large Deviations of Queues under QoS Scheduling Algorithms," Proc. 44th Annual Allerton Conf. of Comm, Control, and Computing, Monticello, Illinois, Sept. 2006.

    This paper looks at large deviations and queue exponents in a wireless system and provides sturctural results and bounds on performance. Asymptotic opitmality of the exponential rule is shown for the case of two queues.

  4. X. Lin, "On Characterizing the Delay Performance of Wireless Scheduling Algorithms," Proc. 44th Annual Allerton Conf. on Comm, Control, and Computing, Monticello, Illinois, Sept. 2006.

    This paper looks at queue backlog exponents and large deviations in wireless scheduling problems, and shows that multi-dimensional calculus of variations problems can be reduced to single-dimension variation problems.

  5. V. J. Venkataramanan and X. Lin, "Structural Properties of LDP for Queue-Length Based Wireless Scheduling Algorithms, in 45th Annual Allerton Conference on Communication, Control, and Computing, Monticello, Illinois, September 2007.

    This paper looks at scheduling to maximize the decay exponent of the backlog probability distribution in a wireless downlink. Using large deviation theory, a rule that schedules according to the queue with the largest product of transmission rate and queue raised to the power alpha is shown to achieve the best exponenent as alpha tends to infinity.


Strict Delay Constraints and Lazy Packet Scheduling
  1. E. Uysal-Biyikoglu, B. Prabhakar, and A. E. Gamal, "Energy-efficient Packet Transmission over a Wireless Link," IEEE/ACM Transactions on Networking, vol. 10, no. 4, pp. 487-499, Aug. 2002.

    This paper demonstrates the "lazy packet scheduling" concept, where convexity of wireless rate-power curves make longer transmission times more energy-efficient. It develops a technique for serving packet arrivals over a timeline with minimum energy, subject to the constraint that all packets must be served by some finite time horizon. Full future knowledge of packet arrival times is known. The optimal solution develops transmission times that are invariant for any convex rate-power curve.

  2. A. Fu, E. Modiano, and J. Tsitsiklis, "Optimal Transmission Scheduling over a Fading Channel with Energy and Deadline Constraints," IEEE Trans. Wireless Communications, vol. 5, no. 3, pp. 630-641, March 2006.

    This paper looks at a similar system as above, but with slotted time and fading channels. It develops an optimal algorithm using finite horizon dynamic programming theory.

  3. M. Goyal, A. Kumar, and V. Sharma, "Power Constrained and Delay Optimal Policies for Scheduling Transmission over a Fading Channel," Proc. IEEE INFOCOM, March 2003.

    This paper treats a related problem of energy and delay aware scheduling in a single queue, and uses Markov decision theory.

  4. M. A. Khojastepour and A. Sabharwal, "Delay-Constrained Scheduling: Power Efficiency, Filter Design, and Bounds," IEEE INFOCOM, March 2004.

    This paper treats a system with a static channel, and uses filter theory to shape the optimal transmission times.

  5. M. A. Zafer and E. Modiano, "A Calculus Approach to Minimum Energy Transmission Policies with Quality of Service Guarantees," Proc. IEEE INFOCOM, March 2005.

    This paper treats lazy packet scheduling for minimum energy subject to a general "service curve," which could be used to enforce individual delay constraints. With a similar assumption that future traffic arrivals are known and channel conditions are static, it shapes optimal transmission durations by an illuminating "pull-the-string" technique. It also treats a case when arrival times are unknown but Poisson and all traffic must depart by a given end time. A differential equation that describes the optimal policy is derived using dynamic programming theory.

  6. W. Chen, M. J. Neely, and U. Mitra, "Energy-Efficient Transmissions with Individual Packet Delay Constraints," IEEE Transactions on Information Theory, vol. 54, no. 5, pp. 2090-2109, May 2008. [Conference Version INFOCOM 2007].

    This paper treats a similar lazy packet scheduling problem where future arrivals are known. It develops an alternate recursive expression for optimal tranmsmission durations that uses convex-ordering theory and complements the "pull-the-string" technique of [Zafer and Modiano 2005]. It also uses a symmetry concept to analyze the exact average delay under the optimal scheduling algorithm.

  7. W. Chen, U. Mitra, and M. J. Neely, "Energy-Efficient Scheduling with Individual Packet Delay Constraints over a Fading Channel," Wireless Networks, DOI 10.1007/s11276-007-0093-y. [Conference Version WiOpt 2007].

    This paper extends the previous work to the case of fading channels, where both future traffic and future channel fades are known. It uses convex optimization theory and Lagrange multipliers to derive the optimal solution. This structure of the solution suggests a natural online heuristic (without future knowledge) that is shown to be close to optimal in the examples simulated.

  8. W. Chen, M. J. Neely, and U. Mitra, "Delay-Constrained Energy-Efficient Scheduling over a Multihop Link," Proc. IEEE International Symposium on Information Theory (ISIT), Nice, France, June 2007.

    This paper treats minimum energy rate scheduling in a multi-hop tandem of wireless links. The optimal solution is shown to reduce to a simple 1-queue structure where the first link schedules everything, and all downstream links simply forward the incoming traffic using the same rate as the first link.

Capacity and Delay Tradeoffs for Ad Hoc Mobile Networks
  1. M. Grossglauser and D. Tse, Mobility Increases the Capacity of Ad-Hoc Wireless Networks," IEEE/ACM Trans. on Networking, vol. 10, no. 4, pp. 477-486, August 2002.

    This paper extends the well known capacity analysis for static networks (by Gupta and Kumar) to networks with full uniform mobility. It shows that, unlike static networks, capacity remains O(1) (independent of the network size). This is illustrated through a 2-hop relay algorithm. The algorithm may give very large delay.

  2. N. Bansal and Z. Liu, "Capacity, Delay and Mobility in Wireless Ad-Hoc Networks," Proc. IEEE INFOCOM, April 2003.

    This paper looks at the mobile network with both static nodes and mobile nodes that facilitate communication. It assumes the mobiles have a random waypoint mobility model with predictable velocity information. By exploiting the velocity information and routing data to nodes that move in directions of the destination, a capacity of O(1/log^3(N)) is obtained with delay that is proportional to the time a node moves from one side of the network to the other.

  3. M. J. Neely and E. Modiano, "Capacity and Delay Tradeoffs for Ad-Hoc Mobile Networks," IEEE Transactions on Information Theory, vol. 51, no. 6, pp. 1917-1937, June 2005. [PowerPoint Slides] [History]

    This paper is a writeup of chapter 6 of my phd thesis [MIT 2003]. It looks at an ad-hoc mobile network with a simple cell partitioned structure. It computes the exact capacity and shows the capacity achieving strategy is a modified version of the 2-hop relay algorithm of [Grossglauser, Tse 2002]. It also computes the exact average delay of the algorithm under a simple i.i.d. mobility model, showing that average delay is O(N) (where N is the number of users). It then uses redundant trasmissions of the same packet to improve delay at the expense of throughput, and derives a fundamental capacity/delay tradeoff curve for this network: E{Delay}/capacity >= (1-ln(2))(N-d)/(4d) where d = N/C = user/cell density. When d = constant = O(1) (i.e., when the transmission radius includes O(1) other nodes), the curve reduces to: E{delay}/capacity >= O(N). When d can be arbitrary, the curve can be shown to imply that E{delay}/capacity^2 >= O(N).

  4. S. Toumpis and A. J. Goldsmith, "Large Wireless Networks Under Fading, Mobility, and Delay Constraints," Proc. IEEE INFOCOM, 2004.

    This paper looks at a wireless mobile network with N nodes (scaled up) over a fixed area. It uses a similar i.i.d. mobility model as above (so that node locations are randomly mixed every T seconds) but allows for both packet redundancy and transmission radius scaling (so that a transmission radius can contain many or all of the N network nodes, not just O(1) of the nodes). In this case of radius scaling, an improved tradeoff of E{Delay}/capacity^2 >= O(Nlog^5(N)) is shown to be achievable. It turns out that the necessary delay/capacity tradeoff constraint derived in [Neely, Modiano 2005] can be used to show that this is optimal (within a logarithmic factor) for a cell partitioned network (note that E{Delay}/capacity^2 >= O(N) is fundamental when radial scaling is allowed, i.e., when the cell size can be scaled so that the user/cell density is increased beyond O(1) ).

  5. X. Lin and N. B. Shroff, "Towards Achieving the Maximum Capacity in Large Mobile Wireless Networks," in Journal of Communications and Networks, Special Issue on Mobile Ad Hoc Wireless Networks, vol. 6, no. 4, December 2004. [ Tech Report 2004].

    This paper considers the same type of ad-hoc mobile network with i.i.d. mobility as introduced in [Neely, Modiano 2003,2005] above, but considers both radial scaling (as [Toumpis, Goldsmith 2004] above) and packet resizing and with transmission pipelining. In particular, if we break timeslots into mini-slots and allow fractional portions of packets to be transmitted and multi-hop pipelined over minislots, then an improved delay tradeoff of E{Delay}/capacity^3 >= O(N) is both necessary and achievable.

  6. X. Lin, G. Sharma, R. R. Mazumdar, and N. B. Shroff, "Degenerate Delay-Capacity Trade-offs in Ad Hoc Networks with Brownian Mobility," in the Joint Special Issue of IEEE Transactions on Information Theory and IEEE/ACM Transactions on Networking on Networking and Information Theory, vol. 52, no. 6, pp2777-2784, June 2006.

    This paper looks at the same ad-hoc mobile scenario as above, but assumes brownian motion mobility (rather than i.i.d. mobility). If only the source can replicate data (as in the 2-hop relay protocol with data replication from [Neely, Modiano 2003, 2005]), then a "degenerate" tradeoff holds, which is not as good as the capacity/delay tradeoff for the i.i.d. mobility case. This suggests such degenerate tradeoff would hold for Markov mobility. Note from Mike: This interesting negative result may only "kick in" for large network sizes N, as the simulations in [Neely, Modiano 2005] suggest that capacity/delay performance for Markov mobility is qualitatively similar to the analyzable i.i.d. mobility case. However, the plots in [Neely, Modiano 2005] above for Markov mobility do show performance that starts to (slightly) degrade with respect to the i.i.d. mobility when N grows large, suggesting that this degradation may become more noticeable if N is increased beyond the values used in the simulation experiments.

  7. A. El Gamal, J. Mammen, B. Prabhakar, and D. Shah, Optimal Throughput-Delay Scaling in Wireless Networks--Part 1: The Fluid Model," IEEE Transactions on Information Theory, vol. 52, no. 6, 2006.

    This paper looks at related capacity and delay tradeoffs using a fluid model. For static networks, it uses radial scaling to achieve a tradeoff of E{Delay}/capacity >= O(N) (similar to the tradeoff curve of [Neely, Modiano 2003,2005] derived for cell partitioned _mobile_ networks with i.i.d. mobility and without radial scaling). It also develops some degenerate tradeoff results for mobile networks, similar to [Lin et. al.] above. The fluid model scales packet sizes down with increasing N, so data can be viewed as flowing like a continuous fluid without queue buffers.

  8. L. Ying, S. Yang and R. Srikant, Optimal delay-throughput tradeoffs in mobile ad hoc networks." IEEE Transactions on Information Theory, to appear. Earlier versions of this paper appeared in Proc. WiOpt, Limassol, Cyprus, April 2007 and Proc. ITA workshop , San Diego, 2007.

    This paper looks at capacity and delay tradeoffs and uses a fixed delay constraint D (throwing packets away that violate the constraint). It considers cases of "fast" and "slow" mobility timescales, and uses network coding to facillitate scheduling and to reduce delay violations.

Backpressure with Enhanced PHY Capabilities ("Beyond Links")
  1. C. Swannack, E. Uysal-Biyikoglu, and G. Wornell, "Low Complexity Multiuser Scheduling for Maximizing Throughput in the MIMO Broadcast Channel," Proc. of 42nd Allerton Conf. on Comm, Control, and Computing, September 2004.

    This paper uses Lyapunov drift theory and max-weight matchings in conjunction with wireless MIMO systems.

  2. M. Kobayashi, G. Caire, and D. Gesbert, "Impact of Multiple Transmit Antennas in a Queued SDMA/TDMA Downlink," In Proc. 6th IEEE Workshop on Signal Processing Advances in Wireless Communications (SPAWC), June 2005.

    This paper also uses Lyapunov drift theory for stable sheduling in a wireless system with multiple antennas. It also considers links with errors and incorporates link success probability and queue backlog into the scheduling decision.

  3. E. Yeh and R. Berry, "Throughput optimal control of cooperative relay networks," Proc. of International Symposium on Information Theory, Adelaide, Australia, pp. 1206-1210, September 2005.

    This paper applies Lyapunov scheduling theory to a system of a source, a destination, and two intermediate relays. The relays can cooperate by sending the same signal for an improved transmission rate. This is the first paper to use Lyapunov drift and "backpressure" theory to a cooperate transmission problem, and it introduces the concept of "cooperation queues." A throughput-optimal scheduling strategy is constructed that chooses dynamically between cooperation or no cooperation based on queue backlog.

  4. T. Ho and H. Viswanathan, "Dynamic algorithms for multicast with intra-session network coding," In Proc. of 43rd Allerton Conf. on Communication, Control and Computing, September 2005.

    This paper is the first to use backpressure in a network coding scenario. It uses Lyapunov drift to analyze system stability, but augments system control options to include intra-session network coding. The system is shown to be stable whenever the arrival rates are within the region achievable by such coding.

  5. A. Eryilmaz and D. S. Lun, "Control for inter-session network coding," Proc. Information Theory and Applications Workshop (ITA), Jan./Feb. 2007.

    This paper looks at backpressure routing in combination with network coding, using a class of inter-session network coding techniques that are based on the 2-session butterfly model.

  6. M. J. Neely and R. Urgaonkar, "Optimal Backpressure Routing in Wireless Networks with Multi-Receiver Diversity," Ad Hoc Networks (Elsevier), 2008, DOI: 10.1016/J.ADHOC.2008.07.009. [Conference Version CISS 2006] [Slides] [CSI Tech Report].

    This paper looks at a wireless network with unreliable channels and possible mobility. It takes advantage of the multi-receiver diversity concept, where multiple neighboring nodes can overhear the same transmission--increasing the probability that at least one node successfully receives the transmission. This concept is also used in heuristic algorithms such as Selection Diversity Forwarding (SDF) [Larsson 2001], Geographic Random Forwarding (GeRaF) [Zorzi and Rao 2003], and Extremely Opportunistic Routing (ExOR) [Biswas and Morris 2005]. The paper develops the first throughput and energy optimal algorithm for this type of system: Diversity Backpressure Routing (DIVBAR). It uses a simple backpressure index to make the optimal decisions. A set of simulation results are also provided that demonstrate delay performance for enhanced versions of the algorithm.

  7. B. Smith and B. Hassibi, "Wireless Erasure Networks with Feedback," arXiv:0804.4298v1, April 2008.

    This paper looks at an ad-hoc network with multi-receiver diversity, similar to the scenario of the DIVBAR paper above. It uses a new Lyapunov function to derive an alternative stabilizing policy in the special case of a single sink. Unlike DIVBAR, the policy propagates multiple copies of the same packet throughout the network. At each random transmission opportunity, a node transmits a random packet in its buffer, without requiring the ACK/NACK response of DIVBAR. However, if a packet is eventually received by the sink, a feedback channel is assumed to delete all copies of that packet from the network. The rate of redundant packet transmissions goes to zero as the arrival rate approaches capacity, and so this policy also supports full throughput.

Low Complexity Scheduling and Complexity-Delay Tradeoffs
  1. L. Tassiulas, "Linear Complexity Algorithms for Maximum Throughput in Radio Networks and Input Queued Switches," Proc. IEEE INFOCOM, 1998.

    This paper looks at networks with scheduling constraints, such as NxN packet switches, and develops a simple randomized algorithm for scheduling. The algorithm approximates Max-Weight scheduling in the following way: It randomly and uniformly generates a server selection, compares its weight to the selection used in the previous slot, and takes the best of those two (the comparison takes linear, O(N), complexity). This is shown to be throughput optimal (although no delay guarantees are given).

    Note: This randomized algorithm works for general scheduling activation sets, including those where construction of the max weight (or max throughput) schedules would be NP complete. Intuitively, it can be viewed as an algorithm that takes a random (but possibly exponentially large) amount of time to compute the max weight match, and hence achieves throughput optimality for the same reason as in algorithms 2 and 3 below. For the same reason, the average delay is roughly proportional to the average time until we randomly choose the correct "Max Weight" match. It is possible to compute an O(N!) average delay bound for this algorithm in the case of a NxN packet switch, simply because the average time to randomly pick the best of N! choices is N! (see next reference 2 below, Neely et. al. 2002, for a more detailed discussion of the N! delay in comparison to a polynomial delay algorithm with similar linear complexity). Several more recent papers are developed that are similar to this randomized policy. However, it should be emphasized that these randomized algorithms all tend to incur exponential average delay in the worst case (particularly when the underlying scheduling problem is NP hard). Some algorithms may experimentally give sub-exponential delay for particular network topologies, although this is not fully understood.

  2. M. J. Neely, E. Modiano, and C.E. Rohrs, "Tradeoffs in Delay Guarantees and Computation Complexity for N x N Packet Switches" Proceedings of the Conference on Information Sciences and Systems, Princeton: March 2002. SLIDES

    This paper looks at low complexity switch scheduling in a NxN packet switch. It uses a simple technique of taking multiple slots to compute a max-weight match, which creates a one-for-one tradeoff between complexity and delay. Specifically, for any parameter "x" such that 0 <= x <= 3, an algorithm can be constructed to yield a per-timeslot complexity of O(N^{x}) with an average packet delay of O(N^{4-x}). Thus, for x=1, we have linear complexity with O(N^{3}) delay (superior to the randomized Tassiulas algorithm above that yields linear complexity with a delay bound of O(N!)), and for x=0 we have O(1) complexity (arbitrarily small), with O(N^{4}) delay. Thus, for systems where the max-weight match can be computed with polynomial complexity, this approach to tradeoff polynomial complexity for polynomial delay may be better than the randomized approach. Overall, this work demonstrates that it is easy to stabilize a network: What matters is joint stability with delay guarantees!

  3. D. Shah and M. Kopikare, "Delay Bounds for Approximate Maximum Weight Matching Algorithms for Input-Queue Switches," Proc. IEEE INFOCOM, 2002.

    This paper is very similar to the previous one, in that it uses a longer time frame to compute a max-weight match, where the complexity savings incurs longer average delay. The technique can be extended to show the same O(N^{x}), O(N^{4-x}) result described above. Both this paper and the [Neely et. al. 2002] paper above are based on the [Leonardi et. al. 2001] paper on average delay compuation for NxN switches.

  4. M. J. Neely, Jun Sun, Eytan Modiano, "Delay and Complexity Tradeoffs for Dynamic Routing and Power Allocation in a Wireless Network," Proceedings of the 40th Annual Allerton Conference on Communication, Control, and Computing, Oct. 2002. SLIDES

    This is a simple 2-page paper that uses network calculus to make complexity/delay tradeoffs for a network with worst case delay guarantees.

  5. E. Modiano, D. Shah, and G. Zussman, "Maximizing Throughput in Wireless Networks via Gossiping," Proc. ACM SIGMETRICS / IFIP Performance'06, June 2006.

    This paper extends the Tassiulas randomized scheduling framework above to general multi-hop networks. Several different types of randomized matches and comparison methods are considered. The algorithms yield 100% throughput, although delay is not directly considered (the delay would be exponential in cases of NP complete problems, as described above).

  6. S. Rajagopalan and D. Shah, "Reversible Networks, Distributed Optimization, and Network Scheduling: What do they have in common?" Proc. Conf. on Information Sciences and Systems (CISS), 2008.

    This paper looks at acceptance of calls in an optical network. It uses a different type of randomized algorithm that asymptotically finds an allocation that can maximize a weighted sum of rates (which can be used for throughput optimality). The randomized selection is based on generating exponential random variables and is related to the technique used in the paper below.

  7. Libin Jiang and Jean Walrand, "A Distributed CSMA Algorithm for Throughput and Utility Maximization in Wireless Networks," Proc. Allerton Conf. on Communication, Control, and Computing, 2008.

    This paper looks at wireless networking without timeslots, and uses a MAC that is similar to unslotted Aloha in that each node independently chooses to transmit at a random time distributed as an exponential random variable. However, the paper shows that if the rate of the exponential is chosen according to a backpressure based queue backlog, then the system yields 100% throughput. This would again suffer from the same (very long) delay in the worst case (when the problem is NP complete). However, it proves an insightful theorem relating max weight scheduling to maximizing the entropy of a Markov chain.

Queueing Analysis and Network Caclulus
  1. R. L. Cruz, "A Calculus for Network Delay. I. Network Elements in Isolation," IEEE Transactions on Information Theory, vol. 37, no. 1, pp. 114-131, Jan 1991.

    This is the foundational paper of network calculus, which analyzes queue length and delay in queueing systems with arrival processes characterized by deterministic traffic curves with rate and burst parameters (so called "leaky bucket" parameters).

  2. R. L. Cruz, "A Calculus for Network Delay. II. Network Analysis," IEEE Transactions on Information Theory, vol. 37, no. 1, pp. 132-141, Jan. 1991.

    This is the second part of the above paper and uses input-output relations of leaky-bucket traffic to obtain network queue and delay bounds.

  3. J-Y Le Boudec and P. Thiran, Network Calculus: A Theory of Deterministic Queueing Systems for the Internet." Online version of Springer-Verlag-LNCS 2050, May 10, 2004.

    This is a book on the topic of network calculus.

  4. A. K. Parekh and R. Gallager, "A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case," IEEE/ACM Trans. on Networking, Vol. 1, no. 3, pp. 344-357, June 1993.

    This paper looks at leaky bucket admission control and job scheduling in a queue with multiple users. The Packetized Generalized Processor Sharing rule is shown to closely track the performance of the fair "processor sharing" rule. Worst case queue and delay guarantees are obtained for leaky bucket sources.

  5. A. Parekh and R. Gallager, "A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Multiple Node Case," IEEE/ACM Trans. on Networking, vol. 2, no. 2, pp. 137-150, April 1994.

    This is the second part of the above paper and derives results for multi-hop networks.

  6. O. Yaron and M. Sidi, "Performance and Stability of Communication Networks via Robust Exponential Bounds," IEEE/ACM Trans. on Networking, vol. 1., no. 3., pp. 372-385, June 1993.

    This paper extends the deterministic network calculus techniques to stochastic arrival processes with "exponentially bounded burstiness" properties.

  7. C-S Chang, "Stability, queue length and delay of deterministic and stochastic queueing networks," IEEE Transactions on Automatic Control, Vol.39, pp. 913-931, 1994.

    This paper develops a theory of "minimum envelope rate" for networks, and demonstrates its input-output properties and its behavior under network routing. This is a stochastic network calculus framework and allows for queue stability and bounded delay results.

  8. D. Starobinski and M. Sidi, "Stochastically Bounded Burstiness for Communication Networks," IEEE Transactions on Information Theory, vol. 46, nol 1., Jan 2000.

    This paper extends the "exponentially bounded burstiness" traffic envelope technique to general (perhaps non-expnoential) stochastic arrivals, and analyzes the resulting input-output behavior for delay bounds in tree networks.

  9. M. Shalmon and M. A. Kaplan, "A Tandem Network of Queues with Deterministic Service and Intermediate Arrivals," Operations Research, vol. 32, no. 4, July-August 1984.

    This paper considers a tandem of deterministic service time queues with Poisson inputs at each stage and with a single output at the last stage. Exact steady state moment generating functions of delay are computed, using a conservation law principle.

  10. M. J. Neely, C. E. Rohrs, and E. Modiano, "Equivalent Models for Queueing Analysis of Deterministic Service Time Tree Networks," IEEE Transactions on Information Theory, Vol. 51, no. 10, pp. 3576-3584, Oct. 2005. [Slides Allerton 2000].

    This paper derives exact queue occupancy results for multi-input single-output tree networks with determinstic service times and arbitrary input traffic. It uses a similar queue conservation law as the above paper. Exact average backlog and delay in the network is derived in terms of a reduced 1-queue equivalent model. Bounds for networks with different service times at each node are also developed.

  11. M. J. Neely, "Exact Queueing Analysis of Discrete Time Tandems with Arbitrary Arrival Processes," IEEE Proceedings of the International Conference on Communications, June 2004.

    This paper uses the equivalent model technique from above and derives exact queue occupancy and average delay in a tandem of slotted queues with arrivals and departures at each stage under a simple "Furthest-to-Go" scheduling policy. The packet arrival processes are arbitrary, and the resulting delay bounds are also order-optimal.

  12. D. Wu and R. Negi, "Effective Capacity-Based Quality of Service Measures for Wireless Networks," ACM Mobile Networks and Applications (MONET) journal, vol. 11, no. 1, February 2006.

    This paper applies network calculus theory to time varying wireless links and tandems of such links. Delay properties are developed using effective capacity concepts for these networks.

  13. F. Ciucu, A. Burchard, and J. Liebeherr, "Scaling Properties of Statistical End-to-End Bounds in the Network Calculus," IEEE Transactions on Information Theory, vol. 52, no. 6, pp. 2300-2312, June 2006.

    This paper looks at stochastic network calculus in multi-input, multi-output tandems, and computes a network service curve. This results in a (near order-optimal) delay bound of O(Hlog(H)) for a tandem of H hops.


Network Economics
  1. P. Marbach and R. Berry, "Downlink Resource Allocation and Pricing for Wireless Networks," Proc. IEEE INFOCOM, June 2002.

    This paper shows that knowledge of user utility functions is needed for optimal pricing in a downlink, but asymptotic optimality can be acheived without this knowledge in a many user regime.

  2. T. Basar and R. Srikant, "Revenue-Maximizing Pricing and Capacity Expansion in a Many Users Regime," Proc. IEEE INFOCOM, June 2002.

    This paper provides some structural results on optimal prices and revenue for many TCP-like users sharing a bandwidth resource.

  3. D. Acemoglu, A. Ozdaglar, and R. Srikant, "The Marginal User Principle for Resource Allocation in Wireless Networks," Proc. of IEEE Conf. on Decision and Control, Dec. 2004.

    This looks at selecting a fixed price for wireless use, together with fixed power allocation. It is shown that power should be allocated according to a "marginal user" rule.

  4. L. He and J. Walrand, "Pricing Differentiated Internet Services, Proc. IEEE INFOCOM, March 2005.

    This paper looks at a 2-class service differentiation scenario from a game theory perspective, and shows that pricing according to different user preferences avoids equilibrium problems such as the "prisoner's dilemma."

  5. I. Ch. Paschalidis and J. N. Tsitsiklis, "Congestion-Dependent Pricing of Network Services," IEEE/ACM Transactions on Networking, vol. 8, no. 2, pp. 171-184, April 2000.

    This uses dynamic programming to look at maximum revenue call admission in a network. Pricing decisions for each call are made based on network congestion levels. Qualitiave structural results of the solution are obtained. Approximate approaches that use congestion-independent pricing are also developed and shown to perform well in a many-user regime.

  6. X. Lin and N. B. Shroff, "Simplification of Network Dynamics in Large Systems," IEEE/ACM Transactions on Networking, vol. 13, no. 4, pp. 813-826, August 2005.

    This looks at a related problem to the call admission and pricing problem of [Paschalidis, Tsitsiklis 2000], and considers general loss networks with possibly dynamic routing.

  7. L. Buttyan and J. -P. Hubaux, "Stimulating Cooperation in Self-Organizing Mobile Ad Hoc Networks," ACM/Kluwer Mobile Netowrks and Applications (MONET), vol. 8, no. 5, pp. 579-592, Oct. 2003.

    This paper considers a heuristic incentive mechanism with tokens that allow nodes in a network to forward their own data only after they have helped as a relay for other traffic.

  8. J. Crowcroft, R. Gibbens, F. Kelly, and S. Ostring, "Modeling Incentives for Collaboration in Mobile Ad-Hoc Networks," Proc. 1st. Int. Symp. on Modeling and Optimization in Mobile, Ad-Hoc, and Wireless Networks (WiOpt), Sophia-Antipolis, France, March 2003.

    This paper uses a heuristic credit-based approach to encourage cooperation and efficient operation in a mobile network.

  9. M. J. Neely, "Optimal Pricing in a Free Market Wireless Network," Wireless Networks, DOI 10.1007/S11276-007-0083-0. [Conference Version INFOCOM 2007] [Slides].

    This paper stimulates cooperation and relaying in an ad-hoc mobile network through a greedy algorithm that maximizes sum profit across all (self interested) network users, while ensuring non-negative profit and bounded worst case queue backlog to all participants. This also maximizes social wellfare. A non-greedy "Bang Bang" pricing algorithm is also developed to yield more balanced profits across network users.

  10. L. Huang and M. J. Neely, "The Optimality of Two Prices: Maximizing Revenue in a Stochastic Network," Proc. of 45th Annual Allerton Conference on Communication, Control, and Computing (invited paper), Sept. 2007. [PowerPoint Slides]

    This paper looks at a wireless service provider that charges users for service, such as a wireless access point. It shows that maximizing time average profit generally requires both a regular price and a reduced "sale" price (a single price is not enough). It then develops an algorithm that maximizes time average profit in a setting with variable user demands and costs.

Network Games
  1. T. Roughgarden and E. Tardos, "How Bad is Selfish Routing?" J. ACM, vol. 49, no. 2, pp. 236-259, 2002.

    A set of network links and rates to be supported is given, along with cost functions of total rate over each link. A greedy routing strategy is shown to provide a sum cost that is at least 3/4 the solution of the optimal, when link costs are linear. When link costs are more general, total cost of selfish routing is shown to be no worse than the opitmal cost of routing twice as much traffic.

  2. R. Johari and J. N. Tsitsiklis, "Efficiency Loss in a Network Resource Allocation Game," Mathematics of Operations Research, Aug. 2004.

    This looks at a congestion game where users anticipate the effect of their actions, and derives a 3/4 utility result.

  3. S. Yang and B. Hajek, "VCG-Kelly Mechanisms for Allocation of Goods: Adapting VCG Mechanisms to One-Dimensional Signals," IEEE Journal on Selected Areas in Communications, vol. 25, no. 6, Aug. 2007.

    This looks at a mechanism for efficient allocation for strategic buyers at Nash equilibrium.

  4. R. Jain and P. Varaiya, "The Combinatorial Seller's Bid Double Auction: An Asymptotically Efficient Market Mechanism," International Conf. on Game Theory, July 2007.

    This looks at mechanism design for trading resources in a communication network. Metrics of efficiency, rationality, budget-balancing, and incentive compatibility are considered, and mechansims that achieve 3 of these things while compromising on the fourth are developed.

  5. A. Ozdaglar, "Price Competition with Elastic Traffic," Networks, published online, Feb. 2008.

    Service providers own routes in a network and set prices to earn profit. A 2/3 efficiency principle is derived for a price competition game.

  6. J. Huang, R. Berry, and M. Honig, "Auction-Based Spectrum Sharing," ACM/Springer Journal of Mobile Networks and Applications (MONET), special issue on WiOpt'04, vol. 11, no. 3, pp. 405-418, June 2006.

    This considers auction mechanisms for sharing spectrum subject to a constraint on interference temperature at a measurement point. Social optimality results are derived in a large system limiting regime.

Distributed Optimization over a Network
  1. J. N. Tsitsiklis, D. P. Bertsekas, and M. Athens, "Distributed asynchronous deterministic and stochastic gradient optimization algorithms," IEEE Transactions on Automatic Control, Vol. AC-31, no. 9, September 1986.

    This paper looks at distributed computation over a network with asynchronous updates.

  2. D. Kempe, A. Dobra, and J. Gehrke, "Gossip-based computation of aggregate information," Proceedings of FOCS, 2003.

    This looks at gossip algorithms for aggregate network functions, such as sums and samples, and proves exponential convergence.

  3. D. Kempe and F. McSherry, "A decentralized algorithm for spectral analysis," Proc. of STOC, 2004.[[http://portal.acm.org/citation.cfm?id=1007438|pdf of paper]]

  4. Y. Bartal, J. W. Byers, and D. Raz, "Fast, distributed approximation algorithms for positive linear programming with applications to to flow control," SIAM Journal of Computing, vol. 33, no. 6, pp. 1261-1279, 2004.

    This looks at distributed compuation of linear programs, and the tradeoff between computation quality and communication time.

  5. M. J. Neely, "Distributed and Secure Computation of Convex Programs over a Network of Connected Processors," DCDIS Conference, Guelph, Ontario, Canada, July 2005.

    This paper looks at distributed computation of convex programs over a network, using the Lyapunov Optimization method for stochastic networks, but in a static setting. Convergence times and secure optimization of private utilities are considered.

  6. M. Andrews, K Jung, and A. Stolyar, "Stability of the Max-Weight Routing and Scheduling Protocol in Dynamic Networks and at Critical Loads," STOC 07.

    This paper looks at a static network flow problem and shows that backpressure and max-weight policy also yields bounded queues at the critical load (rate vector exactly on capacity boundary), which can be used to compute a solution to an epsilon-approximation in time that is 1/epsilon (but unfortunately exponential in the number of nodes).

Cognitive Radio (with Primary and Secondary Users)
  1. Y. Chen, Q. Zhao, and A. Swami, "Joint Design and Separation Principle for Opportunistic Spectrum Access in the Presence of Sensing Errors," IEEE Transactions on Information Theory, vol. 54, no. 5, pp. 2053-2071, May, 2008

    This paper uses a constrained partially observable Markov decision process (POMDP) framework to address the problem of maximizing the throughput of a secondary user while limiting the probability of colliding with primary users in the presence of channel sensing errors.

  2. R. Urgaonkar and M. J. Neely, Opportunistic Scheduling with Reliability Guarantees in Cognitive Radio Networks," Proc. IEEE INFOCOM, April 2008.

    This paper uses Lyapunov optimization theory to develop opportunistic scheduling policies in a cognitive radio network with primary (licensed) and secondary (unlicensed) users. It considers the problem of maximizing the throughput utility of the secondary users subject to maximum collision constraints with the primary users. It applies the virtual cost queue technique of [Neely 2006] in the form of "collision" queues that are used to provide strong reliability bounds in terms of the worst case number of collisions suffered by a primary user in any time interval.

Adaptive Channel Measurement
  1. S. Guha, K. Munagala, and S. Sarkar, "Approximation Schemes for Information Acquisition and Exploitation in Multichannel Wireless Networks," Proc. of the Allerton Conference on Communication, Control, and Computing, (invited paper), Sept. 2006.

    The goal of this paper is to maximize a linear utility through joint channel probing and channel selection mechanisms. The linear utility captures a tradeoff between the reward of serving packets and the cost of probing a subset of channels. An approximation algorithm is provided so that the linear utility can be made arbitrarily close to optimal, at the expense of increasing computation time.

  2. A. Gopalan, C. Caramanis, and S. Shakkottai, "On Wireless Scheduling with Partial Channel-State Information," Proc. of the Allerton Conference on Communication, Control, and Computing, Sept. 2007.

    In this paper continuous-time Lyapunov theory is used to develop a MaxWeight-type throughput optimal policy in a wireless downlink with partially observed channel states. In particular, the system model assumes that only a subset of channels (chosen from a fixed collection of subsets) can be observed at any time and only the channels with known states can serve packets.

  3. N. B. Chang and M. Liu, "Optimal Channel Probing and Transmission Scheduling for Opportunistic Spectrum Access," Proc. of ACM International Conference on Mobile Computing and Networking (MobiCom), Sept. 2007.

    The objective of this paper is to maximize a linear utility by choosing an optimal sequence of decisions of partial channel probing and rate allocations in a wireless network. Structural properties of the optimal policies are characterized by a dynamic programming formulation. A two-step look-ahead algorithm is shown to be optimal in some special cases.

  4. C. Li and M. J. Neely, "Energy-Optimal Scheduling with Dynamic Channel Acquisition in Wireless Downlinks," Proc. of 46th IEEE Conf. on Decision and Control, (invited paper), Dec. 2007.

    This paper considers serving multiple users in a wireless downlink system where channel states are only known through explicit channel probing that consumes power. It is shown that sometimes it is more energy efficient to transmit packets blindly, that is, without the knowledge of current channel states. Inspired by Lyapunov theory, a unified dynamic channel acquisition algorithm is proposed to stabilize the system for all date rates within the capacity region, while the average power consumption can be made arbitrarily close to optimal, at the expense of increasing network delays.


Backpressure Simulation and Experimentation
    Simulations of backpressure can be found in the simulation sections of the following papers:
    -[ Backpressure in Mobile Nets] -- "Dynamic Power...", Neely JSAC 2005.
    -[ Backpressure with Flow Control] -- "Fairness and Optimal...", Neely, Modiano, Li, INFOCOM 2005.
    -[ Energy Optimal Control in Mobile Networks] -- "Energy Optimal Control...", Neely, IT 2006.
    -[ Flow Control in Mesh Nets with Arbitrary Mobility] -- "Cross Layer Adaptive...", Neely, Urgaokar, Ad Hoc Networks (Elsevier) 2007.
    -[ DIVBAR with Enhanced Shortest Path for Delay Improvement] -- "Optimal Backpressure...", Neely, Urgaonkar, Ad Hoc Networks (Elsevier) 2008.

    Experimental results with backpressure can be found here:

  1. A. Sridharan, S. Moeller, and B. Krishnamachari, Making Distributed Rate Control using Lyapunov Drifts a Reality in Wireless Sensor Networks," 6th Intl. Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt), April 2008.

    This paper considers a tree of sensor nodes that communicate with a modified backpressure scheme that also uses CSMA. Preliminary experimental results are provided for a small 5-node testbed with Tmote sky class devices.

  2. A. Warrier, S. Ha, P. Wason, I. Rhee, and J. H. Kim "DiffQ: Differential Backlog Congestion Control for Multi-Hop Wireless Networks," Demo, SECON 2008.

    This paper implements a backpressure based algorithm on a 70-node wireless mesh test-bed at North Carolina State University.


Non-Stationary, Non-Ergodic Mobility
  1. M. J. Neely and R. Urgaonkar, "Cross Layer Adaptive Control for Wireless Mesh Networks," Ad Hoc Networks (Elsevier), vol. 5, no. 6, pp. 719-743, August 2007. [PowerPoint Slides]

    This paper looks at networks with arbitrary (possibly non-ergodic) mobility, and develops a theory of "instantaneous capacity regions." Specifically, it treats a mesh network with mobile clients and fixed mesh routers. Full throughput, with delay that is independent of the mobility timescales, is proven under the assumption that traffic rates are within the "instantaneous capacity region" at all times. Flow control algorithms are also used and analyzed in the case of arbitrary traffic rates (possibly outside of the instantaneous capacity regions at some times). A nice set of simulation results for backpressure and flow control in this context is also provided.


Additional Papers can be uploaded to the Editable Bibliography.

[SNO HOME] [M. J. NEELY HOME] [ADDITIONAL LINKS]