Abstract
Let a flow be a sequence of packets sent from a source computer to a destination computer. Routers at the core of the Internet do not maintain any information about the flows that traverse them. This has allowed for great speeds at the routers, at the expense of providing only best-effort service. In this paper, we consider the problem of fairly allocating bandwidth to each flow. We assume some flows request a constant amount of bandwidth from the network. The bandwidth that remains is distributed fairly among the rest of the flows. The fairness sought after is max-min fairness, which assigns to each flow the largest possible bandwidth that avoids affecting other flows. The distinguishing factor to other approaches is that routers only maintain a constant amount of state, which is consistent with trends in the Internet (such as the proposed Differentiated Services Internet architecture). In addition, due to the need for high fault-tolerance in the Internet, we ensure our protocol is self-stabilizing, that is, it tolerates a wide variety of transient faults.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Heinanen, J., Baker, F., Weiss, W., Wroclawski, J.: Assured forwarding phb group. Internet RFC 2597
Jacobson, V., Nichols, K., Poduri, K.: An expedited forwarding phb. Internet RFC 2598
Braden, R., Clark, D., Shenker, S.: Integrated services in the internet architecture. Internet RFC 1633
Wroclawski, J.: Specification of controlled-load network element service, Internet RFC 2211 (1997)
Boudec, J.-Y.L.: Rate adaptation, congestion control and fairness (2008), http://ica1www.epfl.ch/PS_files/LEB3132.pdf
Abraham, S., Kumar, A.: A stochastic approximation approach for max-min fair adaptive rate control of abr sessions with mcrs. In: Proceedings of IEEE INFOCOM, New York, NY (March 1999)
Charny, A.: An algorithm for rate allocation in a packet switching network with feedback, M.S. thesis, Massachusetts Institute of Technology (May 1994)
Hou, Y.T., Tzeng, H.H.Y., Panwar, S.S.: A generalized max-min rate allocation policy and its distributed implementation using the abr flow control mechanism. In: Proceedings of IEEE Infocom, San Francisco, CA (March 1998)
Ros, J., Tsai, W.K.: A general theory of constrained max-min rate allocation for multicast networks. In: IEEE International Conference on Networks, Singapore (2000)
Sarkar, S., Ren, T., Tassiulas, L.: Achieving fairness in multicasting with almost stateless rate control. In: Proceedings of the conference on Scalability and Traffic Control in IP Networks, SPIE, ITcom (2002)
Kim, Y., Tsai, W.K., Iyer, M., Ros, J.: Minimum rate guarantee without per-flow information. In: ICNP 1999: Proceedings of the Seventh Annual International Conference on Network Protocols, Washington, DC, USA, p. 155. IEEE Computer Society, Los Alamitos (1999)
Arora, A., Gouda, M.: Closure and convergence: A foundation of fault-tolerant computing. IEEE Transactions on Software Engineering 19(11), 1015–1027 (1993)
Dolev, S., Herman, T.: Superstabilizing protocols for dynamic distributed systems. Chicago Journal of Theoretical Computer Science 1997(4) (1997)
Dijkstra, E.W.: Self-stabilizing systems in spite of distributed control. Commun. ACM 17(11), 643–644 (1974)
Stoica, I., Zhang, H.: Providing guaranteed services without per-flow management. In: Proc. of the ACM SIGCOMM Conference (1999)
Zhang, Z., Duan, Z., Gao, L., Hou, Y.T.: Decoupling QoS control from core routers: A novel bandwidth architecture for scalable support for guaranteed services. In: Proc. ACM SIGCOMM Conference (2000)
Kaur, J., Vin, H.M.: Core-stateless guaranteed rate scheduling algorithms. In: Proc. of the IEEE INFOCOM Conf. (2001)
Kaur, J., Vin, H.M.: Core stateless guaranteed throughput networks. In: Proc. of the IEEE INFOCOM Conf. (2003)
Callon, R., Doolan, P., Feldman, N., Fredette, A., Swallow, G., Viswanathan, A.: A framework for multiprotocol label switching, Internet draft draft-ietf-mpls-framework-02.txt (1997)
Cobb, J.: Preserving quality of service without per-flow state. In: Proc. IEEE International Conference on Network Protocols (ICNP) (November 2001)
Cobb, J.: Scalable quality of service across multiple domains. Computer Communications 28(18), 1997–2008 (2005)
Cobb, J.A., Gouda, M.G.: Stabilization of max-min fair networks without per-flow state, Department of Computer Science Technical Report, The University of Texas at Dallas (September 2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cobb, J.A., Gouda, M.G. (2008). Stabilization of Max-Min Fair Networks without Per-flow State. In: Kulkarni, S., Schiper, A. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2008. Lecture Notes in Computer Science, vol 5340. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-89335-6_14
Download citation
DOI: https://doi.org/10.1007/978-3-540-89335-6_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-89334-9
Online ISBN: 978-3-540-89335-6
eBook Packages: Computer ScienceComputer Science (R0)