אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

Data centers are becoming the hosting platform for a wide spectrum of composite applications. In recent years, large investments have been made in massive data centers supporting cloud services, by companies such as eBay, Facebook, Google, Microsoft, and Yahoo!. With an increasing trend towards global and more communication intensive applications, the bandwidth usage within and between data centers is rapidly growing. The placement of the data used by these global applications presents a challenging optimization problem, involving several factors. We study a network design problem that combines facility location and connectivity problems. Consider an email application that uses on an authentication service, and consider the problem of placing replicas of an object (e.g., the authentication service) at multiple locations in the Cloud. Replica placement deals with the actual number and network location of the replicas. Clearly, we would like to minimize the network distance between an application server in a data center and the closest replica containing the desired content and thus having more replicas helps. On the other hand, having more replicas is more expensive so we need to model the cost and the benefit in a way that will allow us to make the appropriate decisions regarding the number and the network locations of the replicas. This problem is strongly related to a family of optimization problems generally referred to as facility location problems. As most of the existing algorithms neglect the cost of keeping the replicas across the network up to date, we believe that considering this factor can lead to better realistic solutions. A replica must be synchronized with the original content server in order to provide reliable and precise response to the client requests. The synchronization traffic across the network depends on the number of replicas deployed in the network, the topology of the distributed update and the rate of updates in the content of the server. Moreover, we extend our model by adding capacity constraint for each replica. We can model the scenario above as a Soft-Capacitated Connected Facility Location Problem which is NP-Hard in the general case. In this work we introduce a constant approximation algorithm for this problem and study its applicability in the Cloud data placement paradigm.