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.

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.

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.

Distributed denial of service (DDoS) has long been an open security problem of the Internet. Most proposed solutions require the upgrade of routers across the Internet, which is extremely difficult to realize, considering that the Internet consists of a very large number of autonomous systems with routers from different vendors deployed over decades. A promising alternative strategy is to avoid the universal upgrade of router infrastructure and instead rely on an overlay of end systems. The prior anti-DoS overlays were designed to protect emergency services for authorized clients. They assume that trust exists between authorized clients and a private server. Only authenticated traffic can pass through the overlay network to reach the server, while the attack traffic is not admitted without passing the authentication. The follow-up extension of the anti-DoS overlays for web service has other serious limitations. This paper attempts to solve an important problem. How to design an anti-DoS overlay service (called AID) that protects general-purpose public servers while overcoming the limitations of the existing systems? Anyone, including the attackers, should be able to access the server. Authentication can no longer be the means of defense. While both normal and malicious clients are given the access, AID is designed to fend off attack traffic while letting legitimate-traffic through. Its operations are completely transparent to the users (humans or hosts), the client/server software, and the internal/core routers. To connect the AID service nodes (which are end systems), we choose a random overlay network for its rich, unpredictable connectivity, short diameter, and ease of management. We use a distributed virtual-clock packet scheduling algorithm to restrict the amount of data any client can impose on AID. We analyze the properties of the AID service based on probabilistic models. Our simulations demonstrate that AID can effectively protect legitimate-traffic from attack traffic. Even when 10% of all clients attack, just 1.4% of legitimate-traffic is mistakenly blocked, no matter how aggressive the attackers are.

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.

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.

Motivated by the work of cache freshness by Cho and Garcia-Molina [2], we present a new metric called additive age as an extension of existing freshness metrics. The additive age, being formulated somewhat differently, deviates from existing freshness metrics in its ability to better quantify the impact of frequently updated content on cache freshness. Mathematical result shows that the long-run average additive age is proportional to λT2, where λ is the change rate of source content, and T the refresh interval. This short paper briefly reviews the key elements of Cho and Garcia-Molina's work and simplifies their derivation by using renewal reward theory, with a focus on formulation of the notion of additive age.

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.

The success of e-commerce, messaging middleware, and other Internet-based applications depends in part on the ability of network servers to respond in a timely and reliable manner to simultaneous service requests. Multithreaded systems, due to their efficient use of system resources and the popularity of shared-memory multi-processor architectures, have become the server implementation of choice. However, creating and destroying a thread is far from free, requiring run-time memory allocation and deallocation. These overheads become especially onerous during periods of high load and can be a major factor behind system slowdowns. A thread-pool architecture addresses this problem by prespawning and then managing a pool of threads. Threads in the pool are reused, so that thread creation and destruction overheads are incurred only once per thread, and not once per request. However, efficient thread management for a given system load highly depends on the thread pool size, which is currently determined heuristically. In this paper, we characterize several system resource costs associated with thread pool size. If the thread pool is too large, and threads go unused, then processing and memory resources are wasted maintaining the thread pool. If the thread pool is too small, then additional threads must be created and destroyed on the fly to handle new requests. We analytically determine the optimal thread pool size to maximize the expected gain of using a thread.

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.

Inheritance, together with object and class, is the key concept of object oriented systems. Adopting the concept-oriented view (COV for short) of inheritance, current OO systems such as GemStone, Orion, C++, O 2 , PostGres, Iris, and SmallTalk dominantly interpret inheritance by retaining all attributes and methods in a subclass from its superclass, and by supporting the specification of additional attributes and methods in the subclass. However, this monotonic extension property may result in a redundant subclass representation which in turn gives rise to update anomalies. Thus extra effort in practice used to prevent these problems from happening is to change an IS-A relationship in COV of hierarchy into sibling in the program-oriented view (POV for short) hierarchy. However, the dichotomy between the concept and implementation leads to a significant difference of the class hierarchy between the designing phase and implementation phase of OO systems, hence increases the complexity in designing OO systems. In this paper, we show that, when the subclass attributes are linearly related to the superclass attributes (the attributes in the superclass can be linearly expressed by those in the subclass), linear subclass assertions/constraints can be elegantly used to resolve the problems such as the redundant subclass representation , and update anomalies . We have proved that (1) given a linear subclass assertion, a non-redundant subclass representation can be automatically decided, and the bilateral mappings between the class and the determined subclass can be automatically constructed, and (2) given a user-chosen subclass representation and the mapping from the chosen subclass to the superclass, the linear subclass assertion and inverse mapping can be automatically constructed, and (3) placing an object into the most specific class in an ISA class hierarchy can be automatically conducted. The proposed novel ideas have been prototyped on GemStone/Smalltalk on a SunSparc/Unix platform. Our experience indicates that the proposed idea can be efficiently and effectively integrated into an OO system.

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

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.

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.

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.

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 tradeoff, 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 ${\cal O}((\lambda n)^{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.

Sampling-based methods for estimating relation sizes after relational operators such as selections, joins and projections have been intensively studied in recent years. Methods of this type can achieve high estimation accuracy and efficiency. Since the dominating overhead involved in a sampling-based method is the sampling cost, different variants of sampling methods are proposed so as to minimize the sampling percentage (thus reducing the sampling cost) while maintaining the estimation accuracy in terms of the confidence level and relative error (to be precisely defined later in Section 2 ). In order to determine the minimal sampling percentage, the overall characteristics of the data such as the mean and variance are needed. Currently, the representative sampling-based methods in literature are based on the assumption that overall characteristics of data are unavailable, and thus a significant amount of effort is dedicated to estimating these characteristics so as to approach the optimal (minimal) sampling percentage. The estimation for these characteristics incurs cost as well as suffers the estimation error. In this short essay, we point out that the exact values of these characteristics of data can be kept track of in a database system at a negligible overhead. As a result, the minimal sampling percentage while ensuring the specified relative error and confidence level can be precisely determined.

Network fault diagnosis is an important aspect of network management. Often, a single component failure will result in a cascade of secondary faults that overwhelm simple reasoning approaches. If the network monitoring information is being transmitted through the network to the network management system (NMS), then fault diagnosis is complicated by the fact that the transmission of relevant monitoring information for fault diagnosis may be blocked either by the fault itself, or by the faultpsilas effects on the network. Without perfect knowledge, the best fault diagnosis algorithm must properly reason about a number of competing diagnostic explanations that are compatible with the ambiguous networking monitoring information known to the NMS. We describe a novel algorithm for computing all such possible diagnostic explanations and their relative likelihoods, thus providing a complete diagnosis of the network state that can be effectively used by an NMS to correct or mitigate faults. The algorithm uses a variant of classic Boolean satisfiability to efficiently and compactly represent the space of possible explanations. The proposed approach is well suited for networks with (semi-)autonomous management domains organized into a larger management hierarchy, a feature common to many military networks.

In a mobile networking environment, constant node motion result in drastic changes in spatial distribution of nodes which in turn causes changes in network topology. Blind position information updates could comprise a significant fraction of the network traffic. Consequently, maintaining accurate position information in such situations could become prohibitively expensive. In addition, the reference of information decreases as the distance increase, i.e., interest in position information could be highly localized and distant nodes do not require precise position description. In this paper, we propose a grid-based update mechanism that establishes the relationship between the grid-size and the frequency of position update. Such an association has two salient features: Firstly, only relevant updates based on location are transmitted avoiding redundant position updates. Secondly, it provides a guidance for adjusting the frequency of position updates in connection with the required positional accuracy and mobility pattern. We present an analysis of the performance of the proposed approach under the random walk mobility model, and proposes a fully distributed grid-based Markov model to capture the impact of mobility pattern on the frequency of position updates. We show in the simulation experiment that the proposed grid-based position update mechanism can reduce the network overhead for position updates by more than 65% while affecting the positional accuracy by less than 3%.

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.

DRAMA1 is a distributed policy-based management system designed to manage Mobile Ad hoc NETworks (MANETs). Its design philosophy is to create intelligent, self-adaptive policy agents to manage dynamic networks without human intervention. Network management functions are performed in a distributed fashion by these policy agents, rather than being controlled by a centralized management station. Policies are used to control the frequency and content of network management messages exchanged among policy agents in a way that reduces bandwidth usage and increases the utility of management messages. This greatly enhances management efficiency and reduces the bandwidth overhead required for network management. As with any new technology, there is a question about the scalability of this approach. The purpose of the work described in this paper is to study whether the DRAMA policy-based network management system can scale to networks of 500+ nodes. The study uses a novel simulation-based approach to evaluate DRAMA performance when DRAMA is used to manage MANETs of up to 500 nodes. The results confirm that the DRAMA distributed policy-based management paradigm provides superior performance over a centralized management paradigm for MANETs.

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

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.

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.

Performance evaluation is an important issue in building efficient Web servers. It is desirable to measure the performance regularity of Web servers for overall performance behavior of the system in the full spectrum of working area, which is generally overlooked and has not received proper attention. In this paper we aim to raising the awareness of the importance of the performance regularity of a Web server by introducing Gini performance coefficient (GPC) as a scale-invariant metric for measuring the performance regularity. 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. Several representative systems that were used in the public benchmark study are examined under the proposed metric. The results are completely in line with our theoretical analysis.

A wide variety of telematics applications emerge as an evolving reality that reflects continual convergence of Internet infrastructure and wireless technologies. Telematics, which is characterized by dynamically changing network environments, deviates significantly from wired-line and fixed-location communication. The ability to adapt to changing network conditions is critically important for telematics applications. In this paper, we highlight the importance of network awareness and network adaptation in telematics applications via real-life results, and present a prototype system, with specially tailored features to address newly emerging issues in telematics applications, as well experimental results based on the prototype system.

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.

The authors have developed an entropic approach to analyze the thermodynamic characteristics of biological growth processes governed by the Logistic, Bertalanffy, and Gompertz models (see IEEE Transactions on Biomedical Engineering, vol. BME-40, no. 12, p. 1193, 1993). In this short paper, the entropic flow, rates of the Logistic, Bertalanffy, and Gompertz growth models expressed in terms of the evolution time and the models' parameters are further discussed, and the critical values for the different patterns of the entropic flow rates are derived. It is interesting to note that the derived critical parameter values are identical to the parameter values at which the corresponding difference systems exhibit large-scale chaotic behavior.

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. >

Using the concept of isomorphism, we provide a quantitative description of the thermodynamic characteristics of the Logistic, Bertalanffy, and Gompertz biological growth models. With the help of the entropy expressions derived from the isomorphic probabilistic models, we show that the Logistic, Bertalanffy, and Gompertz growth models have distinct thermodynamic characteristics, though they have similar sigmoid trajectories in the time domain. The entropic analysis further reveals that the Gompertz model corresponds to a completely open system, in which cells receive adequate nutrition and competition among cells can be neglected. We have also applied the present entropic analysis to the modeling of tumor growth. Our results suggest that the entropic expression provides a theoretical justification for using the Gompertz model for describing the development of tumor cell populations. The entropic analysis may play an important role in studying the mechanisms of different biological growth processes. >

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.