Stochastic network models with all components being observable and controllable have been the focus of classic network optimization theory for decades. However, in modern network systems, it is common that the network controller can only observe and operate on some nodes (i.e., overlay nodes), and the other nodes (i.e., underlay nodes) are neither observable nor controllable. Moreover, the dynamics can be non-stochastic or even adversarial. In this paper, we focus on the network utility maximization (NUM) problem for networks with overlay-underlay structures. The network dynamics, such as packet admissions, external arrivals and control actions of underlay nodes, can be stochastic, non-stochastic or even adversarial. We propose the Tracking Drift-plus-Penalty (TDP*) algorithm that only operates on the overlay nodes and does not require direct observations of the underlay nodes, and analyze the tradeoffs between the average utility and queue backlog. We show that as long as the peak queue backlog of the network is sublinear in time horizon, TDP* can solve the NUM problem, i.e., reaching the maximum utility while preserving stability.

Modern networks are complex and may include components that cannot be fully controlled or observed. Such network models can be characterized by overlay-underlay structures, where the network controller can only observe and operate on overlay nodes, and the underlay nodes are neither observable nor controllable. Classic network control algorithms may fail to work properly if they are only applied to the overlay nodes. To tackle this issue, we propose the Tracking MaxWeight (TMW*) algorithm that does not require direct observations of underlay nodes and only operates on overlay nodes. TMW* maintains virtual queues that track the dynamics of the underlay nodes and makes control decisions based on those virtual queues. We show that TMW* is throughput optimal as long as the network is stabilizable. We further extend our analysis to the setting that the estimates of the underlay state is erroneous and show that as long as the errors scale sub-linearly in time, TMW* preserves throughput optimality.

The effectiveness of many optimal network control algorithms (e.g., BackPressure) relies on the premise that all of the nodes are fully controllable. However, these algorithms may yield poor performance in a partially-controllable network where a subset of nodes are uncontrollable and use some unknown policy. Such a partially-controllable model is of increasing importance in real-world networked systems such as overlay-underlay networks. In this paper, we design optimal network control algorithms that can stabilize a partially-controllable network. We first study the scenario where uncontrollable nodes use a queue-agnostic policy, and propose a low-complexity throughput-optimal algorithm, called Tracking-MaxWeight (TMW), which enhances the original MaxWeight algorithm with an explicit learning of the policy used by uncontrollable nodes. Next, we investigate the scenario where uncontrollable nodes use a queue-dependent policy and the problem is formulated as an MDP with unknown queueing dynamics. We propose a new reinforcement learning algorithm, called Truncated Upper Confidence Reinforcement Learning (TUCRL), and prove that TUCRL achieves tunable three-way tradeoffs between throughput, delay and convergence rate.

The effectiveness of many well-known network control algorithms (e.g., MaxWeight) relies on the premise that all of the nodes are fully controllable. However, these algorithms may yield poor performance in a partially-controllable network where a subset of nodes are uncontrollable and may take arbitrary (possibly adversarial) actions. Such a partially-controllable model is of increasing importance in real-world networked systems such as overlay-underlay networks and uncooperative wireless networks. In this paper, we study two fundamental network optimization problems in a network with adversarial uncontrollable nodes. First, we investigate the network stability problem where the objective is to stabilize the network whenever possible. We develop a lower bound on the total queue length that can be achieved by any causal policy, and propose a throughput-optimal algorithm, called Tracking-MaxWeight (TMW), which enhances the original MaxWeight algorithm with an explicit learning of the behavior of uncontrollable nodes. Second, we study the network utility maximization problem where the objective is to maximize cumulative utility subject to stability constraints. We provide a lower bound on the utility-delay tradeoff, and develop the Tracking Drift-plus-Penalty (TDP) algorithm that achieves tunable utility-delay tradeoffs.

In spectrum-sharing networks, primary users have the right to preempt secondary users, which can significantly degrade the performance of underlying secondary users. In this paper, we use backup channels to provide reliability guarantees for secondary users. In particular, we study the optimal white channel assignment that minimizes the amount of recovery capacity (i.e., bandwidth of backup channels) needed to meet a given reliability guarantee, where both deterministic and probabilistic requirements are considered. This problem is shown to be coupled by two NP-hard objectives. We characterize the structure of the optimal assignment and develop bi-criteria approximation algorithms. Moreover, we investigate the scaling of the recovery capacity as the network size becomes large. It is shown that the recovery capacity is negligible as compared to the total traffic demands in a large-scale network.

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).

A coflow is a collection of parallel flows belonging to the same job. It has the all-or-nothing property: a coflow is not complete until the completion of all its constituent flows. In this paper, we focus on optimizing coflow-level delay, i.e., the time to complete all the flows in a coflow, in the context of an N × N input-queued switch. In particular, we develop a throughput-optimal scheduling policy that achieves the best scaling of coflow-level delay as N → ∞. We first derive lower bounds on the coflow-level delay that can be achieved by any scheduling policy. It is observed that these lower bounds critically depend on the variability of flow sizes. Then we analyze the coflow-level performance of some existing coflow-agnostic scheduling policies and show that none of them achieves provably optimal performance with respect to coflow-level delay. Finally, we propose the Coflow-Aware Batching (CAB) policy which achieves the optimal scaling of coflow-level delay under some mild assumptions.

Most load balancing techniques implemented in current data centers tend to rely on a mapping from packets to server IP addresses through a hash value calculated from the flow five-tuple. The hash calculation allows extremely fast packet forwarding and provides flow `stickiness', meaning that all packets belonging to the same flow get dispatched to the same server. Unfortunately, such static hashing may not yield an optimal degree of load balancing, e.g. due to variations in server processing speeds or traffic patterns. On the other hand, dynamic schemes, such as the Join-the-Shortest-Queue (JSQ) scheme, provide a natural way to mitigate load imbalances, but at the expense of stickiness violation.In the present paper we examine the fundamental trade-off between stickiness violation and packet-level latency performance in large-scale data centers. We establish that stringent flow stickiness carries a significant performance penalty in terms of packet-level delay. Moreover, relaxing the stickiness requirement by a minuscule amount is highly effective in clipping the tail of the latency distribution. We further propose a bin-based load balancing scheme that achieves a good balance among scalability, stickiness violation and packet-level delay performance. Extensive simulation experiments corroborate the analytical results and validate the effectiveness of the bin-based load balancing scheme.

Time-varying graphs are a useful model for networks with dynamic connectivity such as vehicular networks, yet, despite their great modeling power, many important features of time-varying graphs are still poorly understood. In this paper, we study the survivability properties of time-varying networks against unpredictable interruptions. We first show that the traditional definition of survivability is not effective in time-varying networks, and propose a new survivability framework. To evaluate the survivability of time-varying networks under the new framework, we propose two metrics that are analogous to MaxFlow and MinCut in static networks. We show that some fundamental survivability-related results such as Menger's Theorem only conditionally hold in time-varying networks. Then, we analyze the complexity of computing the proposed metrics and develop approximation algorithms. Finally, we conduct trace-driven simulations to demonstrate the application of our survivability framework in the robust design of a real-world bus communication network.

Time-varying graphs are a useful model for networks with dynamic connectivity such as vehicular networks, yet, despite their great modeling power, many important features of time-varying graphs are still poorly understood. In this paper, we study the survivability properties of time-varying networks against unpredictable interruptions. We first show that the traditional definition of survivability is not effective in time-varying networks, and propose a new survivability framework. To evaluate the survivability of time-varying networks under the new framework, we propose two metrics that are analogous to MaxFlow and MinCut in static networks. We show that some fundamental survivability-related results such as Menger's Theorem only conditionally hold in time-varying networks. Then we analyze the complexity of computing the proposed metrics and develop approximation algorithms. Finally, we conduct trace-driven simulations to demonstrate the application of our survivability framework in the robust design of a real-world bus communication network.

In spectrum-sharing networks, primary users have the right to preempt secondary users, which significantly degrades the performance of underlying secondary users. In this paper, we use backup channels to provide reliability guarantees for secondary users. In particular, we study the optimal white channel assignment that minimizes the amount of recovery capacity (i.e., bandwidth of backup channels) needed to meet a given reliability guarantee. This problem is shown to be coupled by two NP-hard objectives. We characterize the structure of the optimal assignment and develop bi-criteria approximation algorithms. Moreover, we investigate the scaling of the recovery capacity as the network size becomes large. It is shown that the recovery capacity is negligible as compared to the total traffic demands in a large-scale network.

In cognitive radio networks (CRNs), secondary users (SUs) can flexibly access primary users' (PUs') idle spectrum bands, but such spectrum opportunities are dynamic due to PUs' uncertain activity patterns. In a multihop CRN consisting of SUs as relays, such spectrum dynamics will further cause the invalidity of predetermined routes. In this paper, we investigate spectrum-mobility-incurred route-switching problems in both spatial and frequency domains for CRNs, where spatial switching determines which relays and links should be reselected and frequency switching decides which channels ought to be reassigned to the spatial routes. The proposed route-switching scheme not only avoids conflicts with PUs but also mitigates spectrum congestion. Meanwhile, tradeoffs between routing costs and channel switching costs are achieved. We further formulate the route-switching problem as the Route-Switching Game, which is shown to be a potential game and has a pure Nash equilibrium (NE). Accordingly, efficient algorithms for finding the NE and the$\epsilon $–NE are proposed. Then, we extend the proposed game to the incomplete-information scenario and provide a method to compute the Bayesian NE. Finally, we prove that the price of anarchy of the proposed game has a deterministic upper bound.

In Cognitive Radio Networks (CRNs), Secondary Users (SUs) are provided with the flexibility of accessing Primary Users' (PUs') idle spectrum bands but the availability of spectra is dynamic due to PUs' uncertain activities of channel reclamation. In the multi-hop CRNs consisting of SUs as relays, such spectrum mobility will cause the invalidity of pre-determined routes of data flows since some of the channels pre-assigned to the routes become unavailable. In this paper, we investigate the spectrum-mobility-incurred route-switching problem in both spatial and frequency domains for CRNs, where the spatial switching determines which relays and links should be re-selected and the frequency switching decides which channels ought to be re-assigned to the spatial routes. We further formulate the route-switching problem as the Route-Switching Game which is shown to be a potential game and has a pure Nash Equilibrium (NE). Accordingly, an efficient algorithm for finding the NE is proposed. The proposed route-switching scheme not only avoids conflicts with PUs but also mitigates spectrum congestion. Meanwhile, tradeoffs between routing costs and channel switching costs are achieved.

In cognitive radio networks (CRNs), Secondary Users (SUs) are provided opportunities to access Primary Users' (PUs') idle spectrums but the availability of spectrums is dynamic due to PUs' uncertain activities of channel reclamation. In this paper, we investigate such spectrum mobility by proposing Singleton Bayesian Spectrum Mobility Games based on the Singleton Congestion Games, where each SU distributively reselects one switch-to (and available) channel which can bring it the maximum SINR when the spectrum environment varies, accounting for other SUs' switching strategies at the same time. Unlike previous game-theoretic schemes for handling the spectrum mobility that assume SUs' complete knowledge of the CRN, we present our scheme in two information scenarios. We first demonstrate the proposed game in the complete-information scenario and prove the existence of pure Nash equilibriums. Then the game is extended to the incomplete-information scenario with the existence of Bayesian equilibriums. Besides, the other major contribution of this paper is that we provide a polynomial-time algorithm for finding the socially optimal equilibrium among all possible equilibriums, which can optimize the (expected) overall performance of the entire CRN in terms of SUs' average SINR.

In Cognitive Radio (CR) networks, Primary Users (PUs) can share their idle spectrums with Secondary Users (SUs) under certain mechanisms. Centralized schemes and market-driven mechanisms are two major considerations in solving the spectrum sharing problems in the multiple-PU scenario. Centralized schemes can achieve the social optimal spectrum allocation among multiple PUs and multiple SUs but require a central control entity, which is impractical in the CR environment due to its distributed nature. Market-driven mechanisms can be implemented in a distributed manner but are hard to obtain the social optimal spectrum utilization in the multiple-PU scenario. Furthermore, many market-driven mechanisms are not economic-robust (Incentive Compatible, Individual Rational, etc). In this paper, we propose a distributed-centralized spectrum sharing scheme based on contracts for the multiple-PU scenario, which introduces a Random Leader who is elected randomly among SUs or PUs. The distributed aspect of our scheme lies in that our scheme requires no central control entities, which can be independently implemented within a distributed spectrum market. The centralized aspect is that the leader draws up and assigns the social optimal spectrum allocation contracts as well as the payment contracts for all PUs and SUs in a centralized manner. The former contracts maximize the spectrum utilization of the whole network, and the latter contracts help attain the economic robustness of our scheme. Under the leadership of the Random Leader, those non-cooperative SUs and PUs behave in a cooperative manner, which mitigates the complexity and time overhead needed for information exchange.

In Cognitive Radio Networks (CRNs), Primary Users (PUs) can share their idle spectra with Secondary Users (SUs) under certain mechanisms. In this paper, we propose a distributed-centralized and incentive-aware spectrum sharing scheme for the multiple-PU scenario, which introduces a Random Leader who is elected randomly from SUs or PUs. The distributed aspect of our scheme lies in that it requires no central control entities, which can be independently implemented within a distributed spectrum market. The centralized aspect is that the leader draws up and assigns the socially optimal contracts for all PUs and SUs in a centralized manner, which maximizes the throughput of the whole network and attains the economic robustness (including Incentive Compatibility and Individual Rationality). Analysis shows that the proposed scheme takes in the advantages of both centralized and distributed schemes but overcomes their weaknesses. We use the proposed scheme to study two sharing scenarios: the short-term and the long-term spectrum sharing. The Short-Term Sharing (STS) focuses on distributing PUs' idle spectra within one time slot while the Long-Term Sharing (LTS) considers multiple slots, where the spectrum mobility must be investigated. As an integrated design of both STS and LTS, our scheme not only fulfils SUs' heterogeneous spectrum requirements but also obtains the socially optimal throughput while accounting for both SUs' and PUs' incentives.