IMDEA Networks Institute Digital Repository
Not a member yet
1915 research outputs found
Sort by
Temporal Connectivity of Vehicular Networks: The Power of Store-Carry-and-Forward
Get PDFStore-carry-and-forward is extensively used in vehicular
environments for many and varied purposes, including
routing, disseminating, downloading, uploading, or offloading delay-tolerant content. The performance gain of store-carryand-forward over traditional connected forwarding is primarily determined by the fact that it grants a much improved network connectivity. Indeed, by letting vehicles physically carry data, store-carry-and-forward adds a temporal dimension to the (typically fragmented) instantaneous network topology that is employed by connected forwarding. Temporal connectivity
has thus a important role in the operation of a wide range of vehicular network protocols. Still, our understanding of the dynamics of the temporal connectivity of vehicular networks is extremely limited. In this paper, we shed light on this underrated aspect of vehicular networking, by exploring a vast space of scenarios through an evolving graph-theoretical approach. Our results show that using store-carry-and-forward greatly increases connectivity, especially in very sparse networks. Moreover, using store-carry-and-forward mechanisms to share content within a geographically-bounded area can be very efficient, i.e., new entering vehicles can be reached rapidly.TRUEpu
On the Diversity of Interdomain Routing in Africa (Presentation)
No full textA summary of our research results has been published on RIPE Labs prior to this RIPE 70 meeting at https://labs.ripe.net/Members/fanou_roderick/on-the-diversity-of-interdomain-routing-in-africaFALSEpu
Dimensioning the Power Supply of a LTE Macro BS Connected to a PV Panel and the Power Grid
Get PDFThe use of solar energy to power base stations of cellular networks is becoming increasingly interesting, in both areas where the power grid is not present or not reliable, and where the power grid is ubiquitous and reliable, but energy costs keep growing. In this paper, we investigate the dimensioning of the photovoltaic panel and energy storage of a hybrid base station powering system that can exploit both solar and grid energy. The objective of the dimensioning is the minimization of the total capital and operational expenditures over a period of 10 years, accounting for the evolution of technology and traffic load. Results show that in a south European city like Torino, a hybrid base station powering system allows significant cost and size reductions, with respect to the case of solar energy only (and of a diesel power generator), and roughly equals the cost of the grid-only case in 8-9 years. When the extra energy produced by the solar panel can be sold back to the grid, the hybrid systems allow significant savings with respect to the grid-only case. For the city of Aswan, with a production that is much higher than in Torino and more constant over the year, costs of pure solar and hybrid systems are significantly lower in absolute terms; hybrid systems result to be still advantageous with respect to pure solar systems.TRUEpu
Efficient Interlayer Network Codes for Fair Layered Multicast Streaming
Get PDFMultilayer video streaming allows to provide different video qualities to a group of multicast receivers with heterogeneous receive rates. The number of layers received (and thus the receive rate) determines the quality of the decoded video stream. For such layered multicast streaming, network coding provides higher capacity than multicast routing. Network coding can be performed within a layer or across layers, and in general, interlayer coding outperforms intralayer coding. An optimal solution to a network-coded layered multicast problem may require decoding of the network code at interior nodes to extract information to be forwarded. However, decoding consumes resources and introduces delay, which is particularly undesirable at interior nodes (the routers) of the network. In this paper, we thus focus on the interlayer network coding problem without decoding at interior nodes. We show that the problem is NP-hard and propose a heuristic algorithm for rate allocation and coding based on the Edmonds–Karp maximum flow algorithm. We prove that our algorithm ensures decodability of the information received and provides some fairness properties. Finally, we perform extensive simulations and show that our algorithm may even outperform other heuristics that do require decoding at interior nodes.pu
Anticipatory Quality-Resource Allocation for Multi-User Mobile Video Streaming
Get PDFMobile video delivery forms the largest part of the traffic in cellular networks. Thus optimizing the resource allocation to satisfy a user's quality of experience is becoming paramount in modern communications. This paper belongs to the line of research known as anticipatory networking that makes use of prediction of wireless capacity to improve communication performance. In particular, we focus on the problem of optimal resource allocation for steady video delivery under maximum average quality constraints for multiple users. We formulate the problem as a piecewise linear program and provide a heuristic algorithm, which solution is close to optimal. Based on our formulation we are now able to trade off minimum video quality, average quality and offered network capacity.TRUEpu
Computing Minimal Update Sequences for Graceful Router-Wide Reconfigurations
Get PDFManageability and high availability are critical properties for IP networks. Unfortunately, with link-state routing protocols commonly used in such networks, topological changes lead to transient forwarding loops inducing service disruption. This reduces the frequency at which operators can adapt their network. Prior works proved that it is possible to avoid disruptions due to the planned reconfiguration of a link by progressively changing its weight, leading to a solution that does not require changing protocol specification. In this paper, we study the more general problem of gracefully modifying the logical state of multiple interfaces of a router, while minimizing the number of weight updates. Compared to single-link modifications, the router update problem is -dimensional for a router having neighbors. We also show that multidimensional updates may trigger new kinds of disruptions that make the problem more challenging than the single-link case. We then present and evaluate efficient algorithms that compute minimal sequences of weights enabling disruption-free router reconfigurations. Based on analysis of real IP network topologies, we show that both the size of such sequences and the computing time taken by our algorithms are limited.pu
A Mechanism for Fair Distribution of Resources with Application to Sponsored Search
Get PDFAs advertisement is shifting from the traditional media to the Internet, advertising in web search engines has
emerged in the form of sponsored search. Advertisers pay the search engine to show their content, usually in
order to get traffic to their own websites. A large amount of the search engine’s income derives from sponsored search. In sponsored search, a number of advertisers are competing for a limited number of slots in each
specific keyword search in the search engine. In order to distribute the available slots among the advertisers,
search engines are starting to hold keyword auctions. The questions that appear in this setup from a mechanism design point of view are two, how to assign advertisers to slots (or vice versa), and how to price each
slot. This work proposes a novel approach were distributing the slots among the advertisers is based on how
much each advertiser values appearing in a keyword search slot at a specific time. The proposed approach
makes this value independent of her true payment to the search engine, which can take the form of a flat fee.
For this purpose we have designed a new auction mechanism that fairly distributes resources (or goods, e.g.,
slots) in online fashion, based on the users’ declared preferences, while being socially efficient. While the
main motivation for this work was sponsored search, the proposed mechanism can be used in general for the
fair distribution of resources in an online fashion among a set of users. Hence, we refer to this mechanism as
Fair and Efficient Distribution of Resources (FEDoR). FEDoR can be used even when the auction is done in
a distributed fashion (i.e., without central authority), and it provides fairness, social efficiency and incentive
compatibility.TRUEpu
Structural Issues and Energy Efficiency in Data Centers
Get PDFWith the rise of cloud computing, data centers have been called to play a main role in the Internet scenario nowadays. Despite this relevance, they are probably far from their zenith yet due to the ever increasing demand of contents to be stored in and distributed by the cloud, the need of computing power or the larger and larger amounts of data being analyzed by top companies such as Google, Microsoft or Amazon.
However, everything is not always a bed of roses. Having a data center entails two major issues: they are terribly expensive to build, and they consume huge amounts of power being, therefore, terribly expensive to maintain. For this reason, cutting down the cost of building and increasing the energy efficiency (and hence reducing the carbon footprint) of data centers has been one of the hottest research topics during the last years. In this thesis we propose different techniques that can have an impact in both the building and the maintenance costs of data centers
of any size, from small scale to large flagship data centers.
The first part of the thesis is devoted to structural issues. We start by analyzing the bisection (band)width of a topology, of product graphs in particular, a useful parameter to compare and choose among different data center topologies. In that same part we describe the problem of
deploying the servers in a data center as a Multidimensional Arrangement Problem (MAP) and propose a heuristic to reduce the deployment and wiring costs.
We target energy efficiency in data centers in the second part of the thesis. We first propose a method to reduce the energy consumption in the data center network: rate adaptation. Rate adaptation is based on the idea of energy proportionality and aims to consume power on network
devices proportionally to the load on their links. Our analysis proves that just using rate adaptation we may achieve average energy savings in the order of a 30-40% and up to a 60% depending on the network topology.
We continue by characterizing the power requirements of a data center server given that, in order to properly increase the energy efficiency of a data center, we first need to understand how energy is being consumed. We present an exhaustive empirical characterization of the power
requirements of multiple components of data center servers, namely, the CPU, the disks, and the network card. To do so, we devise different experiments to stress these components, taking into account the multiple available frequencies as well as the fact that we are working with multicore servers. In these experiments, we measure their energy consumption and identify their optimal operational points. Our study proves that the curve that defines the minimal power consumption of the CPU, as a function of the load in Active Cycles Per Second (ACPS), is neither concave
nor purely convex. Moreover, it definitively has a superlinear dependence on the load. We also validate the accuracy of the model derived from our characterization by running different Hadoop applications in diverse scenarios obtaining an error below 4:1% on average.
The last topic we study is the Virtual Machine Assignment problem (VMA), i.e., optimizing how virtual machines (VMs) are assigned to physical machines (PMs) in data centers. Our
optimization target is to minimize the power consumed by all the PMs when considering that power consumption depends superlinearly on the load. We study four different VMA problems, depending on whether the number of PMs and their capacity are bounded or not. We study their complexity and perform an offline and online analysis of these problems. The online analysis is complemented with simulations that show that the online algorithms we propose consume substantially less power than other state of the art assignment algorithms.Telematics EngineeringUniversidad Carlos III de Madrid, Spainpu
On the Diversity of Interdomain Routing in Africa
Get PDFWith IP networking booming in Africa, promotion of BGP peering in the region emerge, and changes in the transit behavior of ISPs serving Africa are expected. However, little is known about the IP transit topology currently forming the African Internet. Enhancing the RIPE Atlas infrastructure, we evaluate the topology interconnecting ISPs based on the continent. We reveal a variety of ISP
transit habits, depending on a range of factors such as the official language or the business profile of the ISP. We highlight the emergence of IXPs in Africa, evaluating its impact on end-to-end connectivity. Our results however emphasize the remaining dominance of ISPs based outside Africa, for the provision of intracontinental paths. We study the impact of this aspect on AS path length and endto-
end delay. Such results illustrate that performing measurements from a broad, diversified, range of vantage points is necessary to assess interdomain routing on the continent.TRUEpu