IMDEA Networks Institute Digital Repository
Not a member yet
1915 research outputs found
Sort by
The effect of range and bandwidth on the round complexity in the congested clique model
Get PDFThe congested clique model is a message-passing model of distributed computation where players communicate with each other over a complete network. Here we consider synchronous protocols in which communication happens in rounds (we allow them to be randomized with public coins).
In the \emph{unicast} communication mode, each player has her own -bit input and may send different -bit messages through each of her communication links in each round. On the other end is the \emph{broadcast} communication mode, where each player can only broadcast a single message over all her links in each round. The goal of this paper is to complete our Brief Announcement at PODC 2015, where we initiated the study of the space that lies between the two extremes. For that purpose, we parametrize the congested clique model by two values: the \emph{range} , which is the maximum number of different messages a player is allowed to send in each round, and the \emph{bandwidth} , which is the maximum size of these messages. We show that the space between the unicast and broadcast congested clique models is very rich and interesting. For instance, we show that the round complexity of the pairwise set-disjointness function \textsc{pwdisj} is completely sensitive to the range .
This translates into a gap between the unicast () and the broadcast () modes. Moreover, provided that and , the round complexity of \textsc{pwdisj} is .
On the other hand, we also prove that the behavior of \textsc{pwdisj} is exceptional: almost every boolean function has maximal round complexity .
Finally, we prove that
is an upper bound for the gap between the round complexities with parameters and parameters of any boolean function.TRUEpu
Analysis of off-the-shelf Millimeter Wave Systems with Phased Antenna Arrays
Get PDFThis Master Thesis presents the paper ‘Boon and Bane of 60 GHz Networks: Practical Insights into Beamforming, Interference, and Frame Level Operation’ written by Thomas Nitsche, Guillermo Bielsa, Irene Tejado, Adrian Loch and Joerg Widmer. This paper was published in the conference ACM CoNEXT 2015, which took place at Heidelberg, Germany in December 2015.
The student was heavily involved in all the measurement campaigns presented in this work, including processing and writing the documentation about them. This makes possible for the student to present this work as his
Master Thesis.The performance of current consumer-grade devices for 60 GHz wireless networks is limited. While such networks promise both high data rates and uncomplicated spatial reuse, we find that commercially available devices based on the WiHD and WiGig standards may suffer from their cost-effective design. Very similar mechanisms are used in upcoming devices based on the IEEE 802.11ad standard. Hence, understanding them well is crucial to improve the efficiency and performance of next generation millimeter wave networks. In this paper, we present the first in-depth beamforming, interference, and frame level protocol analysis of off-the-shelf millimeter wave systems with phased antenna arrays. We focus on (a) the interference due to the lack of directionality of consumer-grade antennas, and (b) the degree of data aggregation of current devices. Regarding (a), our beam pattern measurements show strong side lobes that challenge the common conception of high spatial reuse in 60 GHz networks. We also show that reflections in realistic settings worsen this effect. Further, we measure weak directionality when beamforming towards the boundary of the transmission area of an antenna array. Regarding (b), we observe that devices only aggregate data if connections require high bandwidth, thus increasing medium usage time otherwise.Signal Theory and CommunicationsUniversidad Carlos III de Madrid, Spainpu
Auditing Methodology to Asses the Quality of Online Display Advertising Campaigns
Get PDFThe reported lack of transparency of the online advertising market may seriously affect the interests of advertisers. In this paper, we present a novel methodology that allows advertisers to independently assess the quality of display advertising campaigns. This methodology also serves to audit the accuracy and completeness of reports delivered by the vendor responsible for running a campaign. We have applied our methodology in 8 display ad campaigns configured in Google AdWords, which overall produced 160K ad impressions displayed in more than 7K publishers. Our results reveal that AdWords seems to provide incomplete information to advertisers. In the case of our campaigns we found that: (i) AdWords did not report 57% of publishers where ad impressions from our campaigns were delivered, (ii) AdWords reports a significantly larger fraction of impressions delivered to contextually meaningful publishers than our auditing methodology (iii) higher CPM investment does not provide guarantees to get impressions delivered to more popular publishers, (iv) AdWords does not offer default control of frequency cap (i.e., the number of impressions of the same ad delivered to a user), (v) around 10% ad impressions delivered in two of the ad campaigns were related to fraud. These findings should contribute to open a debate between advertisers and Ad Tech vendors to standardize the utilization of independent auditing methodologies as the one presented in this work.Telematics EngineeringUniversidad Carlos III de Madrid, Spainpu
Greening the Airwaves With Collaborating Mobile Network Operators
Get PDFBase station sharing is currently considered one of the most promising solutions for reducing the energy consumption costs of cellular networks. This paper presents a game theoretic framework for the study of such cooperative solutions where different mobile network operators (MNOs) decide to switch OFF subsets of their base stations during off-peak hours and roam their traffic to the remaining stations. The solution is based on a detailed optimization framework that determines exactly which base stations should remain active and how much traffic each one of them should serve, so as to maximize the aggregate energy savings. Accordingly, using the axiomatic Shapley value rule, it is determined how the benefits from the cooperation, i.e., the cost savings, should be dispersed among the cooperating MNOs. It is proved that this coalitional game with transferrable utilities has a nonempty core, and thus there exists a cooperation solution that incentivizes the participation of all operators. Moreover,using a thorough numerical analysis, it is shown that the benefits achieved with the implementation of the cooperation strategy depend mainly on the power consumption characteristics of the MNOs, which in turn are related to the number, type, and technology of their base stations. Overall, the energy savings are found to be most sensitive to the technology of the used base stations, and more precisely to the no-load base station energy consumption which defines the energy waste in a network.pu
Practical Lower Layer 60 GHz Measurements Using Commercial Off-The-Shelf Hardware
Get PDFExperimenting platforms for wireless 60 GHz networking measurements are limited and extremely costly. The requirements for such a platform in terms of bandwidth and antenna capabilities are very high. For instance, the 802.11 ad protocol uses channels with a bandwidth of 2.16 GHz and requires electronically steerable phased antenna arrays. Devices implementing this protocol are available as consumer-grade off-the-shelf hardware but are typically a black box which barely allows any insights for research purposes. In this paper, we show the hidden monitoring capabilities of such a consumer-grade 60 GHz device, and explain how to access lower layer parameters such as modulation and coding schemes, antenna steering, and packet decoding. Moreover, we present an extensive set of experiments showing the behavior of these parameters by means of the aforementioned monitoring capabilitiesTRUEpu
Mobility and connectivity in highway vehicular networks: A case study in Madrid
Get PDFThe performance of protocols and architectures for upcoming vehicular networks are commonly investigated by means of computer simulations, due to the excessive cost and complexity of large-scale experiments. Dependable and reproducible simulations are thus paramount to a proper evaluation of vehicular networking solutions. Yet, we lack today a reference dataset of vehicular mobility
scenarios that are realistic, publicly available, heterogeneous, and that can be used for networking simulations straightaway. In this paper, we contribute to the endeavor of developing such a reference dataset, and present original synthetic traces that are generated from high-resolution real-world traffic counts. They describe road traffic in quasi-stationary state on three highways near Madrid, Spain, for different time-spans of several working days. To assess the potential impact of the traces on networking studies, we carry out a comprehensive analysis of the vehicular network topology they yield. Our results highlight the significant variability of the vehicular connectivity over time and space, and its invariant correlation with the vehicular density. We also underpin the dramatic influence of the communication range on the network fragmentation, availability, and stability, in all of the scenarios we consider.TRUEpu
Challenges and Solutions for Millimeter-Wave Wireless Networks
No full textOne of the most promising options to significantly increase data rates in future wireless networks is to vastly increase the communication bandwidth. Such very high bandwidth channels are only available in the extremely high frequency part of the radio spectrum, the millimeter wave band (mm-wave). Upcoming communication technologies, for example IEEE 802.11ad, are already starting to exploit this part of the radio spectrum to achieve data rates of several GBit/s. mm-wave communication is also discussed as key technology for 5G mobile networks. However, communication at such high frequencies also suffers from high attenuation and signal absorption, often restricting communication to line-of-sight scenarios and requiring the use of highly directional antennas. This in turn requires a radical rethinking of wireless network design. On the one hand side, such channels experience little interference, allowing for a high degree of spatial reuse and potentially simpler MAC and interference management mechanisms. On the other hand, such an environment is extremely dynamic and channels may appear and disappear over very short time intervals, in particular for mobile devices. It is essential to take these characteristics into account to design efficient wireless architectures. The talk will highlight main challenges and possible solutions for networking in the mm-wave band.FALSEpu
Estimating the Real with the Virtual: How does the Accuracy Relate to the Internet Penetration?
Get PDFDirect measurements of the real world are typically
expensive and time-consuming. Recent studies have revealed the promising quick alternative where real-world characteristics are indirectly estimated based on data readily available in the Internet. Such methods for indirect virtual-world estimation of real-world properties rely on the implicit hypothesis that the estimation accuracy depends on how extensively the Internet penetrates into the real world. Our paper makes the first step towards validating this hypothesis. We adopt a simple statistical model to quantify the relationship between an index of consumer prices and online searches for respective categories of goods and services across 19 countries. We also show how the strength of this relationship depends on Internet-penetration and other socioeconomic variables.TRUEpu
Markovian models of solar power supply for a LTE macro BS
Get PDFDOI: 10.1109/ICC.2016.7510698We consider a solar power supply for a LTE macro base station (BS) based on a photovoltaic (PV) panel and a battery, and we develop two discrete-time Markov chain (DTMC) models for the analysis and the dimensioning of the system elements (PV panel size and battery capacity). The DTMC models account for the solar irradiance levels in pairs or triples of consecutive days, and for the quantity of energy stored in the battery. From the DTMC steady-state (or transient) solution it is possible to derive performance metrics on which the system dimensioning can be based. We apply our models to BS locations in southern and northern Italy. Results show that the simpler model contains sufficient details for an effective system design.TRUEpu
Evaluation of Self-Positioning Algorithms for Time-of-Flight based Localization
Get PDFSelf-localization systems based on the Time-of-Flight (ToF) of radio signals are highly susceptible to noise and their performance therefore heavily rely on the design and parametrization of robust algorithms. In this work, we study the noise sources of GPS and WiFi ToF ranging techniques and compare the performance of different self-positioning algorithms at a mobile node using those ranges. Our results show that the localization error varies greatly depending on the ranging technology, algorithm selection, and appropriate tuning of the algorithms. We characterize the localization error using real-world measurements and different parameter settings to provide guidance for the design of robust location estimators in realistic settings.TRUEpu