Network Utility Maximization in Adversarial Environments

Stochastic models have been dominant in network optimization theory for over two decades, due to their analytical tractability. However, these models fail to capture non-stationary or even adversarial network dynamics which are of increasing importance for modeling the behavior of networks under mal...

Full description

Bibliographic Details
Main Authors: Liang, Qingkai, Modiano, Eytan H
Other Authors: Massachusetts Institute of Technology. Laboratory for Information and Decision Systems
Format: Article
Language:English
Published: Institute of Electrical and Electronics Engineers (IEEE) 2020
Online Access:https://hdl.handle.net/1721.1/126329
_version_ 1826188289682440192
author Liang, Qingkai
Modiano, Eytan H
author2 Massachusetts Institute of Technology. Laboratory for Information and Decision Systems
author_facet Massachusetts Institute of Technology. Laboratory for Information and Decision Systems
Liang, Qingkai
Modiano, Eytan H
author_sort Liang, Qingkai
collection MIT
description Stochastic models have been dominant in network optimization theory for over two decades, due to their analytical tractability. However, these models fail to capture non-stationary or even adversarial network dynamics which are of increasing importance for modeling the behavior of networks under malicious attacks or characterizing short-term transient behavior. In this paper, we consider the network utility maximization problem in adversarial network settings. In particular, we focus on the tradeoffs between total queue length and utility regret which measures the difference in network utility between a causal policy and an 'oracle' that knows the future within a finite time horizon. Two adversarial network models are developed to characterize the adversary's behavior. We provide lower bounds on the tradeoff between utility regret and queue length under these adversarial models, and analyze the performance of two control policies (i.e., the Drift-plus-Penalty algorithm and the Tracking Algorithm).
first_indexed 2024-09-23T07:57:24Z
format Article
id mit-1721.1/126329
institution Massachusetts Institute of Technology
language English
last_indexed 2024-09-23T07:57:24Z
publishDate 2020
publisher Institute of Electrical and Electronics Engineers (IEEE)
record_format dspace
spelling mit-1721.1/1263292022-09-30T01:16:10Z Network Utility Maximization in Adversarial Environments Liang, Qingkai Modiano, Eytan H Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Stochastic models have been dominant in network optimization theory for over two decades, due to their analytical tractability. However, these models fail to capture non-stationary or even adversarial network dynamics which are of increasing importance for modeling the behavior of networks under malicious attacks or characterizing short-term transient behavior. In this paper, we consider the network utility maximization problem in adversarial network settings. In particular, we focus on the tradeoffs between total queue length and utility regret which measures the difference in network utility between a causal policy and an 'oracle' that knows the future within a finite time horizon. Two adversarial network models are developed to characterize the adversary's behavior. We provide lower bounds on the tradeoff between utility regret and queue length under these adversarial models, and analyze the performance of two control policies (i.e., the Drift-plus-Penalty algorithm and the Tracking Algorithm). National Science Foundation (U.S.) (Grant CNS-1524317) United States. Defense Advanced Research Projects Agency (Contract HROO l l-l 5-C-0097) 2020-07-22T20:42:55Z 2020-07-22T20:42:55Z 2018-04 2019-10-30T15:12:20Z Article http://purl.org/eprint/type/ConferencePaper 9781538641293 https://hdl.handle.net/1721.1/126329 Liang, Qingkai and Eytan Modiano. “Network Utility Maximization in Adversarial Environments.” Paper presented at the IEEE INFOCOM 2018 Conference, Honolulu, HI, April 15-19, 2018, IEEE © 2019 The Author(s) en 10.1109/INFOCOM.2018.8485973 IEEE INFOCOM 2018 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv
spellingShingle Liang, Qingkai
Modiano, Eytan H
Network Utility Maximization in Adversarial Environments
title Network Utility Maximization in Adversarial Environments
title_full Network Utility Maximization in Adversarial Environments
title_fullStr Network Utility Maximization in Adversarial Environments
title_full_unstemmed Network Utility Maximization in Adversarial Environments
title_short Network Utility Maximization in Adversarial Environments
title_sort network utility maximization in adversarial environments
url https://hdl.handle.net/1721.1/126329
work_keys_str_mv AT liangqingkai networkutilitymaximizationinadversarialenvironments
AT modianoeytanh networkutilitymaximizationinadversarialenvironments