We study the optimal control of multiple video streams over a wireless downlink from a base-transceiver-station (BTS)/access point to N end-devices (EDs). The BTS sends video packets to each ED under a joint transmission energy constraint, the EDs choose when to play out the received packets, and the collective goal is to provide a high Quality-of-Experience (QoE) to the clients/end-users. All EDs send feedback about their states and actions to the BTS which reaches it after a fixed deterministic delay. We analyze this team problem with delayed feedback as a cooperative Multi-Agent Constrained Partially Observable Markov Decision Process (MA-C-POMDP).First, using a recently established strong duality result for MAC-POMDPs, the original problem is decomposed into N independent unconstrained transmitter-receiver (two-agent) problems— all sharing a Lagrange multiplier (that also needs to be optimized for optimal control). Thereafter, the common information (CI) approach and the formalism of approximate information states (AISs) are used to guide the design of a neural-network based architecture for learning-based multi-agent control in a single unconstrained transmitter-receiver problem. Finally, simulations on a single transmitter-receiver pair with a stylized QoE model are performed to highlight the advantage of delay-aware two-agent coordination over the transmitter choosing both transmission and play-out actions (perceiving the delayed state of the receiver as its current state).

Recent studies suggested that the BitTorrent’s rarest-first (RF) protocol, owing to its work-conserving nature, can become unstable in the presence of non-persistent users. Consequently, for any provably stable protocol, many peers, at some point, have to be forced to hold off their file-download activity. In this work, we propose a tunable piece-selection policy that minimizes this (undesirable) requisite by combining the (work-conserving but not stabilizing) RF protocol with only an appropriate share of the (stabilizing but not work-conserving) mode-suppression (MS) protocol. We refer to this policy as “Rarest-First with Probabilistic Mode-Suppression” or simply RFwPMS. We study RFwPMS using a stochastic abstraction of the BitTorrent network that is general enough to capture a multi-swarm setting of non-persistent users—each swarm having its own altruistic preferences that may or may not overlap with those of other swarms. Using Lyapunov drift analysis, we show that for all kinds of inter-swarm behaviors and all arrival-rate configurations, RFwPMS is stable. Then, using the Kingman’s moment bound technique, we further show that the steady-state expected sojourn time of RFwPMS is independent of the arrival-rate in the single-swarm case (under a mild additional assumption). Finally, our simulation-based performance evaluation confirms our theoretical findings, and shows that the steady-state expected sojourn time is linear in the file-size (compared to our loose estimate of a polynomial with degree 6). Overall, an improved performance is observed in comparison to previously proposed stabilizing schemes like MS.

Models of many real-life applications, such as queueing models of communication networks or computing systems, have a countably infinite state-space. Algorithmic and learning procedures that have been developed to produce optimal policies mainly focus on finite state settings, and do not directly apply to these models. To overcome this lacuna, in this work we study the problem of optimal control of a family of discrete-time countable state-space Markov Decision Processes (MDPs) governed by an unknown parameter $\theta\in\Theta$, and defined on a countably-infinite state-space $\mathcal X=\mathbb{Z}_+^d$, with finite action space $\mathcal A$, and an unbounded cost function. We take a Bayesian perspective with the random unknown parameter $\boldsymbol{\theta}^*$ generated via a given fixed prior distribution on $\Theta$. To optimally control the unknown MDP, we propose an algorithm based on Thompson sampling with dynamically-sized episodes: at the beginning of each episode, the posterior distribution formed via Bayes' rule is used to produce a parameter estimate, which then decides the policy applied during the episode. To ensure the stability of the Markov chain obtained by following the policy chosen for each parameter, we impose ergodicity assumptions. From this condition and using the solution of the average cost Bellman equation, we establish an $\tilde O(dh^d\sqrt{|\mathcal A|T})$ upper bound on the Bayesian regret of our algorithm, where $T$ is the time-horizon. Finally, to elucidate the applicability of our algorithm, we consider two different queueing models with unknown dynamics, and show that our algorithm can be applied to develop approximately optimal control algorithms.

Due to information asymmetry, finding optimal policies for Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs) is hard with the complexity growing doubly exponentially in the horizon length. The challenge increases greatly in the multi-agent reinforcement learning (MARL) setting where the transition probabilities, observation kernel, and reward function are unknown. Here, we develop a general compression framework with approximate common and private state representations, based on which decentralized policies can be constructed. We derive the optimality gap of executing dynamic programming (DP) with the approximate states in terms of the approximation error parameters and the remaining time steps. When the compression is exact (no error), the resulting DP is equivalent to the one in existing work. Our general framework generalizes a number of methods proposed in the literature. The results shed light on designing practically useful deep-MARL network structures under the "centralized learning distributed execution" scheme.

Multi-agent reinforcement learning (MARL) problems are challenging due to information asymmetry. To overcome this challenge, existing methods often require high level of coordination or communication between the agents. We consider two-agent multi-armed bandits (MABs) and Markov decision processes (MDPs) with a hierarchical information structure arising in applications, which we exploit to propose simpler and more efficient algorithms that require no coordination or communication. In the structure, in each step the “leader" chooses her action first, and then the “follower" decides his action after observing the leader’s action. The two agents observe the same reward (and the same state transition in the MDP setting) that depends on their joint action. For the bandit setting, we propose a hierarchical bandit algorithm that achieves a near-optimal gap-independent regret of $\widetilde{\mathcal{O}}(\sqrt{ABT})$ and a near-optimal gap-dependent regret of $\mathcal{O}(\log(T))$, where $A$ and $B$ are the numbers of actions of the leader and the follower, respectively, and $T$ is the number of steps. We further extend to the case of multiple followers and the case with a deep hierarchy, where we both obtain near-optimal regret bounds. For the MDP setting, we obtain $\widetilde{\mathcal{O}}(\sqrt{H^7S^2ABT})$ regret, where $H$ is the number of steps per episode, $S$ is the number of states, $T$ is the number of episodes. This matches the existing lower bound in terms of $A, B$, and $T$.

Recent studies have suggested that the BitTorrent's rarest-first protocol, owing to its work-conserving nature, can become unstable in the presence of non-persistent users. Consequently, in any stable protocol, many peers are at some point endogenously forced to hold off their file-download activity. In this work, we propose a tunable piece-selection policy that minimizes this (undesirable) requisite by combining the (work-conserving) rarest-first protocol with only an appropriate share of the (non-work conserving) mode-suppression protocol. We refer to this policy as "Rarest-First with Probabilistic Mode-Suppression" or simply RFwPMS. We study RFwPMS under a stochastic model of the BitTorrent network that is general enough to capture multiple swarms of non-persistent users - each swarm having its own altruistic preferences that may or may not overlap with those of other swarms. Using a Lyapunov drift analysis, we show that RFwPMS is provably stable for all kinds of inter-swarm behaviors, and that the use of rarest-first instead of random-selection is indeed more justified. Our numerical results suggest that RFwPMS is scalable in the general multi-swarm setting and offers better performance than the existing stabilizing schemes like mode-suppression.

Small-cells in licensed spectrum and unlicensed access via Wi-Fi are two commonly used options to reduce the demand for conventional macro-cellular networks and to provide expanded wireless services to low mobility users. The mix of these technologies depends on both the decisions made by wireless service providers (SPs) that seek to maximize revenue, and the allocation of licensed and unlicensed spectrum by regulators. In this paper, we study these interactions and consider heterogeneous cellular networks together with unlicensed access. Both a single monopoly SP and multiple competing SPs are investigated. The SPs split any available licensed spectrum into two separate bands for macro- and small-cells, which are then used to serve two types of users: mobile and fixed. Mobile users must be served by macro-cells only, whereas fixed users can be served by either macro- or small-cells, or alternatively by unlicensed access service. While the providers charge a (different) price per unit rate for licensed access services (macro- or small-cell), unlicensed access is free. We formulate a sequential game in which the users choose a service that yields the highest payoff, and the providers allocate bandwidth across macro-/small-cells. In general, the competition from unlicensed access results in inefficient (albeit unique) market equilibria, and in many cases all or some SPs allocate no resources to small-cell deployment. We conclude by showing how our framework can also be used to optimize the fraction of unlicensed spectrum when new bandwidth becomes available.

Small-cells deployed in licensed spectrum can expand wireless service to low mobility users, which potentially reduces the demand for macro-cellular networks with wide-area coverage. Introducing such heterogeneity also makes network resource allocation more complicated. To understand these challenges and tradeoffs we present a two-tier heterogeneous wireless network model with two types of users: mobile users that can only connect to macro-cells; and fixed users that can associate with either macro-cells or small-cells. We study pricing strategies and bandwidth allocation across macro- and small-cells, assuming both monopoly and competitive Service Providers (SPs). For a monopoly SP, we characterize the revenue-maximizing prices and bandwidth allocations. We then consider a competitive scenario, and we show the existence of a unique Nash equilibrium. The possible Nash equilibria for different system parameters are sorted into four categories corresponding to whether or not different SPs assign bandwidth to the macro- and/or small-cells. We also study the allocations that maximize social welfare. For the competitive scenario, we characterize the conditions under which the optimal social welfare is obtained in equilibria as the number of SPs tends to infinity. Case study examples and numerical results illustrate the corresponding pricing and bandwidth allocations.

We consider a general small-scale market for agent-to-agent resource sharing, in which each agent could either be a server (seller) or a client (buyer) in each time period. In every time period, a server has a certain amount of resources that any client could consume, and randomly gets matched with a client. Our target is to maximize the resource utilization in such an agent-to-agent market, where the agents are strategic. During each transaction, the server gets money and the client gets resources. Hence, trade ratio maximization implies efficiency maximization of our system. We model the proposed market system through a Mean Field Game approach and prove the existence of the Mean Field Equilibrium, which can achieve an almost 100% trade ratio. Finally, we carry out a simulation study motivated by an agent-to-agent computing market, and a case study on a proposed photovoltaic market, and show the designed market benefits both individuals and the system as a whole.

We add to a line of work considering the impact of observation imperfections in models of Bayesian observational learning. In particular, we study a discrete-time model in which in each time-slot, an agent may randomly arrive. Agents who arrive have the opportunity to buy a given item. If an agent chooses to buy, this action is recorded for subsequent agents. However, the decisions of agents that choose not to buy are not recorded. Hence, if no one buys in a given slot, agents are unaware if this was due to no agent arriving or an agent choosing not to buy. We study the impact of this uncertainty on the emergence of information cascades. Using a Markov chain based analysis, we show that the probability of incorrect cascades and the expected time until a cascade happens are not monotonic in the arrival probability of a user. We find that adding a small uncertainty in the arrival information from the perfect information setting will make a buy cascade happen with higher probability than a not-buy cascade. However, if the agents' private signals are weak, then a not-buy cascade is more likely to occur for most arrival rates, resulting in wrong cascades dominating when the item is good and vice-versa when the item is bad.

Typical analysis of content caching algorithms using the metric of steady state hit probability under a stationary request process does not account for performance loss under a variable request arrival process. In this paper, we instead conceptualize caching algorithms as complexity-limited online distribution learning algorithms and use this vantage point to study their adaptability from two perspectives: 1) the accuracy of learning a fixed popularity distribution and 2) the speed of learning items' popularity. In order to attain this goal, we compute the distance between the stationary distributions of several popular algorithms with that of a genie-aided algorithm that has the knowledge of the true popularity ranking, which we use as a measure of learning accuracy. We then characterize the mixing time of each algorithm, i.e., the time needed to attain the stationary distribution, which we use as a measure of learning efficiency. We merge both the above-mentioned measures to obtain the “learning error” representing both how quickly and how accurately an algorithm learns the optimal caching distribution and use this to determine the trade-off between these two objectives of many popular caching algorithms. Informed by the results of our analysis, we propose a novel hybrid algorithm, adaptive-least recently used, that learns both faster and better the changes in the popularity. We show numerically that it also outperforms all other candidate algorithms when confronted with either a dynamically changing synthetic request process or using real world traces.

We consider the problem of streaming live content to a cluster of co-located wireless devices that have both an expensive unicast base-station-to-device (B2D) interface, as well as an inexpensive broadcast device-to-device (D2D) interface, which can be used simultaneously. Our setting is a streaming system that uses a block-by-block random linear coding approach to achieve a target percentage of on-time deliveries with minimal B2D usage. Our goal is to design an incentive framework that would promote such cooperation across devices, while ensuring good quality of service. Based on the ideas drawn from truth-telling auctions, we design a mechanism that achieves this goal via appropriate transfers (monetary payments or rebates) in a setting with a large number of devices, and with peer arrivals and departures. Here, we show that a mean field game can be used to accurately approximate our system. Furthermore, the complexity of calculating the best responses under this regime is low. We implement the proposed system on an Android testbed, and illustrate its efficient performance using real world experiments.

Small cells deployed in licensed spectrum and unlicensed access via WiFi provide different ways of expanding wireless services to low mobility users. That reduces the demand for conventional macro-cellular networks, which are better suited for wide-area mobile coverage. The mix of these technologies seen in practice depends in part on the decisions made by wireless service providers that seek to maximize revenue, and allocations of licensed and unlicensed spectrum by regulators. To understand these interactions we present a model in which a service provider allocates available licensed spectrum across two separate bands, one for macro- and one for small-cells, in order to serve two types of users: mobile and fixed. We assume a service model in which the providers can charge a (different) price per unit rate for each type of service (macro- or small-cell); unlicensed access is free. With this setup we study how the addition of unlicensed spectrum affects prices and the optimal allocation of bandwidth across macro-/small-cells. We also characterize the optimal fraction of unlicensed spectrum when new bandwidth becomes available.

Social learning encompasses situations in which agents attempt to learn from observing the actions of other agents. It is well known that in some cases this can lead to information cascades in which agents blindly follow the actions of others, even though this may not be optimal. Having agents provide reviews in addition to their actions provides one possible way to avoid “bad cascades.” In this paper, we study one such model where agents sequentially decide whether or not to purchase a product, whose true value is either good or bad. If they purchase the item, agents also leave a review, which may be imperfect. Conditioning on the underlying state of the item, we study the impact of such reviews on the asymptotic properties of cascades. For a good underlying state, using Markov analysis we show that depending on the review quality, reviews may in fact increase the probability of a wrong cascade. On the other hand, for a bad underlying state, we use martingale analysis to bound the tail-probability of the time until a correct cascade happens.

The threshold model is widely used to study the propagation of opinions and technologies in social networks. In this model individuals adopt the new behavior based on how many neighbors have already chosen it. We study cascades under the threshold model on sparse random graphs with community structure to see whether the existence of communities affects the number of individuals who finally adopt the new behavior. Specifically, we consider the permanent adoption model where nodes that have adopted the new behavior cannot change their state. When seeding a small number of agents with the new behavior, the community structure has little effect on the final proportion of people that adopt it, i.e., the contagion threshold is the same as if there were just one community. On the other hand, seeding a fraction of population with the new behavior has a significant impact on the cascade with the optimal seeding strategy depending on how strongly the communities are connected. In particular, when the communities are strongly connected, seeding in one community outperforms the symmetric seeding strategy that seeds equally in all communities.

We model an Internet marketplace using a set of servers that choose prices for performing jobs. Each server has a queue of unfinished jobs, and is penalized for delay by the market maker via a holding cost. A server completes jobs with a low or high "quality", and jobs truthfully report the quality with which they were completed. The best estimate of quality based on these reports is the "reputation" of the server. A server bases its pricing decision on the distribution of its competitors offered prices and reputations. An entering job is given a random sample of servers, and chooses the best one based on a linear combination of price and reputation. We seek to understand how prices would be determined in such a marketplace using the theory of Mean Field Games. We show the existence of a Mean Field Equilibrium and show how reputation plays a role in allowing servers to declare larger prices than their competitors. We illustrate our results by a numerical study of the system via simulation with parameters chosen from data gathered from existing Internet marketplaces.

We consider the problem of streaming live content to a cluster of co-located wireless devices that have both an expensive unicast base-station-to-device (B2D) interface, as well as an inexpensive broadcast device-to-device (D2D) interface, which can be used simultaneously. Our setting is a streaming system that uses a block-by-block random linear coding approach to achieve a target percentage of on-time deliveries with minimal B2D usage. Our goal is to design an incentive framework that would promote such cooperation across devices, while ensuring good quality of service. Based on ideas drawn from truth-telling auctions, we design a mechanism that achieves this goal via appropriate transfers (monetary payments or rebates) in a setting with a large number of devices, and with peer arrivals and departures. Here, we show that a Mean Field Game can be used to accurately approximate our system. Furthermore, the complexity of calculating the best responses under this regime is low. We implement the proposed system on an Android testbed, and illustrate its efficient performance using real world experiments.

No abstract available.

Informational cascades are said to occur when rational agents ignore their own private information and blindly follow the actions of other agents. Models for such cascades have been well studied for Bayesian agents, who observe perfectly the actions of other agents. In this paper, we investigate the impact of errors in these observations; the errors are modelled via a binary symmetric channel (BSC). Using a Markov chain model, we analyze the net payoff of each agent as a function of his signal quality and the crossover error probability in the channel. Our main result is that a lower error level does not always lead to a higher payoff when the number of agents is large.

This paper considers a one-dimensional model for a cellular network in which neighboring base stations may cooperatively transmit to users located between them. A distributed algorithm is given for deciding on the power allocation of each base station as well as on which users to serve either cooperatively or individually. The algorithm is proven to converge monotonically and the sum rate performance of different limit points is illustrated. Numerical results are presented that illustrate the performance of the algorithm in terms of sum rate, convergence speed and a fairness metric.

Bufferbloat is a phenomenon where excess buffers in the network cause high latency and jitter. As more and more interactive applications (e.g. voice over IP, real time video conferencing and financial transactions) run in the Internet, high latency and jitter degrade application performance. There is a pressing need to design intelligent queue management schemes that can control latency and jitter; and hence provide desirable quality of service to users. We present here a lightweight design, PIE (Proportional Integral controller Enhanced), that can effectively control the average queueing latency to a reference value. The design does not require per-packet extra processing, so it incurs very small overhead and is simple to implement in both hardware and software. In addition, the design parameters are self-tuning, and hence PIE is robust and optimized for various network scenarios. Simulation results, theoretical analysis and Linux testbed results show that PIE can ensure low latency and achieve high link utilization under various congestion situations.

In a limited form cellular providers have long shared spectrum in the form of roaming agreements. The primary motivation for this has been to extend the coverage of a wireless carrier's network into regions where it has no infrastructure. As devices and infrastructure become more agile, such sharing could be done on a much faster time-scale and have advantages even when two providers both have coverage in a given area, e.g., by enabling one provider to acquire “overflow” capacity from another provider during periods of high demand. This may provide carriers with an attractive means to better meet their rapidly increasing bandwidth demands. On the other hand, the presence of such a sharing agreement could encourage providers to underinvest in their networks, resulting in poorer performance. We adapt the newsvendor model from the operations management literature to model such a situation and to gain insight into these trade-offs. In particular, we analyze the structure of revenue-sharing contracts that incentivize both capacity sharing and increased access for end-users.

In this paper, we develop a novel inter-cell interference co-ordination scheme that takes into account the interference cost on neighboring cells. We formulate a multi-cell utility maximization problem and subsequently decouple it into single-cell optimization problems by including an interference penalty. By solving this decoupled problem, we derive policies for user selection, resource allocation, and power-control. Since the coupling between cells is indirectly taken into account by means of the user's channel gain to the neighboring cells, our simulation results show that this distributed solution has no degradation in performance while little or no inter-cell co-ordination is required. We present simulation results that show that the Interference Penalty Algorithm (IPA) provides significant improvement in sector and cell-edge throughputs.

We characterize the (nonconvex) rate region and its maximal convex subsets for carrier-sense multiple-access with collision-avoidance (CSMA/CA) wireless local-area networks (WLANs), and in particular for 802.11 WLANs. In addition to being of intrinsic interest as fundamental properties of CSMA/CA WLANs, this characterization can be exploited to allow the wealth of convex optimization approaches to be applied to CSMA/CA WLANs, especially to utility fair resource allocation problems.

In this paper, we establish that the rate region of a large class of IEEE 802.11 mesh networks is log-convex, immediately allowing standard utility fairness methods to be generalized to this class of networks. This creates a solid theoretical underpinning for fairness analysis and resource allocation in this practically important class of networks. For the special case of max-min fairness, we use this new insight to obtain an almost complete characterization of the fair rate allocation and a remarkably simple, practically implementable method for achieving max-min fairness in 802.11 mesh networks.

We analyze packet delay in CSMA-based random access schemes in networks under the protocol interference model. Using a stochastic coupling argument we identify a subset of the throughput-region where queue lengths can be bounded uniformly for all network sizes. This conclusion provides a throughput-region of interest for delay sensitive applications and suggests that delay bounds based on mixing time analyses may be loose.

In this paper, a many-sources large deviations principle (LDP) for the transient workload of a multiqueue single-server system is established where the service rates are chosen from a compact, convex, and coordinate-convex rate region and where the service discipline is the max-weight policy. Under the assumption that the arrival processes satisfy a many-sources LDP, this is accomplished by employing Garcia's extended contraction principle that is applicable to quasi-continuous mappings. For the traditional single-server queue (simplex rate-region), an LDP for the stationary workload is also established under the additional requirements that the scheduling policy be work-conserving and that the arrival processes satisfy certain mixing conditions. The LDP results can be used to calculate asymptotic buffer overflow probabilities accounting for the multiplexing gain, e.g., when the arrival process is an average of i.i.d. processes. The rate function for the stationary workload is expressed in term of the rate functions of the finite-horizon workloads when the arrival processes have i.i.d. increments.

As video traffic increases in the Internet and competes for limited bandwidth resources, it is important to design bandwidth-sharing and loss-protection schemes that account for video characteristics, beyond the traditional paradigm of fair-rate allocation among data flows. Ideally, such a scheme should handle both persistent and transient congestion as video streaming applications demand low-latency transmissions and low packet-loss ratios. This paper presents a novel scheme, layered Internet video adaptation (LIVA), in which network nodes feed back virtual congestion levels to video senders to assist both media-aware bandwidth sharing and transient-loss protection. The video senders respond to such feedback by adapting the rates of encoded scalable bitstreams based on their respective video rate-distortion (R-D) characteristics. The same feedback is employed to calculate the amount of forward error correction (FEC) protection for combating transient losses. Simulation studies show that LIVA can minimize the total distortion of all participating video streams and hence maximize their overall quality. At steady state, video streams experience no queueing delays or packet losses. In the face of transient congestion, the network-assisted adaptive FEC promptly protects video packets from losses. Our Linux-based demonstration showcases how LIVA can be implemented in a simple manner in real systems. We also present a solution for LIVA streams to coexist with TCP flows based on explicit congestion notification signaling. Finally, our theoretical analysis guarantees system stability for an arbitrary number of streams with round-trip delays below a prescribed limit.

This paper presents a novel scheme, Layered Internet Video Engineering (LIVE), in which network nodes feedback virtual congestion levels to video senders to assist both media-aware bandwidth sharing and transient loss protection. The video senders respond to such feedback by adapting the rates of encoded H.264/SVC streams based on their respective video rate-distortion (R-D) characteristics. The same feedback is employed to calculate the amount of forward error correction (FEC) protection for combating transient losses. Simulation studies show that LIVE can minimize the total distortion of all participating video streams and hence maximize their overall quality. At steady state, video streams experience no queuing delays or packet losses. In face of transient congestion, the network-assisted adaptive FEC effectively protect video packets from losses while keeping a minimum overhead. Our theoretical analysis further guarantees system stability for arbitrary number of streams with arbitrary round trip delays below a prescribed limit. Finally, we show that LIVE streams can coexist with TCP flows within the existing explicit congestion notification (ECN) framework.

We consider the problem of scheduling jobs with given start and finish times over two classes of multi-user channels, namely Multiple Access Channels and Degraded Broadcast Channels, and derive necessary and sufficient conditions for feasible scheduling of the jobs.

We study packet streaming over an erasure channel with delayed feedback. We consider the lag in playback between the sender and the receiver as the performance criterion and propose and analyze schemes to minimize the lag. We show that at lower delays in feedback, purely retransmission based schemes are better than random linear coding schemes and also analyze the tradeoff of the lag with the delay in feedback.

In this paper, the scheduling and resource allocation problem for the downlink in a code-division multiple access (CDMA)-based wireless network is considered. The problem is to select a subset of the users for transmission and for each of the users selected, to choose the modulation and coding scheme, transmission power, and number of codes used. We refer to this combination as the physical layer operating point (PLOP). Each PLOP consumes different amounts of code and power resources. The resource allocation task is to pick the ¿optimal¿ PLOP taking into account both system-wide and individual user resource constraints that can arise in a practical system. This problem is tackled as part of a utility maximization problem framed in earlier papers that includes both scheduling and resource allocation. In this setting, the problem reduces to maximizing the weighted throughput over the state-dependent downlink capacity region while taking into account the system-wide and individual user constraints. This problem is studied for the downlink of a Gaussian broadcast channel with orthogonal CDMA transmissions. This results in a tractable convex optimization problem. A dual formulation is used to obtain several key structural properties. By exploiting this structure, algorithms are developed to find the optimal solution with geometric convergence.

We present a network-assisted scheme for media-aware bandwidth sharing among multiple video streaming sessions. Departing from the conventional paradigm of fair-rate allocation among data traffic flows, our scheme allocates the bottleneck bandwidth among the video streams according to their rate-distortion (R-D) characteristics, with the objective of minimizing the total video distortion of all streams. This demonstration shows that our scheme achieves the optimal rate allocation with fast convergence, efficient bottleneck utilization, and balanced video qualities among the competing streams.

All opportunistic scheduling algorithms solve simpler optimization problems at each scheduling instance in order to achieve good long-term performance. The analysis of these algorithms assumes that the simpler optimization problems are solved exactly. However, in contrast, real-life implementations only approximately solve these problems but still yield close to optimal performance. We formalize this observation by explicitly bounding the longterm performance in terms of the error in the approximation made at every stage.

Orthogonal frequency division multiplexing (OFDM) with dynamic scheduling and resource allocation is a key component of most emerging broadband wireless access networks such as WiMAX and LTE (long term evolution) for 3GPP. However, scheduling and resource allocation in an OFDM system is complicated, especially in the uplink due to two reasons: (i) the discrete nature of subchannel assignments, and (ii) the heterogeneity of the users' subchannel conditions, individual resource constraints and application requirements. We approach this problem using a gradient-based scheduling framework. Physical layer resources (bandwidth and power) are allocated to maximize the projection onto the gradient of a total system utility function which models application-layer Quality of Service (QoS). This is formulated as a convex optimization problem and solved using a dual decomposition approach. This optimal solution has prohibitively high computational complexity but reveals guiding principles that we use to generate lower complexity sub-optimal algorithms. We analyze the complexity and compare the performance of these algorithms via extensive simulations.

We consider scheduling and resource allocation for the downlink of a cellular OFDM system, with various practical considerations including integer tone allocations, different sub-channelization schemes, maximum SNR constraint per tone, and "self-noise" due to channel estimation errors and phase noise. During each time-slot a subset of users must be scheduled, and the available tones and transmission power must be allocated among them. Employing a gradient-based scheduling scheme presented in earlier papers reduces this to an optimization problem to be solved in each time-slot. Using a dual formulation, we give an optimal algorithm for this problem when multiple users can time-share each tone. We then give several low complexity heuristics that enforce integer tone allocations. Simulations are used to compare the performance of different algorithms.

To extend established concepts of fair resource allocation in wired networks to wireless networks, wired model assumptions must be adapted to be relevant for wireless networks as for example, in wireless networks losses due to environmental conditions may occur even in the absence of queueing congestion. Thus fundamental questions of the existence and uniqueness of fair rate allocations must be reconsidered. We treat wireless networks characterized by lossy channels, spatial channel reuse, multiple routes and multiple frequencies. We establish the existence and uniqueness of utility fair and max-min fair solutions and that, as loss rates decrease, fair allocations converge to the loss-less ones.

This paper presents a proof of the rate distortion function of a Poisson process with a queuing distortion measure that is in complete analogy with the proofs associated with the rate distortion functions of a Bernoulli source with Hamming distortion measure and a Gaussian source with squared-error distortion measure. Analogous to those problems, the distortion measure that we consider is related to the logarithm of the conditional distribution relating the input to the output of a well-known channel coding problem, specifically the Anantharam and Verdu "Bits through Queues" [1] coding problem. Our proof of the converse utilizes McFadden's point process entropy formulation [2] and involves a number of mutual information inequalities, one of which exploits the maximum-entropy achieving property of the Poisson process. Our test channel uses Burke's theorem [3], [4] to prove achievability.

The capacity and the reliability function as the peak constraint tends to zero are considered for a discrete-time memoryless channel with peak constrained inputs. Prelov and van der Meulen (1993) showed that under mild conditions the ratio of the capacity to the squared peak constraint converges to one-half the maximum eigenvalue of the Fisher information matrix and if the Fisher information matrix is nonzero, the asymptotically optimal input distribution is symmetric antipodal signaling. Under similar conditions, it is shown in the first part of the paper that the reliability function has the same asymptotic shape as the reliability function for the power-constrained infinite bandwidth white Gaussian noise channel. The second part of the paper deals with Rayleigh-fading channels. For such channels, the Fisher information matrix is zero, indicating the difficulty of transmission over such channels with small peak constrained signals. Asymptotics for the Rayleigh channel are derived and applied to obtain the asymptotics of the capacity of the Marzetta and Hochwald (1999) fading channel model for small peak constraints, and to obtain a result of the type of Medard and Gallager for wide-band fading channels.

Medard and Gallager (2002) showed that very large bandwidths on certain fading channels cannot be effectively used by direct sequence or related spread-spectrum systems. This paper complements the work of Medard and Gallager. First, it is shown that a key information-theoretic inequality of Medard and Gallager can be directly derived using the theory of capacity per unit cost, for a certain fourth-order cost function, called fourthegy. This provides insight into the tightness of the bound. Secondly, the bound is explored for a wide-sense-stationary uncorrelated scattering (WSSUS) fading channel, which entails mathematically defining such a channel. In this context, the fourthegy can be expressed using the ambiguity function of the input signal. Finally, numerical data and conclusions are presented for direct-sequence type input signals.