Several systems rely on traceroute to track a large number of Internet paths as they change over time. Monitoring systems perform this task by remapping paths periodically or whenever a change is detected. This paper shows that such complete remapping is inefficient, because most path changes are localized to a few hops of a path. We develop RemapRoute, a tool to remap a path locally given the previously known path and a change point. RemapRoute sends targeted probes to locate and remap the often few hops that have changed. Our evaluation with trace-driven simulations and in a real deployment shows that local remapping reduces the average number of probes issued during remapping by 63% and 79%, respectively, when compared with complete remapping. At the same time, our results show that local remapping has little impact on the accuracy of inferred paths.

Recent advances in programmable data planes, software-defined networking, and the adoption of IPv6 support novel, more complex load balancing strategies. We introduce the Multipath Classification Algorithm (MCA), a probing algorithm that extends traceroute to identify and classify load balancing in Internet routes. MCA extends existing formalism and techniques to consider that load balancers may use arbitrary combinations of bits in the packet header for load balancing. We propose optimizations to reduce probing cost that are applicable to MCA and existing load balancing measurement techniques. Through large-scale measurement campaigns, we characterize and study the evolution of load balancing on the IPv4 and IPv6 Internet with multiple transport protocols. Our results show that load balancing is more prevalent and that load balancing strategies are more mature than previous characterizations have found.

The majority of Internet traffic is now dominated by streamed video content. As video quality continues to increase, the strain that streaming traffic places on the network infrastructure also increases. Caching content closer to users, e.g., using Content Distribution Networks, is a common solution to reduce the load on the network. A simple approach to selecting what to put in regional caches is to put the videos that are most popular globally across the entire customer base. However, this approach ignores distinct regional taste. In this paper we explore the question of how a video content provider could go about determining whether or not they should use a cache filling policy based solely upon global popularity or take into account regional tastes as well. We propose a model that captures the overlap between inter-regional and intra-regional preferences. We focus on movie content and derive a synthetic model that captures “taste” using matrix factorization, similarly to the method used in recommender systems. Our model enables us to widely explore the parameter space, and derive a set of metrics providers can use to determine whether populating caches according to regional of global tastes provides better cache performance.

Routing events impact multiple paths in the Internet, but current active topology mapping techniques monitor paths independently. Detecting a routing event on one Internet path does not trigger any measurements on other possibly-impacted paths. This approach leads to outdated and inconsistent routing information. We characterize routing events in the Internet and investigate probing strategies to efficiently identify paths impacted by a routing event. Our results indicate that targeted probing can help us quickly remap routing events and maintain more up-to-date and consistent topology maps.

In this paper, we analyze a large dataset of passive wireless measurements and obtain insights about wireless performance. We monitor 167 homes continuously for 4 months from the vantage point of the gateway, which allows us to capture all the activity on the home wireless network. We report on the makeup of the home wireless network, traffic activity, and performance characteristics. We find that in most homes, a small number of devices account for most of the observed traffic volume and the bulk of this traffic activity occurs in the evenings. Studying link performance, we find that overall, the vast majority of transmissions are carried out at high data rates and the wireless networks have good coverage. We find a small number of episodes where performance is poor; a few homes have a disproportionate number of poor performance reports. Investigating further, we observe that most of these are not caused by poor coverage (pointing to network interference). Our results significantly add to the understanding of home wireless networks and will help ISPs to understand their subscriber networks.

In this paper, we implement and evaluate a system that predicts and tracks Internet path changes to maintain an up-to-date network topology. Based on empirical observations, we claim that monitors can enhance probing according to the likelihood of path changes. We design a simple predictor of path changes and show that it can be used to enhance probe targeting. Our path tracking system, called DTRACK, focuses probes on unstable paths and spreads probes over time to minimize the chances of missing path changes. Our evaluations of DTRACK with trace-driven simulations and with a prototype show that DTRACK can detect up to three times more path changes than traditional trace-route-based topology mapping techniques.

Epidemic content dissemination in opportunistic social networks (OSN) has been analyzed in depth, theoretically and empirically. Most related works have studied the pairwise contact history among nodes in conference or campus environments. We claim that given the nature of these networks, this approach leads to a biased understanding of the content dissemination process. We design a methodology to break OSN traces down into 'temporal communities', i.e., groups of people who meet periodically during an experiment. We show that these communities correlate with people's social communities. As in previous works, we observe that efficient content dissemination is mostly due to high contact rate nodes. However, we show that high contact rate nodes that are more frequently involved in temporal communities contribute less to the dissemination process, leading us to conjecture that social communities tend to limit dissemination in OSNs.

Massively multiplayer online games have become popular in the recent years. Scaling with the number of users is challenging due to the low latency requirements of these games. Peer-to-peer techniques naturally address the scalability issues at the expense of additional complexity to maintain consistency among players.

Online hotel searching is a daunting task due to the wealth of online information. Reviews written by other travelers replace the word-of-mouth, yet turn the search into a time consuming task. Users do not rate enough hotels to enable a collaborative filtering based recommendation. Thus, a cold start recommender system is needed. In this work we design a cold start hotel recommender system, which uses the text of the reviews as its main data. We define context groups based on reviews extracted from TripAdvisor.com and Venere.com. We introduce a novel weighted algorithm for text mining. Our algorithm imitates a user that favors reviews written with the same trip intent and from people of similar background (nationality) and with similar preferences for hotel aspects, which are our defined context groups. Our approach combines numerous elements, including unsupervised clustering to build a vocabulary for hotel aspects, semantic analysis to understand sentiment towards hotel features, and the profiling of intent and nationality groups.

Online hotel searching is a daunting task due to the wealth of online information. Reviews written by other travelers replace the word-of-mouth, yet turn the search into a time consuming task. Users do not rate enough hotels to enable a collaborative filtering based recommendation. Thus, a cold start recommender system is needed. This demo describes briefly our cold start hotel recommender system, which uses the text of the reviews as its main data. We define context groups based on reviews extracted from TripAdvisor.com and Venere.com. We introduce a novel weighted algorithm for text mining.

Opportunistic ad-hoc communication enables portable devices such as smartphones to effectively exchange information, taking advantage of their mobility and locality. The nature of human interaction makes information dissemination using such networks challenging. We use three different experimental traces to study fundamental properties of human interactions. We break our traces down in multiple areas and classify mobile users in each area according to their social behavior: Socials are devices that show up frequently or periodically, while Vagabonds represent the rest of the population. We find that in most cases the majority of the population consists of Vagabonds. We evaluate the relative role of these two groups of users in data dissemination. Surprisingly, we observe that under certain circumstances, which appear to be common in real life situations, the effectiveness of dissemination predominantly depends on the number of users in each class rather than their social behavior, contradicting some of the previous observations. We validate and extend the findings of our experimental study through a mathematical analysis.

This paper investigates to what extent it is possible to use traceroute-style probing for accurately tracking Internet path changes. When the number of paths is large, the usual traceroute based approach misses many path changes because it probes all paths equally. Based on empirical observations, we argue that monitors can optimize probing according to the likelihood of path changes. We design a simple predictor of path changes using a nearest neighbor model. Although predicting path changes is not very accurate, we show that it can be used to improve probe targeting. Our path tracking method, called DTrack, detects up to two times more path changes than traditional probing, with lower detection delay, as well as providing complete load-balancer information.

The success of broadband residential Internet access is changing the way home users consume digital content and services. Currently, each home service requires the installation of a separate physical box (for instance, the NetFlix box or IPTV set-top-boxes). Instead, we argue for deploying a single box in the home that is powerful and flexible enough to host a variety of home services. In addition, this box is managed by the Internet Service provider and is able to provide service guarantees. We call such a box a service-hosting gateway (SHG), as it combines the functionalities of the home gateway managed by the network service provider with the capability of hosting services. Isolation between such services is ensured by virtualization.

Social virtual worlds such as Second Life (SL) are digital representations of the real world where human-controlled avatars evolve and interact through social activities. Understanding the characteristics of virtual worlds can be extremely valuable in order to optimize their design. In this paper, we perform an extensive analysis of SL. We exploit standard avatar capabilities to monitor the virtual world, and we emulate avatar behaviors in order to evaluate user experience. We make several surprising observations. We find that 30% of the regions are never visited during the six-day monitoring period, whereas less than 1% of the regions have large peak populations. Moreover, the vast majority of regions are static, i.e., objects are seldom created or destroyed. Interestingly, we show that avatars interact similarly to humans in real life, gathering in small groups of 2-10 avatars. We also show that user experience is poor. Most of the time, avatars have an incorrect view of their neighbor avatars, and inconsistency can last several seconds, impacting interactivity among avatars.

In opportunistic networks, end-to-end paths between two communicating nodes are rarely available. In such situations, the nodes might still copy and forward messages to nodes that are more likely to meet the destination. The question is which forwarding algorithm offers the best trade off between cost (number of message replicas) and rate of successful message delivery. We address this challenge by developing the PeopleRank approach in which nodes are ranked using a tunable weighted social information. Similar to the PageRank idea, PeopleRank gives higher weight to nodes if they are socially connected to important other nodes of the network. We develop centralized and distributed variants for the computation of PeopleRank. We present an evaluation using real mobility traces of nodes and their social interactions to show that PeopleRank manages to deliver messages with near optimal success rate (close to Epidemic Routing) while reducing the number of message retransmissions by 50% compared to Epidemic Routing.

Traffic anomaly detection has received a lot of attention over recent years, but understanding the nature of these anomalies and identifying the flows involved is still a manual task, in most cases. We introduce Unsupervised Root Cause Analysis (URCA) which isolates anomalous traffic and classifies alarms with minimal manual assistance and high accuracy. URCA proceeds by successive reduction of the anomalous space, eliminating normal traffic based on feedback from the anomaly detection method. Classification is done by clustering a new anomaly with previously labeled events. We validate URCA using manually analyzed real anomalies as well as synthetic anomaly injection. Our validation shows that URCA can accurately diagnose a large range of anomaly types, including network scans, DDoS attacks, and major routing changes.

When many flows are multiplexed on a non-saturated link, their volume changes over short timescales tend to cancel each other out, making the average change across flows close to zero. This equilibrium property holds if the flows are nearly independent, and it is violated by traffic changes caused by several, potentially small, correlated flows. Many traffic anomalies (both malicious and benign) fit this description. Based on this observation, we exploit equilibrium to design a computationally simple detection method for correlated anomalous flows. We compare our new method to two well known techniques on three network links. We manually classify the anomalies detected by the three methods, and discover that our method uncovers a different class of anomalies than previous techniques do.

When many flows are multiplexed on a non-saturated link, their volume changes over short timescales tend to cancel each other out, making the average change across flows close to zero. This equilibrium property holds if the flows are nearly independent, and it is violated by traffic changes caused by several correlated flows. We exploit this empirical property to design a computationally simple anomaly detection method.

Wi-Fi access points can be found in any urban environment and have the potential to be a source of useful bandwidth even for users that are only in range for short periods of time. In this paper, we describe how in-motion networking is capable of exploiting short connection opportunities and transferring significant amounts of data by using only open or community access points. We describe the issues facing the in-motion user of today and present a protocol that is capable of eliminating backhaul bottlenecks at the access point's connection to the Internet. We describe and present the results of our implementation with measurements in an urban area of a city.

Motivated by increased concern over energy consumption in moderndatacenters,wepropose anew,distributedcomputingplatform calledNanoDataCenters(NaDa). NaDausesISP-controlledhome gateways to provide computing and storage services and adopts a managed peer-to-peer model to form a distributed data center infrastructure. To evaluate the potential for energy savings in NaDa platform we pick Video-on-Demand (VoD) services. We develop an energy consumption model for VoD in traditional and in NaDa data centers and evaluate this model using a large set of empirical VoD access data. We find that even under the most pessimistic scenarios, NaDa saves at least 20 % to 30 % of the energy compared to traditional data centers. These savings stem from energypreserving properties inherent to NaDa such as the reuse of already committed baseline power on underutilized gateways, the avoidance of cooling costs, and the reduction of network energy consumption as a result of demand and service co-localization in NaDa. Categories andSubject Descriptors

Abstract: Binary tomography—the process of identifying faulty network links through coordinated end-to-end probes—is a promising method for detecting failures that the network does not automatically mask (e.g., network “blackholes”). Because tomography is sensitive to the quality of the input, however, naive end-to-end measurements can introduce inaccuracies. This paper develops two methods for generating inputs to binary tomography algorithms that improve their inference speed and accuracy. Failure confirmation is a per-path probing technique to distinguish packet losses caused by congestion from persistent link or node failures. Aggregation strategies combine path measurements from unsynchronized monitors into a set of consistent observations. When used in conjunction with existing binary tomography algorithms, our methods identify all failures that are longer than two measurement cycles while inducing relatively few false alarms. In two wide-area networks, our techniques decrease the number of alarms by as much as two orders of magnitude. Compared to the state of the art in

The automatic detection of failures in IP paths is an essential step for operators to perform diagnosis or for overlays to adapt. We study a scenario where a set of monitors send probes toward a set of target end-hosts to detect failures in a given set of IP interfaces. Unfortunately, there is a large probing cost to monitor paths between all monitors and targets at a very high frequency. We make two major contributions to reduce this probing cost. First, we propose a formulation of the probe optimization problem which, in contrast to the established formulation, is not NP complete. Second, we propose two linear programming algorithms to minimize probing cost. Our algorithms combine low frequency per-path probing to detect per-interface failures at a higher frequency. We analyze our solutions both analytically and experimentally. Our theoretical results show that the probing cost increases linearly with the number of interfaces in a random power-law graph. We confirm this linear increase in Internet graphs measured from PlanetLab and RON. Hence, Internet graphs belong to the most costly class of graph to probe.

Network tomography is a promising technique to identify the location of of IP faults. The goal of tomography is to infer the status of network internal characteristics based on end-to-end observations. In particular, binary tomography identifies the set of failed links from end-to-end path meausrments. Upon detecting the failure of one or more of the monitored paths, a monitor sends its measurements to a central coordinator. The coordinator then runs the binary tomography algorithm, which takes as input the topology of the network and the status (i.e., up or down) of all monitored paths and finds the minimum set of links that explain the observations.

Social virtual worlds such as Second Life are digital representations of the real world where human-controlled avatars evolve and interact through social activities. Understanding the characteristics of existing virtual worlds can be extremely valuable to optimize their design. In this work we perform the first extensive analysis of Second Life. We have crawled around 13000 Regions over one month, and gathered information about objects, avatars, and server state. The analysis of our traces shows several surprising results. We find that 30% of the Regions are never visited during a six day period, whereas only few Regions have large peak populations. Moreover, the vast majority of Regions are static, i.e., objects are seldom created or destroyed. Interestingly, avatars interact similarly to humans in real life, gathering in small groups, visiting the same places and meeting the same avatars again, showing a highly predictable behavior. Based on these observations, we discuss several techniques to enhance Second Life or other similar social virtual worlds.

Mobile opportunistic networks are characterized by unpredictable mobility, heterogeneity of contact rates and lack of global information. Successful delivery of messages at low costs and delays in such networks is thus challenging. Most forwarding algorithms avoid the cost associated with flooding the network by forwarding only to nodes that are likely to be good relays, using a quality metric associated with nodes. However it is non-trivial to decide whether an encountered node is a good relay at the moment of encounter. Thus the problem is in part one of online inference of the quality distribution of nodes from sequential samples, and has connections to optimal stopping theory. Based on these observations we develop a new strategy for forwarding, which we refer to as delegation forwarding.

We present Cross-layer Unicast Transmission Time (X-UTT), a MAC-aware load-independent link cost metric for 802.11-based wireless mesh networks. X-UTT utilizes information acquired from a network-layer unicast probing system and a MAC-layer monitoring system. It is designed to capture the wireless link capacity and be independent of the load induced by self-interference and cross-interference in a mesh network. We present experiments that validate these two properties on our mesh network testbed. These properties can be further exploited in the design of stable path metrics and routing protocols for wireless mesh networks.

Portable devices have more data storage and increasing communication capabilities everyday. In addition to classic infrastructure based communication, these devices can exploit human mobility and opportunistic contacts to communicate. We analyze the characteristics of such opportunistic forwarding paths. We establish that opportunistic mobile networks in general are characterized by a small diameter, a destination device is reachable using only a small number of relays under tight delay constraint. This property is first demonstrated analytically on a family of mobile networks which follow a random graph process. We then establish a similar result empirically with four data sets capturing human mobility, using a new methodology to efficiently compute all the paths that impact the diameter of an opportunistic mobile networks. We complete our analysis of network diameter by studying the impact of intensity of contact rate and contact duration. This work is, to our knowledge, the first validation that the so called “small world ” phenomenon applies very generally to opportunistic networking between mobile nodes. 1.

The distributed nature of the Internet makes it difficult for a single service provider to troubleshoot the disruptions experienced by its customers. We propose NetDiagnoser, a troubleshooting algorithm to identify the location of failures in an internetwork environment. First, we adapt the well-known Boolean tomography technique to work in this environment. Then, we significantly extend this technique to improve the diagnosis accuracy in the presence of multiple link failures, logical failures (for instance, misconfigurations of route export filters), and incomplete topology inference. In particular, NetDiagnoser takes advantage of rerouted paths, routing messages collected at one provider's network and Looking Glass servers. We evaluate each feature of Net-Diagnoser separately using C-BGP simulations on realistic topologies. Our results show that NetDiagnoser can successfully identify a small set of links, which almost always includes the actually failed/misconfigured links.

Past approaches to routing in mesh networks either (i) do not account for the MAC-layer interactions between the links in a tractable manner, or (ii) are agnostic to load-balancing across gateways. Our answer to these problems is MaLB (MAC-aware and Load Balanced routing algorithm), a greedy, tractable, and distributed mesh routing algorithm. Since the underlying objective function has high combinatorial complexity, MaLB uses a greedy approach. MaLB finds an optimum routing forest (union of trees rooted at the gateways) by taking into account MAC-layer interaction between links, as well as optimum multi-hop association of mesh nodes to gateways. MaLB builds on top of ETP (Expected Through-Put), a recently proposed MAC-aware routing metric. We also propose a low complexity variant of MaLB called LB (Load Balanced routing algorithm) which performs load balancing in a MAC-agnostic manner. MaLB performs especially well in networks with skewed topologies that result from unplanned mesh network deployment, as well as in the presence of gateway failures. Simulations with an enhanced version of ns-2 show that MaLB results in up to 60% higher throughput than a shortest path algorithm with ETX (Expected Transmission Count). Furthermore, MaLB results in up to 30% improvement over the LB algorithm, as well as a shortest path algorithm with ETT (Expected Transmission Time).

Pocket Switched Networks (PSN) is a novel communication paradigm which aims to exploit the opportunistic contacts between mobile devices to exchange data over multiple hops. A key characteristic and enabler of PSN is the human mobility, and consequently the detection of the arising contact opportunities. In this paper we present a prototype implementation of a software to detect contact opportunities and the initial experimental observations.

Traffic anomalies are specific types of events and conditions which differ from the normal or expected network behavior, and therefore should be brought to the attention of network operators. Examples of such events include, but are not limited to link or router outages, Denial-of-Service (DoS) attacks, flash crowds, port scans and misconfigured devices.

A Networked Virtual Environment (NVE) is a digital world where multiple participants interact via virtual characters called avatar. A popular application for NVEs is Second Life (SL)[5].

Forwarding in Delay Tolerant Networks (DTNs) is a challenging problem. We focus on the specific issue of forwarding in an environment where mobile devices are carried by people in a restricted physical space (a conference) and contact patterns are not predictable. We show for the first time a path explosion phenomenon between most pairs of nodes. This means that, once the first path reaches the destination, the number of subsequent paths grows rapidly with time, so there usually exist many near-optimal paths. We study the path explosion phenomenon both analytically and empirically. Our results highlight the importance of unequal contact rates across nodes for understanding the performance of forwarding algorithms. We also find that a variety of well-known forwarding algorithms show surprisingly similar performance in our setting and we interpret this fact in light of the path explosion phenomenon.

Multiple network-wide anomaly detection techniques proposed in the literature define an anomaly as a statistical outlier in aggregated network traffic. The most popular way to aggregate the traffic is as a Traffic Matrix, where the traffic is divided according to its ingress and egress points in the network. However, the reasons for choosing traffic matrices instead of any other formalism have not been studied yet. In this paper we compare three network-driven traffic aggregation formalisms: ingress routers, input links and origin-destination pairs (i.e. traffic matrices). Each formalism is computed on data collected from two research backbones. Then, a network-wide anomaly detection method is applied to each formalism. All anomalies are manually labeled, as a true or false positive. Our results show that the traffic aggregation level has asignificant impact on the number of anomalies detected and on the false positive rate. We show that aggregating by OD pairs is indeed the most appropriate choice for the data sets and the detection method we consider. We correlate our observations with time series statistics in order to explain how aggregation impacts anomaly detection.

The popularity of IEEE 802.11 WLANs has led to dense deployments in urban areas. High density leads to sub-optimal performance unless the interfering networks learn how to optimally use and share the spectrum. This paper proposes two fully distributed algorithms that allow (i) multiple interfering 802.11 access points to select their operating frequency in order to minimize interference, and (ii) users to choose the access point they attach to, in order to get their fair share of the whole network bandwidth. The proposed algorithms rely on Gibbs sampler, and do not require explicit coordination among the wireless devices. They only require the participating wireless nodes to measure local quantities such as interference and transmission delay. The algorithms are shown to lead to optimal bandwidth sharing, where optimality is defined according to the minimal potential delay. We analytically prove the convergence of the proposed algorithms, and study their performance by simulation.

Detecting anomalous traffic is a crucial part of managing IP networks. In recent years, network-wide anomaly de-tection based on Principal Component Analysis (PCA) has emerged as a powerful method for detecting a wide vari-ety of anomalies. We show that tuning PCA to operate effectively in practice is difficult and requires more robust techniques than have been presented thus far. We analyze a week of network-wide traffic measurements from two IP backbones (Abilene and Geant) across three different traffic aggregations (ingress routers, OD flows, and input links), and conduct a detailed inspection of the feature time se-ries for each suspected anomaly. Our study identifies and evaluates four main challenges of using PCA to detect traf-fic anomalies: (i) the false positive rate is very sensitive to small differences in the number of principal components in the normal subspace, (ii) the effectiveness of PCA is sensi-tive to the level of aggregation of the traffic measurements, (iii) a large anomaly may inadvertently pollute the normal subspace, (iv) correctly identifying which flow triggered the anomaly detector is an inherently challenging problem.

We propose Push-to-Peer, a peer-to-peer system to cooperatively stream video. The main departure from previous work is that content is proactively pushed to peers, and persistently stored before the actual peer-to-peer transfers. The initial content placement increases content availability and improves the use of peer uplink bandwidth. Our specific contributions are: (i) content placement and associated pull policies that allow the optimal use of uplink bandwidth; (ii) performance analysis of such policies in controlled environments such as DSL networks under ISP control; (iii) a distributed load balancing strategy for selection of serving peers.

We study data transfer opportunities between wireless devices carried by humans. We observe that the distribution of the intercontact time (the time gap separating two contacts between the same pair of devices) may be well approximated by a power law over the range [10 minutes; 1 day]. This observation is confirmed using eight distinct experimental data sets. It is at odds with the exponential decay implied by the most commonly used mobility models. In this paper, we study how this newly uncovered characteristic of human mobility impacts one class of forwarding algorithms previously proposed. We use a simplified model based on the renewal theory to study how the parameters of the distribution impact the performance in terms of the delivery delay of these algorithms. We make recommendations for the design of well-founded opportunistic forwarding algorithms in the context of human-carried devices

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.

Pocket Switched Networking (PSN) is a new communication paradigm between mobile devices. It takes advantage of every local communication opportunity, and the physical mobility of the devices, in order to transport data.

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.

Abstract — Studying transfer opportunities between wireless devices carried by humans, we observe that the distribution of the inter-contact time, that is the time gap separating two contacts of the same pair of devices, exhibits a heavy tail such as one of a power law, over a large range of value. This observation is confirmed on six distinct experimental data sets. It is at odds with the exponential decay implied by most mobility models. In this paper, we study how this new characteristic of human mobility impacts a class of previously proposed forwarding algorithms. We use a simplified model based on the renewal theory to study how the parameters of the distribution impact the delay performance of these algorithms. We make recommendation for the design of well founded opportunistic forwarding algorithms, in the context of human carried devices. 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.

Point-to-point delay is an important network performance measure as well as a key parameter in SLAs. We study how to measure and report delay in a concise and meaningful way for an ISP, and how to monitor it efficiently. We analyze various measurement intervals and potential metric definitions. We find that reporting high quantiles (between 0.95 and 0.99)every 10-30 minutes as the most effective way to summarize the delay in an ISP. We then propose an active probing scheme to estimate a high quantile with bounded error. We show that only a small number of probes are sufficient to provide an accurate estimate. We validate the proposed delay monitoring technique on real data collected on the Sprint IP backbone network.

The increasing practicality of large-scale flow capture makes it possible to conceive of traffic analysis methods that detect and identify a large and diverse set of anomalies. However the challenge of effectively analyzing this massive data source for anomaly diagnosis is as yet unmet. We argue that the distributions of packet features (IP addresses and ports) observed in flow traces reveals both the presence and the structure of a wide range of anomalies. Using entropy as a summarization tool, we show that the analysis of feature distributions leads to significant advances on two fronts: (1) it enables highly sensitive detection of a wide range of anomalies, augmenting detections by volume-based methods, and (2) it enables automatic classification of anomalies via unsupervised learning. We show that using feature distributions, anomalies naturally fall into distinct and meaningful clusters. These clusters can be used to automatically classify anomalies and to uncover new anomaly types. We validate our claims on data from two backbone networks (Abilene and Geant) and conclude that feature distributions show promise as a key element of a fairly general network anomaly diagnosis framework.

International audience

We introduce a methodology to predict when and where link additions/upgrades have to take place in an Internet protocol (IP) backbone network. Using simple network management protocol (SNMP) statistics, collected continuously since 1999, we compute aggregate demand between any two adjacent points of presence (PoPs) and look at its evolution at time scales larger than 1 h. We show that IP backbone traffic exhibits visible long term trends, strong periodicities, and variability at multiple time scales. Our methodology relies on the wavelet multiresolution analysis (MRA) and linear time series models. Using wavelet MRA, we smooth the collected measurements until we identify the overall long-term trend. The fluctuations around the obtained trend are further analyzed at multiple time scales. We show that the largest amount of variability in the original signal is due to its fluctuations at the 12-h time scale. We model inter-PoP aggregate demand as a multiple linear regression model, consisting of the two identified components. We show that this model accounts for 98% of the total energy in the original signal, while explaining 90% of its variance. Weekly approximations of those components can be accurately modeled with low-order autoregressive integrated moving average (ARIMA) models. We show that forecasting the long term trend and the fluctuations of the traffic at the 12-h time scale yields accurate estimates for at least 6 months in the future.

Traffic engineering aims to distribute traffic so as to "optimize" some performance criterion. This optimal distribution of traffic depends on both the routing protocol and the forwarding mechanisms in use in the network. In IP networks running the OSPF or IS-IS protocols, routing is over shortest paths, and forwarding mechanisms distribute traffic "uniformly" over equal cost shortest paths. These constraints often make achieving an optimal distribution of traffic impossible. In this paper, we propose and evaluate an approach that can realize near optimal traffic distribution without changes to routing protocols and forwarding mechanisms. In addition, we explore the tradeoff that exists between performance and the configuration overhead that our solution requires. The paper's contributions are in formulating and evaluating an approach to traffic engineering in IP networks that achieves near-optimal performance while preserving the existing infrastructure.

According to conventional wisdom, links connecting different autonomous systems (AS) are the performance bottlenecks in the core of the Internet. The paper presents an empirical evaluation of delays across inter-AS links using hop-limited active probes. The measurements cover a diverse set of Internet paths starting from locations within three large transit Internet service providers (ISPs). We find that most inter-AS links on the Internet paths covered by this study do not contribute significantly to end-to-end delays. The few exceptions are long-haul links with large propagation delays. Furthermore, the delay estimates are fairly stable across days, making it possible for ISPs to choose inter-domain paths or perform traffic engineering based on delay measurement feedback. Our observations also suggest that a very large component of the end-to-end delay for the measured paths usually occurs within a single AS.

Detecting and understanding anomalies in IP networks is an open and ill-defined problem. Toward this end, we have recently proposed the subspace method for anomaly diagnosis. In this paper we present the first large-scale exploration of the power of the subspace method when applied to flow traffic. An important aspect of this approach is that it fuses information from flow measurements taken throughout a network. We apply the subspace method to three different types of sampled flow traffic in a large academic network: multivariate timeseries of byte counts, packet counts, and IP-flow counts. We show that each traffic type brings into focus a different set of anomalies via the subspace method. We illustrate and classify the set of anomalies detected. We find that almost all of the anomalies detected represent events of interest to network operators. Furthermore, the anomalies span a remarkably wide spectrum of event types, including denial of service attacks (single-source and distributed), flash crowds, port scanning, downstream traffic engineering, high-rate flows, worm propagation, and network outage.

We perform a detailed analysis of point-to-point packet delay in an operational tier-1 network. The point-to-point delay is the time between a packet entering a router in one PoP (an ingress point) and its leaving a router in another PoP (an egress point). It measures the one-way delay experienced by packets from an ingress point to an egress point across an ISP's network and provides the most basic information regarding the delay performance of the ISP's network. Using packet traces captured in the operational network, we obtain precise point-to-point packet delay measurements and analyze the various factors affecting them. Through a simple, step-by-step, systematic methodology and careful data analysis, we identify the major network factors that contribute to point-to-point packet delay and characterize their effect on the network delay performance. Our findings are: 1) delay distributions vary greatly in shape, depending on the path and link utilization; 2) after constant factors dependent only on the path and packet size are removed, the 99th percentile variable delay remains under 1 ms over several hops and under link utilization below 90% on a bottleneck; 3) a very small number of packets experience very large delay in short bursts.

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.

We consider the traffic matrix estimation problem in IP backbone networks, whose goal is to accurately estimate the volume of traffic traveling between network endpoints. Previous approaches to this problem involve measuring the volume of traffic on each link in the network during a time interval where the routing configuration is fixed, and exploit a statistical model of the traffic in order to obtain an estimate of the traffic matrix. These previous approaches are prone to large estimation errors because the link measurements from a fixed muting scenario constitute a data set that is simply too limited to provide enough data to enable estimation procedures that yield very small errors. We propose the idea of collecting link measurements under multiple routing scenarios so that the traffic matrix can be determined very accurately. We present an algorithm for determining a sequence of routing configurations, each of which is specified by a set of link weights. We incorporate carrier requirements into our algorithm so that our proposed routing configurations are operationally viable. We present the results of applying our algorithm to some representative IP backbone topologies and discuss the performance trade-offs that arise.

A common traffic engineering design principle is to select a small set of flows, that account for a large fraction of the overall traffic, to be differentially treated inside the network so as to achieve a specific performance objective. We illustrate that one needs to be careful in implementing such an approach because there are tradeoffs to be addressed that arise due to traffic dynamics. We demonstrate that Internet flows are very volatile in terms of volume, and may substantially change the volume of traffic they transmit as time evolves. Currently proposed schemes for flow classification, although attractive due to their simplicity, face challenges due to this property of flows. Bandwidth volatility impacts the amount of load captured in a set of flows, which usually drops both significantly and quickly after flow classification is performed. Thus if the goal is to capture a large fraction of traffic consistently over time, flows will need to be reselected often. Our first contribution is in understanding the impact of flow volatility on the classification schemes employed in a traffic engineering context. Our second contribution is to propose a classification scheme that is capable of addressing the issues identified above by incorporating historical flow information. Using actual Internet data we demonstrate that our scheme outperforms previously proposed schemes, and reduces both the impact of flow volatility on the load captured by the selected set of flows and the required frequency for its reselection.

Anomalies are unusual and significant changes in a network's traffic levels, which can often span multiple links. Diagnosing anomalies is critical for both network operators and end users. It is a difficult problem because one must extract and interpret anomalous patterns from large amounts of high-dimensional, noisy data.In this paper we propose a general method to diagnose anomalies. This method is based on a separation of the high-dimensional space occupied by a set of network traffic measurements into disjoint subspaces corresponding to normal and anomalous network conditions. We show that this separation can be performed effectively by Principal Component Analysis.Using only simple traffic measurements from links, we study volume anomalies and show that the method can: (1) accurately detect when a volume anomaly is occurring; (2) correctly identify the underlying origin-destination (OD) flow which is the source of the anomaly; and (3) accurately estimate the amount of traffic involved in the anomalous OD flow.We evaluate the method's ability to diagnose (i.e., detect, identify, and quantify) both existing and synthetically injected volume anomalies in real traffic from two backbone networks. Our method consistently diagnoses the largest volume anomalies, and does so with a very low false alarm rate.

Recent work in network traffic matrix estimation has focused on generating router-to-router or PoP-to-PoP (Point-of-Presence) traffic matrices within an ISP backbone from network link load data. However, these estimation techniques have not considered the impact of inter-domain routing changes in BGP (Border Gateway Protocol) . BGP routing changes have the potential to introduce significant errors in estimated traffic matrices by causing traffic shifts between egress routers or PoPs within a single backbone network. We present a methodology to correlate BGP routing table changes with packet traces in order to analyze how BGP dynamics affect traffic fan-out within a large "tier-1" network. Despite an average of 133 BGP routing updates per minute, we find that BGP routing changes do not cause more than 0.03% of ingress traffic to shift between egress PoPs. This limited impact is mostly due to the relative stability of network prefixes that receive the majority of traffic -- 0.05% of BGP routing table changes affect intra-domain routes for prefixes that carry 80% of the traffic. Thus our work validates an important assumption underlying existing techniques for traffic matrix estimation in large IP networks.

This paper provides an authoritative knowledge of through-router packet delays and therefore a better understanding of data network performance. Thanks to a unique experimental setup, we capture all packets crossing a router for 13 hours and present detailed statistics of their delays. These measurements allow us to build the following physical model for router performance: each packet experiences a minimum router processing time before entering a fluid output queue. Although simple, this model reproduces the router behaviour with excellent accuracy and avoids two common pitfalls. First we show that in-router packet processing time accounts for a significant portion of the overall packet delay and should not be neglected. Second we point out that one should fully understand both link and physical layer characteristics to use the appropriate bandwidth value.Focusing directly on router performance, we provide insights into system busy periods and show precisely how queues build up inside a router. We explain why current practices for inferring delays based on average utilization have fundamental problems, and propose an alternative solution to directly report router delay information based on busy period statistics.

Network traffic arises from the superposition of Origin-Destination (OD) flows. Hence, a thorough understanding of OD flows is essential for modeling network traffic, and for addressing a wide variety of problems including traffic engineering, traffic matrix estimation, capacity planning, forecasting and anomaly detection. However, to date, OD flows have not been closely studied, and there is very little known about their properties.We present the first analysis of complete sets of OD flow time-series, taken from two different backbone networks (Abilene and Sprint-Europe). Using Principal Component Analysis (PCA), we find that the set of OD flows has small intrinsic dimension. In fact, even in a network with over a hundred OD flows, these flows can be accurately modeled in time using a small number (10 or less) of independent components or dimensions.We also show how to use PCA to systematically decompose the structure of OD flow timeseries into three main constituents: common periodic trends, short-lived bursts, and noise. We provide insight into how the various constitutents contribute to the overall structure of OD flows and explore the extent to which this decomposition varies over time.

SNMP statistics are usually collected over intervals of 5 minutes and correspond to average activity of IP links and network elements for the duration of the interval. Nevertheless, reports of traffic performance across periods of minutes can mask out performance degradation due to short-lived events, such as micro-congestion episodes, that manifest themselves at smaller time scales. In this paper we perform a measurement study of packet traces collected inside the Sprint IP network to identify the time scales over which micro-congestion episodes occur. We characterize these episodes with respect to their amplitude, frequency and duration. We define a new performance metric that could be easily computed by a router and reported every 5 minutes through SNMP to shed light into the micro-behavior of the carried traffic. We show that the proposed performance metric is well suited to track the time scales over which micro-congestion episodes occur, and may be useful for a variety of network provisioning tasks.

Routing loops are caused by inconsistencies in the routing state of the network. Although undesirable from this aspect, they can provide insight into the routing dynamics that caused them. In this work we present a methodology that utilizes a priori knowledge of loops to study the correlation between routing loops and routing events that could have caused them. We apply our technique to associate route changes with packet loops detected in actual traffic traces collected from the Sprint Backbone. Our study shows that a strong correlation exists between loops and changes in the BGP routing state while the link state protocols ISIS is seldom responsible for such events. Our analysis also identifies factors that influence the distribution of loop path lengths as well as the effectiveness of our detection techniques.

To support latency sensitive traffic such as voice, network providers can either use service differentiation to prioritize such traffic or provision their network with enough bandwidth so that all traffic meets the most stringent delay requirements. In the context of wide-area Internet backbones, two factors make overprovisioning an attractive approach. First, the high link speeds and large volumes of traffic make service differentiation complex and potentially costly to deploy. Second, given the degree of aggregation and resulting traffic characteristics, the amount of overprovisioning necessary may not be very large. This study develops a methodology to compute the amount of overprovisioning required to support a given delay requirement. We first develop a model for backbone traffic which is needed to compute the end-to-end delay through the network. The model is validated using 331 one-hour traffic measurements collected from the Sprint IP network. We then develop a procedure which uses this model to find the amount of bandwidth needed on each link in the network so that an end-to-end delay requirement is satisfied. Applying this procedure to the Sprint network, we find that satisfying end-to-end delay requirements as low as 3 ms requires only 15% extra bandwidth above the average data rate of the traffic.

There are two fundamental technology issues that challenge the robustness of IP backbones. First, SONET protection is gradually being removed because of its high cost (while SONET framing is kept for failure detection purposes). Protection and restoration are provided by the IP layer that operates directly over a DWDM infrastructure. Second, ISPs are systematically forced to use the shortest distance path between two points of presence in order to meet their promised SLAs. In this context, IP backbones are extremely vulnerable to fiber cuts that can bring down a significant fraction of the IP routes. We propose two solutions (an ILP model and a heuristic algorithm) to optimally map a given IP topology onto a fiber infrastructure. The version of the mapping problem that we address incorporates a number of real constraints and requirements faced by carriers today. The optimal mapping maximizes the robustness of the network while maintaining the ISP's SLA delay requirements. In addition, our heuristic takes into consideration constraints such as a shortage of wavelengths and priorities among POPs and routes. The heuristic is evaluated on the Sprint backbone network. We illustrate the tradeoffs between the many requirements.

Shortest path routing protocols may suffer from congestion due to the use of a single shortest path between a source and a destination. The goal of our work is to first understand how links become overloaded in an IP backbone, and then to explore if the routing protocol, -either in its existing form, or in some enhanced form could be made to respond immediately to overload and reduce the likelihood of its occurrence. Our method is to use extensive measurements of Sprint's backbone network, measuring 138 links between September 2000 and June 2001. We find that since the backbone is designed to be overprovisioned, link overload is rare, and when it occurs, 80% of the time it is caused due to link failures. Furthermore, we find that when a link is overloaded, few (if any) other links in the network are also overloaded. This suggests that deflecting packets to less utilized alternate paths could be an effective method for tackling overload. We analytically derive the condition that a network, which has multiple equal length shortest paths between every pair of nodes (as is common in the highly meshed backbone networks) can provide for loop-free deflection paths if all the link weights are within a ratio 1 + 1/(d- I) of each other; where d is the diameter of the network. Based on our measurements, the nature of the backbone topology and the careful use of link weights, we propose a deflection routing algorithm to tackle link overload where each node makes local decisions. Simulations suggest that this can be a simple and efficient way to overcome link overload, without requiring any changes to the routing protocol.

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.

We introduce a methodology to predict when and where link additions/upgrades have to take place in an IP backbone network. Using SNMP statistics, collected continuously since 1999, we compute aggregate demand between any two adjacent PoPs and look at its evolution at time scales larger than one hour. We show that IP backbone traffic exhibits visible long term trends, strong periodicities, and variability at multiple time scales. Our methodology relies on the wavelet multiresolution analysis and linear time series models. Using wavelet multiresolution analysis, we smooth the collected measurements until we identify the overall long-term trend. The fluctuations around the obtained trend are further analyzed at multiple time scales. We show that the largest amount of variability in the original signal is due to its fluctuations at the 12 hour time scale. We model inter-PoP aggregate demand as a multiple linear regression model, consisting of the two identified components. We show that this model accounts for 98% of the total energy in the original signal, while explaining 90% of its variance. Weekly approximations of those components can be accurately modeled with low-order autoregressive integrated moving average (ARIMA) models. We show that forecasting the long term trend and the fluctuations of the traffic at the 12 hour time scale yields accurate estimates for at least six months in the future.

Traffic engineering is aimed at distributing traffic so as to "optimize" a given performance criterion. The ability to carry out such an optimal distribution depends on both the routing protocol and the forwarding mechanisms in use in the network. In IP networks running the OSPF or IS-IS protocols, routing is over shortest paths, and forwarding mechanisms are constrained to distributing traffic uniformly over equal cost shortest paths. These constraints often make achieving an optimal distribution of traffic impossible. In this paper, we propose and evaluate an approach, based on manipulating the set of next hops for routing prefixes, that is capable of realizing near optimal traffic distribution without any change to existing routing protocols and forwarding mechanisms. In addition, we explore the tradeoff that exists between performance and the overhead associated with the additional configuration steps that our solution requires. The paper's contributions are in formulating and evaluating an approach to traffic engineering for existing IP networks that achieves performance levels comparable to that offered when deploying other forwarding technologies such as MPLS.

The small-time (sub-seconds) scaling behaviors of Internet backbone traffic, based on traces collected from OC3/12/48 links in a tier-1 ISP is studied. We observe that for a majority of these traces, the (second-order) scaling exponents at small time scales (1 ms - 100 ms) are fairly close to 0.5, indicating that traffic fluctuations at these time scales are (nearly) uncorrelated. In addition, the traces manifest mostly monofractal behaviors at small time scales. The objective of the paper is to understand the potential causes or factors that influence the small-time scalings of Internet backbone traffic via empirical data analysis. We analyze the traffic composition of the traces along two dimensions - flow size and flow density. Our study uncovers dense flows (i.e., flows with bursts of densely clustered packets) as the correlation-causing factor in small time scales, and reveals that the traffic composition in terms of proportions of dense vs. sparse flows plays a major role in influencing the small-time scalings of aggregate traffic.

We measure and analyze the single-hop packet delay through operational routers in the Sprint Internet protocol (IP) backbone network. After presenting our delay measurements through a single router for OC-3 and OC-12 link speeds, we propose a methodology to identify the factors contributing to single-hop delay. In addition to packet processing, transmission, and queueing delay at the output link, we observe the presence of very large delays that cannot be explained within the context of a first-in first-out output queue model. We isolate and analyze these outliers. Results indicate that there is very little queueing taking place in Sprint's backbone. As link speeds increase, transmission delay decreases and the dominant part of single-hop delay is packet processing time. We show that if a packet is received and transmitted on the same linecard, it experiences less than 20 μs of delay. If the packet is transmitted across the switch fabric, its delay doubles in magnitude. We observe that processing due to IP options results in single-hop delays in the order of milliseconds. Milliseconds of delay may also be experienced by packets that do not carry IP options. We attribute those delays to router idiosyncratic behavior that affects less than 1% of the packets. Finally, we show that the queueing delay distribution is long-tailed and can be approximated with a Weibull distribution with the scale parameter a=0.5 and the shape parameter b=0.6 to 0.82.

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.

Routing loops are caused by inconsistencies in routing state among a set of routers. They occur in perfectly engineered networks, and have a detrimental effect on performance. They impact end-to-end performance through increased packet loss and delay for packets caught in the loop, and through increased link utilization and corresponding delay and jitter for packets that traverse the link but are not caught in the loop.Using packet traces from a tier-1 ISP backbone, we first explain how routing loops manifest in packet traces. We characterize routing loops in terms of the packet types caught in the loop, the loop sizes, and the loop durations. Finally, we analyze the impact of routing loops on network performance in terms of loss and delay.

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.

No abstract available.

We measure and analyze the single-hop packet delay through operational routers in a backbone IP network. First we present our delay measurements through a single router. Then we identify step-by-step the factors contributing to single-hop delay. In addition to packet processing, transmission, and queueing delays, we identify the presence of very large delays due to non-work-conserving router behavior. We use a simple output queue model to separate those delay components. Our step-by-step methodology used to ohtain the pure queueing delay is easily applicable to any single-hop delay measurements. After obtaining the queueing delay, we analyze the tail of its distribution, and find that it is long tailed and fits a Weihull distrihution with the scale parameter, a = 0.5, and the shape parameter, b = 0.58 to 0.6. The measured average queueing delay is larger than predicted by M/M/l, M/G/l, and FBM models when the link utilization is below 70%, but its absolute value is quite small.

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.

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.

LCA

1441-1443

We study the impact of random queueing delays stemming from traffic variability on the performance of a multicast session. With a simple analytical model, we analyze the throughput degradation within a multicast (one-to-many) tree under TCP-like congestion and flow control. We use the (max,plus) formalism together with methods based on stochastic comparison (association and convex ordering) and on the theory of extremes to prove various properties of the throughput. We first prove that the throughput predicted by a deterministic model is systematically optimistic. In the presence of light-tailed random delays, we show that the throughput decreases according to the inverse of the logarithm of the number of receivers. We find analytically an upper and a lower bound for the throughput degradation. Within these bounds, we characterize the degradation which is obtained for various tree topologies. In particular, we observe that a class of trees commonly found in IP multicast sessions is significantly more sensitive to traffic variability than other topologies.

We study the impact of random noise (queueing delay) on the performance of a multicast session. With a simple analytical model, we analyze the throughput degradation within a multicast (one-to-many) tree under TCP-like congestion and flow control. We use the (max, plus) formalism together with methods based on stochastic comparison (association and convex ordering) and on the theory of extremes (Lai and Robbins' (1978) notion of maximal characteristics) to prove various properties of the throughput. We first prove that the throughput obtained from Golestani and Sabnani's (1999) deterministic model is systematically optimistic. In presence of light tailed random noise, we show that the throughput decreases like the inverse of the logarithm of the number of receivers. We find analytically an upper and a lower bound for the throughput degradation. Within these bounds, we characterize the degradation which is obtained for various tree topologies. In particular, we observe that a class of trees commonly found in IP multicast sessions (which we call umbrella trees) is significantly more sensitive to network noise than other topologies.

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.

Large-scale applications are characterized by a large number of dynamic and often interactive group members. The nature of these applications is such that participants are not interested in all the content transmitted. We examine three currently available techniques to scope delivery of content to interested receivers in IP multicast: filtering, where data is filtered by middleware before being passed to the application; addressing, where data is routed only to those receivers that express their interest; and hybrid approaches. We propose a framework that models large-scale application behavior. We use this framework to evaluate the performance of these applications and related protocols when the network is capable of filtering or addressing. Our results show that the current Internet architecture does not efficiently support large-scale applications because it can not efficiently manage multiple multicast groups. We show that network-level addressing is preferred to filtering and hybrid approaches given that groups are easy to create and manage. We highlight areas of research in the multicast architecture to bring about this change.

The Differentiated services (diffserv) architecture has been proposed as a scalable solution for providing service differentiation among flows without any per-flow buffer management inside the core of the network. It has been advocated that it is feasible to provide service differentiation among a set of flows by choosing an appropriate “marking profile” for each flow. In this paper, we examine (i) whether it is possible to provide service differentiation among a set of TCP flows by choosing appropriate marking profiles for each flow, (ii) under what circumstances, the marking profiles are able to influence the service that a TCP flow receives, and, (iii) how to choose a correct profile to achieve a given service level. We derive a simple, and yet accurate, analytical model for determining the achieved rate of a TCP flow when edge-routers use “token bucket” packet marking and core-routers use active queue management for preferential packet dropping. From our study, we observe three important results: (i) the achieved rate is not proportional to the assured rate, (ii) it is not always possible to achieve the assured rate and, (iii) there exist ranges of values of the achieved rate for which token bucket parameters have no influence. We find that it is not easy to regulate the service level achieved by a TCP flow by solely setting the profile parameters. In addition, we derive conditions that determine when the bucket size influences the achieved rate, and rates that can be achieved and those that cannot. Our study provides insight for choosing appropriate token bucket parameters for the achievable rates.

This paper reports on the design and the evaluation of transmission control mechanisms specifically designed for multiplayer, distributed (serverless), interactive Internet applications. Distributed synchronization and dead reckoning are the main elements of this transmission control infrastructure. These mechanisms have been implemented in a fully distributed, multiplayer game application, i.e., one in which each entity in a game session computes its own local view of the session. The role of each entity is consequently to periodically send its own state to all other session participants (using RTP/UDP/IP multicast) and to periodically compute its own local view of the global game state using information received from the other participants. A detailed experimental analysis is provided using MBone and LAN experiments. We investigate how the "quality" of the game is influenced by the frequency at which players exchange state information, as well as by network impairments such as packet loss and transmission delay.

Schemes based on the tagging of packets have been proposed as a low-cost way to augment the single class best effort service model of the current Internet by including some kind of service discrimination. Such schemes have a number of attractive features, however, it is not clear exactly what kind of service they would provide to applications. Yet quantifying such service is very important to understand the benefits and drawbacks of the different tagging schemes and of the mechanisms in each scheme (for example how much RED with input and output (RIO) contributes in the assured scheme), and to tackle key performance and economic issues (e.g. the difference in tariff between different service classes would presumably depend on the difference in performance between the classes). The goal in this paper is to obtain a quantitative description of the service provided by tagging schemes. Specifically, we describe and solve simple analytic models of two previously proposed schemes, namely the assured service scheme and the premium service scheme. We obtain expressions for performance measures that characterize the service provided to tagged packets, the service provided to non-tagged packets, and the fraction of tagged packets that do not get the better service they were supposed to. We use these expressions, as well as simulations and experiments from actual implementations, to illustrate the benefits and shortcomings of the schemes.

The application level framing (ALF) principle states that information should be packetized by the application into application data units (ADUs), each of which should be at the same time a unit of transmission, a unit of control, and a unit of processing. This paper describes a communication system architecture based on the ALF principle, which then attempts to maximize what might be gained from using ADUs. In this architecture, protocols are tailored to application requirements, i.e., to ADU types. In a first approximation, we consider three specific requirements, namely, in-order delivery, reliable delivery, and real-time delivery. ALF-based systems promise performance gains; however, implementing them in practice might be a complex task. Therefore, we have developed a compiler that automatically generates ALF-based communication systems starting from formal specification of applications. We have used this compiler to generate protocols tailored to three specific applications. Experimental results show that the gains are linked to application "complexity".

Group communication supports information transfer between a set of participants. It is becoming more and more relevant in distributed environments. For distributed or replicated data, it provides efficient communication without overloading the network. For some types of multimedia applications, it is the only way to control data transmission to group members. This paper surveys protocol functions and mechanisms for data transmission within a group, from multicast routing problems up to end-to-end multipoint transmission control. We provide a bibliography which is organized by topic.

This paper describes the design and the prototyping of a compiling tool for the automated implementation of distributed applications: ALFred. This compiler starts from the formal specification of an application written in ESTEREL and then integrates end-to-end communication functions tailored to the application characteristics (described in the specification); it finally produces a high performance implementation. The paper describes the communication architecture associated with the approach. The compiler consists of a control compiler, also called ALF compiler, and a data manipulation compiler (the ILP compiler) that combines data manipulation functions in an efficient way (the ILP loop). The ALFred compiler has been designed to allow the development and the analysis of non-layered high performance communication architectures based on ALF and ILP.

Integrated layer processing (ILP) is an implementation concept that "permits the implementor the option of performing all the (data) manipulation steps in one or two integrated processing loops". To estimate the achievable benefits of ILP, a file transfer application with an encryption function on top of a user-level TCP has been implemented and the performance of the application in terms of throughput and packet processing times has been measured. The results show that it is possible to obtain performance benefits by integrating marshalling, encryption, and TCP checksum calculation. The experiments yielded in a throughput gain of only 10-20% in contrast to the 50% gain achieved for simple loop experiments. Simulations of memory access and cache hit rate show that the main benefit of ILP is reduced memory access rather than an improved cache hit rate. ILP reduced the number of memory accesses up to 30% in the experiment, but the relative amount of cache misses could not be reduced compared to a carefully designed non-ILP implementation. The results also show that data manipulation characteristics may significantly influence the cache behavior and the achievable performance gain of ILP. Considering these results, ILP can only be recommended in cases where the the ILP loop consists of several, but very simple data manipulations without complex calculations over the data.

Integrated Layer Processing (ILP) is an implementation concept which "permit[s] the implementor the option of performing all the [data] manipulation steps in one or two integrated processing loops" [1]. To estimate the achievable benefits of ILP, a file transfer application with an encryption function on top of a user-level TCP has been implemented and the performance of the application in terms of throughput and packet processing times has been measured. The results show that it is possible to obtain performance benefits by integrating marshalling, encryption and TCP checksum calculation. They also show that the benefits are smaller than in simple experiments, where ILP effects have not been evaluated in a complete protocol environment. Simulations of memory access and cache hit rate show that the main benefit of ILP is reduced memory accesses rather than an improved cache hit rate. The results further show that data manipulation characteristics may significantly influence the cache b...

XTP is a real time transfer protocol designed to be implemented in a dedicated hardware environment. To obtain a transputer based parallel implementation, the authors modified a standard implementation (based on UNIX BSD system) on three aspects: the structure of the implementation, interfaces with host, and system primitive references. This new implementation was modelled. Performance was analyzed. This paper tries, in two sections to distinguish what in the performance is linked to the protocol specification and what is the consequence of the implementation. For this purpose, the KRM is compared to a high performance implementation of OSI TP4 the authors had previously modelled. XTP high performance conditions of implementation (including software techniques and multi-processor host architectures) are discussed.>

General-purpose protocols such as open systems interconnection (OSI) transport protocol class 4 (TP4) are confronted with new requirements in computer communication. The services proposed become unadapted and performance insufficient. Then appears a new generation of high-speed protocols designed for real-time applications or VLSI implementation. TP4 performance and its modeling for multiprocessor implementation are analyzed. Functionalities efficiency and implementation characteristics (about dedicated data structures, resources management, and dedicated algorithms) are presented. General elements on TP4 availability are discussed, and implementation environment characteristics are presented.>