Abstract
This paper presents a new mathematical model of AIMD (Additive Increase Multiplicative Decrease) TCP for general networks that we believe is better than those previously used when it is driven by bottleneck capacities. Extending the paper by Edmonds, Datta, and Dymond that solves the single bottleneck case, we view AIMD as a distributed scheduling algorithm and prove that with extra resources, it is competitive against the optimal global algorithm in minimizing the average flow time of the jobs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Baccelli, F., Hong, D.: AIMD, Fairness and Fractal Scaling of TCP Traffic RR-4155 INRIA Rocquencourt and Infocom (June 2002)
Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)
Chiu, D.M., Jain, R.: Analysis of the increase and decrease algorithms for congestion avoidance in computer networks. Computer networks and ISDN systems 17(1), 1–14 (1989)
Edmonds, J.: Scheduling in the dark. Journal of Theoretic Computer Science (1999); ACM Symposium on Theory of Computing, pp. 179–188 (1999)
Edmonds, J.: Scheduling in the dark – improved results: manuscript (2001), http://www.cs.yorku.ca/~jeff
Edmonds, J., Datta, S., Dymond, P.: TCP is Competitive Agains a Limited Adversary. In: Proc. 15th Ann. ACM Symp. of Parallelism in Algorithms and Achitectures, pp. 174–183 (2003)
Floyd, S.: Connections with multiple congested gateways in packet-switched networks, part I: One-way traffic. Computer communications review 21(5), 30–47 (1991)
Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as Clairvoyance. Journal of the ACM 47(4), 617–643 (2000)
Karp, R., Koutsoupias, E., Papadimitriou, C., Shenker, S.: Optimization problems in congestion control. In: IEEE Symposium on Foundations of Computer Science, pp. 66–74 (2000)
Kelly, F.: Mathematical modelling of the internet. In: Engquist, B., Schmid, W. (eds.) Mathematics Unlimited – 2001 and Beyond. Springer, Heidelberg (2001)
Kelly, F.: Fairness and stability of end-to-end congestion control European Control Conference, Cambridge (2003)
Kelly, F., Maulloo, A., Tan, D.: Rate control in communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Society 49 (1998)
Kurose, J., Ross, K.: Computer networking: A top-down approach featuring the Internet. Addison-Wesley, Reading (2002)
Motwani, R., Phillips, S., Torng, E.: Non-clairvoyant scheduling. Theoretical computer science (Special issue on dynamic and on-line algorithms) 130, 17–47 (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Edmonds, J. (2004). On the Competitiveness of AIMD-TCP within a General Network. In: Farach-Colton, M. (eds) LATIN 2004: Theoretical Informatics. LATIN 2004. Lecture Notes in Computer Science, vol 2976. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24698-5_59
Download citation
DOI: https://doi.org/10.1007/978-3-540-24698-5_59
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21258-4
Online ISBN: 978-3-540-24698-5
eBook Packages: Springer Book Archive