Optimization of overlay computing systems with many – to - many transmissions

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 formulated in the form of an ILP (Integer Linear Programing) model. Since the model is computationally demanding and NPcomplete, 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.

Zagadnienia dotyczące optymalizacji systemów obliczeń rozproszonych zyskują w ostatnich latach na znaczeniu. Systemy obliczeń rozproszonych rozwijane są w dwóch podstawowych architekturach sieciowych. Po pierwsze, budowane są dedykowane sieci optyczne łączące ośrodki obliczeniowe. Po drugie, wykorzystuje się istniejącą infrastrukturę sieciową (np. Internet) dla budowania systemów pracujących w architekturze nakładkowej (ang. overlay). Ta druga koncepcja zyskuje ostatnio dużą popularność, gdyż umożliwia szybką i tanią realizację systemów obliczeniowych bez potrzeby mocnej współpracy z operatorami sieciowymi. W pracy rozważamy nakładkowy system obliczeniowy umożliwiający transmisje wielu do wielu – dane wejściowe do obliczeń są generowane w wielu źródłach (węzłach sieciowych), następnie po przetworzeniu są przesyłane do wielu odbiorców zainteresowanych wynikami obliczeń. W oparciu o zaproponowaną architekturę systemu, w pracy sformułowano problem optymalizacyjny mający na celu minimalizację kosztów operacyjnych systemu obejmujących koszty obliczeń i koszty przesyłania danych. Model został zapisany jako program całkowitoliczbowy. Z uwagi na fakt, że ten problem należy do klasy problemów NP-zupełnych, zaproponowano dodatkowe odcięcia dla algorytmu podziału i oszacowań oraz dwa efektywne algorytmy heurystyczne. Przeprowadzone eksperymenty obliczeniowe wykazały, że opracowane algorytmy dają wyniki bliskie optymalnym w mniejszym czasie niż algorytm optymalny zawarty w pakiecie CPLEX