Join-the-shortest queue (JSQ) and its variants have often been used in solving load balancing problems. The aim of such policies is to minimize the average system occupation, e.g., the customer's system time. In this paper, we extend the load balancing setting to include constraints that may be imposed, e.g., due to the communication network. First, we cast the problem in the framework of constrained MDPs: this permits us to address both action-dependent constraints, such as, e.g, bandwidth limitation, and state-dependent constraints, such as, e.g., minimum queue utilization. Hence, unlike the state-of-the-art approaches in load balancing, we derive new policies that satisfy the constraints while minimizing system occupancy. Extensive numerical simulations have evaluated their performance under various system settings.

The Kelly or proportional allocation mechanism is a simple and efficient auction-based decentralized resource allocation scheme that distributes an infinitely divisible resource proportionally to the agents' bids. When agents are aware of the allocation mechanism, their interactions form a game. The properties of its Nash equilibria are well understood under the simplifying assumption of unbounded budgets. In this paper, we analyze the game in a more realistic budget-constrained setting, motivated by its optimality in terms of the liquid price of anarchy (LPoA). Specifically, we establish a sufficient condition for the uniqueness of the Nash equilibrium and design a distributed sequential learning procedure that provably converges to the equilibrium. In particular, our sufficient condition holds when the payoff functions of the agents are of the proportional fair type in the allocated fraction. Finally, extensive numerical experiments shed light on the interplay between the heterogeneity of the payoff functions and the agents' budgets.

The deployment of large antenna arrays in Massive Multiple Input Multiple Output (M-MIMO) systems substantially improves mobile networks’ performance. Nevertheless, the increase in performance brought by additional antennas is often counterbalanced by an increase in Power Consumption (PC) caused by the use of supplemental hardware resources supporting additional Radio Frequency (RF) channels. In M-MIMO networks, switching on/off RF channels and muting the associated antennas according to load conditions is known to be an efficient Energy Saving (ES) mechanism. This paper introduces a new RF channels switch on/off solution to maximize the Energy Efficiency (EE) under Quality of Service (QoS) constraints. The proposed solution is based on a MAB algorithm, which appears simpler than state of the art approaches and can be easily implemented in real systems. The algorithm leverages the quasiconcave shape of the EE metric to sequentially select the optimal antenna array configuration - i.e., the number of RF channels in both azimuth and elevation - from a predefined set of configurations. Extensive system-level simulations demonstrate that the proposed algorithm achieves a significant EE gain over a baseline solution.

Modern portable devices can execute increasingly sophisticated AI models on sensed data. The complexity of such processing tasks is data-dependent and has relevant energy cost. This work develops an Age of Information Markovian model for a system where multiple battery-operated devices perform data processing and energy harvesting in parallel. Part of their computational burden is offloaded to an edge server which polls devices at given rate. The structural properties of an optimal policy for a single device-server system are derived. They permit to define a new model-free reinforcement learning method specialized for monotone policies, namely Ordered Q-Learning, providing a fast procedure to learn the optimal policy. The method is oblivious to the devices’ battery capacities, the cost and the value of data batch processing and to the dynamics of the energy harvesting process. Finally, the polling strategy of the server is optimized by combining this policy improvement technique with stochastic approximation methods. Extensive numerical results provide insight into the system properties and demonstrate that the proposed learning algorithms outperform existing baselines.

Datacenter networks commonly facilitate the transmission of data in distributed computing frameworks through coflows, which are collections of parallel flows associated with a common task. Most of the existing research has concentrated on scheduling coflows to minimize the time required for their completion, i.e., to optimize the average dispatch rate of coflows in the network fabric. Nevertheless, modern applications often produce coflows that are specifically intended for online services and mission-crucial computational tasks, necessitating adherence to specific deadlines for their completion. In this paper, we introduce$\mathtt {WDCoflow}$, a new algorithm to maximize the weighted number of coflows that complete before their deadline. By combining a dynamic programming algorithm along with parallel inequalities, our heuristic solution performs at once coflow admission control and coflow prioritization, imposing a$\sigma$-order on the set of coflows. With extensive simulation, we demonstrate the effectiveness of our algorithm in improving up to$3\times$more coflows that meet their deadline in comparison the best SoA solution, namely$\mathtt {CS\rm{-}MHA}$. Furthermore, when weights are used to differentiate coflow classes,$\mathtt {WDCoflow}$is able to improve the admission per class up to$4\times$, while increasing the average weighted coflow admission rate.

With the advent of big data applications, coflow scheduling has become a cornerstone for the engineering of traffic in datacenters. Minimizing the average weighted Coflow Completion Times (CCT) is a crucial step to minimize the execution time of jobs running in distributed computing frameworks. In this paper, we present a new$\sigma $-order coflow scheduling solution, ONE-PARIS, an online semi-clairvoyant and semi-distributed implementation suitable to minimize the weighted CCT in production environments. We achieves this through ONE-PARIS scheduler for ordering coflows and a decentralized resource allocation mechanism, called Sync-Rate, enabling to respect the order of priority of coflows provided by ONE-PARIS and ensuring efficient synchronization between flows of the same coflow in order to free up bandwidth for low-priority flows. Extensive simulations on both synthetic and real traffics show that our proposed coflow scheduler outperforms other state-of-art schemes.

The average coflow completion time (CCT) is the standard performance metric in coflow scheduling. However, standard CCT minimization may introduce unfairness between the data transfer phase of different computing jobs. Thus, while progress guarantees have been introduced in the literature to mitigate this fairness issue, the trade-off between fairness and efficiency of data transfer is hard to control. This paper introduces a fairness framework for coflow scheduling based on the concept of slowdown, i.e., the performance loss of a coflow compared to isolation. By controlling the slowdown it is possible to enforce a target coflow progress while minimizing the average CCT. In the proposed framework, the minimum slowdown for a batch of coflows can be determined in polynomial time. By showing the equivalence with Gaussian elimination, slowdown constraints are introduced into primal-dual iterations of the CoFair algorithm. The algorithm extends the class of the$\sigma$-order schedulers to solve the fair coflow scheduling problem in polynomial time. It provides a 4-approximation of the average CCT w.r.t. an optimal scheduler. Extensive numerical results demonstrate that this approach can trade off average CCT for slowdown more efficiently than existing state of the art schedulers.

The deployment of RISs in future 6G networks is expected to substantially improve mobile network coverage. This paper introduces a new cross-layer low-complexity scheme for the online optimization of RIS-assisted communication systems. It jointly combines BS and RIS configuration and fair UEs’ scheduling which is critical for high-performance deployments. A RIS beam synthesis method is especially proposed for RIS configuration. The proposed solution embeds two nested control loops: i) a fast control loop working at the OFDMA slot scale and consisting in a standard UEs proportional fair scheduler, and ii) a slow control loop operating at the OFDMA frame scale which adapts the RIS’ configuration to the UEs’ spatial distribution and maximizes the UEs’ aggregated performance. The slow control loop is based on an online stochastic approximation algorithm whose convergence to the optimal restpoint is proved. In a reference scenario, the proposed scheduler achieves a gain of 47% in mean spectral efficiency for NLOS UEs over a baseline scheme.

Modern portable devices can execute increasingly sophisticated AI models on sensed data. The complexity of such processing tasks is data-dependent and has relevant energy cost. This work develops an Age of Information markovian model for a system where multiple battery-operated devices perform data processing and energy harvesting in parallel. Part of their computational burden is offloaded to an edge server which polls devices at given rate. The structural properties of an optimal policy for a single device-server system are derived. They permit to define a new model-free reinforcement learning method specialized for monotone policies, namely Ordered Q-Learning, providing a fast procedure to learn the optimal policy. The method is oblivious to the devices' battery capacities, the cost and the value of data batch processing and to the dynamics of the energy harvesting process. Finally, the polling strategy of the server is optimized by combining this policy improvement technique with stochastic approximation methods. Extensive numerical results provide insight into the system properties and demonstrate that the proposed learning algorithms outperform existing baselines.

The widespread adoption of 5G cellular technology will evolve as one of the major drivers for the growth of IoT-based applications. In this paper, we consider a Service Provider (SP) that launches a smart city service based on IoT data readings: in order to serve IoT data collected across different locations, the SP dynamically negotiates and rescales bandwidth and service functions. 5G network slicing functions are key to lease appropriate amount of resources over heterogeneous access technologies and different site types. Also, different infrastructure providers will charge slicing service depending on specific access technology supported across sites and IoT data collection patterns. We introduce a pricing mechanism based on Age of Information (AoI) to reduce the cost of SPs. It provides incentives for devices to smooth traffic by shifting part of the traffic load from highly congested and more expensive locations to lesser charged ones, while meeting QoS requirements of the IoT service. The proposed optimal pricing scheme comprises a two-stage decision process, where the SP determines the pricing of each location and devices schedule uploads of collected data based on the optimal uploading policy. Simulations show that the SP attains consistent cost reductions tuning the trade-off between slicing costs and the AoI of uploaded IoT data.

Reducing Coflow Completion Time (CCT) has a significant impact on data-intensive application performance in datacenter networks. An efficient allocation of network resources allows for accelerating the computations to be performed. In this paper, we propose a new scheduler, named ELITE, to minimize the Weighted Coflow Completion Time (WCCT). Our scheduling algorithm is a 2-approximation of the optimal and the rate allocation can achieve a 4-approximation as long as the scheduling priority is respected. We also present a new rate allocation procedure, named RACO, that shows near-optimal performance when combined with our scheduling algorithms. We also propose a low complexity online scheduler, named LSPRT to attain near-optimal performance in online setting. With extensive simulations, we demonstrate the effectiveness of our algorithms by measuring the performance gain of ELITE and LSPRT over previous solutions in the literature. In particular, ELITE and LSPRT perform about 44 % better than Varys, while Sincronia achieves only 32 % against Varys.

Network slicing is becoming the platform of choice for several applications and services. Nowadays most applications are virtualized to gain flexibility and portability. With network slicing, operators can create multiple network slices or tenants, which can be used for certain applications with specific requirements. Behind the network slicing, a slice expresses the need to access a precise service type, under a fully qualified set of computing and network requirements. Resource allocation decision encompasses a combination of different resource types (e.g., radio resource, CPU, memory, bandwidth). In this paper, we explore a differential pricing scheme that maximizes social welfare among slices as well as among end-users. To do so, we propose a pricing mechanism that makes fairness at multiple levels: fairness among slices and fairness among slice locations supported by each slice. Therefore, the proposed scheme is beneficial for both the slices and the end-users independent of their location. Additionally, we study the case where slices can manipulate their preferences to improve their utility. We show that the Fisher market game always has a pure Nash equilibrium and we prove Price of Anarchy is $\frac{1}{N}$, where N is the number of slices. Finally, we conduct simulations using Amazon EC2 instances to numerically analyze and compare the performance of the mechanisms and confirm the theoretical properties of the market model.

When adopting a novel mobile technology, a mobile network operator faces the dilemma of determining which is the best time to start the installation of next generation equipment onto the existing infrastructure. In a strategic context, the best possible time for deployment is also the best response to competitors’ actions, subject to normative and material constraints and to the customer’s adoption curve. We formulate in this paper a finite discrete-time game which captures the main features of the problem for a two-player game played over a prescribed finite horizon. Our numerical results provide insights on the possible optimal tradeoffs for an operator between fixed costs and installation strategies.

Fog computing promises to extend cloud computing to match emerging demands for low latency, location-awareness and dynamic computation. It thus brings data processing close to the edge of the network by leveraging on devices with different computational characteristics. However, the heterogeneity, the geographical distribution, and the data-intensive profiles of IoT deployments render the placement of fog applications a fundamental problem to guarantee target performance figures. This is a core challenge for fog computing providers to offer fog infrastructure as a service, while satisfying the requirements of this new class of microservices-based applications. In this article we root our analysis on the throughput requirements of the applications while exploiting offloading towards different regions. The resulting resource allocation problem is developed for a fog-native application architecture based on containerised microservice modules. An algorithmic solution is designed to optimise the placement of applications modules either in cloud or in fog. Finally, the overall solution consists of two cascaded algorithms. The first one performs a throughput-oriented partitioning of fog application modules. The second one rules the orchestration of applications over a region-based infrastructure. Extensive numerical experiments validate the performance of the overall scheme and confirm that it outperforms state-of-the-art solutions adapted to our context.

In the framework of queuing theory with multiclass jobs, trunk-reservation is an admission control technique to handle job class priority in an online fashion, and serve as many high priority jobs as possible. This is achieved by rejecting jobs with sufficiently low priority when the buffer space becomes a scarce resource, i.e., when the queue may soon overflow. Mathematically, the objective is to maximize the long-term reward of the admitted jobs, where each job is assigned a reward which is monotonic with respect to the priority class it belongs to. In this paper we study online learning of optimal trunk-reservation policies when the system parameters, i.e., class arrival rates and service time, are unknown. Starting from a Markov Decision Process (MDP) formulation, we leverage the stairway structure of the optimal policy to define Integer Gradient Ascent (IGA), a reinforcement learning (RL) algorithm based on policy-gradient methods, specifically tailored to the mathematical properties of the problem at hand. We provide theoretical results on the convergence properties of IGA. Extensive numerical experiments characterize its behavior and confirm that it outperforms standard RL techniques in terms of convergence rate.

Dynamic Adaptive Streaming over HTTP (DASH) has become the standard choice for live events and on-demand video services. In fact, by performing bitrate adaptation at the client side, DASH operates to deliver the highest possible Quality of Experience (QoE) under given network conditions. In cellular networks, in particular, video streaming services are affected by mobility and cell load variation. In this context, DASH video clients continually adapt the streaming quality to cope with channel variability. However, since they operate in a greedy manner, adaptive video clients can overload cellular network resources, degrading the QoE of other users and suffer persistent bitrate oscillations. In this paper, we tackle this problem using a new eNB scheduler, named Shadow-Enforcer, which ensures minimal number of quality switches as well as efficient and fair utilization of network resources. Our scheduler works well under dynamic scenarios and mobility, and requires minimal information, i.e., just the set of video bitrates supported by DASH video clients. It consists of the cascade of a virtual scheduler, Shadow, and the actual scheduler, Enforcer, piloted by the virtual one. Extensive simulations demonstrate the efficiency, fairness and the smooth response to channel variations of the proposed solution.

To optimize routing of flows in datacenters, SDN controllers receive a packet-in message whenever a new flow appears in the network. Unfortunately, flow arrival rates can peak to millions per second, impairing the ability of controllers to treat them on time. Flow scheduling copes with such sheer numbers by segmenting the traffic between elephant and mice flows and by treating elephant flows in priority, as they disrupt short lived TCP flows and create bottlenecks. We propose a learning algorithm called SOFIA and able to perform optimal online flow segmentation. Our solution, based on stochastic approximation techniques, is implemented at the switch level and updated by the controller, with minimal signaling over the control channel. SOFIA is blind, i.e., it is oblivious to the flow size distribution. It is also adaptive, since it can track traffic variations over time. We prove its convergence properties and its message complexity. Moreover, we specialize our solution to be robust to traffic classification errors. Extensive numerical experiments characterize the performance of our approach in vitro. Finally, results of the implementation in a real OpenFlow controller demonstrate the viability of SOFIA as a solution in production environments.

High availability of containerized applications requires to perform robust storage of applications' state. Since basic replication techniques are extremely costly at scale, storage space requirements can be reduced by means of erasure and/or repairing codes. In this paper we address storage regeneration using repair codes, a robust distributed storage technique with no need to fully restore the whole state in case of failure. In fact, only the lost servers' content is replaced. To do so, new clean-slate storage units are made operational at a cost for activating new storage servers and a cost for the transfer of repair data. Our goal is to guarantee maximal availability of containers' state files by a given deadline. Upon a fault occurring at a subset of the storage servers, we aim at ensuring that they are repaired by a given deadline. We introduce a controlled fluid model and derive the optimal activation policy to replace servers under such correlated faults. The solution concept is the optimal control of regeneration via the Pontryagin minimum principle. We characterize feasibility conditions and we prove that the optimal policy is of threshold type. Numerical results describe how to apply the model for system dimensioning and show the tradeoff between activation of servers and communication cost.

In this paper we present Foggy, an architectural framework and software platform based on Open Source technologies. Foggy orchestrates application workload, negotiates resources and supports IoT operations for multi-tier, distributed, heterogeneous and decentralized Cloud Computing systems. Foggy is tailored for emerging domains such as 5G Networks and IoT, which demand resources and services to be distributed and located close to data sources and users following the Fog Computing paradigm. Foggy provides a platform for infrastructure owners and tenants (i.e., application providers) offering functionality of negotiation, scheduling and workload placement taking into account traditional requirements (e.g. based on RAM, CPU, disk) and non-traditional ones (e.g. based on networking) as well as diversified constraints on location and access rights. Economics and pricing of resources can also be considered by the Foggy model in a near future. The ability of Foggy to find a trade-off between infrastructure owners' and tenants' needs, in terms of efficient and optimized use of the infrastructure while satisfying the application requirements, is demonstrated through three use cases in the video surveillance and vehicle tracking contexts.

HTTP Adaptive Streaming is able to dynamically match video quality to variable network conditions. This is a key feature for multimedia delivery when quality of service cannot be granted network-wide. For instance, the end-to-end throughput towards mobile terminals may suffer short term fluctuations due to fading. Hence, robust bitrate adaptation schemes become crucial in order to avoid degraded video reproduction. The objective, in this context, is to control the filling level of the playback buffer, maximize the video quality, and avoid unnecessary quality variations which may also impair the perceived quality of experience. In this work we study bitrate adaptation algorithms leveraging on Backward-Shifted Coding (BSC), a scalable video coding scheme able to cope with the effects of end-to-end throughput fluctuations. We have proposed a new adaptation scheme able to balance video rate smoothness and high network capacity utilization. Both the throughput-based and buffer-based variants of such scheme have been designed. Extensive simulations using synthetic and real-world video traffic traces show that the proposed solution performs remarkably well even under challenging network conditions.

Cooperative sensing enables secondary users to combine individual sensing results in order to attain sensing accuracies beyond those achieved by consumer RF devices. However, due to sensing costs, secondary users may prefer not to cooperate to the sensing task, leading to higher false alarm probability. In this paper, we study how information about the presence of cooperators affects the dynamics of cooperative sensing schemes. We consider two scenarios, namely the case when SUs cannot detect the presence of other potential cooperators, and the case when SUs have prior information on the presence of other SUs in radio range. Using an evolutionary game framework, we demonstrate that protocols delivering such type of information to SUs reduce cooperation and ultimately lead to degraded network performance. Finally, a learning process based on the replicator dynamics is proposed which is capable to drive the system to the evolutionary stable solution. The results of the paper are illustrated through numerical simulations.

The surge of mobile data traffic forces network operators to cope with capacity shortage. The deployment of small cells in 5G networks shall increase radio access capacity. Mobile edge computing technologies can be used to manage dedicated cache memory at the edge of mobile networks. As a result, data traffic can be confined within the radio access network thus reducing latency, round-trip time and backhaul congestion. Such technique can be used to offer content providers premium connectivity services to enhance the quality of experience of their customers on the move. In this context, cache memory in the mobile edge network becomes a shared resource. We study a competitive caching scheme where contents are stored at a given price set by the mobile network operator. We first formulate a resource allocation problem for a tagged content provider seeking to minimize the expected missed cache rate. The optimal caching policy is derived accounting for popularity of contents, spatial distribution of small cells, and caching strategies of competing content providers. Next, we study a game among content providers in the form of a generalized non-smooth Kelly mechanism with bounded strategy sets and heterogeneous players. Existence and uniqueness of the Nash equilibrium are proved. Finally, numerical results validate and characterize the performance of the system.

Optimal stochastic control of delay tolerant networks is studied in this paper. First, the structure of optimal two-hop forwarding policies is derived. In order to be implemented, such policies require knowledge of certain global system parameters such as the number of mobiles or the rate of contacts between mobiles. But, such parameters could be unknown at system design time or may even change over time. In order to address this problem, adaptive policies are designed that combine estimation and control: based on stochastic approximation techniques, such policies are proved to achieve optimal performance in spite of lack of global information. Furthermore, the paper studies interactions that may occur in the presence of several DTNs which compete for the access to a gateway node. The latter problem is formulated as a cost-coupled stochastic game and a unique Nash equilibrium is found. Such equilibrium corresponds to the system configuration in which each DTN adopts the optimal forwarding policy determined for the single network problem.

We introduce Cloud4IoT, a platform offering automatic deployment, orchestration and dynamic configuration of IoT support software components and data-intensive applications for data processing and analytics, thus enabling plug-and-play integration of new sensor objects and dynamic workload scalability. Cloud4IoT enables the concept of Infrastructure as Code in the IoT context: it empowers IoT operations with the flexibility and elasticity of Cloud services. Furthermore it shifts traditionally centralized Cloud architectures towards a more distributed and decentralized computation paradigm, as required by IoT technologies, bridging the gap between Cloud Computing and IoT ecosystems. Thus, Cloud4IoT is playing a role similar to the one covered by solutions like Fog Computing, Cloudlets or Mobile Edge Cloud. The hierarchical architecture of Cloud4IoThosts a central Cloud platform and multiple remote edge Cloud modules supporting dedicated devices, namely the IoT Gateways, through which new sensor objects are made accessible to the platform. Overall, the platform is designed in order to support systems where IoT-based and data intensive applications may pose specific requirements for low latency, restricted available bandwidth, or data locality. Cloud4IoT is built on several Open Source technologies for containerisation and implementations of standards, protocols and services for the IoT. We present the implementation of the platform and demonstrate it in two different use cases.

The endeavor to develop 5G technology aims to support the recent outstanding mobile data traffic growth. In this regard, mobile network providers will be able to leverage on cloud edge-caching to offer services with enhanced quality of experience on the move. By this technology, dedicated cache space of mobile networks can be provisioned to OTT content providers, e.g., over metropolitan areas covered the network of a mobile network provider. In this work we address the problem of fair pricing such caching service, with storage the actual shared resource for caching. We study a scheme in which contents are dynamically stored in the edge memory. The mobile network provider offers a price λ for storing contents on the shared cache, thus engendering competition for cache memory sharing among content providers. We model such competition among OTT content providers using the economic notion of Kelly mechanism. Hence, we have studied the Stackelberg equilibrium, i.e., the optimal price configuration for the network provider. Numerical results describe the structure of the Nash equilibrium and the optimal prices resulting from the network provider optimal strategy.

Access to online contents represents a large share of the Internet traffic. Most such contents are multimedia items which are user-generated, i.e., posted online by the contents' owners. In this paper we focus on how those who provide contents can leverage online platforms in order to profit from their large base of potential viewers. Actually, platforms like Vimeo or YouTube provide tools to accelerate the dissemination of contents, i.e., recommendation lists and other re-ranking mechanisms. Hence, the popularity of a content can be increased by paying a cost for advertisement: doing so, it will appear with some priority in the recommendation lists and will be accessed more frequently by the platform users. Ultimately, such acceleration mechanism engenders a competition among online contents to gain popularity. In this context, our focus is on the structure of the acceleration strategies which a content provider should use in order to optimally promote a content given a certain daily budget. Such a best response indeed depends on the strategies adopted by competing content providers. Also, it is a function of the potential popularity of a content and the fee paid for the platform advertisement service. We formulate the problem as a differential game and we solve it for the infinite horizon case by deriving the structure of certain Nash equilibria of the game.

Network virtualization sits firmly on the Internet evolutionary path allowing researchers to experiment with novel clean-slate designs over the production network and practitioners to manage multi-tenants infrastructures in a flexible and scalable manner. In such scenarios, isolation between virtual networks is often intended as purely logical: this is the case of address space isolation or flow space isolation. This approach neglects the effect that network virtualization has on resource allocation network-wide. In this work we investigate the price paid by a purely logical approach in terms of performance degradation. This performance loss is paid by the actual users of a multi-tenants datacenter network. We propose a solution to this problem leveraging on a new network virtualization primitive, namely an online link utilization feedback mechanism. It provides each tenant with the necessary information to make efficient use of network resources. We evaluate our solution trough a real implementation exploiting the OpenFlow protocol. Empirical results confirm that the proposed scheme is able to support tenants in exploiting virtualized network resources effectively.

In this paper we study mobile ad hoc wireless networks by using the notion of evolving connectivity graphs. In such systems, the connectivity changes over time due to the intermittent contacts of mobile terminals. In particular, we are interested in studying the expected flooding time when full connectivity cannot be ensured at each point in time. Even in this case, due to finite contact times durations, connected components may appear in the connectivity graph. Hence, this represents the intermediate case between extreme cases of fully mobile ad hoc networks and fully static ad hoc networks. By using a generalization of edge-Markovian graphs, we extend the existing models based on sparse scenarios to this intermediate case and calculate the expected flooding time. We also propose bounds that have reduced computational complexity.

Social scientists have observed that human behavior in society can often be modeled as corresponding to a threshold type policy. A new behavior would propagate by a procedure in which an individual adopts the new behavior if the fraction of his neighbors or friends having adopted such behavior exceeds some threshold. In this paper we study the question of whether the emergence of threshold policies may be modeled as a result of some rational process which would describe the behavior of non-cooperative rational members of some social network. We focus on situations in which individuals take the decision whether to access or not some content, based on the number of views that the content has. Our analysis aims at understanding not only the behavior of individuals, but also the way in which information about the quality of a given content can be deduced from view counts when only part of the viewers that access the content are informed about its quality. In this paper we present a game formulation for the behavior of individuals using a meanfield model: the number of individuals is approximated by a continuum of atomless players and for which the Wardrop equilibrium is the solution concept. We derive conditions on the problem's parameters that result indeed in the emergence of threshold equilibria policies. But we also identify some parameters in which other structures are obtained for the equilibrium behavior of individuals.

Performance of a delay-tolerant network has strong dependence on the nodes participating in data transportation. Such networks often face several resource constraints especially related to energy. Energy is consumed not only in data transmission, but also in listening and in several signaling activities. On one hand these activities enhance the system's performance while on the other hand, they consume a significant amount of energy even when they do not involve actual node transmission. Accordingly, in order to use energy efficiently, one may have to limit not only the amount of transmissions, but also the amount of nodes that are active at each time. Therefore, we study two coupled problems: 1) the activation problem that determines when a mobile will turn on in order to receive packets; and 2) the problem of regulating the beaconing. We derive optimal energy management strategies by formulating the problem as an optimal control one, which we then explicitly solve. We also validate our findings through extensive simulations that are based on contact traces.

Several novel metrics have been proposed in recent literature in order to study the relative importance of nodes in complex networks. Among those, k-coreness has found a number of applications in areas as diverse as sociology, proteinomics, graph visualization, and distributed system analysis and design. This paper proposes new distributed algorithms for the computation of the k-coreness of a network, a process also known as k-core decomposition. This technique 1) allows the decomposition, over a set of connected machines, of very large graphs, when size does not allow storing and processing them on a single host, and 2) enables the runtime computation of k-cores in “live” distributed systems. Lower bounds on the algorithms complexity are given, and an exhaustive experimental analysis on real-world data sets is provided.

In Delay Tolerant Networks (DTNs) the core challenge is to cope with lack of persistent connectivity and yet be able to deliver messages from source to destination. In particular, routing schemes that leverage relays' memory and mobility are a customary solution in order to improve message delivery delay. When large files need to be transferred from source to destination, not all packets may be available at the source prior to the first transmission. This motivates us to study general packet arrivals at the source, derive performance analysis of replication-based routing policies and study their optimization under two-hop routing. In particular, we determine the conditions for optimality in terms of probability of successful delivery and mean delay and we devise optimal policies, so-called it piecewise-threshold policies. We account for linear block-codes and rateless random linear coding to efficiently generate redundancy, as well as for an energy constraint in the optimization. We numerically assess the higher efficiency of piecewise-threshold policies compared with other policies by developing heuristic optimization of the thresholds for all flavors of coding considered.

Maximizing system throughput and bandwidth utilization while guaranteeing fairness among users is a core technical challenge in the design of next generation cellular networks. In this context, fractional frequency reuse (FFR) is a helpful tool if it is flexible in terms of resource and power allocation as well as scheduling. Complementary to this tool, a well-chosen association of users to base station sectors can yet be another important factor, particularly when users are distributed unevenly in space. Here we propose a load balancing scheme that combines flexible FFR with an unrestricted association of users to sectors or base stations, thereby effectively increasing the user data rates in the dense regions of the network. In a first step, we perform virtual joint power allocation and scheduling so as to determine the best sectors for maximizing the throughput for a given user. In a second step, users are actually associated to the best sectors, which are not necessarily the ones providing the strongest signal. Simulation results show that our proposed mechanism provides fairness by load balancing while still maintaining the throughput over all users.

Epidemics dynamics can describe the dissemination of information in delay tolerant networks, in peer to peer networks and in content delivery networks. The control of such dynamics has thus gained a central role in all of these areas. However, a major difficulty in this context is that the objective functions to be optimized are often not additive in time but are rather multiplicative. The classical objective function in DTNs, i.e., the successful delivery probability of a message within a given deadline, falls precisely in this category, because it takes often the form of the expectation of the exponent of some integral cost. So far, models involving such costs have been solved by interchanging the order of expectation and the exponential function. While reducing the problem to a standard optimal control problem, this interchange is only tight in the mean field limit obtained as the population tends to infinity. In this paper we identify a general framework from optimal control in finance, known as risk sensitive control, which let us handle the original (multiplicative) cost and obtain solutions to several novel control problems in DTNs. In particular, we can derive the structure of state-dependent controls that optimize transmission power at the source node. Further, we can account for the propagation loss factor of the wireless medium while obtaining these controls, and, finally, we address power control at the destination node, resulting in a novel threshold optimal activation policy. Combined optimal power control at source and destination nodes is also obtained.

Among the novel metrics used to study the relative importance of nodes in complex networks, k-core decomposition has found a number of applications in areas as diverse as sociology, proteinomics, graph visualization, and distributed system analysis and design. This paper proposes new distributed algorithms for the computation of the k-core decomposition of a network, with the purpose of (i) enabling the run-time computation of k-cores in "live" distributed systems and (ii) allowing the decomposition, over a set of connected machines, of very large graphs, that cannot be hosted in a single machine. Lower bounds on the algorithms complexity are given, and an exhaustive experimental analysis on real-world graphs is provided.

No abstract available.

As the number and capabilities of mobile devices is rapidly increasing, new challenges arise in the way services are currently designed. Users are seeking for more complex and advanced functionalities able to satisfy their increasing requirements. As a consequence, in ubiquitous environments, a different way to design services has to be introduced in order to guarantee services always up to date in a transparent and efficient way. In this paper, we present and analyze a framework for distributed cooperative service evolution in a wireless nomadic environment. In particular, we assume a disconnected network architecture, where users' mobility is exploited to achieve a scalable behavior, and communication is based on localized peer-to-peer interactions among neighboring nodes. Service management is achieved by introducing autonomic services, whose operations are based on a distributed evolution process, which draws tools and concepts from evolutionary computation (and genetic algorithms in particular). The latter relies on the concept of recombination , i.e., the exchange of information among service users, which collaborate to enhance their fitness , defined as the ability of the actual service to fulfill user's requirements. We introduce a general framework for analyzing service recombination policies and exploit results from martingales theory to study their convergence properties.

Delay-tolerant ad hoc networks leverage the mobility of relay nodes to compensate for lack of permanent connectivity and thus enable communication between nodes that are out of range of each other. To decrease delivery delay, the information to be delivered is replicated in the network. Our objective in this paper is to study a class of replication mechanisms that include coding in order to improve the probability of successful delivery within a given time limit. We propose an analytical approach that allows to quantify tradeoffs between resources and performance measures (energy and delay). We study the effect of coding on the performance of the network while optimizing parameters that govern routing. Our results, based on fluid approximations, are compared to simulations that validate the model.

Much research has been devoted to maximize the life time of mobile ad-hoc networks. Life time has often been defined as the time elapsed until the first node is out of battery power. In the context of static networks, this could lead to disconnectivity. In contrast, Delay Tolerant Networks (DTNs) leverage the mobility of relay nodes to compensate for lack of permanent connectivity, and thus enable communication even after some nodes deplete their stored energy. One can thus consider the lifetimes of nodes as some additional parameters that can be controlled to optimize the performance of a DTN. In this paper, we consider two ways in which the energy state of a mobile can be controlled. Both listening and transmission require energy, besides each of these has a different type of effect on the network performance. Therefore we consider a joint optimization problem consisting of: i) activation, which determines when a mobile will turn on in order to receive packets, and ii) transmission control, which regulates the beaconing. The optimal solutions are shown to be of the threshold type. The findings are validated through extensive simulations.

We study replication mechanisms that include Reed-Solomon type codes as well as network coding in order to improve the probability of successful delivery within a given time limit. We propose an analytical approach to compute these and study the effect of coding on the performance of the network while optimizing parameters that govern routing.

We study in this paper optimal stochastic control issues in delay tolerant networks. We first derive the structure of optimal 2-hop forwarding policies. In order to be implemented, such policies require the knowledge of some system parameters such as the number of mobiles or the rate of contacts between mobiles, but these could be unknown at system design time or may change over time. To address this problem, we design adaptive policies combining estimation and control that achieve optimal performance in spite of the lack of information. We then study interactions that may occur in the presence of several competing classes of mobiles and formulate this as a cost-coupled stochastic game. We show that this game has a unique Nash equilibrium such that each class adopts the optimal forwarding policy determined for the single class problem.

Delay tolerant ad-hoc networks leverage the mobility of relay nodes to compensate for lack of permanent connectivity and thus enable communication between nodes that are out of range of each other. To decrease delivery delay, the information to be delivered is replicated in the network. Our objective in this paper is to study a class of replication mechanisms that include coding in order to improve the probability of successful delivery within a given time limit. We propose an analytical approach that allows to quantify tradeoffs between resources and performance measures (energy and delay). We study the effect of coding on the performance of the network while optimizing parameters that govern routing. Our results, based on fluid approximations, are compared to simulations which validate the model.

Distributed estimation of global parameters in intermittently connected mobile environments is a challenging problem. In this paper, we introduce a set of methods, based on gossip techniques and population protocols, for performing such task. The applicability of such techniques to various environments, characterized by different mobility patterns, is evaluated through numerical simulations and discussed extensively. Guidelines are provided to help practitioners choosing the right method for their specific application problem.

Recently, research on disconnected networks has been fostered by several studies on delay-tolerant networks, which are designed in order to sustain disconnected operations. We focus on the emerging notion of connectivity which exists in such networks, where the message exchange between nodes is enforced by leveraging storage capabilities at intermediate relays, with the aim of achieving connectivity over time. The problem, under the constraint of intermittent connectivity, is hence to devise efficient mechanisms for message delivery, and evaluate the performance thereof. In this paper, we introduce a graph-based model able to capture the evolution of the connectivity properties of such systems over time. We show that, for most networks of interest, such connectivity graphs can be modeled as Erdos-Renyi random graphs. Furthermore, we show that, under a uniformity assumption, the time taken for the connectivity graph to become connected scales as Theta((n log n)/lambda) with the number of nodes in the network. Hence we found that, using epidemic routing techniques, message delay is O((n log2n)/(lambda log log n)). The model is validated by numerical simulations and by a comparison with the connectivity patterns emerging from real experiments.

Wireless communication systems are rapidly becoming a viable solution for employment at the lowest level of factory automation systems, usually referred to as either "device" or "field" level, where the requested performance may be rather critical in terms of both transmission time and reliability. In this paper, we deal with the use of wireless networks at the device level. Specifically, after an analysis of the communication requirements, we introduce a general profile of a wireless fieldbus. Both the physical and data link layers are taken directly from existing wireless local area networks and wireless personal area networks standards, whereas the application layer is derived from the most popular wired fieldbuses. We discuss implementation issues related to two models of application layer protocols and present performance results obtained through numerical simulations. We also address some important aspects related to data security and power consumption.

Ethernet networks rely on the so-called spanning tree protocol (IEEE 802.1d) in order to break cycles, thereby avoiding the possibility of infinitely circulating packets and deadlocks. This protocol imposes a severe penalty on the performance and scalability of large gigabit Ethernet backbones, since it makes inefficient use of expensive fibers and may lead to bottlenecks. We propose a significantly more scalable cycle-breaking approach, based on the novel theory of turn-prohibition. Specifically, we introduce, analyze and evaluate a new algorithm, called tree-based turn-prohibition (TBTP). We show that this polynomial-time algorithm maintains backward-compatibility with the IEEE 802.1d standard and never prohibits more than 1/2 of the turns in the network, for any given graph and any given spanning tree. Through extensive simulations on a variety of graph topologies, we show that it can lead to an order of magnitude improvement over the spanning tree protocol with respect to throughput and end-of-end delay metrics. In addition, we propose and evaluate heuristics to determine the replacement order of legacy switches that results in the fastest performance improvement.

We propose a new framework for providing robust location detection in emergency response systems, based on the theory of identifying codes. The key idea of this approach is to allow sensor coverage areas to overlap in such a way that each resolvable position is covered by a unique set of sensors. In this setting, determining a sensor-placement with a minimum number of sensors is equivalent to constructing an optimal identifying code, an NP-complete problem in general. We thus propose and analyze a new polynomial-time algorithm for generating irreducible codes for arbitrary topologies. We also generalize the concept of identifying codes to incorporate robustness properties that are critically needed in emergency networks and provide a polynomial-time algorithm to compute irreducible robust identifying codes. Through analysis and simulation, we show that our approach typically requires significantly fewer sensors than existing proximity-based schemes. Alternatively, for a fixed number of sensors, our scheme can provide robustness in the face of sensor failures or physical damage to the system.