Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Nonhomogeneous place-dependent Markov chains, unsynchronised AIMD, and optimisation
Wirth F., Stüdli S., Yu J., Corless M., Shorten R. Journal of the ACM66 (4):1-37,2019.Type:Article
Date Reviewed: Oct 19 2020

The transmission control protocol (TCP) that underpins most Internet traffic has a simple yet intuitively beautiful algorithm for congestion control. Every connection will gradually ramp up the bandwidth it uses until congestion occurs, at which point the connection throttles utilization. The additive-increase/multiplicative-decrease (AIMD) algorithm can be applied to a wide array of problem spaces where multiple agents compete for a limited resource.

The authors propose an algorithm that allows agents to respond probabilistically to a capacity constraint event, where such a response is determined by the agent’s success over either its entire past or some recent history interval. The authors also allow for each agent to have its own cost function. No inter-agent communication is required. The only coordination that is needed is for the shared resource to signal capacity constraint events and for an upfront global choice of a constant. This constant is chosen such that when multiplied by the derivative of each cost function and divided by that agent’s utilization, it gives a probability value between zero and one that can be used to decide whether to respond to a capacity event. Responses are considered asynchronous.

The authors prove that the algorithm will converge in the long run to an optimal state if the cost functions are strictly convex and continuously differentiable. They also show that despite having different cost functions, the agents converge to a common rate of change in their cost function. Although not the easiest paper to follow without domain knowledge or access to prior work, the authors do provide an excellent analysis of how their work differs from related research in a variety of domains.

Reviewer:  Bernard Kuc Review #: CR147085 (2012-0295)
Bookmark and Share
  Featured Reviewer  
 
Probability And Statistics (G.3 )
 
 
Miscellaneous (F.2.m )
 
 
Optimization (G.1.6 )
 
Would you recommend this review?
yes
no
Other reviews under "Probability And Statistics": Date
Probabilities from fuzzy observations
Yager R. (ed) Information Sciences 32(1): 1-31, 1984. Type: Article
Mar 1 1985
Randomness conservation inequalities; information and independence in mathematical theories
Levin L. Information and Control 61(1): 15-37, 1984. Type: Article
Sep 1 1985
The valuing of management information. Part I: the Bayesian approach
Carter M. Journal of Information Science 10(1): 1-9, 1985. Type: Article
May 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy