Recipient of the IEEE COMPSAC 2026 Best Paper Award.

Packet processing in modern routers and switches relies on rule matching, primarily performed by two core modules: IP prefix lookup for next-hop determination and packet classification for multi-field policy enforcement. However, most existing algorithms are rule-centric and assume uniform rule access, overlooking the highly skewed nature of real-world network traffic. Such mismatch between static rule organization and dynamic traffic behavior leads to inefficiency in both lookup and classification. To address this limitation, we propose a Traffic-aware Lookup and Forwarding (TLF) framework that leverages traffic measurement with lookup operations, enabling online adaptation to dynamic traffic patterns and frequent rule updates. Experimental results demonstrate that TLF provides 1.04×–3.37× speedups for lookup and forwarding over state-of-the-art algorithms, while substantially reducing both memory overhead and construction time. Furthermore, integrating TLF into Vector Packet Processor (VPP) and Open vSwitch (OVS) results in throughput improvements of 2.61× and 4.88×, respectively.

In natural language processing, topic modeling aims to extract a corpora latent structure. In recent years, optimal transport distances have improved the topic extraction capabilities of Neural Topic Models (NTMs). More precisely, the Sinkhorn-Knopp algorithm is used to compute the blurred Wasserstein distance with relatively low complexity and is fully differentiable. This algorithm ease of implementation and advantages are thus particularly interesting for enforcing desired properties in NTMs. However, the algorithm can be unstable and inefficient under low blur setups, hence hindering overall topic model performances. In this article, we first assess the stability and efficiency of the Sinkhorn-Knopp algorithm in NTM scenarios. We compare five of the most relevant variations of this algorithm, and three distinct usages in NTMs. We evaluate each specific Sinkhorn-Knopp algorithm variation and topic model architecture independently, under various quantitative and qualitative metrics. Furthermore, we propose a novel method that focuses on the Sinkhorn-Knopp algorithm initialization, by reusing its dual variables from previous model updates as warm-start values. Our experiments reveal that our method can drastically improve the computation efficiency of the algorithm by reducing its number of iterations by up to 70%, and is easily applicable to any topic model using the Sinkhorn distance.

Federated Learning (FL) has emerged as a promising paradigm for decentralized machine learning, enabling multiple clients to collaboratively train a global model without sharing their raw data. Despite its privacy-preserving design, FL remains vulnerable to privacy leakage through inference attacks, such as membership inference, and to integrity threats like Byzantine behaviors that can degrade model reliability. To address these risks, we propose Local Data Privatization Preprocessing (LDPP), a lightweight client-side method that enforces differential privacy while preserving the statistical properties of local data. LDPP operates through a three-stage process: (i) transforming data into a standardized representation (normal or uniform), (ii) injecting calibrated noise using differential privacy mechanisms, such as Laplace or Gaussian distributions, and (iii) applying an inverse transformation to asymptotically recover the original data distribution. We formally prove that LDPP satisfies $\epsilon$-differential privacy and maintains key distributional characteristics. Additionally, LDPP can be combined with robust aggregation techniques, such as Krum, to strengthen defense against adversarial tampering. Comprehensive experiments in EMNIST and MedMNIST datasets demonstrate that LDPP significantly reduces the success of membership inference attacks and improves robustness under label-flipping scenarios while preserving high model accuracy. These findings position LDPP as a scalable and practical solution to improve both privacy and robustness in federated learning frameworks.

Packet classification is a critical component for accurately categorizing traffic in network systems. The efficiency of packet classification algorithms is primarily determined by two key factors: the classifier's data structure and the characteristics of the traffic being classified. While significant efforts have been made to optimize data structures, the potential of leveraging traffic characteristics remains underexplored. In this study, we revisit the network dataplane by integrating the network measurement module with the packet classification module. We propose an innovative Network-aware Packet Classification system (NPC) that utilizes sketch techniques to extract network traffic features. These features guide the construction of decision trees, enabling efficient and adaptable packet classification across diverse network environments. Experimental results demonstrate that the NPC achieves speedups ranging from 1.86× to 23.88× over state-of-the-art algorithms, while significantly reducing memory overhead and construction time, highlighting its practical value in real-world scenarios. Furthermore, integrating NPC into Open vSwitch (OVS) yields throughput improvements of 10.71× to 13.01× compared to the native OVS.

Today we are able to generate a large set of text representations from the simple Bag-of-word (BOW) to the recent transformers capturing the semantic and the contextual text meaning. It was proven that there is no best text representation for text clustering task. Consequently, some works combined text representations using a consensus clustering approach. Two consensus approach types exist, namely explicit and implicit consensus. In the explicit consensus, also known asensemble clustering, the consensus function is applied a posterior after obtaining cluster labels from each text representation clustering allowing to capture global mutual information between the partitions of all text representations. On the other hand, implicit consensus uses tensor clustering to optimize the clustering consensus partition that deals with similarity matrices of text representations.

Issue Tracking Systems software serves as an interface between a company and its customers. Customers can report bugs and seek assistance, among other demands. Reported issues include textual description, along with company defined metadata, aim at simplifying issue treatment by experts. In the context of the rapid growth of customer-reported issues, the manual treatment process becomes tedious and time-consuming. As a result, more and more studies focus on automating parts of this process, using semantic extraction and topic modeling approaches to automatically classify issues. To this end, most approaches consider the issue of textual description along with metadata, which can be a source of uncertainty and misleading in many real-world scenarios. Besides, knowledge from the company experts is often neglected. In this paper, we propose a general taxonomy of information incorporation into topic models. This aims to assemble all existing techniques, to further detect literature gaps. In addition, we propose a technique to incorporate expert knowledge into neural topic models. We evaluate our techniques and others in the literature on a real-world dataset coming from the JIRA software of a French HR management company. Results show a significant increase of more than 22% in classification performances when using expert knowledge, in addition to the issue textual description. The results validate our approach's effectiveness in improving the automatic classification of issues.

Anomaly detection is a common task in various domains, which has attracted significant research efforts in recent years. Existing reviews mainly focus on structured data, such as numerical or categorical data. Several studies treated review of anomaly detection in general on heterogeneous data or concerning a specific domain. However, anomaly detection on unstructured textual data is less treated. In this work, we target textual anomaly detection. Thus, we propose a systematic review of anomaly detection solutions in the text. To do so, we analyze the included papers in our survey in terms of anomaly detection types, feature extraction methods, and machine learning methods. We also introduce a web scrapping to collect papers from digital libraries and propose a clustering method to classify selected papers automatically. Finally, we compare the proposed automatic clustering approach with manual classification, and we show the interest of our contribution.

Although deep pre-trained language models have shown promising benefit in a large set of industrial scenarios, including Click-Through-Rate (CTR) prediction, how to integrate pre-trained language models that handle only textual signals into a prediction pipeline with non-textual features is challenging.

Cloud computing provides a new paradigm to offer flexible IT infrastructures. In IaaS clouds, tenants deploy software-defined networking (SDN) policies to simplify network management and customize network behaviors. However, programming SDN networks is error-prone no matter using low-level APIs or high-level programming languages. Specifically, SDN policies may contain misconfigurations that do not break the pre-defined network invariants (e.g., black holes), but either degrade the deployment efficiency or mistakenly translate tenants intents. Prior studies for checking either traditional access control policies or network-wide invariants, are thus fail to detect these misconfigurations. To address this gap, this paper presents PMM, a misconfiguration checking tool for compositional SDN that works at the data plane of cloud networks. We first propose a new data structure, minimal interval set, to represent the match patterns of rulesets. This representation serves the basis for composition algebra construction and misconfiguration checking. We then propose the principles, algorithms and also optimisations for fast and accurate checking. We finally implement PMM in Covisor. Experiments with both real-world rulesets and synthetic rulesets show that PMM can detect misconfigurations of SDN policies in cloud networks within hundreds of milliseconds.

In sponsored search engines, pre-trained language models have shown promising performance improvements on Click-Through-Rate (CTR) prediction. A widely used approach for utilizing pre-trained language models in CTR prediction consists of fine-tuning the language models with click labels and early stopping on peak value of the obtained Area Under the ROC Curve (AUC). Thereafter the output of these fine-tuned models, i.e., the final score or intermediate embedding generated by language model, is used as a new Natural Language Processing (NLP) feature into CTR prediction baseline. This cascade approach avoids complicating the CTR prediction baseline, while keeping flexibility and agility. However, we show in this work that calibrating separately the language model based on the peak single model AUC does not always yield NLP features that give the best performance in CTR prediction model ultimately. Our analysis reveals that the misalignment is due to overlap and redundancy between the new NLP features and the existing features in CTR prediction baseline. In other words, the NLP features can improve CTR prediction better if such overlap can be reduced.

Open vSwitch (OVS) is a widely used virtual switch designed to provide virtual network capabilities in virtualized environments. As the core of OVS, the packet classification task is time-consuming with the implementation of Tuple Space Search (TSS), a classical hash table-based algorithm that can achieve fast rule updating but at the cost of the reduced packet classification throughput. However, because of the central role of OVS in a virtualized environment, its performance is of utmost importance and we need mechanisms that can achieve high update rate along with high packet classification throughput. In this paper, we compare the performance of several classification algorithms and show that Tuple Merge Relaxation (TMR) is able to achieve the highest sustainable classification throughput while dealing with updates. After integrating it into OVS and evaluating its in vivo performance, we observe that TMR-OVS can achieve up to$24.7\times $higher throughput compared with native OVS. Moreover, we show that TMR-OVS is also effective against Tuple Space Explosion attack effectively and maintains OVS throughput under this attack.

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.2\times $classification speed and$4.2\times $update speed on average compared with state-of-the-art algorithms. We also implement CRP in OVS. The throughput of CRP-OVS is$10\times $that of native OVS.

This paper presents a complete framework for content discovery and retrieval in Information-Centric Networks. For content discovery, we implement a method similar to our previously developed pull-based BFR [1], which uses Bloom filter-based signaling to inform servers about the name prefixes of available requests. For content retrieval, we propose in this paper a feedback-based cooperative protocol implementing network coding-based forwarding. The proposed network coding-based protocol provides a distributed solution to control the multisession codeblock size, i.e., the number of variables that are combined into network coded packets, by setting a capacity constraint on each node and by piggybacking the available capacity as feedback on messages sent to neighbors. The network codes are decided using linear programming. We compare the proposed network coding-based protocol with push-based BFR [2] and pull-based BFR [1]. The results show that the proposed protocol outperforms both push-based BFR and pull-based BFR in terms of content discovery overhead and average content block retrieval delay.

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.

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.

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.

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 (1011records) 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.

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 filter-based routing protocols, namely BFR and COBRA. BFR is a push-based routing protocol that works based on Bloom filter-based 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.

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 (1011records) 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.

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.3×) compared with state-of-the-art techniques.

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.

In mobile live streaming systems, users have fairly limited interactions with streaming objects due to the constraints coming from mobile devices and the 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 nonmobile 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 a video delivery system, telco-content delivery networks, and mobile applications.

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.

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.

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.

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.

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.

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.

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.

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 Group2theory. 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.

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.

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%.

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.

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.

Virtual routers are increasingly being studied, as an important building block to enable network virtualization. In a virtual router platform, multiple virtual router instances coexist, each having its own FIB (Forwarding Information Base). In this context, memory scalability and route updates are two major challenges. Existing approaches addressed one of these challenges but not both. In this paper, we present a trie merging approach, which compactly represents multiple FIBs by a merged trie and a table of next-hop-pointer arrays to achieve good memory scalability, while supporting fast incremental updates by avoiding the use of leaf pushing during merging. Experimental results show that storing the merged trie requires limited memory space, e.g., we only need 10MB memory space to store the merged trie for 14 full FIBs from IPv4 core routers, achieving a memory reduction by 87% when compared to the total size of the individual tries. We implement our approach in an SRAM (Static Random Access Memory)-based lookup pipeline. Using our approach, an on-chip SRAM-based lookup pipeline with 5 external stages is sufficient to store the 14 full IPv4 FIBs. Furthermore, our approach can guarantee a minimum update overhead of one write bubble per update, as well as a high lookup throughput of one lookup per clock cycle, which corresponds to a throughput of 251 million lookups per second in the implementation.

In this paper, we study the process of information diffusion in a microblog service developing Galton-Watson with Killing (GWK) model. Microblog services offer a unique approach to online information sharing allowing microblog users to forward messages to others. We describe an information propagation as a discrete GWK process based on Galton-Watson model which models the evolution of family names. Our model explains the interaction between the topology of the social graph and the intrinsic interest of the message. We validate our model on dataset collected from Sina Weibo and Twitter microblog. Sina Weibo is a Chinese microblog web service which reached over 100 million users as for January 2011. Our Sina Weibo dataset contains over 261 thousand tweets which have retweets and 2 million retweets from 500 thousand users. Twitter dataset contains over 1.1 million tweets which have retweets and 3.3 million retweets from 4.3 million users. The results of the validation show that our proposed GWK model fits the information diffusion of microblog service very well in terms of the number of message receivers. We show that our model can be used in generating tweets load and also analyze the relationships between parameters of our model and popularity of the diffused information. To the best of our knowledge, this paper is the first to give a systemic and comprehensive analysis for the information diffusion on microblog services, to be used in tweets-like load generators while still guaranteeing popularity distribution characteristics.

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%.

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.

Packet classification has been studied extensively in the past decade. While many efficient algorithms have been proposed, the lack of deterministic performance has hindered the adoption and deployment of these algorithms: the expensive and power-hungry TCAM is still the de facto standard solution for packet classification. In this work, in contrast to proposing yet another new packet classification algorithm, we present the first steps to understand this unpredictability in performance for the existing algorithms. We focus on decision-tree based algorithms in this paper. In order to achieve the predictability, we firstly revisit the classical and many state-of-art packet classification algorithms. Through a detailed analysis, we conclude that two features of ruleset usually dominate the performance results: 1) the uniformity of the range distribution in different dimensions of the rules; 2) the existence and the number of “orthogonal structure” and wildcard rules in the ruleset. We conduct experiments to show the correctness of these observations, and discribe some potential applications for those results. Our work provides some insight to make the packet classification algorithms a credible alternative to the TCAM-only solutions.

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%.

User-generated content (UGC) video systems by definition heavily depend on the input of their community of users and their social interactions for video diffusion and opinion sharing. Nevertheless, we show in this paper, through measurement and analysis of YouKu, the most popular UGC video system in China, that the social connectivity of its users is very low. These observations are consistent with what was reported about YouTube in previous works. As a UGC system can achieve a larger audience through improved connectivity, our findings motivate us to propose a mean to enhance the users' connectivity by taking benefit of friend recommendation. To this end, we assess two similarity metrics based on users' interests that are derived from their uploads and favorites tagging of videos, to evaluate the interest similarity between friends. The results consistently show that friends share to a great extent common interests. Two friend recommendation algorithms are then proposed. The algorithms use public information provided by users to suggest potential friends with similar interests as measured by the similarity metrics. Experiments on our gathered YouKu dataset demonstrate that the social connectivity can be greatly enhanced by our friend proposition set and that users can access a larger set of interesting videos through the recommendations.

As the key building block for enabling network virtualization, virtual routers have attracted much attention recently. In a virtual router platform, multiple virtual router instances coexist, each with its own FIB (Forwarding Information Base). The small amount of high-speed memory in a physical router platform severely limits the number of FIBs supported, which leads to a scalability challenge. In this paper, we present a method towards TCAM (Ternary Content Addressable Memory) based scalable virtual routers, through a merged data structure that enables the sharing of prefixes from several FIBs in TCAMs. Based on this data structure, we propose two approaches to merge multiple FIBs in TCAMs, paving the way for scalable virtual routers. Experimental results show that, by using the two approaches for storing 14 full IPv4 FIBs, the TCAM memory requirement can be reduced by about 92% and 82% respectively, compared with the conventional approach of treating FIBs as independent entities.

In recent years, there has been a growing interest in multi/many core processors as a target architecture for high performance software router. This is a clear difference from the previous trend to use dedicated network processors and hardware components. Because of its key position in routers, hardware IP lookup implementation has been intensively studied with TCAM and FPGA based architecture. However, increasing interest in software implementation has also been observed. In this paper, we evaluate the performance of software only IP lookup on a many core chip, the TILEPro64 processor. For this purpose we have implemented two widely used IP lookup algorithms, DIR-24-8-BASIC and Tree Bitmap. We evaluate the performance of these two algorithms over the TILEPro64 processor with both synthetic and real-world traces. After a detailed analysis, we propose a hybrid scheme which provides high lookup speed and low worst case update overhead. Our work shows how to exploit the architectural features of TILEPro64 to improve the performance, including many optimization in both single-core and parallelism aspects. Experiment results show by using only 18 cores, we can achieve a lookup throughput of 60Mpps (almost 40Gbps) with low power consumption, which demonstrates great performance potentials in many core processor.

In this work, we aim to analyze and compare interaction patterns in different types of social platforms. To this end, we measured Renren, the largest online social network in China, and Sina Weibo, the most popular microblog service in China. We model the interaction networks as unidirectional weighted graphs in light of the asymmetry of user interactions. Following this model, we first study the basic interaction patterns. Then, we examine whether weak ties hypothesis holds in these interaction graphs and analyze the impacts on information diffusion. Furthermore, we model the temporal patterns of user interactions and cluster users based on the temporal patterns. Our findings demonstrate that although users in the two platforms share some common interaction patterns, users in Sina Weibo are more popular and diverse. Moreover, analysis and simulation results show that Sina Weibo is a more efficient platform for information diffusion. These findings provide an in-depth understanding of interaction patterns in different social platforms and can be used for the design of efficient information diffusion.

While there are several ways for video finding in UGC (user generated content) video systems, video search is still the number one source of video views in aggregation. In this paper, we propose to use peer-assisted search to alleviate the server burden caused by video search. To this end, we have measured and analyzed YouKu, the largest UGC video system in China. With a large dataset, we have found non-power law distribution of video popularity, low replication level for popular videos, skewed user activity and interest locality. Based on the findings, we design two-layer hierarchical semantic overlay structures to implement peer-assisted search for UGC video systems. A novel search algorithm called WISE is proposed to guide queries quickly to the semantically relevant clusters by visiting a very small fraction of nodes. Simulations using the YouKu trace demonstrate that WISE is effective and helpful to assist the search in UGC video systems. To the best of our knowledge, this is the first work to study peer-assisted search in UGC.

As network link rates are being pushed beyond 40 Gbps, IP lookup in high-speed routers is moving to hardware. The TCAM (Ternary Content Addressable Memory)-based IP lookup engine and the SRAM (Static Random Access Memory)-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 (MLPS). The update overhead is significantly lower than that of previous work and the utilization ratio of most external TCAMs is up to 100%.

P2P platforms have been criticized because of the heavy strain that some P2P services can inflict on costly inter-domain links of network operators. It is therefore necessary to develop network optimization schemes for controlling the load generated by P2P platforms on an operator network. Previous focus on network optimization has been mostly on centralized tracker-based systems. However, in recent years multiple DHT-based P2P networks are widely deployed due to their scalability and fault tolerance, and these networks have even been considered as platforms for commercial services. Thereby, finding network optimization for DHT-based P2P applications has potentially large practical impacts. In this paper, we present THash, a simple scheme to implement an effective distributed network optimization for DHT systems. THash is based on standard DHT put/get semantics and utilizes a triple hash method to guide the DHT clients sharing resources with peers in proper domains. We have implemented THash in a major P2P application (PPLive) by using the standard ALTO/P4P protocol as the network information source. We conducted realistic experiments over the network and observed that compared with Native DHT, THash only generated 45.5% and 35.7% of inter-PID and inter-AS traffic, and at the same time shortened the average downloading time by 13.8% to 22.1%.

Traffic flow measurement is of great importance to ISPs for various network engineering tasks. An interesting problem is that how to determine the minimum number of links by monitoring which one can obtain the traffic flows of the whole ISP network. Previous works view the problem as Vertex Cover problem. They suffer from high time complexity and redundant monitoring. Different from these works, we study the problem from the perspective of edges and propose two models. The first model, Extended Edge Cover model, can determine the minimum set of monitored links, which are 30% less than that of previous works. The second model, shared-path model, is more suitable when the monitoring resources are limited but one still wants to measure a large part of the networks. Using this method, one can measure 85% of the network by monitoring 5% of links. Finally, we evaluate the performance of the two models through extensive simulations. The experimental results show the effectiveness and robustness of the two models.

Anomaly extraction refers to automatically finding, in a large set of flows observed during an anomalous time interval, the flows associated with the anomalous event(s). It is important for root-cause analysis, network forensics, attack mitigation, and anomaly modeling. In this paper, we use meta-data provided by several histogram-based detectors to identify suspicious flows, and then apply association rule mining to find and summarize anomalous flows. Using rich traffic data from a backbone network, we show that our technique effectively finds the flows associated with the anomalous event(s) in all studied cases. In addition, it triggers a very small number of false positives, on average between 2 and 8.5, which exhibit specific patterns and can be trivially sorted out by an administrator. Our anomaly extraction method significantly reduces the work-hours needed for analyzing alarms, making anomaly detection systems more practical.

In the Web 2.0 era, users share and discover interesting content via a network of relationships created in various social networking or content sharing sites. They can become for example contacts, followers or friends and express their appreciation of specific content uploaded by their peers by faving, retweeting or liking them depending on whether they are in Flickr, Twitter or Facebook respectively. Then they can discover additional content of interest through the lists of favorites of their contacts and so on. This faving (or favoring) functionality becomes thus a central part of content sharing communities for two purposes: (a) it helps the propagation of content amongst users and (b) it stimulates users' participation and activity. In this paper, we make a first step to understand users' faving behavior in content sharing communities in terms of reciprocity using publicly available datasets from Flickr and Twitter. Do users favor content only when they really appreciate it or they often feel the need to reciprocate when their content is appreciated by one of their contacts or even by a stranger? Do people take advantage of this process to gain popularity? What is the impact of the design, the social software, of a specific community and the type of content shared? These are some of the questions that our first results help to answer.

In this paper, we present our P2P-TV measurement experiment performed in France and Japan. By using multiple measurement points in different locations of the world, we are able to get a global view of the measured P2P networks and we can infer their main properties. More precisely, we focus on the level of collaboration between peers, their location and the effect of the traffic on the networks. Our results show that there is no fairness between peers and it is an important issue for the scalability of P2P-TV systems. Moreover, hundreds of Autonomous Systems are involved in the P2P-TV traffic and it points out the lack of locality-aware mechanisms for these systems. The geographic location of peers testifies the wide spread of these applications in Asia and highlights their worldwide usage.

In this paper, we present our P2P-TV measurement experiment performed in France and in Japan. By using multiple measurement points in different locations of the world, we are able to get a global view of the measured P2P networks and we can infer their main properties. More precisely, we focus on the location of peers and the effect of the P2P-TV traffic on the networks. Our results shows that hundred of Autonomous Systems are involved in the exchange of traffic between peers and it points out the lack of locality-aware mechanisms for these P2P-TV systems. We also investigate the geographic location of users. It testifies the wide spread of these applications in Asia and highlights the worldwide usage of these applications.

Anomaly detection methods typically operate on preprocessed traffic traces. Firstly, most traffic capturing devices today employ random packet sampling, where each packet is selected with a certain probability, to cope with increasing link speeds. Secondly, temporal aggregation, where all packets in a measurement interval are represented by their temporal mean, is applied to transform the traffic trace to the observation timescale of interest for anomaly detection. These preprocessing steps affect the temporal correlation structure of traffic that is used by anomaly detection methods such as Kalman filtering or PCA, and have thus an impact on anomaly detection performance. Prior work has analyzed how packet sampling degrades the accuracy of anomaly detection methods; however, neither theoretical explanations nor solutions to the sampling problem have been provided. This paper makes the following key contributions: (i) It provides a thorough analysis and quantification of how random packet sampling and temporal aggregation modify the signal properties by introducing noise, distortion and aliasing. (ii) We show that aliasing introduced by the aggregation step has the largest impact on the correlation structure. (iii) We further propose to replace the aggregation step with a specifically designed low-pass filter that reduces the aliasing effect. (iv) Finally, we show that with our solution applied, the performance of anomaly detection systems can be considerably improved in the presence of packet sampling.

Identifying heavy-hitter traffic flows efficiently and accurately is essential for Internet security, accounting and traffic engineering. However, finding all heavy-hitters might require large memory for storage of flows information that is incompatible with the usage of fast and small memory. Moreover, upcoming 100Gbps transmission rates make this recognition more challenging. How to improve the accuracy of heavy-hitters identification with limited memory space has become a critical issue. This paper presents a scalable algorithm named Mnemonic Lossy Counting (MLC) that improves the accuracy of heavy-hitters identification while having a reasonable time and space complexity. MLC algorithm holds potential candidate heavy-hitters in a historical information table. This table is used to obtain tighter error bounds on the estimated sizes of candidate heavy-hitters. We validate the MLC algorithm using real network traffic traces, and we compared its performance with two state-of-the-art algorithms, namely Lossy Counting (LC) and Probabilistic Lossy Counting (PLC). The results reveal that: 1) with same set of parameters and memory usage, MLC achieves between 31.5% and 6.67% fewer false positives than LC and PLC. 2) MLC and LC have a zero false negative ratio, whereas 38% of the cases PLC has a non-zero false negatives and PLC can miss up to 4.4% of heavy-hitters. 3) MLC has a slightly lower memory cost than LC during the first few windows and its memory usage decreases with time, when PLC memory usage declines sharply. 4) MLC has similar runtime than LC, and smaller time than PLC.

In many practical scenarios, nodes gathering at points of interest yield sizable connected components (clusters), which sometimes comprise the majority of nodes. While recent analysis of mobile networks focused on the process governing node encounters ("contacts"), this model is not particularly suitable for gathering behavior. In this paper, we propose a model of stochastic coalescence (merge) and fragmentation (split) of clusters. We implement this process as a Markov chain and derive analytically the exact stationary distribution of cluster size. Further, we prove that, as the number of nodes grows, the clustering behavior converges to a mean field, which is obtained as a closed-form expression. This expression translates the empirical merge and split rate of a scenario, a microscopic property, to an important macroscopic property - the cluster size distribution - with surprising accuracy. We validate all results with synthetic as well as real-world mobility traces from conference visitors and taxicabs with several thousand nodes.

In this paper, we propose a methodology to predict the popularity of online contents. More precisely, rather than trying to infer the popularity of a content itself, we infer the likelihood that a content will be popular. Our approach is rooted in survival analysis where predicting the precise lifetime of an individual is very hard and almost impossible but predicting the likelihood of one's survival longer than a threshold or another individual is possible. We position ourselves in the standpoint of an external observer who has to infer the popularity of a content only using publicly observable metrics, such as the lifetime of a thread, the number of comments, and the number of views. Our goal is to infer these observable metrics, using a set of explanatory factors, such as the number of comments and the number of links in the first hours after the content publication, which are observable by the external observer. We use a Cox proportional hazard regression model that divides the distribution function of the observable popularity metric into two components: (a) one that can be explained by the given set of explanatory factors (called risk factors) and(b) a baseline distribution function that integrates all the factors not taken into account. To validate our proposed approach, we use data sets from two different online discussion forums: dpreview.com, one of the largest online discussion groups providing news and discussion forums about all kinds of digital cameras, and myspace.com, one of the representative online social networking services. On these two data sets we model two different popularity metrics, the lifetime of threads and the number of comments, and show that our approach can predict the lifetime of threads from Dpreview (Myspace) by observing a thread during the first 5~6 days (24 hours, respectively) and the number of comments of Dpreview threads by observing a thread during first 2~3 days.

We address the issue of asserting the accuracy of coordinates advertised by nodes of Internet coordinate systems during distance estimations. Indeed, some nodes may lie deliberately about their coordinates to mount various attacks against applications and overlays. Our proposed method consists in two steps: 1) establish the correctness of a node's claimed coordinate (which leverages our previous work on securing the coordinates embedding phase using a Surveyor infrastructure); and 2) issue a time limited validity certificate for each verified coordinate. Validity periods are computed based on an analysis of coordinate inter-shift times observed on PlanetLab, and shown to follow a long-tail distribution (lognormal distribution in most cases, or Weibull distribution otherwise). The effectiveness of the coordinate certification method is validated by measuring the impact of a variety of attacks on distance estimates.

Abstract—Anomaly extraction refers to automatically finding, in a large set of flows observed during an anomalous time interval, the flows associated with the anomalous event(s). It is important for root-cause analysis, network forensics, attack mitigation, and anomaly modeling. In this paper, we use meta-data provided by several histogram-based detectors to identify suspicious flows, and then apply association rule mining to find and summarize anoma-lous flows. Using rich traffic data from a backbone network, we show that our technique effectively finds the flows associated with the anomalous event(s) in all studied cases. In addition, it triggers a very small number of false positives, on average between 2 and 8.5, which exhibit specific patterns and can be trivially sorted out by an administrator. Our anomaly extraction method significantly reduces the work-hours needed for analyzing alarms, making anomaly detection systems more practical. Index Terms—Association rules, computer networks, data mining, detection algorithms.

Spatial Principal Component Analysis (PCA) has been proposed for network-wide anomaly detection. A recent work has shown that PCA is very sensitive to calibration settings. Unfortunately, the authors did not provide further explanations for this observation. In this paper, we fill this gap and provide the reasoning behind the found discrepancies. We revisit PCA for anomaly detection and evaluate its performance on our data. We develop a slightly modified version of PCA that uses only data from a single router. Instead of correlating data across different spatial measurement points, we correlate the data across different metrics. With the help of the analyzed data, we explain the pitfalls of PCA and underline our argumentation with measurement results. We show that the main problem is that PCA fails to capture temporal correlation. We propose a solution to deal with this problem by replacing PCA with the Karhunen-Loeve transform. We find that when we consider temporal correlation, anomaly detection results are significantly improved.

In this poster, we investigate the characteristics of online commenting behaviors which can influence on the popularity of various online contents, such as user created contents. To understand the behaviors, we make three dataset, which are crawled from two online discussion forums and one online community. We, first, analyze our dataset in aspects of thread lifetime and the number of comments per thread. Then we cluster and classify threads with two characteristics of the lifetime and the number of comments. Finally we study the characteristic of the number of comments per user. 1.

P2P IPTV applications arise on the Internet and will be massively used in the future. It is expected that P2P IPTV will contribute to increase the overall Internet traffic. Moreover, these emerging applications are proprietary and their exact implementation details are still widely unknown. In this context, it is important to measure the traffic generated by these applications to understand their underlying mechanisms and to evaluate their impact on the network.

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.

We identify vulnerabilities in epidemic forwarding. We address broadcast applications over wireless ad-hoc networks. Epidemic forwarding employes several mechanisms such as inhibition and spread control, and each of them can be implemented using alternative methods. Thus, the existence of vulnerabilities is highly dependent on the methods used. We examine the links between them. We classify vulnerabilities into two categories: maliccious and rational. We examine the effect of the attacks according to the number of attackers and the different network settings such as density, mobility and congestion. We show that malicious attacks are hard to achieve and their impacts are scenario dependent. In contrast, rational attackers always obtain a significant benefit. The evaluation is carried out using detailed realistic simulations over networks with up to 1000 nodes. We consider static scenarios, as well as vehicular networks.

The automatic detection of applications associated with network traffic is an essential step for network security and traffic engineering. Unfortunately, simple port-based classification methods are not always efficient and systematic analysis of packet payloads is too slow. Most recent research proposals use flow statistics to classify traffic flows once they are finished, which limit their applicability for online classification. In this paper, we evaluate the feasibility of application identification at the beginning of a TCP connection. Based on an analysis of packet traces collected on eight different networks, we find that it is possible to distinguish the behavior of an application from the observation of the size and the direction of the first few packets of the TCP connection. We apply three techniques to cluster TCP connections: K-Means, Gaussian Mixture Model and spectral clustering. Resulting clusters are used together with assignment and labeling heuristics to design classifiers. We evaluate these classifiers on different packet traces. Our results show that the first four packets of a TCP connection are sufficient to classify known applications with an accuracy over 90% and to identify new applications as unknown with a probability of 60%.

In this paper our recent results in the capacity of single relay erasure channels are used to derive a new and tighter cut-set bound. We initially present a simple and intuitive approach to derive the classical cut-set bound in general multi-terminal erasure channels. This derivation shows that attaining the bound supposes that a full level of collaboration exists between nodes in the channel. However under some scenarios the full collaboration is not possible. We thereafter use a bounding technique based on reducing every cut-set in a general multi-terminal erasure channel to a single relay super-channel consisting of super nodes. We show that if a rate setting is not achievable over the single relay super-channel it could not then achieved over the general multi-terminal erasure channel. This led us to a tighter cut-set type of bound for general multi-terminal erasure channel

We consider here a single sender-destination multi-relay channel. The links connecting the nodes are supposed to be erasure where symbols are received correctly without any error, or lost. We consider that the nodes are not able to use any interference cancellation mechanism. The interference might be suppressed through using separated physical channel or thought a time-sharing mechanism. This model is realistic for many practical scenarios in the context of wireless networks. In previous works, the capacity region of broadcast erasure channels as well as the capacity of the single-sender relay channel (under degraded and non-degraded hypothesis) has been derived. This paper extends the previous results to the more general case of multi-relay channels. We derive the cut-set bound for a general (stationary ergodic) multi-relay erasure channel, and we show that it can be reached through a practical linear coding scheme based on MDS codes.

International audience

Wireless networks consist of senders, receivers, and intermediate nodes collaborating (more or less) to establish the communication paths. Most of the researches in the domain of wireless network have focused on routing based approaches. In such an approach, wireless network is reduced to a dynamic graph, and a minimum cost routing mechanism is applied. These approaches have led to several routing mechanisms as OLSR and AODV. However, the fundamental nature of wireless network is the broadcast. In the wireless network, all the tuned receivers potentially receive every transmission. This basic property is not well captured by graph-based approaches where packets follow a single path from sender to receiver. In this paper we propose a relaying scheme for wireless multi-hop networks. It is based on collaboration of intermediate relays at network layer to forward useful side information in place of forwarding packets. In our scheme we assume that the nodes are not able to benefit from any interference cancellation mechanism. The channels from sender to relay nodes and from sender to receiver are logically separated through a temporal scheduling. This model is realistic for many practical scenarios in the context of wireless networks. We show in this paper the information theoretic bounds and show that they are achievable using practical codes. The proposed coding scheme is simulated in realistic scenarios. The obtained results show a remarkable improvement in throughput, relay load and reliability compared to network using classical routing approach.

In order to control and manage highly aggregated Internet traffic flows efficiently, we need to be able to categorize flows into distinct classes and to be knowledgeable about the different behavior of flows belonging to these classes. In this paper we consider the problem of classifying BGP level prefix flows into a small set of homogeneous classes. We argue that using the entire distributional properties of flows can have significant benefits in terms of quality in the derived classification. We propose a method based on modeling flow histograms using Dirichlet Mixture Processes for random distributions. We present an inference procedure based on the Simulated Annealing Expectation Maximization algorithm that estimates all the model parameters as well as flow membership probabilities - the probability that a flow belongs to any given class. One of our key contributions is a new method for Internet flow classification. We show that our method is powerful in that it is capable of examining macroscopic flows while simultaneously making fine distinctions between different traffic classes. We demonstrate that our scheme can address issues with flows being close to class boundaries and the inherent dynamic behaviour of Internet flows.

No abstract available.

Very few techniques have been proposed for estimating traffic matrices in the context of Internet traffic. Our work on POP-to-POP traffic matrices (TM) makes two contributions. The primary contribution is the outcome of a detailed comparative evaluation of the three existing techniques. We evaluate these methods with respect to the estimation errors yielded, sensitivity to prior information required and sensitivity to the statistical assumptions they make. We study the impact of characteristics such as path length and the amount of link sharing on the estimation errors. Using actual data from a Tier-1 backbone, we assess the validity of the typical assumptions needed by the TM estimation techniques. The secondary contribution of our work is the proposal of a new direction for TM estimation based on using choice models to model POP fanouts. These models allow us to overcome some of the problems of existing methods because they can incorporate additional data and information about POPs and they enable us to make a fundamentally different kind of modeling assumption. We validate this approach by illustrating that our modeling assumption matches actual Internet data well. Using two initial simple models we provide a proof of concept showing that the incorporation of knowledge of POP features (such as total incoming bytes, number of customers, etc.) can reduce estimation errors. Our proposed approach can be used in conjunction with existing or future methods in that it can be used to generate good priors that serve as inputs to statistical inference techniques.