IMDEA Networks Institute Digital Repository
Not a member yet
1915 research outputs found
Sort by
Making "Fast" Atomic Operations Computationally Tractable
Get PDFCommunication overhead is the most commonly used performance metric for the operation com- plexity of distributed algorithms in message-passing environments. However, aside with com- munication, many distributed operations utilize complex computations to reach their desired outcomes. Therefore, a most accurate operation latency measure should account of both compu- tation and communication metrics.
In this paper we focus on the efficiency of read and write operations in an atomic read/write shared memory emulation in the message-passing environment. We examine the operation com- plexity of the best known atomic register algorithm, presented in [2], that allows all read and write operations to complete in a single communication round-trip. Such operations are called fast. At its heart, the algorithm utilizes a predicate to allow processes to compute their outcome. We show that the predicate used in [2] is computationally hard, by devising a computationally equivalent problem and reducing that to Maximum Biclique, a known NP-hard problem. To improve the computational complexity of the algorithm we derive a new predicate that leads to a new algorithm, we call ccFast, and has the following properties: (i) can be computed in polyno- mial time, rendering each read operation in ccFast tractable compared to the read operations in the original algorithm, (ii) the messages used in ccFast are reduced in size, compared to the original algorithm, by almost a linear factor, (iii) allows all operations in ccFast to be fast, and (iv) allows ccFast to preserve atomicity. A linear time algorithm for the computation of the new predicate is presented along with an analysis of the message complexity of the new algorithm. We believe that the new algorithm redefines the term fast capturing both the communication and the computation metrics of each operation.TRUEpu
Tracking the evolution of intra-African traffic localization (Remote talk)
No full textBased on paris-traceroutes data collected from RIPE Atlas probes (from Nov. 2013 to Apr. 2014; June 2014 to Aug. 2014, and from Nov. 2014 to Feb. 2015), we tracked the evolution of intra-African traffic localization. We indeed looked for IXPs traversed by the AS paths, using information collected from public datasets (PeeringDB, PCHdata, IXP websites, etc.). We then evaluated the impacts of peering on the minimum RTT among ASes and compare the Quality of Service experienced by random end-users in Africa, Europe, and North America for communications between same countries.
After that, we presented a web platform displaying statistics such as the IP paths between any probe source and destination, the minimum RTT heat-map between any probes pair, the discovered IXPs in the dataset, etc. Such an application would allow stakeholders and engineers to have a view of the impact of their routing policies on the QoS experienced by end-users. We aim to get feedbacks from the AFPIF community before its release.TRUEpu
Failure Detectors in Homonymous Distributed Systems (with an Application to Consensus)
Get PDFThis paper is on homonymous distributed systems where processes are prone to crash failures and have no initial knowledge of the system membership (“homonymous” means that several processes may have the same identifier). New classes of failure detectors suited to these systems are first defined. Among them, the classes HΩ and HΣ are introduced that are the homonymous counterparts of the classes Ω and Σ, respectively. (Recall that the pair ⟨Ω, Σ⟩ defines the weakest failure detector to solve consensus.) Then, the paper shows how HΩ and HΣ can be implemented in homonymous systems without membership knowledge (under different synchrony requirements). Finally, two algorithms are presented that use these failure detectors to solve consensus in homonymous asynchronous systems where there is no initial knowledge of the membership. One algorithm solves consensus with ⟨HΩ,HΣ⟩, while the other uses only HΩ, but needs a majority of correct processes.
Observe that the systems with unique identifiers and anonymous systems are extreme cases of homonymous systems from which follows that all these results also apply to these systems. Interestingly, the new failure detector class HΩ can be implemented with partial synchrony1, while the analogous class AΩ defined for anonymous systems can not be implemented (even in synchronous systems). Hence, the paper provides the first consensus algorithm for anonymous systems with this model of partial synchrony and a majority of correct processes.pu
Underwater radiocommunications: An alternative to acoustics?
Get PDFProyecto UNDERWORLD:
UNDERWater radiocommunications for Optimized monitoring using multiReLay Devices
Radiocomunicaciones optimizadas submarinas usando dispositivos repetidores para aplicaciones de monitorización
Event location: Plataforma Oceánica de Canarias
Carretera de Taliarte s/n, 35214 Telde, Gran Canaria, Islas CanariasRadio-frequency communications are recently being re-evaluated for the purpose of transmitting digital data under water. However, the conductivity of ocean waters as well as fresh waters tends to quickly dissipate the power of a radiating radio wave, confining the communication range within a few tens of cm, and requiring careful design of antennas, physical layer modulation techniques and of the system as a whole.
In this talk, we will address the vision of IMDEA Networks on radio communications under water, review a few recent underwater applications whose challenges could be at least partially addressed via radio-frequency communications, and discuss relevant previous work and current efforts related to this topic.
The bottom line of the presented arguments is that, compared to optical and acoustic communications, underwater digital radio communications constitute a comparatively newer research area. However, if the technology will be sufficiently researched and developed, this technology is very likely to provide a good solution to a set of practical communication and operational problems found in underwater static and mobile networks.TRUEpu
Distributed mobility management for future 5G networks: overview and analysis of existing approaches
Get PDFThe ever-increasing demand of mobile Internet traffic is pushing operators to look for solutions to increase the available bandwidth per user and per unit of area. At the same time, they need to reduce the load in the core network at a reasonable cost in their future 5G deployments. Today's trend points to the deployment of extremely dense networks in order to provide ubiquitous connectivity at high data rates. However, this is hard to couple with the current mobile networks architecture, which is heavily centralized, posing difficult challenges when coping with the foreseen explosion of mobile data. Additionally, future 5G networks will exhibit disparate types of services, posing different connectivity requirements. Distributed mobility management is emerging as a valid framework to design future mobile network architectures, taking into account the requirements for large traffic in the core and the rise of extremely dense wireless access networks. In this article, we discuss the adoption of a distributed mobility management approach for mobile networks, and analyze the operation of the main existing solutions proposed so far, including a first practical evaluation based on experiments with real Linux-based prototype implementations.pu
LabVIEW based Software-Defined Physical/MAC layer architecture for prototyping dense LTE Networks
Get PDFWe propose to adopt and extend the Software Defined Networking (SDN) paradigm to manage interference within dense heterogeneous deployments of wireless network cells. Specifically, we present a network architecture and the initial research results we have achieved by using software-defined physical and MAC layers to build a small scale LTE testbed. To build the testbed presented in this paper, we have used LabVIEW and the open-source NS-3 LENA LTE stack for real time emulation of dense deployments. The testbed has been designed to serve as a powerful validation and demonstration tool for algorithms pro- posed within the framework of the CROWD project for tack- ling the challenges of dense and heterogeneous wireless deployments. Our testbed specifically allows to study the performance of cross layer PHY/MAC control algorithms within a realistic cellular environment.TRUEpu
Persistence and Availability of Floating Content in a Campus Environment
Get PDFThis work presents the first experimental evaluation of the Floating Content (FC) communication paradigm in a campus/large office setting. By logging information transfer events we have characterized mobility patterns, and we have assessed the performance of services implemented using the FC paradigm. Our results unveil the key relevance of group dynamics in user movements for the FC performance. Surprisingly, in such an environment, our results show that a relatively low user density is enough to guarantee content persistence over time, contrarily to predictions from available models. Based on these experimental findings, we develop a novel simple analytical model that accounts for the peculiarities of the mobility patterns in such a setting, and that can accurately predict the effectiveness of FC for the implementation of services in a campus/large office setting.TRUEpu
Service Mobility in Mobile Networks
Get PDFIn the current mobile network architecture, network traffic between user equipment (UE) and services deployed on the public cloud is tromboned towards the anchor point which could lead to network congestion. Deploying services closer to the UE, for example near the eNodeB, is a potential solution. The services are deployed on small scale data centers connected to, or collocated with the eNodeB, called ’eNodeB-Cloud’ (eNBC). Mobility of UEs presents a challenge for deploying services in an eNBC. When the UE is handed over from one eNodeB to another, seamless migration of UE context between the service instances running in different eNBCs needs to be ensured.
In this paper, we propose a Platform as a Service framework to enable UE context migration between eNBCs. The architecture consists of handover signaling mechanism, TCP session migration technology, context transfer protocol and a set of APIs towards the service. An evaluation of the prototype implementation shows that on an average the time taken to migrate a UE context between two eNBCs is in the order of 12 ms, which is within the limit of handover interruption time between two eNodeBs.TRUEpu
ALAS-KA: A learning analytics extension for better understanding the learning process in the Khan Academy platform
Get PDFThe Khan Academy platform enables powerful on-line courses in which students can watch videos, solve exercises, or earn badges. This platform provides an advanced learning analytics module with useful visualizations. Nevertheless, it can be improved. In this paper, we describe ALAS-KA, which provides an extension of the learning analytics support for the Khan Academy platform. We herein present an overview of the architecture of ALAS-KA. In addition, we report the different types of visualizations and information provided by ALAS-KA, which have not been available previously in the Khan Academy platform. ALAS-KA includes new visualizations for the entire class and also for individual students. Individual visualizations can be used to check on the learning styles of students based on all the indicators available. ALAS-KA visualizations help teachers and students to make decisions in the learning process. The paper presents some guidelines and examples to help teachers make these decisions based on data from undergraduate courses, where ALAS-KA was installed. These courses (physics, chemistry, and mathematics) for freshmen were developed at Universidad Carlos III de Madrid (UC3M) and were taken by more than 300 students.pu
Demo: Media Download Optimization through Prefetching and Resource Allocation in Mobile Networks
Get PDFMobile network operators are expected to face significant traffic increase in the upcoming years. One alternative method is to intelligently move transmissions to times of network underutilization, either on 3G/4G or by offloading to WiFi. Video content, predicted by Cisco to constitute 69% of mobile traffic, offers the greatest potential for offloading. To this end, the demonstrated app strives to relieve the mobile network in a two ways. First, long-term prefetching of promising videos based on posts from the user’s Online Social Network feed is performed. The knowledge about which video is likely being requested in the near future offers the opportunity to schedule the transmission according to its probability of being watched. Second, the approach is complemented with short-term prefetching, which is used whenever a content could not be downloaded by long-term prefetching. In this case, resources are optimized so as to maximize the communication efficiency while preserving the quality of service. The demonstrated app considers the smartphone’s observed cellular network history to optimize the mobile throughput. A customized video player implements both the long-term and short-term prefetching. It reduces both the load on mobile networks, decreases playback pausing events and hereby achieves a high QoE. Thus, the player addresses both the operators’ and the users’ needs.TRUEpu