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.

Achieving consensus behavior robust to time delay in multiagent systems has attracted much attention. This work is concerned with optimizing the convergence rate of the consensus algorithm in such systems with time delays. Previous approaches optimize either the robustness to time delay or the convergence rate separately, while imposing a limit on the other. Eigenratio optimization is another method, which does not necessarily result in a unique set of weights. Here, the problem is treated in its general form as a multiobjective optimization problem. It is shown that the corresponding Pareto frontier depends solely on the optimal condition number of the Laplacian, and it includes the optimal answer of previously adopted approaches as special cases. A notion of optimal consensusability is then defined, which allows a particular point on the Pareto Frontier with special properties to be identified. The resulting optimization problem is shown to be convex, as is solved by reformulating it as a standard semidefinite programming problem. The optimal weights for individual topologies, clique lifted graphs, and different types of subgraphs are provided, where for the latter, the optimal weights have shown to be independent of the rest of topology. Through numerical simulations, the tradeoff between robustness and convergence rate is demonstrated.

High accuracy, synchronized clocks are essential to a growing number of Internet applications. Standard protocols and their associated server infrastructure typically enable client clocks to synchronize to the order of tens of milliseconds. We address one of the key challenges to high precision Internet timekeeping – the intrinsic contribution to clock error of underlying path asymmetry between client and time server, a fundamental barrier to microsecond level accuracy. We first exploit results of a unique measurement study to reliably quantify asymmetry by taking routing changes into account for the first time, and then to infer the impacts on timing. We then describe three approaches to addressing the path asymmetry problem: LBBE, SBBE and K-SBBE, each based on timestamp exchange with multiple servers, with the goal of tightening bounds on asymmetry for each client. We explore their capabilities and limitations through simulation and model-based argument. We show that substantial improvements are possible, and discuss whether, and how, the goal of microsecond accuracy might be attained.

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.

Conventional networks are based on layered protocols with intensive cross-layer interactions and complex signal processing at every node, making it difficult to meet the ultra-low latency requirement of mission critical applications in future communication systems. In this paper, we address this issue by proposing the concept of network template, which allows data to flow through it at the transmission symbol level, with minimal node processing. This is achieved by carefully calibrating the inter-connecting links among the nodes and pre-calculating the routing/network coding actions for each node, according to a set of preconfigured flows. In this paper, we focus on the minimum cost network template design to minimize the connections within the template, while ensuring that all the pre-defined configurations are feasible with the guaranteed throughput, latency and reliability. We show that the minimum cost network template design problem is difficult to solve optimally in general. We thus propose an efficient greedy algorithm to find a close-to-optimal solution. Simulation results show that the construction cost of the templates obtained by the proposed algorithm is very close to a lower bound. Furthermore, the construction cost increases only slightly with the number of pre-defined configurations, which confirms the flexibility of the network template design.

The core of the Internet's timekeeping system are the Stratum-1 timeservers, those connected to reference hardware, that anchor the server hierarchy. It is essential that these root servers are accurate and reliable, and this it is typically taken as a given. We examine this premise through an examination of 102 prominent Stratum-1 servers, using 3 datasets spanning 6 years, collected in reference testbeds with authoritative timestamping. We describe a methodology capable of rigorously removing congestion related variability, allowing server errors to be unambiguously revealed. We use the data and methodology to assess the health of public network timing, and how it varies over time, by reporting on the type, severity, duration, and prevalence of server errors, and how they relate to protocol level information. We present conclusive evidence that the system has problems. We find that errors are widespread, significant, often endemic, consistent over time, and typically come with no warning at the protocol level. Our results highlight the lack of oversight in the current system, and provides the foundation of a server health monitoring capability, necessary to restore and maintain trust in network timing. We describe three specific applications where our results can have an impact. Our data, detailed results and software are publically available.

We collect high resolution timing packet data from 459 public Stratum-1 NTP servers during the leap second event of Dec. 2016, including all those participating in the NTP Pool Project, using a testbed with GPS and atomic clock synchronized DAG cards. We report in detail on a wide variety of anomalous behaviors found both at the NTP protocol level, and in the detailed timestamp performance of the server clocks themselves, which can last days or even weeks after the event. Overall, only 37.3% of servers had Adequate performance overall.

Network tomographic techniques have almost exclusively been built on a strong assumption of mutual independence of link processes. We introduce model classes for link loss processes with non-trivial spatial dependencies, for which the tree topology is nonetheless identifiable from leaf measurements using multicast probing. We show that these classes are large in a well-defined sense, and we provide an algorithm, SLTD, capable of returning the correct topology with certainty in the limit of infinite data.

In the mid 1990s, it was shown that the statistics of aggregated time series from Internet traffic departed from those of traditional short range-dependent models, and were instead characterized by asymptotic self-similarity. Following this seminal contribution, over the years, many studies have investigated the existence and form of scaling in Internet traffic. This contribution first aims at presenting a methodology, combining multiscale analysis (wavelet and wavelet leaders) and random projections (or sketches), permitting a precise, efficient and robust characterization of scaling, which is capable of seeing through non-stationary anomalies. Second, we apply the methodology to a data set spanning an unusually long period: 14 years, from the MAWI traffic archive, thereby allowing an in-depth longitudinal analysis of the form, nature, and evolutions of scaling in Internet traffic, as well as network mechanisms producing them. We also study a separate three-day long trace to obtain complementary insight into intra-day behavior. We find that a biscaling (two ranges of independent scaling phenomena) regime is systematically observed: long-range dependence over the large scales, and multifractallike scaling over the fine scales. We quantify the actual scaling ranges precisely, verify to high accuracy the expected relationship between the long range dependent parameter and the heavy tail parameter of the flow size distribution, and relate fine scale multifractal scaling to typical IP packet inter-arrival and to round-trip time distributions.

Timekeeping is central to network measurement. In typical systems, its accuracy is ultimately dependent on the forest of timeservers accessible over the network, whose roots are the stratum-1 timeservers, which benefit from reference hardware. It is essential that these servers are accurate and reliable, and it is commonly assumed that this is the case. We put this belief to the test through an examination of around 100 publicly accessible stratum-1 servers, using datasets spanning over 3 years, collected in a testbed with reference timestamping. We develop a methodology capable of disambiguating the effects of routing changes, congestion related variability, and server anomalies on timestamps. We use it to make a first assessment of the health of (public) network timing, by reporting on the type, severity, and frequency of anomalies we encounter.

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.

The ubiquity of Internet access and the wide variety of Internet-enabled devices and applications have made the Internet a principal pillar of the Information Society. Decentralized and diverse, the Internet is resilient and universal. However, its distributed nature leads to operational brittleness and difficulty in identifying and tracking the root causes of performance and availability issues.

We present a new anomaly detector for data traffic, ‘SMS’, based on combining random projections (sketches) with multiscale analysis, which has low computational complexity. The sketches allow ‘normal’ traffic to be automatically and robustly extracted, and anomalies detected, without the need for training data. The multiscale analysis extracts statistical descriptors, using wavelet leader tools developed recently for multifractal analysis, without any need for timescales to be selected a priori. The proposed detector is illustrated using a large recent dataset of Internet backbone traffic from the MAWI archive, and compared against existing detectors.

We introduce a new method of data collection for flow size estimation, the optimized flow sampling sketch, which combines the optimal properties of flow sampling with the computational advantages of a counter array sketch. Using Fisher information as a definitive basis of comparison, we show that the statistical efficiency of the method is within a constant factor of that of flow sampling, which is known to be optimal but which cannot be implemented without a flow table, which has higher memory and computational costs. In the process, we derive new results on the Fisher information theoretic and variance properties of the counter array sketch, proving that an overloaded sketch actually destroys information. We revisit the `eviction sketch' of Ribeiro et al. using the Fisher information framework. We show that its performance is much higher than previously supposed, and we define a new method, the optimized eviction sketch, which has very high efficiency. We compare these methods against each other and a third skampling method, sketch guided sampling, theoretically, on models and on data.

We introduce a new method for flow size estimation, the Optimised Flow Sampled Sketch, which combines the optimal properties of Flow Sampling with the computational advantages of a counter array sketch. Using Fisher Information as a definitive basis of comparison, we show that it is superior to alternatives in both model and traffic based comparisons.

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.

Variable latencies due to communication delays or system noise is the central challenge faced by time-keeping algorithms when synchronizing over the network. Using extensive experiments, we explore the robustness of synchronization in the face of both normal and extreme latency variability and compare the feedback approaches of ntpd and ptpd (a software implementation of IEEE-1588) to the feed-forward approach of the RADclock and advocate for the benefits of a feed-forward approach. Noting the current lack of kernel support, we present extensions to existing mechanisms in the Linux and FreeBSD kernels giving full access to all available raw counters, and then evaluate the TSC, HPET, and ACPI counters' suitability as hardware timing sources. We demonstrate how the RADclock achieves the same microsecond accuracy with each counter.

The main approaches to high speed measurement in routers are traffic sampling, and sketching. However, it is not known which paradigm is inherently better at extracting information from traffic streams. We tackle this problem for the first time using Fisher information as a means of comparison, in the context of flow size distribution measurement. We first provide a side-by-side information theoretic comparison, and then with added resource constraints according to simple models of router implementations. Finally, we evaluate the performance of both methods on actual traffic traces.

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.

We study the role of Kullback-Leibler divergence in the framework of anomaly detection, where its abilities as a statistic underlying detection have never been investigated in depth. We give an in-principle analysis of network attack detection, showing explicitly attacks may be masked at minimal cost through 'camouflage'. We illustrate on both synthetic distributions and ones taken from real traffic.

Traditional rate adaptation algorithms (RAAs) suffer under congested scenarios as they are unable to differentiate between packet errors due to poor physical channel conditions, from those due to collisions arising from contention for the channel. This degrades the rate selection which results in a dramatic loss of throughput both for individual users and the system. This paper presents `SmartRate', a throughput and packet size aware, passive measurement based, clientside RAA. It employs 802.11 MAC fragmentation for physical PER isolation, and employs a dynamic sampling regime to collect per-rate statistics. It uses a novel RSSI based volatility adaptivity mechanism to fine tune various parameters of the algorithm under different channel conditions (stationary or mobile). We compare SmartRate against SampleRate and AMRR in our wireless testbed and show that SmartRate outperforms them in single and multi-user cases.

The flow size distribution is a useful metric for traffic modeling and management. Its estimation based on sampled data, however, is problematic. Previous work has shown that flow sampling (FS) offers enormous statistical benefits over packet sampling but high resource requirements precludes its use in routers. We present dual sampling (DS), a two-parameter family, which, to a large extent, provide FS-like statistical performance by approaching FS continuously, with just packet-sampling-like computational cost. Our work utilizes a Fisher information based approach recently used to evaluate a number of sampling schemes, excluding FS, for TCP flows. We revise and extend the approach to make rigorous and fair comparisons between FS, DS, and others. We show how DS significantly outperforms other packet based methods, including Sample and Hold, the closest packet sampling-based competitor to FS. We describe a packet sampling-based implementation of DS and analyze its key computational costs to show that router implementation is feasible. Our approach offers insights into numerous issues, including the notion of “flow quality” for understanding the relative performance of methods, and how and when employing sequence numbers is beneficial. Our work is theoretical with some simulation support and case studies on Internet data.

In this work we present a simple toy-model that is able to explain certain empirical observations reported in a set of previous papers by Hohn et al. about the wavelet spectrum of real traffic traces. Therein, the authors found that the wavelet spectrum is substantially invariant to flow scrambling and truncation. Such finding suggested that super-flow structures above the transport layer - i.e., sessions - can be ignored for modeling the packet arrival process. Based on the proposed toy-model, we offer an interpretation framework that goes in the opposite direction, indicating that sessions, not transport-layer flows, should be taken as the main structural entities in simplified on/off models.

Current rate control (selection) algorithms in IEEE 802.11 are not based on accurate measurements of packet errors caused at the physical layer. Instead, algorithms act on measurements which, either implicitly or explicitly, mix physical errors with those arising from contention. In this paper we first illustrate how contention can adversely affect the performance of these algorithms, and point out the potential benefits of an ability to isolate physical packet error rate. We introduce and compare two variants of a single core idea enabling the isolation and accurate measurement of physical packet error, based on exploiting existing features of the MAC standard in a novel way. One is based on the RTS/CTS mechanism, and the other on packet fragmentation. Using proof of concept experimental results from a wireless testbed, we show these mechanisms can be used to improve the performance of two existing algorithms, SampleRate and AMRR, both for individual stations and for the system as a whole, and show how incremental deployment is unproblematic. We discuss how the methodology can be integrated in a modular way into rate control algorithms with acceptable overhead.

Traceroute is widely used to report the path packets take between two Internet hosts, but the widespread deployment of load balancing routers breaks a basic assumption - that there is only a single such path. We specify an adaptive, stochastic probing algorithm, the multipath detection algorithm (MDA), to report all paths that probes can follow between a source and a destination. We establish the foundations of, and show how to calculate, rigorous statistical guarantees for the discovery of the entire multipath route. We explore algorithm cost/guarantee tradeoffs in real experiments and show the inadequacy of the classic practice of sending three probes per hop.

The flow size distribution is a useful metric for traffic modeling and management. It is well known however that its estimation based on sampled data is problematic. Previous work has shown that flow sampling (FS) offers enormous statistical benefits over packet sampling, however it suffers from high resource requirements and is not currently used in routers. In this paper we present Dual Sampling, which can to a large extent provide flow-sampling-like statistical performance for packet-sampling-like computational cost. Our work is grounded in a Fisher information based approach recently used to evaluate a number of sampling schemes, excluding however FS, for TCP flows. We show how to revise and extend the approach to include FS as well as DS and others, and how to make rigorous and fair comparisons. We show how DS significantly outperforms other packet based methods, but also prove that DS is inferior to flow sampling. However, since DS is a two-parameter family of methods which includes FS as a special case, DS can be used to approach flow sampling continuously. We then describe a packet sampling based implementation of DS and analyze its key computational costs to show that router implementation is feasible. Our approach offers insights into many issues, including how the notions of 'flow quality' and 'packet gain' can be used to understand the relative performance of methods, and how the problem of optimal sampling can be formulated. Our work is theoretical with some simulation support and a case study on Internet data.

Multicast-based network tomography enables inference of average loss rates and delay distributions of internal network links from end-to-end measurements of multicast probes. Recent work showed that this method, based on correlating observations of multicast receivers, also supports the inference of temporal loss characteristics of network links. In this paper, we show that temporal characteristics can, in fact, be estimated even for link delay processes. Knowledge of temporal delay characteristics has applications for delay sensitive services such as VoIP as well as for characterizing the queueing behavior of bottleneck links. By assuming mutually independent, but arbitrary link delay processes, we develop estimators which can infer, in addition to delay distributions, the probabilities of arbitrary patterns of delay, means and full distributions of delay-run periods at chosen delay levels, for each link in the multicast tree. By applying the recently proposed principle of subtree-partitioning, the estimator is made scalable to multicast trees of large degree. Estimation error and convergence rates are evaluated using simulations.

End to end available bandwidth is often constrained by IEEE 802.11 hops in the access network. Available bandwidth measurement is particularly challenging in the wireless environment because of adaptive data rates, a time varying channel, and CSMA/CA based contention instead of simple FIFO queueing. We present a novel estimation scheme for IEEE 802.11 networks in infrastructure mode, based on passive monitoring, without any need for access point cooperation or protocol modifications. We employ an empirical map of relationships local to the client station, and direct measurements of channel utilisation, combined with the known packet size dependent overheads. In testbed experiments we show how the method provides a reliable lower bound of the achievable IP bandwidth, which is also a good point estimate in the case where sources are not greedy. We compare against probegap, an alternative method which also measures channel utilisation, but does not take rate or PER into account.

Packet delay and loss are two fundamental measures of performance. Using active probing to measure delay and loss typically involves sending Poisson probes, on the basis of the PASTA property (Poisson Arrivals See Time Averages), which ensures that Poisson probing yields unbiased estimates. Recent work, however, has questioned the utility of PASTA for probing and shown that, for delay measurements, i) a wide variety of processes other than Poisson can be used to probe with zero bias and ii) Poisson probing does not necessarily minimize the variance of delay estimates.

Abstract — With the explosive growth of the Internet over the last 10 years, a lot of work has been dedicated to understanding the underlying mechanisms of wired IP traffic. Recently, the rapid deployment of large-scale wireless infrastructures in various environments and the interesting mixture of traffic carried coupled with the large diversity of devices accessing the medium (Cellphones, Laptops, PDAs) have triggered the attention and curiosity of the research community. This paper analyzes in depth the properties of several large traces of packet data collected between the wireless access point and the IP cloud from an operational wireless service provider. We determine unambiguously the influence of network variables such as the arrival patterns of packet and flows, flow durations and flow interactions, on the aggregate statistics of TCP traffic. In doing so, we highlight the main differences and similarities between wireless and wired IP traffic, and between the two directions (from wireless devices to IP cloud and vice-versa), and show how they can be distinguished. The resulting insights provide a foundation for models of such traffic, necessary for improved resource allocation schemes as well as for the effectiveness of future services and applications. Index Terms—wireless traffic characterization, Internet traffic, wavelets, semi-experiments I.

Numerous studies have shown that the process of packet arrivals from Web traffic exhibits strong long-range dependence, which makes it not amenable to be described using the convenient but necessarily short-range dependent framework of Poisson modeling. However, Web traffic is ultimately driven by independent human behavior, so it seems natural to search for an underlying "seed process", consistent with Poissonity, indirectly driving the packet arrivals of Web traffic. Our study examines Web traffic at different levels of packet aggregation, using powerful statistical analysis tools for identifying the finest level that can be effectively modeled using a homogeneous Poisson process. We show that the arrivals of HTTP responses, TCP connections and Web pages do not provide a satisfactory seed process. However, we find Poissonity in the arrivals of "navigation bursts". A navigation burst is a tightly-spaced sequence of Web pages downloaded by the same Web client, which can be explained by fast navigation through several pages before reaching relevant content. Our analysis suggests that the start times of such navigation bursts, which we identify by detecting user think times between 12 and 30 seconds, can be effectively modeled as a homogeneous Poisson process. We believe that our methodology can be extended to other complex modeling problems where finding Poissonity can greatly simplify parsimonious modeling.

Poisson Arrivals See Time Averages (PASTA) is a well known property applicable to many stochastic systems. In active probing, PASTA is invoked to justify the sending of probe packets (or trains) at Poisson times in a variety of contexts. However, due to the diversity of aims and analysis techniques used in active probing, the benefits of Poisson based measurement, and the utility and role of PASTA, are unclear. Using a combination of rigorous results and carefully constructed examples and counter-examples, we map out the issues involved, and argue that PASTA is of very limited use in active probing. In particular, Poisson probes are not unique in their ability to sample without bias. Furthermore, PASTA ignores the issue of estimation variance, and the central need for an inversion phase to estimate the quantity of interest ased on what is directly observable. We give concrete examples of when Poisson probes should not be used, and explain why, and offer initial guidelines on suitable alternative sending processes.

Active probing heuristics are usually based on queuing systems. However, a rigorous probabilistic treatment of probing methods has been lacking. For instance, it is not known even in principle, what can and cannot be measured in general, nor the true limitations of existing methods. We provide a probabilistic treatment for the measurement of cross traffic in the 1-hop case. We derive inversion formulae for the cross traffic process, and explain their fundamental limits, using an intuitive geometric framework.

Accurate, reliable timestamping which is also convenient and inexpensive is needed in many important areas including real-time network applications and network measurement.Recently the TSC register, which counts CPU cycles in popular PC architectures, was proposed as the basis of a new software clock which in terms of rate performance performs as well as more expensive GPS alternatives.Smooth and precise clock rate is essential to measure time differences accurately.We show how to define a TSC based clock which is also accurate with respect to absolute time.The clock is calibrated by processing, in a novel way, timestamps contained in the usual flow of Network Time Protocol (NTP) packets between a NTP server and the existing software clock, and TSC timestamps made independently on the host side.Using real measurements over 4 months, validated with a GPS synchronized hardware timing solution, the algorithm measured absolute time with a median error of only 30 microseconds when using a nearby stratum-1 NTP server.Results for two other servers are given.We also provide new algorithms for the robust determination of clock rate.We exploit the reliability of the available hardware to design synchronization algorithms which are inherently robust to many factors including packet loss, server outages, route changes, temperature environment, and network congestion.

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.

Internet packet data is analysed to determine the relationship between the arrival process of packets, and of TCP flows of packets. Viewed as point processes, second order properties of the two processes are studied using wavelets, and each is found to have long range dependence. A new result is given directly linking flow durations to the onset scale of the long range dependence in the flow process. Using this result, a mechanism is described whereby the flow level structure could, in principle, influence the packet level structure, and it is shown and explained why this is not the case currently. The circumstances under which the flow structure could impact on the packet process, and therefore become important for the modeling of the packet level dynamics, are given.

Routers have the ability to output statistics about packets and flows of packets that traverse them. Since however the generation of detailed tra#c statistics does not scale well with link speed, increasingly routers and measurement boxes implement sampling strategies at the packet level. In this paper we study both theoretically and practically what information about the original tra#c can be inferred when sampling, or `thinning', is performed at the packet level. While basic packet level characteristics such as first order statistics can be fairly directly recovered, other aspects require more attention. We focus mainly on the spectral density, a second order statistic, and the distribution of the number of packets per flow, showing how both can be exactly recovered, in theory. We then show in detail why in practice this cannot be done using the traditional packet based sampling, even for high sampling rate. We introduce an alternative flow based thinning, where practical inversion is possible even at arbitrarily low sampling rate. We also investigate the theory and practice of fitting the parameters of a Poisson cluster process, modelling the full packet tra#c, from sampled data.

In addition to the well known long-range dependence in time series of IP bytes and packets, evidence for scaling behaviour has also been found at small scales for these series, separated by a characteristic transition timescale. It is less well known that two scaling regimes are also commonly found in time series describing the arrivals of TCP flows, again with long-range dependence, and with a broadly similar scaling exponent at small scales. The transition timescale is also roughly similar to that found in the IP level case. We investigate the dependencies between the scaling behaviours of the IP and TCP arrival levels at both small and large scales. We also study the origin of scaling at small scales at the IP level. The arrival level process is important to study both for its potential impact on the IP level, and in its own right, for example for web server performance. Our findings are based on gigabytes of high precision packet level data collected at multiple locations. The analysis methodology combines models with real data in a 'semi-experimental' approach which reduces the need for modeling assumptions. Flows and packets are individually manipulated to selectively isolate the components of scaling due to packet dynamics within a TCP flow, the dependencies between flows, their durations and packet counts, and the flow arrival process. The scaling behaviour is analysed using wavelet based methods.

A significant proportion of link bandwidth measurement methods are based on IP's ability to control the number of hops a packet can traverse along a route via the time-to-live (TTL) field of the IP header. A new delay variation based path model is introduced and used to analyse the fundamental networking effects underlying these methods. Insight from the model allows new link estimation methods to be derived and analysed. A new method family based on packet quartets: a combination of two packet pairs each comprising a probe following a pacesetter packet, where the TTL of the pacesetter is limited and the end-to-end delay variation of the probes is measured, is introduced. The methods provide 'pathchar-like' rate estimates over multiple links without relying on the delivery of ICMP messages, with reduced invasiveness and other advantages. The methods are demonstrated using simulations, and measurements on two different network routes are used for illustration and comparison against available tools (pathchar and clink). A comprehensive analysis of practical issues affecting the accuracy of the methods, such as link layer headers, is provided. Particular attention is paid to the consequences of 'invisible' hops: nodes where the TTL is not decreased.

A highly accurate monitoring solution for active network measurement is provided without the need for GPS, based on an alternative software clock for PC’s runningUnix. With respect to clock rate, it’s performance exceeds common GPS and NTP synchronized software clock accuracy. It is based on the TSC register counting CPU cycles and offers a resolution of around 1ns, a rate stability of 0.1PPM equal to that of the underlying hardware, and a processing overhead well under 1µs per timestamp. It is scalable and can be run in parallel with the usual clock. It is argued that accurate rate, and not synchronised offset, is the key requirement of a clock for network measurement. The clock requires an accurate estimation of the CPU cycle period. Two calibration methods which do not require a reference clock at the calibration point are given. To the TSC clock we add timestamping optimisations to create two high accuracy monitors, one based on Linux and the other on Real-Time Linux. The TSC-RT-Linux monitor has offset fluctuations of the order of 1µs. The clock is ideally suited for high precision active measurement.

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.

The scaling properties of Internet data are analysed in detail through the unifying viewpoint of infinitely divisible cascades (IDC). From exceptionally precise TCP/IP traffic traces are extracted time series including arrival rate, durations, and interarrival times of TCP connections. We show that IDC offer a pertinent description of these series. Relations between them are investigated, yielding insights on the sources of the scaling and possible modelling approaches.

This work is a contribution to the analysis of the procedure, based on wavelet coefficient partition functions, commonly used to estimate the Legendre multifractal spectrum. The procedure is applied to two examples, a fractional Brownian motion in multifractal time and a self-similar /spl alpha/-stable process, whose sample paths exhibit irregularities that by eye appear very close. We observe that, for the second example, this analysis results in a qualitatively inaccurate estimation of its multifractal spectrum, and a related masking of the /spl alpha/-stable nature of the process. We explain the origin of this error through a detailed analysis of the partition functions of the self-similar /spl alpha/-stable process. Such a study is made possible by the specific properties of the wavelet coefficients of such processes. We indicate how the estimation procedure might be modified to avoid such errors.

Infinitely divisible cascades are a model class previously introduced in the field of turbulence to describe the statistics of velocity fields. In this paper, using a wavelet reformulation of the cascades, we investigate their ability to analyze band model scaling properties of data and compare their fundamental ingredients to those of other scaling model classes such as self-similar and multifractal processes. We also propose an estimation procedure for the propagator or kernel of the cascades. Finally the cascade model is successfully applied to describe Internet TCP network traffic data, bringing new insights into their scaling properties and revealing a pitfall in existing techniques.

An on-line version of the Abry-Veitch (see IEEE GLOBECOM'98, Sydney, Australia,p.3716-21, 1998) wavelet-based estimator of the Hurst parameter is presented. It has very low memory and computational requirements and scales naturally to arbitrarily high data rates, enabling its use in real-time applications such as admission control, and avoiding the need to store huge data sets for off-line analysis. The performance of the estimator as a function of the length of data processed is demonstrated using simulated data. An implementation for 10-Mb/s Ethernet based on standard hardware supporting sampling rates of 1 data point per millisecond is described, and results of its operation presented, as is an implementation for 155-Mb/s asynchronous transfer mode networks. Finally we illustrate the power of on-line measurements by collecting measurements over a period of five months, and using them to look for diurnal trends in scaling properties of the data.

Previous measurements of various types of network traffic have shown evidence consistent with long-range dependence and self-similarity. However, an alternative explanation for these measurements is non-stationarity. Standard estimators of LRD parameters such as the Hurst parameter H assume stationarity and are susceptible to bias when this assumption does not hold. Hence LRD may be indicated by these estimators when none is present, or alternatively LRD taken to be non-stationarity. The Abry-Veitch (see IEEE Trans. on on Info. Theory, vol.44, no.1, p.2-15, 1998) joint estimator has much better properties when a time-series is non-stationary. In particular the effect of polynomial trends in data may be intrinsically eliminated from the estimates of LRD parameters. This paper investigates the behavior of the AV estimator when there are non-stationarities in the form of a level shift in the mean and/or the variance of a process. We examine cases where the change occurs both gradually or as a single jump discontinuity, and also examine the effect of the size of the shift. In particular we show that although a jump discontinuity may cause bins in the estimates of the H, the bias is negligible except when the jump is sharp, and large compared with the standard deviation of the process. We explain these effects and suggest how any introduced errors might be minimized. We define a broad class of non-stationary LRD processes so that LRD remains well defined under time varying mean and variance. The results are tested by applying the estimator to a real data set which contains a clear non-stationary event falling within this class.

A joint estimator is presented for the two parameters that define the long-range dependence phenomenon in the simplest case. The estimator is based on the coefficients of a discrete wavelet decomposition, improving a wavelet-based estimator of the scaling parameter (Abry and Veitch 1998), as well as extending it to include the associated power parameter. An important feature is its conceptual and practical simplicity, consisting essentially in measuring the slope and the intercept of a linear fit after a discrete wavelet transform is performed, a very fast (O(n)) operation. Under well-justified technical idealizations the estimator is shown to be unbiased and of minimum or close to minimum variance for the scale parameter, and asymptotically unbiased and efficient for the second parameter. Through theoretical arguments and numerical simulations it is shown that in practice, even for small data sets, the bias is very small and the variance close to optimal for both parameters. Closed-form expressions are given for the covariance matrix of the estimator as a function of data length, and are shown by simulation to be very accurate even when the technical idealizations are not satisfied. Comparisons are made against two maximum-likelihood estimators. In terms of robustness and computational cost the wavelet estimator is found to be clearly superior and statistically its performance is comparable. We apply the tool to the analysis of Ethernet teletraffic data, completing an earlier study on the scaling parameter alone.

The interest sparked by observations of long-range dependent traffic in real networks has lead to a revival of interest in non-standard queueing systems. One such queueing system is the M/G/1 queue where the service-time distribution has infinite variance. The known results for such systems are asymptotic in nature, typically providing the asymptotic form for the tail of the workload distribution, simulation being required to learn about the rest of the distribution. Simulation however performs very poorly for such systems due to the large impact of rare events. We provide a method for numerically evaluating the entire distribution for the number of customers in the M/G/1 queue with power-law tail service-time. The method is computationally efficient and shown to be accurate through careful simulations. It can be directly extended to other queueing systems and more generally to many problems where the inversion of probability generating functions complicated by power-laws is at issue. Through the use of examples we study the limitations of simulation and show that information on the tail of the queue-length distribution is not always sufficient to answer significant performance questions. We also derive the asymptotic form of the number of customers in the system in the case of a service-time distribution with a regularly varying tail (e.g. infinite variance) and thus illustrate the techniques required to apply the method in other contexts.

A wavelet-based tool for the analysis of long-range dependence and a related semi-parametric estimator of the Hurst parameter is introduced. The estimator is shown to be unbiased under very general conditions, and efficient under Gaussian assumptions. It can be implemented very efficiently allowing the direct analysis of very large data sets, and is highly robust against the presence of deterministic trends, as well as allowing their detection and identification. Statistical, computational, and numerical comparisons are made against traditional estimators including that of Whittle. The estimator is used to perform a thorough analysis of the long-range dependence in Ethernet traffic traces. New features are found with important implications for the choice of valid models for performance evaluation. A study of mono versus multifractality is also performed, and a preliminary study of the stationarity with respect to the Hurst parameter and deterministic trends.