Diploma Thesis DIP-2604

BibliographyHäuser, Philipp: Caching and Prefetching for Efficient Read Access to Multidimensional Wave Propagation Data on Disk.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Diploma Thesis No. 2604 (2007).
73 pages, german.
CR-SchemaD.4.2 (Storage Management)
H.3.3 (Information Search and Retrieval)
C.2.1 (Network Architecture and Design)
KeywordsNetwork Emulation Testbed; Caching Methods; Cache Hits; Compulsory Misses; Conflict Misses; Belady; OPT Algorithm; Optimal Cache Replacement
Abstract

The NET (Network Emulation Testbed) project has established an emulation system for computer networks at the Distributed Systems department of the University of Stuttgart. One purpose of the emulation system is the realistic emulation of MANETs (mobile ad hoc networks), including node mobility and resulting communication channel quality between nodes. Since the prediction of wave propagation is not possible in real-time, precomputed attenuation values between all locations in the 2D simulation grid are used. Since the size of the wave propagation data may exceed the available main memory, it is stored on secondary storage and read from disk periodically.

In this work, caching methods that take advantages of previously read wave propagation data are developed and evaluated. Clustering is a technique used for the formation of larger blocks of data in the cache. It is explained and evaluated. For the special case of deterministic node mobility, the sequence of the queries to the cache is known beforehand. For this case, an implementation for optimal cache replacement is developed. For indeterministic node mobility, replacement heuristics are developed and analysed. The connection between node mobility patterns, query distances and cache hits and misses is explained. The results are presented through graphs showing the cache hit and miss rates. Some examples for the distribution of queries in the cache are presented. The feasibility of using application specific knowledge within the current NET framework is evaluated. Connections between the movement of mobile nodes and the resulting cache queries for wave propagation data are examined.

The results of this work include the follwing findings: For clustering, i.e. the grouping of data into blocks, the cluster size must be carefully selected. Large clusters increase the amount of cache memory wasted on unused data, whereas small clusters create unnecessary I/O overhead. A precomputed optimal replacement order can be used for emulation scenarios with deterministic node mobility. Application knowledge, such as the position of roads, is helpful for anticipating motion. Anticipating node movements can help optimising the cache replacement. The knowledge is layered: The scenario is at the top layer, the wave propagation data with only the grid coordinates at the bottom layer. Nonlinear mathematical interpolation of the mobile nodes on the lowest knowledge level is not exact enough to yield acceptable results. Other approaches are to collect statistical data about the distribution of the nodes in a scenario over several runs or to determine hot spots in the motion patterns. Simple triangular interpolation of the mobile node positions on the lowest knowledge layer also does not yield acceptable results.

The content of this thesis is written in German language.

Full text and
other links
PDF (869064 Bytes)
PostScript (2623862 Bytes)
Access to students' publications restricted to the faculty due to current privacy regulations
CopyrightPhilipp Häuser
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Project(s)NET
Entry dateNovember 20, 2007
   Publ. Computer Science