Cited By
View all- Shen SAkella A(2012)DECORProceedings of the 2012 IEEE 20th International Workshop on Quality of Service10.5555/2330748.2330776(1-9)Online publication date: 4-Jun-2012
Understanding XCP: equilibrium and fairness
Pages 1697 - 1710
Abstract
We prove that the XCP equilibrium solves a constrained max-min fairness problem by identifying it with the unique solution of a hierarchy of optimization problems, namely those solved by max-min fair allocation, but solved by XCP under an additional constraint. This constraint is due to the "bandwidth shuffling" necessary to obtain fairness. We describe an algorithm to compute this equilibrium and derive a lower and upper bound on link utilization. While XCP reduces to max-min allocation at a single link, its behavior in a network can be very different. We illustrate that the additional constraint can cause flows to receive an arbitrarily small fraction of their max-min fair allocations. We confirm these results using ns2 simulations.
References
[1]
V. Jacobson, "Congestion avoidance and control," in Proc. ACM SIGCOMM, Aug. 1988, pp. 314-329.
[2]
C. Hollot, V. Misra, D. Towsley, and W. Gong, "Analysis and design of controllers for AQM routers supporting TCP flows," IEEE Trans. Autom. Control, vol. 47, no. 6, pp. 945-959, Jun. 2002.
[3]
S. H. Low, F. Paganini, J. Wang, and J. C. Doyle, "Linear stability of TCP/RED and a scalable control," Comput. Netw. J., vol. 43, no. 5, pp. 633-647, 2003.
[4]
C. Casetti, M. Gerla, S. Mascolo, M. Sansadidi, and R. Wang, "TCP Westwood: End-to-end congestion control for wired/wireless networks," Wireless Netw. J., vol. 8, pp. 467-479, 2002.
[5]
S. Floyd, "High-speed TCP for large congestion windows," IETF, RFC 3649, Dec. 2003.
[6]
D. X. Wei, C. Jin, and S. H. Low, "FAST TCP: Motivation, architecture, algorithms, performance," IEEE/ACM Trans. Netw., vol. 14, no. 6, pp. 1246-1259, Dec. 2006.
[7]
I. Rhee and L. Xu, "CUBIC: A new TCP-friendly high-speed TCP variant," presented at the PFLDnet, 2005.
[8]
D. Leith and R. Shorten, "H-TCP: TCP for high-speed and long-distance networks," presented at the PFLDnet, Argonne, IL, 2004, in Proc..
[9]
D. Katabi, M. Handley, and C. Rohrs, "Congestion control for high-bandwidth delay product networks," in Proc. ACM SIGCOMM, 2002.
[10]
A. Falk, D. Katabi, and Y. Pryadkin, "Specification for the Explicit Control Protocol (XCP)," draft-falk-xcp-03.txt, 2007.
[11]
Y. Zhang and M. Ahmed, "A control theoretic analysis of XCP," in Proc. IEEE GLOBECOM, Mar. 2005, pp. 2831-2835.
[12]
F. Abrantes and M. Ricardo, "XCP for shared access multirate media," Comput. Commun. Rev., vol. 36, pp. 29-38, Jul. 2006.
[13]
Y. Sakumoto, H. Ohsaki, and M. Imase, "On XCP stability in a heterogeneous network," in Proc. Int. Symp. Comput. Commun., 2007, pp. 531-537.
[14]
C. Wilson, C. Coakley, and B. Y. Zhao, "Fairness attacks in the explicit control protocol," in Proc. IEEE IWQoS, 2007, pp. 21-28.
[15]
Y. Zhang and T. Henderson, "An implementation and experimental study of the explicit control protocol (XCP)," in Proc. IEEE INFOCOM, Miami, FL, 2005, pp. 1037-1048.
[16]
B. Wydrowski and M. Zukerman, "MaxNet: A congestion control architecture for max-min fairness," IEEE Commun. Lett., vol. 6, no. 11, pp. 512-514, Nov. 2002.
[17]
B. Wydrowski, L. L. H. Andrew, and M. Zukerman, "MaxNet: A congestion control architecture for scalable networks," IEEE Commun. Lett., vol. 7, no. 10, pp. 511-513, Oct. 2003.
[18]
H. Balakrishnan, N. Dukkipati, N. McKeown, and C. J. Tomlin, "Stability analysis of explicit congestion control protocols," IEEE Commun. Lett., vol. 11, no. 10, pp. 823-825, Oct. 2007.
[19]
S. Low, L. Andrew, and B.Wydrowski, "Understanding XCP: Equilibrium and fairness," in Proc. IEEE INFOCOM, 2005, pp. 1025-1036.
[20]
P. Wang and D. L. Mills, "Further analysis of XCP equilibrium performance," in Proc. IEEE Globecom, 2006, pp. 1-5.
[21]
J. M. Jaffe, "Bottleneck flow control," IEEE Trans. Commun., vol. COM-29, no. 7, pp. 954-962, Jul. 1981.
[22]
S. Athuraliya, V. H. Li, S. H. Low, and Q. Yin, "REM: Active queue management," IEEE Network, vol. 15, pp. 48-53, May/June 2001.
[23]
D. Bertsekas and R. Gallager, Data Networks, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 1992.
[24]
E. M. Gafni and D. P. Bertsekas, "Dynamic control of session input rates in communication networks," IEEE Trans. Autom. Control, vol. AC-29, no. 1, pp. 1009-1016, Jan. 1984.
[25]
NS Network Simulator, {Online}. Available: http://www.isi.edu/ nsnam/ns/
[26]
L. L. H. Andrew, B. P. Wydrowski, and S. H. Low, "An example of instability in XCP," {Online}. Available: http://netlab.caltech. edu/lachlan/abstract/xcpInstability.pdf, unpublished.
Index Terms
- Understanding XCP: equilibrium and fairness
Recommendations
Airtime Fairness for IEEE 802.11 Multirate Networks
Under a multi rate network scenario, the IEEE 802.11 DCF MAC fails to provide air-time fairness for all competing stations since the protocol is designed for ensuring max-min throughput fairness and the maximum achievable throughput by any station gets ...
A simulation study of xcp-b performance in wireless multi-hop networks
Q2SWinet '07: Proceedings of the 3rd ACM workshop on QoS and security for wireless and mobile networksXCP-b proposes a modification to the XCP router algorithm that computes the spare bandwidth. The modification removes the need for an XCP router to know the exact capacity of the channel, making it possible to use the XCP-b variant in transmission media ...
XCP for shared-access multi-rate media
The eXplicit Control Protocol (XCP) was developed to overcome some of the limitations of TCP, such as low utilization in high bandwidth delay product networks, unstable throughput, large queue build-up, and limited fairness. XCP, however, requires that ...
Comments
Information & Contributors
Information
Published In
Publisher
IEEE Press
Publication History
Published: 01 December 2009
Revised: 24 October 2008
Received: 27 February 2008
Published in TON Volume 17, Issue 6
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 305Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 15 Sep 2024
Other Metrics
Citations
Cited By
View all- Shen SAkella A(2012)DECORProceedings of the 2012 IEEE 20th International Workshop on Quality of Service10.5555/2330748.2330776(1-9)Online publication date: 4-Jun-2012
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in