Through detailed analysis of scores of publicly available data sets corresponding to a wide range of large-scale networks, from communication and road networks to various forms of social networks, we explore a little-studied geometric characteristic of real-life networks, namely their hyperbolicity. We provide strong evidence that large-scale communication and social networks exhibit this fundamental property, and through extensive computations we quantify the degree of hyperbolicity of each network in comparison to its diameter. By contrast, and as evidence of the validity of the methodology, applying the same technique to graphs of road networks shows that they are not hyperbolic, which is as expected. Finally, we present practical computational means for detection of hyperbolicity and show how the test itself may be scaled to much larger graphs than those we examined via renormalization group methodology.

Good clustering can provide critical insight into potential locations where congestion in a network may occur. A natural measure of congestion for a collection of nodes in a graph is its Cheeger ratio, defined as the ratio of the size of its boundary to its volume. Spectral methods provide effective means to estimate the smallest Cheeger ratio via the spectral gap of the graph Laplacian. Here, we compute the spectral gap of the truncated graph Laplacian, with the so-called Dirichlet boundary condition, for the graphs of a dozen communication networks at the IP-layer, which are subgraphs of the much larger global IP-layer network. We show that i) the Dirichlet spectral gap of these networks is substantially larger than the standard spectral gap and is therefore a better indicator of the true expansion properties of the graph, ii) unlike the standard spectral gap, the Dirichlet spectral gaps of progressively larger subgraphs converge to that of the global network, thus allowing properties of the global network to be efficiently obtained from them, and (iii) the (first two) eigenvectors of the Dirichlet graph Laplacian can be used for spectral clustering with arguably better results than standard spectral clustering. We first demonstrate these results analytically for finite regular trees. We then perform spectral clustering on the IP-layer networks using Dirichlet eigenvectors and show that it yields cuts near the network core, thus creating genuine single-component clusters. This is much better than traditional spectral clustering where several disjoint fragments near the network periphery are liable to be misleadingly classified as a single cluster. Since congestion in communication networks is known to peak at the core due to large-scale curvature and geometry, identification of core congestion and its localization are important steps in analysis and improved engineering of networks. Thus, spectral clustering with Dirichlet boundary condition is seen to be more effective at finding bona-fide bottlenecks and congestion than standard spectral clustering.

Recent measurement and simulation studies have revealed that wide area network traffic has complex statistical, possibly multifractal, characteristics on short timescales, and is self-similar on long timescales. In this paper, using measured TCP traces and queueing simulations, we show that the fine timescale features can affect performance substantially at low and intermediate utilizations, while the coarse timescale self-similarity is important at intermediate and high utilizations. We outline an analytical method for estimating performance for traffic that is self-similar on coarse timescales and multi-fractal on fine timescales, and show that the engineering problem of setting safe operating points for planning or admission control can be significantly affected by fine timescale fluctuations in network traffic.

We present a novel formulation, called the WaMPDE, for solving systems with forced autonomous components. An important feature of the WaMPDE is its ability to capture frequency modulation (FM) in a natural and compact manner. This is made possible by a key new concept: that of warped time, related to normal time through separate time scales. Using warped time, we obtain a completely general formulation that captures complex dynamics in autonomous nonlinear systems of arbitrary size or complexity. We present computationally efficient numerical methods for solving large practical problems using the WaMPDE. Our approach explicitly calculates a time-varying local frequency that matches intuitive expectations. Applications to voltage-controlled oscillators demonstrate speedups of two orders of magnitude.

We present a novel formulation, called the WaMPDE, for solving systems with forced autonomous components.An important feature of the WaMPDE is its ability to capture frequency modulation (FM) in a natural and compact manner.This is made possible by a key new concept: that of warped time, related to normal time through separate time scales.Using warped time, we obtain a completely general formulation that captures complex dynamics in autonomous nonlinear systems of arbitrary size or complexity.We present computationally efficient numerical methods for solving large practical problems using the WaMPDE.Our approach explicitly calculates a time-varying local frequency that matches intuitive expectations.Applied to VCOs, WaMPDE-based simulation results in speedups of two orders of magnitude over transient simulation.

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.

Given n data points in d-dimensional space, nearest neighbor searching involves determining the nearest of these data points to a given query point. Most averagecase analyses of nearest neighbor searching algorithms are made under the simplifying assumption that d is fixed and that n is so large relative to d that boundary effects can be ignored. This means that for any query point the statistical distribution of the data points surrounding it is independent of the location of the query point. However, in many applications of nearest neighbor searching (such as data compression by vector quantization) this assumption is not met, since the number of data points n grows roughly as 2 d. Largely for this reason, the actual performances of many nearest neighbor algorithms tend to be much better than their theoretical analyses would suggest. We present evidence of why this is the case. We provide an accurate analysis of the number of cells visited in nearest neighbor searching by the bucketing and k-d tree algorithms. We assume m d points uniformly distributed in dimension d, where m is a fixed integer ≥ 2. Further, we assume that distances are measured in the L ∞ metric. Our analysis is tight in the limit as d approaches infinity. Empirical evidence is presented showing that the analysis applies even in low dimensions.

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.