Skip to main content
SpringerLink
Log in

SRPT applied to bandwidth-sharing networks

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

We consider bandwidth-sharing networks, and show how the SRPT (Shortest Remaining Processing Time) discipline can be used in order to improve the delay performance of the system. Our main idea is not to use SRPT globally between the traffic classes, which has been shown to induce instability, but rather deploy SRPT only locally within each traffic class. We show that with this approach, the performance of any stable bandwidth allocation policy can be improved. Importantly, our result is valid for any network topology and any flow size distribution. A numerical study is included to illustrate the results.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Avrahami, N., & Azar, Y. (2007). Minimizing total flow time and total completion time with immediate dispatching. Algorithmica, 47, 253–268.

    Article  Google Scholar 

  • Bertsekas, D., & Gallager, R. (1992). Data networks (2nd edn.). New York: Prentice-Hall.

    Google Scholar 

  • Bonald, T., & Massoulié, L. (2001). Impact of fairness on Internet performance. In ACM sigmetrics 2001 (pp. 82–91). Cambridge, MA.

  • Bonald, T., & Proutière, A. (2003). Insensitive bandwidth sharing in data networks. Queueing Systems, 44, 69–100.

    Article  Google Scholar 

  • Bramson, M. (2005). Stability of networks for max-min fair routing. In 13th INFORMS applied probability conference, Ottawa, Canada.

  • Chang, C. S., & Yao, D. D. (1993). Rearrangement, majorization, and stochastic scheduling. Mathematics of Operations Research, 18, 658–684.

    Article  Google Scholar 

  • Crovella, M., & Bestavros, A. (1996). Self-similarity in world wide web traffic: evidence and possible causes. In ACM SIGMETRICS 1996 (pp. 160–169), Philadelphia, PA.

  • de Veciana, G., Lee, T.-J., & Konstantopoulos, T. (2001). Stability and performance analysis of networks supporting elastic services. IEEE Transactions on Networking, 8, 556–567.

    Google Scholar 

  • Feldmann, A., & Whitt, W. (1997). Fitting mixtures of exponentials to long-tail distributions to analyze network performance models. In IEEE infocom 1997 (pp. 1096–1104), Kobe, Japan.

  • Gromoll, H. C., & Williams, R. J. (2006). Fluid limit of a network with fair bandwidth sharing and general document size distribution. Preprint.

  • Hirayama, T., & Kijima, M. (1992). Single machine scheduling problem when the machine capacity varies stochastically. Operations Research, 40, 376–383.

    Article  Google Scholar 

  • Kelly, F. P. (1997). Charging and rate control for elastic traffic. European Transactions on Telecommunications, 8, 33–37.

    Article  Google Scholar 

  • Kelly, F. P., Maulloo, A. K., & Tan, D. K. H. (1998). Rate control in communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Society, 49, 237–252.

    Article  Google Scholar 

  • Massoulié, L., & Roberts, J. (1999). Bandwidth sharing: objectives and algorithms. In IEEE infocom 1999 (pp. 1395–1403), New York, NY.

  • Massoulié, L., & Roberts, J. (2000). Bandwidth sharing and admission control for elastic traffic. Telecommunication Systems, 15, 185–201.

    Article  Google Scholar 

  • Massoulié, L. (2005). Structural properties of proportional fairness: stability and insensitivity. Preprint.

  • Mo, J., & Walrand, J. (2000). Fair end-to-end window-based congestion control. IEEE Transactions on Networking, 8, 556–567.

    Article  Google Scholar 

  • Schrage, L. E. (1968). A proof of the optimality of the shortest remaining processing time discipline. Operations Research, 16, 687–690.

    Article  Google Scholar 

  • Smith, D. R. (1978). A new proof of the optimality of the shortest remaining processing time discipline. Operations Research, 26, 197–199.

    Article  Google Scholar 

  • Verloop, I. M., Borst, S. C., & Núñez-Queija, R. (2005). Stability of size-based scheduling disciplines in resource-sharing networks. Performance Evaluation, 62, 247–262.

    Article  Google Scholar 

  • Verloop, I. M., Borst, S. C., & Núñez-Queija, R. (2006). Delay optimization in bandwidth-sharing networks. In CISS 2006, Princeton, NJ.

  • Yashkov, S. F. (1987). Processor-sharing queues: some progress in analysis. Queueing Systems, 2, 1–17.

    Article  Google Scholar 

  • Ye, H.-Q. (2003). Stability of data networks under an optimization-based bandwidth allocation. IEEE Transactions on Automatic Control, 48, 1238–1242.

    Article  Google Scholar 

  • Ye, H.-Q., Ou, J., & Yuan, X.-M. (2005). Stability of data networks: stationary and bursty models. Operations Research, 53, 107–125.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. TKK Helsinki University of Technology, Networking Laboratory,, P.O. Box 3000, 02015, Helsinki, Finland

    Samuli Aalto

  2. LAAS-CNRS, 7 Avenue du Colonel Roche, 31 077, Toulouse Cedex 4, France

    Urtzi Ayesta

Authors
  1. Samuli Aalto
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Urtzi Ayesta
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Samuli Aalto.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Aalto, S., Ayesta, U. SRPT applied to bandwidth-sharing networks. Ann Oper Res 170, 3–19 (2009). https://doi.org/10.1007/s10479-008-0427-x

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-008-0427-x

Keywords

Search

Navigation