TL;DR
This paper argues that "pushing" content proactively into Telco-CDNs, managed by ISPs, makes more sense than traditional "pull" caching. They introduce an efficient genetic algorithm on MapReduce to find near-optimal content placement, demonstrating it significantly alleviates network link congestion while maintaining comparable hit rates to LRU caching.
What Problem Does This Paper Address?
The explosion of HD video streaming traffic has led Internet Service Providers (ISPs) to consider deploying their own Content Delivery Networks (CDNs), termed "Telco-CDNs." Unlike traditional CDNs, Telco-CDNs are managed by the ISP, giving them control over both the content delivery overlay and the underlying network infrastructure. This unique position allows ISPs to optimize not just content delivery performance (like hit rates) but also the utilization of their network resources. The core challenge is how to best place video content within these Telco-CDNs to achieve this dual optimization. The paper re-opens the debate between "push" strategies (where content is proactively placed) and "pull" (caching) strategies, arguing that traditional caching is "blind" to the underlying network's needs.
Methods
The paper proposes a novel approach for content placement in Telco-CDNs:
- Genetic Algorithm (GA) for Placement: The core of their solution is a genetic algorithm designed to solve the k-Product Capacitated Facility Location Problem (k-PCFLP). This algorithm models content placement as finding the optimal locations for video chunks across a set of repositories.
- MapReduce Implementation: To handle the large scale of Telco-CDNs, the GA is implemented on the MapReduce framework. This parallelization allows for efficient computation of near-optimal solutions on distributed systems.
- Fitness Function via Minimum Cost Maximum Flow (MCMF): The fitness function of the GA, which evaluates the quality of a given placement, is formulated as a Minimum Cost Maximum Flow problem. This allows for the optimal assignment of users to repositories, considering both content availability and repository capacity.
- Traffic Engineering Integration: A key innovation is the integration of traffic engineering costs into the optimization problem. By overweighting the service cost of links leading to the main CDN points-of-presence (PoPs), the algorithm penalizes misses and encourages solutions that better utilize the ISP's internal network.
Datasets
The paper uses real traces from a national Video-on-Demand (VoD) service provided by Orange, a major European Telco. The dataset includes:
- Over 700,000 download requests.
- Data from over 20,000 end-users.
- Geographical distribution across 13 regions.
This dataset is used to simulate a Telco-CDN scenario and evaluate the proposed strategies.
Key Insights and Ideas
- Telco-CDNs are Different: The fundamental difference between traditional CDNs and Telco-CDNs is the ISP's control over the underlying network. This allows for a broader optimization goal that includes network traffic management, not just content delivery metrics.
- Push Strategy Makes Sense for ISPs: While traditional caching is simple and effective for hit rates, a proactive "push" strategy, when optimized, can significantly improve network utilization and reduce congestion on critical links.
- GA on MapReduce is Feasible: The paper demonstrates that a complex optimization problem like content placement can be efficiently solved using a parallelized genetic algorithm on a MapReduce framework, making it practical for large-scale Telco-CDN deployments.
- Traffic Engineering is Crucial: Integrating traffic engineering costs into the placement decision is key. By penalizing reliance on external PoPs, the algorithm incentivizes solutions that leverage the ISP's internal infrastructure more effectively.
- Recommendation Accuracy Matters: The performance of the push strategy is sensitive to the accuracy of user request predictions. While perfect prediction yields the best results, even realistic predictions can lead to significant improvements over traditional caching.
Key Results
- Comparable Hit Rates: The proposed quasi-optimal placement algorithm achieves hit rates comparable to LRU caching.
- Significant Network Cost Reduction: The push strategy, particularly with near-optimal placement, reduces the overall network cost (normalized overall cost) by up to 1.8 times compared to LRU caching.
- Alleviated Link Congestion: The push strategy significantly alleviates the workload on troubled links (e.g., over-used links) by intelligently distributing content and utilizing internal network paths.
- Efficient Computation: The GA implementation on MapReduce can converge within 12 hours for a population of 500 individuals over 350 generations, demonstrating the feasibility of daily or frequent re-placement.
- Impact of Prediction Accuracy: The performance of the push strategy is sensitive to recommendation accuracy. Substituting incorrect videos has a larger negative impact than substituting incorrect requesters.
Limitations and Future Work
- Limitations:
- The paper acknowledges that the evaluation is based on a specific network topology and a single VoD service.
- The evaluation process itself is noted as time-consuming, suggesting room for optimization.
- The study uses a "warm-up" period for prediction, implying that real-time adaptation might be more complex.
- Future Work:
- Evaluating the algorithm on more realistic and complex network topologies.
- Further parallelization and optimization of the evaluation process within the PGA.
- Developing an online version of the algorithm for real-time content placement.
- Investigating the impact of different traffic engineering policies beyond simple cost weighting.
Summary updated