This project introduces a novel paradigm for wireless network control, whereby control algorithms are designed to operate effectively in networks with uncooperative or adversarial users. Recent growth in mobile and media-rich applications has greatly increased the demand for wireless capacity. Network control algorithms for flow control, routing, and scheduling have the potential to significantly improve performance. However, these algorithms were designed under idealized assumptions, and cannot operate effectively in heterogeneous environments that includes uncooperative or even malicious users. Our approach, which differentiates us from other efforts in the field, is to design network control algorithms to operate effectively in adversarial environments from the onset – not as an afterthought.
We will develop a new network optimization framework for networks where some of the nodes, as well as the external dynamics, may be uncooperative and exhibit adversarial or even malicious behavior. Our framework envisions network control algorithms that are `secure-by-design,’ in the face of adversarial dynamics. Moreover, the network control algorithms will be designed in the spirit of `robust-optimization’ to perform well under worst-case conditions, while maintaining nearly optimal performance under normal conditions.
Participants:
Prof. Eytan Modiano, PI
Bai Liu, graduate student
Results:
In [1] we studied fundamental limits on volume-based network denial-of-service (DoS) attacks. Volume-based DoS attacks refer to a class of cyber attacks where an adversary seeks to block user traffic from service by sending adversarial traffic that reduces the available user capacity. In this work, we explore the fundamental limits of volume-based network DoS attacks by studying the minimum required rate of adversarial traffic and investigating optimal attack strategies. We start our analysis with single-hop networks where user traffic is routed to servers following the Join-the-Shortest-Queue (JSQ) rule. Given the service rates of servers and arrival rates of user traffic, we first characterize the feasibility region of the attack and show that the attack is feasible if and only if the rate of the adversarial traffic lies in the region. We then design an attack strategy that is (i). optimal: it guarantees the success of the attack whenever the adversarial traffic rate lies in the feasibility region and (ii). oblivious: it does not rely on knowledge of service rates or user traffic rates. Finally, we extend our results on the feasibility region of the attack and the optimal attack strategy to multi-hop networks that employ Back-pressure (Max-Weight) routing. At a higher level, this paper addresses a class of dual problems of stochastic network stability, i.e., how to optimally de-stabilize a network.
In [2] we consider the problem of network control in adversarial environments. Classic network optimization theory focuses on network models with stochastic dynamics and all nodes being observable and controllable. However, modern network systems often offer limited access and suffer from adversarial attacks. In this work we focus on networks with unobservable malicious nodes, where the network dynamics, such as external arrivals and control actions of malicious nodes can be adversarial. We first extend the existing adversarial network models by introducing a new maliciousness metric that constrains the dynamics of the adversary, and characterize the stability region of a network under adversarial dynamics. We then propose an algorithm that only operates on the accessible nodes and does not require direct observations of the malicious nodes, and show that our algorithm is stabilizing as long as the network dynamics are within the stability region. Finally, we show that our algorithm stabilizes the network even if the estimates of the network state are erroneous, and characterize the necessary and sufficient conditions for networks with unobservable malicious nodes to be stabilizable when subjected to estimation errors.
In [3] and [4] we consider the problem of network utility maximization with unknown utiity functions. Network Utility Maximization (NUM) studies the problems of allocating traffic rates to network users in order to maximize the users’ total utility subject to network resource constraints. In [3], we propose a new NUM framework, Learning-NUM, where the users’ utility functions are unknown apriori and the utility function values of the traffic rates can be observed only after the corresponding traffic is delivered to the destination, which means that the utility feedback experiences queueing delay. Our goal is to design a policy that learns the unknown utility functions and makes network scheduing and routing decisions so as to maximize network utility over a finite time horizon T. We first show that the expected total utility obtained by the best dynamic policy is upper bounded by the solution to a static optimization problem. Without the presence of feedback delay, we design an algorithm based on the ideas of gradient estimation and Max-Weight scheduling. To handle the feedback delay, we embedthe algorithm in a parallel-instance paradigm to form a policy that achieves O(T^3/4) regret, i.e., the difference between the expected utility obtained by the best dynamic policy and our policy is in O(T^3/4). We demonstrate the practical applicability of the Learning-NUM framework, in three application scenarios including database query, job scheduling and video streaming.
In [4] we consider a bipartite network consisting of job schedulers and parallel servers. Jobs arrive at the schedulers following stochastic processes with unknown arrival rates, and get routed to the servers, which execute the jobs with unknown service rates. The jobs are elastic, as their ‘‘size’’, i.e., the amount of service needed for their completion, is determined by the schedulers. After a job finishes execution, some utility is obtained where the utility value depends on the job’s size through some underlying concave utility function. We consider the setting where the utility functions are unknown apriori, while a noisy observation of the utility value of each job is obtained upon its completion. Our goal is to design a policy that makes job-size and routing decisions to maximize the total utility obtained by the end of the time horizon T . We measure the performance of a policy by regret, i.e., the gap between the expected utility obtained under the policy and that under the optimal policy. We first establish an upper bound on the regret of a generic policy, that consists of the cumulative difference in utility between the job-size decisions of the policy and the solution to a static optimization problem, and the total backlog of unfinished jobs at the end of the time horizon. We then propose a policy that simultaneously controls the cumulative utility difference and backlog of unfinished jobs, and achieves an order optimal regret of O(T^1/2). Our policy solves the elastic job scheduling problem by extending the Stochastic Convex Bandit Algorithm to handle unknown and stochastic constraints, and making routing decisions based on the Join-the-Shortest-Queue rule. It also presents a principled approach to extending algorithms for zeroth-order convex optimization to the settings with unknown and stochastic constraints.
Publications:
- Xinzhe fu, Eytan Modiano, “Fundamental Limits on Volume-based Network DoS attacks” ACM Sigmetrics, 2020.
- Bai Liu, Eytan Modiano, “Optimal control for networks with unobservable malicious nodes,” Performance Evaluation, 2021.
- Xinzhe Fu, Eytan Modiano, “Learning-NUM: Network Utility Maximization with Unknown Utility Functions and Queueing Delay,” ACM MobiHoc 2021.
- Xinzhe Fu, Eytan Modiano, “Elastic job scheduling with unknown utility functions,” Performance Evaluation, 2021.