Mobile data traffic has witnessed tremendous growth over the last few years. A key application driving that growth is Over-The-Top (OTT) applications. Yet very little is known about the OTT traffic characteristics. In this paper, we focus on delay-sensitive real-time Internet video call applications such as Skype. We propose a novel intra-flow prioritization packet dropping (IPPD) scheme for efficient congestion mitigation of OTT Internet applications in Mobile Broadband Networks, e.g. 3G, LTE, LTE-A, etc. Simulation results show a great increase of video call capacity in a LTE network. The necessary protocol enhancements for LTE networks are also discussed.

A fundamental theoretical problem in opportunistic spectrum access is the following: a single secondary user must choose a channel to sense and access at each time, with the availability of each channel (due to primary user behavior) described by a Markov Chain. The problem of maximizing the expected channel usage can be formulated as a restless multi-armed bandit. We present in this paper an online learning algorithm with the best known results to date for this problem in the case when channels are homogeneous and the channel statistics are unknown a priori. Specifically, we show that this policy, that we refer to as CSE, achieves a regret (the gap between the rewards accumulated by a model-aware Genie and the policy) that is bounded in finite time by a function that scales as O(log t). By explicitly learning the underlying statistics over time, this novel policy outperforms a previously proposed scheme shown to provide near-logarithmic regret.

The problem of opportunistic spectrum access in cognitive radio networks has been recently formulated as a non-Bayesian restless multi-armed bandit problem. In this problem, there are N arms (corresponding to channels) and one player (corresponding to a secondary user). The state of each arm evolves as a finite-state Markov chain with unknown parameters. At each time slot, the player can select K <; N arms to play and receives state-dependent rewards (corresponding to the throughput obtained given the activity of primary users). The objective is to maximize the expected total rewards (i.e., total throughput) obtained over multiple plays. The performance of an algorithm for such a multi-armed bandit problem is measured in terms of regret, defined as the difference in expected reward compared to a model-aware genie who always plays the best K arms. In this paper, we propose a new continuous exploration and exploitation (CEE) algorithm for this problem. When no information is available about the dynamics of the arms, CEE is the first algorithm to guarantee near-logarithmic regret uniformly over time. When some bounds corresponding to the stationary state distributions and the state-dependent rewards are known, we show that CEE can be easily modified to achieve logarithmic regret over time. In contrast, prior algorithms require additional information concerning bounds on the second eigenvalues of the transition matrices in order to guarantee logarithmic regret. Finally, we show through numerical simulations that CEE is more efficient than prior algorithms.

Combinatorial network optimization algorithms that compute optimal structures taking into account edge weights form the foundation for many network protocols. Examples include shortest path routing, minimal spanning tree computation, maximum weighted matching on bipartite graphs, etc. We present CLRMR, the first online learning algorithm that efficiently solves the stochastic version of these problems where the underlying edge weights vary as independent Markov chains with unknown dynamics. The performance of an online learning algorithm is characterized in terms of regret, defined as the cumulative difference in rewards between a suitably-defined genie, and that obtained by the given algorithm. We prove that, compared to a genie that knows the Markov transition matrices and uses the single-best structure at all times, CLRMR yields regret that is polynomial in the number of edges and nearly-logarithmic in time.

We formulate the following combinatorial multi-armed bandit (MAB) problem: There areNrandom variables with unknown mean that are each instantiated in an i.i.d. fashion over time. At each time multiple random variables can be selected, subject to an arbitrary constraint on weights associated with the selected variables. All of the selected individual random variables are observed at that time, and a linearly weighted combination of these selected variables is yielded as the reward. The goal is to find a policy that minimizes regret, defined as the difference between the reward obtained by a genie that knows the mean of each random variable, and that obtained by the given policy. This formulation is broadly applicable and useful for stochastic online versions of many interesting tasks in networks that can be formulated as tractable combinatorial optimization problems with linear objective functions, such as maximum weighted matching, shortest path, and minimum spanning tree computations. Prior work on multi-armed bandits with multiple plays cannot be applied to this formulation because of the general nature of the constraint. On the other hand, the mapping of all feasible combinations to arms allows for the use of prior work on MAB with single-play, but results in regret, storage, and computation growing exponentially in the number of unknown variables. We present new efficient policies for this problem that are shown to achieve regret that grows logarithmically with time, and polynomially in the number of unknown variables. Furthermore, these policies only require storage that grows linearly in the number of unknown parameters. For problems where the underlying deterministic problem is tractable, these policies further require only polynomial computation. For computationally intractable problems, we also present results on a different notion of regret that is suitable when a polynomial-time approximation algorithm is used.

The fundamental problem of multiple secondary users contending for opportunistic spectrum access over multiple channels in cognitive radio networks has been formulated recently as a decentralized multi-armed bandit (D-MAB) problem. In a D-MAB problem there are M users and N arms (channels) that each offer i.i.d. stochastic rewards with unknown means so long as they are accessed without collision. The goal is to design a decentralized online learning policy that incurs minimal regret, defined as the difference between the total expected rewards accumulated by a model-aware genie, and that obtained by all users applying the policy. We make two contributions in this paper. First, we consider the setting where the users have a prioritized ranking, such that it is desired for the K-th-ranked user to learn to access the arm offering the K-th highest mean reward. For this problem, we present the first distributed policy that yields regret that is uniformly logarithmic over time without requiring any prior assumption about the mean rewards. Second, we consider the case when a fair access policy is required, i.e., it is desired for all users to experience the same mean reward. For this problem, we present a distributed policy that yields order-optimal regret scaling with respect to the number of users and arms, better than previously proposed policies in the literature. Both of our distributed policies make use of an innovative modification of the well known UCB1 policy for the classic multi-armed bandit problem that allows a single user to learn how to play the arm that yields the K-th largest mean reward.

We consider a combinatorial generalization of the classical multi-armed bandit problem that is defined as follows. There is a given bipartite graph of M users and N≥M resources. For each user-resource pair (i,j), there is an associated state that evolves as an aperiodic irreducible finite-state Markov chain with unknown parameters, with transitions occurring each time the particular user i is allocated resource j. The user i receives a reward that depends on the corresponding state each time it is allocated the resource j. The system objective is to learn the best matching of users to resources so that the long-term sum of the rewards received by all users is maximized. This corresponds to minimizing regret, defined here as the gap between the expected total reward that can be obtained by the best-possible static matching and the expected total reward that can be achieved by a given algorithm. We present a polynomial-storage and polynomial-complexity-per-step matching-learning algorithm for this problem. We show that this algorithm can achieve a regret that is uniformly arbitrarily close to logarithmic in time and polynomial in the number of users and resources. This formulation is broadly applicable to scheduling and switching problems in communication networks including cognitive radio networks and significantly extends prior results in the area.

In the classic Bayesian restless multi-armed bandit (RMAB) problem, there are N arms, with rewards on all arms evolving at each time as Markov chains with known parameters. A player seeks to activate K ≥ 1 arms at each time in order to maximize the expected total reward obtained over multiple plays. RMAB is a challenging problem that is known to be PSPACE-hard in general. We consider in this work the even harder non-Bayesian RMAB, in which the parameters of the Markov chain are assumed to be unknown a priori. We develop an original approach to this problem that is applicable when the corresponding Bayesian problem has the structure that, de pending on the known parameter values, the optimal solution is one of a prescribed finite set of policies. In such settings, we propose to learn the optimal policy for the non-Bayesian RMAB by employing a suitable meta-policy which treats each policy from this finite set as an arm in a different non-Bayesian multi-armed bandit problem for which a single-arm selection policy is optimal. We demonstrate this approach by developing a novel sensing policy for opportunistic spectrum access over unknown dynamic channels. We prove that our policy achieves near-logarithmic regret (the difference in expected reward compared to a model-aware genie), which leads to the same average reward that can be achieved by the optimal policy under a known model. This is the first such result in the literature for a non Bayesian RMAB.

We study a novel game theoretic incentive mechanism design problem for network congestion control in the context of selfish users sending data through a single store-and-forward router (a.k.a. “server” in this work). The scenario is modeled as an M/M/1 queueing game with each user (a.k.a. “player”) aiming to optimize a tradeoff between throughput and delay in a selfish distributed manner. We first show that the original game has an inefficient unique Nash Equilibrium (NE). In order to improve the outcome efficiency, we propose an incentivizing packet dropping scheme that can be easily implemented at the server. We then show that if the packet dropping scheme is a function of the sum of arrival rates, we have a modified M/M/1 queueing game that is an ordinal potential game with a unique NE. In particular, for a linear packet dropping scheme, which is similar to the Random Early Detection (RED) algorithm used with TCP, we show that there exists a unique Nash Equilibrium. For this scheme, the social welfare (expressed either as the summation of utilities of all players or log summation of utilities of all players) at the equilibrium point can be arbitrarily close to the social welfare at the global optimal point. Finally, we show that the simple best response dynamic converges to this unique efficient Nash Equilibrium.

We consider a number of related problem formulations pertaining to adaptive subcarrier allocation in multiuser Orthogonal Frequency-Division Multiplexing (OFDM) systems, and prove that they are NP-hard. Thus there exist no known algorithms that can provide optimal solutions for all instances of these problems in polynomial time. We further prove that these problems are hard to approximate in polynomial time. Finally, we discuss qualitatively the settings under which worst case performance is likely to be observed.

An emerging problem facing future high performance multi-core processors is transient faults caused by radiation, noise and other factors. These faults will likely make future multi-core processors less reliable as chip features shrink and the number of cores increase. To address this problem, we propose a new and practical systems approach of managing and allocating reliability according to software process requirements. The asymmetric multi-core architecture is based on cores with differing reliabilities. Critical and non-critical software components are identified and matched with the higher reliability cores. We show that by using asymmetrically reliable cores the overall system failure rate can be reduced by several times when critical processes can be isolated and executed by higher reliability cores, while offering the same or better overall performance, power utilization and chip area as symmetric cores.

Future network systems and embedded infrastructure devices in ubiquitous environments will need to consume low power and process large amounts of network packet traffic. In order to meet necessary high processing efficiency requirements, future processors will have many heterogeneous cores with reduced reliability due to low voltage, small transistor sizes, semiconductor wearout, and environmental factors such as noise and interference. It will be necessary for multi-core network infrastructure software to mitigate transient hardware faults to maintain acceptable system reliability. Applications such as packet processing can benefit from the reliability versus performance tradeoff. We propose a model based on stochastic reward nets to evaluate the performance vs. reliability tradeoff of unreliable embedded multi-core network processors, and apply this model to a multi-core packet processing application.

An energy model for wireless sensor networks based on the cooperative MIMO (multiple-in-multiple-out) technique is proposed, taking into consideration of both the transmission and data aggregation energy. Based on the model, two cooperative wireless sensor network schemes, namely, MIMO approach and SISO (single-in-single-out) approach are compared. It is shown that the overall energy consumption in the systems is related to not only the transmission range but also the correlation among the raw sensor data, and can be solved as a nonlinear programming problem. Furthermore, a critical value above which MIMO approach outperforms SISO approach is analyzed. Simulation results show that jointly considering both data aggregation and cooperative MIMO techniques further reduce the total energy consumption and thus prolong the network lifetime.