Search

For many practical applications, it is a fundamental problem to estimate the flow cardinalities over big network data consisting of numerous flows (especially a large quantity of mouse flows mixed with a small number of elephant flows, whose cardinalities follow a power-law distribution). Traditionally the research on this problem focused on using a small amount of memory to estimate each flow’s cardinality from a large range (up to ${10}^{{9}}$ ). However, although the memory needed for each individual flow has been greatly compressed, when there is an extremely large number of flows, the overall memory demand can still be very high, exceeding the availability under some important scenarios, such as implementing online measurement modules in network processors using only on-chip cache memory. In this paper, instead of allocating a separated data structure (called estimator ) for each flow, we take a different path by viewing all the flows together as a whole: Each flow is allocated with a virtual estimator, and these virtual estimators share a common memory space. We discover that sharing at the multi-bit register level is superior than sharing at the bit level. We propose a unified framework of virtual estimators that allows us to apply the idea of sharing to an array of cardinality estimation solutions, e.g., HyperLogLog and PCSA, achieving far better memory efficiency than the best existing work. Our experiment shows that the new solution can work in a tight memory space of less than 1 bit per flow or even one tenth of a bit per flow — a quest that has never been realized before.

Traffic measurement provides critical real-world data for service providers and network administrators to perform capacity planning, accounting and billing, anomaly detection, and service provision. One of the greatest challenges in designing an online measurement module is to minimize the per-packet processing time in order to keep up with the line speed of the modern routers. To meet this challenge, we should minimize the number of memory accesses per packet and implement the measurement module in the on-die SRAM. The small size of SRAM requires extremely compact data structures to be designed for storing per-flow information. The best existing work, called counter braids, requires more than 4 bits per flow and performs six or more memory accesses per packet. In this paper, we design a fast and compact measurement function that estimates the sizes of all flows. It achieves the optimal processing speed: two memory accesses per packet. In addition, it provides reasonable measurement accuracy in a tight space where the counter braids no longer work. Our design is based on a new data encoding/decoding scheme, called randomized counter sharing. This scheme allows us to mix per-flow information together in storage for compactness and, at the decoding time, separate the information of each flow through statistical removal of the error introduced during information mixing from other flows. The effectiveness of our online per-flow measurement approach is analyzed and confirmed through extensive experiments based on real network traffic traces. We also propose several methods to increase the estimation range of flow sizes.

The global deployment of IP multicast has been slow due to the difficulties related to heterogeneity, scalability, manageability, and lack of a robust interdomain multicast routing protocol. Application-level multicast becomes a promising alternative. Many overlay multicast systems have been proposed in recent years. However, they are insufficient in supporting applications that require any-source multicast with varied host capacities and dynamic membership. In this paper, we propose two capacity-aware multicast systems that focus on host heterogeneity, any source multicast, dynamic membership, and scalability. We extend Chord and Koorde to be capacity-aware. We then embed implicit degree-varying multicast trees on top of the overlay network and develop multicast routines that automatically follow the trees to disseminate multicast messages. The implicit trees are well balanced with the workload evenly spread across the network. We rigorously analyze the expected performance of multisource capacity-aware multicasting, which was not thoroughly addressed in any previous work. We also perform extensive simulations to evaluate the proposed multicast systems.

The performance regularity is concerned with the overall performance behavior of a system in the full spectrum of working area. Such a performance characteristic is generally overlooked and does not receive proper attention. The aim of this paper is twofold. First, it raises awareness of the importance of the performance regularity of a Web server. Secondly, it introduces the Gini performance coefficient (GPC) as a scale-invariant metric for measuring the performance regularity. In this paper, we present the theorems that relate the performance regularity of a Web server to the GPC, thereby providing a quantitative yardstick that complements the system capacity metric such as maximum throughput for measuring the system performance. To illustrate the use of the proposed approach, we calculate the values of GPC for several representative systems that were used in the public SPECweb96 benchmark study. The results are completely in line with our theoretical analysis.

Vehicular networks might be deployed in the near future, and as a consequence a potentially large number of exciting applications are expected to enhance the human driving experience. Unless the security of such applications is guaranteed, however, such enhancements may be accompanied by similarly powerful and yet undesired consequences in malicious behaviour. While current research in the vehicular networks security area has recognized conventional security and cryptographic threats, detailed modeling and analysis of threats that are specific to vehicle traffic are rarely considered in the literature. In this paper we lay ground for a comprehensive investigation of “traffic-related” threats to vehicular networks. We study the problem of modeling traffic-related attacks in these networks and present automatic and efficient (i.e., no human intervention and no expensive cryptographic protocols) yet general solutions to prevent or tolerate a number of these attacks. Specifically, we propose techniques based on the capability of implementing simple and non-interactive voting algorithms that use the mere participations of vehicles to the network and, while doing that, attempt to maximize use of already exchanged and relevant network data. We validate our techniques by providing analysis results based on both simulated and real-life mobility data in typical urban environments. Previous work required interactive protocols to implement voting or consensus techniques, and implicitly left open the question we solve in this paper.

This paper attempts to answer a question: for a given traversal area, how to quantify the geometric impact of anchor placement on localization performance. We present a theoretical framework for quantifying the anchor placement impact. An experimental study, as well as the field test using a UWB ranging technology, is presented. These experimental results validate the theoretical analysis. As a byproduct, we propose a two-phase localization method (TPLM) and show that TPLM outperforms the least-square method in localization accuracy by a huge margin. TPLM performs much faster than the gradient descent method and slightly better than the gradient descent method in localization accuracy. Our field test suggests that TPLM is more robust against noise than the least-square and gradient descent methods., Comment: infocom 1012

We study the power-aware buffering problem in battery-powered sensor networks, focusing on the fixed-size and fixed-interval buffering schemes. The main motivation is to address the yet poorly understood size variation-induced effect on power-aware buffering schemes. Our theoretical analysis elucidates the fundamental differences between the fixed-size and fixed-interval buffering schemes in the presence of data-size variation. It shows that data-size variation has detrimental effects on the power expenditure of the fixed-size buffering in general, and reveals that the size variation induced effects can be either mitigated by a positive skewness or promoted by a negative skewness in size distribution. By contrast, the fixed-interval buffering scheme has an obvious advantage of being eminently immune to the data-size variation. Hence the fixed-interval buffering scheme is a risk-averse strategy for its robustness in a variety of operational environments. In addition, based on the fixed-interval buffering scheme, we establish the power consumption relationship between child nodes and parent node in a static data-collection tree, and give an in-depth analysis of the impact of child bandwidth distribution on the parent's power consumption. This study is of practical significance: it sheds new light on the relationship among power consumption of buffering schemes, power parameters of radio module and memory bank, data arrival rate, and data-size variation, thereby providing well-informed guidance in determining an optimal buffer size (interval) to maximize the operational lifespan of sensor networks.

We lay ground for a comprehensive investigation of “traffic-related” threats to vehicular networks. While current research in the vehicular networks security area has done a good job in recognizing standard security and cryptographic threats, detailed modeling and analysis of threats that are specific to vehicle traffic are rarely considered in the literature. In this paper we study the problem of modeling traffic-related attacks in vehicular networks and presenting automatic and efficient (i.e., no human intervention and no expensive cryptographic protocols) solutions to prevent or tolerate a number of these attacks. To prevent these attacks, we propose techniques based on the capability of implementing simple and non-interactive voting algorithms using the mere participations of vehicles to the vehicular network. We provide analysis and simulation results in typical urban environments validating our techniques. Previous work required interactive protocols to implement voting or consensus techniques and implicitly left open the question we solve in this paper.

Wireless Internet in the in-vehicle environment is an evolving reality that reflects the gradual maturity of wireless technologies. Its complexity is reflected in the diversity of wireless technologies and dynamically changing network environments. The ability to adapt to the dynamics of such environments and to survive transient failures due to network handoffs are fundamentally important in failure-prone vehicular environments. In this paper we identify several new issues arising from network heterogeneity in vehicular environments and concentrate on designing and implementing a network-aware prototype system that supports HTTP session continuity in the presence of network volatility, with the emphasis on the following specifically tailored features: (1) automatic and transparent HTTP failure recovery, (2) network awareness and adaptation, (3) application-layer preemptive network handoff. Experimental results gathered from real application environments based on CDMA {\it 1xRTT} and IEEE 802 networks are presented and analyzed.

Caching is an effective mechanism for reducing bandwidth usage and alleviating server load. However, the use of caching entails a compromise between content freshness and refresh cost. Constant refreshing allows a high degree of content freshness at a greater cost of system resource. Conversely, too little refreshing reduces content freshness but saves the cost of resource usage. To address the freshness-cost problem, we formulate the refresh scheduling problem with a generic cost model and use this cost model to determine an optimal refresh frequency that gives the best trade-off between refresh cost and content freshness. We prove the existence and uniqueness of an optimal refresh frequency under the assumptions that the arrival of updated content is Poisson and the age-related cost monotonically increases with decreasing freshness. In addition, we provide an analytic comparison of system performance under fixed refresh scheduling and random refresh scheduling, showing that two refresh schedulings with the same average refresh frequency are mathematically equivalent in terms of the long-run average cost.