טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentPanman Evgeny
SubjectEfficient Data Collection Algorithm
DepartmentDepartment of Computer Science
Supervisor Professor Dan Raz


Abstract

The problem of collecting information from the nodes in a network, also called the convergecast problem, is a well studied problem in distributed computing. However, the commonly used distributed models do not take into account the computations delay at the nodes themselves. This delay may, in some cases, be significant with respect to the network delay. Thus, it is important to develop and analyze the performance of convergecast algorithms in a model that considers both the communication and computation delay.


Active Network is a network in which programs can be injected into the network and be executed in internal nodes. This new paradigm allows the introduction of new, more efficient network services.  One area that can benefit from these new services is the area of a network management. Managing a communication network is a complicated task that requires collecting information from the network nodes, analyzing the data, and taking proactive measures when needed. A basic component in any network management system is monitoring, or information collection.


In the presented work, we studied various ways to collect information efficiently in Active Networks.  To do so, we developed new algorithms for the convergecast problem and analyzed them under a recently introduced model that considers both the communication and computation delay.  We present efficient algorithms for collecting information both from paths and general networks.

For these algorithms we both provide theoretical analysis and study their practical expected performance via a simulations.  These algorithms can be also used in other distributed systems scenarios where the computation delay is significant with respect to the network delay.