Most deployed WAN Traffic Engineering (TE) systems use a logically centralized controller that periodically gathers traffic demands, runs a TE optimization or heuristic, and then programs the network. At scale, these solutions are often suboptimal and can take minutes to react to demand changes or failures. In this paper, we introduce OnlineTE, a system that reacts immediately to demand changes and failures and delivers near-optimal solutions within seconds of a change. OnlineTE builds on the theory of optimization decomposition to devise scalable, near-optimal, distributed TE solvers for path-based MLU and Max-Flow problems. In OnlineTE, switches each solve a local subproblem, and a central coordinator coordinates their convergence. As such, a switch can trigger a re-optimization as soon as it detects a demand change or failure, enabling high reactivity. OnlineTE scales to large WANs, and its computational requirements are well within the capabilities of modern WAN switches. It also enables a novel paradigm, edge-based TE, which can utilize resources more efficiently than today's path-based approaches. On a testbed emulation of a 750-node WAN topology, OnlineTE outperforms the state-of-the-art by up to an order of magnitude.

Even though scientific studies have shown that humans are inherently visual creatures, nearly every published networking research paper presents its results in the form of figures such as line graphs, histograms, bar charts, or scatter plots that can be printed on paper but are often some of the least memorable aspects of a paper. In this work, we call on networking researchers to be more creative in utilizing digital media to communicate the findings of their studies and be more cognizant of the extraordinary capabilities of human readers to process and retain visual information, especially as network telemetry datasets critical for monitoring and diagnosing "network health" continue to grow in size and in the amount of semantic-rich information they contain. To illustrate what we have in mind, we consider the use case where sets of simultaneously collected time series that represent latency measurements over time between different pairs of routers or vantage points within a network (e.g., ES-net) are used to define that network's dynamically changing delay space. By representing successive snapshots of this delay space as 2D manifolds in 3D and animating the resulting manifold views, we transform the information contained in all the simultaneously collected time series into a visualization that effectively shows how a network "breathes" and that can be directly used for diagnosing aspects of a network's health.

This work presents a systematic investigation into the latent knowledge encoded within Network Foundation Models (NFMs). Different from existing efforts, we focus on hidden representations analysis rather than pure downstream task performance and analyze NFMs through a three-part evaluation: Embedding Geometry Analysis to assess representation space utilization, Metric Alignment Assessment to measure correspondence with domain-expert features, and Causal Sensitivity Testing to evaluate robustness to protocol perturbations. Using five diverse network datasets spanning controlled and real-world environments, we evaluate four state-of-the-art NFMs, revealing that they all exhibit significant anisotropy, inconsistent feature sensitivity patterns, an inability to separate the high-level context, payload dependency, and other properties. Our work identifies numerous limitations across all models and demonstrates that addressing them can significantly improve model performance (up to 0.35 increase in $F_1$ scores without architectural changes).

Machine learning is increasingly used in programmable data planes, such as switches [4, 12, 13] and smartNICs [1, 16], to enable real-time traffic analysis and security monitoring at line rate. Decision trees (DTs) are particularly well-suited for these tasks due to their interpretability and compatibility with the Reconfigurable Match-Action Table (RMT) architecture. However, current DT implementations require collecting all features upfront, which limits scalability and accuracy due to constrained data plane resources.

In just a few decades, the Internet has evolved from a research prototype to a cyber-physical infrastructure of critical importance for modern society and the global economy. Surprisingly, despite its new role, the survivability of the Internet-its ability to fulfill its mission in the presence of large-scale failures-has received limited attention. We introduce Domino, our initial design and implementation of a testbench tool for stress testing the Internet's routing system, a key element of the critical Internet infrastructure. The simulation-based testbench consists of a comprehensive and flexible framework that allows for the incorporation of diverse survivability metrics, provides a platform for specifying, evaluating, and comparing different topologies of the underlying Internet infrastructure, and can account for modifications to networking protocols and architectural components. By demonstrating the utility of the proposed testbench with a number of illustrative examples, we make a case for stress testing as a viable approach to evaluating the Internet's survivability in the face of evolving challenges.

Todays enterprise networks wrestle with accommodating an ever-growing number of devices of different types, supporting increasingly demanding applications and ever more complex services, and protecting their users from sophisticated and disrupting cyber threats. In response, a proposed architectural approach for improving network management, referred to as Intent-Based Networking (IBN), has attracted significant attention. It is built on the premise that network operators specify network policies in natural language and the network correctly translates these spoken intents (e.g., policies) into proper device-specific configurations that are then deployed across the network to reliably act on the operators expressed intents. Unfortunately, IBN has not yet fully delivered on its promise of automated, fast, and reliable policy deployment, mainly due to the significant challenges that the reliance on methods from Natural Language Processing (NLP) or more recent techniques from Machine Learning (ML) and Artificial Intelligence (AI) poses for unambiguously and accurately translating the myriad of intents that operators can express in natural language into “trustworthy” device configurations. This paper uses LUMI, a recently designed end-to-end prototype of a system that allows operators “to manage their network by talking to the network”, as an illustrative case study. In particular, we use it to elaborate on the different functionalities such systems should have to realize IBNs vision of automating the fast deployment of policies. At the same time, we leverage LUMI to highlight the extra efforts that are required to ensure that the deployed policies can be entrusted to accurately express and execute the operators original intents.

In just a few decades, the Internet has evolved from a research prototype to a critical infrastructure for modern society and the global economy. Despite its importance, the Internet's survivability amid large-scale failures has received limited attention. We present a testbench design for stress testing the Internet's routing system. This simulation-based framework allows for flexible integration of survivability metrics, evaluation of different topologies, and assessment of protocol and architectural changes. With several illustrative examples, we show the effectiveness of our proposed testbench and make a case for stress testing as a viable approach to evaluating the survivability of inter-domain routing against evolving challenges.

As increasingly complex and dynamic volumetric DDoS attacks continue to wreak havoc on edge networks, two recent developments promise to bolster DDoS defense at the edge. First, programmable switches have emerged as promising means for achieving scalable and cost-effective attack signature detection. However, their practical application in edge networks remains a challenging open problem. Second, machine learning (ML)-based solutions have demonstrated potential in accurately detecting attack signatures based on per-flow traffic features. Yet, their inability to effectively scale to the traffic volumes and number of flows in actual production edge networks has largely excluded them from practical considerations.In this paper, we introduce ZAPDOS, a novel approach to accurately, quickly, and scalably detect volumetric DDoS attack signatures at the source prefix level. ZAPDOS is the first to utilize a key characteristic of the observed structure of measured attack and benign source prefixes (i.e., a pronounced cluster-within-cluster property) and effectively apply it in practice against modern attacks. ZAPDOS operates by monitoring aggregate prefix-level features in switch hardware, employing a learning model to identify prefixes suspected of containing attack sources, and using several innovative algorithmic methods to pinpoint attack sources efficiently. We have built a hardware prototype of ZAPDOS and a packet-level software simulator which achieve comparable accuracy results. Since existing datasets are inadequate for training and evaluating prefix-level models, we have developed a new data-fusion methodology for training and evaluating ZAPDOS. We use our prototype and simulator to show that ZAPDOS can detect volumetric DDoS attack signatures with orders of magnitude lower error rates than state-of-the-art under comparable monitoring resource budgets and for a range of different attack scenarios.

Network telemetry systems provide critical visibility into the state of network traffic. By leveraging modern programmable switch hardware, significant progress has been made to scale these systems to production network traffic workloads. Less attention has been paid towards efficiently utilizing these hardware targets’ limited resources in the face of dynamics such as the composition of the traffic workload as well as the number and types of queries running at any given point in time. However, both of these dynamics have implications on resource requirements and query accuracy. Building on our prior work DynATOS, which argues that this dynamics problem motivates reframing telemetry systems as resource schedulers, we present in this paper the design, implementation, and evaluation of DynATOS+. DynATOS+ relies on the same efficient time-division approximation and scheduling algorithm that DynATOS uses and that allows for user-defined query accuracy and latency specifications that are intended to result in tradeoffs with respect to query execution to reduce hardware resource usage. However, unlike DynATOS, DynATOS+ significantly reduces the burden on end users to express their queries by allowing them to use simple-to-state accuracy goals. For example, the method for specifying per-query accuracy goals in DynATOS+ no longer requires end users to either know the average range of query results in advance or to submit multiple trial queries to tune their accuracy goal specifications. We perform extensive simulation-based evaluations that (i) show that this new functionality of DynATOS+ works in practice, (ii) illustrate in detail the tradeoffs that result with respect to query execution and hardware resource usage for a wide range of systems parameters, and (iii) allow for an assessment of system performance under changing query workloads on top of changes in the composition of traffic workloads that has eluded previous work in this area.

Modern enterprises are increasingly adopting multicloud strategies (i.e. connecting islands of resources from disparate public cloud providers, or CPs for short) due to benefits such as competitive pricing, global expansion, or improved reliability. While these benefits are compelling in their own right, what is critically lacking is a framework for establishing optimized multi-cloud overlays atop individual CP backbones in a performance- and cost-aware manner. A key challenge is that we have little understanding of the performance characteristics of CPs' private backbones in light of multi-cloud overlays. To address this challenge, we present a third-party, cloud-centric study to understand and examine the path, delay, and traffic-cost characteristics of CP backbones by deploying VMs in three global-scale CPs (i.e. AWS, Azure, and GCP). Our measurements reveal new insights including the “optimal backbone of cloud backbones” and a lack of path and delay asymmetries in it. Next, we report on several instances where performance-awareness of multi-cloud paths offer better latency reductions than default paths provided by CPs. While these results make a strong case for performance-aware multi-cloud overlays, the problem is further complicated by the varying transit costs/pricing models of CPs across different geographic regions. Based on our findings, we propose a research agenda for creating performance- and cost-aware multi-cloud overlays that deals with issues such as egress costs, considering IXPs as relays, using cloud auctions for transit cost pricing, and improving the performance of cloud-native applications.

The remarkable success of the use of machine learning-based solutions for network security problems has been impeded by the developed ML models' inability to maintain efficacy when used in different network environments exhibiting different network behaviors. This issue is commonly referred to as the generalizability problem of ML models. The community has recognized the critical role that training datasets play in this context and has developed various techniques to improve dataset curation to overcome this problem. Unfortunately, these methods are generally ill-suited or even counterproductive in the network security domain, where they often result in unrealistic or poor-quality datasets.

Several recent research efforts have proposed Machine Learning (ML)-based solutions that can detect complex patterns in network traffic for a wide range of network security problems. However, without understanding how these black-box models are making their decisions, network operators are reluctant to trust and deploy them in their production settings. One key reason for this reluctance is that these models are prone to the problem of underspecification, defined here as the failure to specify a model in adequate detail. Not unique to the network security domain, this problem manifests itself in ML models that exhibit unexpectedly poor behavior when deployed in real-world settings and has prompted growing interest in developing interpretable ML solutions (e.g., decision trees) for "explaining'' to humans how a given black-box model makes its decisions. However, synthesizing such explainable models that capture a given black-box model's decisions with high fidelity while also being practical (i.e., small enough in size for humans to comprehend) is challenging.

This paper presents a P4 implementation of the (1-D) Discrete Wavelet Transform (DWT) method. As a mathe-matical tool for analyzing signals such as packet-level traces, the DWT divides a given signal into different frequency components and analyzes each component with a resolution matched to its scale. We develop an efficient online algorithm that circumvents various limitations of existing P4-programmable data plane devices and performs the DWT decomposition entirely in the data plane. Our evaluation of a hardware implementation (i.e., Netronome NFP-4000 SmartNIC) of the algorithm shows that it results in only minimal throughput overhead (less than 1% for average-sized packets) and operates within constraints imposed by the limited available data plane resources. As an application, we use our lightweight P4 implementation of the DWT and describe a novel threshold-based approach for detecting periodic behavior in a signal in real-time, at line rate in the data plane (40 Gbps). We illustrate our approach with different examples of synthetic and real-world packet-level traffic traces that exhibit periodic patterns of either benign or malicious origins.

The application of machine learning (ML) to mitigate network-related problems poses significant challenges for researchers and operators alike. For one, there is a general lack of labeled training data in networking, and labeling techniques popular in other domains are ill-suited due to the scarcity of operators’ domain expertise. Second, network problems are typically multi-tasked in nature, requiring multiple ML models (one per task) and resulting in multiplicative increases in training times as the number of tasks increases. Third, the adoption of ML by network operators hinges on the models’ ability to provide basic reasoning about their decision-making procedures. To address these challenges, we propose ARISE, a multi-task weak supervision framework for network measurements. ARISE uses weak supervision-based data programming to label network data at scale and applies learning paradigms such as multi-task learning (MTL) and meta-learning to facilitate information sharing between tasks as well as reduce overall training time. Using community datasets, we show that ARISE can generate MTL models with improved classification accuracy compared to multiple single-task learning (STL) models. We also report findings that show the promise of MTL models for providing a means for reasoning about their decision-making process, at least at the level of individual tasks.

A growing concern within today's networking community is that with the proliferation of Artificial Intelligence/Machine Learning (AI/ML) techniques, a lack of access to real-world production networks is putting academic researchers at a significant disadvantage. Indeed, compared to a select few research groups in industry that can leverage access to their global-scale production networks in their data-driven efforts to develop and evaluate learning models, academic researchers not only struggle to get their hands on real-world data sets but find it almost impossible to adequately train and assess their learning models under realistic conditions.

The growing demand for an ever-increasing number of cloud services is profoundly transforming the Internet's interconnection or peering ecosystem, and one example is the emergence of "virtual private interconnections (VPIs)". However, due to the underlying technologies, these VPIs are not publicly visible and traffic traversing them remains largely hidden as it bypasses the public Internet. In particular, existing techniques for inferring Internet interconnections are unable to detect these VPIs and are also incapable of mapping them to the physical facility or geographic region where they are established.

Internet interconnections are the means by which networks exchange traffic between one another. These interconnections are typically established in facilities that have known geographic locations, and are owned and operated by so-called colocation and interconnection services providers (e.g., Equinix, CoreSite, and EdgeConneX). These previously under-studied colocation facilities and the critical role they play in solving the notoriously difficult problem of obtaining a comprehensive view of the structure and evolution of the interconnections in today's Internet are the focus of this paper. We present mi2, a new approach for mapping Internet interconnections inside a given colocation facility.1We infer the existence of interconnections from localized traceroutes and use the Belief Propagation algorithm on a specially defined Markov Random Field graphical model to geolocate them to a target colocation facility. We evaluate mi2by applying it initially to a small set of US-based colocation facilities. In the process, we compare our results against those obtained by two recently developed related techniques and discuss observed discrepancies that derive from how the different techniques determine the ownership of border routers. As part of our validation approach, we also identify drastic changes in today's Internet interconnection ecosystem (e.g., new infrastructures in the form of “cloud exchanges” that offer new types of interconnections called “virtual private interconnections”), and discuss their wide-ranging implications for obtaining an accurate and comprehensive map of the Internet's interconnection fabric.

The most-followed Twitter users and their pairwise relationships form a sub-graph of all Twitter users that we call the Twitter elite network. The connectivity patterns and influence (in terms of reply and retweet activity) among these elite users illustrate how the “important” users connect and interact with one another on Twitter. Such an elite-focused view also provides valuable information about the structure of the Twitter network as a whole. This paper presents the first detailed characterization of the top-10K Twitter elite network. We describe a new technique to efficiently and accurately capture the Twitter elite network along with social attributes of individual elite accounts. We show that a sufficiently large elite network is typically composed of 15-20 resilient and socially cohesive communities representing “socially meaningful” components of the elite network. We then characterize the community-level structure of the elite network in terms of bias in directed pairwise connectivity and relative reachability. We demonstrate that both the retweet and reply activity between elite users are effectively contained within individual elite communities. Finally, we illustrate that a majority of the elite friends of regular Twitter users tend to belong to a single elite community. This finding offers a promising criterion to group regular users into “shadow partitions” based on their association with elite communities. We show that the level of overall inter-connectivity between shadow partitions mirrors the inter-connectivity of the elite communities. This suggests that these shadow partitions can be viewed as extensions of their corresponding elite communities.

Managing and securing networks requires collecting and analyzing network traffic data in real time. Existing telemetry systems do not allow operators to express the range of queries needed to perform management or scale to large traffic volumes and rates. We present Sonata, an expressive and scalable telemetry system that coordinates joint collection and analysis of network traffic. Sonata provides a declarative interface to express queries for a wide range of common telemetry tasks; to enable real-time execution, Sonata partitions each query across the stream processor and the data plane, running as much of the query as it can on the network switch, at line rate. To optimize the use of limited switch memory, Sonata dynamically refines each query to ensure that available resources focus only on traffic that satisfies the query. Our evaluation shows that Sonata can support a wide range of telemetry tasks while reducing the workload for the stream processor by as much as seven orders of magnitude compared to existing telemetry systems.

Today's large content providers (CP) are busy building out their service infrastructures or "peering edges" to satisfy the insatiable demand for content created by an ever-expanding Internet edge. One component of these serving infrastructures that features prominently in this build-out is their connectivity fabric; i.e., the set of all Internet interconnections that content has to traverse en route from the CP's various "deployments" or "serving sites" to end users. However, these connectivity fabrics have received little attention in the past and remain largely ill-understood.

Cellular network providers collect and use a wide variety of data for assessing the service quality experienced by their smartphone users. The data is essential for tasks ranging from event detection, problem diagnosis, impact analysis, coverage and capacity planning, load balancing, and performance optimization. For example, service quality measurements and data from drive-by tests provide useful and detailed information about different aspects of quality of service such as dropped calls due to handovers or radio interference. However, a major challenge for effective service quality management in operational setup is the presence of missing or unavailable data. Furthermore, the cellular data is inherently multidimensional, i.e. is a function of several variables such as location, device type, and time. Motivated by recent advances in handling multidimensional data, we propose to use tensor algebraic models and methods for cellular data prediction. The main idea is to model the data as a low rank tensor and use a rank constrained interpolation for data prediction. We focus on two recently proposed algebraic models employing two different notions of tensor rank. We test and compare the performance of the two approaches on real-world data sets collected from an operational cellular network and indicate the regimes in which one method is superior to the other. Based on these observations the proposed algorithm chooses the best of the two approaches using cross-validation.

Programmable switches potentially make it easier to perform flexible network monitoring queries at line rate, and scalable stream processors make it possible to fuse data streams to answer more sophisticated queries about the network in real-time. However, processing such network monitoring queries at high traffic rates requires both the switches and the stream processors to filter the traffic iteratively and adaptively so as to extract only that traffic that is of interest to the query at hand. While the realization that network monitoring is a streaming analytics problem has been made earlier, our main contribution in this paper is the design and implementation of Sonata, a closed-loop system that enables network operators to perform streaming analytics for network monitoring applications at scale. To achieve this objective, Sonata allows operators to express a network monitoring query by considering each packet as a tuple. More importantly, Sonata allows them to partition the query across both the switches and the stream processor, and through iterative refinement, Sonata's runtime attempts to extract only the traffic that pertains to the query, thus ensuring that the stream processor can scale to satisfy a large number of queries for traffic at very high rates. We show with a simple example query involving DNS reflection attacks and traffic traces from one of the world's largest IXPs that Sonata can capture 95% of all traffic pertaining to the query, while reducing the overall data rate by a factor of about 400 and the number of required counters by four orders of magnitude.

The complexity and enormous costs of installing new long-haul fiber-optic infrastructure has led to a significant amount of infrastructure sharing in previously installed conduits. In this paper, we study the characteristics and implications of infrastructure sharing by analyzing the long-haul fiber-optic network in the US. We start by using fiber maps provided by tier-1 ISPs and major cable providers to construct a map of the long-haul US fiber-optic infrastructure. We also rely on previously under-utilized data sources in the form of public records from federal, state, and municipal agencies to improve the fidelity of our map. We quantify the resulting map's connectivity characteristics and confirm a clear correspondence between long-haul fiber-optic, roadway, and railway infrastructures. Next, we examine the prevalence of high-risk links by mapping end-to-end paths resulting from large-scale traceroute campaigns onto our fiber-optic infrastructure map. We show how both risk and latency (i.e., propagation delay) can be reduced by deploying new links along previously unused transportation corridors and rights-of-way. In particular, focusing on a subset of high-risk links is sufficient to improve the overall robustness of the network to failures. Finally, we discuss the implications of our findings on issues related to performance, net neutrality, and policy decision-making.

Poor visibility into the network hampers progress in a number of important research areas, from network troubleshooting to Internet topology and performance mapping. This persistent, well-known problem has served as motivation for numerous proposals to build or extend existing Internet measurement platforms by recruiting larger, more diverse vantage points. Capturing the edge of the network, however, remains an elusive goal. We argue that at its root the problem is one of incentives. Today's measurement platforms build on the assumption that the goals of experimenters and those hosting the platform are the same. As much of the Internet growth occurs in residential broadband networks, this assumption no longer holds. We present a measurement experimentation platform that reaches the network edge by explicitly aligning the objectives of the experimenters with those of the users hosting the platform. Dasu-our current prototype-is designed to support both network measurement experimentation and broadband characterization. Dasu has been publicly available since July 2010 and has been installed by over 100 000 users with a heterogeneous set of connections spreading across 2431 autonomous systems (ASs) and 166 countries. We discuss some of the challenges we faced building and using a platform for the Internet's edge, describe its design and implementation, and illustrate the unique perspective its current deployment brings to Internet measurement.

During the last few years, more and more of the medium-to-large Internet eXchange Points (IXP) around the world have started to operate a route server and offer its use as a free value-added service to their members. This service has greatly simplified inter-domain routing for those members and has made it easy for them to peer with possibly hundreds of networks at those IXPs from the get-go.

Characterizing the flow of Internet traffic is important in a wide range of contexts, from network engineering and application design to understanding the network impact of consumer demand and business relationships. Despite the growing interest, the nearly impossible task of collecting large-scale, Internet-wide traffic data has severely constrained the focus of traffic-related studies.

Recent Internet studies have reported on continued traffic growth, changes in applications usage, and a proliferation in the adoption of high-speed access links. Any adverse impact that these observed trends may have on Internet traffic flows can result in sub par performance, which in turn results in unsatisfactory user experience. To study such adverse impacts, we examine in this paper the flow-level performance of popular applications across a range of size-based flow-classes and applications. We use out-of-sequence packets, retransmissions, throughput, and RTTs as key flow performance metrics. Leveraging data sets collected from two complementary network environments, we compare these metrics for popular applications and for the up/downstream directions. We show that irrespective of the direction, flows are severely impacted by the specifics of the network, e.g., DSL or CDN and application behavior. We also find that, in general, this impact differs markedly across the different flow-classes. In particular, contrary to popular belief, the small flows from all applications, which make up the majority of flows, experience significant retransmissions, while the very large flows, although small in number, experience very limited retransmissions. In terms of application-related performance, we observe that especially when compared to HTTP, apart from large flows, P2P flows suffer from continuously high retransmissions and low throughput. As for the root cause of these retransmissions, we identify the access part of the network as the main culprit and not the network core.

Models of human mobility have broad applicability in fields such as mobile computing, urban planning, and ecology. This paper proposes and evaluates WHERE, a novel approach to modeling how large populations move within different metropolitan areas. WHERE takes as input spatial and temporal probability distributions drawn from empirical data, such as Call Detail Records (CDRs) from a cellular telephone network, and produces synthetic CDRs for a synthetic population. We have validated WHERE against billions of anonymous location samples for hundreds of thousands of phones in the New York and Los Angeles metropolitan areas. We found that WHERE offers significantly higher fidelity than other modeling approaches. For example, daily range of travel statistics fall within one mile of their true values, an improvement of more than 14 times over a Weighted Random Waypoint model. Our modeling techniques and synthetic CDRs can be applied to a wide range of problems while avoiding many of the privacy concerns surrounding real CDRs.

The largest IXPs carry on a daily basis traffic volumes in the petabyte range, similar to what some of the largest global ISPs reportedly handle. This little-known fact is due to a few hundreds of member ASes exchanging traffic with one another over the IXP's infrastructure. This paper reports on a first-of-its-kind and in-depth analysis of one of the largest IXPs worldwide based on nine months' worth of sFlow records collected at that IXP in 2011.

Despite advances in measurement technology, it is still challenging to reliably compile large-scale network datasets. For example, because of flaws in the measurement systems or difficulties posed by the measurement problem itself, missing, ambiguous, or indirect data are common. In the case where such data have spatio-temporal structure, it is natural to try to leverage this structure to deal with the challenges posed by the problematic nature of the data. Our work involving network datasets draws on ideas from the area of compressive sensing and matrix completion, where sparsity is exploited in estimating quantities of interest. However, the standard results on compressive sensing are: 1) reliant on conditions that generally do not hold for network datasets; and 2) do not allow us to exploit all we know about their spatio-temporal structure. In this paper, we overcome these limitations with an algorithm that has at its heart the same ideas espoused in compressive sensing, but adapted to the problem of network datasets. We show how this algorithm can be used in a variety of ways, in particular on traffic data, to solve problems such as simple interpolation of missing values, traffic matrix inference from link data, prediction, and anomaly detection. The elegance of the approach lies in the fact that it unifies all of these tasks and allows them to be performed even when as much as 98% of the data is missing.

Formally, the Internet inter-domain routing system is a collection of networks, their policies, peering relationships and organizational affiliations, and the addresses they advertize. It also includes components like Internet exchange points. By its very definition, each and every aspect of this system is impacted by BGP, the de-facto standard inter-domain routing protocol. The element of this inter-domain routing system that has attracted the single-most attention within the research community has been the "inter-domain topology". Unfortunately, almost from the get go, the vast majority of studies of this topology, from definition, to measurement, to modeling and analysis, have ignored the central role of BGP in this problem. The legacy is a set of specious findings, unsubstantiated claims, and ill-conceived ideas about the Internet as a whole. By presenting a BGP-focused state-of-the-art treatment of the aspects that are critical for a rigorous study of this inter-domain topology, we demystify in this paper many "controversial" observations reported in the existing literature. At the same time, we illustrate the benefits and richness of new scientific approaches to measuring, modeling, and analyzing the inter-domain topology that are faithful to the BGP-specific nature of this problem domain.

An understanding of Internet topology is central to answer various questions ranging from network resilience to peer selection or data center location. While much of prior work has examined AS-level connectivity, meaningful and relevant results from such an abstract view of Internet topology have been limited. For one, semantically, AS relationships capture business relationships and not physical connectivity. Additionally, many organizations often use multiple ASes, either to implement different routing policies, or as legacies from mergers and acquisitions. In this paper, we move beyond the traditional AS graph view of the Internet to define the problem of AS-to-organization mapping. We describe our initial steps at automating the capture of the rich semantics inherent in the AS-level ecosystem where routing and connectivity intersect with organizations. We discuss preliminary methods that identify multi-AS organizations from WHOIS data and illustrate the challenges posed by the quality of the available data and the complexity of real-world organizational relationships.

This paper presents a new approach to determine the geographical footprint of individual Autonomous Systems that directly provide service to end-users, i.e., eyeball ASes. The key idea is to leverage the geo-location of end-users associated with an eyeball AS to identify its geographical footprint. We leverage the kernel density estimation method to estimate the density of users across individual eyeball ASes. This method enables us to cope with the potential error associated with the location of individual end-users while controlling the level of aggregation among data points to capture a geo-footprint at the desired resolution. We use the resulting geo-footprint of individual eyeball ASes to identify their likely Point-of-Presence (PoP) locations. To demonstrate our proposed technique, we use the inferred geo-locations of 48 million users from three popular P2P applications and assess the geo- and PoP-level footprints of 1233 eyeball ASes. The validation of the identified PoP locations by our technique against online information and prior results by a commonly-used technique based on traceroute shows a very high accuracy. Leveraging the acquired PoP locations, we examine the implications of geo-footprint of eyeball ASes on their connectivity to the rest of the Internet. In particular, we present a case study that reveals a much more complex picture of AS-level connectivity as compared to what the more traditional but geography-agnostic BGP- or traceroute-based approaches depict.

Internet exchange points (IXPs) are an important ingredient of the Internet AS-level ecosystem - a logical fabric of the Internet made up of about 30,000 ASes and their mutual business relationships whose primary purpose is to control and manage the flow of traffic. Despite the IXPs' critical role in this fabric, little is known about them in terms of their peering matrices (i.e., who peers with whom at which IXP) and corresponding traffic matrices (i.e., how much traffic do the different ASes that peer at an IXP exchange with one another). In this paper, we report on an Internet-wide traceroute study that was specifically designed to shed light on the unknown IXP-specific peering matrices and involves targeted traceroutes from publicly available and geographically dispersed vantage points. Based on our method, we were able to discover and validate the existence of about 44K IXP-specific peering links - nearly 18K more links than were previously known. In the process, we also classified all known IXPs depending on the type of information required to detect them. Moreover, in view of the currently used inferred AS-level maps of the Internet that are known to miss a significant portion of the actual AS relationships of the peer-to-peer type, our study provides a new method for augmenting these maps with IXP-related peering links in a systematic and informed manner.

Since the last in-depth studies of measured TCP traffic some 6-8 years ago, the Internet has experienced significant changes, including the rapid deployment of backbone links with 1-2 orders of magnitude more capacity, the emergence of bandwidth-intensive streaming applications, and the massive penetration of new TCP variants. These and other changes beg the question whether the characteristics of measured TCP traffic in today's Internet reflect these changes or have largely remained the same. To answer this question, we collected and analyzed packet traces from a number of Internet backbone and access links, focused on the "heavy-hitter" flows responsible for the majority of traffic. Next we analyzed their within-flow packet dynamics, and observed the following features: (1) in one of our datasets, up to 15.8% of flows have an initial congestion window (ICW) size larger than the upper bound specified by RFC 3390. (2) Among flows that encounter retransmission rates of more than 10%, 5% of them exhibit irregular retransmission behavior where the sender does not slow down its sending rate during retransmissions. (3) TCP flow clocking (i.e., regular spacing between flights of packets) can be caused by both RTT and non-RTT factors such as application or link layer, and 60% of flows studied show no pronounced flow clocking. To arrive at these findings, we developed novel techniques for analyzing unidirectional TCP flows, including a technique for inferring ICW size, a method for detecting irregular retransmissions, and a new approach for accurately extracting flow clocks.

Online Social Networks (OSNs) have already attracted more than half a billion users. However, our understanding of which OSN features attract and keep the attention of these users is poor. Studies thus far have relied on surveys or interviews of OSN users or focused on static properties, e. g., the friendship graph, gathered via sampled crawls. In this paper, we study how users actually interact with OSNs by extracting clickstreams from passively monitored network traffic. Our characterization of user interactions within the OSN for four different OSNs (Facebook, LinkedIn, Hi5, and StudiVZ) focuses on feature popularity, session characteristics, and the dynamics within OSN sessions. We find, for example, that users commonly spend more than half an hour interacting with the OSNs while the byte contributions per OSN session are relatively small.

This paper presents Respondent-Driven Sampling (RDS) as a promising technique to derive unbiased estimates of node properties in unstructured overlay networks such as Gnutella. Using RDS and a previously proposed technique, namely Metropolized Random Walk (MRW) sampling, we examine the efficiency of estimating node properties in unstructured overlays and identify some of the key factors that determine the accuracy of sampling techniques. We evaluate the RDS and MRW techniques using simulation over a wide range of static and dynamic graphs as well as experiments over a widely deployed Gnutella network. Our study sheds light on how the connectivity structure among nodes and its dynamics affect the accuracy and efficiency of the two sampling techniques. Both techniques exhibit a rather similar performance over a wide range of scenarios. However, RDS significantly outperforms MRW when the overlay structure exhibits a combination of highly skewed node degrees and highly skewed (local) clustering coefficients.

Many basic network engineering tasks (e.g., traffic engineering, capacity planning, anomaly detection) rely heavily on the availability and accuracy of traffic matrices. However, in practice it is challenging to reliably measure traffic matrices. Missing values are common. This observation brings us into the realm of compressive sensing, a generic technique for dealing with missing values that exploits the presence of structure and redundancy in many real-world systems. Despite much recent progress made in compressive sensing, existing compressive-sensing solutions often perform poorly for traffic matrix interpolation, because real traffic matrices rarely satisfy the technical conditions required for these solutions.

Most research on traffic matrices (TM) has focused on finding models that help with inference, but not with other important tasks such as synthesis of TMs, traffic prediction, or anomaly detection. In this paper we approach the problem of a general model for traffic matrices, and argue that such a model must be sparse, i.e., have a small number of parameters in comparison to the size of the TM. A Multi-Resolution Analysis (MRA) of TMs can provide such a sparse representation. The Diffusion Wavelet (DW) transform is a good choice as a MRA tool here, because it inherently adapts to the structure of the underlying network. The paper describes our construction of the two-dimensional version of the DW transform and shows how to use it for our proposed MRA of TMs. The results obtained with operational networks confirm the sparseness of the DW-based TM analysis approach and its applicability to other TM-related tasks.

Despite significant efforts to obtain an accurate picture of the Internet's actual connectivity structure at the level of individual autonomous systems (ASes), much has remained unknown in terms of the quality of the inferred AS maps that have been widely used by the research community. In this paper we assess the quality of the inferred Internet maps through case studies of a set of ASes. These case studies allow us to establish the ground truth of AS-level Internet connectivity between the set of ASes and their directly connected neighbors. They also enable a direct comparison between the ground truth and inferred topology maps and yield new insights into questions such as which parts of the actual topology are adequately captured by the inferred maps, and which parts are missing and why. This information is critical in assessing for what kinds of real-world networking problems the use of currently inferred AS maps or proposed AS topology models are, or are not, appropriate. More importantly, our newly gained insights also point to new directions towards building realistic and economically viable Internet topology maps.

During the past few years, Peer-to-Peer (P2P) applications have become increasingly popular over the Internet. In these applications, a large number (e.g., millions) of geographically distributed end-systems (or peers) form an overlay to exchange content and share their resources. Several recent studies have observed the network traffic at one or few vantage points and shown that P2P applications significantly contribute to the overall Internet traffic(e.g., [2]). Given the distributed nature of P2P applications, the observed traffic associated with a P2P application across different regions (i.e., ASes) in the Internet depends on several factors including (i) the location of participating peers, (ii) the connectivity among the peers, and (iii) the BGP routing of traffic among ASes in the underlay. Therefore, the observed traffic for a P2P application at a single (or few) vantage point(s) clearly does not represent the extent of its impact across the network. Capturing an accurate view of the global impact of a P2P application requires access to a large number of vantage points that is prohibitively expensive. To our knowledge, none of the previous empirical studies on P2P systems have characterized the global impact of a P2P application on the AS-level underlay.

This paper addresses the difficult problem of selecting representative samples of peer properties (eg degree, link bandwidth, number of files shared) in unstructured peer-to-peer systems. Due to the large size and dynamic nature of these systems, measuring the quantities of interest on every peer is often prohibitively expensive, while sampling provides a natural means for estimating system-wide behavior efficiently. However, commonly-used sampling techniques for measuring peer-to-peer systems tend to introduce considerable bias for two reasons. First, the dynamic nature of peers can bias results towards short-lived peers, much as naively sampling flows in a router can lead to bias towards short-lived flows. Second, the heterogeneous nature of the overlay topology can lead to bias towards high-degree peers.We present a detailed examination of the ways that the behavior of peer-to-peer systems can introduce bias and suggest the Metropolized Random Walk with Backtracking (MRWB) as a viable and promising technique for collecting nearly unbiased samples. We conduct an extensive simulation study to demonstrate that the proposed technique works well for a wide variety of common peer-to-peer network conditions. Using the Gnutella network, we empirically show that our implementation of the MRWB technique yields more accurate samples than relying on commonly-used sampling techniques. Furthermore, we provide insights into the causes of the observed differences. The tool we have developed, ion-sampler, selects peer addresses uniformly at random using the MRWB technique. These addresses may then be used as input to another measurement tool to collect data on a particular property.

Abstract — Internet connectivity at the AS level, defined in terms of pairwise logical peering relationships, is constantly evolving. This evolution is largely a response to economic, political, and technological changes that impact the way ASs conduct their business. We present a new framework for modeling this evolutionary process by identifying a set of criteria that ASs consider either in establishing a new peering relationship or in reassessing an existing relationship. The proposed framework is intended to capture key elements in the decision processes underlying the formation of these relationships. We present two decision processes that are executed by an AS, depending on its role in a given peering decision, as a customer or a peer of another AS. When acting as a peer, a key feature of the AS’s corresponding decision model is its reliance on realistic inter-AS traffic demands. To reflect the enormous heterogeneity among customer or peer ASs, our decision models are flexible enough to accommodate a wide range of AS-specific objectives. We demonstrate the potential of this new framework by considering different decision models in various realistic “what if ” experiment scenarios. We implement these decision models to generate and study the evolution of the resulting AS graphs over time, and compare them against observed historical evolutionary features of the Internet at the AS level. I.

Peer-to-peer systems are becoming increasingly popular, with millions of simultaneous users and a wide range of applications. Understanding existing systems and devising new peer-to-peer techniques relies on access to representative models derived from empirical observations. Due to the large and dynamic nature of these systems, directly capturing global behavior is often impractical. Sampling is a natural approach for learning about these systems, and most previous studies rely on it to collect data. This paper addresses the common problem of selecting representative samples of peer properties such as peer degree, link bandwidth, or the number of files shared. A good sampling technique will select any of the peers present with equal probability. However, common sampling techniques introduce bias in two ways. First, the dynamic nature of peers can bias results towards short-lived peers, much as naively sampling flows in a router can lead to bias towards short-lived flows. Second, the heterogeneous overlay topology can lead to bias towards high-degree peers. We present preliminary evidence suggesting that applying a degree-correction method to random walk-based peer selection leads to unbiased sampling, at the expense of a loss of efficiency.

Examining the validity or accuracy of proposed available bandwidth estimation tools remains a challenging problem. A common approach consists of evaluating a newly developed tool using a combination of simple nstype simulations and feasible experiments in situ (i.e., using parts of the actual Internet). In this paper, we argue that this strategy tends to fall short of establishing a reliable "ground truth," and we advocate an alternative in vitro-like methodology for calibrating available bandwidth estimation tools that has not been widely used in this context. Our approach relies on performing controlled laboratory experiments and using tools to visualize and analyze the relevant tool-specific traffic dynamics. We present a case study of how two canonical available bandwidth estimation tools, SPRUCE and PATHLOAD, respond to increasingly more complex cross traffic and network path conditions. We expose measurement bias and algorithmic omissions that lead to poor tool calibration. As a result of this evaluation, we designed a calibrated available bandwidth estimation tool called YAZ that builds on the insights of PATHLOAD. We show that in head to head comparisons with SPRUCE and PATHLOAD, YAZ is significantly and consistently more accurate with respect to ground truth, and reports results more quickly with a small number of probes.

Building on a recent effort that combines a first-principles approach to modeling router-level connectivity with a more pragmatic use of statistics and graph theory, we show in this paper that for the Internet, an improved understanding of its physical infrastructure is possible by viewing the physical connectivity as an annotated graph that delivers raw connectivity and bandwidth to the upper layers in the TCP/IP protocol stack, subject to practical constraints (e.g., router technology) and economic considerations (e.g., link costs). More importantly, by relying on data from Abilene, a Tier-1 ISP, and the Rocketfuel project, we provide empirical evidence in support of the proposed approach and its consistency with networking reality. To illustrate its utility, we: 1) show that our approach provides insight into the origin of high variability in measured or inferred router-level maps; 2) demonstrate that it easily accommodates the incorporation of additional objectives of network design (e.g., robustness to router failure); and 3) discuss how it complements ongoing community efforts to reverse-engineer the Internet.

The Internet is teeming with high variability phenomena, from measured IP flow sizes to aspects of inferred router-level connectivity, but there still exists considerable debate about how best to deal with this encountered high variability and model it. While one popular approach favors modeling highly variable event sizes with conventional, finite variance distributions such as lognormal or Weibull distributions, Mandelbrot has argued for the last 40 years that there are compelling mathematical, statistical, and practical reasons for why infinite variance distributions are natural candidates for capturing the essence behind high variability phenomena. In this paper, we elaborate on Mandelbrot's arguments and present a methodology that often allows for a clear distinction between the two approaches. In particular, by requiring the resulting models to be resilient to ambiguities (i.e., robust to real-world deficiencies in the underlying network measurements) and internally self-consistent (i.e., insensitive with respect the duration, location, or time of the data collection), we provide a rigorous framework for a qualitative assessment of the observed high variability. We apply the proposed framework to assess previously reported findings about measured Internet traffic and inferred router- and AS-level connectivity. In the process, we also discuss what our approach has to say about recent discussions concerning network traffic being Poisson or self-similar and router-level or AS-level connectivity graphs of the Internet being scale-free or not.

A detailed understanding of the many facets of the Internet's topological structure is critical for evaluating the performance of networking protocols, for assessing the effectiveness of proposed techniques to protect the network from nefarious intrusions and attacks, or for developing improved designs for resource provisioning. Previous studies of topology have focused on interpreting measurements or on phenomenological descriptions and evaluation of graph-theoretic properties of topology generators. We propose a complementary approach of combining a more subtle use of statistics and graph theory with a first-principles theory of router-level topology that reflects practical constraints and tradeoffs. While there is an inevitable tradeoff between model complexity and fidelity, a challenge is to distill from the seemingly endless list of potentially relevant technological and economic issues the features that are most essential to a solid understanding of the intrinsic fundamentals of network topology. We claim that very simple models that incorporate hard technological constraints on router and link bandwidth and connectivity, together with abstract models of user demand and network performance, can successfully address this challenge and further resolve much of the confusion and controversy that has surrounded topology generation and evaluation.

C. Faloutsos et al. (see Proc. ACM SIGCOMM, 1999) found that the inter autonomous system (AS) topology exhibits a power-law vertex degree distribution. This result was quite unexpected in the networking community and stirred significant interest in exploring the possible causes of this phenomenon. The work of A.-L. Barabasi and R. Albert (see Science, p.509-512, 1999) and its application to network topology generation in the work of A. Medina et al. (see Proc. MASCOTS, 2001) have explored a promising class of models that yield strict power-law vertex degree distributions. We re-examine the BGP (border gateway protocol) measurements that form the basis for the results reported by Faloutsos et al. We find that by their very nature (i.e., being strictly BGP-based), the data provides a very incomplete picture of Internet connectivity at the AS level. The AS connectivity maps constructed from this data (original maps) typically miss 20-50% or even more of the physical links in AS maps constructed using additional sources (extended maps). Subsequently, we find that while the vertex degree distributions resulting from the extended maps are heavy-tailed, they deviate significantly from a strict power law. Finally, we show that available historical data does not support the connectivity-based dynamics assumed by Barabasi and Albert. Together, our results suggest that the Internet topology at the AS level may well have developed over time following a very different set of growth processes than those proposed by Barabasi and Albert.

Following the long-held belief that the Internet is hierarchical, the network topology generators most widely used by the Internet research community, Transit-Stub and Tiers, create networks with a deliberately hierarchical structure. However, in 1999 a seminal paper by Faloutsos et al. revealed that the Internet's degree distribution is a power-law. Because the degree distributions produced by the Transit-Stub and Tiers generators are not power-laws, the research community has largely dismissed them as inadequate and proposed new network generators that attempt to generate graphs with power-law degree distributions.Contrary to much of the current literature on network topology generators, this paper starts with the assumption that it is more important for network generators to accurately model the large-scale structure of the Internet (such as its hierarchical structure) than to faithfully imitate its local properties (such as the degree distribution). The purpose of this paper is to determine, using various topology metrics, which network generators better represent this large-scale structure. We find, much to our surprise, that network generators based on the degree distribution more accurately capture the large-scale structure of measured topologies. We then seek an explanation for this result by examining the nature of hierarchy in the Internet more closely; we find that degree-based generators produce a form of hierarchy that closely resembles the loosely hierarchical nature of the Internet.

For the past two years,there has been a significant increase in research activities related to studying and modeling the Internet's topology, especially at the level of autonomous systems (ASs). A closer look at the measurements that form the basis for all these studies reveals that the data sets used consist of the BGP routing tables collected by the Oregon route server (henceforth, the Oregon route-views) [1]. So far, there has been anecdotal evidence and an intuitive understanding among researchers in the field that BGP-derived AS connectivity is not complete. However, as far as we know, there has been no systematic study on quantifying the completeness of currently known AS-level Internet topologies. Our main objective in this paper is to quantify the completeness of Internet AS maps constructed from the Oregon route-views and to attempt to capture more representative AS-level Internet topology. One of the main contributions of this paper is in developing a methodology that enables quantitative investigations into issues related to the (in)completeness of BGP-derived AS maps.

One of the most significant findings of traffic measurement studies over the last decade has been the observed self-similarity in packet network traffic. Subsequent research has focused on the origins of this self-similarity, and the network engineering significance of this phenomenon. This paper reviews what is currently known about network traffic self-similarity and its significance. We then consider a matter of current research, namely, the manner in which network dynamics (specifically, the dynamics of transmission control protocol (TCP), the predominant transport protocol used in today's Internet) can affect the observed self-similarity. To this end, we first discuss some of the pitfalls associated with applying traditional performance evaluation techniques to highly-interacting, large-scale networks such as the Internet. We then present one promising approach based on chaotic maps to capture and model the dynamics of TCP-type feedback control in such networks. Not only can appropriately chosen chaotic map models capture a range of realistic source characteristics, but by coupling these to network state equations, one can study the effects of network dynamics on the observed scaling behavior We consider several aspects of TCP feedback, and illustrate by examples that while TCP-type feedback can modify the self-similar scaling behavior of network traffic, it neither generates it nor eliminates it.

Using the ns-2-simulator to experiment with different aspects of user- or session-behaviors and network configurations and focusing on the qualitative aspects of a wavelet-based scaling analysis, we present a systematic investigation into how and why variability and feedback-control contribute to the intriguing scaling properties observed in actual Internet traces (as our benchmark data, we use measured Internet traffic from an ISP). We illustrate how variability of both user aspects and network environments (i) causes self-similar scaling behavior over large time scales, (ii) determines a more or less pronounced change in scaling behavior around a specific time scale, and (iii) sets the stage for the emergence of surprisingly rich scaling dynamics over small time scales; i.e., multifractal scaling. Moreover, our scaling analyses indicate whether or not open-loop controls such as UDP or closed-loop controls such as TCP impact the local or small-scale behavior of the traffic and how they contribute to the observed multifractal nature of measured Internet traffic. In fact, our findings suggest an initial physical explanation for why measured Internet traffic over small time scales is highly complex and suggest novel ways for detecting and identifying, for example, performance bottlenecks.This paper focuses on the qualitative aspects of a wavelet-based scaling analysis rather than on the quantitative use for which it was originally designed. We demonstrate how the presented techniques can be used for analyzing a wide range of different kinds of network-related measurements in ways that were not previously feasible. We show that scaling analysis has the ability to extract relevant information about the time-scale dynamics of Internet traffic, thereby, we hope, making these techniques available to a larger segment of the networking research community.

Previous studies have demonstrated that measured wide-area network traffic such as Internet traffic exhibits locally complex irregularities, consistent with multifractal behavior. It has also been shown that the observed multifractal structure becomes most apparent when analyzing measured network traffic at a particular layer in the well-defined protocol hierarchy that characterizes modern data networks, namely the transport or transmission control protocol (TCP) layer. To investigate this new scaling phenomenon associated with the dynamics of measured network traffic over small time scales, we consider a class of multiplicative processes, the so-called conservative cascades, that serves as a cascade paradigm for and is motivated by the networking application. We present a wavelet-based time/scale analysis of these cascades to determine rigorously their global and local-scaling behavior. In particular, we prove that for the class of multifractals generated by these conservative cascades the multifractal formalism applies and is valid, and we illustrate some of the wavelet-based techniques for inferring multifractal scaling behavior by applying them to a set of wide-area traffic traces.

In apparent contrast to the well-documented self-similar (i.e., monofractal) scaling behavior of measured LAN traffic, recent studies have suggested that measured TCP/IP and ATM WAN traffic exhibits more complex scaling behavior, consistent with multifractals. To bring multifractals into the realm of networking, this paper provides a simple construction based on cascades (also known as multiplicative processes) that is motivated by the protocol hierarchy of IP data networks. The cascade framework allows for a plausible physical explanation of the observed multifractal scaling behavior of data traffic and suggests that the underlying multiplicative structure is a traffic invariant for WAN traffic that co-exists with self-similarity. In particular, cascades allow us to refine the previously observed self-similar nature of data traffic to account for local irregularities in WAN traffic that are typically associated with networking mechanisms operating on small time scales, such as TCP flow control.To validate our approach, we show that recent measurements of Internet WAN traffic from both an ISP and a corporate environment are consistent with the proposed cascade paradigm and hence with multifractality. We rely on wavelet-based time-scale analysis techniques to visualize and to infer the scaling behavior of the traces, both globally and locally. We also discuss and illustrate with some examples how this cascade-based approach to describing data network traffic suggests novel ways for dealing with networking problems and helps in building intuition and physical understanding about the possible implications of multifractality on issues related to network performance analysis.

A number of empirical studies of traffic measurements from a variety of working packet networks have demonstrated that actual network traffic is self-similar or long-range dependent in nature-in sharp contrast to commonly made traffic modeling assumptions. We provide a plausible physical explanation for the occurrence of self-similarity in local-area network (LAN) traffic. Our explanation is based on convergence results for processes that exhibit high variability and is supported by detailed statistical analyzes of real-time traffic measurements from Ethernet LANs at the level of individual sources. This paper is an extended version of Willinger et al. (1995). We develop here the mathematical results concerning the superposition of strictly alternating ON/OFF sources. Our key mathematical result states that the superposition of many ON/OFF sources (also known as packet-trains) with strictly alternating ON- and OFF-periods and whose ON-periods or OFF-periods exhibit the Noah effect produces aggregate network traffic that exhibits the Joseph effect. There is, moreover, a simple relation between the parameters describing the intensities of the Noah effect (high variability) and the Joseph effect (self-similarity). An extensive statistical analysis of high time-resolution Ethernet LAN traffic traces confirms that the data at the level of individual sources or source-destination pairs are consistent with the Noah effect. We also discuss implications of this simple physical explanation for the presence of self-similar traffic patterns in modern high-speed network traffic.

Traffic measurement studies from a wide range of working packet networks have convincingly established the presence of significant statistical features that are characteristic of fractal traffic processes, in the sense that these features span many time scales. Of particular interest in packet traffic modeling is a property called long-range dependence (LRD), which is marked by the presence of correlations that can extend over many time scales. We demonstrate empirically that, beyond its statistical significance in traffic measurements, long-range dependence has considerable impact on queueing performance, and is a dominant characteristic for a number of packet traffic engineering problems. In addition, we give conditions under which the use of compact and simple traffic models that incorporate long-range dependence in a parsimonious manner (e.g., fractional Brownian motion) is justified and can lead to new insights into the traffic management of high speed networks.

A number of recent empirical studies of traffic measurements from a variety of working packet networks have convincingly demonstrated that actual network traffic is self-similar or long-range dependent in nature (i.e., bursty over a wide range of time scales) - in sharp contrast to commonly made traffic modeling assumptions. In this paper, we provide a plausible physical explanation for the occurrence of self-similarity in high-speed network traffic. Our explanation is based on convergence results for processes that exhibit high variability (i.e., infinite variance) and is supported by detailed statistical analyses of real-time traffic measurements from Ethernet LAN's at the level of individual sources.Our key mathematical result states that the superposition of many ON/OFF sources (also known as packet trains) whose ON-periods and OFF-periods exhibit the Noah Effect (i.e., have high variability or infinite variance) produces aggregate network traffic that features the Joseph Effect (i.e., is self-similar or long-range dependent). There is, moreover, a simple relation between the parameters describing the intensities of the Noah Effect (high variability) and the Joseph Effect (self-similarity). An extensive statistical analysis of two sets of high time-resolution traffic measurements from two Ethernet LAN's (involving a few hundred active source-destination pairs) confirms that the data at the level of individual sources or source-destination pairs are consistent with the Noah Effect. We also discuss implications of this simple physical explanation for the presence of self-similar traffic patterns in modern high-speed network traffic for (i) parsimonious traffic modeling (ii) efficient synthetic generation of realistic traffic patterns, and (iii) relevant network performance and protocol analysis.

Recent measurement studies in Bellcore and elsewhere have convincingly established the presence of statistical self similarity in high-speed network traffic. What is less clear --- and as such the subject of intense current research --- is the impact of the self-similarity on network performance. Given that traditional queueing models of network performance do not model self-similarity, the validity of traditional models to predict network performance would be supported if it is shown that self-similarity does not have measurable impacts on performance. On the other hand, if the converse of this assertion were true, it would have significant impacts on the way networks are designed and analyzed, as well as open up new areas of research in mathematical modeling, queueing analysis, network design and control. The issues addressed in this session are therefore of fundamental importance in high-speed network research.Given that queueing behavior is dominated by traffic characteristics over the time scales of busy periods, it has been argued that phenomena that span many time scales, such as self-similarity, should not be relevant for queueing performance. However, the paper by Narayan, Erramilli and Willinger presents evidence that for data traffic, the long range dependence (which is related to the self-similarity in traffic) can dominate queueing behavior under a variety of conditions. Specifically, it is shown based on a series of carefully designed simulation experiments with actual traffic traces, that the queueing behavior with actual traces is considerably heavier than that predicted by traditional theory, and that these differences are attributable to long range dependence. The paper by Heyman and Lakshman investigates modeling of video traffic to predict cell loss performance with finite buffer systems, and they conclude that long-range dependence is not a crucial property in determining the finite buffer behavior of video conferences. In particular, a Markov chain model that does not model long-range dependence is nevertheless able to reproduce various operating characteristics over a wide range of loadings obtained with the actual video trace. Mukherjee, Adas, Klivansky and Song investigate the performance impacts of short-range and long-range correlation components using simulations with a fractional ARIMA model. They also discuss a strategy to provide quality of service guarantees with long range dependent traffic, as well as recent results on NSFNET traffic. Finally, the paper by Li describes a frequency-domain based analytical tool that matches a special class of Markov chains with traces exhibiting a variety of characteristics, including long-range dependence. Good agreement is reported between analytical queueing solutions of the matched Markov chains, and simulation results obtained video and data traffic traces.This session therefore brings together a wide range of viewpoints on this issue. Resolution of such seemingly conflicting conclusions lies in the fact that in performance analysis, answers sensitively depend on the specific details of a problem. Thus the proper question to ask is not whether or not self-similarity matters in queueing; but under what conditions it matters. Likewise, the question to ask is not whether a class of models is invalid; but to identify the conditions under which traditional Markov or self-similar traffic models are expected to be valid. Finally, given an understanding of statistical features that are relevant to a given problem, the challenge is to model these accurately and parsimoniously so that the model is useful in practical performance analysis. The work outlined in the abstracts below adds significantly to our understanding of these issues.

Network traffic measurement and workload characterization are key steps in the workload modeling process. Much has been learned through network measurement and workload modeling in the last ten years, but new challenges are now at the forefront: measuring network traffic in the Internet environment, understanding the implications of network traffic structure (e.g., self-similarity, autocorrelation, long range dependence), and accurate modeling of network traffic workloads for high speed network environments.This "hot topic" session brings together three prominent speakers to address each of these topics, in turn.

We analyze 20 large sets of actual variable-bit-rate (VBR) video data, generated by a variety of different codecs and representing a wide range of different scenes. Performing extensive statistical and graphical tests, our main conclusion is that long-range dependence is an inherent feature of VBR video traffic, i.e., a feature that is independent of scene (e.g., video phone, video conference, motion picture video) and codec. In particular, we show that the long-range dependence property allows us to clearly distinguish between our measured data and traffic generated by VBR source models currently used in the literature. These findings give rise to novel and challenging problems in traffic engineering for high-speed networks and open up new areas of research in queueing and performance analysis involving long-range dependent traffic models. A small number of analytic queueing results already exist, and we discuss their implications for network design and network control strategies in the presence of long-range dependent traffic.>

We present a detailed statistical analysis of a 2-hour long empirical sample of VBR video. The sample was obtained by applying a simple intraframe video compression code to an action movie. The main findings of our analysis are (1) the tail behavior of the marginal bandwidth distribution can be accurately described using “heavy-tailed” distributions (e.g., Pareto); (2) the autocorrelation of the VBR video sequence decays hyperbolically (equivalent to long-range dependence) and can be modeled using self-similar processes. We combine our findings in a new (non-Markovian) source model for VBR video and present an algorithm for generating synthetic traffic. Trace-driven simulations show that statistical multiplexing results in significant bandwidth efficiency even when long-range dependence is present. Simulations of our source model show long-range dependence and heavy-tailed marginals to be important components which are not accounted for in currently used VBR video traffic models.

Reports on an ongoing statistical analysis of actual CCSN traffic data. The data consist of approximately 170 million signaling messages collected from a variety of different working CCS subnetworks. The key findings from the analysis concern: 1) the characteristics of both the telephone call arrival process and the signaling message arrival process; 2) the tail behavior of the call holding time distribution; and 3) the observed performance of the CCSN with respect to a variety of performance and reliability measurements.>

Demonstrates that Ethernet LAN traffic is statistically self-similar, that none of the commonly used traffic models is able to capture this fractal-like behavior, that such behavior has serious implications for the design, control, and analysis of high-speed, cell-based networks, and that aggregating streams of such traffic typically intensifies the self-similarity ("burstiness") instead of smoothing it. These conclusions are supported by a rigorous statistical analysis of hundreds of millions of high quality Ethernet traffic measurements collected between 1989 and 1992, coupled with a discussion of the underlying mathematical and statistical properties of self-similarity and their relationship with actual network behavior. The authors also present traffic models based on self-similar stochastic processes that provide simple, accurate, and realistic descriptions of traffic scenarios expected during B-ISDN deployment.>

We demonstrate that Ethernet local area network (LAN) traffic is statistically self-similar, that none of the commonly used traffic models is able to capture this fractal behavior, and that such behavior has serious implications for the design, control, and analysis of high-speed, cell-based networks. Intuitively, the critical characteristic of this self-similar traffic is that there is no natural length of a "burst": at every time scale ranging from a few milliseconds to minutes and hours, similar-looking traffic bursts are evident; we find that aggregating streams of such traffic typically intensifies the self-similarity ("burstiness") instead of smoothing it.Our conclusions are supported by a rigorous statistical analysis of hundreds of millions of high quality Ethernet traffic measurements collected between 1989 and 1992, coupled with a discussion of the underlying mathematical and statistical properties of self-similarity and their relationship with actual network behavior. We also consider some implications for congestion control in high-bandwidth networks and present traffic models based on self-similar stochastic processes that are simple, accurate, and realistic for aggregate traffic.

A parametric model is proposed for the cell arrival traffic on the input lines of a switch. The cell stream alternates between active and silent periods, and general distributions are allowed for the lengths of these periods. The traffic is represented by a discrete Markov chain model obtained through a simple moment matching procedure. The cell arrivals at in input port of the switch are typically non-Poisson and exhibit periodicities. The simulation experiments illustrate that each parameter included in the model has a significant impact on the performance of the switch (as measured by cell-loss probabilities, average cell delay, and steady-state queue length distribution).>