1,720,977 research outputs found
Low cost routing in mobile ad-hoc networks: Is it achievable?
No full textCache schemes that adopt timeout (i.e. lifetime) for removing stale information have its correct estimation as basic assumption. An incorrect value for the timeout highly reduces the effect of the cache scheme or, even worst, produces a severe performance degradation rather than an improvement. However, lifetime estimation in mobile ad-hoc networks is difficult to assure due to the rapid ad random changes in the network topology as well as to dependency on the path length. In this paper we discuss the general issue of caching in the context of mobile environments as a means to achieve efficient routing protocols. We propose a class of cache schemes that adopt active topology monitoring to determine when cached routes become stale. The scheme requires explicit support from the routing protocol. We present an implementation of the scheme when using a ZRP-like routing protocol and present some preliminary performance results
Power of random choices made efficient for fog computing
Get PDFIn this paper, we consider a load balancing protocol based on the power of random choices that is adapted to a fog deploy in which several independent fog nodes equipped with a set of servers or VM are serving the same geographical area. The protocol is based on a simple but effective mechanism based on a threshold of . When a fog node receives a unit of computation or a job, it immediately executes the job if the number of its occupied servers is lower than , otherwise the node executes a randomized algorithm by probing other fog nodes in the area, and delegates the execution of the job to the least loaded one, provided the workload is lower than the probing node. Through a mathematical analysis we show that probing just one node () when there are less than two VM free provides the same performance of the well known power-of-two random choices centralized algorithm, but at a much lower delay and control overhead costs. Also, simulations are used to address the node heterogeneity and, with a real testbed, we offer results that prove the effective benefit of the proposed solution in practical applications
Exploiting power-of-choices for load balancing in fog computing
No full textPower-of-random choices is a well-known phenomenon exploited in load balancing algorithms to achieve an extraordinary improvement at low cost. These algorithms are particularly suitable for the Fog computing model, since they don't require coordination among different fog nodes when they decide to mutually share their resources. In this paper, we propose LL(F, T ) a power-of-random choices based distributed peer-to-peer load balancing algorithm running on a set of autonomous cooperating fog nodes, where F is the protocol fan-out and T a threshold. Nodes implement a random choice over F fog nodes when their current load is above T. Through a mathematical analysis and preliminary simulations we show that tuning T very close to the node saturation condition, this algorithm achieves practically the same performance of its classical implementation requiring a single global scheduler, without the need for each and every job execution to be preceded by a time costly probing phase, a clear benefit for the low delay requirement of fog applications
Distributed fair randomized (DFR): A resource sharing protocol for fog providers
No full textFog computing promises to support many emerging classes of applications that can't be rely on a cloud-only backend. Fog-to-Fog (F2F) cooperation is suggested in the openFog's Fog computing Reference Architecture, now adopted as an IEEE standard, as a way to improve the computation service provided by this computing delivery model.In this paper, we propose DFR-Distributed Fair Randomized, a distributed F2F cooperation algorithm that allows for sharing computation resources among fog providers that agree on a (reasonable) measure of fairness. We adopt an analytical approach to study the cooperation problem of providers subject to different load conditions. We initially put the cooperation problem in the light of a simple game-theory framework to capture the selfish behavior of providers without any fairness criteria and its consequence in limiting cooperation. Then, we cast the problem as an optimization problem that incorporates fairness. Preliminary simulations results show how DFR converges to the predicted optimal value. © 2019 IEEE
On the impact of stale information on distributed online load balancing protocols for edge computing
Get PDFThe distributed nature of edge computing infrastructures requires a significant effort to avoid overload conditions due to uneven distribution of incoming load from sensors placed over a wide area. While optimisation algorithms operating offline can address this issue in the medium to long term, sudden and unexpected traffic surges require an online approach where load balancing actions are taken at a smaller time scale. However, when the service time of a single request becomes comparable with the latency needed to take and actuate load balancing decisions, the design of online approaches becomes particularly challenging. This paper focuses on the class of online algorithms for load balancing based on resource sharing among random nodes. While this randomisation principle is a straightforward and effective way to share resources and achieve load balance, it fails to work properly when the interval between decision making and decision actuating times (called schedule lag) becomes comparable with the time required to execute a job, a condition not rare in edge computing systems, and provokes stale (out-of-date) information to be involved in scheduling decisions. Our analysis combines (1) a theoretical model that evaluates how stale information reduces the effectiveness of the balancing mechanism and describes the correlation between the system state at decision making and decision actuating times; (2) a simulation approach to study a wide range of algorithm parameters and possible usage scenarios. The results of our analysis provides the designers of distributed edge systems with useful hints to decide, based on the scenario, which load balancing protocol is the most suitable
Randomized Load Balancing under Loosely Correlated State Information in Fog Computing
Get PDFFog computing infrastructures must support increasingly complex applications where a large number of sensors send data to intermediate fog nodes for processing. As the load in such applications (as in the case of a smart cities scenario) is subject to significant fluctuations both over time and space, load balancing is a fundamental task. In this paper we study a fully distributed algorithm for load balancing based on random probing of the neighbors' status. A qualifying point of our study is considering the impact of delay during the probe phase and analyzing the impact of stale load information. We propose a theoretical model for the loss of correlation between actual load on a node and stale information arriving to the neighbors. Furthermore, we analyze through simulation the performance of the proposed algorithm considering a wide set of parameters and comparing it with an approach from the literature based on random walks. Our analysis points out under which conditions the proposed algorithm can outperform the alternatives
Traffic density estimation protocol using vehicular networks
No full textTraffic density estimates on maps not only assist drivers to decide routes that are time and fuel economical due to less congestions and but also help in preventing accidents that may occur due to the lack of not being able to see far ahead. In this paper, we propose a protocol that exploit vehicle-to-vehicle ad hoc communication for the estimation of vehicular density and the amount of congestion on roads. The protocol forms cluster heads by a voting algorithm. These cluster heads aggregate density information and spread it to the network via few selected forwarding vehicles. The protocol does not assume all vehicles to be equipped with Global Positioning System. We analytically study the cluster head formation part of the protocol and then simulate the proposed protocol using network simulator NS2 to understand different characteristics of the protocol. © Institute for Computer Sciences, Social Informatics and Telecommunications Engineering 2013
Distributed load balancing for heterogeneous fog computing infrastructures in smart cities
Get PDFSmart cities represent an archetypal example of infrastructures where the fog computing paradigm can express its potential: we have a large set of sensors deployed over a large geographic area where data should be pre-processed (e.g., to extract relevant information or to filter and aggregate data) before sending the result to a collector that may be a cloud data center, where relevant data are further processed and stored. However, during its lifetime the infrastructure may change, e.g., due to the additional sensors or fog nodes deploy, while the load can grow, e.g., for additional services based on the collected data. Since nodes are typically deployed in multiple time stages, they may have different computation capacity due to technology improvements. In addition, an uneven distribution of the workload intensity can arise, e.g., due to hot spot for occasional public events or to rush hours and users’ behavior. In simple words, resources and load can vary over time and space. Under the resource management point of view, this scenario is clearly challenging. Due to the large scale and variable nature of the resources, classical centralized solutions should in fact be avoided, since they do not scale well and require to transfer all data from sensors to a central hub, distorting the very nature of in-situ data processing. In this paper, we address the problem of resources management by proposing two distributed load balancing algorithms, tailored to deal with heterogeneity. We evaluate the performance of such algorithms using both a simplified environment where we perform several sensitivity analysis with respect to the factors responsible for the infrastructure heterogeneity and exploiting a realistic scenario of a smart city. Furthermore, in our study we combine theoretical models and simulation. Our experiments demonstrate the effectiveness of the algorithms under a wide range of heterogeneity, overall providing a remarkable improvement compared to the case of not cooperating nodes
CICO: A Credit-Based Incentive Mechanism for COoperative Fog Computing Paradigms
No full textFog computing is a key paradigm that brings together shared storage, low latency communication, and computation resources closer to users' end-devices. While most IoT services adopt a three-tier computing architecture, where fog nodes are always probed first before reaching a distant Cloud, collaboration across multi-stakeholder, multi-tenant fog providers remains unexplored. In this paper, we quantitatively highlight the gain which may arise if a collaborative fog computing paradigm is deployed. Next, we propose sol, an incentive-based collaborative mechanism for fog computing networks. solregulates a multi-stakeholder, multi-tenant cooperation among fog providers. We present a mathematical model and an experimental approach to make the case for such cooperation paradigm. © 2018 IEEE
- …
