skip to main content
article

Time-scale decomposition and equivalent rate-based marking

Published: 01 October 2006 Publication History

Abstract

Differential equation models for Internet congestion control algorithms have been widely used to understand network dynamics and the design of router algorithms. These models use a fluid approximation for user data traffic and describe the dynamics of the router queue and user adaptation through coupled differential equations. The interaction between the routers and flows occurs through marking, where routers indicate congestion by appropriately marking packets during congestion.In this paper, we show that the randomness due to short and unresponsive flows in the Internet is sufficient to decouple the dynamics of the router queues from those of the end controllers. This implies that a time-scale decomposition naturally occurs such that the dynamics of the router manifest only through their statistical steady-state behavior. We show that this time-scale decomposition implies that a queue-length based marking function (e.g., RED-like and REM-like algorithms, which have no queue averaging, but depend only on the instantaneous queue length) has an equivalent form which depends only on the data arrival rate from the end-systems and does not depend on the queue dynamics. This leads to much simpler dynamics of the differential equation models (there is no queueing dynamics to consider), which enables easier analysis and could be potentially used for low-complexity fast simulation.Using packet-based simulations, we study queue-based marking schemes and their equivalent rate-based marking schemes for different types of controlled sources (i.e., proportional fair and TCP) and queue-based marking schemes. Our results indicate a good match in the rates observed at the intermediate router with the queue-based marking function and the corresponding rate-based approximation. Further, the window size distributions of a typical TCP flow with a queue-based marking function as well as the equivalent rate-based marking function match closely, indicating that replacing a queue-based marking function by its equivalent rate-based function does not statistically affect the end host's behavior.

References

[1]
{1} S. Floyd and V. Jacobson, "Random early detection gateways for congestion avoidance," IEEE/ACM Trans. Netw., vol. 1, no. 4, pp. 397-413, Aug. 1993.
[2]
{2} F. Kelly, "Mathematical modeling of the Internet," in Mathematics Unlimited-2001 and Beyond, B. Engquist and W. Schmid, Eds. Berlin, Germany: Springer-Verlag, 2001, pp. 685-702.
[3]
{3} S. H. Low, F. Paganini, and J. C. Doyle, "Internet congestion control," IEEE Control Syst. Mag., vol. 22, no. 1, pp. 28-43, Feb. 2002.
[4]
{4} S. Deb, S. Shakkottai, and R. Srikant, "Stability and convergence of TCP-like congestion controllers in a many-flows," in Proc. INFOCOM, San Francisco, CA, 2003, pp. 884-894.
[5]
{5} S. Low, F. Paganini, J. Wang, S. Adlakha, and J. C. Doyle, "Dynamics of TCP/RED and a scalable control," in Proc. IEEE INFOCOM, New York, 2002, vol. 1, pp. 239-248.
[6]
{6} S. Shakkottai and R. Srikant, "How good are deterministic fluid models of Internet congestion control?," in Proc. IEEE INFOCOM, New York, Jun. 2002, vol. 2, pp. 497-505.
[7]
{7} V. Misra, W.-B. Gong, and D. Towsley, "Fluid-based analysis of a network of AQM routers supporting TCP flows with an application to RED," in Proc. ACM SIGCOMM, 2000.
[8]
{8} S. Kunniyur and R. Srikant, "End-to-end congestion control: Utility functions, random losses and ECN marks," in Proc. IEEE INFOCOM, Tel Aviv, Israel, Mar. 2000, vol. 3, pp. 1323-1332.
[9]
{9} S. Kunniyur and R. Srikant, "Analysis and design of an adaptive virtual queue algorithm for active queue management," in Proc. ACM SIGCOMM, San Diego, CA, Aug. 2001, pp. 123-134.
[10]
{10} S. Athuraliya, V. H. Li, S. H. Low, and Q. Yin, "REM: Active queue management," IEEE Network, vol. 15, no. 3, pp. 48-53, May/Jun. 2001.
[11]
{11} P. Tinnakornsrisuphap and A. Makowski, "Limit behavior of ECN/RED gateways under a large number of TCP flows," in Proc. IEEE INFOCOM, San Francisco, CA, Apr. 2003, pp. 873-883.
[12]
{12} J. Cao and K. Ramanan, "A poisson limit for buffer overflow probabilities," in Proc. IEEE INFOCOM, New York, Jun. 2002, vol. 2, pp. 994-1003.
[13]
{13} M. Mandjes and J. H. Kim, "Large deviations for small buffers: An insensitivity result," Queueing Syst., vol. 37, pp. 349-362, 2001.
[14]
{14} F. P. Kelly, "Models for a self-managed Internet," Philos. Trans. Roy. Soc. A, vol. 358, pp. 2335-2348, 2000.
[15]
{15} S. Deb and R. Srikant, "Rate-based versus queue-based models of congestion control," in Proc. ACM SIGMETRICS, 2004.
[16]
{16} Ns-2, {Online}. Available: http://www.isi.edu/nsnam/ns/
[17]
{17} Parallel and Distributed NS PDNS {Online}. Available: http://www.cc. gatech.edu/computing/compass/pdns/
[18]
{18} GloMoSim, {Online}. Available: http://pcl.cs.ucla.edu/projects/glomosim/
[19]
{19} QualNet, {Online}. Available: http://www.scalable-networks.com
[20]
{20} R. Johari and D. Tan, "End-to-end congestion control for the Internet: Delays and stability," IEEE/ACM Trans. Netw., vol. 9, no. 6, pp. 818-832, Dec. 2001.
[21]
{21} D. Daley and D. Vere-Jones, An Introduction to the Theory of Point Processes. New York: Springer-Verlag, 1988.
[22]
{22} S. Shakkottai and R. Srikant, "Mean FDE models for Internet congestion control under a many-flows regime," IEEE Trans. Inf. Theory, vol. 50, no. 6, pp. 1050-1072, Jun. 2004.
[23]
{23} P. Billingsley, Convergence of Probability Measures. New York: Wiley-Interscience, 1999.
[24]
{24} W. L. Smith, "Regenerative stochastic processes," in Proc. Roy. Soc. London A, 1955, vol. 232, pp. 6-31.
[25]
{25} S. I. Resnick, Adventures in Stochastic Processes. Boston, MA: Birkhauser, 1992.
[26]
{26} R. W. Wolff, Stochastic Modeling and the Theory of Queues. Englewood Cliffs, NJ: Prentice-Hall, 1989.
[27]
{27} U. M. J. Roberts and J. Virtamo, Broadband Network Teletraffic, Final Report of Action COST 242 Birkhauser, Boston, MA, 1992.
[28]
{28} J. Virtamo, "Numerical evaluation of the distribution of unfinished work in an M/D/1 system," Electron. Lett., vol. 31, no. 7, pp. 531-532, 1995.
[29]
{29} S. Floyd, "Thoughts on the evolution of TCP in the Internet," in Proc. 2nd Int. Workshop Protocols for Fast Long-Distance Networks, 2004.
[30]
{30} C. V. Hollot, Y. Liu, V. Misra, and D. Towsley, "Unresponsive flows and AQM performance," in Proc. INFOCOM, San Francisco, CA, Apr. 2003, vol. 1, pp. 85-95.
[31]
{31} H. Kim and J. C. Hou, "Network calculus based simulation for TCP congestion control: Theorems, implementation and evaluation," in Proc. IEEE INFOCOM, Mar. 2004, vol. 4, pp. 2844-2855.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 14, Issue 5
October 2006
226 pages

Publisher

IEEE Press

Publication History

Published: 01 October 2006
Published in TON Volume 14, Issue 5

Author Tags

  1. internet congestion control
  2. marking functions
  3. time-scale decomposition

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 240
    Total Downloads
  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media