Bounds on the capacity of wireless networks often rely on simplifying assumptions and are given in terms of coarse network parameters, such as the number of nodes. While useful due to their simplicity, such bounds can significantly overestimate the achievable capacity in real-world situations, ignoring actual network topology and traffic patterns. The results of this paper improve such analytical results on network capacity in several ways. At the heart of our methodology lies the concept of transmission arenas, which indicates the presence of active transmissions near any given location in the network. This novel space-based approach is well-suited to untangle the interactions of simultaneous transmissions. Avoiding a graph-based model of the network, it opens new avenues of studying capacities. For homogeneous networks, we recover classical bounds. However, our methodology applies to arbitrary networks and can, thus, inform placing and activating of nodes also in the presence of clustering. Our method works with all classical channel models and dimensions. It provides bounds on the transport capacity which involve only high-level knowledge of node locations, such as the length of Euclidean minimum spanning tree. As an additional novelty, we establish bounds on wireless unicast and multicast capacities.

In this paper, we explore fundamental limitations of the benefit of network coding in multihop wireless networks. We study two well-accepted scenarios in the field: single multicast session and multiple unicast sessions. We assume arbitrary but fixed topology and traffic patterns for the wireless network. We prove that the gain of network coding in terms of throughput and energy saving of a single multicast session is at most a constant factor. Also, we present a lower bound on the average number of transmissions of multiple unicast sessions under any arbitrary network coding. We identify scenarios under which network coding provides no gain at all, in the sense that there exists a simple flow scheme that achieves the same performance. Moreover, we prove that the gain of network coding in terms of the maximum transport capacity is bounded by a constant factor of at most $(\pi)$ in any arbitrary wireless network under all traditional Gaussian channel models. As a corollary, we find that the gain of network coding on the throughput of large homogeneous wireless networks is asymptotically bounded by a constant. Furthermore, we establish theorems which relate a network coding scheme to a simple routing scheme for multiple unicast sessions. The theorems can be used as criteria for evaluating the potential gain of network coding in a given wired or wireless network. Based on these criteria, we find more scenarios where network coding has no gain on throughput or energy saving.

Many algorithms can take a variable amount of time to complete depending on the data being processed. These timing differences can sometimes disclose confidential information. Indeed, researchers have been able to reconstruct an RSA private key purely by querying an SSL Web server and timing the results. Our work analyzes the limits of attacks based on accurately measuring network response times and jitter over a local network and across the Internet. We present the design of filters to significantly reduce the effects of jitter, allowing an attacker to measure events with 15-100 μ s accuracy across the Internet, and as good as 100ns over a local network. Notably, security-related algorithms on Web servers and other network servers need to be carefully engineered to avoid timing channel leaks at the accuracy demonstrated in this article.

We present PedSims, a suite of mobility models spanning the entire range from the classic random waypoint (RWP), to correlated movement, to trace-level-quality social-activity-based mobility. Instrumenting PedSims at various levels of structural complexity we assess and quantify the impact of real world mobility patterns, such as common interests or synchronous behavior, on ad hoc network performance. Thus, PedSims provides not only a flexible platform for mobility simulation but also a means to strike a trade-off between a tolerable error and computational complexity. Notably, as our study of DSR, AODV and SAFARI finds, neglecting to capture mobility patterns may result in inversion of the ranking of routing protocols as well as in over- and under-estimation of network performance. Further contributions include a bias correction for the sampling of node-node connection time.

In this paper we establish fundamental limitations to the benefit of network coding in terms of energy and throughput in multihop wireless networks. Thereby we adopt two well accepted scenarios in the field: single multicast session and multiple unicast sessions. Most of our results apply to arbitrary wireless network and are, in particular, not asymptotic in kind. In terms of throughput and energy saving we prove that the gain of network coding of a single multicast session is at most a constant factor. Also, we present a lower bound on the expected number of transmissions of multiple unicast sessions under an arbitrary network coding. We identify scenarios for which the network coding gain for energy saving becomes surprisingly close to 1, in some cases even exactly 1, corresponding to no benefit at all. Interestingly, we prove that the gain of network coding in terms of transport capacity is bounded by a constant factor pi in any arbitrary wireless network and for all traditional channel models. This shows that the traditional bounds on the transport capacity [1]-[4] do not change more than constant factor pi if we employ network coding. As a corollary, we find that the gain of network coding on the throughput of large scale homogeneous wireless networks is asymptotically bounded by a constant. Note that our result is more general than the previous work [5] and it is obtained by a different technique. In conclusion, we show that in contrast to wired networks, the network coding gain in wireless networks is constraint by fundamental limitations.

This paper addresses the dynamics of broadcast flooding in random wireless ad hoc networks. In particular, we study the subset of nodes covered by a flood as well as timing issues related to the first (latency) and the last time (duration of back-chatter) at which a broadcast is received by a fixed node. Notably, this analysis takes into account the MAC-layer as well as background traffic which both are often neglected in related studies. Assuming a protocol model for the transmission channel which accounts for carrier sensing and interference, we find bounds for the probability of survival of the flood and for its coverage probabilities. Moreover, under certain conditions on the parameters, we establish asymptotical linear bounds on the latency as the distance from the origin of the flood increases and show that the duration of the back-chatter is stochastically bounded. The analytical results are compared to simulation.

Existing work on the capacity of wireless networks predominantly considers homogeneous random networks with random work load. The most relevant bounds on the network capacity, e.g., take into account only the number of nodes and the area of the network. However, these bounds can significantly overestimate the achievable capacity in real world situations where network topology or traffic patterns often deviate from these simplistic assumptions. To provide analytically tractable yet asymptotically tight approximations of network capacity we propose a novel space-based approach. At the heart of our methodology lie simple functions which indicate the presence of active transmissions near any given location in the network and which constitute a tool well suited to untangle the interactions of simultaneous transmissions. We are able to provide capacity bounds which are tighter than the traditional ones and which involve topology and traffic patterns explicitly, e.g., through the length of Euclidean Minimum Spanning Tree, or through traffic demands between clusters of nodes. As an additional novelty our results cover unicast, multicast and broadcast and are asymptotically tight. Notably, our capacity bounds are simple enough to require only knowledge of node location, and there is no need for solving or optimizing multi-variable equations in our approach.

Understanding the characteristics of the Internet delay space (i.e., the all-pairs set of static round-trip propagation delays among edge networks in the Internet) is important for the design of global-scale distributed systems. For instance, algorithms used in overlay networks are often sensitive to violations of the triangle inequality and to the growth properties within the Internet delay space. Since designers of distributed systems often rely on simulation and emulation to study design alternatives, they need a realistic model of the Internet delay space.Our analysis shows that existing models do not adequately capture important properties of the Internet delay space. In this paper, we analyze measured delays among thousands of Internet edge networks and identify key properties that are important for distributed system design. Furthermore, we derive a simple model of the Internet delay space based on our analytical findings. This model preserves the relevant metrics far better than existing models, allows for a compact representation, and can be used to synthesize delay data for simulations and emulations at a scale where direct measurement and storage are impractical.

In this paper we study the broadcast capacity of multihop wireless networks which we define as the maximum rate at which broadcast packets can be generated in the network such that all nodes receive the packets successfully in a limited time. We employ the Protocol Model for successful packet reception usually adopted in network capacity studies and provide novel upper and lower bounds for the broadcast capacity for arbitrary connected networks. In a homogeneous dense network these bounds simplify to Θ(W/max(1,Δd)) where W is the wireless channel capacity, Δ the interference parameter, and d the number of dimensions of space in which the network lies. Interestingly, we show that the broadcast capacity does not change by more than a constant factor when we vary the number of nodes, the radio range, the area of the network, and even the node mobility. To address the achievability of capacity, we demonstrate that any broadcast scheme based on a backbone of size proportional to the Minimum Connected Dominating Set guarantees a throughput within a constant factor of the broadcast capacity. Finally, we demonstrate that broadcast capacity, in stark contrast to unicast capacity, does not depend on the choice of source nodes or the dimension of the network.

This paper develops a novel color-based broadcast scheme for wireless ad hoc networks where each forwarding of the broadcast message is assigned a color from a given pool of colors. A node only forwards the message if it can assign it a color from the pool which it has not already overheard after a random time. In the closely related counter-based broadcast scheme a node simply counts the number of broadcasts not the colors overheard. The forwarding nodes form a so-called backbone, which is determined by the random timers and, thus, is random itself. Notably, any counter-generated backbone could result from pruning a color-generated backbone; the typical color-generated backbone, however, exhibits a connectivity graph richer than the counter-based ones. As a particular advantage, the colors reveal simple geometric properties of the backbones which we exploit to prove that the size of both, color- and counter-generated back-bones are within a small constant factor of the optimum. We also propose two techniques, boosting and edge-growing, that improve the performance of color- and counter-based broadcast in terms of reachability and number of rebroadcasts. Experiments reveal that the powerful boosting method is considerably more effective with the color-based schemes.

High capacity data transfers over the Internet routinely fail to meet end-to-end performance expectations. The default transport control protocol for best effort data traffic is currently TCP, which does not scale well to 100 Mbps and higher networks over long distances. In congestion avoidance, TCP is not swift enough to fully utilize resources over paths with a high delay bandwidth product. First attempts to alleviate this problem by equipping TCP with increased aggressiveness have shown the disadvantage of poor fairness with the ubiquitous standard TCP-Reno, or in some cases, even among two connections running over the same path. We propose a new delay sensitive-congestion avoidance mode (TCP-Africa) that allows for scalable, aggressive behavior in large underutilized links, yet falls back to the more conservative TCP-Reno algorithm once links become well utilized and congestion is imminent. Through ns2 simulations we argue for the safety, efficiency, and fairness of TCP-Africa.

Multiplicative processes, multifractals, and more recently also infinitely divisible cascades have seen increased popularity in a host of applications requiring versatile multiscale models, ranging from hydrodynamic turbulence to computer network traffic, from image processing to economics. The methodologies prevalent as of today rely to a large extent on iterative schemes used to produce infinite detail and repetitive structure across scales. While appealing, due to their simplicity, these constructions have limited applicability as they lead by default to power-law progression of moments through scales, to nonstationary increments and often to inherent log-periodic scaling which favors an exponential set of scales. This paper studies and develops a wide class of infinitely divisible cascades (IDC), thereby establishing the first reported cases of controllable scaling of moments in non-power-law form. Embedded in the framework of IDC, these processes exhibit stationary increments and scaling over a continuous range of scales. Criteria for convergence, further statistical properties, as well as MATLAB routines are provided.

We study the problem of locating in space and over time a network pathâ s tight link, that is the link with the least available bandwidth on the path. Tight link localization benefits network-aware applications, provides insight into the causes of network congestion and ways to circumvent it, and aids network operations. We present STAB, a light-weight probing tool to locate tight links. STAB combines the probing concepts of self-induced congestion, tailgating, and packet chirps in a novel fashion. We demonstrate its capabilities through experiments on the Internet and verify our results using router MRTG data.

Over the last few years, the network community has started to make heavy use of novel concepts such as self-similarity and long-range dependence (LRD). Despite their wide use, there is still much confusion regarding the identification of such phenomena in real network traffic data. We show that estimating long-range dependence is not straightforward: there is no systematic or definitive methodology. There exist several estimating methodologies, but they can give misleading and conflicting estimates. More specifically, we arrive at several conclusions that could provide guidelines for a systematic approach to LRD. First, long-range dependence may exist, even if the estimators have different estimates of the Hurst exponent in the interval 0.5-1. Second, long-range dependence is unlikely to exist, if there are several estimators that fail to estimate the Hurst exponent. Third, we show that periodicity can obscure the analysis of a signal giving partial evidence of long-range dependence. Fourth, the Whittle estimator is the most accurate in finding the exact value when LRD exists, but it can be fooled easily by periodicity. As a case-study, we analyze real round-trip time data. We find and remove a periodic component from the signal, before we can identify long-range dependence in the remaining signal.

Network traffic exhibits drastically different statistics, ranging from nearly Gaussian marginals and Long range dependence at very large time scales to highly non-Gaussian marginals and multi fractal scaling on small scales. This behavior can be explained by forming two components of the traffic according to the speed of connections, one component absorbing most traffic and being mostly Gaussian, the other constituting virtually all the small scale bursts. Towards a better understanding of this phenomenon, we propose a novel tree-based model which is flexible enough to accommodate Gaussian as well as bursty behavior on different scales in a parsimonious way.

This paper reviews the multifractal wavelet model (MWM) and its applications to network traffic modeling and inference. The discovery of the fractal nature of traffic has made new models and analysis tools for traffic essential, since classical Poisson and Markov models do not capture important fractal properties like multiscale variability and burstiness that deleteriously affect performance. Set in the framework of multiplicative cascades, the MWM provides a link to multifractal analysis, a natural tool to characterize burstiness. The simple structure of the MWM enables fast O(N) synthesis of traffic for simulations and a tractable queuing analysis, thus rendering it suitable for real networking applications including end-to-end path modeling.

Many studies have indicated the importance of capturing scaling properties when modeling traffic loads; however, the influence of long-range dependence (LRD) and marginal statistics still remains on an unsure footing. In this paper, we study these two issues by introducing a multiscale traffic model and a novel multiscale approach to queuing analysis. The multifractal wavelet model (MWM) is a multiplicative, wavelet-based model that captures the positivity, LRD, and "spikiness" of non-Gaussian traffic. Using a binary tree, the model synthesizes an N-point data set with only O(N) computations. Leveraging the tree structure of the model, we derive a multiscale queuing analysis that provides a simple closed form approximation to the tail queue probability, valid for any given buffer size. The analysis is applicable not only to the MWM but to tree-based models in general, including fractional Gaussian noise. Simulated queuing experiments demonstrate the accuracy of the MWM for matching real data traces and the precision of our theoretical queuing formula. Thus, the MWM is useful not only for fast synthesis of data for simulation purposes but also for applications requiring accurate queuing formulas such as call admission control. Our results clearly indicate that the marginal distribution of traffic at different time-resolutions affects queuing and that a Gaussian assumption can lead to over-optimistic predictions of tail queue probability even when taking LRD into account.

Understanding the nature and characteristics of e-business workloads is a crucial step to improve the quality of service offered to customers in electronic business environments.However, the variety and complexity of the interactions between customers and sites make the characterization of ebusiness workloads a challenging problem.Using a multilayer hierarchical model, this paper presents a detailed characterization of the workload of two actual e-business sites: an online bookstore and an electronic auction site.Through the characterization process, we found the presence of autonomous agents, or robots, in the workload and used the hierarchical structure to determine their characteristics.We also found that search terms follow a Zipf distribution.

In this paper, we develop a simple and powerful multiscale model for the synthesis of nonGaussian, long-range dependent (LRD) network traffic. Although wavelets effectively decorrelate LRD data, wavelet-based models have generally been restricted by a Gaussianity assumption that can be unrealistic for traffic. Using a multiplicative superstructure on top of the Haar wavelet transform, we exploit the decorrelating properties of wavelets while simultaneously capturing the positivity and "spikiness" of nonGaussian traffic. This leads to a swift O(N) algorithm for fitting and synthesizing N-point data sets. The resulting model belongs to the class of multifractal cascades, a set of processes with rich statistical properties. We elucidate our model's ability to capture the covariance structure of real data and then fit it to real traffic traces. Queueing experiments demonstrate the accuracy of the model for matching real data. Our results indicate that the nonGaussian nature of traffic has a significant effect on queuing.

We develop a new multiscale modeling framework for characterizing positive-valued data with long-range-dependent correlations (1/f noise). Using the Haar wavelet transform and a special multiplicative structure on the wavelet and scaling coefficients to ensure positive results, the model provides a rapid O(N) cascade algorithm for synthesizing N-point data sets. We study both the second-order and multifractal properties of the model, the latter after a tutorial overview of multifractal analysis. We derive a scheme for matching the model to real data observations and, to demonstrate its effectiveness, apply the model to network traffic synthesis. The flexibility and accuracy of the model and fitting procedure result in a close fit to the real data statistics (variance-time plots and moment scaling) and queuing behavior. Although for illustrative purposes we focus on applications in network traffic modeling, the multifractal wavelet model could be useful in a number of other areas involving positive data, including image processing, finance, and geophysics.