IMDEA Networks Institute Digital Repository
Not a member yet
1915 research outputs found
Sort by
An SDR-based Experimental Study of Outband D2D Communications
Get PDFBest-in-session presentation award.Device-to-Device communications represent a paradigm shift in cellular networks. Analytical results on D2D performance are very promising, but there is no experimental evidence that validates these results to date. This paper is the first to provide an experimental analysis of outband D2D schemes. Moreover, we design DORE, a complete framework for handling channel opportunities offered by outband D2D relay nodes. DORE consists of resource allocation optimization tools and protocols suitable to integrate QoS-aware opportunistic D2D communications within the architecture of 3GPP Proximity-based Services. We implement DORE using an SDR framework to profile cellular network dynamics in presence of opportunistic outband D2D communication schemes. Our experiments reveal that outband D2D communications are suitable for a large variety of delay-sensitive cellular applications, and that DORE enables notable gains even with a few active D2D relay nodes.TRUEpu
BASEL (Buffer mAnagement SpEcification Language)
Get PDFBuffering architectures and policies for their efficient management constitute one of the core ingredients of a network architecture. In this work we introduce a new specification language, BASEL, that allows to express virtual buffering architectures and management policies representing a variety of economic models. BASEL does
not require the user to implement policies in a high-level language; rather, the entire buffering architecture and its policy are reduced to several comparators and simple functions. We show examples of buffer management policies in BASEL and demonstrate empirically the impact of various settings on performance.TRUEpu
Optimization of Energy Efficiency in Data and Web Hosting Centers
Get PDFFor what concerns networking utilization the work focuses on Energy Efficient Ethernet (EEE) - IEEE 802.3az standard - which is the energy-aware alternative to legacy Ethernet, and an important component of current and future green data centers. More specifically the first contribution of this thesis consists in deriving and analytical model of gigabit EEE links with coalescing using M/G/1 queues with sleep and wake-up periods. Packet coalescing has been proposed to save energy by extending the sojourn in the Low Power Idle state of EEE. The model presented in this thesis approximates with a good accuracy both the energy saving and the average packet delay by using a few significant traffic descriptors. While coalescing improves by far the energy efficiency of EEE, it is still far from achieving energy consumption proportional to traffic. Moreover, coalescing can introduce high delays. To this extend, by using sensitivity analysis the thesis evaluates the impact of coalescing timers and buffer sizes, and sheds light on the delay incurred by adopting coalescing schemes. Accordingly, the design and study of a first family of dynamic algorithms, namely measurement-based coalescing control (MBCC), is proposed. MBCC schemes tune the coalescing parameters on-the-fly, according to the instantaneous load and the coalescing delay experienced by the packets. The thesis also discusses a second family of dynamic algorithms, namely NT-policy coalescing control (NTCC), that adjusts the coalescing parameters based on the sole occurrence of timeouts and buffer fill-ups. Furthermore, the performance of static as well as dynamic coalescing schemes is investigated using real traffic traces. The results reported in this work show that, by relying on run-time delay measurements, simple and practical MBCC adaptive coalescing schemes outperform traditional static and dynamic coalescing while the adoption of NTCC coalescing schemes has practically no advantages with respect to static coalescing when delay guarantees have to be provided. Notably, MBCC schemes double the energy saving benefit of legacy EEE coalescing and allow to control the coalescing delay.
For what concerns server utilization, the thesis presents an exhaustive empirical characterization of the power requirements of multiple components of data center servers. The characterization is the second key contribution of this thesis, and is achieved by devising different experiments to stress server components, taking into account the multiple available CPU frequencies and the presence of multicore servers. The described experiments, allow to measure energy consumption of server components and identify their optimal operational points. The study proves that the curve defining the minimal CPU power utilization, as a function of the load expressed in Active Cycles Per Second, is neither concave nor purely convex. Instead, it definitively shows a superlinear dependence on the load. The results illustrate how to improve the efficiency of network cards and disks. Finally, the accuracy of the model derived from the server components consumption characterization is validated by comparing the real energy consumed by two Hadoop applications - PageRank and WordCount - with the estimation from the model, obtaining errors below 4:1%, on average.Telematics EngineeringUniversidad Carlos III de Madrid, Spainpu
Independent Auditing of Online Display Advertising Campaigns
Get PDFDOI:http://dx.doi.org/10.1145/3005745.3005752The 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. Specifically, we found that: (i) AdWords did not report 57% of publishers where ad impressions from our campaigns were delivered, (ii) AdWords reports a large
fraction of contextually meaningful impressions based on
(non-disclosed) criteria different from the publisher’s theme,(iii) higher CPM investment does not lead to get impressions delivered to more popular publishers, (iv) AdWords does not offer default control of frequency cap, (v) around 10% ad impressions in two of our campaigns were delivered to IP’s from Data Centers. The industry considers these IPs to be likely 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.TRUEpu
Online Scheduling in Fault-prone Systems: Performance Optimization and Energy Efficiency
Get PDFEveryone is familiar with the problem of online scheduling (even if they are not aware of it), from the way we prioritize our everyday decisions to the way a delivery service must decide on the route to follow in order to cover the ongoing requests. In computer science, this is a problem of even greater importance. This thesis considers two main families of online scheduling problems in computer science, and aims to provide an extended clear framework for their analysis, presenting at the same time some common characteristics that connect these problems.
The first and main family of online scheduling problems considered, is task scheduling in fault-prone computing systems. As the number of clients and the possibilities offered by the rapid development of computing systems, grow with time, the increase of demands of computationally-intensive tasks is inevitable. Uniprocessors are no longer capable of coping with the escalation of these demands, which among others, has led to the development of multicore-based parallel machines, Internet-based computing platforms and co-operational distributed systems. Nonetheless, the challenges of these systems, even of the simplest ones, are numerous: They have to deal with continuous dynamic requests from the clients, which are probably not of the same nature (require different amount of computational resources). The processing elements (i.e., machines) may suffer from unpredictable failures, either malicious or due to overload. Furthermore, depending on the size of these systems and the exact processing units, their power consumption may be of significant amount; even equal to the electricity needed for a small town. Hence, limiting their power consumption is another challenge.
To analyze such a system one must consider the online nature of the problem; the dynamic task arrivals (client requests) of different sizes (computational demands), and the unpredictable machine crashes and restarts (failures). It is important to give guarantees for the performance of the algorithms used in these systems, thus the thesis conducts worst-case competitive analysis and covers a significant level of the three dimensions of the problem. More precisely, it studies the effects of the number of machines, the number of different task sizes and the speed of the machines – which as will be explained through the thesis, affects the power consumption of the system – on the efficiency of online scheduling algorithms. As performance measures, this thesis uses the completed load, the pending load and the latency competitiveness of the algorithms. In some cases, it considers the long-term competitiveness versions of these measures as well.
One of the most important results shown, is that resource augmentation in the form of increasing the machine speedup, is necessary in order to achieve some competitiveness, or to reach optimal competitiveness. The sufficient amount of speedup is found, and online algorithms that achieve the desired competitiveness are proposed and analyzed. Apart from the algorithms designed, some of the most widely used algorithms in scheduling are also analyzed in the model considered for the first time; namely, Longest In System (LIS), Shortest In System (SIS), Largest Processing Time (LPT), and
Smallest Processing Time (SPT). Nonetheless, deciding on the best algorithm between them, is not easy. Each algorithm behaves better with respect to a different evaluation metric and under different model parameters.
The second family of problems considered, is packet scheduling over an unreliable wireless communication link. As claimed, these problems have a strong connection to the task scheduling problem, especially when considering one machine and no speedup, hence some of the results can be shared. A setting with a single pair of nodes is considered, connected through an unreliable wireless channel. The sending station transmits packets to a receiving station over the channel, which can be jammed and hence corrupt the packet being transmitted. First, worst-case scenarios are assumed for the channel jams, modeled by a malicious adversarial entity. The packet arrivals however, follow a stochastic distribution and competitive analysis of scheduling algorithms is pursued giving matching bounds for the most pessimistic scenarios of channel jams. The aim of the algorithms is to find the schedule (or order or transmission of the arriving packets) in order to maximize the asymptotic throughout, which corresponds to the long-term competitive ratio of total length of successfully transmitted packets.
Then, a slightly different problem is considered, assuming infinite amount of data to be transmitted over the same unreliable communication link. This time however, an adversarial entity with constrained power is assumed for the channel jams. The constrained power is modeled by an Adversarial Queueing Theory (AQT) approach, defined with two main parameters; p, the error availability rate, and o, the maximum batch of errors available to the adversary at any time. This is the first time AQT is used to model channel jams; it has been mostly used to model the packet arrivals in networking problems. In this problem, the scheduling algorithms must decide on the length of the packets to be transmitted, with the objective of maximizing the goodput rate; the rate of successfully transmitted load. It is seen, that even for the simplest settings, the analysis and results are not trivial.Telematics EngineeringUniversidad Carlos III de Madrid, Spainpu
CoVer-ability: Consistent Versioning in Asynchronous, Fail-Prone, Message-Passing Environments
Get PDFAn object type characterizes the domain space and
the operations that can be invoked on an object of that type. In this paper we introduce a new property for concurrent objects, we call coverability, that aims to provide precise guarantees on the consistent evolution of the version (and thus value) of an object. This new property is suitable for a variety of distributed objects,
including concurrent file objects, that demand operations to
manipulate the latest version of the object. To preserve the order of versions, traditional approaches use locking, compare-andswap (CAS), or linked-load/conditional-store (LL/SC) primitives to allow a single modification at a time on such objects. Such primitives however can be used to solve consensus, and thus are impossible to be implemented in an asynchronous, message passing environment with failures.
Coverability, relaxes the strong requirements imposed by stronger primitives, and allows us to define and implement consistent versioning in the aforementioned adversarial environment. In particular, coverability allows multiple operations to modify the same version of an object concurrently, leading to a set of different versions. Given an order of operations, coverability properties specify a single version in that set that any subsequent operation may modify, preserving this way the consistent evolution of the object. We first define versioned objects and then provide the specification of coverability. We then combine coverability with atomic guarantees to yield coverable
atomic read/write registers; we show that coverable registers cannot be implemented by similar types of registers, such as ranked-registers. Next, we show how coverable registers may be implemented by modifying an existing MWMR atomic register implementation, and we continue by showing that coverable registers may be used to implement basic (weak) read-modify-write and file objects.TRUEpu
Winning the I-COM Datascience Hackathon 2016
Get PDFI-COM is a global trade body focused on the use of marketing data & measurement to obtain business advantage. On the occasion of the 2016 I-COM global summit (a meeting venue for around 100 associations in 40 countries representing marketers, agencies and media owners), they organised the 2nd I-COM Data Science Hackathon, sponsored by Unilever and Twitter. The challenge? In 24 hours, the participant teams have to be able to predict trends, provided with a one-year twitter dataset.
In this talk, one of the Scientist-Level category winners will speak about his experience, the hackathon procedure, and how his team manage to win the contest, where teams from some of the leading marketing and data analytics companies were participating too.TRUEpu
An entropy-based methodology for detecting Online Advertising Fraud at scale
Get PDFProgrammatic online advertising allows advertisers to di-
versify their budget dynamically, set the desired context of
publishers content, and target a specific audience. Besides,
it is accessible to all budgets. Despite these notable benefits, programmatic advertising has the drawback of being highly exposed to fraud.
The detection of fraudulent activities is a difficult task due to the limited information exchanged between ad-networks
and the large volume of publishers and traffic sources (IPs). In general, identifying participants in ad-fraud requires a large effort, while recreating a fraudulent system from different IPs targeting new publishers is relatively easy.
In this paper, we propose an efficient and scalable solution
to deterministic ad-fraud. The traffic patterns of ad-fraud
bots can be identified using the concept of entropy from
information theory. We develop a normalized entropic score
to identify the domains involved in ad-fraud and the IPs
from which the ad-fraud bots operate. We also describe a
lightweight and scalable modular system for fraud mitigation
that allows not only to filter out evident fraud, but also
configure diffeerent levels of suspicious activity.
Given the complexity of evaluating the potential fraud,
the system is configurable letting advertisers to decide the
level of risk they are willing to take. As reducing the risk involves increasing the number of false positives, we propose a multi-level scheme with a bank of bloom filters with different price limits to soften the trade-off.Telematics EngineeringUniversidad Carlos III de Madrid, Spainpu
Resource location based on precomputed partial random walks in dynamic networks
Get PDFThe problem of finding a resource residing in a network node (the resource location problem) is a challenge in complex networks due to aspects as network size, unknown network topology, and network dynamics. The problem is especially difficult if no requirements on the resource placement strategy or the network structure are to be imposed, assuming of course that keeping centralized resource information is not feasible or appropriate. Under these conditions, random algorithms are useful to search the network. A possible strategy for static networks, proposed in previous work, uses short random walks precomputed at each network node as partial walks to construct longer random walks with associated resource information. In this work, we adapt the previous mechanisms to dynamic networks, where resource instances may appear in, and disappear from, network nodes, and the nodes themselves may leave and join the network, resembling realistic scenarios. We analyze the resulting resource location mechanisms, providing expressions that accurately predict average search lengths, which are validated using simulation experiments. Reduction of average search lengths compared to simple random walk searches are found to be very large, even in the face of high network volatility. We also study the cost of the mechanisms, focusing on the overhead implied by the periodic recomputation of partial walks to refresh the information on resources, concluding that the proposed mechanisms behave efficiently and robustly in dynamic networks.pu
How to Represent IPv6 Forwarding Tables on IPv4 or MPLS Dataplanes
Get PDFThe Internet routing ecosystem is facing substantial
scalability challenges on the data plane. Various “clean slate” architectures for representing forwarding tables (FIBs), such as IPv6, introduce additional constraints on efficient implementations from both lookup time and memory footprint perspectives due to significant classification width. In this work, we propose an abstraction layer able to represent IPv6 FIBs on existing IP and even MPLS infrastructure. Feasibility of the proposed representations is confirmed by an extensive simulation study on real IPv6 forwarding tables, including low-level experimental performance evaluation.TRUEpu