Exploiting client caches to build large Web caches

New demands brought by the continuing growth of the Internet will be met in part by more effective and comprehensive use of caching. This paper proposes to exploit client browser caches in the context of cooperative proxy caching by constructing the client caches within each organization (e.g., corporate networks) as a peer-to-peer (P2P) client cache. Via trace-driven simulations we evaluate the potential performance benefit of cooperative proxy caching with/without exploiting client caches. We show that exploiting client caches in cooperative proxy caching can significantly improve performance, particularly when the size of individual proxy caches is limited compared to the universe of Web objects. We further devise a cooperative hierarchical greedy-dual replacement algorithm (Hier-GD), which not only provides some cache coordination but also utilizes client caches. Through Hier-GD, we explore the design issues of how to exploit client caches in cooperative proxy caching to build large Web caches. We show that Hier-GD is technically practical and can potentially improve the performance of cooperative proxy caching by utilizing client caches.

OCS: An effective caching scheme for video streaming on overlay networks

Video streaming is vital for many important applications such as distance learning, digital video libraries, and movie-on-demand. Since video streaming requires significant server and networking resources, caching has been used to reduce the demand on these resources. In this paper, we propose a novel collaboration scheme for video caching on overlay networks, called Overlay Caching Scheme (OCS), to further minimize service delays and loads placed on an overlay network for video streaming applications. OCS is not a centralized nor a hierarchical collaborative scheme. Despite its design simplicity, OCS effectively uses an aggregate storage space and capability of distributed overlay nodes to cache popular videos and serve nearby clients. Moreover, OCS is light-weight and adaptive to clients’ locations and request patterns. We also investigate other video caching techniques for overlay networks including both collaborative and non-collaborative ones. Compared with these techniques on topologies inspired from actual networks, OCS offers extremely low average service delays and approximately half the server load. OCS also offers smaller network load in most cases in our study.

Caching collaboration and cache allocation in peer-to-peer video systems

Providing scalable video services in a peer-to-peer (P2P) environment is challenging. Since videos are typically large and require high communication bandwidth for delivery, many peers may be unwilling to cache them in whole to serve others. In this paper, we address two fundamental research problems in providing scalable P2P video services: (1) how a host can find enough video pieces, which may scatter among the whole system, to assemble a complete video; and (2) given a limited buffer size, what part of a video a host should cache and what existing data should be expunged to make necessary space. We address these problems with two new ideas: Cell caching collaboration and Controlled Inverse Proportional (CIP) cache allocation. The Cell concept allows cost-effective caching collaboration in a fully distributed environment and can dramatically reduce video lookup cost. On the other hand, CIP cache allocation challenges the conventional caching wisdom by caching unpopular videos in higher priority. Our approach allows the system to retain many copies of popular videos to avoid creating hot spots and at the same time, prevent unpopular videos from being quickly evicted from the system. We have implemented a Gnutella-like simulation network and use it as a testbed to evaluate the proposed technique. Our extensive study shows convincingly the performance advantage of the new scheme.

Throughput optimization for video streaming proxy servers based on video staging

A video streaming proxy server needs to handle hundreds of simultaneous connections between media servers and clients. Inside, every video arrived at the server and delivered from it follows a specific arrival and delivery schedule. While arrival schedules compete for incoming network bandwidth, delivery schedules compete for outgoing network bandwidth. As a result, a proxy server has to provide sufficient buffer and disk cache for storage, together with memory space, disk space and disk bandwidth. In order to optimize the throughput, a proxy server has to govern the usage of these resources. In this paper, we first analyze the property of a traditional smoothing algorithm and a video staging algorithm. Then we develop, based on the smoothing algorithm, a video staging algorithm for video streaming proxy servers. This algorithm allows us to devise an arrival schedule based on the delivery schedule. Under this arrival and delivery schedule pair, we can achieve a better resource utilization rate gracefully between different parameter sets. It is also interesting to note that the usage of the resources such as network bandwidth, disk bandwidth and memory space becomes interchangeable. It provides the basis for inter-resource scheduling to further improve the throughput of a video streaming proxy server system.

Optimized scalable cache management for video streaming system

An important research issue in video streaming is how to efficiently utilize the network resources to provide clients instant access to multiple video objects. Caching strategy and transmission scheme are the two essential points inside the video streaming framework. Recent research efforts on them are not sufficient due to their inflexible support for scalable encoded video streams and heterogeneous requests from clients. In this paper, we propose an optimized caching strategy (OCS) and a scalable transmission scheme (STS) for scalable coded video streaming. By exploring the characteristics of video streaming workload and system design objectives, OCS and STS work efficiently to minimize both network bandwidth cost and user access latency. Firstly, we analyze the caching problem for the proxy-assisted video streaming system and derive a maneuverable caching scenario. Secondly, we develop an efficient transmission scheme for scalable coded videos. Thirdly, we formulate a multi-objective optimization model with closed-form expressions to obtain the optimized caching strategy. Finally, with designed algorithms, an excellent compromise between two competing objectives (minimizing the bandwidth cost and the access latency) is achieved. We start our evaluation by studying the optimized caching strategy for a single video object. Then we apply the strategy to multiple video objects and illustrate the tradeoff between the optimization objectives. Our evaluation results show that compared with other caching strategies, the proposed optimized scalable caching strategy can achieve a significant reduction in bandwidth cost with even a small proxy cache size. Meanwhile, the best performance (in terms of bandwidth cost) is obtained together with the proposed scalable batch-patching transmission scheme.

A structured P2P network based on the small world phenomenon

In this paper, we propose a new structured P2P overlay network, named SW-Uinta(small-world). In order to reduce the routing latency, we firstly construct the Uinta network in which both physical characteristics of network and data semantic are considered. Furthermore, based on Uinta, a nondeterministic caching strategy is employed to allow for poly-logarithmic search time while having only a constant cache size. Compared with the deterministic caching strategy proposed by previous P2P systems, the nondeterministic caching strategy can reduce communication overhead for maintaining the routing cache table. Cache entries in the cache table of peer nodes can be updated by subsequent queries rather than only by running stabilization periodically. In the following, a novel cache replacement scheme, named the SW cache replacement scheme, is used to improve lookup performance, which has proved to satisfy the small-world principle. So we call this network SW-Uinta(small-world). After that, according to the theoretical analysis, it can be proved that SW-Uinta(small-world) can get O((log ² N)/k) search time with O(k) cache size. Lastly, the performance of SW-Uinta(small-world) is compared with those of other structured P2P networks such as Chord and Uinta. It shows that SW-Uinta(small-world) can achieve improved object lookup performance and reduce maintenance cost.

Periodic broadcast with dynamic server selection

Service replication is an effective way to address resource requirements and resource availability problem. Dynamic service selection enables clients to choose a server offering the best performance. Proper server selection is especially important for video streaming over the Internet due to its high bandwidth requirements. However, given the length of a typical video transmission, the server priorly selected may no longer be an optimal one for the duration of the entire transmission. More importantly, a server may fail during the transmission of a video. In this paper we examine the possibility of switching to another server during an on-going transmission for Periodic Broadcast schemes. Due to the timing requirements typical for Periodic Broadcast the server switch may cause playback disruptions. We analyze the magnitude of the problem and propose an easy to implement solution. We define the criteria, additional to the bandwidth availability for example, according to which a new server should be selected. The client is also required to delay its playback by the amount of time bounded by the server transmission offset. In addition, we propose an alternative method to ensure uninterrupted playback that relies on proxy caching. Simulation results show that our approach can significantly reduce the likelihood of playback disruptions.

Cache oblivious algorithms for nonserial polyadic programming

The nonserial polyadic dynamic programming algorithm is one of the most fundamental algorithms for solving discrete optimization problems. Although the loops in the nonserial polyadic dynamic programming algorithm are similar to those in matrix multiplication, the available automatic optimization techniques have little effect on this imperfect loop because of nonuniform data dependencies. In this paper, we develop algorithmic optimizations to improve the cache performance of the nonserial polyadic dynamic programming algorithm. Our algorithmic transformation takes advantage of the cache oblivious method by relaxing some dependencies in the standard iterative version. Based on the ideal cache model of the cache oblivious algorithm, the approximate bound of cache misses is given by . We also found that the optimized algorithm with the cache oblivious approach is more sensitive to conventional optimization techniques such as tiling. Experimental results on several platforms show that the optimized algorithms improve the cache performance and achieves speedups of 2–10 times.

The 2007 IEEE CEC simulated car racing competition

This paper describes the simulated car racing competition that was arranged as part of the 2007 IEEE Congress on Evolutionary Computation. Both the game that was used as the domain for the competition, the controllers submitted as entries to the competition and its results are presented. With this paper, we hope to provide some insight into the efficacy of various computational intelligence methods on a well-defined game task, as well as an example of one way of running a competition. In the process, we provide a set of reference results for those who wish to use the simplerace game to benchmark their own algorithms. The paper is co-authored by the organizers and participants of the competition.

---

Interacting with mobile services: an evaluation of camera-phones and visual tags

We present a study of using camera-phones and visual-tags to access mobile services. Firstly, a user-experience study is described in which participants were both observed learning to interact with a prototype mobile service and interviewed about their experiences. Secondly, a pointing-device task is presented in which quantitative data was gathered regarding the speed and accuracy with which participants aimed and clicked on visual-tags using camera-phones. We found that participants’ attitudes to visual-tag-based applications were broadly positive, although they had several important reservations about camera-phone technology more generally. Data from our pointing-device task demonstrated that novice users were able to aim and click on visual-tags quickly (well under 3 s per pointing-device trial on average) and accurately (almost all meeting our defined speed/accuracy tradeoff of 6% error-rate). Based on our findings, design lessons for camera-phone and visual-tag applications are presented.

---

Bayesian network based business information retrieval model

The quality of business information can significantly affect the operation level of enterprise. This paper analyses the problem of business information retrieval (BIR). A Bayesian Network Based business information retrieval model (BN-BIRM) is proposed by means of Bayesian network (BN) and information retrieval (IR) theory and a method for query adaptation is presented. In this model the customized query requirement of enterprise (CQR) is expressed in terms of the predefined illustrative documents related to business domain. The similarities between the documents and the query are evaluated with the conditional probabilities among the nodes in the BN. In the experiments, BN-BIRM is compared with the Belief Network model based on vector space model (VSM) ranking strategy and the Inference Network model based on TF-IDF ranking strategy. The experimental results show that BN-BIRM is effective for collecting business information on a large scale.

RRSi: indexing XML data for proximity twig queries

Twig query pattern matching is a core operation in XML query processing. Indexing XML documents for twig query processing is of fundamental importance to supporting effective information retrieval. In practice, many XML documents on the web are heterogeneous and have their own formats; documents describing relevant information can possess different structures. Therefore some “user-interesting” documents having similar but non-exact structures against a user query are often missed out. In this paper, we propose the RRSi, a novel structural index designed for structure-based query lookup on heterogeneous sources of XML documents supporting proximate query answers. The index avoids the unnecessary processing of structurally irrelevant candidates that might show good content relevance. An optimized version of the index, oRRSi, is also developed to further reduce both space requirements and computational complexity. To our knowledge, these structural indexes are the first to support proximity twig queries on XML documents. The results of our preliminary experiments show that RRSi and oRRSi based query processing significantly outperform previously proposed techniques in XML repositories with structural heterogeneity.

Parallel Lagrange interpolation on <Emphasis Type="Italic">k</Emphasis>-ary <Emphasis Type="Italic">n</Emphasis>-cubes with maximum channel utilization

This paper proposes an efficient parallel algorithm for computing Lagrange interpolation on k-ary n-cube networks. This is done using the fact that a k-ary n-cube can be decomposed into n link-disjoint Hamiltonian cycles. Using these n link-disjoint cycles, we interpolate Lagrange polynomial using full bandwidth of the employed network. Communication in the main phase of the algorithm is based on an all-to-all broadcast algorithm on the n link-disjoint Hamiltonian cycles exploiting all network channels, and thus, resulting in high-efficiency in using network resources. A performance evaluation of the proposed algorithm reveals an optimum speedup for a typical range of system parameters used in current state-of-the-art implementations.

On aggregate available bandwidth in many-to-one data transfer—modeling and applications

This work investigates the modeling of aggregate available bandwidth in multi-sender network applications. Unlike the well-established client–server model, where there is only one server sending the requested data, the available bandwidth of multiple senders when combined together does exhibit consistent properties and thus can be modeled and estimated. Through extensive experiments conducted in the Internet this work proposed to model the aggregate available bandwidth using a normal distribution and then illustrates its application through a hybrid download-streaming algorithm and a playback-adaptive streaming algorithm for video delivery under different bandwidth availability scenarios. This new multi-source bandwidth model opens a new way to provide probabilistic performance guarantee in best-effort networks such as the Internet, and is particularly suitable for the emerging peer-to-peer applications, where having multiple sources is the norm rather than the exception.

Inverse multi-objective robust evolutionary design

In this paper, we present an Inverse Multi-Objective Robust Evolutionary (IMORE) design methodology that handles the presence of uncertainty without making assumptions about the uncertainty structure. We model the clustering of uncertain events in families of nested sets using a multi-level optimization search. To reduce the high computational costs of the proposed methodology we proposed schemes for (1) adapting the step-size in estimating the uncertainty, and (2) trimming down the number of calls to the objective function in the nested search. Both offline and online adaptation strategies are considered in conjunction with the IMORE design algorithm. Design of Experiments (DOE) approaches further reduce the number of objective function calls in the online adaptive IMORE algorithm. Empirical studies conducted on a series of test functions having diverse complexities show that the proposed algorithms converge to a set of Pareto-optimal design solutions with non-dominated nominal and robustness performances efficiently.

---

Methods for quantitative usability requirements: a case study on the development of the user interface of a mobile phone

Quantitative usability requirements are a critical but challenging, and hence an often neglected aspect of a usability engineering process. A case study is described where quantitative usability requirements played a key role in the development of a new user interface of a mobile phone. Within the practical constraints of the project, existing methods for determining usability requirements and evaluating the extent to which these are met, could not be applied as such, therefore tailored methods had to be developed. These methods and their applications are discussed.

---

Timing predictability of cache replacement policies

Hard real-time systems must obey strict timing constraints. Therefore, one needs to derive guarantees on the worst-case execution times of a system’s tasks. In this context, predictable behavior of system components is crucial for the derivation of tight and thus useful bounds. This paper presents results about the predictability of common cache replacement policies. To this end, we introduce three metrics, evict, fill, and mls that capture aspects of cache-state predictability. A thorough analysis of the LRU, FIFO, MRU, and PLRU policies yields the respective values under these metrics. To the best of our knowledge, this work presents the first quantitative, analytical results for the predictability of replacement policies. Our results support empirical evidence in static cache analysis.

Proxy-assisted periodic broadcast for video streaming with multiple servers

Large scale video streaming over the Internet requires a large amount of resources such as server I/O bandwidth and network bandwidth. A number of video delivery techniques can be used to lower these requirements. Periodic broadcast by a central server combined with proxy caching offers a significant reduction of the aggregate network and server I/O bandwidth usage. However, the resources available to a single server are still limited. In this paper we propose a system with multiple geographically distributed servers. The problem of multiple servers for periodic broadcast is quite different from the problem of object location for multiple web servers. Multiple servers offer increased amount of resources and service availability and may potentially allow a further reduction of network bandwidth usage. On the other hand, the benefit of periodic broadcast mostly comes from high demand videos. With multiple servers holding a video, the demand of the video at each server is reduced. Therefore, it is a challenge to use multiple servers efficiently. We first analyze the dependence of the resource requirements on the number and locations of the servers. Based on the character of the function describing such a dependence, we formulate and solve the problem of video location and delivery, in a way that minimizes resource usage. We explore a trade-off between network and I/O bandwidth requirements. We evaluate our proposed solutions through a number of tests.

Semantic representation of multimedia content: Knowledge representation and semantic indexing

In this paper we present a framework for unified, personalized access to heterogeneous multimedia content in distributed repositories. Focusing on semantic analysis of multimedia documents, metadata, user queries and user profiles, it contributes to the bridging of the gap between the semantic nature of user queries and raw multimedia documents. The proposed approach utilizes as input visual content analysis results, as well as analyzes and exploits associated textual annotation, in order to extract the underlying semantics, construct a semantic index and classify documents to topics, based on a unified knowledge and semantics representation model. It may then accept user queries, and, carrying out semantic interpretation and expansion, retrieve documents from the index and rank them according to user preferences, similarly to text retrieval. All processes are based on a novel semantic processing methodology, employing fuzzy algebra and principles of taxonomic knowledge representation. The first part of this work presented in this paper deals with data and knowledge models, manipulation of multimedia content annotations and semantic indexing, while the second part will continue on the use of the extracted semantic information for personalized retrieval.

A coherent query language for XML

Text search engines are inadequate for indexing and searching XML documents because they ignore metadata and aggregation structure implicit in the XML documents. On the other hand, the query languages supported by specialized XML search engines are very complex. In this paper, we present a simple yet flexible query language, and develop its semantics to enable intuitively appealing extraction of relevant fragments of information while simultaneously falling back on retrieval through plain text search if necessary. Our approach combines and generalizes several available techniques to obtain precise and coherent results.