LINEAR PROGRAMMING OPTIMIZATION OF QUERY ALLOCATION IN A DISTRIBUTED CEP SYSTEM
Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
In Fujitsu’s up-and-coming Complex Event Processing service, the servers used for query-storage lie in a cloud environment. The cost of setting up the user-defined systems can therefore immediately be translated into the number of servers that is required and the amount of data that need to be sent between the servers.
The objective of this thesis was to provide a model that optimizes the cost of setting up these systems. The problem of query allocation has been modeled a linear program, such that the number of servers needed and the communication between them is minimized.
This turns out to be a kind of bin-packing-problem, which is known to be NP hard. Attempts to optimize the execution time were therefore made by implementing a customized solver that combined optimizations based on the problem-specific knowledge with the branch-and-bound-technique generally used by LP (Linear Programming) solvers. The customized solver was then compared to the commonly-used GLPK-solver and the comparison showed that the customized solver was to prefer in realistic scenarios where a lot of servers were needed. The GLPK solver did however often find the optimal solution early on, but could not discard the possibility of better solutions due to symmetry problems. The GLPK solver may therefore also be used if a certain fault-tolerance is acceptable.
Place, publisher, year, edition, pages
2012. , 45 p.
Engineering and Technology
IdentifiersURN: urn:nbn:se:kth:diva-102390OAI: oai:DiVA.org:kth-102390DiVA: diva2:552594
Master of Science in Engineering - Computer Science and Technology
Montelius, Johan, Universitetslektor