IMDEA Networks Institute Digital Repository
Not a member yet
1915 research outputs found
Sort by
Combining Graphs and Big Data to Recommend Apps
Get PDFRecommendation engines (RE) are becoming highly popular, e.g., in the area of e-commerce. A RE offers new items (products or content) to users based on their profile and historical data. The most popular algorithms used in RE are based on collaborative filtering. This technique makes recommendations based on the past behavior of other users and the similarity between users and items. Metrics used for the computation of similarity include Euclidean distance, cosine distance, and correlation based distances. We have examined alternative similarity definitions based on the properties of the networks formed by users and items. The evaluated similarity metrics use graph theoretic concepts like the degree, several centrality measures, and ow maximization. In this paper we present how the techniques proposed have been evaluated in a real environment for the recommendation of applications to smartphone users. Training the RE required the pre-processing of a large dataset consisting of around 1 billion records. A big data environment, based on Hadoop/Elastic Map Reduce, HBase, and Pig was set up for building and processing the application and user graphs. The big data environment reduced the processing time from more than one week in a single machine, to a couple of hours in the Hadoop cluster. Hence, the application of big data techniques allows a near real-time re-training of the RE.FALSEpu
Cooperative Device-to-Device Communications Achieve Maximum Throughput and Maximum Fairness in Cellular Networks
Get PDFOpportunistic schedulers such as MaxRate and Proportional Fair are known for trading off throughput and fairness of users in cellular networks. In this paper we show how to achieve maximum fairness without sacrificing throughput. We propose a novel solution that integrates opportunistic scheduling design principles and cooperative device-to-device communication capabilities in order to improve both fairness and capacity in cellular networks. We develop a mathematical approach and design a smart tie-breaking mechanism which enhances the fairness achieved by the MaxRate scheduler. We show that users that cooperatively form clusters benefit from both higher throughput and fairness. Our scheduling mechanism is simple to implement and scales linearly with the number of clusters, and is able to achieve equal or better fairness than Proportional Fair schedulers.pu
Queueing systems to study the energy consumption of a campus WLAN
Get PDFIn this paper we exploit simple approximate queueing models to assess the effectiveness of the approaches that have been proposed to save energy in dense wireless local area networks (WLANs), based on the activation of access points (APs) according to the user demand. In particular, we look at a portion of a dense WLAN, where several APs are deployed to provide sufficient capacity to serve a large number of active users during peak traffic hours. To increase capacity, some APs are colocated and provide identical coverage; we say that these APs belong to the same group, and they serve users in the same area. The areas covered by different AP groups only partially overlap, so that some active users can only be served by a group of APs, but a fraction of active users can be served by more groups. Due to daily variations of the number of active users accessing the WLAN, some APs can be switched off to save energy when not all the capacity is needed. A real example of this setting is provided by a floor of one building of Politecnico di Torino in Italy, where a student library is located. The approximate analytical models indicate that the energy saving achievable with the proposed approaches is quite substantial, over 40% if at least one AP for each group is always kept on, even with no traffic, to be ready to accept incoming users, and it grows to almost 60% if all APs can be switched off at night, using a separate technology to activate an AP when the first user requests association in the morning.TRUEpu
A System for the Detection of Limited Visibility in BGP
Get PDFThe performance of the global routing system is vital to thousands of entities operating the Autonomous Systems (ASes) which make up the Internet. The Border Gateway
Protocol (BGP) is currently responsible for the exchange of reachability information and the selection of paths according to their specified routing policies. BGP thus enables traffic to flow from any point to another connected to the Internet. The manner traffic flows is often influenced by entities in the Internet according to their preferences. The latter are implemented in the form of routing policies by tweaking BGP configurations. Routing policies are usually complex and aim to achieve a myriad goals, including technical, economic and political purposes. Additionally, individual network managers need to
permanently adapt to the interdomain routing changes and, by engineering the Internet traffic, optimize the use of their network.
Despite the flexibility offered, the implementation of routing policies is a complicated process in itself, involving fine-tuning operations. Thus, it is an error-prone task and operators might end up with faulty configurations that impact the efficacy of their strate-
gies or, more importantly, their revenues. Withal, even when correctly defining legitimate routing policies, unforeseen interactions between ASes have been observed to cause important disruptions that affect the global routing system. The main reason behind this resides in the fact that the actual inter-domain routing is the result of the interplay of many routing policies from ASes across the Internet, possibly bringing about a different
outcome than the one expected.
In this thesis, we perform an extensive analysis of the intricacies emerging from the complex netting of routing policies at the interdomain level, in the context of the current operational status of the Internet. Abundant implications on the way traffic flows in the Internet arise from the convolution of routing policies at a global scale, at times resulting in ASes using suboptimal ill-favored paths or in the undetected propagation of configuration errors in the routing system. We argue here that monitoring prefix visibility at the interdomain level can be used to detect cases of faulty configurations or backfired routing policies, which disrupt the functionality of the routing system. We show that the lack of global prefix visibility can offer early warning signs for anomalous events which,
despite their impact, often remain hidden from state of the art tools. Additionally, we show that such unintended Internet behavior not only degrades the efficacy of the routing policies implemented by operators, causing their traffic to follow ill-favored paths, but can also point out problems in the global connectivity of prefixes.
We further observe that majority of prefixes suffering from limited visibility at the interdomain level is a set of more-specific prefixes, often used by network operators to
fulfill binding traffic engineering needs. One important task achieved through the use of routing policies for traffic engineering is the control and optimization of the routing function in order to allow the ASes to engineer the incoming traffic. The advertisement of more-specific prefixes, also known as prefix deaggregation, provides network operators with a fine-grained method to control the interdomain ingress traffic, given that the longest-prefix match rule over-rides any other routing policy applied to the covering less specific prefixes.
Nevertheless, however efficient, this traffic engineering tool comes with a cost, which is usually externalized to the entire Internet community. Prefix deaggregation is a known reason for the artificial inflation of the BGP routing table, which can further affect the
scalability of the global routing system. Looking past the main motivation for deploying deaggregation in the first place, we identify and analyze here the economic impact of
this type of strategy. We propose a general Internet model to analyze the effect that advertising more-specific prefixes has on the incoming transit traffic burstiness. We show that deaggregation combined with selective advertisements (further defined as strategic deaggregation) has a traffic stabilization side-effect, which translates into a decrease of the transit traffic bill. Next, we develop a methodology for Internet Service Providers (ISPs)
to monitor general occurrences of deaggregation within their customer base. Furthermore, the ISPs can detect selective advertisements of deaggregated prefixes, and thus identify customers which may impact the business of their providers. We apply the proposed methodology on a complete set of data including routing, traffic, topological and billing information provided by an operational ISP and we discuss the obtained results.Telematics EngineeringUniversidad Carlos III de Madrid, Spainpu
Distributed Mobility Management solutions for next mobile network architectures
Get PDFThe architecture of current operator infrastructures
is being challenged by the non-stopping growing demand of
data hungry services appearing every day. Deployed operator
networks are focused on providing mobile services to users,
relying on hierarchical architectures and protocols, such as
Proxy Mobile IP, which force all the traffic to and from the
terminals to traverse specific gateways connecting the network to the Internet. Such approaches pose several scalability problems when dealing with high demanding users. This has triggered to study how to provide mobility services in a flatter network architecture, enabling local access to the Internet, in order to reduce the amount of traffic traversing the core. Due to the novelty of these ideas, several possible solutions are being discussed and evaluated. This work aims at comparing the three more prominent families of solutions currently discussed at the
IETF, providing an analysis of their scalability characteristics, both from an analytic and experimental point of view.Telematics EngineeringUniversidad Carlos III de Madrid, Spainpu
Topology Independent Fast Reroute using Segment Routing
Get PDFThis document presents Topology Independent Loop-free Alternate Fast Re-route (TI-LFA), aimed at providing link and node protection of node and adjacency segments within the Segment Routing (SR) framework. This Fast Re-route (FRR) behavior builds on proven IP-FRR concepts being LFAs, remote LFAs (RLFA), and remote LFAs with directed forwarding (DLFA). It extends these concepts to provide guaranteed coverage in any IGP network. We accommodate the FRR discovery and selection approaches in order to establish protection over post-convergence paths from the point of local repair, dramatically reducing the operational need to control the tie-breaks among various FRR options.pu
ESPRES: Transparent SDN Update Scheduling
Get PDFNetwork forwarding state undergoes frequent changes, in
batches of forwarding rule modi�cations at multiple switches. Installing or modifying a large number of rules is time consuming given the performance limits of current programmable switches, which are also due to economical factors in addition to technological ones.
In this paper, we observe that a large network-state update
typically consists of a set of sub-updates that are independent of one another w.r.t. the traffic they affect, and hence sub-updates can be installed in parallel, in any order.
Leveraging this observation, we treat update installation as
a scheduling problem and design ESPRES, a runtime mechanism
that rate-limits and reorders updates to fully utilize
processing capacities of switches without overloading them.
Our early results show that compared to using no scheduler,
our schemes yield 2.17-3.88 times quicker sub-update completion time for 20th percentile of sub-updates and 1.27-1.57 times quicker for 50th percentile.TRUEpu
Models for the detection of emotions in the Khan Academy Platform
No full textMassive Open Online Courses (MOOCs) have grown up to the point of becoming a new learning scenario for the support of large amounts of students. Among current research efforts related to MOOCs, some are studying the application of well-known characteristics and technologies. An example of these characteristics is adaptation, in order to personalize the MOOC experience to the learner’s skills, objectives and profile. Several educational adaptive systems have emphasized the advantages of including affective information in the learner profile. Our hypothesis, based on theoretical models for the appraisal of emotions, is that we can infer the learner’s emotions by analysing their actions with tools in the MOOC platform. We propose four models, each to detect an emotion known to correlate with learning gains and they have been implemented in the Khan Academy Platform. This article presents the four models proposed, the pedagogical theories supporting them, their implementation and the result of a first user study.pu