research-article

Nonhomogeneous Place-dependent Markov Chains, Unsynchronised AIMD, and Optimisation

Authors:
Fabian R. Wirth

University of Passau, Germany

University of Passau, Germany

0000-0002-2123-3714
View Profile

,
Sonja Stüdli

University of Newcastle, Australia

University of Newcastle, Australia
View Profile

,
Jia Yuan Yu

Concordia University, Quebec, Canada

Concordia University, Quebec, Canada
View Profile

,
Martin Corless

Purdue University, Newcastle, West Lafayette, IN, USA

Purdue University, Newcastle, West Lafayette, IN, USA
View Profile

,
Robert Shorten

Imperial College London and University College Dublin, Dublin, Ireland

Imperial College London and University College Dublin, Dublin, Ireland
View Profile

Authors Info & Claims

Journal of the ACM Volume 66 Issue 4Article No.: 24pp 1–37https://doi.org/10.1145/3312741

Published:07 June 2019Publication History

Journal of the ACM

Abstract

A stochastic algorithm is presented for a class of optimisation problems that arise when a group of agents compete to share a single constrained resource in an optimal manner. The approach uses intermittent single-bit feedback, which indicates a constraint violation and does not require inter-agent communication. The algorithm is based on a positive matrix model of AIMD, which is extended to the nonhomogeneous Markovian case. The key feature is the assignment of back-off probabilities to the individual agents as a function of the past average access to the resource. This leads to a nonhomogeneous Markov chain in an extended state space, and we show almost sure convergence of the average access to the social optimum.

References

D. Angeli and P.-A. Kountouriotis. 2012. A stochastic approach to dynamic-demand refrigerator control. IEEE Trans. Control Syst. Technol. 20, 3 (2012), 581--592.Google ScholarCross Ref
M. F. Barnsley, S. G. Demko, J. H. Elton, and J. S. Geronimo. 1988. Invariant measures for Markov processes arising from iterated function systems with place-dependent probabilities. Annales de l’Institut Henri Poincaré (B) Probabilités et Statistiques 24, 3 (1988), 367--394.Google Scholar
S. Bhandarkar, A. L. N. Reddy, Y. Zhang, and D. Loguinov. 2007. Emulating AQM from end hosts. SIGCOMM Comput. Commun. Rev. 37, 4 (2007), 349--360. Google ScholarDigital Library
P. Bianchi, G. Fort, and W. Hachem. 2013. Performance of a distributed stochastic approximation algorithm. IEEE Trans. Info. Theory 59, 11 (2013), 7405--7418. Google ScholarDigital Library
B. Biegel, P. Andersen, T. S. Pedersen, K. M. Nielsen, J. Stoustrup, and L. H. Hansen. 2013. Smart grid dispatch strategy for ON/OFF demand-side devices. In Proceedings of the European Control Conference (ECC’13). 2541--2548.Google Scholar
P. Billingsley. 1995. Probability and Measure, 3rd ed. John Wiley 8 Sons, Hoboken, NJ.Google Scholar
V. S. Borkar. 2008. Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge University Press, Cambridge, UK.Google ScholarCross Ref
S. Boyd and L. Vandenberghe. 2004. Convex Optimization. Cambridge University Press, New York, NY. Google ScholarDigital Library
L. S. Brakmo, S. W. O'Malley, and L. L. Peterson. 1994. TCP Vegas: New techniques for congestion detection and avoidance. SIGCOMM Comput. Commun. Rev. 24, 4 (1994), 24--35. Google ScholarDigital Library
A. Brooks, E. Lu, D. Reicher, C. Spirakis, and B. Weihl. 2010. Demand dispatch. IEEE Power Energy Mag. 8, 3 (2010), 20--29.Google ScholarCross Ref
Ł. Budzisz, R. Stanojević, A. Schlote, F. Baker, and R. Shorten. 2011. On the fair coexistence of loss-and delay-based TCP. IEEE/ACM Trans. Netw. 19, 6 (2011), 1811--1824. Google ScholarDigital Library
M. Chiang, S. Low, R. Calderbank, and J. Doyle. 2007. Layering as optimization decomposition: A mathematical theory of network architectures. Proc. IEEE 95, 1 (2007), 255--312.Google ScholarCross Ref
K. Clement, E. Haesen, and J. Driesen. 2009. Coordinated charging of multiple plug-in hybrid electric vehicles in residential distribution grids. In Proceedings of the IEEE/PES Power Systems Conference and Exposition (PSCE’09). 1--7.Google Scholar
K. Clement-Nyns, E. Haesen, and J. Driesen. 2010. The impact of charging plug-in hybrid electric vehicles on a residential distribution grid. IEEE Trans. Power Syst. 25, 1 (2010), 371--380.Google ScholarCross Ref
M. Corless, C. King, R. Shorten, and F. Wirth. 2016. AIMD Dynamics and Distributed Resource Allocation. Number 29 in Advances in Design and Control. SIAM, Philadelphia, PA. Google ScholarDigital Library
E. Crisostomi, M. Liu, M. Raugi, and R. Shorten. 2014. Stochastic distributed algorithms for power generation in a microgrid. IEEE Trans. Smart Grid 5, 4 (2014), 2145--2154.Google ScholarCross Ref
E. Crisostomi, R. Shorten, S. Stüdli, and F. Wirth. 2017. Electric and Plug-in Hybrid Vehicle Networks: Optimization and Control. CRC Press, 2017.Google Scholar
S. Deilami, A. S. Masoum, P. S. Moses, and M. A. S. Masoum. 2011. Real-time coordination of plug-in electric vehicle charging in smart grids to minimize power losses and improve voltage profile. IEEE Trans. Smart Grid 2, 3 (2011), 456--467.Google ScholarCross Ref
J. Duchi, A. Agarwal, and M. Wainwright. 2012. Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Trans. Automat. Control 57, 3 (2012), 592--606.Google ScholarCross Ref
J. H. Elton. 1987. An ergodic theorem for iterated maps. Ergodic Theory Dynam. Systems 7, 4 (1987), 481--488.Google ScholarCross Ref
P. Ferarro, E. Crisostomi, R. Shorten, and F. Milano. 2018. Stochastic frequency control of grid-connected microgrids. IEEE Trans. Power Syst. 33, 5 (2018), 5704--5713.Google ScholarCross Ref
L. P. Fernández, T. G. San Róman, R. Cossent, C. M. Domingo, and P. Frías. 2011. Assessment of the impact of plug-in electric vehicles on distribution networks. IEEE Trans. Power Syst. 26, 1 (Feb. 2011), 206--213.Google Scholar
P. Finn, C. Fitzpatrick, and M. Leahy. 2009. Increased penetration of wind generated electricity using real time pricing; demand side management. In Proceedings of the IEEE International Symposium on Sustainable Systems and Technology (ISSST’09). IEEE, 1--6.Google Scholar
A. Fioravanti, J. Marecek, R. Shorten, M. Souza, and F. Wirth. 2017. On classical control and Smart Cities. In Proceedings of the 56th Conference on Decision and Control (CDC’17). 1412--1420.Google Scholar
S. Floyd. 2003. High Speed TCP for Large Congestion Windows. Technical Report. Internet draft draft-floyd-tcp-highspeed-02.txt, RFC 3649. Google ScholarDigital Library
W. Griggs, R. Ordonez-Hurtado, E. Crisostomi, F. Haeusler, K. Massow, and R. Shorten. 2015. A large-scale SUMO-based emulation platform. IEEE Trans. Intell. Transport. Syst. 16, 3 (2015), 3050--3059.Google ScholarDigital Library
A. Harris. 2000. Charge of the electric car {electric vehicles}. Engineer. Technol. 4, 10 (June 2000), 52--53.Google Scholar
D. J. Hartfiel. 2002. Nonhomogeneous Matrix Products. World Scientific, Singapore.Google Scholar
D. Hayes and G. Armitage. 2010. Improved coexistence and loss tolerance for delay-based TCP congestion control. In Proceedings of the IEEE Local Computer Network Conference. 24--31. Google ScholarDigital Library
V. Jacobson. 1988. Congestion avoidance and control. ACM SIGCOMM Comput. Commun. Rev. 18, 4 (1988), 314--329. Google ScholarDigital Library
B. Johansson, M. Rabi, and M. Johansson. 2009. A randomized incremental subgradient method for distributed optimization in networked systems. SIAM J. Control Optimiz. 20, 3 (2009), 1157--1170.Google ScholarDigital Library
K. Kar, S. Sarkar, and L. Tassiulas. 2001. A simple rate control algorithm for max total user utility. In Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’01), vol. 1. IEEE, 133--141 vol.1.Google Scholar
T. Kelly. 2002. On Engineering a Stable and Scalable TCP Variant. Technical Report. Cambridge University Engineering Department Technical Report CUED/F-INFENG/TR.435.Google Scholar
S. Kumar, S.-J. Park, and S. S. Iyengar. 2010. A loss-event driven scalable fluid simulation method for high-speed networks. Comput. Netw. 54, 1 (2010), 112--132. Google ScholarDigital Library
S. Kunniyur and R. Srikant. 2003a. End-to-end congestion control schemes: Utility functions, random losses and ECN marks. IEEE/ACM Trans. Netw. 11, 5 (2003), 689--702. Google ScholarDigital Library
S. S. Kunniyur and R. Srikant. 2003b. Stable, scalable, fair congestion control and AQM schemes that achieve high utilisation in the internet. IEEE Trans. Automat. Control 48, 11 (2003), 2024--2029.Google ScholarCross Ref
N. Li, L. Chen, and S. H. Low. 2011. Optimal demand response based on utility maximization in power networks. In Proceedings of the IEEE Power and Energy Society General Meeting. IEEE, 1--8.Google Scholar
S. Low, F. Paganini, and J. Doyle. 2002a. Internet congestion control. IEEE Control Syst. Mag. 32, 1 (2002), 28--43.Google Scholar
S. H. Low, L. L. Peterson, and L. Wang. 2002b. Understanding TCP Vegas: A duality model. J. ACM 49, 2 (2002), 207--235.Google ScholarDigital Library
G. Mann, R. T. McDonald, M. Mohri, N. Silberman, and D. Walker. 2009. Efficient large-scale distributed training of conditional maximum entropy models. Adv. Neural Info. Process. Syst. 22 (2009), 1231--1239. Google ScholarDigital Library
J. Masaki, G. G. D. Nishantha, and Y. Hayashida. 2010. Development of a high-speed transport protocol with TCP-Reno friendliness. In Proceedings of the International Conference on Advanced Communication Technology (ICACT’10), vol. 1. 174--179.Google Scholar
J. L. Mathieu, M. Kamgarpour, J. Lygeros, and D. S. Callaway. 2013. Energy arbitrage with thermostatically controlled loads. In Proceedings of the European Control Conference (ECC’13). IEEE, Zurich, Switzerland, 2519--2526.Google Scholar
S. Molnar, S. Balazs, and T. Tuan. 2009. A comprehensive TCP fairness analysis in high speed networks. Comput. Commun. 32 (2009), 1460--1484. Google ScholarDigital Library
A. Nedic and A. Ozdaglar. 2009. Distributed subgradient methods for multi-agent optimization. IEEE Trans. Automat. Control 54, 1 (2009), 48--61.Google ScholarCross Ref
G. A. Putrus, P. Suwanapingkarl, D. Johnston, E. C. Bentley, and M. Narayana. 2009. Impact of electric vehicles on power distribution networks. In Proceedings of the IEEE Vehicle Power and Propulsion Conference (VPPC’09). IEEE, 827--831.Google Scholar
S. S. Ram, A. Nedić, and V. V. Veeravalli. 2010. Distributed stochastic subgradient projection algorithms for convex optimization. J. Optim. Theory Appl. 147, 3 (2010), 516--545.Google ScholarCross Ref
S. Sayeef, S. Heslop, D. Cornforth, T. Moore, S. Percy, J. K. Ward, A. Berry, and D. Rowe. 2012. Solar intermittency: Australia’s clean energy challenge. Retrieved from http://www.csiro.au/Organisation-Structure/Flagships/Energy-Flagship/Solar-Intermittency-Report.aspx.Google Scholar
A. Schlote, F. Häusler, T. Hecker, A. Bergmann, E. Crisostomi, I. Radusch, and R. Shorten. 2013. Cooperative regulation and trading of emissions using plug-in hybrid vehicles. IEEE Trans. Intell. Transport. Syst. 14, 4 (2013), 1572--1585. Google ScholarDigital Library
S. E. Shafiei, H. Rasmussen, and J. Stoustrup. 2013. Model predictive control for a thermostatic controlled system. In Proceedings of the European Control Conference (ECC’13). IEEE, Zurich, Switzerland, 1559--1564.Google Scholar
R. Shorten, C. King, F. Wirth, and D. Leith. 2007. Modelling TCP congestion control dynamics in drop-tail environments. Automatica 43, 3 (2007), 441--449. Google ScholarDigital Library
R. Shorten, F. Wirth, and D. Leith. 2006. A positive systems model of TCP-like congestion control: Asymptotic analysis. IEEE/ACM Trans. Netw. 14 (2006), 616--629.Google ScholarDigital Library
S. Sinnot, R. Ordonez-Hurtado, G. Russo, and R. Shorten. 2016. On the design of a route parsing engine for connected vehicles with applications to congestion management systems. In Proceedings of the 19th IEEE International Conference on Intelligent Transportation. 1586--1591.Google Scholar
R. Srikant. 2004. Internet Congestion Control. Control Theory, vol. 14. Birkhäuser, Boston, MA.Google Scholar
S. Stuedli, E. Crisostomi, R. Middleton, and R. Shorten. 2012. A flexible distributed framework for realising electric and plug-in hybrid vehicle charging policies. Int. J. Control 85, 8 (2012), 1130--1145.Google ScholarCross Ref
K. Tan, J. Song, Q. Zhang, and M. Sridharan. 2006. A compound TCP approach for high-speed and long distance networks. In Proceedings of the 25th Conference of the IEEE Computer and Communications Societies (INFOCOM’06). 1--12.Google Scholar
D. X. Wei, C. Jin, S. H. Low, and S. Hegde. 2006. FAST TCP: Motivation, architecture, algorithms, performance. IEEE/ACM Trans. Netw. 14, 6 (2006), 1246--1259. Google ScholarDigital Library
F. Wirth, R. Stanojevic, R. Shorten, and D. Leith. 2006. Stochastic equilibria of AIMD communication networks. SIAM J. Matrix Anal. Appl. 28, 3 (2006), 703--723. Google ScholarDigital Library
L. Xu, K. Harfoush, and I. Rhee. 2004. Binary increase congestion control (BIC) for fast long-distance networks. In Proceedings of the Conference of the IEEE Computer and Communications Societies (INFOCOM’04). IEEE, 2514--2524.Google Scholar
M. Zinkevich, M. Weimer, A. J. Smola, and L. Li. 2010. Parallelized stochastic gradient descent. Adv. Neural Info. Process. Syst. 23 (2010), 2595--2603. Google ScholarDigital Library

Index Terms

Nonhomogeneous Place-dependent Markov Chains, Unsynchronised AIMD, and Optimisation
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
  2. Probability and statistics
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization

Recommendations

Uniformization for nonhomogeneous Markov chains

The discrete Poissonian representation for transition probabilities of homogeneous continuous-time Markov chains, known as uniformization or randomization, is extended to time-inhomogeneous chains. For computational purposes a discrete-time ...
Read More
Deterministic and stochastic convergence properties of AIMD algorithms with nonlinear back-off functions

In this paper we establish basic stability results for a class of nonlinear AIMD (additive-increase multiplicative-decrease) algorithms. We consider networks in which the nonlinearity enters through the multiplicative-decrease mechanism. In particular, ...
Read More
Sensitivity to the Service-Time Distribution in the Nonstationary Erlang Loss Model

The stationary Erlang loss model is a classic example of an insensitive queueing system: the steady-state distribution of the number of busy servers depends on the service-time distribution only through its mean. However, when the arrival process is a ...
Read More

Reviews

Reviewer: Bernard Kuc

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.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Published in
Journal of the ACM Volume 66, Issue 4
Networking, Computational Complexity, Design and Analysis of Algorithms, Real Computation, Algorithms, Online Algorithms and Computer-aided Verification
August 2019
299 pages
ISSN:0004-5411
EISSN:1557-735X
DOI:10.1145/3338848
Editor:
Éva Tardos
Cornell University
Issue’s Table of Contents
Copyright © 2019 ACM
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
- Published: 7 June 2019
- Revised: 1 January 2019
- Accepted: 1 January 2019
- Received: 1 March 2016
Published in jacm Volume 66, Issue 4

Permissions
Request permissions about this article.
Request Permissions

Check for updates
Author Tags
AIMD
Nonhomogeneous Markov chains
almost sure convergence
invariant measure
iterated function systems
optimisation
Qualifiers
- research-article
- Research
- Refereed
Conference
Funding Sources
Other Metrics
View Article Metrics

Article Metrics
- 9
  Total Citations
  View Citations
- 321
  Total Downloads
- Downloads (Last 12 months)16
- Downloads (Last 6 weeks)3
Other Metrics
View Author Metrics
Cited By
View all

PDF Format

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

HTML Format

View this article in HTML Format .

View HTML Format

Nonhomogeneous Place-dependent Markov Chains, Unsynchronised AIMD, and Optimisation

Journal of the ACM

Abstract

References

Cited By

Index Terms

Recommendations

Uniformization for nonhomogeneous Markov chains

Deterministic and stochastic convergence properties of AIMD algorithms with nonlinear back-off functions

Sensitivity to the Service-Time Distribution in the Nonstationary Erlang Loss Model

Reviews

Access critical reviews of Computing literature here