M.Sc Student | Shaul Cemel |
---|---|

Subject | Simulation and Analysis of Growing Half- Balls |

Department | Department of Industrial Engineering and Management |

Supervisors | Full Professor Kutten Shay |

Dr. Amitabh Trehan | |

Full Thesis text |

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.