05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Permanent URI for this collectionhttps://elib.uni-stuttgart.de/handle/11682/6

Browse

Filters

2014 - 20172

Settings

Author: search.filters.author.Grunert, JonasSubject: search.filters.subject.004Institute: search.filters.UBSInstitut.Institut für Parallele und Verteilte Systeme

Search Results

Now showing 1 - 2 of 2
  • Thumbnail Image
    ItemOpen Access
    Concurrent query analytics on distributed graph systems
    (2017) Grunert, Jonas
    Large-scale graph problems, such as shortest path finding or social media graph evaluations, are an important area in computer science. In recent years, important graph applications such as PowerGraph or PowerLyra lead to a shift of paradigms of distributed graph processing systems towards processing of multiple parallel queries rather than a single global graph algorithm. Queries usually have locality in graphs, i.e. involve only a subset of the graphs vertices. Suitable partitioning and query synchronization approaches can minimize communication overhead and query latency by exploiting this locality. Additionally, partitioning algorithms must be dynamic as the number and locality of queries can change over time. Existing graph processing systems are not optimized to exploit query locality or to adapt graph partitioning at runtime. In this thesis we present Q-Graph, an open source, multitenant graph analytics system with dynamic graph repartitioning. Q-Graph's query-aware partitioning algorithm Q-Cut performs adaptive graph partitioning at runtime. Compared to static partitioning strategies, Q-Cut can exploit runtime knowledge about query locality and workload to improve partitioning dynamically. Furthermore a case study with an implementation for the shortest path problem and point search queries is presented. We present evaluations showing the performance of Q-Graph and the effectiveness of Q-Cut. Measurements show that Q-Cut improves query processing performance by up to 60% and automatically adapts partitioning on changing query workload and locality, outperforming partitioning methods using domain knowledge.
  • Thumbnail Image
    ItemOpen Access
    Increasing the bandwidth efficiency of content-based routing in software-defined networks
    (2014) Grunert, Jonas
    Content-based routing systems such as publish/subscribe (pub/sub) have become an important model for distributed systems with loosely coupled participants. Usually publish/subscribe systems are realized by overlay networks where dissemination and filtering of information is done in the application layer, which causes significant delay. The emergence of software-defined networking (SDN), where switches with programmable TCAM memory allow dynamic configuration of networks, has opened new opportunities in realizing dynamic logic inside the network. Current publications have presented realizations of pub/sub systems based on SDN. In these systems the information filtering is not done in the application layer but directly inside the network by switches. This allows event filtering with low delay and line-rate performance. However, SDN-based pub/sub systems are limited by the available resources. The TCAM memory of the switches, containing the forwarding rules, is very cost-intensive and hence the maximum number of rules and their complexity is limited. In order to provide bandwidthefficient content-based routing it is necessary to use a large number of complex forwarding rules. Therefore the limitation of resources causes a drop of the routing quality and less bandwidth-efficient routing. In this thesis, approaches to increase bandwidth-efficiency in the context of limited resources are proposed. To achieve efficient routing, the precision of in-network filtering must be high to avoid unnecessarily disseminated information, so-called false positives, which cause higher network utilization. This thesis proposes and evaluates two approaches to increase the efficiency of in-network filtering: Selection of more important information to be used for filtering and improvement of the filtering itself. Several algorithms to rate the importance of information are proposed and evaluated. Furthermore, ways to combine the selection of information and the improved filtering are shown. Our results show that the developed approaches can strongly reduce the number of false positives. The combination of best performing approaches can reduce the number of false positives by up to 75% and thereby increase the bandwidth efficiency significantly.