Online network optimization using product-form Markov processes

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
2 Downloads (Pure)

Abstract

We develop a gradient algorithm for optimizing the performance of product-form networks through online adjustment of control parameters. The use of standard algorithms for finding optimal parameter settings is hampered by the prohibitive computational burden of calculating the gradient in terms of the stationary probabilities. The proposed approach instead relies on measuring empirical frequencies of the various states through simulation or online operation so as to obtain estimates for the gradient. Besides the reduction in computational effort, a further benefit of the online operation lies in the natural adaptation to slow variations in ambient parameters as commonly occurring in dynamic environments. On the downside, the measurements result in inherently noisy and biased estimates. We exploit mixing time results in order to overcome the impact of the bias and establish sufficient conditions for convergence to a globally optimal solution. We discuss our algorithm in the context of different systems, including queueing networks, loss networks, and wireless networks. We also illustrate how the algorithm can be used in such systems to optimize a service/cost trade-off, to map parameter regions that lead to systems meeting specified constraints, and to achieve target performance measures. For the latter application, we first identify which performance measures can be controlled depending on the set of configurable parameters. We then characterize the achievable region of performance measures in product-form networks, and finally we describe how our algorithm can be used to achieve the target performance in an online, distributed fashion, depending on the application context.

Original languageEnglish
Article number7279087
Pages (from-to)1838-1853
Number of pages16
JournalIEEE Transactions on Automatic Control
Volume61
Issue number7
DOIs
Publication statusPublished - 1 Jul 2016

Fingerprint

Markov processes
Queueing networks
Wireless networks
Costs

Keywords

  • achievable region
  • distributed control
  • Gradient algorithm
  • Markov processes
  • mixing times
  • online optimization
  • product-form networks
  • stochastic approximation

Cite this

@article{5c35ba1c39774092a3c6f4a2c6896b42,
title = "Online network optimization using product-form Markov processes",
abstract = "We develop a gradient algorithm for optimizing the performance of product-form networks through online adjustment of control parameters. The use of standard algorithms for finding optimal parameter settings is hampered by the prohibitive computational burden of calculating the gradient in terms of the stationary probabilities. The proposed approach instead relies on measuring empirical frequencies of the various states through simulation or online operation so as to obtain estimates for the gradient. Besides the reduction in computational effort, a further benefit of the online operation lies in the natural adaptation to slow variations in ambient parameters as commonly occurring in dynamic environments. On the downside, the measurements result in inherently noisy and biased estimates. We exploit mixing time results in order to overcome the impact of the bias and establish sufficient conditions for convergence to a globally optimal solution. We discuss our algorithm in the context of different systems, including queueing networks, loss networks, and wireless networks. We also illustrate how the algorithm can be used in such systems to optimize a service/cost trade-off, to map parameter regions that lead to systems meeting specified constraints, and to achieve target performance measures. For the latter application, we first identify which performance measures can be controlled depending on the set of configurable parameters. We then characterize the achievable region of performance measures in product-form networks, and finally we describe how our algorithm can be used to achieve the target performance in an online, distributed fashion, depending on the application context.",
keywords = "achievable region, distributed control, Gradient algorithm, Markov processes, mixing times, online optimization, product-form networks, stochastic approximation",
author = "J. Sanders and S.C. Borst and {Van Leeuwaarden}, J.S.H.",
year = "2016",
month = "7",
day = "1",
doi = "10.1109/TAC.2015.2482961",
language = "English",
volume = "61",
pages = "1838--1853",
journal = "IEEE Transactions on Automatic Control",
issn = "0018-9286",
publisher = "Institute of Electrical and Electronics Engineers",
number = "7",

}

Online network optimization using product-form Markov processes. / Sanders, J.; Borst, S.C.; Van Leeuwaarden, J.S.H.

In: IEEE Transactions on Automatic Control, Vol. 61, No. 7, 7279087, 01.07.2016, p. 1838-1853.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Online network optimization using product-form Markov processes

AU - Sanders, J.

AU - Borst, S.C.

AU - Van Leeuwaarden, J.S.H.

PY - 2016/7/1

Y1 - 2016/7/1

N2 - We develop a gradient algorithm for optimizing the performance of product-form networks through online adjustment of control parameters. The use of standard algorithms for finding optimal parameter settings is hampered by the prohibitive computational burden of calculating the gradient in terms of the stationary probabilities. The proposed approach instead relies on measuring empirical frequencies of the various states through simulation or online operation so as to obtain estimates for the gradient. Besides the reduction in computational effort, a further benefit of the online operation lies in the natural adaptation to slow variations in ambient parameters as commonly occurring in dynamic environments. On the downside, the measurements result in inherently noisy and biased estimates. We exploit mixing time results in order to overcome the impact of the bias and establish sufficient conditions for convergence to a globally optimal solution. We discuss our algorithm in the context of different systems, including queueing networks, loss networks, and wireless networks. We also illustrate how the algorithm can be used in such systems to optimize a service/cost trade-off, to map parameter regions that lead to systems meeting specified constraints, and to achieve target performance measures. For the latter application, we first identify which performance measures can be controlled depending on the set of configurable parameters. We then characterize the achievable region of performance measures in product-form networks, and finally we describe how our algorithm can be used to achieve the target performance in an online, distributed fashion, depending on the application context.

AB - We develop a gradient algorithm for optimizing the performance of product-form networks through online adjustment of control parameters. The use of standard algorithms for finding optimal parameter settings is hampered by the prohibitive computational burden of calculating the gradient in terms of the stationary probabilities. The proposed approach instead relies on measuring empirical frequencies of the various states through simulation or online operation so as to obtain estimates for the gradient. Besides the reduction in computational effort, a further benefit of the online operation lies in the natural adaptation to slow variations in ambient parameters as commonly occurring in dynamic environments. On the downside, the measurements result in inherently noisy and biased estimates. We exploit mixing time results in order to overcome the impact of the bias and establish sufficient conditions for convergence to a globally optimal solution. We discuss our algorithm in the context of different systems, including queueing networks, loss networks, and wireless networks. We also illustrate how the algorithm can be used in such systems to optimize a service/cost trade-off, to map parameter regions that lead to systems meeting specified constraints, and to achieve target performance measures. For the latter application, we first identify which performance measures can be controlled depending on the set of configurable parameters. We then characterize the achievable region of performance measures in product-form networks, and finally we describe how our algorithm can be used to achieve the target performance in an online, distributed fashion, depending on the application context.

KW - achievable region

KW - distributed control

KW - Gradient algorithm

KW - Markov processes

KW - mixing times

KW - online optimization

KW - product-form networks

KW - stochastic approximation

UR - http://www.scopus.com/inward/record.url?scp=84977080438&partnerID=8YFLogxK

U2 - 10.1109/TAC.2015.2482961

DO - 10.1109/TAC.2015.2482961

M3 - Article

AN - SCOPUS:84977080438

VL - 61

SP - 1838

EP - 1853

JO - IEEE Transactions on Automatic Control

JF - IEEE Transactions on Automatic Control

SN - 0018-9286

IS - 7

M1 - 7279087

ER -