Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
LINEAR PROGRAMMING OPTIMIZATION OF QUERY ALLOCATION IN A DISTRIBUTED CEP SYSTEM
KTH, School of Information and Communication Technology (ICT).
2012 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

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.
Series
Trita-ICT-EX, 2012:197
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:kth:diva-102390OAI: oai:DiVA.org:kth-102390DiVA: diva2:552594
Educational program
Master of Science in Engineering - Computer Science and Technology
Uppsok
Technology
Examiners
Available from: 2012-09-14 Created: 2012-09-14 Last updated: 2012-09-14Bibliographically approved

Open Access in DiVA

fulltext(1230 kB)322 downloads
File information
File name FULLTEXT01.pdfFile size 1230 kBChecksum SHA-512
365dabc028d5b8320e15113bce48e2d508763ad594dbd8563f7ca3705c550c0e3930d5324d1d16a5361d2cc29088a6bb5933ef4e67713406ac2d4b3b32bceac2
Type fulltextMimetype application/pdf

By organisation
School of Information and Communication Technology (ICT)
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 322 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 206 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf