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.

Cardinality estimation over big network data consisting of numerous flows is a fundamental problem with many practical applications. 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 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 register (multi-bit) level is superior than sharing at the bit level. We propose a framework of virtual estimators that allows us to apply the idea of sharing to an array of cardinality estimation solutions, 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.

Compared to the classical barcode system, radio frequency identification (RFID) extends the operational distance from inches to a number of feet (passive RFID tags) or even hundreds of feet (active RFID tags). Their wireless transmission, processing, and storage capabilities enable them to support full automation of many inventory management functions in industry. This paper studies the practically important problem of monitoring a large set of active RFID tags and identifying the missing ones-the objects that the missing tags are associated with are likely to be missing as well. This monitoring function may need to be executed frequently and therefore should be made efficient in terms of execution time in order to avoid disruption of normal inventory operations. Based on probabilistic methods, we design a series of missing-tag identification protocols that employ novel techniques to reduce the execution time. Our best protocol reduces the time for detecting the missing tags by an order of magnitude when compared to existing protocols.

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.

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.

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 6 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: 2 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.

End-to-end fairness in a sensor network ensures that data from each sensor has an equal (or weighted) chance to reach the sink. It eliminates the problem that data flows from sensors at some locations (close to the sink) obtain most network bandwidth, while flows from sensors at other locations (far away from the sink) are starved. Existing fairness solutions assume single-path routing, which reduces achievable throughput of the network. In this paper, we propose a multipath fairness solution (MFS) that achieves end-to-end fairness among competing flows through fully distributed operations. MFS is easy to implement, which is advantageous in a resource-scarce sensor network. More importantly, it achieves much higher network throughput and better fairness among the flows.

Comparing with the classical barcode system, RFID extends the operational distance from inches to a number of feet (passive RFID tags) or even hundreds of feet (active RFID tags). Their wireless transmission, processing and storage capabilities enable them to support the full automation of many inventory management functions in the industry. This paper studies the practically important problem of monitoring a large set of RFID tags and identifying the missing ones - the objects that the missing tags are associated with are likely to be missing, too. This monitoring function may need to be executed frequently and therefore should be made efficient in terms of execution time, in order to avoid disruption of normal inventory operations. Based on probabilistic methods, we design a series of missing-tag identification protocols that employ novel techniques to reduce the execution time. Our best protocol reduces the time for detecting the missing tags by 88.9% or more, when comparing with existing protocols.

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.

This paper presents a study on the impact of buffering schemes on wireless sensor power consumption. Two common buffering paradigms are studied: fixed-size buffering and fixed-interval buffering. We present theoretical analyses of the power consumption of the buffering schemes, in relation to parameters of the sensor node's wireless radio and memory modules, as well as the sensor data arrival rate. Our results indicate that, under the same circumstances, the optimal fixed-size buffering scheme outperforms the optimal fixed-interval scheme in terms of overall power conservation. We also show that a power-aware buffering scheme can save significant energy consumption over a power-oblivious buffering scheme, thus prolonging the useful lifespan of the sensor nodes.

Cognitive adaptive radio teams (CART) is a new platform developed by our group in support of collaborative mapping of complex communications-challenged environments, for example in support of search and rescue operations in environments lacking an adequate communications infrastructure. Experience during the 9/11 terrorist attacks, Asian tsunami, Kashmir earthquake, and post-Katrina Gulf Coast make it clear that rescue workers cannot count upon computer networks or even cell telephone support in the immediate aftermath of such events. Similarly, military urban warfare operations must also be conducted in locations lacking communication infrastructure. CART combines state-of-the-art ad-hoc networking technology with machine learning and prediction algorithms to offer new capabilities under these very difficult conditions

Deadlock detection scheduling is an important, yet often overlooked problem that can significantly affect the overall performance of deadlock handling. Excessive initiation of deadlock detection increases overall message usage, resulting in degraded system performance in the absence of deadlocks, while insufficient initiation of deadlock detection increases the deadlock persistence time, resulting in an increased deadlock resolution cost in the presence of deadlocks. The investigation of this performance trade-off, however, is missing in the literature. This paper studies the impact of deadlock detection scheduling on the overall performance of deadlock handling. In particular, we show that there exists an optimal deadlock detection frequency that yields the minimum long-run mean average cost, which is determined by the message complexities of the deadlock detection and resolution algorithms being used, as well as the rate of deadlock formation, denoted as lambda. For the best known deadlock detection and resolution algorithms, we show that the asymptotically optimal frequency of deadlock detection scheduling that minimizes the overall message overhead is O((lambdan)1/3) when the total number n of processes is sufficiently large. Furthermore, we show that, in general, fully distributed (uncoordinated) deadlock detection scheduling cannot be performed as efficiently as centralized (coordinated) deadlock detection scheduling

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.

Load balancing for distributed servers is a common issue in many applications and has been extensively studied. Several distributed load balancing schemes have been proposed that proactively route individual requests to appropriate servers to best balance the load and shorten request response time. These schemes do not require a centralized load balancer. Instead, each server is responsible for determining, for each request it receives from a client, to which server in the pool the request should be forwarded for processing. We propose a new request routing scheme that is more scalable to increasing number of servers and request load than the existing schemes. The method combines random server selection and next-neighbor load sharing techniques that together prevent the staleness of load information from building up when the number of servers increases. Our simulation shows that it outperforms existing schemes under a piggyback-based load update model.

The global deployment of IP multicast has been slow due to the difficulties related to heterogeneity, scalability, manageability, and lack of a robust inter-domain 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 large-scale any-source multicast with highly varied host capacities and highly dynamic membership. In this paper, we propose two capacity-aware multicast systems that focus on host heterogeneity, dynamic membership, scalability, and any source multicast. 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 workload evenly spread across the network. We also perform extensive simulations to evaluate the proposed multicast systems

Deadlock detection scheduling is an important, yet oft-overlooked problem that can significantly affect the overall performance of deadlock handling.An excessive initiation of deadlock detection increases overall message usage, resulting in degraded system performance in the absence of deadlocks; while a deficient initiation of deadlock detection increases the deadlock persistence time, resulting in an increased deadlock resolution cost in the presence of deadlocks. Such a performance tradeoff, however, is generally missing in literature. In this paper we study the impact of deadlock detection scheduling on the system performance, and show that there exists an optimal deadlock detection frequency that yields the minimum long-run mean average cost associated with the message complexity of deadlock detection and resolution algorithms, and the rate of deadlock formation, λ. Based on the up-to-date deadlock detection and resolution algorithms, we show that the asymptotically optimal frequency of deadlock detection scheduling that minimizes the message overhead is cal O((λ n)1/3), when the total number of processes n is sufficiently large. Furthermore, we show that in general fully distributed (uncoordinated) deadlock detection scheduling can not be performed as efficiently as centralized (coordinated) deadlock detection scheduling.

In mobile wireless environments, bandwidth fluctuations are unpredictable, and the throughput experienced by mobile user applications is dynamic. Real-time tracking of bandwidth variations is desirable to effectively manage the throughput available to a user application at any given time. We propose a throughput control mechanism for applicability over wireless networks, transparent to the underlying transport and network technologies. To improve the utilization of the available throughput, we develop a two-component application-layer, real-time control technique for mobile users traversing diverse networks with varying service rates. We first calculate the weighted average throughput experienced by the user's application. Secondly, we appropriately adjust the download rate to the user based on the real-time average throughput information. In this paper, we detail the throughput control algorithm and provide some initial simulation results.

Top-k queries arise naturally in many database applications that require searching for records whose attribute values are close to those specified in a query. We study the problem of processing a top-k query by translating it into an approximate range query that can be efficiently processed by traditional relational DBMSs. We propose a sampling-based approach, along with various query mapping strategies, to determine a range query that yields high recall with low access cost. Our experiments on real-world datasets show that, given the same memory budgets, our sampling-based estimator outperforms a previous histogram-based method in terms of access cost, while achieving the same level of recall. Furthermore, unlike the histogram-based approach, our sampling-based query mapping scheme scales well for high dimensional data and is easy to implement with low maintenance cost.

Checkpointing is an effective fault-tolerant technique for improving system availability and reliability. However, a blind checkpointing placement can result in either performance degradation or expensive recovery cost. By means of the calculus of variations, we derive an explicit formula that links the optimal checkpointing frequency with a general failure rate, with the objective of globally minimizing the total expected cost of checkpointing and recovery. Theoretical result shows that the optimal checkpointing frequency is proportional to the square root of the failure rate and can be uniquely determined by the failure rate (time-varying or constant) if the recovery function is strictly increasing and the failure rate is /spl lambda/(/spl infin/)>0. J.L. Bruno and E.G. Coffman (1997) suggest that optimal checkpointing by its nature is a function of system failure rate, i.e., the time-varying failure rate demands time-varying checkpointing in order to meet the criteria of certain optimality. The results obtained in this paper agree with their viewpoint.

Traditional sampling-based estimators infer the actual selectivity of a query based purely on runtime information gathering, excluding the previously collected information, which underutilizes the information available. Table-based and parametric estimators extrapolate the actual selectivity of a query based only on the previously collected information, ignoring online information, which results in inaccurate estimation in a frequently updated environment. We propose a novel hybrid estimator that utilizes and optimally combines the online and previously collected information. A theoretical analysis demonstrates that the online and previously collected information is complementary, and that the comprehensive utilization of the online and previously collected information is of value for further performance improvement. Our theoretical results are validated by a comprehensive experimental study using a practical database, in the presence of insert, delete and update operations. The hybrid approach is very promising in the sense that it provides an adaptive mechanism that allows the optimal combination of information obtained from different sources in order to achieve a higher estimation accuracy and reliability.

The results of a performance study of the representative sampling-based size estimation methods in database management systems are reported in this paper. Major performance measurement includes estimation accuracy, the amount of sample taken, and the coverage. The impact of skewed data on the performance is also discussed. These results allow a better understanding and assessment of sampling estimation methods and determine the suitability of different methods under different situations.>

This paper proposes a novel strategy for estimating the size of the resulting relation after an equi-join and selection using a regression model. An approximating series representing the underlying data distribution and dependency is derived from the actual data. The proposed method provides an instant and accurate size estimation by performing an evaluation of the series, with no run-time overheads in page faults and space, and with negligible CPU overhead. In contrast, the popular sampling methods incur run-time overheads in page faults (for sampling), CPU time and space. These overheads of sampling methods increase the response time of processing a query. The results of a comprehensive experimental study are also reported, which demonstrate that the estimation accuracy by the proposed method is comparable with that of the sampling methods which are believed to provide the most accurate estimation. The proposed method seems ideal for retrieval-intensive database and information systems. Since the overheads involved in deriving the approximating series are fairly moderate, we believe that this method is also an extremely competent method when moderate or periodical updates are present.