Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-09T09:35:09.191Z Has data issue: false hasContentIssue false

16 - Stochastic network utility maximization and wireless scheduling

from Part IV - Theory and models

Published online by Cambridge University Press:  05 October 2012

By
Yung Yi  and
Mung Chiang
Edited by
Byrav Ramamurthy ,
George N. Rouskas  and
Krishna Moorthy Sivalingam
Yung Yi
Affiliation:
Korea Advanced Institute of Science and Technology, South Korea
Mung Chiang
Affiliation:
Princeton University, USA
Byrav Ramamurthy
Affiliation:
University of Nebraska, Lincoln
George N. Rouskas
Affiliation:
North Carolina State University
Krishna Moorthy Sivalingam
Affiliation:
Indian Institute of Technology, Madras
Get access

Summary

A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.
Image of the first page of this content. For PDF version, please use the ‘Save PDF’ preceeding this image.'
Type
Chapter
Information
Next-Generation Internet
Architectures and Protocols
 , pp. 324 - 358
Publisher: Cambridge University Press
Print publication year: 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Baccelli, F., McDonald, D. R., Reynier, J. (2002). A mean-field model for multiple TCP connections through a buffer implementing RED. Performance Evaluation 49, 1–4, 77–97.CrossRefGoogle Scholar
Bender, P., Black, P., Grob, M., et al. (2000). CDMA/HDR: a bandwidthefficient high-speed wireless data service for nomadic users. IEEE Communications Magazine 38, 4, 70–77.CrossRefGoogle Scholar
Bonald, T., Borst, S., Hegde, N., Proutière, A. (2004). Wireless data performance in multicell scenarios. In Proceedings of ACM Sigmetrics.Google Scholar
Bonald, T., Massoulie, L. (2001). Impact of fairness on internet performance. In Proceedings of ACM Sigmetrics.Google Scholar
Bonald, T., Massoulie, L., Proutière, A., Virtamo, J. (2006). A queueing analysis of max-min fairness, proportional fairness and balanced fairness. Queueing Systems 53, 1–2, 65–84.CrossRefGoogle Scholar
Bonald, T., Proutière, A. (2006). Flow-level stability of utility-based allocations for non-convex rate regions. In Proceedings of the 40th Conference on Information Sciences and Systems.Google Scholar
Bordenave, C., McDonald, D., Proutière, A. (2008). Performance of random multi-access algorithms, an asymptotic approach. Proceedings of ACM Sigmetrics.CrossRefGoogle Scholar
Borst, S. (2003). User-level performance of channel-aware scheduling algorithms in wireless data networks. In Proceedings of IEEE Infocom.Google Scholar
Borst, S., Leskela, L., Jonckheere, M. (2008). Stability of parallel queueing systems with coupled rates. Discrete Event Dynamic Systems. In press.Google Scholar
Bramson, M. (1998). State space collapse with application to heavy traffic limits for multiclass queueing networks. Queueing Systems 30, 1–2, 89–148.CrossRefGoogle Scholar
Bramson, M. (2005). Stability of networks for max-min fair routing. In Presentation at INFORMS Applied Probability Conference.Google Scholar
Brzesinski, A., Zussman, G., Modiano, E. (2006). Enabling distributed throughput maximization in wireless mesh networks: a partitioning approach. In Proceedings of ACM Mobicom.Google Scholar
Chang, C. S., Liu, Z. (2004). A bandwidth sharing theory for a large number of http-like connections. IEEE/ACM Transactions on Networking 12, 5, 952–962.CrossRefGoogle Scholar
Chaporkar, P., Kar, K., Sarkar, S. (2005). Throughput guarantees through maximal scheduling in wireless networks. In Proceedings of the 43rd Annual Allerton Conference on Communication, Control and Computing.Google Scholar
Chen, L., Low, S. H., Chiang, M., Doyle, J. C. (2006). Joint optimal congestion control, routing, and scheduling in wireless ad hoc networks. In Proceedings of IEEE Infocom.Google Scholar
Chen, L., Low, S. H., Doyle, J. C. (2005). Joint congestion control and medium access control design for wireless ad-hoc networks. In Proceedings of IEEE Infocom.Google Scholar
Chiang, M. (2005). Balancing transport and physical layers in wireless multihop networks: jointly optimal congestion control and power control. IEEE Journal on Selected Areas in Communications 23, 1, 104–116.Google Scholar
Chiang, M., Low, S. H., Calderbank, A. R., Doyle, J. C. (2007). Layering as optimization decomposition. Proceedings of the IEEE 95, 1, 255–312.CrossRefGoogle Scholar
Chiang, M., Shah, D., Tang, A. (2006). Stochastic stability of network utility maximization: general file size distribution. In Proceedings of Allerton Conference.Google Scholar
Dai, J. G. (1995). On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models. Annals of Applied Probability 5, 49–77.CrossRefGoogle Scholar
Dai, J. G., Prabhakar, B. (2000). The throughput of data switches with and without speedup. In INFOCOM.Google Scholar
de Veciana, G., Lee, T., Konstantopoulos, T. (2001). Stability and performance analysis of networks supporting elastic services. IEEE/ACM Transactions on Networking 1, 2–14.CrossRefGoogle Scholar
Deb, S., Shakkottai, S., Srikant, R. (2005). Asymptotic behavior of internet congestion controllers in a many-flows regime. Mathematics of Operation Research 30, 2, 420–440.CrossRefGoogle Scholar
Dimaki, A., Walrand, J. (2006). Sufficient conditions for stability of longest queue first scheduling: second order properties using fluid limits. Advances in Applied Probability 38, 2, 505–521.CrossRefGoogle Scholar
Durvy, M., Thiran, P. (2006). Packing approach to compare slotted and non-slotted medium access control. In Proceedings of IEEE Infocom.Google Scholar
Eryilmaz, A., Ozdaglar, A., Modiano, E. (2007). Polynomial complexity algorithms for full utilization of multi-hop wireless networks. In Proceedings of IEEE Infocom.Google Scholar
Eryilmaz, A., Srikant, R. (2005). Fair resource allocation in wireless networks using queue-length-based scheduling and congestion control. In Proceedings of IEEE Infocom.Google Scholar
Eryilmaz, A., Srikant, R. (2006). Joint congestion control, routing, and MAC for stability and fairness in wireless networks. IEEE Journal on Selected Areas in Communications 24, 8, 1514–1524.CrossRefGoogle Scholar
Floyd, S., Jacobson, V. (1993). Random early detection gateways for congestion avoidance. IEEE/ACM Transactions on Networking 1, 4 (August), 397–413.CrossRefGoogle Scholar
Griffin, T. G., Shepherd, F. B., Wilfong, G. (2002). The stable paths problem and interdomain routing. IEEE/ACM Transactions on Networking 10, 2, 232–243.CrossRefGoogle Scholar
Gromoll, H. C., Williams, R. (2007). Fluid limit of a network with fair bandwidth sharing and general document size distribution. Annals of Applied Probability. In press.Google Scholar
Gupta, A., Lin, X., Srikant, R. (2007). Low-complexity distributed scheduling algorithms for wireless networks. In Proceedings of IEEE Infocom.Google Scholar
Gupta, G. R., Shroff, N. (2009). Delay analysis of multi-hop wireless networks. In Proceedings of IEEE Infocom.Google Scholar
Gupta, P., Stolyar, A. (2006). Optimal throughput in general random access networks. In Proceedings of CISS.Google Scholar
Hajek, B. (1988). Cooling schedules for optimal annealing. Mathematics of Operations Research 13, 2, 311–329.CrossRefGoogle Scholar
Jiang, L., Walrand, J. (2008). A CSMA distributed algorithm for throughput and utility maximization in wireless networks. Technical report, UCB.
Jin, C., Wei, D. X., Low, S. H. (2004). Fast TCP: motivation, architecture, algorithms, and performance. In Proceedings of IEEE Infocom.Google Scholar
Jonckheere, M., Borst, S. (2006). Stability of multi-class queueing systems with state-dependent service rates. In Proceedings of IEEE Value Tools.Google Scholar
Joo, C., Lin, X., Shroff, N. B. (2008). Understanding the capacity region of the greedy maximal scheduling algorithm in multihop wireless networks. In Proceedings of IEEE Infocom.Google Scholar
Joo, C., Shroff, N. B. (2007). Performance of random access scheduling schemes in multi-hop wireless networks. In Proceedings of IEEE Infocom.Google Scholar
Jung, K., Shah, D. (2007). Low delay scheduling in wireless network. In Proceeding of ISIT.Google Scholar
Kar, K., Sarkar, S., Tassiulas, L. (2004). Achieving proportional fairness using local information in Aloha networks. IEEE Transactions on Automatic Control 49, 10, 1858–1862.CrossRefGoogle Scholar
Kelly, F. (1979). Reversibility and Stochastic Networks. Wiley.Google Scholar
Kelly, F. P. (1997). Charging and rate control for elastic traffic. European Transactions on Telecommunications 8, 33–37.CrossRefGoogle Scholar
Kelly, F. P., Maulloo, A., Tan, D. (1998). Rate control in communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Society 49, 237–252.CrossRefGoogle Scholar
Kelly, F. P., Williams, R. J. (2004). Fluid model for a network operating under a fair bandwidth-sharing policy. Annals of Applied Probability 14, 1055–1083.Google Scholar
Kunniyur, S., Srikant, R. (2000). End-to-end congestion control: utility functions, random losses and ECN marks. In Proceedings of IEEE Infocom.Google Scholar
La, R. J., Anantharam, V. (2002). Utility-based rate control in the internet for elastic traffic. IEEE/ACM Transactions on Networking 10, 2, 272–286.CrossRefGoogle Scholar
Lakshmikantha, A., Beck, C. L., Srikant, R. (2004). Connection level stability analysis of the internet using the sum of squares (SOS) techniques. In Proceedings of the 38th Conference on Information Sciences and Systems.Google Scholar
Lee, J. W., Chiang, M., Calderbank, A. R. (2006a). Jointly optimal congestion and contention control based on network utility maximization. IEEE Communication Letters 10, 3, 216–218.Google Scholar
Lee, J. W., Chiang, M., Calderbank, R. A. (2006b). Utility-optimal medium access control: reverse and forward engineering. In Proceedings of IEEE Infocom.Google Scholar
Lin, X., Rasool, S. (2006). Constant-time distributed scheduling policies for ad hoc wireless networks. In Proceedings of IEEE CDC.Google Scholar
Lin, X., Shroff, N. B. (2004). On the stability region of congestion control. In Proceedings of the 42nd Annual Allerton Conference on Communication, Control and Computing.Google Scholar
Lin, X., Shroff, N. B. (2005). The impact of imperfect scheduling on crosslayer rate control in wireless networks. In Proceedings of IEEE Infocom.Google Scholar
Liu, J., Proutière, A., Yi, Y., Chiang, M., Poor, V. H. (2007). Flow-level stability of data networks with non-convex and time-varying rate regions. In Proceedings of ACM Sigmetrics.Google Scholar
Liu, J., Stolyar, A., Chiang, M., Poor, H. V. (2008). Queue backpressure random access in multihop wireless networks: optimality and stability. IEEE Transactions on Information Theory. In submission.Google Scholar
Liu, J., Yi, Y., Proutière, A., Chiang, M., Poor, H. V. (2009a). Adaptive CSMA: approaching optimality without message passing. Wiley Journal of Wireless Communications and Mobile Computing, Special Issue on Recent Advances in Wireless Communications and Networking.Google Scholar
Liu, J., Yi, Y., Proutière, A., Chiang, M., Poor, H. V. (2009b). Maximizing utility via random access without message passing. Technical report, Microsoft Research Labs, UK. September.
Liu, X., Chong, E. K. P., Shroff, N. B. (2001). Opportunistic transmission scheduling with resource-sharing constraints in wireless networks. IEEE Journal on Selected Areas in Communications 19, 10, 2053–2064.CrossRefGoogle Scholar
Low, S., Srikant, R. (2003). A mathematical framework for designing a low-loss low-delay internet. Network and Spatial Economics, Special Issue on Crossovers between Transportation Planning and Telecommunications 4, 75–101.Google Scholar
Low, S. H. (2003). A duality model of TCP and queue management algorithms. IEEE/ACM Transactions on Networking 11, 4, 525–536.CrossRefGoogle Scholar
Low, S. H., Lapsley, D. E. (1999). Optimization flow control, I: Basic algorithm and convergence. IEEE/ACM Transactions on Networking, 861–875.CrossRefGoogle Scholar
Low, S. H., Peterson, L., Wang, L. (2002). Understanding vegas: a duality model. Journal of ACM 49, 2 (March), 207–235.CrossRefGoogle Scholar
Luo, W., Ephremides, A. (1999). Stability of n interacting queues in randomaccess systems. IEEE Transactions on Information Theory 45, 5, 1579–1587.CrossRefGoogle Scholar
Marbach, P., Eryilmaz, A. (2008). A backlog-based CSMA-mechanism to achieve fairness and throughput-optimality in multihop wireless networks. In Proceedings of the 46th Annual Allerton Conference on Communication, Control and Computing.Google Scholar
Marbach, P., Eryilmaz, A., Ozdaglar, A. (2007). Achievable rate region of CSMA schedulers in wireless networks with primary interference constraints. In Proceedings of IEEE CDC.Google Scholar
Massoulie, L. (2007). Structural properties of proportional fairness: stability and insensitivity. Annals of Applied Probability 17, 3, 809–839.CrossRefGoogle Scholar
Mehyar, M., Spanos, D., Low, S. H. (2004). Optimization flow control with estimation error. In Proceedings of IEEE Infocom.Google Scholar
Mo, J., Walrand, J. (2000). Fair end-to-end window-based congestion control. IEEE/ACM Transactions on Networking 8, 5, 556–567.CrossRefGoogle Scholar
Modiano, E., Shah, D., Zussman, G. (2006). Maximizing throughput in wireless networks via gossiping. In Proceedings of ACM Sigmetrics.Google Scholar
Mohsenian-Rad, A. H., Huang, J., Chiang, M., Wong, V. W. S. (2009a). Utility-optimal random access: optimal performance without frequent explicit message passing. IEEE Transactions on Wireless Communications. To appear.Google Scholar
Mohsenian-Rad, A. H., Huang, J., Chiang, M., Wong, V. W. S. (2009b). Utility-optimal random access: reduced complexity, fast convergence, and robust performance. IEEE Transactions on Wireless Communications 8, 2, 898–911.CrossRefGoogle Scholar
Neely, M. J. (2006). Super-fast delay tradeoffs for utility optimal fair scheduling in wireless networks. IEEE Journal on Selected Areas in Communications 24, 8, 1489–1501.CrossRefGoogle Scholar
Neely, M. J., Modiano, E., Li, C. (2005). Fairness and optimal stochastic control for heterogeneous networks. In Proceedings of IEEE Infocom.Google Scholar
Neely, M. J., Modiano, E., Rohrs, C. E. (2002). Tradeoffs in delay guarantees and computation complexity for n × n packet switches. In Proceedings of CISS.Google Scholar
Ni, J., Srikant, R. (2009). Distributed CSMA/CA algorithms for achieving maximum throughput in wireless networks. In Invited talk in Information Theory and Applications Workshop.Google Scholar
Palomar, D., Chiang, M. (2006). Alternative decompositions for distributed maximization of network utility: framework and applications. In Proceedings of IEEE Infocom.Google Scholar
Pantelidou, A., Ephremides, A., Tits, A. L. (2005). Maximum throughput scheduling in time-varying-topology wireless ad-hoc networks. In Proceedings of Conference on Information Sciences and Systems.Google Scholar
Pantelidou, A., Ephremides, A., Tits, A. L. (2009). A cross-layer approach for stable throughput maximization under channel state uncertainty. ACM/Kluwer Journal of Wireless Networks. To appear.CrossRefGoogle Scholar
Preis, R. (1999). Linear time ½-approximation algorithm for maximum weighted matching in general graphs. In Proceedings of STOC.Google Scholar
Proutière, A., Yi, Y., Chiang, M. (2008). Throughput of random access without message passing. In Proceedings of CISS.Google Scholar
Ray, S., Sarkar, S. (2007). Arbitrary throughput versus complexity tradeoffs in wireless networks using graph partitioning. In Proceedings of Information Theory and Applications Second Workshop.Google Scholar
Sanghavi, S., Bui, L., Srikant, R. (2007). Distributed link scheduling with constant overhead. In Proceedings of ACM Sigmetrics.Google Scholar
Sarkar, S., Chaporkar, P., Kar, K. (2006). Fairness and throughput guarantee with maximal scheduling in multihop wireless networks. In Proceedings of Wiopt.Google Scholar
Sarkar, S., Kar, K. (2006). Achieving 2/3 throughput approximation with sequential maximal scheduling under primary internference constraints. In Proceedings of Allerton.Google Scholar
Shah, D., Wischik, D. J. (2006). Optimal scheduling algorithms for inputqueued switches. In Proceedings of IEEE Infocom.Google Scholar
Shakkottai, S. (2008). Effective capacity and QoS for wireless scheduling. IEEE Transactions on Automatic Control 53, 3, 749–761.CrossRefGoogle Scholar
Shakkottai, S., Srikant, R. (2004). Mean FDE models for Internet congestion control under a many-flows regime. IEEE Transactions on Information Theory 50, 6 (June).CrossRefGoogle Scholar
Shakkottai, S., Srikant, R., Stolyar, A. (2004). Pathwise optimality of the exponential scheduling rule for wireless channels. Advances in Applied Probability 36, 4, 1021–1045.CrossRefGoogle Scholar
Sharma, G., Mazumdar, R. R., Shroff, N. B. (2006). On the complexity of scheduling in wireless networks. In Proceedings of ACM Mobicom.Google Scholar
Shin, J., Shah, D., Rajagopalan, S. (2009). Network adiabatic theorem: an efficient randomized protocol for contention resolution. In Proceedings of ACM Sigmetrics.Google Scholar
Srikant, R. (2004). The Mathematics of Internet Congestion Control. Birkhauser.
Srikant, R. (2005). On the positive recurrence of a Markov chain describing file arrivals and departures in a congestion-controlled network. In IEEE Computer Communications Workshop.Google Scholar
Stolyar, A. (2006a). Greedy primal-dual algorithm for dynamic resource allocation in complex networks. Queueing Systems 54, 203–220.CrossRefGoogle Scholar
Stolyar, A. (2008). Dynamic distributed scheduling in random access network. Journal of Applied Probability 45, 2.CrossRefGoogle Scholar
Stolyar, A. L. (2004). Maxweight scheduling in a generalized switch: state space collapse and workload minimization in heavy traffic. Annals in Applied Probability 14, 1, 1–53.CrossRefGoogle Scholar
Stolyar, A. L. (2005). Maximizing queueing network utility subject to statbility: greedy primal-dual algorithm. Queueing Systems 50, 4, 401–457.CrossRefGoogle Scholar
Stolyar, A. L. (2006b). Large deviations of queues under QoS scheduling algorithms. In Proceedings of Allerton.Google Scholar
Szpankowski, W. (1994). Stability conditions for some multi-queue distributed systems: buffered random access systems. Annals of Applied Probability 26, 498–515.CrossRefGoogle Scholar
Tang, A., Lee, J. W., Chiang, M., Calderbank, A. R. (2006). Reverse engineering MAC. In Proceedings of IEEE Wiopt.Google Scholar
Tassiulas, L. (1998). Linear complexity algorithms for maximum throughput in radio networks and input queued switches. In Proceedings of IEEE Infocom.Google Scholar
Tassiulas, L., Ephremides, A. (1992). Stability properties of constrained queueing systems and scheduling for maximum throughput in multihop radio networks. IEEE Transactions on Automatic Control 37, 12, 1936–1949.CrossRefGoogle Scholar
Tinnakornsrisuphap, P., La, R. J. (2004). Characterization of queue fluctuations in probabilistic AQM mechanisms. In Proceedings of ACM Sigmetrics.Google Scholar
Venkataramanan, V. J., Lin, X. (2007). Structural properties of LDP for queue-length based wireless scheduling algorithms. In Proceedings of Allerton.Google Scholar
Wang, X., Kar, K. (2005). Cross-layer rate optimization for proportional fairness in multihop wireless networks with random access. In Proceedings of ACM Mobihoc.Google Scholar
Williams, R. J. (1998). An invariance principle for semimartingale reflecting brownian motions in an orthant. Queueing Systems and Theory Applications 30, 1–2, 5–25.CrossRefGoogle Scholar
Wu, X., Srikant, R. (2006). Bounds on the capacity region of multi-hop wireless networks under distributed greedy scheduling. In Proceedings of IEEE Infocom.Google Scholar
Yäiche, H., Mazumdar, R. R., Rosenberg, C. (2000). A game theoretic framework for bandwidth allocation and pricing of elastic connections in broadband networks: theory and algorithms. IEEE/ACM Transactions on Networking 8, 5, 667–678.CrossRefGoogle Scholar
Ye, H., Ou, J., Yuan, X. (2005). Stability of data networks: stationary and bursty models. Operations Research 53, 107–125.CrossRefGoogle Scholar
Yi, Y., Chiang, M. (2008). Wireless scheduling with O(1) complexity for m-hop interference model. In Proceedings of ICC.Google Scholar
Yi, Y., Proutière, A., Chiang, M. (2008). Complexity in wireless scheduling: Impact and tradeoffs. In Proceedings of ACM Mobihoc.Google Scholar
Yi, Y., Shakkottai, S. (2008). On the elasticity of marking functions in an integrated network. IEEE Transactions on Automatic Control. In press.Google Scholar
Yi, Y., Zhang, J., Chiang, M. (2009). Delay and effective throughput of wireless scheduling in heavy traffic regimes: vacation model for complexity. In Proceedings of ACM Mobihoc.Google Scholar
Ying, L., Shakkottai, S. (2009). Scheduling in mobile wireless networks with topology and channel-state uncertainty. In Proceedings of IEEE Infocom.Google Scholar
Ying, L., Srikant, R., Eryilmaz, A., Dullerud, G. E. (2006). A large deviations analysis of scheduling in wireless networks. IEEE Transactions on Information Theory, 5088–5098.CrossRefGoogle Scholar
Zhang, J., Zheng, D., Chiang, M. (2008). The impact of stochastic noisy feedback on distributed network utility maximization. IEEE Transactions on Information Theory 54, 2, 645–665.CrossRefGoogle Scholar
Zussman, G., Brzesinski, A., Modiano, E. (2008). Multihop local pooling for distributed throughput maximization in wireless networks. In Proceedings of IEEE Infocom.Google Scholar
Lee, J., Lee, J., Yi, Y., Chong, S., Proutière, A., Chiang, M. (2009). Implementing utility-optimal CSMA. In Proceedings of Allerton Conference.Google Scholar
Nardelli, B., Lee, J., Lee, K., Yi, Y., Chong, S., Knightly, E. W., Chiang, M. (2010). Technical report, Rice University.

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×