Caching has been widely leveraged to significantly improve network performance and mitigate congestion. However, characterizing the optimal tradeoff between routing cost and cache deployment cost remains an open problem. In this paper, for a network with arbitrary topology and congestion-dependent nonlinear cost functions, we aim to jointly determine the cache deployment, content placement, and hop-by-hop routing strategies, so that the sum of routing cost and cache deployment cost is minimized. We tackle this mixed-integer nonlinear problem starting with a fixed-routing setting, and then generalize to a dynamic-routing setting. For the fixed-routing setting, a Gradient-combining Frank-Wolfe algorithm with (1/2, 1)-approximation is presented. For the general dynamic-routing setting, we obtain a set of KKT conditions, and devise a distributed and adaptive online algorithm based on these conditions. We demonstrate via extensive simulation that our algorithms significantly outperform a number of baselines.

Deploying data- and computation-intensive applications such as large-scale AI into heterogeneous dispersed computing networks can significantly enhance application performance by mitigating network resource bottlenecks, including bandwidth, storage, and computing power. However, current resource allocation methods do not provide a comprehensive solution that jointly considers arbitrary topology, elastic resource amount, reuse of computation results, and congestion-dependent optimization objectives. These aspects are vital when modeling state-of-the-art heterogeneous dispersed computing networks with high demand volume. In this paper, we propose LOAM, a low-latency joint communication, caching, and computation placement framework. LOAM incorporates the above aspects with a rigorous analytical foundation. It tackles the formulated NP-hard cost minimization problem with two methods: an offline method with a constant factor approximation of 1/2, and an online adaptive method with a bounded gap from the optimum. Through extensive packetlevel simulation, LOAM outperforms multiple baselines in both synthesis and real-world network scenarios.

Federated learning (FL) enables collaborative learning across multiple clients. In most FL work, all clients train a single learning task. However, the recent proliferation of FL applications may increasingly require multiple FL tasks to be trained simultaneously, sharing clients’ computing resources, which we call Multiple-Model Federated Learning (MMFL). Current MMFL algorithms use naïve average-based client-task allocation schemes that often lead to unfair performance when FL tasks have heterogeneous difficulty levels, as the more difficult tasks may need more client participation to train effectively. Furthermore, in the MMFL setting, we face a further challenge that some clients may prefer training specific tasks to others, and may not even be willing to train other tasks, e.g., due to high computational costs, which may exacerbate unfairness in training outcomes across tasks. We address both challenges by firstly designing FedFairMMFL, a difficulty-aware algorithm that dynamically allocates clients to tasks in each training round, based on the tasks’ current performance levels. We provide guarantees on the resulting task fairness and FedFairMMFL’s convergence rate. We then propose novel auction designs that incentivizes clients to train multiple tasks, so as to fairly distribute clients’ training efforts across the tasks, and extend our convergence guarantees to this setting. We finally evaluate our algorithm with multiple sets of learning tasks on real world datasets, showing that our algorithm improves fairness by improving the final model accuracy and convergence speed of the worst performing tasks, while maintaining the average accuracy across tasks.

Caching is vital for high-throughput networks in data-intensive applications. Dynamic random-access memory (DRAM), often used for caching due to its high data transfer rate, faces limitations in capacity and cost, hindering scalability needed to meet growing demand. Evolving flash storage can augment DRAM, but necessitates caching techniques adapted to its charac-teristics for optimal network performance. This paper models the cache as a set of storage blocks with varying rate parameters and utilization costs. Utilizing a framework that enables joint caching and forwarding, we introduce an optimization technique based on the drift-plus-penalty method. Our approach minimizes the drift-plus-penalty expression in a virtual control plane and offers a throughput-cache utilization cost trade-off. We implement a corresponding practical policy in the data plane. Simulations demonstrate the superior performance of our approach in total delay and cache utilization costs.

Collaborative edge computing (CEC) is an emerging paradigm for heterogeneous devices to collaborate on edge computation jobs. For congestible links and computing units, delay-optimal forwarding and offloading for service chain tasks (e.g., DNN with vertical split) in CEC remains an open problem. In this paper, we formulate the service chain forwarding and offloading problem in CEC with arbitrary topology and heterogeneous transmission/computation capability, and aim to minimize the aggregated network cost. We consider congestion-aware nonlinear cost functions that cover various performance metrics and constraints, such as average queueing delay with limited processor capacity. We solve the non-convex optimization problem globally by analyzing the KKT condition and proposing a sufficient condition for optimality. We then propose a distributed algorithm that converges to the global optimum. The algorithm adapts to changes in input rates and network topology, and can be implemented as an online algorithm. Numerical evaluation shows that our method significantly outperforms baselines in multiple network instances, especially in congested scenarios.

As edge computing capabilities increase, model learning deployments in diverse edge environments have emerged. In experimental design networks, introduced recently, network routing and rate allocation are designed to aid the transfer of data from sensors to heterogeneous learners. We design efficient experimental design network algorithms that are (a) distributed and (b) use multicast transmissions. This setting poses significant challenges as classic decentralization approaches often operate on (strictly) concave objectives under differentiable constraints. In contrast, the problem we study here has a non-convex, continuous DR-submodular objective, while multicast transmissions naturally result in non-differentiable constraints. From a technical standpoint, we propose a distributed Frank-Wolfe and a distributed projected gradient ascent algorithm that, coupled with a relaxation of non-differentiable constraints, yield allocations within a 1 − 1/e factor from the optimal. Numerical evaluations show that our proposed algorithms outperform competitors with respect to model learning quality.

Caching can be leveraged to significantly improve network performance and mitigate congestion. However, characterizing the optimal tradeoff between routing cost and cache deployment cost remains an open problem. In this paper, for a network with arbitrary topology and congestion-dependent nonlinear cost functions, we aim to jointly determine the cache deployment, content placement, and hop-by-hop routing strategies, so that the sum of routing cost and cache deployment cost is minimized. We tackle this mixed-integer nonlinear problem starting with a fixed-routing setting, and then generalize to a dynamic-routing setting. For the fixed-routing setting, a Gradient-combining Frank-Wolfe algorithm with $\left( {\frac{1}{2},1} \right)$-approximation is presented. For the general dynamic-routing setting, we obtain a set of KKT conditions, and devise a distributed and adaptive online algorithm based on these conditions. We demonstrate via extensive simulation that our algorithms significantly outperform a number of baselines.

Addressing intermittent client availability is critical for the real-world deployment of federated learning algorithms. Most prior work either overlooks the potential non-stationarity in the dynamics of client unavailability or requires substantial memory/computation overhead. We study federated learning in the presence of heterogeneous and non-stationary client availability, which may occur when the deployment environments are uncertain, or the clients are mobile. The impacts of heterogeneity and non-stationarity on client unavailability can be significant, as we illustrate using FedAvg, the most widely adopted federated learning algorithm. We propose FedAWE, which includes novel algorithmic structures that (i) compensate for missed computations due to unavailability with only $O(1)$ additional memory and computation with respect to standard FedAvg, and (ii) evenly diffuse local updates within the federated learning system through implicit gossiping, despite being agnostic to non-stationary dynamics. We show that FedAWE converges to a stationary point of even non-convex objectives while achieving the desired linear speedup property. We corroborate our analysis with numerical experiments over diversified client unavailability dynamics on real-world data sets.

We study the problem of minimizing energy costs for content delivery in wireless heterogeneous networks by jointly optimizing caching and power control strategies. This can be equivalently cast as a problem of maximizing the joint caching and power gain subject to meeting minimum signal-to-interference-plus-noise ratio constraints. The offline version of this problem is NP-hard, but we show that there exist polynomial-time approximation algorithms producing solutions within a constant factor 1 - 1/$e$from the optimal. We further provide an adaptive algorithm based on projected subgradient ascent over a concave relaxation of the expected joint caching and power gain, which yields the same approximation guarantee. We show that our proposed algorithm outperforms the alternating optimization method and other baseline algorithms in a number of network scenarios, in total power consumption and run time.

A fundamental challenge in wireless heterogeneous networks (HetNets) is to effectively utilize the limited transmission and storage resources in the presence of increasing deployment density and backhaul capacity constraints. To alleviate bottlenecks and reduce resource consumption, we design optimal caching and power control algorithms for multi-hop wireless HetNets. We formulate a joint optimization framework to minimize the average transmission delay as a function of the caching variables and the signal-to-interference-plus-noise ratios (SINR) which are determined by the transmission powers, while explicitly accounting for backhaul connection costs and the power constraints. Using convex relaxation and rounding, we obtain a reduced-complexity formulation (RCF) of the joint optimization problem, which can provide a constant factor approximation to the globally optimal solution. We then solve RCF in two ways: 1) alternating optimization of the power and caching variables by leveraging biconvexity, and 2) joint optimization of power control and caching. We characterize the necessary (KKT) conditions for an optimal solution to RCF, and use quasi-convexity to show that the KKT points are Pareto optimal for RCF. We then devise a subgradient projection algorithm to jointly update the caching and power variables under general SINR conditions. Finally, our analytical findings are supported by results from extensive numerical experiments.

Federated learning (FL) is an increasingly popular form of distributed learning across devices such as sensors and smartphones. To amortize the effort and cost of setting up FL training in real world systems, in practice multiple machine learning tasks may be trained during one FL execution. However, given that the tasks have varying complexities, naïve methods of allocating resource-constrained devices to work on each task may lead to highly variable performance across the tasks. We instead propose an α -fair based allocation algorithm that dynamically allocates tasks to users during multi-model FL training, based on the prevailing loss levels.

Federated learning (FL) is a distributed paradigm for collaboratively learning models without having clients disclose their private data. One natural and practically relevant metric to measure the efficiency of FL algorithms is the total wall-clock training time, which can be quantified by the product of the average time needed for a single iteration and the number of iterations for convergence. In this work, we focus on improving FL efficiency with respect to this metric through caching. Specifically, instead of having all clients download the latest global model from a parameter server, we select a subset of clients to access, with a smaller delay, a somewhat stale global model stored in caches. We propose CacheFL - a cache-enabled variant of FedAvg, and provide theoretical convergence guarantees in the general setting where the local data is imbalanced and heterogeneous. Armed with this result, we determine the caching strategies that minimize total wall-clock training time at a given convergence threshold for both stochastic and deterministic communication/computation delays. Through numerical experiments on real data traces, we show the advantage of our proposed scheme against several baselines, over both synthetic and real-world datasets.

We provide a flow-based coded caching framework for information centric networks. We jointly optimize delivery rates, cross coding, and cache contents allocation as a function of demand and the network's topology. Our model accounts for stor-age and transmission costs, demand asymmetry, and arbitrary multi-hop topologies, and relies on an ordered flow-based de-coding schedule for the transmissions created by pairwise coded flows. Through extensive experiments over multiple topologies, we observe that our coded caching scheme reduces transmission costs over competitors by several orders of magnitude.

Significant advances in edge computing capabilities enable learning to occur at geographically diverse locations. In general, the training data needed in those learning tasks are not only heterogeneous but also not fully generated locally. In this paper, we propose an experimental design network paradigm, wherein learner nodes train possibly different Bayesian linear regression models via consuming data streams generated by data source nodes over a network. We formulate this problem as a social welfare optimization problem in which the global objective is defined as the sum of experimental design objectives of individual learners, and the decision variables are the data transmission strategies subject to network constraints. We first show that, assuming Poisson data streams in steady state, the global objective is a continuous DR-submodular function. We then propose a Frank-Wolfe type algorithm that outputs a solution within a$1-1/e$factor from the optimal. Our algorithm contains a novel gradient estimation component which is carefully designed based on Poisson tail bounds and sampling. Finally, we complement our theoretical findings through extensive experiments. Our numerical evaluation shows that the proposed algorithm outperforms several baseline algorithms both in maximizing the global objective and in the quality of the trained models.

Significant advances in edge computing capabilities enable learning to occur at geographically diverse locations. In general, the training data needed in those learning tasks are not only heterogeneous but also not fully generated locally. In this paper, we propose an experimental design network paradigm, wherein learner nodes train possibly different Bayesian linear regression models via consuming data streams generated by data source nodes over a network. We formulate this problem as a social welfare optimization problem in which the global objective is defined as the sum of experimental design objectives of individual learners, and the decision variables are the data transmission strategies subject to network constraints. We first show that, assuming Poisson data streams, the global objective is a continuous DR-submodular function. We then propose a Frank-Wolfe type algorithm that outputs a solution within a 1 – 1/e factor from the optimal. Our algorithm contains a novel gradient estimation component which is carefully designed based on Poisson tail bounds and sampling. Finally, we complement our theoretical findings through extensive experiments. Our numerical evaluation shows that the proposed algorithm outperforms several baseline algorithms both in maximizing the global objective and in the quality of the trained models.

Collaborative edge computing (CEC) is an emerging paradigm where heterogeneous edge devices collaborate to fulfill computation tasks, such as model training or video processing, by sharing communication and computation resources. Nevertheless, when considering network congestion, the optimal data/result routing and computation offloading strategy of CEC still remains an open problem. In this paper, we formulate a flow model of partial-offloading and multi-hop routing in CEC network with arbitrarily topology and heterogeneous communication/computation capability. In contrast to most existing works, our model applies to tasks with non-negligible result size, and allows data sources to be distinct from the result destination. We propose a network-wide cost minimization problem with congestion-aware convex cost functions. Such convex cost covers various performance metrics and constraints, such as average queueing delay with limited processor capacity. Although the problem is non-convex, we provide necessary conditions and sufficient conditions for the global-optimal solution, and devise a fully distributed algorithm that converges to the optimum in polynomial time. Our proposed method allows asynchronous individual updating, and is adaptive to changes of network parameters. Numerical evaluation shows that our method significantly outperforms other baseline algorithms in multiple network instances, especially in congested scenarios.

We introduce a framework and provably-efficient schemes for ‘fresh’ caching at the (front-end) local cache of content that is subject to ‘dynamic’ updates at the (back-end) database. We start by formulating the hard-cache-constrained problem for this setting, which quickly becomes intractable due to the limited cache. To bypass this challenge, we first propose a flexible time-based-eviction model to derive the average system cost function that measures the system’s cost due to the service of aging content in addition to the regular cache miss cost. Next, we solve the cache-unconstrained case, which reveals how the refresh dynamics and popularity of content affect optimal caching. Then, we extend our approach to a soft-cache-constrained version, where we can guarantee that the cache use is limited with arbitrarily high probability. The corresponding solution reveals the interesting insight that ‘whether to cache an item or not in the local cache?’ depends primarily on its popularity level and channel reliability, whereas ‘how long the cached item should be held in the cache before eviction?’ depends primarily on its refresh rate. Moreover, we investigate the cost-cache saving trade-offs and prove that substantial cache gains can be obtained while also asymptotically achieving the minimum cost as the database size grows.

Driven by technologies such as IoT-enabled health care, machine learning applications at the edge, and industrial automation, mobile edge and fog computing paradigms have reinforced a general trend toward decentralized computing, where any network node can route traffic, compute tasks, and store data, possibly at the same time. In many such computing environments, there is a need to cache significant amounts of data, which may include large data sets, machine learning models, or executable code. In this work, we propose a framework for joint computation scheduling, caching, and request forwarding within such decentralized computing environments. We first characterize the stability region of a “genie-aided” computing network where data required by computation are instantly accessible, and develop a throughput optimal control policy for this model. Based on this, we develop a practically implementable distributed and adaptive algorithm, and show that it exhibits superior performance in terms of average task completion time, when compared to several baseline policies.

We consider a mobile network consisting of both the wireless access network and the backhaul network. All base stations in the access network and gateways in the backhaul network are equipped with caches, so that routing costs for serving content requests can be reduced by caching the requested content items closer to the users. In this case, user association in the wireless access network must be aware of both the quality of wireless channels and the content caching strategy. In this paper, we propose a framework that jointly optimizes wireless user association and content caching in both access and backhaul networks. The resulting problem is NP-hard. We propose a polynomial-time algorithm based on convex approximation and pipage rounding that produces a solution within a constant factor of 1 − 1/e from the optimal. Simulation results show that the proposed joint algorithm outperforms schemes that combine cache-independent user association methods with traditional caching strategies (e.g. LRU) in terms of minimizing the aggregate routing cost and backhaul traffic while achieving a high data sum rate in the access network.

We introduce a framework and provably-efficient schemes for `fresh' caching at the (front-end) local cache of content that is subject to `dynamic' updates at the (back-end) database. We start by formulating the hard-cache-constrained problem for this setting, which quickly becomes intractable due to the limited cache. To bypass this challenge, we first propose a flexible time-based-eviction model to derive the average system cost function that measures the system's cost due to the service of aging content in addition to the regular cache miss cost. Next, we solve the cache-unconstrained case, which reveals how the refresh dynamics and popularity of content affect the optimal caching. Then, we extend our approach to a soft-cache-constrained version, where we can guarantee that the cache use is limited with arbitrarily high probability. The corresponding solution reveals the interesting insight that `whether to cache an item or not in the local cache?' depends primarily on its popularity level, whereas `how long the cached item should be held in the cache before eviction?' depends primarily on its refresh rate. Moreover, we investigate the cost-cache saving tradeoffs and prove that substantial cache gains can be obtained while also asymptotically achieving the minimum cost as the database size grows.

We introduce the problem of optimal congestion control in cache networks, whereby both rate allocations and content placements are optimized jointly. We formulate this as a maximization problem with non-convex constraints, and propose solving this problem via (a) a Lagrangian barrier algorithm and (b) a convex relaxation. We prove different optimality guarantees for each of these two algorithms; our proofs exploit the fact that the non-convex constraints of our problem involve DR-submodular functions.

A fundamental challenge in wireless heterogeneous networks (HetNets) is to effectively use the limited transmission and storage resources in the presence of increasing deployment density and backhaul capacity constraints. To alleviate bottlenecks and reduce resource consumption, we design optimal caching and power control algorithms for multi-hop wireless HetNets. We devise a joint optimization framework to minimize the average transmission delay as a function of the caching variables and the signal-to-interference-plus-noise ratios (SINR) as determined by the transmission powers, while explicitly accounting for backhaul connection costs and the power constraints.Using convex relaxation and rounding, we obtain a reduced-complexity formulation (RCF) of the joint optimization problem, which can provide a constant factor approximation to the globally optimal solution. We characterize the necessary (KKT) conditions for an optimal solution to RCF, and use strict quasi-convexity to show that the KKT points are Pareto optimal for RCF. We then devise a subgradient projection algorithm to jointly update the caching and power variables, and show that under appropriate conditions, the algorithm converges at a linear rate to the local minima of RCF, under general SINR. We support our analytical findings with results from numerical experiments.

Caching networks can reduce the routing costs of accessing contents by caching contents closer to users. However, cache nodes may belong to different entities and behave selfishly to maximize their own benefits, which often lead to performance degradation for the overall network. While there has been extensive literature on allocating contents to caches to maximize the social welfare, the analysis of selfish caching behaviors remains largely unexplored. In this paper, we model the selfish behaviors of cache nodes as selfish caching games on arbitrary directed graphs with heterogeneous content popularity. We study the existence of a pure strategy Nash equilibrium (PSNE) in selfish caching games, and analyze its efficiency in terms of social welfare. We show that a PSNE does not always exist in arbitrary-topology caching networks. However, if the network does not have a mixed request loop, i.e., a directed loop in which each edge is traversed by at least one content request, we show that a PSNE always exists and can be found in polynomial time. Furthermore, we can avoid mixed request loops by properly choosing request forwarding paths. We then show that the efficiency of Nash equilibria, captured by the price of anarchy (PoA), can be arbitrarily poor if we allow arbitrary content request patterns, and adding extra cache nodes can make the PoA worse, i.e., cache paradox happens. However, when cache nodes have homogeneous request patterns, we show that the PoA is bounded even allowing arbitrary topologies. We further analyze the selfish caching games for cache nodes with limited computational capabilities, and show that an approximate PSNE exists with bounded PoA in certain cases of interest. Simulation results show that increasing the cache capacity in the network improves the efficiency of Nash equilibria, while adding extra cache nodes can degrade the efficiency of Nash equilibria.

We study networks of M/M/1 queues in which nodes act as caches that store objects. Exogenous requests for objects are routed towards nodes that store them; as a result, object traffic in the network is determined not only by demand but, crucially, by where objects are cached. We determine how to place objects in caches to attain a certain design objective, such as, e.g., minimizing network congestion or retrieval delays. We show that for a broad class of objectives, including minimizing both the expected network delay and the sum of network queue lengths, this optimization problem can be cast as an NP-hard submodular maximization problem. We show that so-called continuous greedy algorithm attains a ratio arbitrarily close to 1 - 1/e ≈ 0.63 using a deterministic estimation via a power series; this drastically reduces execution time over prior art, which resorts to sampling. Finally, we show that our results generalize, beyond M/M/1 queues, to networks of M/M/k and symmetric M/D/1 queues.

We propose a decentralized spatial soft-core cache placement (SSCC) policy for wireless networks. SSCC yields a spatially balanced sampling via negative dependence across caches, and can be tuned to satisfy cache size constraints with high probability. Given a desired cache hit probability, we compare the 95% confidence intervals of the required cache sizes for independent placement, hard-core placement and SSCC policies. We demonstrate that in terms of the required cache storage size, SSCC can provide up to more than 180% and 100% gains with respect to the independent and hard-core placement policies, respectively. SSCC can be used to enable proximity-based applications such as device-to-device communications and peer-to-peer networking as it promotes the item diversity and reciprocation among the nodes.

The emergence of IoT devices and the predicted increase in the number of data-driven and delay-sensitive applications highlight the importance of dispersed computing platforms (e.g. edge computing and fog computing) that can intelligently manage in-network computation and data placement. In this paper, we propose the DECO (Data-cEntric COmputation) framework for joint computation, caching, and request forwarding in data-centric computing networks. DECO utilizes a virtual control plane which operates on the demand rates for computation and data, and an actual plane which handles computation requests, data requests, data objects and computation results in the physical network. We present a throughput optimal policy within the virtual plane, and use it as a basis for adaptive and distributed computation, caching, and request forwarding in the actual plane. We demonstrate the superior performance of the DECO policy in terms of request satisfaction delay as compared with several baseline policies, through extensive numerical simulations over multiple network topologies.

Caching networks can reduce the routing costs of accessing contents by caching contents closer to users. However, cache nodes may belong to different entities and behave selfishly to maximize their own benefits, which often lead to performance degradation for the overall network. In this paper, we model the selfish behaviors of cache nodes as selfish caching games on arbitrary directed graphs with heterogeneous content popularity. We study the existence of a pure strategy Nash equilibrium (PSNE) in selfish caching games, and analyze its efficiency in terms of social welfare. We show that a PSNE does not always exist in arbitrary-topology caching networks. However, if the network does not have a mixed request loop, i.e., a directed loop in which each edge is traversed by at least one content request, we show that a PSNE always exists and can be found in polynomial time. We then show that the efficiency of Nash equilibria, captured by the price of anarchy (PoA), can be arbitrarily poor if we allow arbitrary content request patterns. However, when cache nodes have homogeneous request patterns, we show that the PoA is bounded even allowing arbitrary topologies. We further analyze the selfish caching games for cache nodes with limited computational capabilities, and show that an approximate PSNE exists with bounded PoA in certain cases of interest.

We propose a Coded selective-repeat ARQ protocol with cumulative feedback, by building on the uncoded baseline scheme for ARQ, developed by Ausavapattanakun and Nosratinia. Our method leverages discrete-time queuing and coding theory to analyze the performance of the proposed data transmission method. We incorporate forward error-correction (FEC) to reduce in-order delivery delay, and exploit a matrix signal-flow graph approach to analyze the throughput and delay. We demonstrate and contrast the performance of the Coded ARQ protocol with that of the uncoded ARQ scheme, with minimum coding, i.e., with a sliding window of size 2. Coded ARQ can provide gains up to about 40% in terms of throughput. It also provides delay guarantees, and is robust to various challenges such as imperfect and delayed feedback, burst erasures, and round-trip time fluctuations.

Future 5G systems will need to support ultra-reliable low-latency communications scenarios. From a latency-reliability viewpoint, it is inefficient to rely on average utility-based system design. Therefore, we introduce the notion of guaranteeable delay which is the average delay plus three standard deviations of the mean. We investigate the trade-off between guaranteeable delay and throughput for the point-to-point wireless erasure links with unreliable and delayed feedback, by bringing together signal flow techniques to the area of coding. We use tiny codes, i.e., sliding window by coding with just 2 packets, and design three variations of selective-repeat ARQ protocols, by building on the baseline scheme, i.e., uncoded ARQ, developed by Ausavapattanakun and Nosratinia: (i) Hybrid ARQ with soft combining at the receiver; (ii) cumulative feedback-based ARQ without rate adaptation; and (iii) coded ARQ with rate adaptation based on the cumulative feedback. Contrasting the performance of these protocols with uncoded ARQ, we demonstrate that the HARQ performs only slightly better, the cumulative feedback-based ARQ does not provide significant throughput while it has a better average delay, and the Coded ARQ can provide gains up to about 40% in terms of throughput. The Coded ARQ also provides delay guarantees, and is robust to various challenges such as imperfect and delayed feedback, burst erasures, and round-trip time fluctuations. This feature may be preferable for meeting the strict end-to-end latency and reliability requirements of the future use cases of ultra-reliable low-latency communications in 5G, such as mission-critical communications and industrial control for critical control messaging.

Recently, physical layer (PHY) caching has been proposed to exploit the dynamic side information induced by caches at base stations (BSs) to support coordinated multi-point (CoMP) and achieve high degrees of freedom (DoF) gains. Due to the limited cache storage capacity, the performance of PHY caching depends heavily on the cache content placement algorithm. In the existing algorithms, the cache content placement is adaptive to the long-term popularity distribution in an offline manner. We propose an online PHY caching framework, which adapts the cache content placement to microscopic spatial and temporary popularity variations to fully exploit the benefits of PHY caching. Specifically, the joint optimization of online cache content placement and content delivery is formulated as a mixed-timescale drift minimization problem to increase the CoMP opportunity and reduce the cache content placement cost. We propose a low-complexity algorithm to obtain a throughput-optimal solution. Moreover, we provide a closed-form characterization of the maximum sum DoF in the stability region and study the impact of key system parameters on the stability region. The simulations results show that the proposed online PHY caching framework achieves large gain over existing solutions.

We propose a cumulative feedback-based ARQ (CF ARQ) protocol for a sliding window of size 2 over packet erasure channels with unreliable feedback. We exploit a matrix signal-flow graph approach to analyze probability-generating functions of transmission and delay times. Contrasting its performance with that of the uncoded baseline scheme for ARQ, developed by Ausavapattanakun and Nosratinia, we demonstrate that CF ARQ can provide significantly less average delay under bursty feedback, and gains up to about 20% in terms of throughput. We also outline the benefits of CF ARQ under burst errors and asymmetric channel conditions. The protocol is more predictable across statistics, hence is more stable. This can help design robust systems when feedback is unreliable. This feature may be preferable for meeting the strict end-to-end latency and reliability requirements of future use cases of ultra-reliable low-latency communications in 5G, such as mission-critical communications and industrial control for critical control messaging.

We present a new unified framework for minimizing congestion-dependent network cost in caching networks by jointly optimizing forwarding and caching strategies. As caching variables are integer-constrained, the resulting optimization problem is NP-hard. To make progress, we focus on a relaxed version of the optimization problem, where caching variables are allowed to be real-valued. We develop necessary optimality conditions for the relaxed problem, and leverage this result to design MinDelay, an adaptive and distributed joint forwarding and caching algorithm, based on the conditional gradient algorithm. The MinDelay algorithm elegantly yields feasible routing variables and integer caching variables at each iteration, and can be implemented in a distributed manner with low complexity and overhead. Over a wide range of network topologies, simulation results show that MinDelay typically has significantly better delay performance in the low to moderate request rate regions. Moreover, the MinDelay and VIP algorithms complement each other in delivering superior delay performance across the entire range of request arrival rates.

Complex systems such as smart cities and smart power grids rely heavily on their interdependent components. The failure of a component in one network may lead to the failure of the supported component in another network. Components which support a large number of interdependent components may be more vulnerable to attacks and failures. In this paper, we study the robustness of two interdependent networks under node failures. By modeling each network using a random geometric graph (RGG), we study conditions for the percolation of two interdependent RGGs after in-homogeneous node failures. We derive analytical bounds on the interdependent degree thresholds (k1,k2), such that the interdependent RGGs percolate after removing nodes in Githat support more than kjnodes in Gj(∀i, j ∈ {1, 2}, i ≠ j). We verify the bounds using numerical simulation, and show that there is a tradeoff between k1and k2for maintaining percolation after the failures.

We study a problem of minimizing routing costs by jointly optimizing caching and routing decisions over an arbitrary network topology. We cast this as an equivalent caching gain maximization problem, and consider both source routing and hop-by-hop routing settings. The respective offline problems are NP-hard. Nevertheless, we show that there exist polynomial time approximation algorithms producing solutions within a constant approximation from the optimal. We also produce distributed, adaptive algorithms with the same approximation guarantees. We simulate our adaptive algorithms over a broad array of different topologies. Our algorithms reduce routing costs by several orders of magnitude compared with prior art, including algorithms optimizing caching under fixed routing.

Motivated by applications to delivery of dynamically updated, but correlated data in settings such as content distribution networks, and distributed file sharing systems, we study a single source multiple destination network coded multicast problem in a cache-aided network. We focus on models where the caches are primarily located near the destinations and the source has no cache. The source observes a sequence of correlated frames and is expected to do frame-by-frame encoding with no access to prior frames. We present a novel scheme that shows how the caches can be advantageously used to decrease the overall cost of multicast, even though the source encodes without access to past data. Our cache design and update scheme works with any choice of network code designed for a corresponding cache-less network, is largely decentralized, and works for an arbitrary network. We study a convex relation of the optimization problem that results from the overall cost function. The results of the optimization problem determine the rate allocation and caching strategies. Numerous simulation results are presented to substantiate the theory developed.

In content-centric wireless networks, physical layer (PHY) caching has been proposed to exploit the dynamic side information induced by base station (BS) cache to support Coordinated Multi-Point (CoMP) and achieve huge capacity gain. The performance of PHY caching depends heavily on the cache content placement algorithm. In existing algorithms, the cache content placement is adaptive to the long-term popularity distribution in an offline manner. We propose an online PHY caching framework based on the concept of virtual interest packet (VIP) in a virtual network. The VIP captures microscopic spatial and temporary popularity variations, and thus the VIP-based online PHY caching can adapt the cached content to the microscopic popularity variations to fully exploit the benefits of PHY caching. The joint optimization of online caching and content delivery is formulated as a mixed timescale drift minimization problem and a low complexity algorithm is proposed to find the optimal solution. Simulations show that the proposed solution achieves large gain over existing solutions.

The problem of finding network codes for general connections is inherently difficult in capacity constrained networks. Resource minimization for general connections with network coding is further complicated. Existing methods for identifying solutions mainly rely on highly restricted classes of network codes, and are almost all centralized. In this paper, we introduce linear network mixing coefficients for code constructions of general connections that generalize random linear network coding for multicast connections. For such code constructions, we pose the problem of cost minimization for the subgraph involved in the coding solution and relate this minimization to a path-based constraint satisfaction problem (CSP) and an edge-based CSP. While CSPs are NP-complete in general, we present a path-based probabilistic distributed algorithm and an edge-based probabilistic distributed algorithm with almost sure convergence in finite time by applying communication free learning. Our approach allows fairly general coding across flows, guarantees no greater cost than routing, and shows a possible distributed implementation. Numerical results illustrate the performance improvement of our approach over existing methods.

We study the throughput and delay characteristics of wireless caching networks, where users are mainly interested in retrieving content stored in the network, rather than in maintaining source-destination communication. Nodes are assumed to be uniformly distributed in the network area. Each node has a limited-capacity content store, which it uses to cache contents. We propose an achievable caching and transmission scheme whereby requesters retrieve content from the caching point, which is closest in the Euclidean distance. We establish the throughput and delay scaling of the achievable scheme, and show that the throughput and delay performance are order-optimal within a class of schemes. We then solve the caching optimization problem, and evaluate the network performance for a Zipf content popularity distribution, letting the number of content types and the network size both go to infinity. Finally, we extend our analysis to heterogeneous wireless networks where, in addition to wireless nodes, there are a number of base stations uniformly distributed at random in the network area. We show that in order to achieve a better performance in a heterogeneous network in the order sense, the number of base stations needs to be greater than the ratio of the number of nodes to the number of content types. Furthermore, we show that the heterogeneous network does not yield performance advantages in the order sense if the Zipf content popularity distribution exponent exceeds 3/2.

Emerging Information-Centric Networking (ICN) architectures seek to optimally utilize both bandwidth and storage for efficient content distribution over the network. The Virtual Interest Packet (VIP) framework has been proposed to enable joint design of forwarding, caching, and congestion control strategies within the Named Data Networking (NDN) architecture. While the existing VIP algorithms exhibit good performance, they are primarily focused on maximizing network throughput and utility, and do not explicitly consider user delay. In this paper, we develop a new class of enhanced algorithms for joint dynamic forwarding, caching and congestion control within the VIP framework. These enhanced VIP algorithms adaptively stabilize the network and maximize network utility, while improving the delay performance by intelligently making use of VIP information beyond one hop. Generalizing Lyapunov drift techniques, we prove the throughput optimality and characterize the utility-delay tradeoff of the enhanced VIP algorithms. Numerical experiments demonstrate the superior performance of the resulting enhanced algorithms for handling Interest Packets and Data Packets within the actual plane, in terms of low network delay and high network utility.

Content-Centric Networking (CCN) is a recent network paradigm designed to address some key limitations of the current IP-based Internet. One of its main features is innetwork content caching which allows requests for content to be served by routers. Despite the benefits of improved bandwidth utilization and lower latency of retrieving popular content, innetwork caching inhibits producers from collecting information about content that is requested and later served from network caches. Such information is often needed for accounting and popularity purposes. In this paper, we address accounting in CCN by varying the degree of consumer, router, and producer involvement. We also identify and analyze inherent performance and security tradeoffs. We show that fine-grained accounting is infeasible with router caches and without explicit application support. We then recommend accounting strategies that entail a few simple requirements for CCN architectures. Finally, we show, via experimental results, that network-layer CCN accounting is viable and incurs low overhead for all parties involved. approaches.

We study the problem of optimal content placement over a network of caches, a problem naturally arising in several networking applications, including ICNs, CDNs, and P2P systems. Given a demand of content request rates and paths followed, we wish to determine the content placement that maximizes the expected caching gain, i.e., the reduction of routing costs due to intermediate caching. The offline version of this problem is NP-hard and, in general, the demand and topology may be a priori unknown. Hence, a distributed, adaptive, constant approximation content placement algorithm is desired. We show that path replication, a simple algorithm frequently encountered in literature, can be arbitrarily suboptimal when combined with traditional eviction policies, like LRU, LFU, or FIFO. We propose a distributed, adaptive algorithm that performs stochastic gradient ascent on a concave relaxation of the expected caching gain, and constructs a probabilistic content placement within 1-1/e factor from the optimal, in expectation. Motivated by our analysis, we also propose a novel greedy eviction policy to be used with path replication, and show through numerical evaluations that both algorithms significantly outperform path replication with traditional eviction policies over a broad array of network topologies.

For general multi-hop queueing networks, delay optimal network control has unfortunately been an outstanding problem. The dynamic backpressure (BP) algorithm elegantly achieves throughput optimality, but does not yield good delay performance in general. In this paper, we obtain an asymptotically delay optimal control policy, which resembles the BP algorithm in basing resource allocation and routing on a backpressure calculation, but differs from the BP algorithm in the form of the backpressure calculation employed. The difference suggests a possible reason for the unsatisfactory delay performance of the BP algorithm, i.e., the myopic nature of the BP control. Motivated by this new connection, we introduce a new class of enhanced backpressure-based algorithms which incorporate a general queue-dependent bias function into the backpressure term of the traditional BP algorithm to improve delay performance. These enhanced algorithms exploit queue state information beyond one hop. We prove the throughput optimality and characterize the utility-delay tradeoff of the enhanced algorithms. We further focus on two specific distributed algorithms within this class, which have demonstrably improved delay performance as well as acceptable implementation complexity.

The problem of finding network codes for general connections is inherently difficult. Resource minimization for general connections with network coding is further complicated. Existing methods for identifying solutions mainly rely on very restricted classes of network codes, and are almost all centralized. In this paper, we introduce linear network mixing coefficients for code constructions of general connections that generalize random linear network coding (RLNC) for multicast connections. For such code constructions, we pose the problem of cost minimization for the subgraph involved in the coding solution and relate this minimization to a Constraint Satisfaction Problem (CSP) which we show can be simplified to have a moderate number of constraints. While CSPs are NP-complete in general, we present a probabilistic distributed algorithm with almost sure convergence in finite time by applying Communication Free Learning (CFL). Our approach allows fairly general coding across flows, guarantees no greater cost than routing, and shows a possible distributed implementation. Numerical results illustrate the performance improvement of our approach over existing methods.

We study the throughput and delay characteristics of wireless networks based on a content-centric network architecture, where users are mainly interested in retrieving content stored in the network, rather than in maintaining source-destination communication. Nodes are assumed to be uniformly distributed in the network area. Each node has a limited-capacity content store, which it uses to cache contents according to the proposed caching scheme. Requested content follows a general popularity distribution, and users employ multi-hop communication to retrieve the requested content from the closest cache. We derive the throughput-delay tradeoff of the content-centric wireless network model and solve the caching optimization problem. We then evaluate the network performance for a Zipf content popularity distribution, letting the number of content types and the network size both go to infinity. Finally, we extend our analysis to heterogeneous wireless networks where, in addition to wireless nodes, there are a number of base stations uniformly distributed at random in the network area.

For general connections, the problem of finding network codes and optimizing resources for those codes is intrinsically difficult and little is known about its complexity. Most of the existing solutions rely on very restricted classes of network codes in terms of the number of flows allowed to be coded together, and are not entirely distributed. In this paper, we consider a new method for constructing linear network codes for general connections of continuous flows to minimize the total cost of edge use based on mixing. We first formulate the minimum-cost network coding design problem. To solve the optimization problem, we propose two equivalent alternative formulations with discrete mixing and continuous mixing, respectively, and develop distributed algorithms to solve them. Our approach allows fairly general coding across flows and guarantees no greater cost than any solution without inter-flow network coding.

Delay optimal control of multi-hop networks remains a challenging problem even in the simplest scenarios. In this paper, we consider delay optimal control of a two-hop half-duplex network with independent identically distributed ON-OFF fading. Both the source node and the relay node are equipped with infinite buffers and have exogenous bit arrivals. We focus on delay optimal link selection to minimize the average sum queue length over a finite horizon subject to a half-duplex constraint. To solve the problem, we introduce a new approach, whereby an actual discrete time system (ADTS) is approximated using a virtual continuous time system (VCTS). We obtain an asymptotically delay optimal policy in the VCTS. Using the relationship between the VCTS and the ADTS, we obtain an asymptotically delay optimal policy in the ADTS. The obtained policy has both a priority feature and a safety stock feature. It offers good design insights for wireless relay networks. In addition, the obtained policy has a closed-form expression, does not require knowledge of arrival statistics, and can be implemented online. Finally, using renewal theory and the theory of random walks, we analyze the average delay resulting from the asymptotically delay optimal policy.

For general multi-hop queueing networks, delay optimal network control has unfortunately been an outstanding problem for some time. The dynamic backpressure (DBP) algorithm is an elegant network control algorithm achieving throughput optimality. However, it does not yield good delay performance in general. In this paper, we formulate the delay optimal network control problem for general multi-hop queueing networks. We obtain an asymptotically delay optimal control policy. Surprisingly, we show that the asymptotically delay optimal control resembles the DBP algorithm in basing resource allocation and routing on a backpressure calculation, but differs from the DBP algorithm in the form of the backpressure calculation employed. This difference suggests a possible reason for the poor delay performance of the DBP algorithm. To the best of our knowledge, this is the first work which provides an analytical connection between delay optimal control and the throughput optimal DBP algorithm. The connection provides a theoretical basis for designing enhanced DBP algorithms with improved delay performance via the use of QSI beyond one hop.

Energy efficiency and quality-of-service (QoS) have been two key considerations in the design of modern multi-user communication systems. In this paper, we study optimal rate control over the multiple-access channel to minimize the sum transmission energy under general QoS constraints. We model the data flows and QoS constraints using a cumulative curves methodology and formulate the optimization problem as a continuous-time control problem. We analyze the optimality properties and show that the optimization problem has a dynamic programming (DP) structure induced by successive interference cancellation (SIC). Based on the DP structure, we propose a low-complexity solution, which is amenable to an appealing graphical visualization and has the same order of complexity as the single user energy minimization problem. We bound the energy gap between the low-complexity solution and the optimal solution, and show that the energy gap diminishes to zero in the symmetric high SNR regime.

We present a natural and low-complexity technique for achieving the capacity of the Gaussian relay network in the high SNR regime. Specifically, we propose the use of end-to-end structured lattice codes with the amplify-and-forward strategy, where the source uses a nested lattice code to encode the messages and the destination decodes the messages by lattice decoding. All intermediate relays simply amplify and forward the received signals over the network to the destination. We show that the end-to-end lattice-coded amplify-and-forward scheme approaches the capacity of the layered Gaussian relay network in the high SNR regime. Next, we extend our scheme to non-layered Gaussian relay networks under the amplify-and-forward scheme, which can be viewed as a Gaussian intersymbol interference (ISI) channel. Compared with other schemes, our approach is significantly simpler and requires only the end-to-end design of the lattice precoding and decoding. It requires little knowledge of the network topology or the individual channel gains.

In this paper, we consider a multihop wireless network, where Femto Base Stations (FBSs) act as relay nodes, and are incentivized to carry traffic from a Macro Base Station (MBS) to Macro Users (MUs).We first examine the the global problem of jointly optimal allocation of traffic flow and transmission power in the multihop wireless network. We then examine a game in which selfish and strategic relays submit charging functions to the source and choose transmission powers over a MAC channel from the relays to the user. Relay charging functions are considered which yield efficient allocation at the Nash Equilibrium (NE) of the game. We observe that for efficiency, relays should be taxed for the interference it creates to other relays. We also observe that inefficient equilibria occur when the charging function is a function only of the traffic flow rate through the relay. Numerical studies demonstrate the variation of inefficiency with network structure.

The capacity of multiuser networks has been a long-standing problem in information theory. Recently, Avestimehr et al. have proposed a deterministic network model to approximate multiuser wireless networks. This model, known as the ADT network model, takes into account the broadcast nature as well as the multiuser interference inherent in the wireless medium. For the types of connections we consider, we show that the results of Avestimehr et al. under the ADT model can be reinterpreted within the algebraic network coding framework introduced by Koetter and Médard. Using this framework, we propose an efficient distributed linear code construction for the deterministic wireless multicast relay network model. Unlike several previous coding schemes, we do not attempt to find flows in the network. Instead, for a layered network, we maintain an invariant where it is required that at each stage of the code construction, certain sets of codewords are linearly independent.

The papers in this special issue explore advances in communication technologies that have the potential for improving energy efficiency and realizing the smart grid vision.

Arikan's polar coding method is extended to two-user multiple-access channels. It is shown that if the two users of the channel use Arikan's construction, the resulting channels will polarize to one of five possible extremals, on each of which uncoded transmission is optimal. The sum rate achieved by this coding technique is the one that corresponds to uniform input distributions. The encoding and decoding complexities and the error performance of these codes are as in the single-user case: O(nlogn) for encoding and decoding, and o(2-n1/2-ε) for the block error probability, where n is the blocklength.

Delay-optimal control of multi-hop networks remains a challenging problem even in the simplest scenarios. In this paper, we consider delay-optimal control of a two-hop half-duplex network with i.i.d. on-off fading. Both the source node and the relay node are equipped with infinite buffers and have exogenous bit arrivals. We focus on delay-optimal link selection to minimize the average bit delay subject to a half-duplex constraint. To solve the problem, we introduce a new approach whereby an actual discrete time system (ADTS) is approximated using a virtual continuous time system (VCTS). Using dynamic programming, we recursively solve the delay minimization problem in the VCTS in terms of a simpler prototype problem, which can be addressed using continuous-time optimal control techniques. We show that the obtained solution in the VCTS is asymptotically optimal in the ADTS. Our solution has a closed-form expression and does not require knowledge of the arrival statistics. Finally, using renewal theory and the theory of random walks, we analyze the average delay resulting from the asymptotically optimal solution.

We analyze a nonlinear pricing model with limited information. Each buyer can purchase a large variety, d, of goods. His preference for each good is represented by a scalar and his preference over d goods is represented by a d-dimensional vector. The type space of each buyer is given by a compact subset of Rd+ with a continuum of possible types. By contrast, the seller is limited to offer a finite number M of d-dimensional choices.

"Smart Grid" refers to the modernization of electric grid to allow for more efficient generation, transmission, distribution, and usage of energy. This is becoming necessary in order to transition to a more sustainable energy generation and consumption and to reduce any adverse effects on the environment. While more advances in areas like renewable energies and network control are necessary, advances in communication technologies, data fusion and mining, as well as scheduling and optimization are also critical in order to achieve this vision. It is anticipated that the same communication technologies that have revolutionized our way of life in the past decades, ranging from sensor networks, mobile Internet, cloud computing, smart phones and many others, will have direct applicability to Smart Grid. Our objectives for this series of IEEE JSAC are focused on identifying the numerous communication challenges posed by the various aspects and functionalities of the Smart Grid and exploring research avenues for addressing them. We have received 67 papers, and after thorough review and careful deliberations, we have accepted 10 papers in this first issue. The articles in this issue can be grouped into 4 main sub-topic areas, namely, scheduling and load balancing, energy pricing, routing, and security.

This paper considers the impact of incomplete information on incentives for node cooperation in parallel relay networks with one source node, one destination node, and multiple relay nodes. All nodes are selfish and strategic, interested in maximizing their own profit instead of the social welfare. The paper considers the practical situation where the channel state on any given relay path is not observable to the source or to the other relays. Different bargaining relationships between the source and the relays are considered, and a framework for studying the efficiency loss induced by incomplete information is proposed. The source of the efficiency loss is analyzed, and the amount of inefficiency which results is quantified.

This paper studies the throughput-delay performance tradeoff in large-scale wireless ad hoc networks. It has been shown that the per source-destination pair throughput can be improved from Θ(1/√{nlogn}) to Θ(1) if nodes are allowed to move and a two-hop relay scheme is employed. The price paid for such a throughput improvement is large delay. Indeed, the delay scaling of the two-hop relay scheme is Θ(nlogn) under the random walk mobility model. In this paper, coding techniques are used to improve the throughput-delay tradeoff for mobile wireless networks. For the random walk mobility model, the delay is reduced from Θ(nlogn) to Θ(n) by employing a maximum distance separable Reed-Solomon coding scheme. This coding approach maintains the diversity gained by mobility while decreasing the delay.

We consider delay-optimal link selection for a two-hop three-node cooperative network with bursty packet arrivals, where both the source node and the half-duplex cooperative node have exogenous arrivals. We consider the problem of minimizing the random sum queue length process subject to link selection constraints under a general bursty bit flow model and obtain a simple closed-form delay-optimal link selection policy, requiring only 1 bit of state information for each queue. Furthermore, using the structure of the delay-optimal link selection policy, we obtain the closed-form average bit delay performance for deterministic and Poisson packet arrival processes, Finally, we derive a new lower bound for the delay penalty incurred by the (throughput-optimal) dynamic backpressure (DBP) link selection algorithm, as compared with the delay-optimal link selection policy.

This paper studies the problem of resilience to node failures in large-scale networks modelled by random geometric graphs. Adopting a percolation-based viewpoint, the paper investigates the ability of the network to maintain global communication in the face of dependent node failures. Degree-dependent site percolation processes on random geometric graphs are examined, and the first known analytical conditions are obtained for the existence and non-existence, respectively, of a large connected component of operational network nodes after degree-dependent node failures. In electrical power networks or wireless communication and computing networks, cascading failure from power blackouts or virus epidemics may result from a small number of initial node failures triggering global failure events affecting the whole network. With the use of a simple but descriptive model, it is shown that the cascading failure problem is equivalent to a degree-dependent percolation process. The first analytical conditions are obtained for the occurrence and non-occurrence of cascading failures, respectively, in large-scale networks with geometric constraints.

The maximum differential backlog (MDB), or “backpressure” control policy of Tassiulas and Ephremides has been shown to adaptively maximize the stable throughput of multihop wireless networks with random traffic arrivals and queueing. The practical implementation of the MDB policy in wireless networks with mutually interfering links, however, requires the development of distributed optimization algorithms. Within the context of code-division multiple-access (CDMA)-based multihop wireless networks, we develop a set of node-based scaled gradient projection power control algorithms which solves the MDB optimization problem based on the high-signal-to-interference-plus-noise ratio (SINR) approximation of link capacities using low communication overhead. We investigate the impact of the high-SINR approximation and the nonnegligible convergence time required by the power control algorithms on the throughput region achievable by the iterative MDB policy. We show that the policy can achieve at least the stability region induced by the high-SINR capacity region.

We study the throughput-delay performance trade-off in large-scale wireless ad hoc networks. It has been shown that the per source-destination pair throughput can be improved from Θ(1/√n log n) to Θ(1) if nodes are allowed to move and a 2-hop relay scheme is employed. The price paid for such an improvement on throughput is large delay. Indeed, the delay scaling of the 2-hop relay scheme is Θ(n log n) under the random walk mobility model. In this paper, we employ coding techniques to improve the throughput-delay trade-off for mobile wireless networks. For the random walk mobility model, we improve the delay from Θ(n log n) to Θ(n) by employing Reed-Solomon (RS) codes. Our approach maintains the diversity gained by mobility while decreasing the delay.

We study the problem of wireless network resilience to node failures from a percolation-based perspective. In practical wireless networks, it is often the case that the failure probability of a node depends on its degree (number of neighbors). We model this phenomenon as a degree-dependent site percolation process on random geometric graphs. In particular, we obtain analytical conditions for the existence of phase transitions within this model. Furthermore, in networks carrying traffic load, the failure of one node can result in redistribution of the load onto other nearby nodes. If these nodes fail due to excessive load, then this process can result in a cascading failure. Using a simple but descriptive model, we show that the cascading failure problem for large-scale wireless networks is equivalent to a degree-dependent site percolation on random geometric graphs. We obtain analytical conditions for cascades in this model. This work represents the first investigation of cascading phenomena in networks with geometric constraints.

We study connectivity and transmission latency in wireless networks with unreliable links from a percolation-based perspective. We first examine static models, where each link of the network is functional (active) with some probability, independently of all other links, where the probability may depend on the distance between the two nodes. We obtain analytical upper and lower bounds on the critical density for phase transition in this model. We then examine dynamic models, where each link is active or inactive according to a Markov on- off process. We show that a phase transition also exists in such dynamic networks, and the critical density for this model is the same as the one for static networks under some mild conditions. Furthermore, due to the dynamic behavior of links, a delay is incurred for any transmission even when propagation delay is ignored. We study the behavior of this transmission delay and show that the delay scales linearly with the Euclidean distance between the sender and the receiver when the network is in the subcritical phase, and the delay scales sub-linearly with the distance if the network is in the supercritical phase.

We study pricing games in multi-hop relay networks where nodes price their services and route their traffic selfishly and strategically. Each node (1) makes a bid to each of its customers, specifying a charging function and a proposed traffic share, and (2) allocates its received traffic to its service providers. A node aims to maximize its profit from forwarding traffic. We show that the socially optimal routing can always be induced by an equilibrium where no node can increase its profit by unilaterally changing its bids. Inefficient equilibria arise in oligopolies due to the monopolistic pricing power of a superior relay. It results in finite price of anarchy if marginal cost functions are concave, but unbounded price of anarchy when they are convex. Pricing games of general topology suffer from the intrinsic multi-hop network structure, which gives rise to infinite price of anarchy.

Information theory has shown that feedback can greatly improve the error probability performance of communication channels. In practical communication systems with random message arrivals and queuing, however, this error improvement may come at the expense of longer delay and additional burstiness caused by the retransmissions. In this paper, we assess the benefits using feedback from an integrated information-theoretic and queuing-theoretic perspective. In particular, we characterize policies which achieve the optimal tradeoff between transmission power and packet queuing delay for communication over fading channels with feedback. It is shown that the use of feedback yields substantial improvements in the power-delay tradeoff over systems without feedback.

In wireless networks, node mobility may be exploited to assist in information dissemination over time. We analyze the latency for information dissemination in large-scale mobile wireless networks. To study this problem, we map a network of mobile nodes to a network of stationary nodes with dynamic links. We then use results from percolation theory to show that under a constrained i.i.d. mobility model, the scaling behavior of the latency falls into two regimes. When the network is not percolated (subcritical), the latency scales linearly with the initial Euclidean distance between the sender and the receiver; when the network is percolated (supercritical), the latency scales sub-linearly with the distance.

In wireless networks, important network functionalities such as power control, rate allocation, routing, and congestion control must be optimized in a coherent and integrated manner. In this work, an interference-limited wireless network is considered, whereby power control and routing variables are chosen to minimize the sum of link costs which depend on both link capacities and link flow rates. The necessary conditions for optimality are established. These conditions are sufficient for optimality if link cost functions are jointly convex, and imply Pareto optimality if link costs are strictly quasi-convex. Network algorithms based on the scaled gradient projection method, where power control and routing are performed on a node-by-node basis, are presented. For these algorithms, explicit scaling matrices and stepsizes are found which lead to more distributed implementation, and which guarantee fast convergence to a network configuration satisfying the optimality conditions, starting from any initial configuration with finite cost. Refinements of the algorithms for more accurate link capacity models are presented, and the results are extended to wireless networks where the physical-layer rate region is given by an arbitrary convex set. Finally, it is shown that the power control and routing algorithms can naturally be extended to incorporate congestion control.

Percolation theory has become a useful tool for the analysis of large-scale wireless networks. We investigate the fundamental problem of characterizing the critical density lambdac(d)for d-dimensional Poisson random geometric graphs in continuum percolation theory. By using a probabilistic analysis which incorporates the clustering effect in random geometric graphs, we develop a new class of analytical lower bounds for the critical density lambdac(d). These analytical lower bounds are the tightest known to date, and reveal a deep underlying relationship between clustering effects and percolation phenomena.

A new spectrum allocation scheme is developed to satisfy the fundamental duplexing constraint in wireless networks. A feasible spectrum allocation is achieved through dividing the whole spectrum into multiple sub-bands and activating conflict-free links on each sub-band. It is found that the minimum number of sub-bands needed to yield a feasible spectrum allocation grows asymptotically at a logarithmic rate with the chromatic number. We design a simple distributed and asynchronous algorithm which yields a feasible spectrum allocation given enough sub-bands.

We consider cooperative relay networks with multiple stochastically varying end-to-end flows. For such networks, we study throughput optimal network control policies which stabilize the network's queues for any arrival rate in its stability region. In earlier work, we have developed such a policy for a simple four-node parallel relay network. In this paper, we show that this policy can be generalized to a much larger class of cooperative relay networks with various types of two-hop "cooperative links".

In battery-constrained wireless sensor networks, it is important to employ effective energy management while maintaining some level of network connectivity. Viewing this problem from a percolation-based connectivity perspective, we propose a fully distributed energy management algorithm for large-scale wireless sensor networks. This algorithm allows each sensor to probabilistically schedule its own activity based on its node degree. This mechanism is modelled by a degree-dependent dynamic site percolation process on random geometric graphs. We specify the conditions under which the resulting network is guaranteed to be percolated at all the time. We further study the delay performance of the proposed energy management algorithm by modelling the problem as a degree-dependent first passage percolation process on random geometric graphs.

We develop distributed algorithms to allocate resources in multi-hop wireless networks with the aim of minimizing the total cost. In order to observe the fundamental duplexing constraint that co-located transmitters and receivers cannot operate simultaneously on the same frequency band, we first devise a spectrum allocation scheme that divides the whole spectrum into multiple sub-bands and activates conflict-free links on each sub-band. We show that the minimum number of required sub-bands grows asymptotically at a logarithmic rate with the chromatic number of network connectivity graph. A simple distributed and asynchronous algorithm is developed to feasibly activate links on the available sub-bands. Given a feasible spectrum allocation, we then develop node-based distributed algorithms for optimally controlling the transmission powers on active links for each sub-band, jointly with traffic routes and user input rates in response to channel states and traffic demands. We show that under specified conditioans, the algorithms asymptotically converge to the optimal operating point.

We consider the multiple-access communication problem in a distributed setting for both the additive white Gaussian noise channel and the discrete memoryless channel. We propose a scheme called Distributed Rate Splitting to achieve the optimal rates allowed by information theory in a distributed manner. In this scheme, each real user creates a number of virtual users via a power/rate splitting mechanism in the M-user Gaussian channel or via a random switching mechanism in the M-user discrete memoryless channel. At the receiver, all virtual users are successively decoded. Compared with other multiple-access techniques, Distributed Rate Splitting (DRS) can be implemented with lower complexity and less coordination. Furthermore, in a symmetric setting, we show that the rate tuple achieved by this scheme converges to the maximum equal rate point allowed by the information-theoretic bound as the number of virtual users per real user tends to infinity. When the capacity regions are asymmetric, we show that a point on the dominant face can be achieved asymptotically. Finally, when there is an unequal number of virtual users per real user, we show that differential user rate requirements can be accommodated in a distributed fashion

In cooperative relaying, multiple nodes cooperate to forward a packet within a network. To date, such schemes have been primarily investigated at the physical layer with the focus on communication of a single end-to-end flow. This paper considers cooperative relay networks with multiple stochastically varying flows, which may be queued within the network. Throughput optimal network control policies are studied that take into account queue dynamics to jointly optimize routing, scheduling and resource allocation. To this end, a generalization of the maximum differential backlog algorithm is given, which takes into account the cooperative gains in the network. Several structural characteristics of this policy are discussed for the special case of parallel relay networks.

As today's communication networks (e.g., the Internet) grow in size and diversity, accurate, large-scale, and distributed traffic matrix estimation techniques will become increasingly important for many network control and management tasks. In this paper, we study the gravity model with entropy penalization approach for estimating traffic matrices based on link traffic measurements, which is known to have remarkable accuracy for real networks [7], [12]. We propose a dual approach to convert the constrained primal optimization problem under the gravity model into an unconstrained dual optimization problem. For most practical networks in which the number of links is much smaller than the number of origin-destination pairs, the dual problem has a much smaller dimension and hence scales for large networks. In addition, the solution algorithm for the dual problem can be implemented in a distributed manner.

We present a unified analytical framework within which power control and routing for wireless networks can be optimized on a node-by-node basis. We consider a multicommodity flow model for an interference-limited wireless network in which power control and routing variables are chosen to minimize convex link costs. Distributed scaled gradient projection algorithms are developed to iteratively adjust power control and routing schemes at individual nodes. We specify appropriate scaling matrices with which the algorithms quickly converge to the global optimum from any initial point. These scaling matrices can be computed locally at each node with limited control message overhead

We present a unified analytical framework within which capacity allocation, routing, and congestion control for wireless networks can be optimized in a coherent and integrated manner. We consider a multi-commodity flow model and examine wireless networks with general coding/modulation schemes represented by convex physical-layer capacity regions. Within this framework, capacity variables and routing variables are chosen to minimize convex link costs reflecting, for instance, average queueing delay. For problems with jointly convex cost functions, the necessary and sufficient conditions for optimality are derived. These results are then extended to the more general case where link costs are quasi-convex. Finally, we demonstrate that congestion control can be seamlessly incorporated into our framework

The Maximum Differential Backlog (MDB) control policy of Tassiulas and Ephremides has been shown to adaptively maximize the stable throughput of multi-hop wireless networks with random traffic arrivals and queueing. The practical implementation of the MDB policy in wireless networks with mutually interfering links, however, requires the development of distributed optimization algorithms. Within the context of CDMA-based multi-hop wireless networks, we develop a set of node-based scaled gradient projection power control algorithms which solves the MDB optimization problem in a distributed manner using low communication overhead. As these algorithms require time to converge to a neighborhood of the optimum, the implementation of the MDB policy must be done with delayed queue state information. For this, we show that the MDB policy with delayed queue state information remains throughput optimal.

We examine communication over slowly varying flat-fading additive white Gaussian noise (AWGN) channels with delayed channel state information (CSI) feedback to the transmitter and finite decoding delay constraints. Under a block-fading channel model, it is shown that a broadcast strategy maximizes the expected reliably received rate when the decoding delay constraint is one block and in certain cases when the delay constraint is two blocks. The latter requires a new analysis of underlying parallel Gaussian broadcast channels (GBCs) which are not degraded in the same direction

We introduce a new distributed multiple-access coding strategy called asymmetric distributed rate splitting for the additive white Gaussian noise multiple-access channel and discrete memoryless multiple-access channel. This strategy uses a rate splitting approach or a random switching approach to accommodate differential user rate requirements in a distributed manner. The achieved rates under this scheme are asymptotically optimal from a fundamental information theoretic viewpoint.

We analyze a distributed M-user multiple-access problem in both the additive white Gaussian noise channel and the discrete memoryless channel. A system where each user independently chooses a transmission rate according to a probability distribution function is considered. Under the assumption of symmetric capacity regions, we show that the optimal transmission rate distribution is a point mass for both channel models. To implement this, we propose a scheme called distributed rate splitting. In this scheme, each real user creates the same number of virtual users via a power/rate splitting mechanism in the M-user Gaussian channel or via a random switching mechanism in the M-user discrete memoryless channel. At the receiver, all virtual users are successively decoded. Distributed rate splitting allows multiple-access communication to take place with minimal control overhead. Moreover, the rate tuple achieved by this scheme converges to the maximum equal rate point allowed by the information-theoretic bound as the number of virtual users per real user tends to infinity

We give a model for cooperative communication in a parallel relay network that includes the stochastic arrival of packets and queueing. Exogenous arrivals at both the non-relay and the relay nodes are allowed. For this model, we provide a throughput optimal network control policy which stabilizes the network for any vector of arrival rates in its stability region. This policy generalizes the maximum differential backlog policies, taking into account potential cooperative gains in the network. Some structural properties of this policy are also discussed

An M-user Gaussian multiaccess channel with noise density No/2 and bandwidth W is studied. The M data sources generate packets according to independent Poisson processes with a common rate A. The goal is to design a controller, which allocates rates from C to the transmitters as a function of the joint queue state, so as to minimize average system delay. We consider the multiaccess channel with general packet length distributions. A policy giving longer queues higher rates (LQHR) for all increasing, Schur-convex functions is showed. A new technique combining dynamic programming and renewal theory to prove that a modified version of the LQHR policy minimizes for the two-user case is deviced.

An adaptive joint power control/rate allocation policies which maximize system throughput for multiaccess and broadcast fading channels with random packet arrivals and queueing is established in this paper.

We propose an algorithm for deinterlacing of interlaced video sequences. It successively builds approximations to the deinterlaced sequence by weighting various interpolation methods. A particular example given here uses four interpolation methods, weighted according to the errors each one introduces. Due to weighting, it is an adaptive algorithm. It is also time-recursive, since the motion-compensated part uses the previously interpolated frame. Furthermore, bidirectional motion estimation and compensation allow for better performance in the case of scene changes and covering/uncovering of objects. Experiments are run both on "real-world" and computer generated sequences. Finally, subjective testing is performed to evaluate the quality of the algorithm.