Search

Information-Centric Networking (ICN) architecture leverages the network of caches’ idea to bring content closer to consumers to ultimately reduce the load on content servers and prevent unnecessary packet re-transmissions. Nevertheless, the performance of existing cache management schemes mainly developed for a single cache is inadequate for a network of caches. There are many factors such as data dependencies, data redundancy, the limited size of caches, poor replacement policies, and many other factors that negatively impact a network of caches. Besides, traffic correlation among different caches on the network influences the performance of the network of caches. One of the essential correlations is the edge filtering effect. In the presence of data redundancy, the edge filtering effect even becomes more severe. The cache filtering effect happens when all arriving requests inspect the first cache for data. Therefore, the subsequent caches in the network receive only those requests that could not find data (cache-miss) from the edge cache. In this paper, we propose Frozen-cache to mitigate the filtering effect. This policy repeatedly freezes content in a cache to allow subsequent caches to receive popular content. A lightweight coordinated scheme incorporated with Frozen-cache policy to cope with the data redundancy problem. Based on our experiments obtained from realistic scenarios, the Frozen-cache idea highly outperforms state of the art caching schemes. Depending on the network setup, this superiority varies from 25% to 700%.

We present a comprehensive study of the list update problem with locality of reference. More specifically, we present a combined theoretical and experimental study in which the theoretically proven and experimentally observed performance guarantees of algorithms match or nearly match. Firstly, we introduce a new model of locality of reference that closely captures the concept of runs. Using this model we develop refined theoretical analyses of popular list update algorithms. Secondly, we present an extensive experimental study in which we have tested the algorithms on traces from benchmark libraries. The theoretical and experimental bounds differ by just a few percent. Our new theoretical bounds are substantially lower than those provided by standard competitive analysis. It shows that the well-known Move-To-Front strategy exhibits the best performance. Its refined competitive ratio tends to 1 as the degree of locality increases. This confirms that Move-To-Front is the method of choice in practice. [ABSTRACT FROM AUTHOR]

It is well-established that input sequences for paging and list update have locality of reference. In this paper we analyze the performance of algorithms for these problems in terms of the amount of locality in the input sequence. We define a measure for locality that is based on Denning's working set model and express the performance of well known algorithms in terms of this parameter. This explicitly introduces parameterized-style analysis to online algorithms. The idea is that rather than normalizing the performance of an online algorithm by an (optimal) offline algorithm, we explicitly express the behavior of the algorithm in terms of two more natural parameters: the size of the cache and Denning's working set measure. This technique creates a performance hierarchy of paging algorithms which better reflects their experimentally observed relative strengths. It also reflects the intuition that a larger cache leads to a better performance. We also apply the parameterized analysis framework to list update and show that certain randomized algorithms which are superior to MTF in the classical model are not so in the parameterized case, which matches experimental results. [ABSTRACT FROM AUTHOR]

A critical problem to peer-to-peer video-on-demand (P2P VoD) systems is to provide efficient user interactivity support. In this paper, we study intra- and inter-video operations separately, aiming to exploit the locality of reference in user access patterns and reduce the latency of these VoD operations. We first introduce the concepts of available, request and delivered locality in intra-video user access patterns and prove that high available locality exists in different videos by both simulation and theoretical analysis. Moreover, with a relaxed definition of data chunk holder, intra-video locality can facilitate a high likelihood of a peer seeking within a video, finding a holder of the requested data among its neighbors. Exploiting this property, an aggressive cached publish scheme is designed to build shortcuts over the DHT network so as to reduce the lookup delay. This scheme may be simple but it is practical and easy to implement. Inter-video locality is exploited via learning association rules from the collective viewing history. A fast association rule learning algorithm is proposed to infer the relations between videos in a distributed manner based on partial knowledge. Both search and content prefetch are incorporated to achieve low inter-video jump delay with minimal overhead. Our simulations demonstrate that the proposed schemes can reduce the buffer and lookup delay for seeking within a video and provide an efficient prediction-based prefetch scheme for inter-video access. [ABSTRACT FROM PUBLISHER]

Abstract: It has been a formidable task to achieve efficiency and scalability for the alignment between two massive, conceptually similar ontologies. Here we assume, an ontology is typically given in RDF (Resource Description Framework) or OWL (Web Ontology Language) and can be represented by a directed graph. A straightforward approach to the alignment of two ontologies entails an computation by comparing every combination of pairs of nodes from given two ontologies, where denotes the average number of nodes in each ontology. Our proposed algorithm called Anchor-Flood algorithm, boasting of computation on the average, starts off with an anchor, a pair of “look-alike” concepts from each ontology, gradually exploring concepts by collecting neighboring concepts, thereby taking advantage of locality of reference in the graph data structure. It outputs a set of alignments between concepts and properties within semantically connected subsets of two entire graphs, which we call segments. When similarity comparison between a pair of nodes in the directed graph has to be made to determine whether two given ontologies are aligned or not, we repeat the similarity comparison between a pair of nodes, within the neighborhood pairs of two ontologies surrounding the anchor iteratively until the algorithm meets that “either all the collected concepts are explored, or no new aligned pair is found”. In this way, we can significantly reduce the computational time for the alignment. Moreover, since we only focus on segment-to-segment comparison, regardless of the entire size of ontologies, our algorithm not only achieves high performance, but also resolves the scalability problem in aligning ontologies. Our proposed algorithm reduces the number of seemingly-aligned but actually misaligned pairs. Through several examples with large ontologies, we will demonstrate the features of our Anchor-Food algorithm. [Copyright &y& Elsevier]

Abstract: In this work, we show that the submachine locality exposed by hierarchical bulk-synchronous computations can be efficiently turned into locality of reference on arbitrarily deep hierarchies. Specifically, we develop efficient schemes to simulate parallel programs written for the Decomposable BSP (a BSP variant which features a hierarchical decomposition into submachines) on the sequential Hierarchical Memory Model (HMM), which rewards the exploitation of temporal locality, and on its extension with block transfer, the BT model, which also rewards the exploitation of spatial locality. The simulations yield good hierarchy-conscious sequential algorithms from parallel ones, and provide evidence of the strict relation between submachine locality in parallel computation and locality of reference in the hierarchical memory setting. We also devise a generalization of the HMM result to the self-simulation of D-BSP augmented with hierarchical memory modules, which yields an interesting analog of Brent''s lemma, thus proving that the enhanced model features a seamless integration of memory and network hierarchies. [Copyright &y& Elsevier]

Abstract: Motivated by the fact that competitive analysis yields too pessimistic results when applied to the paging problem, there has been considerable research interest in refining competitive analysis and in developing alternative models for studying online paging. In this paper, we propose a new, simple model for studying paging with locality of reference. The model is closely related to Denning''s working set concept and directly reflects the amount of locality that request sequences exhibit. We use the page fault rate to evaluate the quality of paging algorithms, which is the performance measure used in practice. We develop tight or nearly tight bounds on the fault rates achieved by popular paging algorithms such as LRU, FIFO, deterministic Marking strategies and LFD. These bounds show that LRU is an optimal online algorithm, whereas FIFO and Marking strategies are not optimal in general. We present an experimental study comparing the page fault rates proven in our analyses to the page fault rates observed in practice. [Copyright &y& Elsevier]

This paper presents a new partitioned algorithm for LU decomposition with partial pivoting. The new algorithm, called the recursively partitioned algorithm, is based on a recursive partitioning of the matrix. The paper analyzes the locality of reference in the new algorithm and the locality of reference in a known and widely used partitioned algorithm for LU decomposition called the right-looking algorithm. The analysis reveals that the new algorithm performs a factor of Θ[This symbol cannot be presented in ASCII format] fewer I/O operations (or cache misses) than the right-looking algorithm, where n is the order of the matrix and M is the size of primary memory. The analysis also determines the optimal block size for the right-looking algorithm. Experimental comparisons between the new algorithm and the right-looking algorithm show that an implementation of the new algorithm outperforms a similarly coded right-looking algorithm on six different RISC architectures, that the new algorithm performs fewer cache misses than any other algorithm tested, and that it benefits more from Strassen's matrix-multiplication algorithm. [ABSTRACT FROM AUTHOR]

Due to the widening gap between central processing unit speed and electromechanical disk performance, future virtual memory systems based on newer technologies will use devices such as extended semiconductor memory or solid-state disks as an intermediate stage in the memory hierarchy or as a replacement for secondary storage. These newer devices will have smaller access times relative to the main memory access time. The role of the virtual memory management system is to assign to main memory those pages of a program's virtual address space that are needed for current execution. To avoid excessively expensive page traffic, a program's memory allocation should be large enough to contain its most economical locality of reference. Too large a memory allocation, however, will needlessly increase space-time execution cost by allowing pages no longer needed to remain in main memory. The choice of a proper memory allocation depends on p, the ratio of secondary to primary memory access time. The memory allocation should be adjusted so that the space-time cost of retaining pages in memory is balanced against the space-time cost of removing pages and later transferring them in again. This paper analyzes some of the problems encountered in designing algorithms for managing virtual memory systems based on the newer technology secondary storage devices. [ABSTRACT FROM AUTHOR]

Many problems of block structure derive from the remote specification of parts of the local environment. An alternative to block structure is proposed, in which the local environment is described within each program module. Concise environment descriptions are made possible by creating a tree whose terminal nodes are declarations and whose intermediate nodes can represent all of their descendant terminal node declarations. The tree encompasses all of the data used by the program and can thus be thought of as the data structure for the entire program. Each intermediate node of the tree names an abstract data structure that is implemented from the data named in its descendant nodes. Top-down refinement of abstract data structures consists of creating descendant nodes, and terminates when all terminal nodes of the tree have been created. This activity occurs as a normal part of program development, along with the top-down refinement of program modules. The tree can be used in place of a symbol table as a referencing structure for compilation or interpretation. Compilation time will then increase linearly with the length of the program and the referencing structure can grow dynamically during compilation. [ABSTRACT FROM AUTHOR]

Paging (caching) is the problem of managing a two-level memory hierarchy in order to minimize the time required to process a sequence of memory accesses. In order to measure this quantity, which we refer to as the total memory access time, we define the system parameter miss penalty to represent the extra time required to access slow memory. We also introduce the system parameter page size. In the context of paging, miss penalty is quite large, so most previous studies of on-line paging have implicitly set miss penalty =∞ in order to simplify the model. We show that this seemingly insignificant simplification substantially alters the precision of derived results. For example, previous studies have essentially ignored page size. Consequently, we reintroduce the miss penalty and page size parameters to the paging problem and present a more accurate analysis of on-line paging (and caching). We validate using this more accurate model by deriving intuitively appealing results for the paging problem which cannot be derived using the simplified model. First, we present a natural, quantifiable definition of the amount of locality of reference in any access sequence. We also point out that the amount of locality of reference in an access sequence should depend on page size among other factors. We then show that deterministic and randomized marking algorithms such as the popular least recently used (LRU) algorithm achieve constant competitive ratios when processing typical access sequences which exhibit significant locality of reference; this represents the first competitive analysis result which (partially) explains why LRU performs as well as it is observed to in practice. Next, we show that finite lookahead can be used to obtain algorithms with improved competitive ratios. In particular, we prove that modified marking algorithms with sufficient lookahead achieve competitive ratios of 2. This is in stark contrast to the simplified model where lookahead cannot be used to obtain algorithms with improved competitive ratios. We conclude by using competitive analysis to evaluate the benefits of increasing associativity in caches. We accomplish this by specifying an algorithm and varying the system configuration rather than the usual process of specifying the system configuration and varying the algorithm. [ABSTRACT FROM AUTHOR]