N2 - The problem that this paper investigates, namely, optimization of overlay computing systems, follows naturally from growing need for effective processing and consequently, fast development of
various distributed systems. We consider an overlay-based computing system, i.e., a virtual computing system is deployed on the top of an existing physical network (e.g., Internet) providing connectivity between
computing nodes. The main motivation behind the overlay concept is simple provision of network functionalities (e.g., diversity, flexibility, manageability) in a relatively cost-effective way as well as regardless
of physical and logical structure of underlying networks. The workflow of tasks processed in the computing system assumes that there are many sources of input data and many destinations of output data, i.e.,
many-to-many transmissions are used in the system. The addressed optimization problem is formulatedin the form of an ILP (Integer Linear Programing) model. Since the model is computationally demanding
and NP-complete, besides the branch-and-bound algorithm included in the CPLEX solver, we propose additional cut inequalities. Moreover, we present and test two effective heuristic algorithms: tabu search and
greedy. Both methods yield satisfactory results close to optimal.
JO - Theoretical and Applied Informatics
L1 - http://rhis.czasopisma.pan.pl/Content/93720/mainfile.pdf
L2 - http://rhis.czasopisma.pan.pl/Content/93720
IS - No 4
KW - optimization
KW - computing systems
KW - overlay
KW - heuristics
ER -
A1 - Walkowiak, Krzysztof
A1 - Kasprzak, Andrzej
A1 - Andrusieczko, Karol
PB - Institute of Theoretical and Applied Informatics of Polish Academy of Science
PB - Committee of Informatics of Polish Academy of Science
JF - Theoretical and Applied Informatics
T1 - Optimization of Overlay Computing Systems with Many-to-Many Transmissions / Optymalizacja nakładkowych systemów obliczeniowych z transmisjami wielu do wielu
UR - http://rhis.czasopisma.pan.pl/dlibra/docmetadata?id=93720