טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentShaul Cemel
SubjectSimulation and Analysis of Growing Half- Balls
DepartmentDepartment of Industrial Engineering and Management
Supervisors Full Professor Kutten Shay
Dr. Amitabh Trehan
Full Thesis textFull thesis text - English Version


Abstract

This study aims to simulate algorithms that bear similarity to those of Bar Yehuda et al. from their paper ‘Growing Half-Balls: Minimizing Storage and Communication Costs in CDNs’ [ICALP 2012], as well as other similar algorithms. The idea is to study the way they behave ‘in practice’. In this study, we mainly cover three algorithms that deal with the content distribution problem: mod-Approx-Line (modified Approx-Line), mod-Partial-Approx-Grid, and mod-Allocate. mod-Approx-Line is an intuitive, simple, 3-approximation algorithm for movie allocation in the line network. mod-Partial-Approx-Grid is an approximation algorithm for the grid network. mod-Allocate is a competitive online algorithm for general networks. In order to simulate the algorithms, this study also aims at improving an existing simulator, called ‘GraphSimulation’ by Yifat Golan 2009, which was conducted at the Technion - Israel Institute of Technology. By improving the existing simulator, it will be possible (and easy) to collect statistics about large inputs (e.g., large networks and long lists of requests). The main contribution of our study is to implement these algorithms as well as add an Analyzer and a logging capability. The Analyzer allows the user to simulate algorithms without visualization. We emphasize that the algorithms implemented are not exactly those from the original papers, but rather modified algorithms whose performance is expected to be less good in that their storage requirements might be higher. Nevertheless, through comprehensive simulations, it can be seen that the modified algorithms still substantially reduce the total cost of movie distribution. Algorithm Approx-Line implemented during this study is at least 70% less costly than a random algorithm on a line network (see Section 6.4) and Algorithm Partial-Approx-Grid is at least 50% less costly than a random algorithm on a grid network (see Section 6.8). Interestingly, when dealing with an increased number of user requests, there seems to be a definite advantage of applying the modified Algorithm Allocate in both cases where requests are either known or unknown in advance.