Skip to Main content Skip to Navigation
Conference papers

Large-Scale Network Utility Maximization: Countering Exponential Growth with Exponentiated Gradients

Abstract : Network utility maximization (NUM) is an iconic problem in network traffic management which is at the core of many current and emerging network design paradigms-and, in particular, software-defined networks (SDNs). Thus, given the exponential growth of modern-day networks (in both size and complexity), it is crucial to develop scalable algorithmic tools that are capable of providing efficient solutions in time which is dimension-free, i.e., independent-or nearly-independent-on the size of the system. To do so, we leverage a suite of modified gradient methods known as "mirror descent", and we derive a scalable and efficient algorithm for the NUM problem based on gradient exponentiation. We show that the convergence speed of the proposed algorithm only carries a logarithmic dependence on the size of the network, so it can be implemented reliably and efficiently in massively large networks where traditional gradient methods are prohibitively slow. These theoretical results are subsequently validated by extensive numerical simulations showing an improvement of several order of magnitudes over standard gradient methods in large-scale networks.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-03043622
Contributor : Panayotis Mertikopoulos <>
Submitted on : Monday, December 7, 2020 - 1:12:26 PM
Last modification on : Tuesday, December 8, 2020 - 3:30:01 AM

File

ExpGrad-INFOCOM.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03043622, version 1

Citation

Luigi Vigneri, Georgios Paschos, Panayotis Mertikopoulos. Large-Scale Network Utility Maximization: Countering Exponential Growth with Exponentiated Gradients. INFOCOM '19: Proceedings of the 38th IEEE International Conference on Computer Communications, 2019, Paris, France. ⟨hal-03043622⟩

Share

Metrics

Record views

5

Files downloads

17