@misc{Kruber2009, type = {Master Thesis}, author = {Kruber, Nico}, title = {DHT Load Balancing with Estimated Global Information}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11514}, school = {Zuse Institute Berlin (ZIB)}, year = {2009}, abstract = {One of the biggest impacts on the performance of a Distributed Hash Table (DHT), once established, is its ability to balance load among its nodes. DHTs supporting range queries for example suffer from a potentially huge skew in the distribution of their items since techniques such as consistent hashing can not be applied. Thus explicit load balancing schemes need to be deployed. Several such schemes have been developed and are part of recent research, most of them using only information locally available in order to scale to arbitrary systems. Gossiping techniques however allow the retrieval of fairly good estimates of global information with low overhead. Such information can then be added to existing load balancing algorithms that can use the additional knowledge to improve their performance. Within this thesis several schemes are developed that use global information like the average load and the standard deviation of the load among the nodes to primarily reduce the number of items an algorithm moves to achieve a certain balance. Two novel load balancing algorithms have then been equipped with implementations of those schemes and have been simulated on several scenarios. Most of these variants show better balance results and move far less items than the algorithms they are based on. The best of the developed algorithms achieves a 15-30\% better balance and moves only about 50-70\% of the number of items its underlying algorithm moves. This variation is also very robust to erroneous estimates and scales linearly with the system size and system load. Further experiments with self-tuning algorithms that set an algorithm's parameter according to the system's state show that even more improvements can be gained if additionally applied. Such a variant based on the algorithm described by Karger and Ruhl shows the same balance improvements of 15-30\% as the variant above but reduces the number of item movements further to 40-65\%.}, language = {en} } @misc{Mauter2009, type = {Master Thesis}, author = {Mauter, Daniel}, title = {Ein eingebettetes Hauptspeicher-Datenbanksystem mit Snapshot-Reads}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11552}, school = {Zuse Institute Berlin (ZIB)}, year = {2009}, abstract = {Entwurf und Entwicklung eines eingebetteten Hauptspeicher-Datenbanksystems mit Snapshot-Reads.}, language = {de} } @misc{Prollius2009, type = {Master Thesis}, author = {Prollius, Christian von}, title = {Ein Peer-to-Peer System mit Bereichsabfragen in PlanetLab}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11492}, school = {Zuse Institute Berlin (ZIB)}, year = {2009}, abstract = {Aktuelle Entwicklungen zeigen, dass Peer-to-Peer (P2P) Anwendungen wie Skype oder Bittorrent im Internet immer mehr an Bedeutung gewinnen. In den letzten Jahren hat es einen explosionsartigen Anstieg an Nutzern und Daten in solchen Netzen gegeben. Dabei stellt der eigentliche Dateitransfer zwischen zwei Rechnern kein großes Problem mehr dar und auch der Speicherbedarf f{\"u}r die große Menge an Daten kann durch die Weiterentwicklung der Hardware gut gedeckt werden. Das eigentliche Problem liegt vielmehr darin, den Rechner zu finden, der die gew{\"u}nschten Daten hat. Client-Server Architekturen, wie zum Beispiel Napster, haben sich als ung{\"u}nstig herausgestellt. Wenige Server, die eine große Anzahl an Clients bedienen m{\"u}ssen, sind einerseits sehr anf{\"a}llig gegen{\"u}ber Angriffen und Ausf{\"a}llen (Single Point of Failure)und kommen auch nicht mit der st{\"a}ndig wachsenden Anzahl an Nutzern zurecht. Verteilte Hashtabellen (DHT) bieten hier einen guten L{\"o}sungsansatz, der mit einer großen Anzahl an Nutzern skaliert und ausfallsicher ist. Andere dezentrale L{\"o}sungen, wie zum Beispiel das P2P Netzwerk Gnutella haben zwar das Problem des Single Point of Failure gel{\"o}st, jedoch haben sie starke Nachteile bei der Suche nach Keys. Bei einer Suche wird ein Broadcast verwendet (jeder schickt die Anfrage an jeden weiter) und damit ein enormer Netzwerkverkehr erzeugt. In "Why Gnutella Can't Scale. No, Really" wird erkl{\"a}rt, dass eine Suchanfrage bei Standardeinstellungen in der Clientsoftware einen Netzwerkverkehr von 17MB erzeugt. Deswegen wird zus{\"a}tzlich eine L{\"o}sung ben{\"o}tigt, die Keys und Values geordnet verteilt, damit sie gezielt gesucht werden k{\"o}nnen. Aus diesem Grund besch{\"a}ftigt sich die folgende Arbeit mit einer v{\"o}llig dezentralen Architektur, die außerdem eine sinnvolle Platzierung der Keys vornimmt. Die dezentrale Architektur hat den Vorteil, dass die Endger{\"a}te den Hauptteil des Dienstes selbst erbringen und damit jeder zus{\"a}tzliche Teilnehmer seine eigenen Ressourcen beisteuert. Diese Arbeit pr{\"a}sentiert Chord\#, eine dezentrale, skalierbare und selbstorganisierende verteilte Hashtabelle. Chord\# wurde ausgew{\"a}hlt, da in dieser Arbeit auch Wert auf Bereichsabfragen gelegt wurde. Diese sind zum Beispiel bei dem Chord Algorithmus nicht m{\"o}glich, da dieser eine Hashfunktion f{\"u}r die Keys verwendet und somit die Daten zwar gleichm{\"a}ßig aber unsortiert auf die Teilnehmer verteilt. Es wird in dieser Arbeit gezeigt, dass mit Hilfe von Chord\# auch ohne die Hashfunktion gute Ergebnisse erzielt werden. Außerdem k{\"o}nnen durch den Verzicht auf die Hashfunktion Bereichsabfragen erm{\"o}glicht werden. Daf{\"u}r wird der Chord\# Algorithmus in Java implementiert (ca. 1500 Zeilen Code) und in dem Forschungsnetz PlanetLab ausf{\"u}hrlich auf Laufzeiten, Instandhaltungskosten und Skalierung getestet.}, language = {de} } @misc{Steidinger2004, author = {Steidinger, Alexander}, title = {Data Management for Processing Molecules}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8358}, number = {05-01}, year = {2004}, abstract = {Molecular dynamics simulations of possible ligands for proteins yield large amounts of data in the form of trajectories which are further processed in order to find metastable conformations. These conformations can then be used for docking between ligand and protein. Around this core computation procedure lots of other data have to be managed. It should also be possible for external users not involved in program development to perform computations. As a paradigm for other fields where a similar constitution of program usage and data processing is found we present a software architecture for data generation, access and management. Requirements for this system include: Ease of use, graphical user interface, persistent storage of data concerning molecules, users, programs, program parameters, metadata, and results. A mere storage in the file system would render a quick overview of data more or less impossible. On the other hand, storing large amounts of binary data in a database doesn't yield any advantage concerning speed of access. Therefore, a hybrid approach combining file system and database is appropriate. The system should be easily extensible by inserting new applications which can be controlled and whose results can be collected and stored. The software system described here consists of different components, the presentation layer (graphical user interface), the business logic, the persistence layer (relational database plus file system), and an interface to the compute cluster (batch system for parallel processing). We will discuss the alternatives and take a closer look at the components.}, language = {en} }