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

Stability of Data Networks: Stationary and Bursty Models

Author

Listed:
  • Heng-Qing Ye

    (School of Business, National University of Singapore, 1 Business Link, Singapore)

  • Jihong Ou

    (School of Business, National University of Singapore, 1 Business Link, Singapore)

  • Xue-Ming Yuan

    (Singapore Institute of Manufacturing Technology, 71 Nanyang Drive, Singapore)

Abstract

This paper studies stability of network models that capture macroscopic features of data communication networks, including the Internet. The network model consists of a set of links and a set of possible routes that are fixed subsets of links. A connection is dynamically established along one of the routes to transmit data as requested and is terminated after the transmission is over. The transmission bandwidth of a link is dynamically allocated, according to specific bandwidth allocation policy, to ongoing connections that traverse the link. A network model is said to be stable under a given bandwidth allocation policy if, roughly, the number of ongoing connections in the network will not blow up over time. We consider a stationary and a bursty network model; the former assumes stochastically stationary arrival processes of connections as did many theoretical studies, while the latter allows more realistic bursty and correlated arrival processes. For both models under a necessary stability condition (i.e., the average offered transmission load on each link is within its bandwidth capacity), we show that the proportionally fair, the minimum potential delay, the max-min fair, and a class of utility-maximizing bandwidth allocation policies ensure network model stability, while some priority-oriented and maximum throughput policies do not. Interestingly, the bandwidth allocation policy that maximizes the arctan(·) utility ensures the stability of the stationary model but not the bursty model. This raises a serious concern about the current practice in the Internet protocol design, since such a policy is thought of as a good approximation of one of the most widely used TCP in the Internet.

Suggested Citation

  • 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.
  • Handle: RePEc:inm:oropre:v:53:y:2005:i:1:p:107-125
    DOI: 10.1287/opre.1040.0139
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1040.0139
    Download Restriction: no

    File URL: https://libkey.io/10.1287/opre.1040.0139?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. Hong Chen & Avi Mandelbaum, 1991. "Discrete Flow Networks: Bottleneck Analysis and Fluid Approximations," Mathematics of Operations Research, INFORMS, vol. 16(2), pages 408-446, May.
    2. J. G. Dai & G. Weiss, 1996. "Stability and Instability of Fluid Models for Reentrant Lines," Mathematics of Operations Research, INFORMS, vol. 21(1), pages 115-134, February.
    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. 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.
    2. 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.
    3. Yiting Xing & Ling Li & Zhuming Bi & Marzena Wilamowska‐Korsak & Li Zhang, 2013. "Operations Research (OR) in Service Industries: A Comprehensive Review," Systems Research and Behavioral Science, Wiley Blackwell, vol. 30(3), pages 300-353, May.
    4. 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.
    5. 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.
    6. Samuli Aalto & Urtzi Ayesta, 2009. "SRPT applied to bandwidth-sharing networks," Annals of Operations Research, Springer, vol. 170(1), pages 3-19, September.
    7. 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.
    8. Ł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.
    9. 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.

    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. Natalia Chernova & Sergey Foss & Bara Kim, 2012. "On the stability of a polling system with an adaptive service mechanism," Annals of Operations Research, Springer, vol. 198(1), pages 125-144, September.
    2. Legros, Benjamin & Jouini, Oualid & Akşin, O. Zeynep & Koole, Ger, 2020. "Front-office multitasking between service encounters and back-office tasks," European Journal of Operational Research, Elsevier, vol. 287(3), pages 946-963.
    3. Zhao, Yaping & Xu, Xiaoyun & Li, Haidong & Liu, Yanni, 2016. "Prioritized customer order scheduling to maximize throughput," European Journal of Operational Research, Elsevier, vol. 255(2), pages 345-356.
    4. Ward Whitt & Wei You, 2020. "Heavy-traffic limits for stationary network flows," Queueing Systems: Theory and Applications, Springer, vol. 95(1), pages 53-68, June.
    5. Kevin D. Glazebrook & José Niño-Mora, 1997. "Assessing an intuitive condition for stability under a range of traffic conditions via a generalised Lu-Kumar network," Economics Working Papers 429, Department of Economics and Business, Universitat Pompeu Fabra, revised Jan 2000.
    6. Hong Chen & Hanqin Zhang, 2000. "Stability of Multiclass Queueing Networks Under Priority Service Disciplines," Operations Research, INFORMS, vol. 48(1), pages 26-37, February.
    7. Koole, Ger & Pot, Auke, 2006. "Workload minimization in re-entrant lines," European Journal of Operational Research, Elsevier, vol. 174(1), pages 216-233, October.
    8. A. B. Dieker & J. Shin, 2013. "From Local to Global Stability in Stochastic Processing Networks Through Quadratic Lyapunov Functions," Mathematics of Operations Research, INFORMS, vol. 38(4), pages 638-664, November.
    9. Hong Chen & Tan Wang & David D. Yao, 2021. "Financial Network and Systemic Risk—A Dynamic Model," Production and Operations Management, Production and Operations Management Society, vol. 30(8), pages 2441-2466, August.
    10. J. G. Dai & J. H. Vande Vate, 2000. "The Stability of Two-Station Multitype Fluid Networks," Operations Research, INFORMS, vol. 48(5), pages 721-744, October.
    11. Pihnastyi, Oleh & Bondarenko, Kristina, 2016. "About the problem of selecting models for production line," MPRA Paper 91235, University Library of Munich, Germany, revised 07 Jan 2018.
    12. Lisa Fleischer & Jay Sethuraman, 2005. "Efficient Algorithms for Separated Continuous Linear Programs: The Multicommodity Flow Problem with Holding Costs and Extensions," Mathematics of Operations Research, INFORMS, vol. 30(4), pages 916-938, November.
    13. Shaler Stidham, 2002. "Analysis, Design, and Control of Queueing Systems," Operations Research, INFORMS, vol. 50(1), pages 197-216, February.
    14. Alexey Piunovskiy & Yi Zhang, 2011. "Accuracy of fluid approximations to controlled birth-and-death processes: absorbing case," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 73(2), pages 159-187, April.
    15. J. G. Dai & O. B. Jennings, 2004. "Stabilizing Queueing Networks with Setups," Mathematics of Operations Research, INFORMS, vol. 29(4), pages 891-922, November.
    16. Ward Whitt, 2001. "The Reflection Map with Discontinuities," Mathematics of Operations Research, INFORMS, vol. 26(3), pages 447-484, August.
    17. Dieter Armbruster & Daniel E. Marthaler & Christian Ringhofer & Karl Kempf & Tae-Chang Jo, 2006. "A Continuum Model for a Re-entrant Factory," Operations Research, INFORMS, vol. 54(5), pages 933-950, October.
    18. Vianney Bœuf & Philippe Robert, 2019. "A stochastic analysis of a network with two levels of service," Queueing Systems: Theory and Applications, Springer, vol. 92(3), pages 203-232, August.
    19. Yunan Liu & Ward Whitt, 2011. "A Network of Time-Varying Many-Server Fluid Queues with Customer Abandonment," Operations Research, INFORMS, vol. 59(4), pages 835-846, August.
    20. Jose Blanchet, 2013. "Optimal Sampling of Overflow Paths in Jackson Networks," Mathematics of Operations Research, INFORMS, vol. 38(4), pages 698-719, November.

    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:53:y:2005:i:1:p:107-125. 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.