NextG (5G and beyond) networks, through the increasing integration of cloud/edge computing technologies, are becoming highly distributed compute platforms ideally suited to host emerging resource-intensive and latency-sensitive applications (e.g., industrial automation, extended reality, distributed AI). The end-to-end orchestration of such demanding applications, which involves function/data placement, flow routing, and joint communication/computation/storage resource allocation, requires new models and algorithms able to capture: (i) their disaggregated microservice-based architecture, (ii) their complex processing graph structures, including multiple-input multiple-output processing stages, and (iii) the opportunities to efficiently share and replicate real-time data streams that may be useful for multiple functions and/or end users. To this end, we first identify the technical gaps in existing literature that prevent efficiently addressing the optimal orchestration of emerging applications described by information-aware directed acyclic graphs (DAGs). We then leverage the recently proposed Cloud Network Flow optimization framework and a novel functionally-equivalent DAG-to-Forest graph transformation procedure to design IDAGO (Information-Aware DAG Orchestration), a polynomial-time multi-criteria approximation algorithm for the optimal orchestration of NextG media services over NextG compute-integrated networks. Results show that IDAGO's multiplicative cost reductions over leading baselines scale linearly with aggregate service load, reaching up to 3X gains in scenarios based on AWS and Unreal Engine data under moderate service loads.

Next-generation real-time compute-intensive applications, such as extended reality, multi-user gaming, and autonomous transportation, are increasingly composed of heterogeneous AI-intensive functions with diverse resource requirements and stringent latency constraints. While recent advances have enabled very efficient algorithms for joint service placement, routing, and resource allocation for increasingly complex applications, current models fail to capture the non-linear relationship between delay and resource usage that becomes especially relevant in AI-intensive workloads. In this paper, we extend thecloud network flowoptimization framework to support queueing-delay-aware orchestration of distributed AI applications over edge-cloud infrastructures. We introduce two execution models, Guaranteed-Resource (GR) and Shared-Resource (SR), that more accurately capture how computation and communication delays emerge from system-level resource constraints. These models incorporate M/M/1 and M/G/1 queue dynamics to represent dedicated and shared resource usage, respectively. The resulting optimization problem is non-convex due to the non-linear delay terms. To overcome this, we develop SPARQ, an iterative approximation algorithm that decomposes the problem into two convex sub-problems, enabling joint optimization of service placement, routing, and resource allocation under nonlinear delay constraints. The modeling approach is validated against real-world data. Simulation results demonstrate that the SPARQ not only offers a more faithful representation of system delays, but also substantially improves resource efficiency and the overall cost-delay tradeoff compared to existing state-of-the-art methods.

Timely delivery of delay-sensitive information over dynamic, heterogeneous networks is increasingly essential for a range of interactive applications, such as industrial automation, self-driving vehicles, and augmented reality. However, most existing network control solutions target onlyaveragedelay performance, falling short of providing strict End-to-End (E2E) peak latency guarantees. This paper addresses the challenge of reliably delivering packets within application-imposed deadlines by leveraging recent advancements in Multi-Agent Deep Reinforcement Learning (MA-DRL). After introducing the Delay-Constrained Maximum-Throughput (DCMT) dynamic network control problem, and highlighting the limitations of current solutions, we present a novel MA-DRL network control framework that leverages a centralized routing and distributed scheduling architecture. The proposed framework leverages critical networking domain knowledge for the design of effective MA-DRL strategies based on the Multi-Agent Deep Deterministic Policy Gradient (MADDPG) technique, where centralized routing and distributed scheduling agents dynamically assign paths and schedule packet transmissions according to packet lifetimes, thereby maximizing on-time packet delivery. The generality of the proposed framework allows integrating both data-driven Deep Reinforcement Learning (DRL) agents and traditional rule-based policies in order to strike the right balance between performance and learning complexity. Our results confirm the superiority of the proposed framework with respect to traditional stochastic optimization-based approaches and provide key insights into the role and interplay between data-driven DRL agents and new rule-based policies for both efficient and high-performance control of latency-critical services.

Data-intensive augmented information (AgI) services (e.g., metaverse applications such as virtual/augmented reality), designed to deliver highly interactive experiences resulting from the real-time combination of live data-streams and pre-stored digital content, are accelerating the need for distributed compute platforms with unprecedented storage, computation, and communication requirements. To this end, the integrated evolution of next-generation networks (5G/6G) and distributed cloud technologies (mobile/edge/cloud computing) have emerged as a promising paradigm to address the interaction- and resource-intensive nature of data-intensive AgI services. In this paper, we focus on the design of control policies for the joint orchestration of compute, caching, and communication (3C) resources in next-generation 3C networks for the delivery of data-intensive AgI services. We design the first throughput-optimal control policy that coordinates joint decisions around (i) routing paths and processing locations for live data streams, with (ii) cache selection and distribution paths for associated data objects. We then extend the proposed solution to include a max-throughput data placement policy and two efficient replacement policies. Numerical results demonstrate the superior performance obtained via the novel multi-pipeline flow control and 3C resource orchestration mechanisms of the proposed policy, compared with state-of-the-art algorithms that lack full 3C integrated control.

Emerging distributed cloud architectures, e.g., fog and mobile edge computing, are playing an increasingly important role in the efficient delivery of real-time stream-processing applications (also referred to as augmented information services), such as industrial automation and metaverse experiences (e.g., extended reality, immersive gaming). While such applications require processed streams to be shared and simultaneously consumed by multiple users/devices, existing technologies lack efficient mechanisms to deal with their inherent multicast nature, leading to unnecessary traffic redundancy and network congestion. In this paper, we establish a unified framework for distributed cloud network control with generalized (mixed-cast) traffic flows that allows optimizing the distributed execution of the required packet processing, forwarding, and replication operations. We first characterize the enlarged multicast network stability region under the new control framework (with respect to its unicast counterpart). We then design a novel queuing system that allows scheduling data packets according to their current destination sets, and leverage Lyapunov drift-plus-penalty control theory to develop the first fully decentralized, throughput- and cost-optimal algorithm for multicast flow control. Numerical experiments validate analytical results and demonstrate the performance gain of the proposed design over existing network control policies.

Next-generation distributed computing networks (e.g., edge and fog computing) enable the efficient delivery of delay-sensitive, compute-intensive applications by facilitating access to computation resources in close proximity to end users. Many of these applications (e.g., augmented/virtual reality) are also data-intensive: in addition to user-specific (live) data streams, they require access to shared (static) digital objects (e.g., image database) to complete the required processing tasks. When required objects are not available at the servers hosting the associated service functions, they must be fetched from other edge locations, incurring additional communication cost and latency. In such settings, overall service delivery performance shall benefit from jointly optimized decisions around (i) routing paths and processing locations for live data streams, together with (ii) cache selection and distribution paths for associated digital objects. In this paper, we address the problem of dynamic control of data-intensive services over edge cloud networks. We characterize the network stability region and design the first throughput-optimal control policy that coordinates processing and routing decisions for both live and static data-streams. Numerical results demonstrate the superior performance (e.g., throughput, delay, and resource consumption) obtained via the novel multi-pipeline flow control mechanism of the proposed policy, compared with state-of-the-art algorithms that lack integrated stream processing and data distribution control.

The DIWINE project aims to play a salient role in the Smart and Sustainable Agriculture industry by enabling creation of a Digital Twin platform for a vineyard. It is conceived as a disruptive solution based on the use of: Unmanned Aerial Vehicles (UAVs), 5G, edge/cloud computing, Machine Learning (ML) and Artificial Intelligence (AI). The platform leverages key 5G technologies such as 5G New Radio (NR) and Multi Access Edge computing (MEC) to remotely control the UAVs and to transfer captured high-resolution images to the cloud. Moreover, the computational power of MEC and central cloud computing enables the use of ML and AI algorithms to process captured data and transform it into a highly accurate Digital Twin. The winemaker has an immediate and flexible access to the Digital Twin platform and is also able to integrate existing technologies, such as IoT sensors and weather forecasts. DIWINE allows: an efficient management of the vineyard, accurately differentiating the final product, simulating different possible scenarios, and optimizing the farm’s consumption, supporting the winemaker to minimize missed harvests risk, and optimizing profitability.

We are entering a rapidly unfolding future driven by the delivery of real-time computation services, such as industrial automation and augmented reality, collectively referred to as augmented information (AgI) services, over highly distributed cloud/edge computing networks. The interaction intensive nature of AgI services is accelerating the need for networking solutions that provide strict latency guarantees. In contrast to most existing studies that can only characterize average delay performance, we focus on the critical goal of delivering AgI services ahead of corresponding deadlines on a per-packet basis, while minimizing overall cloud network operational cost. To this end, we design a novel queuing system able to track data packets’ lifetime and formalize thedelay-constrained least-cost dynamic network control problem. To address this challenging problem, we first study the setting with average capacity (or resource budget) constraints, for which we characterize the delay-constrained stability region and design a throughput-optimal control policy leveraging Lyapunov optimization theory on an equivalent virtual network. Guided by the same principle, we tackle the peak capacity constrained scenario by developing thereliable cloud network control(RCNC) algorithm, which employs a two-way optimization method to make actual and virtual network flow solutions converge in an iterative manner. Extensive numerical results show the superior performance of the proposed control policy compared with the state-of-the-art cloud network control algorithm, and the value of guaranteeing strict end-to-end deadlines for the delivery of next-generation AgI services.

The timely delivery of resource-intensive and latency-sensitive services (e.g., industrial automation, augmented reality) over distributed computing networks (e.g., mobile edge computing) is drawing increasing attention. Motivated by the insufficiency of average delay performance guarantees provided by existing studies, we focus on the critical goal of delivering next generation real-time services ahead of corresponding deadlines on a per-packet basis, while minimizing overall cloud network resource cost. We introduce a novel queuing system that is able to track data packets’ lifetime and formalize the optimal cloud network control problem with strict deadline constraints. After illustrating the main challenges in delivering packets to their destinations before getting dropped due to lifetime expiry, we construct an equivalent formulation, where relaxed flow conservation allows leveraging Lyapunov optimization to derive a provably near-optimal fully distributed algorithm for the original problem. Numerical results validate the theoretical analysis and show the superior performance of the proposed control policy compared with state-of-the-art cloud network control.

Distributed computing (cloud) networks, e.g., mobile edge computing (MEC), are playing an increasingly important role in the efficient hosting, running, and delivery of real-time stream-processing applications such as industrial automation, immersive video, and augmented reality. While such applications require timely processing of real-time streams that are simultaneously useful for multiple users/devices, existing technologies lack efficient mechanisms to handle their increasingly multicast nature, leading to unnecessary traffic redundancy and associated network congestion. In this paper, we address the design of distributed packet processing, routing, and duplication policies for optimal control of multicast stream-processing services. We present a characterization of the enlarged capacity region that results from efficient packet duplication, and design the first fully distributed multicast traffic management policy that stabilizes any input rate in the interior of the capacity region while minimizing overall operational cost. Numerical results demonstrate the effectiveness of the proposed policy to achieve throughput- and cost-optimal delivery of stream-processing services over distributed computing networks.

Distributed computing networks, tasked with both packet transmission and processing, require the joint optimization of communication and computation resources. We develop a dynamic control policy that determines both routes and processing locations for packets upon their arrival at a distributed computing network. The proposed policy, referred to as Universal Computing Network Control (UCNC), guarantees that packets i) are processed by a specified chain of service functions, ii) follow cycle-free routes between consecutive functions, and iii) are delivered to their corresponding set of destinations via proper packet duplications. UCNC is shown to be throughput-optimal for any mix of unicast and multicast traffic, and is the first throughput-optimal policy for non-unicast traffic in distributed computing networks with both communication and computation constraints. Moreover, simulation results suggest that UCNC yields substantially lower average packet delay compared with existing control policies for unicast traffic.

A full multi-dimensional characterization of the angle of arrival (AoA) has immediate applications to the efficient operation of modern wireless communication systems. In this work, we develop a compressed sensing based method to extract multi-dimensional AoA information exploiting the sparse nature of the signal received by a sensor array. The proposed solution, based on the atomicl0norm, enables accurate gridless resolution of the AoA in systems with arbitrary 3D antenna arrays. Our approach allows characterizing the maximum number of distinct sources (or scatters) that can be identified for a given number of antennas and array geometry. Both noiseless and noisy measurement scenarios are addressed, deriving and evaluating the resolvability of the AoA propagation parameters through a multi-level Toeplitz matrix rank\nolimits-minimization problem. To facilitate the implementation of the proposed solution, we also present a least squares approach regularized by a convex relaxation of the rank\nolimits-minimization problem and characterize its conditions for resolvability.

The geometric block model is a recently proposed generative model for random graphs that is able to capture the inherent geometric properties of many community detection problems, providing more accurate characterizations of practical community structures compared with the popular stochastic block model. Galhotra et al. recently proposed a motif-counting algorithm for unsupervised community detection in the geometric block model that is proved to be near-optimal. They also characterized the regimes of the model parameters for which the proposed algorithm can achieve exact recovery. In this work, we initiate the study of active learning in the geometric block model. That is, we are interested in the problem of exactly recovering the community structure of random graphs following the geometric block model under arbitrary model parameters, by possibly querying the labels of a limited number of chosen nodes. We propose two active learning algorithms that combine the use of motif-counting with two different label query policies. Our main contribution is to show that sampling the labels of a vanishingly small fraction of nodes (sub-linear in the total number of nodes) is sufficient to achieve exact recovery in the regimes under which the state-of-the-art unsupervised method fails. We validate the superior performance of our algorithms via numerical simulations on both real and synthetic datasets.

As mobile edge computing (MEC) finds widespread use for relieving the computational burden of compute- and interaction-intensive applications on end user devices, understanding the resulting delay and cost performance is drawing significant attention. While most existing works focus on single-task offloading in single-hop MEC networks, next generation applications (e.g., industrial automation, augmented/virtual reality) require advance models and algorithms for dynamic configuration of multi-task services over multi-hop MEC networks. In this work, we leverage recent advances in dynamic cloud network control to provide a comprehensive study of the performance of multi-hop MEC networks, addressing the key problems of multi-task offloading, timely packet scheduling, and joint computation and communication resource allocation. We present a fully distributed algorithm based on Lyapunov control theory that achieves throughput-optimal performance with delay and cost guarantees. Simulation results validate our theoretical analysis and provide insightful guidelines on the interplay between communication and computation resources in MEC networks.

Semi-supervised classification, one of the most prominent fields in machine learning, studies how to combine the statistical knowledge of the often abundant unlabeled data with the often limited labeled data in order to maximize overall classification accuracy. In this context, the process of actively choosing the data to be labeled is referred to as active learning. In this paper, we initiate the non-asymptotic analysis of the optimal policy for semi-supervised classification with actively obtained labeled data. Considering a general Bayesian classification model, we provide the first characterization of the jointly optimal active learning and semi-supervised classification policy, in terms of the cost-performance tradeoff driven by the label query budget (number of data items to be labeled) and overall classification accuracy. Leveraging recent results on the Rényi Entropy, we derive tight information-theoretic bounds on such active learning cost-performance tradeoff.

Recent advances in network virtualization and programmability enable innovative service models such as Service Chaining (SC), where flows can be steered through a pre-defined sequence of service functions deployed at different cloud locations. A key aspect dictating the performance and efficiency of a SC is its instantiation onto the physical infrastructure. While existing SC Embedding (SCE) algorithms can effectively address the instantiation of SCs consuming computation and communication resources, they lack efficient mechanisms to handle the increasing data-intensive nature of next-generation services. Differently from computation and communication resources, which are allocated in a dedicated per request manner, storage resources can be shared to satisfy multiple requests for the same data. To fill this gap, in this paper, we formulate the data-intensive SCE problem with the goal of minimizing storage, computation, and communication resource costs subject to resource capacity, service chaining, and data sharing constraints. Using a randomized rounding technique that exploits a novel data-aware linear programming decomposition procedure, we develop a multi-criteria approximation algorithm with provable performance guarantees. Evaluation results show that the proposed algorithm achieves near-optimal resource costs with up to 27.8% of the cost savings owed to the sharing of the data.

The multi-version coding problem is a recently formulated information-theoretic framework to study the storage cost of consistent key-value data stores. Previous work on multi-version coding considered a completely decentralized asynchronous system where the nodes (servers) are not aware of which updates (versions) of the data are received by the other nodes. In this paper, we relax this assumption and study a system where a node acquires side information of the versions propagated to some other nodes based on the network topology. Specifically, we study a storage system with n nodes over a graph that stores ν totally ordered versions of an object (message). Each node receives a subset of these ν versions. A node is aware of which versions that were received by its neighbors in the network graph. Our code constructions show that the side information can result in a better storage cost as compared with the case where the nodes do not exchange side information for some regimes at the expense of the additional latency and the negligible communication overhead of exchanging the side information. Through an information-theoretic converse, we identify surprising scenarios where exchanging tremendous amount of side information does not reduce the storage cost. Finally, we present a case study over Amazon web services (AWS) that demonstrates the potential storage cost reductions of our code constructions.

This paper studies the fundamental limits of content delivery in a cache-aided broadcast network for correlated content generated by a discrete memoryless source with arbitrary joint distribution. Each receiver is equipped with a cache of equal capacity, and the requested files are delivered over a shared error-free broadcast link. A class of achievable correlation-aware schemes based on a two-step source coding approach is proposed. Library files are first compressed, and then cached and delivered using a combination of multiple-request caching schemes that are agnostic to the content correlations. The first step uses Gray-Wyner source coding to represent the library via private descriptions and descriptions that are common to more than one file. The second step then becomes a multiple-request caching problem, where the demand structure is dictated by the configuration of the compressed library, and it is interesting in its own right. The performance of the proposed two-step scheme is evaluated by comparing its achievable rate with a lower bound on the optimal peak and average rate-memory trade-offs in a two-file multiple-receiver network, and in a three-file two-receiver network. Specifically, in a network with two files and two receivers, the achievable rate matches the lower bound for a significant memory regime and it is within half of the conditional entropy of files for all other memory values. In the three-file two-receiver network, the two-step strategy achieves the lower bound for large cache capacities, and it is within half of the joint entropy of two of the sources conditioned on the third one for all other cache sizes.

The proliferation of innovative mobile services such as augmented reality, networked gaming, and autonomous driving has spurred a growing need for low-latency access to computing resources that cannot be met solely by existing centralized cloud systems. Mobile Edge Computing (MEC) is expected to be an effective solution to meet the demand for low-latency services by enabling the execution of computing tasks at the network edge, in proximity to the end-users. While a number of recent studies have addressed the problem of determining the execution of service tasks and the routing of user requests to corresponding edge servers, the focus has primarily been on the efficient utilization of computing resources, neglecting the fact that non-trivial amounts of data need to be pre-stored to enable service execution, and that many emerging services exhibit asymmetric bandwidth requirements. To fill this gap, we study the joint optimization of service placement and request routing in dense MEC networks with multidimensional constraints. We show that this problem generalizes several well-known placement and routing problems and propose an algorithm that achieves close-to-optimal performance using a randomized rounding technique. Evaluation results demonstrate that our approach can effectively utilize available storage, computation, and communication resources to maximize the number of requests served by low-latency edge cloud servers.

Caching at the wireless edge can be used to keep up with the increasing demand for high-definition wireless video streaming. By prefetching popular content into memory at wireless access points or end-user devices, requests can be served locally, relieving strain on expensive backhaul. In addition, using network coding allows the simultaneous serving of distinct cache misses via common coded multicast transmissions, resulting in significantly larger load reductions compared to those achieved with traditional delivery schemes. Most prior works simply treat video content as fixed-size files that users would like to fully download. This work is motivated by the fact that video can be coded in a scalable fashion and that the decoded video quality depends on the number of layers a user receives in sequence. Using a Gaussian source model, caching and coded delivery methods are designed to minimize the squared error distortion at end-user devices in a rate-limited caching network. The framework is very general and accounts for heterogeneous cache sizes, video popularities and user-file play-back qualities. As part of the solution, a new decentralized scheme for lossy cache-aided delivery subject to preset user distortion targets is proposed, which further generalizes prior literature to a setting with file heterogeneity.

Real-time stream-processing (RTSP) services, such as telepresence, augmented reality, and real-time computer vision, allow end users to consume personalized media streams that result from the real-time processing of live sources via possibly multiple service functions (or stream processing operators) distributed throughout a cloud network. We consider the problem of optimizing the distribution of RTSP services over a cloud network, which requires the placement of stream processing operators, the routing of streams through the appropriate sequence of operators and the associated allocation of cloud and network resources. We show that existing formulations based on virtual network embedding cannot capture key features of RTSP services such as flow/function replication, and provide a new cloud network flow based formulation that captures arbitrary function and flow chaining, scaling, and replication. We then design two polynomial-time algorithms with bi-criteria approximation guarantees. To the best of our knowledge, these are the first approximation algorithms for the optimization of distributed computing services with arbitrary function/flow chaining, scaling, and replication. We finally illustrate the performance of our algorithms via simulations in practical cloud network settings.

The proliferation of innovative mobile services such as augmented reality, networked gaming, and autonomous driving has spurred a growing need for low-latency access to computing resources that cannot be met solely by existing centralized cloud systems. Mobile Edge Computing (MEC) is expected to be an effective solution to meet the demand for low-latency services by enabling the execution of computing tasks at the network-periphery, in proximity to end-users. While a number of recent studies have addressed the problem of determining the execution of service tasks and the routing of user requests to corresponding edge servers, the focus has primarily been on the efficient utilization of computing resources, neglecting the fact that non-trivial amounts of data need to be stored to enable service execution, and that many emerging services exhibit asymmetric bandwidth requirements. To fill this gap, we study the joint optimization of service placement and request routing in MEC-enabled multi-cell networks with multidimensional (storage-computation-communication) constraints. We show that this problem generalizes several problems in literature and propose an algorithm that achieves close-to-optimal performance using randomized rounding. Evaluation results demonstrate that our approach can effectively utilize the available resources to maximize the number of requests served by low-latency edge cloud servers.

Network virtualization and programmability allow operators to deploy a wide range of services over a common physical infrastructure and elastically allocate cloud and network resources according to changing requirements. While the elastic reconfiguration of virtual resources enables dynamically scaling capacity in order to support service demands with minimal operational cost, reconfiguration operations make resources unavailable during a given time period and may incur additional cost. In this paper, we address the dynamic cloud network control problem under non-negligible reconfiguration delay and cost. We show that while the capacity region remains unchanged regardless of the reconfiguration delay/cost values, a reconfiguration-agnostic policy may fail to guarantee throughput-optimality and minimum cost under nonzero reconfiguration delay/cost. We then present an adaptive dynamic cloud network control policy that allows network nodes to make local flow scheduling and resource allocation decisions while controlling the frequency of reconfiguration in order to support any input rate in the capacity region and achieve arbitrarily close to minimum cost for any finite reconfiguration delay/cost values.

Distributed computing networks, tasked with both packet transmission and processing, require the joint optimization of communication and computation resources. We develop a dynamic control policy that determines both routes and processing locations for packets upon their arrival at a distributed computing network. The proposed policy, referred to as Universal Computing Network Control (UCNC), guarantees that packets i) are processed by a specified chain of service functions, ii) follow cycle-free routes between consecutive functions, and iii) are delivered to their corresponding set of destinations via proper packet duplications. UCNC is shown to be throughput-optimal for any mix of unicast and multicast traffic, and is the first throughput-optimal policy for non-unicast traffic in distributed computing networks with both communication and computation constraints. Moreover, simulation results suggest that UCNC yields substantially lower average packet delay compared with existing control policies for unicast traffic.

In applications of storage systems to modern key-value stores, the stored data is highly dynamic due to frequent updates from the system write clients. The multi-version coding problem has been formulated to study the cost of storing dynamic data in asynchronous distributed storage systems. In this problem, previous work considered a completely decentralized system where a server is not aware of which versions of the data are received by the other servers. In this paper, we relax this assumption and study a system where a server may acquire side information of the versions propagated to some other servers. In particular, we study a storage system with n servers that store v totally ordered independent versions of a message. Each server receives a subset of theseνversions that defines the state of that server. Assuming that the servers are distributed in a ring, a server is aware of which versions have been received by itsh-hop neighbors. If the server is aware of the states of (n- 2) other servers, we show that this side information can result in a better storage cost as compared with the case where there is no side information. Through an information-theoretic converse, we identify scenarios where, even if the server is aware of the states of (n-3) /2 other servers, the side information may not help in improving the worst-case storage cost beyond the case where servers have no side information.

We study cloud resource control in the global-local distributed cloud infrastructure. We firstly model and formulate the problem while capturing the multiple challenges such as the inter-dependency between resources and the uncertainty in the inputs. We then propose a novel online algorithm which, via the regularization technique, decouples the original problem into a series of subproblems for individual time slots and solves both the subproblems and the original problem over every prediction time window to jointly make resource allocation decisions. Compared against the offline optimum with accurate inputs, our approach maintains a provable parameterized worst-case performance gap with only inaccurate inputs under certain conditions. Finally, we conduct evaluations with large-scale, real-world data traces and show that our solution outperforms existing methods and works efficiently with near-optimal cost in practice.

Cache-aided coded multicast leverages side information at wireless edge caches to efficiently serve multiple unicast demands via common multicast transmissions, leading to load reductions that are proportional to the aggregate cache size. However, the increasingly dynamic, unpredictable, and personalized nature of the content that users consume challenges the efficiency of existing caching-based solutions in which only exact content reuse is explored. This paper generalizes the cache-aided coded multicast problem to specifically account for the correlation among content files, such as, for example, the one between updated versions of dynamic data. It is shown that: 1) caching content pieces based on their correlation with the rest of the library and 2) jointly compressing requested files using cached information as references during delivery, can provide load reductions that go beyond those achieved with existing schemes. This is accomplished via the design of a class of correlation-aware achievable schemes, shown to significantly outperform the state-of-the-art correlation-unaware solutions. Our results show that as we move towards real-time and/or personalized media dominated services, where exact cache hits are almost non-existent but updates can exhibit high levels of correlation, network cached information can still be useful as references for network compression.

Augmented information (AgI) services allow users to consume information that results from the execution of a chain of service functions that process source information to create real-time augmented value. Applications include real-time analysis of remote sensing data, real-time computer vision, personalized video streaming, and augmented reality, among others. We consider the problem of optimal distribution of AgI services over a wireless computing network, in which nodes are equipped with both communication and computing resources. We characterize the wireless computing network capacity region and design a joint flow scheduling and resource allocation algorithm that stabilizes the underlying queuing system while achieving a network cost arbitrarily close to the minimum, with a tradeoff in network delay. Our solution captures the unique chaining and flow scaling aspects of AgI services while exploiting the use of the broadcast approach coding scheme over the wireless channel.

In an augmented information (Agi) service, users consume information that results from the execution of a chain of service functions that process source information to create real-time augmented value. Applications may include real-time analysis of remote sensing data, real-time computer vision, personalized video streaming, and augmented reality, among others. We consider the problem of optimal distribution of AgI services over a wireless computing network, in which nodes are equipped with both communication and computing resources. We characterize the wireless computing network capacity region and design a joint flow scheduling and resource allocation algorithm that stabilizes the underlying queuing system while achieving arbitrarily close to minimum network cost, with a tradeoff in network delay. Our solution captures the unique chaining and flow scaling aspects of AgI services, while exploiting the use of the broadcast approach over the wireless channel.

Distributed cloud networking builds on network functions virtualization (NFV) and software defined networking (SDN) to enable the deployment of network services in the form of elastic virtual network functions (VNFs) instantiated over general purpose servers at distributed cloud locations. We address the design of fast approximation algorithms for the NFV service distribution problem (NSDP), whose goal is to determine the placement of VNFs, the routing of service flows, and the associated allocation of cloud and network resources that satisfy client demands with minimum cost. We show that in the case of load-proportional costs, the resulting fractional NSDP can be formulated as a multi-commodity-chain flow problem on a cloud-augmented graph, and design a queue-length based algorithm, named QNSD, that provides an O(ε) approximation in time O (1/ε). We then address the case in which resource costs are a function of the integer number of allocated resources and design a variation of QNSD that effectively pushes for flow consolidation into a limited number of active resources to minimize overall cloud network cost.

This paper studies the fundamental limits of caching in a network with two receivers and two files generated by a two-component discrete memoryless source with arbitrary joint distribution. Each receiver is equipped with a cache of equal capacity, and the requested files are delivered over a shared error-free broadcast link. First, a lower bound on the optimal peak rate-memory trade-off is provided. Then, in order to leverage the correlation among the library files to alleviate the load over the shared link, a two-step correlation-aware cache-aided coded multicast (CACM) scheme is proposed. The first step uses Gray-Wyner source coding to represent the library via one common and two private descriptions, such that a second correlation-unaware multiple-request CACM step can exploit the additional coded multicast opportunities that arise. It is shown that the rate achieved by the proposed two-step scheme matches the lower bound for a significant memory regime and it is within half of the conditional entropy for all other memory values.

We consider the canonical shared link caching network formed by a source node, hosting a library of m information messages (files), connected via a noiseless multicast link to n user nodes, each equipped with a cache of size M files. Users request files independently at random according to an a-priori known demand distribution q. A coding scheme for this network consists of two phases: cache placement and delivery. The cache placement is a mapping of the library files onto the user caches that can be optimized as a function of the demand statistics, but is agnostic of the actual demand realization. After the user demands are revealed, during the delivery phase the source sends a codeword (function of the library files, cache placement, and demands) to the users, such that each user retrieves its requested file with arbitrarily high probability. The goal is to minimize the average transmission length of the delivery phase, referred to as rate (expressed in channel symbols per file). In the case of deterministic demands, the optimal min-max rate has been characterized within a constant multiplicative factor, independent of the network parameters. The case of random demands was previously addressed by applying the order-optimal min-max scheme separately within groups of files requested with similar probability. However, no complete characterization of order-optimality was previously provided for random demands under the average rate performance criterion. In this paper, we consider the random demand setting and, for the special yet relevant case of a Zipf demand distribution, we provide a comprehensive characterization of the order-optimal rate for all regimes of the system parameters, as well as an explicit placement and delivery scheme achieving order-optimal rates. We present also numerical results that confirm the superiority of our scheme with respect to previously proposed schemes for the same setting.

The problem of dynamic resource allocation for service provisioning in multi-tier distributed clouds is particularly challenging due to the coexistence of several factors: the need for joint allocation of cloud and network resources, the need for online decision-making under time-varying service demands and resource prices, and the reconfiguration cost associated with changing resource allocation decisions. We study this problem from an online optimization perspective to address all these challenges. We design an online algorithm that decouples the original offline problem over time by constructing a series of regularized subproblems, solvable at each corresponding time slot using the output of the previous time slot. We prove that, without prediction beyond the current time slot, our algorithm achieves a parameterized competitive ratio for arbitrarily dynamic workloads and resource prices. If prediction is available, we demonstrate that existing prediction-based control algorithms lack worst case performance guarantees for our problem, and we design two novel predictive control algorithms that inherit the theoretical guarantees of our online algorithm, while exhibiting improved practical performance. We conduct evaluations in a variety of settings based on real-world dynamic inputs and show that, without prediction, our online algorithm achieves up to nine times total cost reduction compared with the sequence of greedy one-shot optimizations and at most three times the offline optimum; with moderate predictions, our control algorithms can achieve two times total cost reduction compared with existing prediction-based algorithms.

One of the main challenges for continued wireless capacity growth is the difficulty in exploiting the multicast nature of the wireless medium: wireless end points rarely experience the same channel conditions or access the same content at the same time. In this paper, we present and analyze a novel wireless video delivery paradigm based on the combined use of channel-aware caching and coded multicasting that allows simultaneously serving multiple cache-enabled access points that may be requesting different content and experiencing different channel conditions. To this end, we reformulate the caching-aided coded multicast problem as a joint source-channel coding problem and design an achievable scheme that preserves the cache-enabled multiplicative throughput gains of the error-free scenario, by guaranteeing per-receiver (access point) rates unaffected by the presence of receivers with worse channel conditions.

Distributed cloud networking enables the deployment of network services in the form of interconnected virtual network functions instantiated over general purpose hardware at multiple cloud locations distributed across the network. The service distribution problem is to find the placement of virtual functions and the routing of network flows that meet a given set of demands with minimum cost. In this paper, we address the design of distributed online solutions that drive local routing, processing, and resource allocation decisions while providing global objective guarantees. We present a distributed joint transmission-processing flow scheduling and resource allocation algorithm that stabilizes the underlying cloud network queuing system, while achieving arbitrarily close to minimum average network cost (with a tradeoff in network delay) with probability 1. We further enhance our algorithm with a shortest transmission-plus-processing distance bias that improves the delay performance without compromising throughput or overall cloud network cost. We provide simulation results that confirm our theoretical analysis, illustrate the effect of the shortest transmission-plus-processing distance bias, and demonstrate remarkably good convergence to the optimal cloud network configuration.

In the emerging edge computing paradigm, small-scale highly distributed edge clouds are on the service path between end users and conventional large-scale clouds at the Internet core. A crucial problem that needs to be addressed in order to drive cost and performance in this multi-tier distributed infrastructure is the dynamic and joint allocation of cloud and network resources, which is particularly challenging due to the coexistence of several factors: the reconfiguration cost associated to changing resource allocation decisions over time, the constantly varying and often unpredictable nature of service demands, as well as the heterogeneity of distributed resources. We study the problem of resource allocation and reconfiguration in the multi-tier resource pool from an online optimization perspective that addresses all the challenges above. Our approach decouples the original problem over time by constructing a series of subproblems that are solvable at each corresponding time slot using the output of the previous time slot. Via solid formal analysis, we prove that, without any lookahead beyond the current time slot, our online algorithm provides a solution with a parameterized competitive ratio for any arbitrarily dynamic workload and operating price. We conduct extensive evaluations in a variety of settings based on a number of clouds and real-world workloads with regular and flash crowd fluctuations, and demonstrate that our online algorithm performs well in practice, achieving up to 9× total cost reduction than the sequence of one-shot optimizations and at most 3× the offline optimum.

Cache-aided coded multicast leverages side information at wireless edge caches to efficiently serve multiple groupcast demands via common multicast transmissions, leading to load reductions that are proportional to the aggregate cache size. However, the increasingly unpredictable and personalized nature of the content that users consume challenges the efficiency of existing caching-based solutions in which only exact content reuse is explored. This paper generalizes the cache-aided coded multicast problem to a source compression with distributed side information problem that specifically accounts for the correlation among the content files. It is shown how joint file compression during the caching and delivery phases can provide load reductions that go beyond those achieved with existing schemes. This is accomplished through a lower bound on the fundamental rate-memory trade-off as well as a correlation-aware achievable scheme, shown to significantly outperform state-of-the-art correlation-unaware solutions, while approaching the limiting rate-memory trade-off.

The impact of the Internet of Things (IoT) on the evolution toward next generation smart environments (e.g., smart homes, buildings, and cities) will largely depend on the efficient integration of IoT and cloud computing technologies. With the predicted explosion in the number of connected devices and IoT services, current centralized cloud architectures, which tend to consolidate computing and storage resources into a few large data centers, will inevitably lead to excessive network load, end-to-end service latencies, and overall power consumption. Thanks to recent advances in network virtualization and programmability, highly distributed cloud networking architectures are a promising solution to efficiently host, manage, and optimize next generation IoT services in smart environments. In this paper, we mathematically formulate the service distribution problem (SDP) in IoT-Cloud networks, referred to as the IoT-CSDP, as a minimum cost mixed-cast flow problem that can be efficiently solved via linear programming. We focus on energy consumption as the major driver of today's network and cloud operational costs and characterize the heterogeneous set of IoT-Cloud network resources according to their associated sensing, computing, and transport capacity and energy efficiency. Our results show that, when properly optimized, the flexibility of IoT-Cloud networks can be efficiently exploited to deliver a wide range of IoT services in the context of next generation smart environments, while significantly reducing overall power consumption.

Future Internet usage will be dominated by the consumption of a rich variety of online multimedia services accessed from an exponentially growing number of multimedia capable mobile devices. As such, future Internet designs will be challenged to provide solutions that can deliver bandwidth-intensive delay-sensitive on-demand video-based services over increasingly crowded and bandwidth-limited wireless access networks. One of the main reasons for the bandwidth stress facing wireless network operators is the difficulty to exploit the multicast nature of the wireless medium when wireless users or access points rarely experience the same channel conditions or access the same content at the same time. In this paper, we present and analyze a novel wireless video delivery paradigm based on the combined use of channel-aware caching and coded multicasting that allows simultaneously serving multiple cache-enabled receivers that may be requesting different content and experiencing different channel conditions. To this end, we reformulate the caching-aided coded multicast problem as a joint source-channel coding problem and design an achievable scheme that preserves the cache-enabled multiplicative throughput gains of the error-free scenario, by guaranteeing per-receiver rates unaffected by the presence of receivers with worse channel conditions.

We study a noiseless broadcast link serving K users whose requests arise from a library of N files. Every user is equipped with a cache of size M files each. It has been shown that by splitting all the files into packets and placing individual packets in a random independent manner across all the caches prior to any transmission, at most N/M file transmissions are required for any set of demands from the library. The achievable delivery scheme involves linearly combining packets of different files following a greedy clique cover solution to the underlying index coding problem. This remarkable multiplicative gain of random placement and coded delivery has been established in the asymptotic regime when the number of packets per file F scales to infinity. The asymptotic coding gain obtained is roughly t = K M/N. In this paper, we initiate the finite-length analysis of random caching schemes when the number of packets F is a function of the system parameters M, N, and K. Specifically, we show that the existing random placement and clique cover delivery schemes that achieve optimality in the asymptotic regime can have at most a multiplicative gain of 2 even if the number of packets is exponential in the asymptotic gain t = K(M/N). Furthermore, for any clique cover-based coded delivery and a large class of random placement schemes that include the existing ones, we show that the number of packets required to get a multiplicative gain of (4/3)g is at least O((g/K)(N/M)g-1). We design a new random placement and an efficient clique cover-based delivery scheme that achieves this lower bound approximately. We also provide tight concentration results that show that the average (over the random placement involved) number of transmissions concentrates very well requiring only a polynomial number of packets in the rest of the system parameters.

We consider the problem of efficient content delivery over networks in which individual nodes are equipped with content caching capabilities. We present a flexible methodology for the design of cooperative, decentralized caching strategies that can adapt to real-time changes in regional content popularity. This design methodology makes use of a recently proposed reduced consensus optimization scheme, in which a number of networked agents cooperate in locating the optimum of the sum of their individual, privately known objective functions. The outcome of the design is a set of dynamic update rules that stipulate how much and which portions of each content piece an individual network node ought to cache. In implementing these update rules, the nodes achieve a collectively optimal caching configuration through nearest-neighbor interactions and measurements of local content request rates only. Moreover, individual nodes need not be aware of the overall network topology or how many other nodes are on the network. The desired caching behavior is encoded in the design of individual nodes' costs and can incorporate a variety of network performance criteria. Using the proposed methodology, we develop a set of content-caching update rules designed to minimize the energy consumption of the network as a whole by dynamically trading off transport and caching energy costs in response to changes in content demand.

The cloud service distribution problem (CSDP) is to find the placement of both content and virtual cloud service functions (vCSFs) over a distributed cloud network platform, that meets user requests, satisfies network resource capacities and minimizes overall network cost. We formulate the CSDP as a minimum cost mixed-cast flow problem in which cloud services are represented by a service graph that encodes the relationship between input and output information flows via the virtual functions that create them. As a result, the CSDP can be efficiently formulated using only linear constraints and solved via integer linear programming (ILP). Our solution jointly optimizes the use of compute, storage and transport resources in arbitrary cloud network topologies, and is able to capture flexible service chaining, resource consolidation savings, unicast and multicast delivery, and latency constraints. We further provide conditions for which a relaxed version of the presented ILP leads to optimal polynomial-time solutions. We finally present results for an illustrative sample of cloud services that show the advantage of optimizing the placement of content and vCSFs over a programmable distributed cloud network.

Coded multicasting has been shown to improve the caching performance of content delivery networks with multiple caches downstream of a common multicast link. However, the schemes that have been shown to achieve order-optimal performance require content items to be partitioned into a number of packets that grows exponentially with the number of users [1]. In this paper, we first extend the analysis of the order-optimal multiple-groupcast coded multicasting scheme in [2] to the case of heterogeneous cache sizes and demand distributions, providing an achievable scheme and an upper bound on the optimal performance when the number of packets goes to infinity. We then show that the scheme achieving this upper bound can very quickly loose its promising multiplicative caching gain for finite content packetization. To overcome this limitation, we design a novel polynomial-time algorithm based on greedy local graph-coloring that, while keeping the same content packetization, recovers a significant part of the multiplicative caching gain. Our results show that the achievable schemes proposed to date to quantify the fundamental limiting performance, must be properly designed for practical regimes of finite content packetization.

The capacity of caching networks has received considerable attention in the past few years. A particularly studied setting is the shared link caching network, in which a single source with access to a file library communicates with multiple users, each having the capability to store segments (packets) of the library files, over a shared multicast link. Each user requests one file from the library according to a common demand distribution and the server sends a coded multicast message to satisfy all users at once. The problem consists of finding the smallest possible average codeword length to satisfy such requests. In this paper, we consider the generalization to the case where each user places L ≥ 1 independent requests according to the same common demand distribution. We propose an achievable scheme based on random vector (packetized) caching placement and multiple groupcast index coding, shown to be order-optimal in the asymptotic regime in which the number of packets per file B goes to infinity. We then show that the scalar (B = 1) version of the proposed scheme can still preserve order-optimality when the number of per-user requests L is large enough. Our results provide the first order-optimal characterization of the shared link caching network with multiple random requests, revealing the key effects of L on the performance of caching-aided coded multicast schemes.

Consider a network of prosumers of media content in which users dynamically create and request content objects. The request process is governed by the objects' popularity, which may vary across network regions and over time. In order to meet user requests, content objects can be stored and transported over the network, characterized by the capacity and efficiency of its storage and transport resources. The energy-efficient dynamic content distribution problem aims at finding the evolution of the network configuration, in terms of the placement and routing of content objects over time, that meets user requests, satisfies network resource capacities and minimizes overall energy use. We present 1) an information-centric linear programming formulation for the energy efficient dynamic content distribution problem that captures multicasting and caching over the network, per-object system dynamics, and delivery deadlines; 2) an offline solution that characterizes the minimum energy use achievable with global knowledge of user requests and network resources; and 3) an efficient distributed online solution that allows network nodes to make caching decisions based on their local estimate of the global energy benefit. Using a custom-built content distribution network simulator as well as a real prototype implementation in an information-centric networking testbed, we show the significant energy savings that can be obtained via the efficient and lightweight cache cooperation induced by our service and energy aware distributed online solution with respect to state of the art approaches.

We consider the problem of designing content-caching strategies for the energy-efficient delivery of content such as video, over an internet-style network. We propose a method for the design of decentralized caching strategies that can adapt to real-time changes in regional content popularity. This design method is based on a recently proposed reduced consensus-optimization scheme wherein a number of agents networked over a general mesh topology cooperate in locating the optimum of the sum of their individual, privately known objective functions. The agents (i.e. network nodes with caching capabilities) achieve the collectively optimal caching configuration via nearest-neighbor interactions and measurements of local content request rates only. The caching behavior of individual nodes, which dynamically trades transport and caching energy costs in response to fluctuations in content demand, is designed to optimize the performance of the network as a whole.

In this paper, we study the efficacy of error control schemes for energy-efficient reliable delivery of large files (hundreds of GBs) over core optical networks. Specifically, we examine two schemes: automatic repeat request (ARQ), and hybrid ARQ (i.e. ARQ combined with forward error correction (FEC) capability). We focus on Reed-Solomon (RS) FEC codes (in hybrid ARQ) and propose a new model, incorporating different block sizes as well as code error-correction capability, to estimate the energy consumption for performing encoding and decoding operations in optical networks. The model considers the impact of varying pre-FEC bit-error rates (BER) of the optical channel, and the signal processing blocks used to implement RS codes. Our results show that when the pre-FEC channel BER is in excess of 10-5, hybrid ARQ offers better performance than ARQ in terms of energy efficiency. However, both hybrid ARQ and ARQ have similar performance under lower BER.

Consider a content delivery network in which storage and transport resources, characterized by their capacity and cost (e.g., energy) efficiency, are used to meet users' content object requests. The goal is to find the evolution of the objects being stored and transported by the network resources that meets user requests, satisfies network resource capacities and minimizes overall network cost. We first present a constructive offline solution that provides the maximum network efficiency (or minimum cost per object delivered) that can be achieved by dynamically exploiting network-coded caching and multicasting under arbitrary time-varying demands. We refer to the solution scheme as a dynamic network-coded caching-aided multicast (NCCAM) scheme, and illustrate it in a 6-node butterfly network. We then consider a single time period in which each user requests an arbitrary subset of content objects. We formulate the problem as a network coding problem on a caching-augmented graph and show that under uniform demand, random linear coded caching and multicasting is sufficient for achieving minimum cost caching-aided multicast. For the arbitrary demand scenario, we provide the transport-storage-popularity tradeoff of a polynomial-time solution that uses uncoded caching according to object popularity and random linear coded transmission. We show that while for skewed Zipf object popularity such a simple scheme achieves close to optimal performance, as the Zipf parameter approaches zero (uniform popularity), significant cost reductions can be obtained by optimizing the transport configuration at the expense of increased computational complexity.

Consider a network of prosumers of media content in which users dynamically create and request content objects. The request process is governed by the objects' popularity and varies across network regions and over time. In order to meet user requests, content objects can be stored and transported over the network, characterized by the capacity and energy efficiency of the storage and transport resources. The energy efficient dynamic in-network caching problem aims at finding the evolution of the network configuration, in terms of the content objects being cached and transported over each network element at any given time, that meets user requests, satisfies network resource capacities and minimizes overall energy use. We provide 1) an information-centric optimization framework for the energy efficient dynamic in-network caching problem, 2) an offline solution, EE-OFD, based on an integer linear program (ILP) that obtains the maximum efficiency gains that can be achieved with global knowledge of user requests and network resources, and 3) an efficient fully distributed online solution, EEOND, that allows network nodes to make local caching decisions based on their current estimate of the global energy benefit. Our solutions take into account the network heterogeneity, in terms of capacity, energy efficiency and content popularity, and adapt to changing network conditions minimizing overall energy use.

In-network processing of media streams will be necessary in order to meet the personalization, interactive, and real time requirements of future video centric media services. Using multi-view video (MVV) streaming as an example, we investigate the energy tradeoff between video processing and transport for the delivery of personalized media services. We focus on evaluating the energy benefit of distributed vs. centralized processing architectures. We provide solutions for the relative energy efficiency regions as a function of the user viewing preferences and the processing-transport efficiency ratio. Our results show that a small number of requests and a homogeneous interest among viewing regions favors the centralized processing of personalized video streams and multicast transport to end users, while a larger number of requests and a heterogeneous interest favors the processing of personalized views at a distributed subset of nodes in the network.

We examine the basic energy tradeoffs between video transport and video processing for services such as multi-view video (MVV) streaming, where multiple media streams are combined and processed to create an immersive and personalized user experience. We analyze and compare the energy efficiency of different architectural options for the location of video processing functions and illustrate how the architecture of choice is influenced by the network topology, the users' view preferences, and the relative transport-processing energy efficiency. We provide an integer linear programming formulation for the energy efficient functional resource allocation problem, which we show it can be solved as a linear program, and an easily implementable algorithm that generates optimal solutions in polynomial time.

In this paper, we present new models and algorithms for control and optimization of a class of next generation communication networks: Hierarchical Heterogeneous Wireless Networks (HHWNs), under real-world physical constraints. Two biology-inspired techniques, a Flocking Algorithm (FA) and a Particle Swarm Optimizer (PSO), are investigated in this context. Our model is based on the control framework at the physical layer presented previously by the authors. We first develop a nonconvex mathematical model for HHWNs. Second, we propose a new FA for self-organization and control of the backbone nodes in an HHWN by collecting local information from end users. Third, we employ PSO, a widely used artificial intelligence algorithm, to directly optimize the HHWN by collecting global information from the entire system. A comprehensive evaluation measurement during the optimization process is developed. In addition, the relationship between HHWN and FA and the comparison of FA and PSO are discussed, respectively. Our novel framework is examined in various dynamic scenarios. Experimental results demonstrate that FA and PSO both outperform current algorithms for the self-organization and optimization of HHWNs while showing different characteristics with respect to convergence speed and quality of solutions.