Minimizing Queue Length Regret Under Adversarial Network Models
Stochastic models have been dominant in network optimization theory for over two decades, due totheir analytical tractability. However, these models fail to capture non-stationary or even adversarialnetwork dynamics which are of increasing importance for modeling the behavior of networks...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Association for Computing Machinery (ACM)
2020
|
| Online Access: | https://hdl.handle.net/1721.1/126332 |
| _version_ | 1811091519314067456 |
|---|---|
| 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 totheir analytical tractability. However, these models fail to capture non-stationary or even adversarialnetwork dynamics which are of increasing importance for modeling the behavior of networksunder malicious attacks or characterizing short-term transient behavior. In this paper, we focuson minimizing queue length regret under adversarial network models, which measures the finite-time queue length difference between a causal policy and an “oracle” that knows the future. Twoadversarial network models are developed to characterize the adversary’s behavior. We provide lowerbounds on queue length regret under these adversary models and analyze the performance of twocontrol policies (i.e., the MaxWeight policy and the Tracking Algorithm). We further characterizethe stability region under adversarial network models, and show that both the MaxWeight policyand the Tracking Algorithm are throughput-optimal even in adversarial settings. |
| first_indexed | 2024-09-23T15:03:40Z |
| format | Article |
| id | mit-1721.1/126332 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:03:40Z |
| publishDate | 2020 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1263322022-09-29T12:23:40Z Minimizing Queue Length Regret Under Adversarial Network Models 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 totheir analytical tractability. However, these models fail to capture non-stationary or even adversarialnetwork dynamics which are of increasing importance for modeling the behavior of networksunder malicious attacks or characterizing short-term transient behavior. In this paper, we focuson minimizing queue length regret under adversarial network models, which measures the finite-time queue length difference between a causal policy and an “oracle” that knows the future. Twoadversarial network models are developed to characterize the adversary’s behavior. We provide lowerbounds on queue length regret under these adversary models and analyze the performance of twocontrol policies (i.e., the MaxWeight policy and the Tracking Algorithm). We further characterizethe stability region under adversarial network models, and show that both the MaxWeight policyand the Tracking Algorithm are throughput-optimal even in adversarial settings. National Science Foundation (U.S.) (Grant CNS-1524317) United States. Defense Advanced Research Projects Agency. Information Innovation Office (Contract HROO l l-l 5-C-0097) 2020-07-23T11:22:19Z 2020-07-23T11:22:19Z 2018-03 2019-10-30T14:57:56Z Article http://purl.org/eprint/type/JournalArticle 2476-1249 https://hdl.handle.net/1721.1/126332 Liang, Qingkai and Eytan Modiano. “Minimizing Queue Length Regret Under Adversarial Network Models.” Proceedings of the ACM on measurement and analysis of computing systems, vol. 2, no. 1, 2018, Article 11 © 2018 The Author(s) en 10.1145/3179414 Proceedings of the ACM on measurement and analysis of computing systems Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) MIT web domain |
| spellingShingle | Liang, Qingkai Modiano, Eytan H Minimizing Queue Length Regret Under Adversarial Network Models |
| title | Minimizing Queue Length Regret Under Adversarial Network Models |
| title_full | Minimizing Queue Length Regret Under Adversarial Network Models |
| title_fullStr | Minimizing Queue Length Regret Under Adversarial Network Models |
| title_full_unstemmed | Minimizing Queue Length Regret Under Adversarial Network Models |
| title_short | Minimizing Queue Length Regret Under Adversarial Network Models |
| title_sort | minimizing queue length regret under adversarial network models |
| url | https://hdl.handle.net/1721.1/126332 |
| work_keys_str_mv | AT liangqingkai minimizingqueuelengthregretunderadversarialnetworkmodels AT modianoeytanh minimizingqueuelengthregretunderadversarialnetworkmodels |