Abstract
This paper introduces the Evolution-Based Hybrid Algorithm (EBHA), a dynamic caching scheme designed for mobile base stations to optimize the delivery of streaming media. Unlike traditional static algorithms, EBHA utilizes genetic algorithms to evolve cache replacement strategies based on access frequency, recency, and object size. Simulation results indicate that EBHA consistently outperforms standard methods like Least Recently Used (LRU) and Least Frequently Used (LFU), providing a scalable solution for the "World Wide Web for Wireless" (W4).
Introduction
In the mid-2000s, the rapid rise of multimedia content posed a significant challenge for mobile networks. Early mobile devices suffered from extremely limited local storage, preventing effective client-side caching. Consequently, base stations became critical intermediaries for content delivery.
Traditional caching algorithms, such as LRU or LFU, rely on fixed rules that often fail to account for the complex relationships between file size, access recency, and request frequency. When a base station fails to serve a request from its cache, it must fetch data from a remote server, leading to increased latency and network congestion. There was a clear need for a scalable, adaptive caching scheme capable of learning optimal strategies for diverse environments.
Methodology: The Evolution-Based Hybrid Algorithm (EBHA)
The core contribution of this research is the Evolution-Based Hybrid Algorithm (EBHA). Rather than employing a hard-coded replacement rule, EBHA uses a scoring function to evaluate cache blocks based on three parameters:
- ReqNum ($f$): Frequency of access.
- Count ($r$): Recency (time since last access).
- Size ($s$): Physical size of the media object.
The weights for these parameters are determined through an evolutionary process. The system maintains a population of "Individuals"—sets of parameter weights—and applies a genetic algorithm featuring crossover and mutation. This allows the system to discover the most effective weights for current request patterns. The paper details three variants:
- EBHA-1: A deterministic approach replacing the block with the minimum calculated weight.
- EBHA-PT: A probabilistic approach inspired by simulated annealing, using a "temperature" parameter to determine replacement likelihood.
- EBHA-P: A threshold-based approach that replaces blocks only when their weight falls below a specific constant.
Experimental Setup
The performance of EBHA was evaluated through a controlled simulation environment. This setup allowed for stress-testing under various conditions:
- Popularity Model: A Zipf distribution with an alpha value of 0.47 was used to model web popularity.
- Media Library: 500 objects with sizes ranging uniformly from 1MB to 10MB.
- Scale: Simulations spanned 50,000 seconds, encompassing roughly 4,000 requests.
- Cache Capacity: Varied between 10% and 30% of the total media data space.
Results and Analysis
The researchers evaluated the system using the Number Hit Ratio (NHR), representing the percentage of satisfied requests, and the Byte Hit Ratio (BHR), measuring saved data traffic.
As shown in the results, all EBHA variants consistently outperformed LFU, LRU, and the FSR (Frequency, Size, and Recentness) scheme. Key insights include:
- Adaptability: The evolutionary approach allows the cache to dynamically prioritize either small files (to maximize hit count) or large files (to minimize bandwidth usage) as needed.
- Performance in Medium Popularity: While most algorithms perform similarly when content popularity is highly skewed, EBHA provides a substantial performance boost in the "medium popularity" range typical of real-world data.
- Robustness: EBHA-PT proved particularly effective in handling irregular request patterns and sudden spikes in new content by avoiding local optima through its probabilistic replacement mechanism.
Conclusion
The EBHA framework demonstrates that an evolutionary approach to cache management can significantly improve performance in mobile data access scenarios. By treating caching strategies as evolving entities, the system achieves superior scalability and adaptability compared to traditional static methods. Future research will explore cooperative caching between neighboring base stations and the integration of more advanced machine learning techniques to further refine request prediction.
Summary updated