This paper presents the design of a novel architecture called CARE (Content-Aware Redundancy Elimination) that enables maximizing the informational value that challenged networks offer their users. We focus on emerging applications for situational awareness in disaster affected regions. Motivated by advances in computer vision algorithms, we propose to incorporate image similarity detection algorithms in the forwarding path of these networks. The purpose is to handle the large generation of redundant content. We outline the many issues involved in such a vision. With a Delay-Tolerant Network (DTN) setup, our simulations demonstrate that CARE can substantially boost the number of unique messages that escape the disaster zone, and it can also deliver them faster. These benefits are achieved despite the energy overhead needed by the similarity detectors.

We propose a predictive resource management scheme for network monitoring systems that can proactively shed excess load while maintaining the accuracy of monitoring applications within bounds defined by the operator. The main novelty of our scheme is that it considers monitoring applications as black boxes, with arbitrary (and highly variable) input traffic and processing cost. This way, the monitoring system preserves a high degree of flexibility, increasing the range of applications and network scenarios where it can be used. We implemented our load-shedding-based resource management scheme in an existing network monitoring system and deployed it in a large research and educational network. We present experimental evidence of the performance and robustness of our system with multiple concurrent monitoring applications during long-lived executions and using real-world traffic traces.

There is a growing body of research exploring new network architectures for the data center. These proposals all seek to improve the scalability and cost-effectiveness of current data center networks, but adopt very different approaches to doing so. For example, some proposals build networks entirely out of switches while others do so using a combination of switches and servers. How do these different network architectures compare? For that matter, by what metrics should we even begin to compare these architectures?

We introduce a protocol which routes on flat, location-independent identifiers with guaranteed scalability and low stretch. Our design builds on theoretical advances in the area of compact routing, and is the first to realize these guarantees in a dynamic distributed setting.

Many measurement systems have been proposed in recent years to shed light on the internal performance of the Internet. Their common goal is to allow distributed applications to improve end-user experience. A common hurdle they face is the need to deploy yet another measurement infrastructure. In this work, we demonstrate that without any new measurement infrastructure or active probing we obtain composite performance estimates from AS-by-AS segments and the estimates are as good as (or even better than) those from existing estimation methodologies that use on-demand, customized active probing. The main contribution of this paper is an estimation algorithm that breaks down measurement data into segments, identifies relevant segments efficiently, and, by carefully stitching segments together, produces delay and path estimates between any two end points. Fittingly, we call our algorithm path stitching. Our results show remarkably good accuracy: error in delay is below 20 ms in 80% of end-to-end paths.

Recent technological advances in commodity server architectures, with multiple multi-core CPUs, integrated memory controllers, high-speed interconnects and enhanced network interface cards, provide substantial computational capacity and thus an attractive platform for packet forwarding. However, to exploit this available capacity, we need a suitable software platform that allows effective parallel packet processing and resource management. In this paper, we at first introduce an improved forwarding architecture for software routers that enhances parallelism by exploiting hardware classification and multi-queue support, already available in recent commodity network interface cards. After evaluating the original scheduling algorithm of the widely-used Click modular router, we propose solutions for extending this scheduler for improved fairness, throughput and more precise resource management. To illustrate the potential benefits of our proposal, we implement and evaluate a few key elements of our overall design.

We revisit the problem of scaling software routers, motivated by recent advances in server technology that enable high-speed parallel processing--a feature router workloads appear ideally suited to exploit. We propose a software router architecture that parallelizes router functionality both across multiple servers and across multiple cores within a single server. By carefully exploiting parallelism at every opportunity, we demonstrate a 35Gbps parallel router prototype; this router capacity can be linearly scaled through the use of additional servers. Our prototype router is fully programmable using the familiar Click/Linux environment and is built entirely from off-the-shelf, general-purpose server hardware.

Massively distributed applications are popular in today's Internet. To improve the end-user experience, they require constantly updated information about the network-internal performance characteristics, such as RTT, effective bandwidth, IP hop count, and loss rate. Knowledge of network-internal characteristics allow distributed applications to solve commonly encountered problems, such as nearest neighbor discovery, leader node selection, and optimal distribution tree organization. Today's Internet does not provide any such information, and applications and new services resort often perform their own measurement to obtain necessary information.

Network monitoring is becoming a necessity for network operators, who usually deploy several monitoring applications that aid in tasks such as traffic engineering, capacity planning and the detection of attacks or other anomalies. There is also an increasing interest in large-scale network monitoring infrastructures that can run multiple applications in several network viewpoints [4].

Confronted with the generalization of monitoring in operational networks, researchers have proposed placement algorithms that can help ISPs deploy their monitoring infrastructure in a cost effective way, while maximizing the benefits of their infrastructure. However, a static placement of monitors cannot be optimal given the short-term and long-term variations in traffic due to re-routing events, anomalies and the normal network evolution. In addition, most ISPs already deploy router embedded monitoring functionalities. Despite some limitations (inherent to being part of a router), these monitoring tools give greater visibility on the network traffic but raise the question on how to configure a network-wide monitoring infrastructure that may contain hundreds of monitoring points.We reformulate the placement problem as follows. Given a network where all links can be monitored, which monitors should be activated and which sampling rate should be set on these monitors in order to achieve a given measurement task with high accuracy and low resource consumption? We provide a formulation of the problem, an optimal algorithm to solve it, and we study its performance on a real backbone network.

Network anomaly detection using dimensionality reduction techniques has received much recent attention in the literature. For example, previous work has aggregated netflow records into origin-destination (OD) flows, yielding a much smaller set of dimensions which can then be mined to uncover anomalies. However, this approach can only identify which OD flow is anomalous, not the particular IP flow(s) responsible for the anomaly. In this paper we show how one can use random aggregations of IP flows (i.e., sketches) to enable more precise identification of the underlying causes of anomalies. We show how to combine traffic sketches with a subspace method to (1) detect anomalies with high accuracy and (2) identify the IP flows(s) that are responsible for the anomaly. Our method has detection rates comparable to previous methods and detects many more anomalies than prior work, taking us a step closer towards a robust on-line system for anomaly detection and identification.

Pattern matching and analysis over network data streams is increasingly becoming an essential primitive of network monitoring systems. It is a fundamental part of most intrusion detection systems, worm detecting algorithms and many other anomaly detection mechanisms. It is a processing-intensive task, usually requiring to search for a large number of patterns simultaneously.We propose the technique of "approximate fingerprinting" to reduce the memory demands and significantly accelerate the pattern matching process. The method computes fingerprints of prefixes of the patterns and matches them against the input stream. It acts as a generic preprocessor to a standard pattern matching engine by "clearing" a large fraction of the input that would not match any of the patterns. The main contribution is the "approximate" characteristic of the fingerprint, which allows to slide the fingerprinting window through the packet at a faster rate, while maintaining a small memory footprint and low number of false positives. An improvement over a Bloom filter solution, a fingerprint can indicate which patterns are the candidate matches. We validate our technique by presenting the performance gain for the popular Snort intrusion detection system with the preprocessor in place.

Abstract — Verifying the accuracy of a passive measurementsbased inference technique under all possible network scenarios is a difficult challenge- the measurement point has limited observability of events along the path, and monitored paths can exhibit a wide range of network properties (packet loss, reordering, end-end delay, route changes). In this paper, we propose and apply formal verification techniques to exhaustively verify the correctness of an inference technique. We apply this approach to the problem of inferring packet retransmissions and reorderings from passively observed packets at a single measurement point. We define classification rules for this inference problem and, through a combination of model-checking and formal reasoning, uncover all possible events in the network for which the rules produce incorrect inferences. Our work is novel in its use of formal verification tools for evaluating inference techniques in network measurements. I.

Detecting coordinated attacks on Internet resources requires a distributed network monitoring infrastructure. Such an infrastructure will have two logically distinct elements: distributed monitors that continuously collect traffic information, and a distributed query system that allows network operators to efficiently correlate information from different monitors in order to detect anomalous traffic patterns. In this paper, we discuss the design and implementation of MIND, a distributed index management system that supports the creation and querying of multiple distributed indices. We validate MIND using traffic traces from two large backbone networks, then examine the performance of a MIND prototype on more than 100 PlanetLab machines. Our experiments show that MIND can detect and report network anomalies in about one second on an inter-continental backbone. We also analyze the efficiency of our load balancing mechanism and evaluate the robustness of MIND to node failure. I.

Most of the theoretical work on sampling has addressed the inversion of general traffic properties such as flow size distribution, average flow size, or total number of flows. In this paper, we make a step towards understanding the impact of packet sampling on individual flow properties. We study how to detect and rank the largest flows on a link. To this end, we develop an analytical model that we validate on real traces from two networks. First we study a blind ranking method where only the number of sampled packets from each flow is known. Then, we propose a new method, protocol-aware ranking, where we make use of the packet sequence number (when available in transport header) to infer the number of non-sampled packets from a flow, and hence to improve the ranking. Surprisingly, our analytical and experimental results indicate that a high sampling rate (10% and even more depending on the number of top flows to be ranked) is required for a correct blind ranking of the largest flows. The sampling rate can be reduced by an order of magnitude if one just aims at detecting these flows or by using the protocol-aware method.

By allowing end hosts to make routing decisions at the application level, different overlay networks may unintentionally interfere with each other. This paper describes how multiple similar or dissimilar overlay networks making independent routing decisions could experience race conditions, resulting in oscillations in both route selection and network load. We pinpoint the causes for synchronization in terms of partially overlapping routes and periodic path probing processes and derive an analytic formulation for the synchronization probability of two overlays. Our model indicates that the probability of synchronization is non-negligible across a wide range of parameter settings, thus implying that the ill-effects of synchronization should not be ignored. Using the analytical model, we find an upper bound on the duration of traffic oscillations. We validate our model through simulations that are designed to capture the transient routing behavior of both the IP- and overlay-layers. We use our model to study the effects of factors such as path diversity (measured in round trip times) and probing aggressiveness on these race conditions. Finally, we discuss the implications of our study on the design of overlay networks and the choice of their path probing parameters

We propose a passive measurement methodology to infer and keep track of the values of two important variables associated with a TCP connection: the sender's congestion window (cwnd) and the connection round trip time (RTT). Together, these variables provide a valuable diagnostic of end-user-perceived network performance. Our methodology is validated via both simulation and concurrent active measurements, and is shown to be able to handle various flavors of TCP. Given our passive approach and measurement points within a Tier-1 network provider, we are able to analyze more than 10 million connections, with senders located in more than 45% of the autonomous systems in today's Internet. Our results indicate that sender throughput is frequently limited by a lack of data to send, that the TCP congestion control flavor often has minimal impact on throughput, and that the vast majority of connections do not experience significant variations in RTT during their lifetime

We analyze IS-IS routing updates from sprint's IP network to characterize failures that affect IP connectivity. Failures are first classified based on probable causes such as maintenance activities, router-related and optical layer problems. Key temporal and spatial characteristics of each class are analyzed and, when appropriate, parameterized using well-known distributions. Our results indicate that 20% of all failures is due to planned maintenance activities. Of the unplanned failures, almost 30% are shared by multiple links and can be attributed to router-related and optical equipment-related problems, while 70% affect a single link at a time. Our classification of failures according to different causes reveals the nature and extent of failures in today's IP backbones. Furthermore, our characterization of the different classes can be used to develop a probabilistic failure model, which is important for various traffic engineering problems.

Traditional SLAs, defined by average delay or packet loss, often camouflage the instantaneous performance perceived by end-users. We define a set of metrics for service availability to quantify the performance of IP backbone networks and capture the impact of routing dynamics on packet forwarding. Given a network topology and its link weights, we propose a novel technique to compute the associated service availability by taking into account transient routing dynamics and operational conditions, such as BGP table size and traffic distributions. Even though there are numerous models for characterizing topologies, none of them provide insights on the expected performance perceived by end customers. Our simulations show that the amount of service disruption experienced by similar networks (i.e., with similar intrinsic properties such as average out-degree or network diameter) could be significantly different, making it imperative to use new metrics for characterizing networks. In the second part of the paper, we derive goodness factors based on service availability viewed from three perspectives: ingress node (from one node to many destinations), link (traffic traversing a link), and network-wide (across all source-destination pairs). We show how goodness factors can be used in various applications and describe our numerical results.

We present a measurement study and classification methodology for out-of-sequence packets in TCP connections observed within the Sprint IP backbone. Such out-of-sequence packets can result from many causes including loss, looping, reordering, or duplication in the network. It is important to quantify and understand the causes of such out-of-sequence packets since they are one indication of the "health" of an end-end TCP connection. Our first contribution is methodological. Because we measure out-of-sequence packets at a single point in the backbone (rather than by sending and measuring end-end probe traffic at the sender or receiver), a new methodology is required to infer the causes of a connection's out-of-sequence packets based only on measurements taken in the "middle" of the connection. We thus describe techniques that classify the causes of observed out-of-sequence behavior based only on the previously- and subsequently-observed packets within a connection and knowledge of how TCP behaves. We show that using these simple techniques, it is possible to classify almost all out-of-sequence packets in our traces and that we can quantify the uncertainty in our classification. Our second contribution is the characterization of the out-of-sequence behavior itself. We analyze numerous several-hour packet-level traces from a set of OC-3 and OC-12 links for several million connections generated in nearly 4,300 unique ASs. Our measurements show a relatively consistent amount of out-of-sequence packets of approximately 5%. We find that few out-of-sequence packets result from pathological problems such as routing loops or in network duplication/reordering.

Our goal is to design a traffic model for uncongested IP backbone links that is simple enough to be used in network operation, and that is protocol and application agnostic in order to be as general as possible. The proposed solution is to model the traffic at the flow level by a Poisson shot-noise process. In our model, a flow is a generic notion that must be able to capture the characteristics of any kind of data stream. We analyze the accuracy of the model with real traffic traces collected on the Sprint IP backbone network. Despite its simplicity, our model provides a good approximation of the real traffic observed in the backbone and of its variation. Finally, we discuss three applications of our model to network design and management.

Today's IP backbones are provisioned to provide excellent performance in terms of loss, delay and availability. However, performance degradation and service disruption are likely in the case of failure, such as fiber cuts, router crashes, etc. In this paper, we investigate the occurence of failures in Sprint's IP backbone and their potential impact on emerging services such as Voice-over-IP (VoIP). We first examine the frequency and duration of failure events derived from IS-IS routing updates collected from three different points in the Sprint IP backbone. We observe that link failures occur as part of everyday operation, and the majority of them are short-lived (less than 10 minutes). We also discuss various statistics such as the distribution of inter-failure time, distribution of link failure durations, etc. which are essential for constructing a realistic link failure model. Next, we present an analysis of routing and service reconvergence time during a controlled link failure scenario in our backbone. Our results indicate that disruption to packet forwarding after link failures depends not only on routing protocol dynamics, but also on the design of routers' architectures and control planes. Thus our results offer insights into two basic components for defining network-wide availability, which we consider a more appropriate metric for service-level agreements to support emerging applications.

No abstract available.

We use active and passive traffic measurements to identify the issues involved in the deployment of a voice service over a tier-1 IP backbone network. Our findings indicate that no specific handling of voice packets (i.e. QoS differentiation) is needed in the current backbone but new protocols and mechanisms need to be introduced to provide a better protection against link failures. We discover that link failures may be followed by long periods of routing instability, during which packets can be dropped because forwarded along invalid paths. We also identify the need for a new family of quality of service mechanisms based on fast protection of traffic and high availability of the service rather than performance in terms of delay and loss.

LCA

This paper compares the performance of tail drop and three different flavors of the RED (random early detection) queue management mechanism: RED with a standard parameter setting, RED with an optimized parameter setting based on a model of RED with TCP flows, and finally a version of RED with a smoother drop function called "gentle RED ". The performance is evaluated under various load situations for FTP-like and Web-like flows, respectively. We use measurements and simulations to evaluate the performance of the queue management mechanisms and assess their impact on a set of operator oriented performance metrics. We find that in total (i) no performance improvements of RED compared to tail drop can be observed; (ii) fine tuning of RED parameters is not sufficient to cope with undesired RED behavior due to the variability in traffic load; and (iii) gentle RED is capable of resolving some of the headaches on RED but not all.