Search

Packet classification is a critical component in network appliances. Software Defined Networking and cloud computing update the rulesets frequently for flexible policy configuration. Tuple Space Search (TSS), implemented in Open vSwitch (OVS), achieves fast rule updating at the sacrifice of the classification rate. In TSS, each tuple is managed by a hash table and classifying a packet needs to go through all hash tables. Merging tuples can reduce the number of hash tables, but inevitably increases the hash conflicts that may even worsen the classification performance in some cases. No existing algorithm meets the need of both fast packet classification and online rule updating. In this paper, we propose Convolutional Neural Network (CNN)-based Range Partition (CRP) to achieve fast packet classification and online update simultaneously. CRP exploits CNN-based image recognition to quickly partition tuples into range spaces upon the change of ruleset distribution, which reduces hash operations while avoiding rule overlapping caused by hashing many rules to the same location of the hash table. Experimental results demonstrate that CRP achieves 3.2x classification speed and 4.2x update speed on average compared with state-of-the-art algorithms. We also implement CRP in OVS. The throughput of CRP-OVS is 10x that of native OVS.

Internet users heavily rely on web search engines for their intended information. The major revenue of search engines is advertisements (or ads). However, the search advertising suffers from fraud. Fraudsters generate fake traffic which does not reach the intended audience, and increases the cost of the advertisers. Therefore, it is critical to detect fraud in web search. Previous studies solve this problem through fraudster detection (especially bots) by leveraging fraudsters’ unique behaviors. However, they may fail to detect new means of fraud, such as crowdsourcing fraud, since crowd workers behave in part like normal users. To this end, this paper proposes an approach to detecting fraud in web search from the perspective of fraudulent keywords. We begin by using a unique dataset of 150 million web search logs to examine the discriminating features of fraudulent keywords. Specifically, we model the temporal correlation of fraudulent keywords as a graph, which reveals a very well-connected community structure. Next, we design DFW (detection of fraudulent keywords) that mines the temporal correlations between candidate fraudulent keywords and a given list of seeds. In particular, DFW leverages several refinements to filter out non-fraudulent keywords that co-occur with seeds occasionally. The evaluation using the search logs shows that DFW achieves high fraud detection precision (99%) and accuracy (93%). A further analysis reveals several typical temporal evolution patterns of fraudulent keywords and the co-existence of both bots and crowd workers as fraudsters for web search fraud.

Le 15 mai 2019, le president des Etats-Unis signait un ordre executif sur la « securisation des technologies de l’information et la communication et de la chaine logistique ». Cette initiative constitue une etape significative dans l’escalade de la guerre commerciale a laquelle se livrent les Etats-Unis et la Chine depuis janvier 2018. Mais d’autres considerations strategiques entrent en jeu. Durant l’annee 2018 et 2019, les Etats-Unis ont appuye de tout leur poids sur leurs alliees pour qu’a leur tour ils prennent des decisions d’interdiction similaires, particulierement a l’encontre de l’entreprise Huawei. L’interdiction de Huawei aux Etats-Unis doit se comprendre dans le cadre de la transition technologique des reseaux mobiles de la quatrieme generation (4G) vers la cinquieme (5G), dont les enjeux sont a la fois geopolitiques, technologiques et economiques. L’objectif de cet article est d’analyser le cas Huawei par une approche cyberstrategique et, par ce biais, d’etudier les tenants et aboutissants de la question hautement strategique des infrastructures critiques.

In the second half of the 2010s, the Arabian Peninsula experienced major foreign policy changes that suggested a reshuffling of the region as a security complex. This paper offers an analysis of the geography of Internet data routing in the Middle East in order to grasp cooperation in cyberspace among the States of the region and Israel. Our main hypothesis is that the architecture of connectivity can reveal the level of trust between data routing operators of different countries through existing cooperation and, then, by extension, this can serve as an indicator to measure cyber cooperation in the Middle East.

Websites use third-party ads and tracking services to deliver targeted ads and collect information about users that visit them. These services put users' privacy at risk, and that is why users' demand for blocking these services is growing. Most of the blocking solutions rely on crowd-sourced filter lists manually maintained by a large community of users. In this work, we seek to simplify the update of these filter lists by combining different websites through a large-scale graph connecting all resource requests made over a large set of sites. The features of this graph are extracted and used to train a machine learning algorithm with the aim of detecting ads and tracking resources. As our approach combines different information sources, it is more robust toward evasion techniques that use obfuscation or changing the usage patterns. We evaluate our work over the Alexa top-10K websites and find its accuracy to be 96.1% biased and 90.9% unbiased with high precision and recall. It can also block new ads and tracking services, which would necessitate being blocked by further crowd-sourced existing filter lists. Moreover, the approach followed in this paper sheds light on the ecosystem of third-party tracking and advertising., 9 pages, 7 figures, To appear in the 13th ACM Web Science Conference 2021 (WebSci '21), June 2021

In this paper, we argue that data routing is of geopolitical significance. We propose new methodologies to understand and represent the new forms of power rivalries and imbalances that occur within the lower layers of cyberspace, through the analysis of Eastern Ukraine. The Internet is a network of networks where each network is an Autonomous System (ASes). ASes are independent administrative entities controlled by a variety of actors such as governments, companies, and universities. Their administrators have to agree and communicate on paths followed by packets travelling across the Internet, which is made possible by the Border Gateway Protocol (BGP). Agreements between ASes are often confidential but BGP requires neighbouring ASes to interact with each other in order to coordinate routing through the constant release of connectivity update messages. These messages announce the availability (or withdrawal) of a sequence of ASes that can be followed to reach an IP address prefix. We select Eastern Ukraine as a case study as in 2020, six years after the beginning of the war in Donbass, data is available to analyze and map changes to data routing. In our study, we conducted a longitudinal analysis of Ukraine’s connectivity through the capture and analysis of these BGP announcements. Our results show how Donbass ASes progressively migrated from Ukraine’s cyberspace towards Russia, while still sharing connections with Ukrainian ASes. Donbass cyberspace therefore sits at the interface of Ukraine and Russia but has been relegated to the periphery of both networks; it is marginalized from the Ukrainian network but not fully integrated into the Russian network. These evolutions both reflect and affect ongoing geopolitical power rivalries in the physical world and demonstrate their strategic significance. Our methodology can be used to conduct studies in other regions subject to geopolitical open conflicts and to infer the strategies developed by states in anticipation of potential threats.

In November 2019, in the wake of political demonstrations against the regime, Iran managed to selectively cut off most traffic from the global Internet while fully operating its own domestic network. It seemingly confirmed the main hypothesis our research had led us to, based on prior observation of data routing: Iran’s architecture of connectivity enables selective censorship of international traffic. This paper examines, through the case of Iran, how states can leverage the Border Gateway Protocol (BGP) as a tool of geopolitical control and what are the trade-offs they face. This question raises a methodological question that we also address: how the analysis of BGP can infer and document these strategies of territorialization of cyberspace. The Internet is a network of networks where each network is an autonomous system. Autonomous systems (ASes) are independent administrative entities controlled by a variety of actors such as governments, companies and universities. Their administrators have to agree and communicate on the path followed by packets travelling across the Internet, which is made possible by BGP. Agreements between ASes are often confidential but BGP requires neighbouring ASes to interact with each other in order to coordinate routing through the constant release of connectivity update messages. These messages announce the availability (or withdrawal) of a sequence of ASes that can be followed to reach an IP address prefix. In our study, we inferred the structure of Iran's connectivity through the capture and analysis of these BGP announcements. We show how the particularities of Iran's BGP and connectivity structure can enable active measures, such as censorship, both internally and externally throughout the network. We argue that Iran has found a way to reconcile a priori conflicting strategic goals: developing a self-sustaining and resilient domestic Internet, but with tight control at its borders. It thus enables the regime to leverage connectivity as a tool of censorship in the face of social instability and as a tool of regional influence in the context of strategic competition.

Software-Defined Networking (SDN) facilitates net-work innovations with programmability. However, programming the network is error-prone no matter using low-level APIs or high-level programming languages. That said, SDN policies deployed in networks may contain misconfigurations. Prior studies focus on either traditional access control policies or network-wide states, and thus are unable to effectively detect potential misconfigurations in SDN policies with bitmask patterns and complex action behaviorsTo address this gap, this paper first presents a new data structure, minimal interval set, to represent the match patterns of rulesets. This representation serves the basis for composition algebra construction and fast misconfiguration checking. We then propose the principles and algorithms for fast and accurate con-figuration verification. We finally implement a misconfiguration checking tool in Covisor with optimisations to further reduce the overhead. Experiments with synthetic and random rulesets show its fitness for purpose.

This paper presents the results of a year-long research project conducted by GEODE (geode.science), a multidisciplinary team made up of geographers, computer scientists and area specialists.We developed a new methodology for mapping cyberspace in its lower layers (infrastructures and routing protocols) in order to measure and represent the level of fragmentation of the Internet in areas of geopolitical tensions using the Border Gateway Protocol (BGP). Our hypothesis was that BGP could be used for geopolitical reasons in the context of a large-scale crisis, leading to a further fragmentation of the Internet. We focused on the Ukrainian crisis.BGP is a core protocol of cyberspace that connects the tens of thousands of autonomous systems (ASes) that compose the Internet. Based on a 35-year-old technology, this protocol is easy to manipulate to re-route Internet traffic or even to cut off entire regions (BGP hijacks). Our results show actions on BGP implemented right after the 2014 Maidan Revolution, when Russian forces took control of the Crimean Peninsula and started to back separatist forces in Eastern Ukraine. In both cases, Russian authorities and separatist forces modified BGP routes in order to divert the local Internet traffic from continental Ukraine – drawing a kind of "digital frontline" consistent with the military one. The study of Donbass and of the Crimean Peninsula leads to important methodological findings to (1) define and map digital borders at the routing level; (2) analyze the strategies of actors conducting actions via BGP; (3) categorize these strategies, from traffic re-routing to cutting-off entire regions for intelligence or military purposes; and (4) anticipate future uses for BGP manipulations by identifying strategic bottlenecks within the network.

International audience; Ternary content addressable memories (TCAMs) are frequently used for fast matching of packets against a given ruleset. While TCAMs can achieve fast matching, they are plagued by high update costs that can make them unusable in a high churn rate environment. We present, in this paper, a systematic and in-depth analysis of the TCAM update problem. We apply partial order theory to derive fundamental constraints on any rule ordering on TCAMs, which ensures correct checking against a given ruleset. This theoretical insight enables us to fully explore the TCAM update algorithms design space, to derive the optimal TCAM update algorithm (though it might not be suitable to be used in practice), and to obtain upper and lower bounds on the performance of practical update algorithms. Having lower bounds, we checked if the smallest update costs are compatible with the churn rate observed in practice, and we observed that this is not always the case. We therefore developed a heuristic based on ruleset splitting, with more than a single TCAM chip, that achieves significant update cost reductions (1.05~11.3x) compared with state-of-the-art techniques.

International audience; Abstract:In mobile live streaming systems, user are fairly limited in interaction with the streaming objects due to the constraints coming from mobile devices and event-driven nature of live content. The constraints could lead to unique user behavior characteristics, which have yet to be explored. This paper investigates over 9 million access logs collected from the PPTV live streaming system, with an emphasis on the discrepancies that might exist when users access the live streaming catalog from mobile and non-mobile terminals. We observe a much higher likelihood of abandoning sessions by mobile users, and examine the structure of abandoned sessions from the perspectives of time of day, channel content and mobile device types. Surprisingly, we find relatively low abandonment rates during peak-load time periods and a notable impact of mobile device type (i.e. Android or iOS) on the abandonment behavior. To further capture the intrinsic characteristics of user behavior, we develop a series of models for session duration, user activity and time-dynamics of user arrivals/departures. More importantly, we relate the model parameters to physical and real-life meanings. The observations and models shed light on video delivery system, telco-CDNs and mobile applications.

Historical network traffic traces, both at the flow and packet level, play a significant role in many research and engineering areas, such as network security, traffic engineering and accounting. To retrieve the specific entries at a higher speed from large traces, each packet or flow should be indexed using multiple query fields during archiving. This brings challenges both in terms of archiving speed and storage consumption. We propose a network traffic indexing and querying method based on Index–Trie, to achieve fast archiving, low storage space of the indexes, and fast retrieval. We implemented a system for online trace archival and retrieval. Our experiments, performed both offline and online on backbone, campus and datacenter network traffic, demonstrate that our method outperforms the popular FastBit method. For packet traces, the Index–Trie based method can obtain an improvement up to 72% for the archiving rate, 56% lower storage consumption, and 14 times faster retrieving time. For flow traces, compared to FastBit, our system is up to 15 times faster in term of the archiving rate, 42% less storage, and 100 times faster retrieving speed. Furthermore, we extend the application of Index-Tries to log file indexing and retrieving.

Multi-Tenancy (MT) is critical for Network Function Virtualization (NFV) platform as it reduces the cost of having network services by sharing expensive server resource among customers. This is especially critical for memory and CPU intensive services like Network Intrusion Prevention System (NIPS). In this work, we explore the issue of deploying a large-scale virtualized NIPS service on a commercial NFV platform. We observe that the scalability of NIPS service is not good when based on independent Virtual Machines (VMs). We propose a Multi-Tenant Aho-Corasick state machine data structure (MT-AC) and adapt it into NIPS to solve the issue. One MT-AC based NIPS service simultaneously checks traffic belonging to different tenants against a merged ruleset. The MT-AC data structure is very efficient as it eliminates the redundancies among tenants' signatures during the rulesets merging. Experimental results with real-world ruleset show that, in comparison with an independent VM-based solution, the MT-AC based NIPS service can support 2 to 4 times more tenants. Moreover, the throughput and latency performance of MT-AC based NIPS engine only degrades by 1%, when the tenant count increases from 8 to 128. The results validate that, the proposed MT-AC based NIPS service on NFV platform can support a large amount of tenants with a very low cost.

International audience; Resource competition and conflicts in datacenter networks (DCNs) are frequent and intense. They become inevitable when mixing elephant and mice flows on shared transmission paths, resulting in arbitration between throughput and latency and performance degradation. We propose a novel flow scheduling scheme, Freeway, that leverages on path diversity in the DCN topology to guarantee, simultaneously, mice flow completion within deadline and high network utilization. Freeway adaptively partitions the available paths into low latency and high throughput paths and provides different transmission services for each category. A M/G/1-based model is developed to theoretically obtain the highest value of average delay over the path that will guarantee for 99% of mice flows their completion time before the deadline. Based on this bound, Freeway proposes a dynamic path partitioning algorithm to adjust dynamically with varying traffic load the number of low latency and high throughput paths. While mice flows are transmitted over low latency paths using a simple equal cost multiple path (ECMP) scheduling, Freeway load balances elephant flows on different high-throughput paths. We evaluate Freeway in a series of simulation on a large scale topology and use real traces. Our evaluation results show that Freeway significantly reduces the mice flows completion time within deadlines, while achieving remarkable throughput compared with current schemes. It is remarkable that Freeway does not need any change of DCN switch fabrics or scheduling algorithms and can be deployed easily on any generic datacenter network with switches implementing VLANs and trunking.

Web tracking plays a crucial role in the Web ecosystem. It relies on third-party tracking actors collecting user information that are used for various applications such as advertisement and analytics, etc. With the massive growth of the Internet, understanding the geography of tracking is of strategic importance. The goal of this paper is to propose a thorough investigation of web tracking inside China taking advantage of a large dataset ( 1 0 11 records) containing two days of full DNS access from a major ISP providing both mobile and landline ADSL. Our results show that a strong Pareto principle applies on the traffic toward trackers, with only 26 trackers, representing 90% of tracking activity. We then show that although most first-party sites accessed from China are owned by Chinese corporations, large proportion of trackers belong to US ones. This raises concerns about the advertisement industry in China, and more generally shed new lights on the international data flows, the interdependency of the main actors, and the complexity of the threats for both people and states.

Web tracking plays a crucial role in the Web ecosystem. It relies on third-party tracking domains collecting user information for various applications such as advertisement and analytics. With the massive growth of the Internet, understanding tracking and its geographical roots is of strategic importance. The goal of this paper is to propose a thorough investigation of web tracking inside China taking advantage of a large dataset (1011 records) containing two days of full DNS access from a major ISP providing both mobile and landline ADSL. Our results show that a power law applies on the traffic of both sites and trackers with a handful of trackers, 26, representing 90% of tracking activity. We then show that although most first-party sites accessed from China are owned by Chinese corporations, large proportion of trackers belong to US ones. This raises concerns about the analytics industry in China, and more generally shed new lights on the international data flows, the interdependency of the main actors, and the complexity of the threats for both people and states.

In Named Data Networking (NDN), there is a need for routing protocols to populate Forwarding Information Base (FIB) tables so that the Interest messages can be forwarded. To populate FIBs, clients and routers require some routing information. One method to obtain this information is that network nodes exchange routing information by each node advertising the available content objects. Bloom Filter-based Routing approaches like BFR [1], use Bloom Filters (BFs) to advertise all provided content objects, which consumes valuable bandwidth and storage resources. This strategy is inefficient as clients request only a small number of the provided content objects and they do not need the content advertisement information for all provided content objects. In this paper, we propose a novel routing algorithm for NDN called pull-based BFR in which servers only advertise the demanded file names. We compare the performance of pull-based BFR with original BFR and with a flooding-assisted routing protocol. Our experimental evaluations show that pull-based BFR outperforms original BFR in terms of communication overhead needed for content advertisements, average roundtrip delay, memory resources needed for storing content advertisements at clients and routers, and the impact of false positive reports on routing. The comparisons also show that pull-based BFR outperforms flooding-assisted routing in terms of average round-trip delay.

DNS is a critical component of Internet architecture. Almost all applications, in particular web based applications that constitute the large majority of current Internet traffic, leverage heavily on DNS. This makes DNS based measurements a promising tool for understanding global properties of Internet traffic, e.g., sites audience, traffic matrix. However, using passive DNS traces from local DNS servers is challenging because of DNS caching and NATs. The goal of this paper is twofold. First, we show how to correct the bias due to DNS cache and the wide use of NATs, to extract meaningful traffic information from DNS traces. The techniques are then used and validated over a large dataset (1011 records) containing two days of full DNS access from a major ISP providing both mobile and landline ADSL in China. Second, we focus on the tracking activity and show that although most sites accessed from China belong to Chinese corporations, most trackers belong to US ones. Mobile and ADSL platforms are alike.

International audience; Video delivery performance is the main factor that affects Internet video quality. Characterizing the video delivery performance, especially the delivery throughput, can help content providers as well as Internet service providers (ISPs) in system optimization and network planning. Based on a unique dataset consisting of 20 million video download speed measurements , this paper comprehensively studies the video delivery throughput of a large-scale commercial video-on- demand (VoD) system. We observe that user speed exhibits a large variation over time of day as well as across provincial locations. In particular, the worst performance of day is 30% lower than the peak performance . The analysis also reveals that video download speed has a notable impact on Internet video quality, which in turn influences user engagement . The impact, however, becomes limited when the speed increases beyond a certain threshold, which is mostly dependent on the video encoded bitrates. We further examine the interaction between Internet infrastructure and video delivery throughput using the linear regression model and find that crossing the ISP or regional network border yields 15-20% speed loss. Based on these observations , we finally evaluate the potential of edge caching and hybrid CDN-P2P in the improvement of video download performance and video quality.

Bloom filter-based routing protocols for Named Data Networking (NDN) aim at facilitating content discovery in NDN. In this paper, we compare the performance of two Bloom filterbased routing protocols, namely BFR and COBRA. BFR is a push-based routing protocol that works based on Bloom filterbased content advertisements, while COBRA is a pull-based routing protocol that operates based on route traces left from previously retrieved content objects, which are stored in Stable Bloom Filters. In this paper, we show that BFR outperforms COBRA in terms of average memory needed for storing routing updates, average round-trip delay, normalized communication overhead, total Interest communication overhead, and mean hit distance.

International audience; NFV together with SDN promises to provide more flexible and efficient service provision methods by decoupling the network functions (NFs) from the physical network topology and devices, but requires the real-time and automatic composition and verification for service function chain (SFC). However, most of SFCs today are still typically built through manual configuration processes, which are slow and error prone. In this paper, we present a novel SFC composition framework, called Automatic Composition Toolkit (ACT). It aims to automatically detect the dependencies and conflicts between NFs, so as to compose and verify SFCs before they are enforced on the physical infrastructure.

International audience; Mobile video is becoming extremely popular, and P2P mobile video platforms are being considered for large-scale deployment in this context. However, the design and deployment of realistic P2P video systems have to consider specific characteristics of mobile networks. In this article, we look from the viewpoint of a large-scale commercial P2P mobile video provider system, PPTV, and describe the implementation challenges of a P2P mobile video system over 3G networks. Our analysis is backed by real measurements and experience from PPTV. We extract from these measurements the characteristics of mobile videos and analyze their impact on P2P video systems. We also briefly discuss other practical issues in the design of a mobile P2P system for PPTV.

Locating the demanded content is one of the major challenges in Information-Centric Networking (ICN). This process is known as content discovery. To facilitate content discovery, in this paper we focus on Named Data Networking (NDN) and propose a novel routing scheme for content discovery, called Bloom Filter-based Routing (BFR), which is fully distributed, content oriented, and topology agnostic at the intra-domain level. In BFR, origin servers advertise their content objects using Bloom filters. We compare the performance of the proposed BFR with flooding and shortest path content discovery approaches. BFR outperforms its counterparts in terms of the average round-trip delay, while it is shown to be very robust to false positive reports from Bloom filters. Also, BFR is much more robust than shortest path routing to topology changes. BFR strongly outperforms flooding and performs almost equal with shortest path routing with respect to the normalized communication costs for data retrieval and total communication overhead for forwarding Interests. All the three approaches achieve similar mean hit distance. The signalling overhead for content advertisement in BFR is much lower than the signalling overhead for calculating shortest paths in the shortest path approach. Finally, BFR requires small storage overhead for maintaining content advertisements.

La cartographie du cyberespace represente un defi a la fois conceptuel et technique. La complexite et le caractere hautement dynamique de cet environnement necessitent le developpement de nouveaux outils intellec­tuels et cartographiques pour en representer les elements strategiques. Cet article, tire d’une etude exploratoire, propose un exemple d’approche cartogra­phique d’une des dimensions cyber d’un theâtre militaire classique et d’un adversaire etatique, a travers un cas precis : l’enjeu de la Siberie comme nouveau territoire strategique du cyberespace pour la Russie. La strategie russe de localisation des donnees s’inscrit dans une politique d’amenagement du territoire et traduit l’apprehension qu’ont les Russes de leur cyberespace : un vecteur de transmission d’informations devant etre soumis a un fort controle etatique.

NFV together with SDN provides the flexibility for NFs in the way that they are deployed and managed. The flexibility enables dynamical scale in and scale out through migrating in-process flows among NFs. Due to stateful packet processing in NFs, flow migration has to guarantee loss-free and order-preserving for both flow states and packets. Existing frameworks closely coupled state transfer and packets migration, and thus fail to achieve safe and efficient migration with low overhead. This paper presents our design and implementation of a distributed flow migration framework, Transparent Flow Migration (TFM). TFM completely decouples the state transfer and packets migrations. The decoupling allows us to optimize the two processes separately and run them in parallel. TFM implements various optimizations through the TFM box, a shim layer providing transparent packet migration to NFs. Our evaluation shows that TFM guarantees loss-free and order-preserving for both scale-in and scale-out flow migration, and outperforms existing approaches with 3× smaller migration time. Besides, TFM uses small overhead and has very limited impacts on throughput of live TCP flows.

International audience; Smartphones have become an important component of everyday's life. They store a large amount of users' private and sensitive information like contacts, GPS location, messages and interests. Privacy issues are a growing concern for the phone users. However, despite an existing rich literature in privacy leakage on mobile network measurement, our empirical knowledge of users' private leakage is relatively limited. In this work, we present a large scale and comprehensive investigation spanning over 9 months of users' private information leakage that consisted of monitoring 180K popular apps coming from 50+ Chinese AppStores. In order to do this, we used a customized platform that can monitor the execution of applications running over Android system to observe in vivo privacy leakage of applications. Our key findings are that: (1) Accessing users' private information is very common among mobile apps, i.e. over 90% of apps accesses some kind of user private information, and to our surprise, almost 95% apps claimed access to private information without concretely accessing them (2) We analyzed different category of Apps and observed slight differences in the pattern of access to private information among different categories (3) Downloading apps from big Appstores does not necessarily mean safer and more private apps. We observe that local Chinese shop and Google Play generate similar observations.

International audience; In Search Engine Marketing (SEM), “third-party” partners play an important intermediate role by bridging the gap between search engines and advertisers in order to optimise advertisers' campaigns in exchange of a service fee. In this paper, we present an economic analysis of the market involving a third-party broker in Google AdWords and the broker's customers. We show that in order to optimise his profit, a third-party broker should minimise the weighted average Cost Per Click (CPC) of the portfolio of keywords attached to customer's ads while still satisfying the negotiated customer's demand. To help the broker build and manage such portfolio of keywords, we develop an optimisation framework inspired from the classical Markowitz portfolio management which integrates the customer's demand constraint and enables the broker to manage the tradeoff between return on investment and risk through a single risk aversion parameter. We then propose a method to augment the keywords portfolio with relevant keywords extracted from trending and popular topics on Twitter. Our evaluation shows that such a keywords-augmented strategy is very promising and enables the broker to achieve, on average, four folds larger return on investment than with a non-augmented strategy, while still maintaining the same level of risk.

International audience; Proteins possess qualities of robustness and adaptability to perturbations such as mutations, but occasionally fail to withstand them, resulting in loss of function. Here the structural impact of mutations is investigated independently of the functional impact. Primarily, we aim at understanding the mechanisms of structural robustness, pre-requisite for functional integrity. The structural changes due to mutations propagate from the site of mutation to residues much more distant than typical scales of chemical interactions, following a cascade mechanism. This can trigger dramatic changes or subtle ones, consistent with a loss of function and disease, or the emergence of new functions. Robustness is enhanced by changes producing alternative structures, in good agreement with the view that proteins are dynamic objects fulfilling their functions from a set of conformations. This result, robust alternative structures, is also coherent with epistasis or rescue mutations, more generally with non-additive mutational effects and compensatory mutations. To achieve this study, we have developed the first algorithm, referred to as Amino Acid Rank (AAR), which follows the structural changes associated with mutations from the site of the mutation to the entire protein structure and quantifies the changes so mutations can be ranked accordingly. Assessing the paths of changes opens the possibility to assume secondary mutations for compensatory mechanisms.

International audience; Programmable routers supporting virtualization are a key building block for bridging the gap between new Internet protocols and their deployment in real operational networks. This article presents the design and implementation of PEARL, a programmable virtual router platform with relatively high performance. It offers high flexibility by allowing users to control the configuration of both hardware and software data paths. The platform makes use of fast lookup in hardware and software exceptions in commodity multicore CPUs to achieve highspeed packet processing. Multiple isolated packet streams and virtualization techniques ensure isolation among virtual router instances.

Network traffic modeling generally views traffic as a superposition of flows that creates a timeseries of volume counts (e.g. of bytes or packets). What is omitted from this view of traffic is the contents of packets. Packet contents (e.g. header fields) contain considerable information that can be useful in many applications such as change and anomaly detection, and router performance evaluation. The goal of this paper is to draw attention to the problem of modeling traffic with respect to the contents of packets. In this regard, we identify a new phenomenon: long range mutual information (LRMI), which means that the dependence of the contents of a pair of packets decays as a power of the lag between them. We demonstrate that although LRMI is hard to measure, and hard to model using the mathematical tools at hand, its effects are easy to identify in real traffic, and it may have a considerable impact on a number of applications. We believe that work in modeling this phenomenon will open doors to new kinds of traffic models, and new advances in a number of applications.

This paper addresses the issue of the security of Internet Coordinate Systems,by proposing a general method for malicious behavior detection during coordinate computations. We first show that the dynamics of a node, in a coordinate system without abnormal or malicious behavior, can be modeled by a Linear State Space model and tracked by a Kalman filter. Then we show, that the obtained model can be generalized in the sense that the parameters of a filtercalibrated at a node can be used effectively to model and predict the dynamic behavior at another node, as long as the two nodes are not too far apart in the network. This leads to the proposal of a Surveyor infrastructure: Surveyor nodes are trusted, honest nodes that use each other exclusively to position themselves in the coordinate space, and are therefore immune to malicious behavior in the system.During their own coordinate embedding, other nodes can thenuse the filter parameters of a nearby Surveyor as a representation of normal, clean system behavior to detect and filter out abnormal or malicious activity. A combination of simulations and PlanetLab experiments are used to demonstrate the validity, generality, and effectiveness of the proposed approach for two representative coordinate embedding systems, namely Vivaldi and NPS.

International audience; Streaming live content to mobile terminals has become prevalent. While there are extensive measurement studies of non-mobile live streaming (and in particular P2P live streaming) and video-on-demand (both mobile and non-mobile), user behavior in mobile live streaming systems is yet to be explored. This paper relies on over 4 million access logs collected from the PPTV live streaming system to study the viewing behavior and user activity pattern, with emphasis on the discrepancies that might exist when users access the live streaming system catalog from mobile and non-mobile terminals. We observe high rates of abandoned viewing sessions for mobile users and identify different reasons of that behavior for 3G-and WiFi-based views. We further examine the structure of abandoned sessions due to connection performance issues from the perspectives of time of day and mobile device types. To understand the user pattern, we analyze user activity distribution, user geographical distribution as well as user arrival/departure rates.

International audience; The Internet is currently experiencing one of the most important challenges in terms of content distribution since its first uses as a medium for content delivery: users from passive downloaders and browsers are moving towards content producers and publishers. They often distribute and retrieve multimedia contents establishing network communities. This is the case of peer-to-peer IPTV communities.In this work we present a detailed study of P2P IPTV traffic, providing useful insights on both transport- and packet-level properties as well as on the behavior of the peers inside the network. In particular, we provide novel results on the (i) ports and protocols used; (ii) differences between signaling and video traffic; (iii) behavior of the traffic at different time scales; (iv) differences between TCP and UDP traffic; (v) traffic generated and received by peers; (vi) peers neighborhood and session duration. The knowledge gained thanks to this analysis is useful for several tasks, e.g. traffic identification, understanding the performance of different P2P IPTV technologies and the impact of such traffic on network nodes and links, and building more realistic models for simulations.

International audience; Abstract:We observe that a same rule set can induce very different memory requirement, as well as varying classification performance, when using various well known decision tree based packet classification algorithms. Worse, two similar rule sets, in terms of types and number of rules, can give rise to widely differing performance behaviour for a same classification algorithms. We identify the intrinsic characteristics of rule sets that yield such performance differences, allowing us to understand and predict the performance behaviour of a rule set for various modern packet classification algorithms. Indeed, from our observations, we are able to derive a memory consumption model and an offline algorithm capable of quickly identifying which packet classification is suited to a give rule set. By splitting a large rule set in several subsets and using different packet classification algorithms for different subsets, our Smart Split algorithm is shown to be capable of configuring a multi-component packet classification system that exhibits up to 11 times less memory consumption, as well as up to about 4× faster classification speed, than the state-of-art work [20] for large rule sets. Our Auto PC framework obtains further performance gain by avoiding splitting large rule sets if the memory size of the built decision tree is shown by the memory consumption model to be small.

International audience; Epidemic forwarding has been proposed as a forwarding technique to achieve opportunistic communication in delay tolerant networks (DTNs). Even if this technique is well known and widely referred, one has to address several practical problems before using it. Unfortunately, while the literature on DTNs is full of new techniques, very little has been done in comparing them. In particular, while Bloom filters have been proposed to exchange information about the buffer content prior to sending information in order to avoid redundant retransmissions, up to our knowledge no real evaluation has been provided to study the tradeoffs that exist for using Bloom filters in practice. A second practical issue in DTNs is buffer management (resulting from finite buffers) and congestion control (resulting from greedy sources). This has also been the topic of several papers that had already uncovered the difficulty to acquire accurate information mandatory to regulate the data transmission rates and buffer space. In this paper, we fill this gap. We have been implementing a simulation of different proposed congestion control schemes for epidemic forwarding in ns-3 environment. We use this simulation to compare different proposed schemes and to uncover issues that remain in each one of them. Based on this analysis, we proposed some strategies for Bloom filter management based on windowing and describe implementation tradeoffs. Afterwards, we propose a back-pressure rate control as a well as an aging based buffer managing solution to deal with congestion control. By simulating our proposed mechanisms in ns-3 both with random-waypoint mobility and realistic mobility traces coming from San-Francisco taxicabs, we show that the proposed mechanisms alleviate the challenges of using epidemic forwarding in DTNs

International audience; As network link rates are being pushed beyond 40 Gb/s, IP lookup in high-speed routers is moving to hardware. The ternary content addressable memory (TCAM)-based IP lookup engine and the static random access memory (SRAM)-based IP lookup pipeline are the two most common ways to achieve high throughput. However, route updates in both engines degrade lookup performance and may lead to packet drops. Moreover, there is a growing interest in virtual IP routers where more frequent updates happen. Finding solutions that achieve both fast lookup and low update overhead becomes critical. In this paper, we propose a hybrid IP lookup architecture to address this challenge. The architecture is based on an efficient trie partitioning scheme that divides the forwarding information base (FIB) into two prefix sets: a large disjoint leaf prefix set mapped into an external TCAM-based lookup engine and a small overlapping prefix set mapped into an on-chip SRAM-based lookup pipeline. Critical optimizations are developed on both IP lookup engines to reduce the update overhead. We show how to extend the proposed hybrid architecture to support virtual routers. Our implementation shows a throughput of 250 million lookups per second (equivalent to 128 Gb/s with 64-B packets). The update overhead is significantly lower than that of previous work, the memory consumption is reasonable, and the utilization ratio of most external TCAMs is up to 100%.

International audience; Bloom Filter is a widely used data structure in computer science. It enables memory efficient and fast set membership queries. Bloom filter-based solutions have been proposed in the past decade for lookup in forwarding tables of backbone routers [2]. However, the main shortcomings of using Bloom Filters for lookup lie in the absence of support for deletion operations that are needed to update the forwarding tables. Counting Bloom Filter supporting deletion has therefore to be used, increasing significantly the memory requirement. Moreover, Counting Bloom Filter suffers from both false positive and false negative. In this paper, we propose to solve the issue with deletion of Bloom Filters by using a Withdrawal To annOuncement (WTO) mapping that replaces withdrawal with announcements, transforming deletions into additions or record changes. Experimental evaluation show that the proposed techniques improve largely the performance of Bloom Filter used for forwarding lookup and open way for the use of Bloom Filters in real operational settings.

International audience; With the fast development of Internet, the size of routing table in the backbone router continues to grow rapidly. Forwarding Information Base (FIB), which is derived from routing table, is stored in line-card to conduct routing lookup. Since the line-card's memory is limited, it would be worthwhile to compress the FIB for consuming less storage. Therefore, various FIB compression algorithms are proposed [2-7]. However, there is no well-presented mathematical support for the feasibility of the FIB compression solution, nor any mathematical derivation to prove the correctness of these algorithms. To address these problems, we propose a universal mathematical method based on the Group2 theory. By defining a Group representing the Longest Prefix Matching Rule (LPM), the bound of the worst case of FIB compression solution can be figured out. Furthermore, in order to guarantee the ultimate correctness of FIB compression algorithms, Routing Table Equation Test (RTET) is proposed and implemented to verify the equivalence of the two routing tables before and after compression by traversing the 32-bit IP address space.

International audience; The widespread availability of smart mobile terminals along with the ever increasing bandwidth capabilities has promoted the popularity of mobile Internet video systems. Understanding the geographic features of mobile content consumption is of an extreme importance for the design and the performance optimization of a mobile video delivery system. This paper is a first step towards characterization of the geographic patterns of a large-scale commercial mobile video-on-demand (VoD) system, by measuring both uniformity and intensity of geographic interests on videos. In particular, we identify a geographical concentration effect of views for individual videos, which is however dependent on video popularity. We also analyze the temporal evolution trends of the geographic popularity which reveal distinct behavior of popular and non-popular videos. While the set of locations that contribute to most of the views of non-popular videos largely varies, the daily geographic popularity distribution of popular videos closely follows the distribution of global traffic and remains stable. We also examine the impact of content type and viewing sources on the geographic features of mobile videos consumption, and the correlation between content similarity and geographic locality. Finally, we provide insights into the implications of our findings.

National audience; L’Internet et le cyberespace sont aujourd’hui des réalités incontournables du monde contemporain, et en géopolitique bien des événements récents en ont souligné l’importance. Cependant, ces deux termes d’Internet et de cyberespace ne se recouvrent pas. L’Internet est un réseau bâti sur du réel, composé de fibres optiques, de liaisons par satellites et de machines qui sont situées dans l’espace terrestre ; le cyberespace regroupe les applications qui exploitent l’Internet et semble s’échapper de l’espace terrestre, pour en former un nouveau. L’analyse géopolitique doit, elle aussi, distinguer ces deux plans. Tout d’abord, et au travers de quelques exemples (Iran, France, Syrie), il convient de porter un regard géographique sur les infrastructures de l’Internet. Elles peuvent être des cibles en situation de conflit et, plus généralement, leur organisation dans les territoires pose de nombreux problèmes classiques de géographie ou de géopolitique, en termes d’aménagement du territoire ou d’inégalités spatiales. Dans un second temps, et à titre d’ébauche, cet article tente d’imaginer ce que sera peut-être demain la cybergéographie, discipline visant à étudier « spatialement » le rapport des humains au cyberespace, par analogie avec la géographie qui a pour objet leurs rapports avec l’espace terrestre. Cela impliquera d’élaborer les outils d’une description du cyberespace en quelque sorte de l’intérieur, et pose de nombreuses questions abstraites et théoriques.

The advances in wireless communications and mobile devices have resulted in a massive growth of the video services over mobile networks. In this article, we study the potential of peer-assisted video delivery in WiFi mobile networks aimed at reducing servers? load. Our study is based on a real measurement of mobile video viewing logs from a leading Internet video provider for 14 days. We analyze viewing behavior of users with respect to three main factors for the design of peer-assisted delivery network: viewing time, user population, and user locality. We then discuss the implications of the observations. Finally, we apply the findings on a BitTorrent-like VoD system and perform experiments with the collected viewing logs to demonstrate the benefits of peer-assisted video delivery. The peer assistance can reduce the servers? load by as much as 50 percent for popular videos on average.

International audience; Network Intrusion Detection Systems (NIDSes) face significant challenges coming from the relentless network link speed growth and increasing complexity of threats. Both hardware accelerated and parallel software-based NIDS solutions, based on commodity multi-core and GPU processors, have been proposed to overcome these challenges. Network Intrusion Detection Systems (NIDSes) face significant challenges coming from the relentless network link speed growth and increasing complexity of threats. Both hardware accelerated and parallel software-based NIDS solutions, based on commodity multi-core and GPU processors, have been proposed to overcome these challenges. This work explores new parallel opportunities afforded by many-core processors for high performance, scalable and inexpensive NIDS. We exploit the huge many-core computational power by adopting a hybrid parallel architecture combining data and pipeline parallelism. We also design a hybrid load balancing scheme, using both ruleset and flow space partitioning. Furthermore, the proposed design leverages particular features of the processor to break the bottlenecks. We have integrated the open source NIDS Suricata into our proposed design and evaluated its performance with synthetic traffic. The prototype exhibits almost linear speedup and can handle up to 7.2 Gbps traffic with 100-bytes packets.

International audience; Regular expression (RegEx) matching is a core function of deep packet inspection in modern network devices. Previous TCAM-based RegEx matching algorithms a priori assume that a deterministic finite automaton (DFA) can be built for a given set of RegEx patterns. However, practical RegEx patterns contain complex terms like wildcard closure and repeat character, and it may be impossible to build a DFA with a reasonable number of states. This results in prior work to being infeasible in practice. Moreover, TCAM-based RegEx matching is required to scale to a large-scale set of RegEx patterns. In this paper, we propose a compressed finite automaton implementation called (CFA) for scalable TCAM-based RegEx matching. CFA is designed to reduce TCAM space by using three compression techniques: transition, character, and state compressions. Experiments on realistic RegEx pattern sets show CFA highly outperforms previous solutions in terms of TCAM space, matching throughput, and TCAM power consumption.

International audience; P2P platforms have been criticized because of the heavy strain that they can inflict on costly inter-domain links of network operators. It is therefore mandatory to develop network optimization schemes for controlling the load generated by a P2P platform on an operator network. While many research efforts exist on centralized tracker-based systems, in recent years multiple DHT-based P2P platforms have been widely deployed and considered as commercial services due to their scalability and fault tolerance. Finding network optimization for DHT-based P2P applications has thereby potential large practical impacts. In this paper, we present THash, a simple scheme that implements a distributed and effective network optimization for DHT systems. THash uses standard DHT put/get semantics and utilizes a triple hash method to guide the DHT clients to choose their sharing peers in proper domains. We have implemented THash in a major commercial P2P system (PPLive), using the standard ALTO/P4P protocol as the network information source. We conducted experiments over this network in real operation and observed that compared with Native DHT, THash reduced respectively by 47.4% and 67.7% the inter-PID and inter-AS traffic, while reducing the average downloading time by 14.6% to 24.5%.

International audience; Deep Packet Inspection (DPI) module in Intrusion Detection Systems (IDSes) consists of two components: Pre-filter and Rule Verification (RV). Pre-filter adopts Multi-Pattern Matching (MPM) engine to filter out the vast majority of benign packets and then leave a few suspicious packets with false positives into RV component. These false positives are due to the scanning process in the pre-filter: it detects the traffic in a single pass against a set of fingerprints, which are extracted from the given ruleset by selecting only a small portion of the patterns in each signature. RV component precisely checks the suspicious packets and eliminates these false positives. The performance of DPI module is related to the extracted fingerprint set. An efficient fingerprint set should improve the pre-filter throughput, and at the same time decrease the count of checking activities in RV component. We show in this paper that these two requirements cannot be simultaneously satisfied in the existing fingerprint extraction strategies. Pre-filter performance greatly benefits from smaller fingerprint set because of the more compact MPM engine. But RV component suffers from the higher rate of false positives caused by the smaller fingerprint set. We optimally trade off these two requirements with a new extraction method in this work. Through analysing a small amount of training traffic in the initial phase, our strategy gives each fingerprint candidate an empirical weight for the subsequent extraction. Experimental results obtained by integrating our proposed method into the Snort IDS show that our strategy improves the IDS average throughput by at least 69% over the latest real ruleset and real traffic.

Bloom filters are space-efficient data structures for fast set membership queries. Counting Bloom Filters (CBFs) extend Bloom filters by allowing insertions and deletions to support dynamic sets. The performance of CBFs is critical for various applications and systems. This paper presents a novel approach to building a fast and accurate data structure called Multiple-Partitioned Counting Bloom Filter (MPCBF) that addresses large-scale data processing challenges. MPCBF is based on two ideas: reducing the number of memory accesses from k (for k hash functions) in the standard CBF to only one memory access in the basic MPCBF-1 case, and a hierarchical structure to improve the false positive rate. We also generalize MPCBF-1 to MPCBF-g to accommodate up to g memory accesses. Our simulation and implementation in MapReduce show that MPCBF outperforms the standard CBF in terms of speed and accuracy. Compared to CBF, at the same memory consumption, MPCBF significantly reduces the false positive rate by an order of magnitude, with a reduction of processing overhead by up to 85.9%.