טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentRappaport Assaf
SubjectApproximation Algorithms for Soft-Capacitated Connected
Facility Location Problems
DepartmentDepartment of Computer Science
Supervisor Professor Dan Raz
Full Thesis textFull thesis text - English Version


Abstract

In recent years, companies such as eBay, Facebook, Google, Microsoft, and Yahoo! have made large investments in massive data centers supporting cloud services. These data centers are becoming the hosting platform for a wide spectrum of composite applications with an increasing trend towards more communication intensive applications. As a result, the bandwidth usage within and between data centers is rapidly growing.


Data centers placement is a challenging set of optimization problems where the goal is to optimally place the applications and their related data over the available infrastructure. Unlike traditional facility location problems, in our case data is continuously updated, and the cost associated with this update increases with the number of data replica and the network distance between them.


We model this problem as a soft-capacitated connected facility location problem, which is NP-Hard in the general case. We present the first deterministic constant approximation algorithm for this problem and show, using extensive simulations and realistic data center and network topology, that our algorithm provides practically good placement decisions.