IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v60y2012i3p716-738.html
   My bibliography  Save this article

A Stochastic Network Under Proportional Fair Resource Control---Diffusion Limit with Multiple Bottlenecks

Author

Listed:
  • Heng-Qing Ye

    (Department of Logistics and Maritime Studies, Hong Kong Polytechnic University, Hong Kong)

  • David D. Yao

    (Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027)

Abstract

We study a multiclass stochastic processing network operating under the so-called proportional fair allocation scheme, and following the head-of-the-line processor-sharing discipline. Specifically, each server's capacity is shared among the job classes that require its service, and it is allocated, in every state of the network, among the first waiting job of each class to maximize a log-utility function. We establish the limiting regime of the network under diffusion scaling, allowing multiple bottlenecks in the network, and relaxing some of the conditions required in prior studies. We also identify the class of allocation schemes among which the proportional fair allocation minimizes a quadratic cost objective function of the diffusion-scaled queue lengths, and we illustrate the limitation of this asymptotic optimality through a counterexample.

Suggested Citation

  • Heng-Qing Ye & David D. Yao, 2012. "A Stochastic Network Under Proportional Fair Resource Control---Diffusion Limit with Multiple Bottlenecks," Operations Research, INFORMS, vol. 60(3), pages 716-738, June.
    • Handle: RePEc:inm:oropre:v:60:y:2012:i:3:p:716-738
    DOI: 10.1287/opre.1120.1047
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1120.1047
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1120.1047?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Heng-Qing Ye & Jihong Ou & Xue-Ming Yuan, 2005. "Stability of Data Networks: Stationary and Bursty Models," Operations Research, INFORMS, vol. 53(1), pages 107-125, February.
    2. Heng-Qing Ye & David D. Yao, 2010. "Utility-Maximizing Resource Control: Diffusion Limit and Asymptotic Optimality for a Two-Bottleneck Model," Operations Research, INFORMS, vol. 58(3), pages 613-623, June.
    3. Avishai Mandelbaum & Alexander L. Stolyar, 2004. "Scheduling Flexible Servers with Convex Delay Costs: Heavy-Traffic Optimality of the Generalized cμ-Rule," Operations Research, INFORMS, vol. 52(6), pages 836-855, December.
    4. Heng-Qing Ye & David D. Yao, 2008. "Heavy-Traffic Optimality of a Stochastic Network Under Utility-Maximizing Resource Allocation," Operations Research, INFORMS, vol. 56(2), pages 453-470, April.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Maury Bramson & Bernardo D’Auria & Neil Walton, 2017. "Proportional Switching in First-in, First-out Networks," Operations Research, INFORMS, vol. 65(2), pages 496-513, April.
    2. Anton Braverman, 2020. "Steady-State Analysis of the Join-the-Shortest-Queue Model in the Halfin–Whitt Regime," Mathematics of Operations Research, INFORMS, vol. 45(3), pages 1069-1103, August.
    3. Heng-Qing Ye & David D. Yao, 2016. "Diffusion Limit of Fair Resource Control—Stationarity and Interchange of Limits," Mathematics of Operations Research, INFORMS, vol. 41(4), pages 1161-1207, November.
    4. Chihoon Lee & Amy R. Ward & Heng-Qing Ye, 2020. "Stationary distribution convergence of the offered waiting processes for $$GI/GI/1+GI$$GI/GI/1+GI queues in heavy traffic," Queueing Systems: Theory and Applications, Springer, vol. 94(1), pages 147-173, February.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Wanyang Dai, 2013. "Optimal Rate Scheduling via Utility-Maximization for J -User MIMO Markov Fading Wireless Channels with Cooperation," Operations Research, INFORMS, vol. 61(6), pages 1450-1462, December.
    2. Heng-Qing Ye & David D. Yao, 2016. "Diffusion Limit of Fair Resource Control—Stationarity and Interchange of Limits," Mathematics of Operations Research, INFORMS, vol. 41(4), pages 1161-1207, November.
    3. Heng-Qing Ye & David D. Yao, 2010. "Utility-Maximizing Resource Control: Diffusion Limit and Asymptotic Optimality for a Two-Bottleneck Model," Operations Research, INFORMS, vol. 58(3), pages 613-623, June.
    4. Josh Reed & Bert Zwart, 2014. "Limit Theorems for Markovian Bandwidth-Sharing Networks with Rate Constraints," Operations Research, INFORMS, vol. 62(6), pages 1453-1466, December.
    5. Heng-Qing Ye & David D. Yao, 2008. "Heavy-Traffic Optimality of a Stochastic Network Under Utility-Maximizing Resource Allocation," Operations Research, INFORMS, vol. 56(2), pages 453-470, April.
    6. Hong Chen & Heng-Qing Ye, 2012. "Asymptotic Optimality of Balanced Routing," Operations Research, INFORMS, vol. 60(1), pages 163-179, February.
    7. Maury Bramson & Bernardo D’Auria & Neil Walton, 2017. "Proportional Switching in First-in, First-out Networks," Operations Research, INFORMS, vol. 65(2), pages 496-513, April.
    8. Maria Remerova & Josh Reed & Bert Zwart, 2014. "Fluid Limits for Bandwidth-Sharing Networks with Rate Constraints," Mathematics of Operations Research, INFORMS, vol. 39(3), pages 746-774, August.
    9. Amy R. Ward & Mor Armony, 2013. "Blind Fair Routing in Large-Scale Service Systems with Heterogeneous Customers and Servers," Operations Research, INFORMS, vol. 61(1), pages 228-243, February.
    10. Achal Bassamboo & J. Michael Harrison & Assaf Zeevi, 2006. "Design and Control of a Large Call Center: Asymptotic Analysis of an LP-Based Method," Operations Research, INFORMS, vol. 54(3), pages 419-435, June.
    11. Samuli Aalto & Urtzi Ayesta, 2009. "SRPT applied to bandwidth-sharing networks," Annals of Operations Research, Springer, vol. 170(1), pages 3-19, September.
    12. Gabriel Zayas‐Cabán & Emmett J. Lodree & David L. Kaufman, 2020. "Optimal Control of Parallel Queues for Managing Volunteer Convergence," Production and Operations Management, Production and Operations Management Society, vol. 29(10), pages 2268-2288, October.
    13. Łukasz Kruk, 2017. "Edge minimality of EDF resource sharing networks," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 86(2), pages 331-366, October.
    14. Xiaowei Mei & Hsing Kenneth Cheng & Subhajyoti Bandyopadhyay & Liangfei Qiu & Lai Wei, 2022. "Sponsored Data: Smarter Data Pricing with Incomplete Information," Information Systems Research, INFORMS, vol. 33(1), pages 362-382, March.
    15. Kuang Xu & Yuan Zhong, 2020. "Information and Memory in Dynamic Resource Allocation," Operations Research, INFORMS, vol. 68(6), pages 1698-1715, November.
    16. Rami Atar & Subhamay Saha, 2017. "Optimality of the generalized $$\varvec{c\mu }$$ c μ rule in the moderate deviation regime," Queueing Systems: Theory and Applications, Springer, vol. 87(1), pages 113-130, October.
    17. Gregory Dobson & Tolga Tezcan & Vera Tilson, 2013. "Optimal Workflow Decisions for Investigators in Systems with Interruptions," Management Science, INFORMS, vol. 59(5), pages 1125-1141, May.
    18. Merve Bodur & James R. Luedtke, 2017. "Mixed-Integer Rounding Enhanced Benders Decomposition for Multiclass Service-System Staffing and Scheduling with Arrival Rate Uncertainty," Management Science, INFORMS, vol. 63(7), pages 2073-2091, July.
    19. Rami Atar & Avi Mandelbaum & Gennady Shaikhet, 2009. "Simplified Control Problems for Multiclass Many-Server Queueing Systems," Mathematics of Operations Research, INFORMS, vol. 34(4), pages 795-812, November.
    20. J. G. Dai & Tolga Tezcan, 2011. "State Space Collapse in Many-Server Diffusion Limits of Parallel Server Systems," Mathematics of Operations Research, INFORMS, vol. 36(2), pages 271-320, May.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:60:y:2012:i:3:p:716-738. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.