1001399
DS-PPS: A Practical Framework to Guarantee Differentiated QoS in Terabit Routers with Parallel Packet Switch
Parallel Packet Switch (PPS) is used intensively in today's terabit router to construct the switching fabric. Basic PPS equally deals with all of the traffic in order to achieve uniform load-balancing and high throughput, but it fails to support differentiated QoS. With the recent blooming of delay- sensitive Internet traffic, such as the peer-to-peer live streaming and IPTV, differentiated QoS is becoming an urgent demand. In this paper, we propose a novel and practical framework, the Differentiated Service Parallel Packet Switch (DS-PPS), which supports three fundamental QoS features: guaranteed-delay (GD), guaranteed-bandwidth (GB) and best-effort (BE). By adaptively adjusting the number of switching planes offered to each QoS class, DS-PPS precisely controls the delay bounds of GD traffic and the drop precedence of GB traffic. We evaluate DS-PPS by extensive theoretical analyses and comprehensive simulations. Experimental results on a prototype implementation of the framework show that DS-PPS outperforms the basic PPS in three main aspects. First, the average delay of TCP short packet under full load is reduced by more than 94%. Second, the average delay of real-time traffic under full load is reduced by more than 82%. And third, the GB traffic of low drop precedence is guaranteed of nearly three times the throughput of high drop precedence at the hotspots. Significantly, our proposed DS-PPS framework is universal and scalable to support various kinds of emerging QoS-sensitive applications in multi-service terabit routers without any extra overhead.
18230
Indexable PLA for Efficient Similarity Search
Similarity-based search over time-series databases has been a hot research topic for a long history, which is widely used in many applications, including multimedia retrieval, data mining, web search and retrieval, and so on. However, due to high dimensionality (i.e. length) of the time series, the similarity search over directly indexed time series usually encounters a serious problem, known as the "dimensionality curse". Thus, many dimensionality reduction techniques are proposed to break such curse by reducing the dimensionality of time series. Among all the proposed methods, only Piecewise Linear Approximation (PLA) does not have indexing mechanisms to support similarity queries, which prevents it from efficiently searching over very large time-series databases. Our initial studies on the effectiveness of different reduction methods, however, show that PLA performs no worse than others. Motivated by this, in this paper, we re-investigate PLA for approximating and indexing time series. Specifically, we propose a novel distance function in the reduced PLA-space, and prove that this function indeed results in a lower bound of the Euclidean distance between the original time series, which can lead to no false dismissals during the similarity search. As a second step, we develop an effective approach to index these lower bounds to improve the search efficiency. Our extensive experiments over a wide spectrum of real and synthetic data sets have demonstrated the efficiency and effectiveness of PLA together with the newly proposed lower bound distance, in terms of both pruning power and wall clock time, compared with two state-of-the-art reduction methods, Adaptive Piecewise Constant Approximation (APCA) and Chebyshev Polynomials (CP).
12060317
DiCAS: An Efficient Distributed Caching Mechanism for P2P Systems
Peer-to-peer networks are widely criticized for their inefficient flooding search mechanism. Distributed hash table (DHT) algorithms have been proposed to improve the search efficiency by mapping the index of a file to a unique peer based on predefined hash functions. However, the tight coupling between indices and hosting peers incurs high maintenance cost in a highly dynamic network. To properly balance the tradeoff between the costs of indexing and searching, we propose the distributed caching and adaptive search (DiCAS) algorithm, where indices are passively cached in a group of peers based on a predefined hash function. Guided by the same function, adaptive search selectively forwards queries to "matched" peers with a high probability of caching the desired indices. The search cost is reduced due to shrunk searching space. Different from the DHT solutions, distributed caching loosely maps the index of a file to a group of peers in a passive fashion, which saves the cost of updating indices. Our simulation study shows that the DiCAS protocol can significantly reduce the network search traffic with the help of small cache space contributed by each individual peer
6911930
LANDMARC: Indoor Location Sensing Using Active RFID
Growing convergence among mobile computing devices and embedded technology sparks the development and deployment of “context-aware” applications, where location is the most essential context. In this paper we present LANDMARC, a location sensing prototype system that uses Radio Frequency Identification (RFID) technology for locating objects inside buildings. The major advantage of LANDMARC is that it improves the overall accuracy of locating objects by utilizing the concept of reference tags. Based on experimental analysis, we demonstrate that active RFID is a viable and cost-effective candidate for indoor location sensing. Although RFID is not designed for indoor location sensing, we point out three major features that should be added to make RFID technologies competitive in this new and growing market.
35965067
Dynamic Layer Management in Superpeer Architectures
Superpeer unstructured P2P systems have been found to be very effective by dividing the peers into two layers, superlayer and leaf-layer, in which message flooding is only conducted among superlayer and all leaf-peers are represented by corresponding superpeers. However, current superpeer systems do not employ any effective layer management schemes, so the transient and low-capacity peers are allowed to act as superpeers. Moreover, the lack of an appropriate size ratio maintenance mechanism on superlayer to leaf-layer makes the system's search performance far from being optimal. We present one workload model aimed at reducing the weighted overhead of a network. Using our proposed workload model, a network can determine an optimal layer size ratio between leaf-layer and superlayer. We then propose a dynamic layer management algorithm, DLM, which can maintain an optimal layer size ratio and adaptively elect and adjust peers between superlayer and leaf-layer. DLM is completely distributed in the sense that each peer decides to be a superpeer or a leaf-peer independently without global knowledge. DLM could effectively help a superpeer P2P system maintain the optimal layer size ratio and designate peers with relatively long lifetime and large capacities as superpeers, and the peers with short lifetime and low capacities as leaf-peers under highly dynamic network situations. We demonstrate that the quality of a superpeer system is significantly improved under the DLM scheme by comprehensive simulations.
848425
Location awareness in unstructured peer-to-peer systems
Peer-to-peer (P2P) computing has emerged as a popular model aiming at further utilizing Internet information and resources. However, the mechanism of peers randomly choosing logical neighbors without any knowledge about underlying physical topology can cause a serious topology mismatch between the P2P overlay network and the physical underlying network. The topology mismatch problem brings great stress in the Internet infrastructure. It greatly limits the performance gain from various search or routing techniques. Meanwhile, due to the inefficient overlay topology, the flooding-based search mechanisms cause a large volume of unnecessary traffic. Aiming at alleviating the mismatching problem and reducing the unnecessary traffic, we propose a location-aware topology matching (LTM) technique. LTM builds an efficient overlay by disconnecting slow connections and choosing physically closer nodes as logical neighbors while still retaining the search scope and reducing response time for queries. LTM is scalable and completely distributed in the sense that it does not require any global knowledge of the whole overlay network. The effectiveness of LTM is demonstrated through simulation studies.
53236276
From datalog rules to efficient programs with time and space guarantees
This paper describes a method for transforming any given set of Datalog rules into an efficient specialized implementation with guaranteed worst-case time and space complexities, and for computing the complexities from the rules. The running time is optimal in the sense that only useful combinations of facts that lead to all hypotheses of a rule being simultaneously true are considered, and each such combination is considered exactly once. The associated space usage is optimal in that it is the minimum space needed for such consideration modulo scheduling optimizations that may eliminate some summands in the space usage formula. The transformation is based on a general method for algorithm design that exploits fixed-point computation, incremental maintenance of invariants, and combinations of indexed and linked data structures. We apply the method to a number of analysis problems, some with improved algorithm complexities and all with greatly improved algorithm understanding and greatly simplified complexity analysis.
26921590
Evaluating structural constraints for accurate range image registration
New technological developments in optics and electronics are rendering laser scanning systems cheaper and more accurate. Such systems can directly capture depth information from objects simplifying range image analysis and enlarging their applications scope. Accurate image registration algorithms represent a pivotal aspect of range image analysis which still require substantial improvements. While a large number of algorithms have been proposed, it is very important to compare the performance of different registration algorithms so that good algorithms can be selected for real applications. Unfortunately, most of these algorithms are iterative with a number of parameters initialised by users. The main disadvantages of these methods are that these parameters are often context dependent. Thus, while aiming to develop automatic registration algorithms instead of comparing the registration algorithms themselves, we compare the structural constraints based on a single registration algorithm(GICP). A large number of experiments using real range images demonstrate their effectiveness on improving the GICP algorithm.
10720584
Graph-Based Semi-Supervised Learning as a Generative Model
This paper proposes and develops a new graph-based semi-supervised learning method. Different from previous graph-based methods that are based on discriminative models, our method is essentially a generative model in that the class conditional probabilities are estimated by graph propagation and the class priors are estimated by linear regression. Experimental results on various datasets show that the proposed method is superior to existing graph-based semi-supervised learning methods, especially when the labeled subset alone proves insufficient to estimate meaningful class priors.
903407
On integrating fluid models with packet simulation
Fluid models have been shown to he efficient and accurate in modelling large IP networks. However, unlike packet models, it is difficult to extract packet-level information from them. In this paper, we present a hybrid simulation method that maintains the performance advantage of fluid models while providing detailed packet level information for selected packet traffic flows. We propose two models to account for the interaction between background TCP traffic in a fluid network and foreground packet traffic of interest. The first assumes that the packet traffic poses a negligible load on the fluid network whereas the second accounts for the added load by transforming the packet traffic into fluid flows and solving the resulting enhanced fluid model. The first of these yields an efficient one pass solution algorithm whereas the second requires an additional pass to account for the packet traffic load. We establish the correctness of both approaches and present their implementation within ns-2. Comparisons between the hybrid models and a classical packet simulation show the two pass approach to be quite accurate and computationally efficient.
19403347
DVSR: a high-performance metro ring protocol
The Resilient Packet Ring (RPR) IEEE 802.17 standard is under development as a new high-speed backbone technology for metropolitan area networks. A key performance objective of RPR is to simultaneously achieve high utilization, spatial reuse, and fairness, an objective not achieved by current technologies such as SONET and Gigabit Ethernet or by legacy ring technologies such as FDDI. The core technical challenge for RPR is the design of a bandwidth allocation algorithm that dynamically achieves these properties. The difficulty is in the distributed nature of the problem, that upstream ring nodes must inject traffic at a rate according to congestion and fairness criteria downstream. Unfortunately, the proposed algorithms in the current draft standards have a number of critical limitations. For example, we show that in a two-flow two-link scenario with unbalanced and constant-rate traffic demand, a draft RPR algorithm will suffer from dramatic bandwidth oscillations within nearly the entire range of the link capacity. Moreover, such oscillations hinder spatial reuse and decrease throughput significantly. We are developing a new dynamic bandwidth allocation algorithm called Distributed Virtual-time Scheduling in Rings (DVSR). The key idea is for nodes to compute a simple lower bound of temporally and spatially aggregated virtual time using per-ingress counters of packet (byte) arrivals. We show that with this information propagated along the ring, each node can remotely approximate the ideal fair rate for its own traffic at each downstream link. Hence, DVSR flows rapidly converge to their ring-wide fair rates while maximizing spatial reuse. To evaluate DVSR, we are using a combination of theoretical analysis, simulation, and implementation, including a proof-of-concept prototype of DVSR on a 1 Gb/sec network processor testbed.