Search

This paper proposes a cluster-based peer-to-peer system, called PeerCluster, for sharing data over the Internet. In PeerCluster, all participant computers are grouped into various interest clusters, each of which contains computers that have the same interests. The intuition behind the system design is that by logically grouping users interested in similar topics together, we can improve query efficiency. To efficiently route and broadcast messages across/within interest clusters, a hypercube topology is employed. In addition, to ensure that the structure of the interest clusters is not altered by arbitrary node insertions/deletions, we have devised corresponding JOIN and LEAVE protocols. The complexities of these protocols are analyzed. Moreover, we augment PeerCluster with a system recovery mechanism to make it robust against unpredictable computer/network failures. Using an event-driven simulation, we evaluate the performance of our approach by varying several system parameters. The experimental results show that PeerCluster outperforms previous approaches in terms of query efficiency, while still providing the desired functionality of keyword-based search. [ABSTRACT FROM AUTHOR]

In a mobile computing environment, the combined use of broadcast and on-demand channels can utilize the bandwidth effectively for data dissemination. We explore in this paper the problem of dynamic data and channel allocation with the number of communication channels and the number of data items given. We first derive the analytical models of the average access time when the data items are requested through the broadcast and on-demand channels. Then, we transform this problem into a guided search problem. In light of the theoretical properties derived, we devise algorithm SOM to obtain the optimal allocation of data and channels. Algorithm SOM is a composite algorithm which will cooperate with 1) a search strategy and 2) a broadcast program generation algorithm. According to the analytical mode, we devise scheme BIS-Incremental on the basis of algorithm SOM, which is able to obtain solutions of high quality efficiently by employing binary interpolation search. In essence, scheme BIS-Incremental is guided to explore the search space with higher likelihood to be the optimal first, thereby leading to an efficient and effective search. It is shown by our simulation results that the solution obtained by scheme BIS-Incremental is of very high quality and is in fact very close to the optimal one. A sensitivity study on several parameters, including the number of data items and the number of communication channels, is conducted. The experimental results show that scheme BIS-Incremental is of very good scalability, which is particularly important for its practical use in a mobile computing environment. [ABSTRACT FROM AUTHOR]

Web caching and Web prefetching are two important techniques used to reduce the noticeable response time perceived by users. Note that by integrating Web caching and Web prefetching, these two techniques can complement each other since the Web caching technique exploits the temporal locality, whereas Web prefetching technique utilizes the spatial locality of Web objects. However, without circumspect design, the integration of these two techniques might cause significant performance degradation to each other. In view of this, we propose in this paper an innovative cache replacement algorithm, which not only considers the caching effect in the Web environment, but also evaluates the prefetching rules provided by various prefetching schemes. Specifically, we formulate a normalized profit function to evaluate the profit from caching an object (i.e., either a nonimplied object or an implied object according to some prefetching rule). Based on the normalized profit function devised, we devise an innovative Web cache replacement algorithm, referred to as Algorithm IWCP (standing for the Integration of Web Caching and Pre fetching). Using an event-driven simulation, we evaluate the performance of Algorithm IWCP under several circumstances. The experimental results show that Algorithm IWCP consistently outperforms the companion schemes in various performance metrics. [ABSTRACT FROM AUTHOR]

In this paper, we devise data allocation algorithms that can utilize the knowledge of user moving patterns for proper allocation of shared data in a mobile computing system. By employing the data allocation algorithms devised, the occurrences of costly remote accesses can be minimized and the performance of a mobile computing system is thus improved. The data allocation: algorithms for shared data, which are able to achieve local optimization and global optimization, are developed. Local optimization refers to the optimization that the likelihood of local data access by an individual mobile user is maximized whereas global optimization refers to the optimization that the likelihood of local data access by all mobile users is maximized. Specifically, by exploring the features of local optimization and global optimization, we devise algorithm SD-local and algorithm SD-global to achieve local optimization and global optimization, respectively. In general, the mobile users are divided into two types, namely, frequently moving users and infrequently moving users. A measurement, called closeness measure which corresponds to the amount of the intersection between the set of frequently moving user patterns and that of infrequently moving user patterns, is derived to assess the quality of solutions provided by SD-local and SD-global. Performance of these data allocation algorithms is comparatively analyzed. From the analysis of SD-local and SD-global, it is shown that SD-local favors infrequently moving users whereas SD-global is good for frequently moving users. The simulation results show that the knowledge obtained from the user moving patterns is very important in devising effective data allocation algorithms which can lead to prominent performance improvement in a mobile computing system. [ABSTRACT FROM AUTHOR]

In a mobile computing system, as users move to a new service area, the new server is usually considered to take over the execution of running programs for mobile users from the previous server so as to reduce the communication overhead of a mobile system. This procedure is referred to as service handoff. Note that when service handoff occurs, the new server will lose its advantage for cache access. To remedy this, we explore in this paper several cache retrieval schemes to improve the efficiency of cache retrieval. In particular, we analyze the impact of using a coordinator buffer to improve the overall performance of cache retrieval. Moreover, in light of the properties of transactions (i.e., temporal locality of data access among transactions), we devise a Dynamic and Adaptive cache Retrieval scheme (DAR) that can utilize proper cache methods according to some specific criteria to deal with the service handoff situation in a mobile computing environment. Performance of these cache retrieval schemes is analyzed and a system simulator is developed to validate our results. We devise a systematic procedure for determining the optimal operating points of DAR. Our experimental results show that by adaptively adopting the advantages of different cache retrieval methods, DAR significantly outperforms other schemes and is particularly effective for a mobile computing environment. [ABSTRACT FROM AUTHOR]

Recent technology advances in mobile networking have ushered in a new era of personal communication. Users can ubiquitously access the Internet via many emerging mobile appliances, such as portable notebooks, personal digital assistants (PDAs), and WAP-enabled cellular phones. While the transcoding proxy is attracting an increasing amount of attention in this environment, it is noted that new caching strategies are required for these transcoding proxies. We propose, in this paper, an efficient cache replacement algorithm for transcoding proxies. Specifically, we formulate a generalized profit function to evaluate the profit from caching each version of an object. This generalized profit function explicitly considers several new emerging factors in the transcoding proxy and the aggregate effect of caching multiple versions of the same object. It is noted that the aggregate effect is not simply the sum of the costs of caching individual versions of an object, but rather, depends on the transcoding relationship among these versions. The notion of a weighted transcoding graph is devised to evaluate the corresponding aggregate effect efficiently. Utilizing the generalized profit function and the weighted transcoding graph, we propose, in this paper, an innovative cache replacement algorithm for transcoding proxies. In addition, an effective data structure is designed to facilitate the management of the multiple versions of different objects cached in the transcoding proxy. Using an event-driven simulation, it is shown that the algorithm proposed consistently outperforms companion schemes in terms of the delay saving ratios and cache hit ratios. [ABSTRACT FROM AUTHOR]