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

• Autorzy: Walkowiak K. , Kasprzak A. , Andrusieczko K.

Warianty tytułu

PL

Optymalizacja nakładkowych systemów obliczeniowych z transmisjami wielu do wielu

• Języki publikacji: EN

Abstrakty

EN

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.

PL

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

Słowa kluczowe

EN

optimization; computing systems; overlay; heuristics

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2012
• Tom: Vol. 24, No. 4
• Strony: 271--291
• Opis fizyczny: Bibliogr. 8 poz., rys.

Twórcy

autor

Walkowiak K.

autor

Kasprzak A.

autor

Andrusieczko K.

• Department of Systems and Computer Networks, Faculty of Electronics, Wroclaw University of Technology, Wybrzeze Wyspianskiego 27, 50-370 Wroclaw, Poland,

Bibliografia

• 1. C. Barnhart, C.A. Hane, P.H. Vance: Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow Problems. Operations Research, Vol. 48,No. 2, pp. 318-326, 2000.
• 2. BioGrid Australia. http://www.biogrid.org.au/wps/portal.
• 3. P. Bonetto, G. Oliva, A.R. Formiconi: MedIGrid: a medical imaging environment based on a grid computing infrastructure. Proceedings of the 25th Annual International Conference of the IEEE Engineering in Medicine and Biology Society, Vol.2, pp. 1338-1341,2003.
• 4. J. Buford, H. Yu, E. Lua: P2P Networking and Applications. Morgan Kaufmann, 2009.
• 5. C. Develder et al.: Survivable Optical Grid Dimensioning: Anycast Routing with Server and Network Failure Protection. In Proc. IEEE International Conference on Communications, ICC 2011, pp. 1-5, 2011.
• 6. C.K. Fong: A Study in Deploying Self-Organized Map (SOM) in an Open Source J2EE Cluster and Caching System. IEEE/ICME International Conference on Complex Medical Engineering, 2007, pp. 778-781, 2007.
• 7. M. Gendreau, J. Potvin: Handbook of metaheuristics. Springer, 2010.
• 8. F. Glover: Tabu Search - Part I. ORSA J. on Computing, Vol. 1, No. 3, pp. 190-206, 1989.
• 9. O. Gunluk: Branch-and-Cut Algorithm for Capacitated Network Design Problems. Math. Programming, Vol. 86, No. 1, pp. 17-39, 1999.
• 10. ILOG: CPLEX, 12.0 User’s Manual. France, 2007.
• 11. B. Jaumard, A. Shaikh: Maximizing access to IT services on resilient optical grids, 3rd International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), pp.1-6, 5-7 Oct. 2011.
• 12. T. Kacprzak, K. Walkowiak, M. Woźniak: Optimization of Overlay Distributed Computing Systems for Multiple Classifier System – Heuristic Approach. Logic Journal of IGPL, DOI: 10.1093/jigpal/jzr020, 2011.
• 13. H. Marchand, L. Wolsey: Aggregation and mixed integer rounding to solve MIPs. Operations Research, Vol. 49, No. 3, pp. 363-371, 2001.
• 14. J. Mitchell: Branch-and-cut methods for combinatorial optimization problems. in the Handbook of Applied Optimization, Oxford University Press, 2002.
• 15. J. Nabrzyski, J. Schopf, J. W˛eglarz (eds.): Grid Resource Management: State of the Art and Future Trends. Kluwer Academic Publishers, 2004.
• 16. M. Pioro, D. Medhi: Routing, Flow, and Capacity Design in Communication and Computer Networks. Morgan Kaufmann Publishers, 2004.
• 17. M.J. Pitkanen, Xin Zhou, A. Hyvarinen, H. Muller: Using the Grid for Enhancing the Performance of a Medical Image Search Engine. 21st IEEE International Symposium on Computer-Based Medical Systems, 2008. CBMS ’08., pp. 367-372, 2008.
• 18. X. Shen, H. Yu, J. Buford, M. Akon (eds.): Handbook of Peer-to-Peer Networking. Springer, 2009.
• 19. S. Lu, K. Lai, D. Yang, M. Tsai, K. Li, Y. Chung: Pervasive health service system: insights on the development of a grid-based personal health service system. 2010 12th IEEE International Conference on e-Health Networking Applications and Services (Healthcom), pp. 61-67, 2010.
• 20. T. Stevens et al.: Multi-Cost Job Routing and Scheduling in Optical Grid Networks. Future Generation Computer Systems. Vol. 25, No. 8, pp. 912-925, 2009.
• 21. S. Tarkoma: Overlay Networks: Toward Information Networking. Auerbach Publications 2010.
• 22. P. Thysebaert et al.: Scalable Dimensioning of Resilient Lambda Grids, Future Generation Computer Systems. Vol. 24, No. 6, pp. 549-560, 2008.
• 23. A. Travostino, J. Mambretti, G. Karmous-Edwards (eds.): Grid Networks Enabling Grids with Advanced Communication Technology. Wiley, 2006.
• 24. B. Wilkinson: Grid Computing: Techniques and Applications. Chapman & Hall/CRC Computational Science 2009.
• 25. Y. Zhu, B. Li: Overlay Networks with Linear Capacity Constraints. IEEE Transactions on Parallel and Distributed Systems, vol. 19, no. 2, pp. 159-173, 2008.