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
14694684
A mutual anonymous peer-to-peer protocol design
Peer-to-peer (P2P) computing has become a popular application model because of its easy resource sharing pattern and powerful query search scheme. However, decentralized P2P architecture is scarcely seen to deploy the anonymity on its peers. In this paper, we propose a mutual anonymity protocol, called Secret-sharing-based Mutual Anonymity Protocol (SSMP), for decentralized P2P systems. SSMP employs Shamirs' secret sharing scheme to allow peers to issue queries and responders to deliver requested files anonymously. Compared with previous designs, SSMP achieves mutual anonymity in P2P systems with a high degree of anonymity and a low cryptography processing overhead. We evaluate SSMP by comprehensive simulations.
8905363
Improving Query Response Delivery Quality in Peer-to-Peer Systems
Unstructured peer-to-peer (P2P) system is the prevalent model in today's P2P systems. In such systems, a response is sent along the same path that carried the incoming query message. To guarantee the anonymity of the requestor, no requestor information is included in the response message, and each node in the query's incoming path only knows its direct neighbors who sent the query request to it. This mechanism introduces response loss when any one node or connection in the path fails, which is a common occurrence in the P2P system due to its dynamic feature. In this paper, we address the response loss problem and show that peers' oscillation can cause up to a 35 percent response loss in an unstructured P2P system. We also present three techniques to alleviate this problem: the redundant response delivery (RRD) scheme as a proactive approach, the adaptive response delivery (ARD) scheme as a reactive approach, and the extended adaptive response delivery scheme to render ARD to function in an unstructured P2P system with limited or no flooding-based search mechanism. We have evaluated our techniques in a large-scale network simulation. With limited traffic overhead, all three techniques reduce response loss rate by more than 65 percent and are fully distributed. We have designed our techniques to be simple to develop and implement in existing P2P systems
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.
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).
132343
Approaching optimal peer-to-peer overlays
In unstructured peer-to-peer (P2P) systems, there exists a serious topology mismatch problem between physical and logical network. We first analyze the relationship between the property of the overlay and the corresponding message duplications incurred by queries in a given overlay, and prove that computing an optimal overlay with global knowledge is an NP-hard problem. Motivated by the analysis results, we design a distributed overlay optimization algorithm, THANCS, to attack topology mismatch. We demonstrate its performance by comprehensive simulations in dynamic environments. The proposed THANCS has three major strengths. First, it does not need any global knowledge. Second, its optimization convergent speed is fast. Third, it is orthogonal with other types of advanced search approaches.
16164675
Energy efficient routing with adaptive data fusion in sensor networks
While in-network data fusion can reduce data redundancy and hence curtail network load, the fusion process itself may introduce significant energy consumption for emerging wireless sensor networks with vectorial data. Therefore, fusion-driven routing protocols for sensor networks cannot optimize over communication cost only -- fusion cost must also be accounted for. Towards this end, we design a novel routing algorithm, called Adaptive Fusion Steiner Tree (AFST), for energy efficient data gathering in sensor networks that jointly optimizes over the costs for data transmission and data fusion. Furthermore, AFST evaluates the benefit and cost of data fusion along information routes and adaptively adjusts whether fusion shall be performed. Analytically and experimentally, we show that AFST achieves better performance than existing algorithms including SLT, MFST, and SPT.
8291180
Grounding for Model Expansion in k-Guarded Formulas with Inductive Definitions
Mitchell and Ternovska [2005] proposed a constraint programming framework based on classical logic extended with inductive definitions. They formulate a search problem as the problem of model expansion (MX), which is the problem of expanding a given structure with new relations so that it satisfies a given formula. Their long-term goal is to produce practical tools to solve combinatorial search problems, especially those in NP. In this framework, a problem is encoded in a logic, an instance of the problem is represented by a finite structure, and a solver generates solutions to the problem. This approach relies on propositionalisation of high-level specifications, and on the efficiency of modern SAT solvers. Here, we propose an efficient algorithm which combines grounding with partial evaluation. Since the MX framework is based on classical logic, we are able to take advantage of known results for the so-called guarded fragments. In the case of k-guarded formulas with inductive definitions under a natural restriction, the algorithm performs much better than naive grounding by relying on connections between k-guarded formulas and tree decompositions.
13098192
On the impact of concurrent downloads
Concurrent downloads accelerate information access speed for individual Web users. The speed-up comes from multiple connections launched for one subject download, which leads to unfairness at user level. We study the impact of concurrent downloads on the network. Particularly, we investigate the fairness between users who employ different downloading concurrency. We also discuss how concurrent downloads affect the transient behavior of the network.
1409797
On the TCP-Friendliness of VoIP Traffic
Recently, some concerns have been raised regarding whether the rapid growth of the UDP traffic due to the Skype-like applications will throttle down regular TCP users because UDP flows are unresponsive to network congestion, i.e., UDP senders do not reduce their sending rates when congestion occurs in the network. However, most UDP based real time applications, such as Voiceover-IP (VoIP), drop out completely if the user perceived quality becomes unacceptable as the network congestion increases. This user back-off mechanism effectively reduces UDP traffic rate at the aggregated level when the network is congested. In this paper, we investigate the fairness issue between VoIP flows and TCP flows under different network environment. Our study explicitly takes into account both transport layer congestion control mechanism built-into TCP protocol stack and the self-adaptiveness of VoIP users. Various models are developed to characterize VoIP user back-off behaviors in response to call quality degradation resulted from packet loss and delay inside the network. The comparison between VoIP user back-off and TCP rate adaption shows that not only VoIP flows consume much less bandwidth than TCP flows, but also VoIP traffic is indeed very responsive to congestion when the network is overloaded.
7717376
Enriching speech recognition with automatic detection of sentence boundaries and disfluencies
Effective human and automatic processing of speech requires recovery of more than just the words. It also involves recovering phenomena such as sentence boundaries, filler words, and disfluencies, referred to as structural metadata. We describe a metadata detection system that combines information from different types of textual knowledge sources with information from a prosodic classifier. We investigate maximum entropy and conditional random field models, as well as the predominant hidden Markov model (HMM) approach, and find that discriminative models generally outperform generative models. We report system performance on both broadcast news and conversational telephone speech tasks, illustrating significant performance differences across tasks and as a function of recognizer performance. The results represent the state of the art, as assessed in the NIST RT-04F evaluation