טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentUnger Oren
SubjectOptimal Content location in IP Multicast Based Overlay
Networks
DepartmentDepartment of Electrical Engineering
Supervisor Professor Emeritus Israel Cidon


Abstract

Overlay networks architecture should support high-performance and high-scalability at low costs. This becomes more crucial when communication, storage costs as well as service latencies grow with the exploding amounts of data exchanged and with the size and span of the overlay network. For that end, multicast methodologies can be used to deliver content from regional servers to end users, as well as for the timely and economical synchronization of content among the distributed servers. Another important architectural problem is the efficient allocation of objects to servers to minimize storage, delivery and update costs.


In this work, we suggest a multicast based architecture and address the optimal allocation and replication of dynamic objects that are both consumed and updated. Our model network includes application servers which are potential storage points connected in the overlay network, consumers which are served using multicast and/or unicast traffic and media sources which update the objects using multicast communication. General costs are associated with distribution (download) and update traffic as well as the storage of objects in the servers.


Optimal object allocation algorithms for tree networks are presented with complexities of O(N) in case of multicast distribution and O(N2) in case of hybrid unicast/multicast distribution. A special case of the hybrid distribution problem automatically selects, for each user, between multicast and unicast distribution.


Using the techniques of the optimal tree algorithm we also present an efficient approximation algorithm for general networks in case of multicast only distribution.