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 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. Performance tradeoffs are provided in the form of utility-delay and energy-delay curves.

The papers introduce the mathematical tools of Lyapunov drift and Lyapunov optimization for networks, and derive the important techniques of backpressure routing, maximum weight matching, and generalized maximum weight scheduling. 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.

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]

    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.

  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 virutual 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.

    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.

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. The algorithm can be shown to achieve the tradeoff to within a logarithmic factor.

  2. M. J. Neely, "Optimal Energy and Delay Tradeoffs for Multi-User Wireless Downlinks," Proc. of IEEE INFOCOM, April 2006. [Slides from INFOCOM 2006]

    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. 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 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.

  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 for Wireless Networks," Proc. of the 39th Annual Allerton Conference on Communication, Control, and Computing, Oct. 2001.

    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.


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.


Back to M. J. Neely homepage