Optimization Methods for Cloud Computing and Communications (OTKA project no. K108947)
Head of the project: Dr. Recski András
Participans: Péter Babarczi, Krisztián Antal Buza, Csongor György Csehi, Balázs Csizmadia, Katalin Friedl, András Gulyás, László Gyimóthi, Éva Hosszú, László Kabódi, Gyula Katona, Attila Kiss, Attila Körösi, Zoltán Ádám Mann, Péter Pál Pach, László Papp, Alija Pasic, Gábor Rétvári, Ildikó Schlotter, Dániel Soltész, Péter Szabó, Dávid Szeszlér, János Tapolcai , Ágnes Tóth, Kitti Varga, Balázs Vass, Gábor Wiener
In the near future cloud computing will become the most dominant operation model of the Internet, and will be responsible for computing, communication and storage of a huge portion of users digital data. Thus, data centers must provide high processing power and high communication rate in order to accommodate the even growing number of cloud users. In order to keep up with the growing number of computation request, data centers and the communication infrastructures need to satisfy two crucial properties: scalability and energy-efficiency. Rather than installing more and more servers (increasing network cost and energy consumption), our main goal is to address the above issues with combinatorial optimization methods to reach better efficiency on the existing infrastructure, or to design more efficient architectures based on the available devices.
Combinatorial optimization applies the structures of discrete mathematics and the tools of theoretical computer science for solving, in a computationally effective way, such problems where even the fastest computers would require millions of years to try every possibility due to the large size and the complexity of the problems. In five consecutive funding projects since 1991 our computer science group has obtained over 350 publications on combinatorial optimization techniques and their engineering applications. We would like to continue this activity, mostly to obtain new results in timely and relevant engineering problems, such as the design of data centers and dynamic communication infrastructures for cloud computing and communications, rely on the expertise of members of the MTA-BME Momentum Future Internet Research Group.
Our main goal is to provide practical and theoretical results for scalable and energy-efficient data center architectures, and to propose novel addressing and protection schemes for dynamic optical transport networks. In order to address these problems in cloud computing and communications we wish to use various combinatorial optimization methods:
(1) How to plan scalable data center and communication infrastructures for the cloud in order to accommodate the growing number of cloud users? We investigate information theoretic properties for efficient channel usage and improved capacity efficiency. Techniques of combinatorial optimization, including graph connectivity and coloring properties, are investigated for reliable network and connection design.
(2) How can we consider the novel routing paradigms and user decisions on green energy usage in the dynamic routing algorithms? We investigate anycast and multicast green-energy aware routing algorithms in cloud backbones with Hamiltonicity-related concepts in graphs and hypergraphs.
(3) How can we redesign the data centers' architecture using the existing devices or with minimal cost to reduce energy consumption and/or to accommodate the growing number of cloud users while backward compatibility is satisfied? We propose novel data center architecture for scalable data center applications with considering complex job scheduling problems and the novel design paradigms of multimedia servers.
(4) We study the worst case complexity of cloud algorithms and provide theoretical and empirical analysis of typical case complexity of such algorithms. We are working on efficient job compressing with kernelization algorithms as well.
Applying the above combinatorial optimization techniques we plan to obtain new results in the following areas of cloud computing and communications:
(1) Scalable data center topologies, which is a highly symmetric simple graph topology where every pair of node is connected through short paths, with high path diversity (multiple edge-disjoint paths between the nodes) and with excellent load balancing.
(2) By solving the optimization problems in router- and data center architecture design (e.g. more effective design of distributed multimedia servers, job scheduling with unknown duration) we can reach lower energy consumption and faster response time in data centers, respectively.
(3) Understanding the worst-case and typical case complexity of routing-, scheduling-, failure management-, etc. algorithms has utmost importance from the point of view of applications in a dynamic network environment such as clouds.
(4) Novel addressing has significant importance in cloud service differentiation and in the fast recovery from network disruptions.
In addition, we expect to enrich the theory of the applied mathematical tools, like discovering polynomial solvable subcases of NP-hard problems. Besides, cloud computing and communications results can be applied in other branches of mathematics as well (scheduling and transportation problems, logic programming, applications of stable matching in economics etc.).
Period closing report (2017 September)
Period closing report (2016 September)