The Function-as-a-Service (FaaS) paradigm has emerged as an evolution of traditional cloud computing services, promising easier development and operations, finer-grained pricing and seamless scalability. With the proliferation of computational capacity at the network edge and across the cloud-to-edge continuum, FaaS adoption has expanded beyond the borders of traditional cloud data centers. However, in such dynamic, distributed and heterogeneous environments, additional challenges arise, including how to deal with load peaks through computational offloading and how to execute functions in a carbon and energy-aware manner. In this paper, we tackle these challenges by introducing an approach to carbon- and Quality of Service (QoS)-aware function offloading based on spatial workload shifting and adaptive selection of function variants (i.e., multiple implementations trading off computational demand, accuracy and energy consumption). Our solution targets a FaaS system spanning the cloud-to-edge continuum hosting users belonging to multiple service classes with diverse QoS requirements. By solving a linear programming problem at run time, our approach determines how to allocate the available resources to optimize the trade-off between carbon emissions and QoS satisfaction. Extensive simulated experiments show that, under the same monetary budget, our approach allows 30% more requests to meet QoS requirements on average compared to a state-of-the-art baseline, with 20% less carbon emissions due to function execution.

Function-as-a-Service (FaaS) paradigm is increasingly attractive to bring the benefits of serverless computing to the edge of the network, besides traditional Cloud data centers. However, FaaS adoption in the emerging Cloud-to-Edge Continuum is challenging, mostly due to geographical distribution and heterogeneous resource availability. This emerging landscape calls for effective strategies to trade off low latency at the edge of the network with Cloud resource richness, taking into account the needs of different functions and users. In this paper, we present QoS-aware offloading policies for serverless functions running in the Cloud-to-Edge continuum. We consider heterogeneous functions and service classes, and aim to maximize utility given a monetary budget for resource usage. Specifically, we introduce a two-level approach, where (i) FaaS nodes rely on a randomized policy to schedule every incoming request according to a set of probability values, and (ii) periodically, a linear programming model is solved to determine the probabilities to use for scheduling. We show by extensive simulation that our approach outperforms alternative approaches in terms of generated utility across multiple scenarios. Moreover, we demonstrate that our solution is computationally efficient and can be adopted in large-scale systems. We also demonstrate the functionality of our approach through a proof-of-concept experiment on an open-source FaaS framework.

Function-as-a-Service (FaaS) has emerged as an evolution of traditional Cloud service models, allowing users to define and execute pieces of codes (i.e., functions) in a serverless manner, with the provider taking care of most operational issues. With the unending growth of resource availability in the Edge-to-Cloud Continuum, there is increasing interest in adopting FaaS near the Edge as well, to better support geo-distributed and pervasive applications. However, as the existing FaaS frameworks have mostly been designed with Cloud in mind, new architectures are necessary to cope with the additional challenges of the Continuum, such as higher heterogeneity, network latencies, limited computing capacity. In this paper, we present an extended version of Serverledge, a FaaS framework designed to span Edge and Cloud computing landscapes. Serverledge relies on a decentralized architecture, where each FaaS node is able to autonomously schedule and execute functions. To take advantage of the computational capacity of the infrastructure, Serverledge nodes also rely on horizontal and vertical function offloading mechanisms. In this work we particularly focus on the design of mechanisms for function offloading and live function migration across nodes. We implement these mechanisms in Serverledge and evaluate their impact and performance considering different scenarios and functions.

The Function-as-a-Service (FaaS) paradigm is increasingly adopted for the development of Cloud-native applications, which especially benefit from the seamless scalability and attractive pricing models of serverless deployments. With the continuous emergence of latency-sensitive applications and services, including Internet-of-Things and augmented reality, it is now natural to wonder whether and how the FaaS paradigm can be efficiently exploited in the Cloud-Edge Continuum, where serverless functions may benefit from reduced network delay between their invoking users and the FaaS platform. In this paper, we illustrate the key challenges that must be faced to effectively deploy serverless functions in the Cloud-Edge Continuum and review recent contributions proposed by the research community towards overcoming those challenges. We also discuss the key issues that currently remain unsolved and highlight a few research opportunities for better support of FaaS in the Compute Continuum.

As the Function-as-a-Service (FaaS) paradigm enjoys growing popularity within Cloud-based systems, there is increasing interest in moving serverless functions towards the Edge, to better support geo-distributed and pervasive applications. However, enjoying both the reduced latency of Edge and the scalability of FaaS requires new architectures and implementations to cope with typical Edge challenges (e.g., nodes with limited computational capacity). While first solutions have been proposed for Edge-based FaaS, including light function sandboxing techniques, we lack a platform with the ability to span both Edge and Cloud and adaptively exploit both. In this paper, we present Serverledge, a FaaS platform designed for the Edge-to-Cloud continuum. Serverledge adopts a decentralized architecture, where function invocation requests can be fully served within Edge nodes. To cope with load peaks, Serverledge also supports vertical (i.e., from Edge to Cloud) and horizontal (i.e., among Edge nodes) computation offloading. Our evaluation shows that Serverledge outperforms Apache OpenWhisk in an Edge-like scenario and has competitive performance with state-of-the-art frameworks optimized for the Edge, with the advantage of built-in support for vertical and horizontal offloading.

Data Stream Processing (DSP) applications analyze data flows in near real-time by means of operators, which process and transform incoming data. Operators handle high data rates running parallel replicas across multiple processors and hosts. To guarantee consistent performance without wasting resources in the face of variable workloads, auto-scaling techniques have been studied to adapt operator parallelism at run-time. However, most of the effort has been spent under the assumption of homogeneous computing infrastructures, neglecting the complexity of modern environments. We consider the problem of deciding both how many operator replicas should be executed and which types of computing nodes should be acquired. We devise heterogeneity-aware policies by means of a two-layered hierarchy of controllers. While application-level components steer the adaptation process for whole applications, aiming to guarantee user-specified requirements, lower-layer components control auto-scaling of single operators. We tackle the fundamental challenge of performance and workload uncertainty, exploiting Bayesian optimization (BO) and reinforcement learning (RL) to devise policies. The evaluation shows that our approach is able to meet users’ requirements in terms of response time and adaptation overhead, while minimizing the cost due to resource usage, outperforming state-of-the-art baselines. We also demonstrate how partial model information is exploited to reduce training time for learning-based controllers.

Cloud-native applications increasingly adopt the microservices architecture, which favors elasticity to satisfy the application performance requirements in face of variable workloads. To simplify the elasticity management, the trend is to create an auto-scaler instance per microservice, which controls its horizontal scalability by using the classic threshold-based policy. Although easy to implement, setting manually the scaling thresholds, which are usually statically-defined on a single metric, may lead to poor scaling decisions when applications are heterogeneous in terms of resource consumption. In this article, we study dynamic multi-metric threshold-based scaling policies, that exploit Reinforcement Learning (RL) to autonomously update the scaling thresholds, one per controlled resource (CPU and memory). The proposed RL approaches (i.e., QL, MB, and DQL Threshold) use different degrees of knowledge about the system dynamics. To model the thresholds’ adaptation actions, we consider two RL-based architectures. In the single-agent architecture, one agent drives the updates of both scaling thresholds. To speed-up the learning, the multi-agent architecture adopts a distinct agent per threshold. Simulation- and prototype-based results show the benefits of the proposed solutions when compared to the state-of-the-art policies and highlight the advantages of multi-agent MB Threshold and DQL Threshold approaches, in terms of deployment objectives and execution times.

The unpredictable variability of Data Stream Processing (DSP) application workloads calls for advanced mechanisms and policies for elastically scaling the processing capacity of DSP operators. Whilst many different approaches have been used to devise policies, most of the solutions have focused on data arrival rate and operator resource utilization as key metrics for auto-scaling. We here show that, under burstiness in the data flows, overly simple characterizations of the input stream can yet lead to very inaccurate performance estimations that affect such policies, resulting in sub-optimal resource allocation.We then present MEAD, a vertical auto-scaling solution that relies on online state-based representation of burstiness to drive resource allocation. We use in particular Markovian Arrival Processes (MAPs), which are composable with analytical queueing models, allowing us to efficiently predict performance at run-time under burstiness. We integrate MEAD in Apache Flink, and evaluate its benefits over simpler yet popular auto-scaling solutions, using both synthetic and real-world workloads. Differently from existing approaches, MEAD satisfies response time requirements under burstiness, while saving up to 50% CPU resources with respect to a static allocation.

The microservice architecture structures an application as a collection of loosely coupled and distributed services. Since application workloads usually change over time, the number of replicas per microservice should be accordingly scaled at run-time. The most widely adopted scaling policy relies on statically defined thresholds, expressed in terms of system-oriented metrics. This policy might not be well-suited to scale multi-component and latency-sensitive applications, which express requirements in terms of response time. In this paper, we present a two-layered hierarchical solution for controlling the elasticity of microservice-based applications. The higher-level controller estimates the microservice contribution to the application performance, and informs the lower-level components. The latter accordingly scale the single microservices using a dynamic threshold-based policy. So, we propose MB Threshold and QL Threshold, two policies that employ respectively model-based and model-free reinforcement learning approaches to learn threshold update strategies. These policies can compute different thresholds for the different application components, according to the desired deployment objectives. A wide set of simulation results shows the benefits and flexibility of the proposed solution, emphasizing the advantages of using dynamic thresholds over the most adopted policy that uses static thresholds.

We consider several Software as a Service (SaaS) providers that offer services using the Cloud resources provided by an Infrastructure as a Service (IaaS) provider which adopts a pay-per-use scheme similar to the Amazon EC2 service, comprising flat, on demand, and spot virtual machine instances. For this scenario, we study the virtual machine provisioning and spot pricing strategies. We consider a two-stage provisioning scheme. In the first stage, the SaaS providers determine the optimal number of required flat and on demand instances. Then, in the second stage, the IaaS provider sells its unused capacity as spot instances for which the SaaS providers compete by submitting a bid. We study two different IaaS provider pricing strategies: the first assumes the IaaS provider sets a unique price; in the second, instead, the IaaS provider can set different prices for different customers. We model the resulting problem as a Stackelberg game. For each pricing scheme, we show the existence of the game equilibrium and provide the solution algorithms. Through numerical evaluation we compare the provisioning and spot price under the two different pricing strategies as function of the system parameters.

Software containers are ever more adopted to manage and execute distributed applications. Indeed, they enable to quickly scale the amount of computing resources by means of horizontal and vertical elasticity. Most of the existing works consider the deployment of containers in centralized data centers. However, to exploit the diffused presence of edge/fog computing resources, we need new solutions that deploy containers while also considering their placement on decentralized resources. In this paper, we present a two-step approach that manages the run-time adaptation of container-based applications deployed over geo-distributed virtual machines. In the first step, our approach exploits Reinforcement Learning (RL) solutions to control the horizontal and vertical elasticity of the containers. In the second step, it addresses the container placement by solving a suitable integer linear programming problem or using a network-aware heuristic. A wide set of simulation results shows the benefits and flexibility of the proposed approach, which can satisfy stringent application requirements expressed in terms of response time percentiles.

Routing solutions for multi-hop underwater wireless sensor networks suffer significant performance degradation as they fail to adapt to the overwhelming dynamics of underwater environments. To respond to this challenge, we propose a new data forwarding scheme where relay selection swiftly adapts to the varying conditions of the underwater channel. Our protocol, termed CARMA for Channel-aware Reinforcement learning-based Multi-path Adaptive routing, adaptively switches between single-path and multi-path routing guided by a distributed reinforcement learning framework that jointly optimizes route-long energy consumption and packet delivery ratio. We compare the performance of CARMA with that of three other routing solutions, namely, CARP, QELAR and EFlood, through SUNSET-based simulations and experiments at sea. Our results show that CARMA obtains a packet delivery ratio that is up to 40% higher than that of all other protocols. CARMA also delivers packets significantly faster than CARP, QELAR and EFlood, while keeping network energy consumption at bay.

In the last few years, a large number of real-time analytics applications rely on the Data Stream Processing (DSP) so to extract, in a timely manner, valuable information from distributed sources. Moreover, to efficiently handle the increasing amount of data, recent trends exploit the emerging presence of edge/Fog computing resources so to decentralize the execution of DSP applications. Since determining the Optimal DSP Placement (for short, ODP) is an NP-hard problem, we need efficient heuristics that can identify a good application placement on the computing infrastructure in a feasible amount of time, even for large problem instances. In this paper, we present several DSP placement heuristics that consider the heterogeneity of computing and network resources; we divide them in two main groups: model-based and model-free. The former employ different strategies for efficiently solving the ODP model. The latter implement, for the problem at hand, some of the well-known meta-heuristics, namely greedy first-fit, local search, and tabu search. By leveraging on ODP, we conduct a thorough experimental evaluation, aimed to assess the heuristics' efficiency and efficacy under different configurations of infrastructure size, application topology, and optimization objectives.

Summary Processing data in a timely manner, data stream processing (DSP) applications are receiving an increasing interest for building new pervasive services. Due to the unpredictability of data sources, these applications often operate in dynamic environments; therefore, they require the ability to elastically scale in response to workload variations. In this paper, we deal with a key problem for the effective runtime management of a DSP application in geo‐distributed environments: We investigate the placement and replication decisions while considering the application and resource heterogeneity and the migration overhead, so to select the optimal adaptation strategy that can minimize migration costs while satisfying the application quality of service (QoS) requirements. We present elastic DSP replication and placement (EDRP), a unified framework for the QoS‐aware initial deployment and runtime elasticity management of DSP applications. In EDRP, the deployment and runtime decisions are driven by the solution of a suitable integer linear programming problem, whose objective function captures the relative importance between QoS goals and reconfiguration costs. We also present the implementation of EDRP and the related mechanisms on Apache Storm. We conduct a thorough experimental evaluation, both numerical and prototype‐based, that shows the benefits achieved by EDRP on the application performance.

Optimal interface selection is a key mobility management issue in heterogeneous wireless networks. Measuring the physical or link level performance on a given wireless access networks does not provide a reliable indication of the IP connectivity, delay, and loss on the (bidirectional) paths from the Mobile Host to the node that is handling the mobility, over different heterogeneous networks. In this paper, we propose, implement, and analyze mechanisms for connectivity check and performance (network delay and packet loss) monitoring over IP access networks. We evaluate the accuracy and timeliness of the performance estimates and provide guidelines for tuning up the parameters. From the implementation perspective, we show that using application level measurements is highly CPU intensive, while a kernel based implementation has comparably a very low CPU usage. The Linux kernel implementation results in an efficient use of batteries in Mobile Hosts and intermediate Mobility Management Nodes can scale up to monitoring thousands of flows. The proposed solutions have been implemented in the context of a specific mobility management solution, but the results are of general applicability. The Linux implementation is available as Open Source.

An ever increasing utility and use of virtualization in various emerging scenarios, e.g.: Cloud Computing, Software Defined Networks, Data Streaming Processing, asks the Infrastructure Providers (InPs) to optimize the allocation of the virtual network requests (VNRs) into a substrate network. In this paper we present a two-stage virtual network embedding (VNE) algorithm, which map first virtual nodes to substrate nodes based on a suitable ranking algorithm and then map link along the shortest paths among the nodes. The key ingredient of our approach is a novel node ranking algorithm, MCRR (Markov Chains with Rewards Ranking), based on Markov Reward Processes, which associates a metric which accounts for and well captures the amount of local resources available in a vicinity of a given node. We have extensively evaluated our algorithm through simulation. Our experiments indicate that our algorithm outperforms previous approaches in terms of lower VNE rejection rate, higher revenues and better resources utilization.

In this paper, we consider an application provider that executes simultaneously periodic long running jobs and needs to ensure a minimum throughput to guarantee QoS to its users; the application provider uses virtual machine (VM) resources offered by an IaaS provider. Aim of the periodic jobs is to compute measures on data collected over a specific time frame. We assume that the IaaS provider offers a pay for only what you use scheme similar to the Amazon EC2 service, comprising on demand and spot VM instances. The former are sold at a fixed price, while the latter are assigned on the basis of an auction. We focus on the bidding decision process by the application provider and model the bidding problem as a Q-Learning problem, taking into account the workloads, the maximum completion times since jobs start, the last checkpoint, and the past spot prices observed. In Q-Learning, a form of model-free Reinforcement Learning, the player is repeatedly faced with a choice among N different actions, which will determine immediate rewards or costs and will influence future evolutions. Through numerical experiments, we analyze the resulting bidding strategy under different scenarios. Our results show the application provider ability to refine its behavior and to determine the best action so to minimize the average cost per job, also taking into account checkpointing issues and QoS constraints.

Fog computing is rapidly changing the distributed computing landscape by extending the Cloud computing paradigm to include wide-spread resources located at the network edges. This diffused infrastructure is well suited for the implementation of data stream processing (DSP) applications, by possibly exploiting local computing resources. Storm is an open source, scalable, and fault-tolerant DSP system designed for locally distributed clusters. We made it suitable to operate in a geographically distributed and highly variable environment; to this end, we extended Storm with new components that allow to execute a distributed QoS-aware scheduler and give self-adaptation capabilities to the system. In this paper we provide a thorough experimental evaluation of the proposed solution using two sets of DSP applications: the former is characterized by a simple topology with different requirements; the latter comprises some well known applications (i.e., Word Count, Log Processing). The results show that the distributed QoS-aware scheduler outperforms the centralized default one, improving the application performance and enhancing the system with runtime adaptation capabilities. However, complex topologies involving many operators may cause some instability that can decrease the DSP application availability.

We present a distributed, integrated medium access control, scheduling, routing and congestion/rate control protocol stack for cognitive radio ad hoc networks (CRAHNs) that dynamically exploits the available spectrum resources left unused by primary licensed users, maximizing the throughput of a set of multi-hop flows between peer nodes. Using a network utility maximization (NUM) formulation, we devise a distributed solution consisting of a set of sub-algorithms for the different layers of the protocol stack (MAC, flow scheduling and routing), which result from a natural decomposition of the problem into sub-problems. Specifically, we show that: 1) The NUM optimization problem can be solved via duality theory in a distributed way, and 2) the resulting algorithms can be regarded as the CRAHN protocols. These protocols combine back-pressure scheduling with a CSMA-based random access with exponential backoffs. Our theoretical findings are exploited to provide a practical implementation of our algorithms using a common control channel for node coordination and a wireless spectrum sensor network for spectrum sensing. We evaluate our solutions through ns-2 MIRACLE-based simulations. Our results show that the proposed protocol stack effectively enables multiple flows among cognitive radio nodes to coexist with primary communications. The CRAHN achieves high utilization of the spectrum left unused by the licensed users, while the impact on their communications is limited to an increase of their packet error rate that is below 1 percent.

In this paper we consider several Software as a Service (SaaS) providers, that offer a set of applications using the Cloud facilities provided by an Infrastructure as a Service (IaaS) provider. We assume that the IaaS provider offers a pay only what you use scheme similar to the Amazon EC2 service, comprising flat, on demand, and spot virtual machine instances. We propose a two stage provisioning scheme. In the first stage, the SaaS providers determine the number of required flat and on demand instances by means of standard optimization techniques. In the second stage the SaaS providers compete, by bidding for the spot instances which are instantiated using the unused IaaS capacity. We assume that the SaaS providers want to maximize a suitable utility function which accounts for both the QoS delivered to their users and the associated cost. The IaaS provider, on the other hand, wants to maximize his revenue by determining the spot prices given the SaaS bids. We model the second stage as a Stackelberg game, and we compute its equilibrium price and allocation strategy by solving a Mathematical Program with Equilibrium Constraints (MPEC) problem. Through numerical evaluation we study the equilibrium solutions as function of the system parameters.

Underwater sensor networks have become an important area of research with many potential practical applications. Given impairments of optical and radio propagation, acoustic communication is used for underwater networking, which translates into variable and long propagation delays, low data rates, long interference ranges and significant fluctuations in terms of link quality over time. A complete characterization of the unique features of the acoustic channel introduces significant complexity both in analytical models and in simulators but is needed for correct characterization of underwater protocols performance. Our objective has been that of designing scalable analytical techniques which are able to derive optimum traffic scheduling and routing for underwater sensor networks while accurately capturing underwater channels features. Specifically the paper presents an analytical model for joint MAC and routing optimization which produces the optimum solution for small to medium scale underwater networks. Scalable, centralized heuristics are then designed, which combine approximate analytical models and scheduling heuristics, and are able to generate solutions close to the optimum. The overall result is a powerful tool to derive benchmark results (upper bounds) for underwater protocol performance and to understand the tradeoffs and performance limits of such systems.

Architecting software systems according to the service-oriented paradigm and designing runtime self-adaptable systems are two relevant research areas in today's software engineering. In this paper, we address issues that lie at the intersection of these two important fields. First, we present a characterization of the problem space of self-adaptation for service-oriented systems, thus providing a frame of reference where our and other approaches can be classified. Then, we present MOSES, a methodology and a software tool implementing it to support QoS-driven adaptation of a service-oriented system. It works in a specific region of the identified problem space, corresponding to the scenario where a service-oriented system architected as a composite service needs to sustain a traffic of requests generated by several users. MOSES integrates within a unified framework different adaptation mechanisms. In this way it achieves greater flexibility in facing various operating environments and the possibly conflicting QoS requirements of several concurrent users. Experimental results obtained with a prototype implementation of MOSES show the effectiveness of the proposed approach.

In this paper, we address the problem of providing a service broker, which offers to prospective users a composite service with a range of different Quality of Service (QoS) classes, with a forward-looking admission control policy based on Markov Decision Processes (MDPs).

Data centers providing modern interactive applications are enriched by autonomous management decision systems that are able to clone and migrate virtual machines, to re-distribute resources or to re-map services in real-time. At the basis of all these decisions, there is the need of a continuous evaluation of the state of system resources and of detecting when some relevant changes are occurring. Unfortunately, the load of interactive applications reaching the system is intrinsically heterogeneous with consequent highly variable effects on the resource behavior emerging from system monitors. Hence, existing algorithms for online detection of state changes are affected by low precision and scarce robustness when they are applied to modern contexts. We propose a novel model for online detection of relevant state changes that combines a filtered representation of the raw measures with adaptive detection rules. Experiments carried out on real and emulated data sets confirm that the proposed model is able to timely signal all relevant state changes, to limit false detections and, even more important, its results are robust in highly variable contexts.

All runtime management decisions in computer and information systems require immediate detection of relevant changes in the state of their resources. This is accomplished by continuously monitoring the performance/utilization of key system resources and by using appropriate statistical tests to detect the occurance of significant state changes. Unfortunately, the complexity of today systems and applications and the unpredictability of user request patterns result in highly variable and non stationary time series which are difficult to analyze. As a consequence, present solutions for detecting state changes at runtime are affected by excessive time delays or false positives. We propose a novel ¿agile¿ runtime detector that solves the delay vs. false positive tradeoff: it is able to detect the relevant state changes as fast as the best reactive models with the lowest percentages of false positives. All evaluations carried out for a large set of scenarios confirm the efficacy and robustness of the proposed model.

Runtime adaptation is recognized as a viable way for a service-oriented system to meet QoS requirements in its volatile operating environment. In this paper we propose a methodology to drive the adaptation of such a system, that integrates within a unified framework different adaptation mechanisms, to achieve a greater flexibility in facing different operating environments and the possibly conflicting QoS requirements of several concurrent users. To determine the most suitable adaptation action(s), the methodology is based on the formulation and solution of a linear programming problem, which is derived from a behavioral model of the system updated at runtime by a monitoring activity. Numerical experiments show the effectiveness of our approach. Besides the methodology, we also present a prototype tool that implements it.

In the service oriented paradigm applications are created as a composition of independently developed Web services. Since the same service may be offered by different providers with different non-functional Quality of Service (QoS) attributes, a selection process is needed to identify the constituent services for a given composite service that best meet the users QoS requirements. In this paper, we consider a broker that offers a composite service with multiple QoS classes to several users each generating a flow of requests over time. We propose a service selection scheme which optimizes the end-to-end aggregated QoS of all incoming flows of requests by means of a simple linear programming problem which scales as the number of users, request volumes and/or services grows. This approach differs from most of the current proposals which may not scale well since: a) requests, even from the same user, are handled independently from one another; and b) the selection process often requires the solution of an NP-hard problem.

The content delivery networks (CDN) paradigm is based on the idea to transparently move third-party content closer to the users. More specifically, content is replicated on CDN servers which are located close to the final users, and user requests are redirected to the "best" replica (e.g., the closest) in a transparent way, so that users perceive a better content access service. In this paper we address user requests redirection and replica placement in CDNs. Differently from previous solutions our scheme considers the two problems jointly and relies on distributed and localized schemes that can be implemented with little complexity and overhead, thus providing a new overall solution that effectively trades-off among the number of replicas, their utilization (i.e., how many users requests they serve), the distance from the best replica and the number of replica adds and removals. An OPNET based thorough performance evaluation has allowed us to assess the effectiveness of the proposed solution. By properly tuning the distributed heuristics parameters the CDN provider can have a strict control on the CDN network operations so that the desired trade-off between all the relevant performance metrics is achieved.

Network performance tomography involves correlating end-to-end performance measures over different network paths to infer the performance characteristics on their intersection. Multicast based inference of link-loss rates is the first paradigm for the approach. Existing algorithms generally require numerical solution of polynomial equations for a maximum-likelihood estimator (MLE), or iteration when applying the expectation maximization (EM) algorithm. The purpose of this note is to demonstrate a new estimator for link-loss rates that is computationally simple, being an explicit function of the measurements, and that has the same asymptotic variance as the MLE, to first order in the link-loss rates.

The content delivery networks (CDN) paradigm is based on the idea to move third-party content closer to the users transparently. More specifically, content is replicated on servers closer to the users, and users requests are redirected to the best replica in a transparent way, so that the user perceives better content access service. In this paper we address the problem of dynamic replica placement and user requests redirection jointly. Our approach accounts for users demand variability and server constraints, and minimizes the costs paid by a CDN provider without degrading the quality of the user perceived access service. A non-linear integer programming formulation is given for the replica placement and user request redirection problems. The actual solution is obtained by mapping the non-linear integer problem into a series of mixed integer linear problems obtained by linearizing the non-linear constraints of the original problem. Preliminary numerical results show that the proposed solution is capable of effectively limiting the percentage of unsatisfied requests without over-replicating the contents over the CDN servers.

The content delivery networks (CDN) paradigm is based on the idea to transparently move third-party content closer to the users. More specifically, content is replicated on CDN servers which are located close to the final users, and user requests are redirected to the "best" replica (e.g. the closest) in a transparent way, so that users perceive a better content access service. In this paper we address the problem of dynamic replica placement. Being dynamic, our solutions adoptively select the number of replicas for each content and the replicas positions to account for traffic requests dynamics. The schemes we propose are designed to minimize the overall cost paid by the CDN provider (for replicas placement, removal, and maintenance) without degrading the quality of the users perceived access service. The contributions of the paper are twofold. First we introduce a centralized and distributed scheme for replica placement in a dynamic traffic scenario. Then, by means of a simulation based performance evaluation, we assess the effectiveness of the proposed schemes, and compare their performance with static solutions which have been proven to perform well in the literature. Simulation results show that both the two proposed algorithms achieve very good performance, resulting in a significant improvement over the static solutions. Despite relying on local information only, the distributed scheme has comparable performance to the centralized one. Both the two schemes result in low average distance between the users and their serving replicas, in low average number of replicas, in infrequent replicas add and tear down, and in high probability of being able to serve a request.

In this paper we present a model for the joint congestion control, routing and MAC link access for ad hoc wireless networks. We formulate the problem as a utility maximization problem with routing and link access constraints. For the solution we exploit the separable structure of the problem via dual decomposition and the sub-gradient algorithm. The resulting algorithm directly translates into a distributed cross-layer scheme for joint congestion control, routing and link scheduling of the wireless links which revolves around link layer pricing. The convex problem formulation and the use of the sub-gradient algorithm ensures that the solution converges within an interval of the optimal value. We illustrate the algorithm behavior through examples.

End-to-end measurement is a common tool for network performance diagnosis, primarily because it can reflect user experience and typically requires minimal support from intervening network elements. However, pinpointing the site of performance degradation from end-to-end measurements is a challenging problem. We show how end-to-end delay measurements of multicast traffic can be used to infer the under-lying logical multicast tree and the packet delay variance on each of its links. The method does not depend on cooperation from intervening network elements; multicast probing is bandwidth efficient. We establish desirable statistical properties of the estimator, namely consistency and asymptotic normality. We evaluate the approach through simulations, and analyze its failure modes and their probabilities.

In this paper we present a scalable model of a network of Active Queue Management (AQM) routers serving a large population of TCP flows. We present efficient solution techniques that allow one to obtain the transient behavior of the average queue lengths, packet loss probabilities, and average end-to-end latencies. We model different versions of TCP as well as different versions of RED, the most popular AQM scheme currently in use. Comparisons between our models andns simulation show our models to be quite accurate while at the same time requiring substantially less time to solve, especially when workloads and bandwidths are high. Categories and Subject Descriptors

In this paper we consider the problem of inferring link-level loss rates from end-to-end multicast measurements taken from a collection of trees. We give conditions under which loss rates are identifiable on a specified set of links. Two algorithms are presented to perform the link-level inferences for those links on which losses can be identified. One, the minimum variance weighted average (MVWA) algorithm treats the trees separately and then averages the results. The second, based on expectation-maximization (EM) merges all of the measurements into one computation. Simulations show that EM is slightly more accurate than MVWA, most likely due to its more efficient use of the measurements. We also describe extensions to the inference of link-level delay, inference from end-to-end unicast measurements, and inference when some measurements are missing.

Abstract—The use of multicast inference on end-to-end measurement has recently been proposed as a means to infer network internal characteristics such as packet link loss rate and delay. In this paper, we propose three types of algorithm that use loss measurements to infer the underlying multicast topology: i) a grouping estimator that exploits the monotonicity of loss rates with increasing path length; ii) a maximum-likelihood (ML) estimator (MLE); and iii) a Bayesian estimator. We establish their consistency, compare their complexity and accuracy, and analyze the modes of failure and their asymptotic probabilities. Index Terms—Communication networks, end-to-end measurement, maximum-likelihood (ML) estimation, multicast, statistical inference, topology discovery.

Packet delay greatly influences the overall performance of network applications. It is therefore important to identify causes and locations of delay performance degradation within a network. Existing techniques, largely based on end-to-end delay measurements of unicast traffic, are well suited to monitor and characterize the behavior of particular end-to-end paths. Within these approaches, however, it is not clear how to apportion the variable component of end-to-end delay as queueing delay at each link along a path. Moreover, there are issues of scalability for large networks. In this paper, we show how end-to-end measurements of multicast traffic can be used to infer the packet delay distribution and utilization on each link of a logical multicast tree. The idea, recently introduced in Caceres et al. (1999), is to exploit the inherent correlation between multicast observations to infer performance of paths between branch points in a tree spanning a multicast source and its receivers. The method does not depend on cooperation from intervening network elements; because of the bandwidth efficiency of multicast traffic, it is suitable for large-scale measurements of both end-to-end and internal network dynamics. We establish desirable statistical properties of the estimator, namely consistency and asymptotic normality. We evaluate the estimator through simulation and observe that it is robust with respect to moderate violations of the underlying model.

The use of end-to-end multicast traffic measurements has been recently proposed as a means to infer network internal characteristics as packet link loss rate and delay. We propose an algorithm that infers the multicast tree topology based on these end-to-end measurements. It is different from previous approaches which make only partial use of the available information, this algorithm adaptively combines different performance measures to reconstruct the topology. We establish its consistency and evaluate its accuracy through simulation. We show that in general it requires many fewer probes to correctly identify the topology than other methods.

In this paper we explore the use of end-to-end unicast traffic as measurement probes to infer link-level loss rates. We leverage on of earlier work that produced efficient estimates for link-level loss rates based on end-to-end multicast traffic measurements. We design experiments based on the notion of transmitting stripes of packets (with no delay between transmission of successive packets within a stripe) to two or more receivers. The purpose of these stripes is to ensure that the correlation in receiver observations matches as closely as possible what would have been observed if the stripe had been replaced by a notional multicast probe that followed the same paths to the receivers. Measurements provide good evidence that a packet pair to distinct receivers introduces considerable correlation which can be further increased by simply considering longer stripes. We then use simulation to explore how well these stripes translate into accurate link-level loss estimates. We observe good accuracy with packet pairs, with a typical error of about 1%, which significantly decreases as stripe length is increased to 4 packets.

End to end measurement is a common tool for network performance diagnosis, primarily because it can reflect user experience and typically requires minimal support from intervening network elements. Challenges in this approach are: (i) to identify the locale of performance degradation; and (ii) to perform measurements in a scalable manner for large and complex networks. In this paper we show how end-to end delay measurements of multicast traffic can be used to estimate packet delay variance on each link of a logical multicast tree. The method does not depend on cooperation from intervening network elements; multicast probing is bandwidth efficient. We establish desirable statistical properties of the estimator, namely consistency and asymptotic normality. We evaluate the approach through model based and network simulations. The approach extends to the estimation of higher order moments of the link delay distribution.

We study the problem of resource allocation and control for a network node with regulated traffic. Both guaranteed lossless service and statistical service with small loss probability are considered. We investigate the relationship between source characteristics and the buffer/bandwidth tradeoff under both services. Our contributions are the following. For guaranteed lossless service, we find that the optimal resource allocation scheme suggests that sources sharing a network node with finite bandwidth and buffer space divide into groups according to time scales defined by their leaky-bucket parameters. This time-scale separation determines the manner by which the buffer and bandwidth resources at the network node are shared among the sources. For statistical service with a small loss probability, we present a new approach for estimating the loss probability in a shared buffer multiplexer using the "extremal" on-off, periodic sources. Under this approach, the optimal resource allocation for statistical service is achieved by maximizing both the benefits of buffering sharing and bandwidth sharing. The optimal buffer/bandwidth tradeoff is again determined by a time-scale separation.

In this paper we study the problem of resource allocation and control for an ATM node with regulated traffic. Both guaranteed lossless service and statistical service with small loss probability are considered. We investigate the relationship between source characteristics and the buffer/bandwidth trade-off under both services. Our contributions are the following. For guaranteed lossless service, we find that the optimal resource allocation scheme suggests a time scale separation of sources sharing an ATM node with finite bandwidth and buffer space, and the optimal buffer/bandwidth trade-off is determined by the sources' time scale. For statistical service with a small loss probability, we present a new approach for estimating the loss probability in a shared buffer multiplexor with the so called "extremal" on-off periodic sources. Under this approach, the optimal resource allocation for statistical service is achieved by maximizing both the benefits of buffering sharing and bandwidth sharing. The optimal buffer/bandwidth trade-off is again determined by time scale separation.

We study the performance of a multiplexer using the generalized processor sharing (GPS) scheduling to serve Markov modulated fluid sources (MMFSs). We focus on a two-queue GPS system serving two classes of sources. By using a bounding approach combined with an approximation approach and by taking advantage of the specific structure of MMFSs, we are able to derive a lower bound and an upper bound approximation on queue length distributions for each class of the GPS system. Numerical investigations show that the lower bound and the upper bound approximation are very accurate. Hence our work greatly improves the earlier results on GPS scheduling which are obtained for a more general stochastic model. Application of our performance bounds to call admission control and bandwidth sharing is also illustrated, and a comparison with FIFO and strict priority in different scenarios is presented. We show that the flexibility provided by GPS does not provide much better performance than FIFO and priority when the classes only have loss requirements. However, this flexibility provides better performance when the classes exhibit delay requirements as well as loss requirements.