טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentRam Roni
SubjectEfficient Distribution of Email Messages
DepartmentDepartment of Computer Science
Supervisor Professor Dan Raz


Abstract

This research aims at making the process of distributing email messages to a (possibly large) list of recipients efficient. By minimizing the communication cost of sending email messages, we achieve both a better response time and a reduction of the network's load. Our goal is to minimize this cost by placing email distribution centers in the network.


We formulate a model that captures this scenario, and based on this model, we define the email message routing and distribution centers placement problems. The email routing problem deals with finding an optimal route for an email message sent to a list of destination addresses by using the distribution centers placed in the network. The distribution centers placement problem deals with finding an optimal placement of a given number of distribution centers in the network. In order to understand the different aspects of the problems, we first study a simple version of the problems in which the distribution centers are limited. Then we turn to study the more general cases in which the distribution centers are placed in a hierarchical structure. We show that in general these problems are NP-hard, and present optimal algorithms based on dynamic programming for the special case of tree networks.


We experimentally study the effects of our algorithms on real networks by simulating them on Internet like topologies and simulated data. Our results indicate that a small number of distribution centers is sufficient to significantly reduce the communication cost. Furthermore, there exists a threshold for which placing more distribution centers in a network will not reduce the communication cost. We also compare our algorithms against several heuristics and report on their relative performance.