@misc{Hiller2004, type = {Master Thesis}, author = {Hiller, Benjamin}, title = {Bad Guys are Rare: Probabilistic Analysis of an Elementary Dial-a-Ride Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10114}, school = {Zuse Institute Berlin (ZIB)}, year = {2004}, abstract = {This thesis deals with a Dial-a-Ride problem on trees and considers both offline and online versions of this problem. We study the behavior of certain algorithms on random instances, i.e. we do probabilistic analysis. The focus is on results describing the typical behavior of the algorithms, i.e. results holding with (asymptotically) high probability. For the offline version, we present a simplified proof of a result of Coja-Oghlan, Krumke und Nierhoff. The results states that some heuristic using a minimum spanning tree to approximate a Steiner tree gives optimal results with high probability. This explains why this heuristic produces optimal solutions quite often. In the second part, probabilistic online versions of the problem are introduced. We study the online strategies REPLAN and IGNORE. Regarding the IGNORE strategy we can show that it works almost optimal under high load with high probability.}, language = {en} } @misc{FarshbafShaker2003, type = {Master Thesis}, author = {Farshbaf-Shaker, Mohammad-Hassan}, title = {Ein neues Verfahren zur L{\"o}sung des Streuproblems der Maxwell-Gleichungen}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9914}, school = {Zuse Institute Berlin (ZIB)}, year = {2003}, language = {de} } @misc{Rieche2003, type = {Master Thesis}, author = {Rieche, Simon}, title = {Lastbalancierung in Peer-to-Peer Systemen}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10048}, school = {Zuse Institute Berlin (ZIB)}, year = {2003}, abstract = {Peer-to-Peer (P2P) Systeme werden u.a. zur Verwaltung von großen Datenmengen benutzt, die auf verschiedene Rechner verteilt sind. Benutzern soll damit der Zugriff auf Daten innerhalb des Systems leicht erm{\"o}glicht werden. Damit in P2P Systemen die Daten effizient verteilt und gesucht werden k{\"o}nnen, existieren Distributed Hash Tables. Distributed Hash Tables (DHT) sind eine Methode, um globale Informationen persistent speichern zu k{\"o}nnen. Der Wertebereich der Hashfunktion, welche die zu ver{\"o}ffentlichenden Eintr{\"a}ge auf Werte abbildet, wird in Abschnitte aufgeteilt, die einzelnen Knoten zugeteilt werden. Die meisten DHTs haben aber ein Problem bei der Verteilung der Last. Die verschiedenen DHT Systeme beruhen meist auf einem identischen Ansatz der Lastverteilung. Die Last wird nur mit Hilfe einer Hashfunktion verteilt. Es wird davon ausgegangen, dass diese Funktion die Last gleichm{\"a}ßig verteilt. Im Rahmen dieser Arbeit wurde ein Verfahren zur Last Verteilung entwickelt, simuliert und implementiert. Bei dem Verfahren wird die Last wie bei der Verteilung von W{\"a}rme an die Umgebung abgegeben. Es wird mit existierenden Lastbalancierungsalgorithmen verglichen. Mit diesem neuen Verfahren ist es m{\"o}glich, Last in DHTs besser zu verteilen ohne große {\"A}nderungen an den DHTs vorzunehmen. Es wird gezeigt, wie mit dem Verfahren zus{\"a}tzlich die Fehlertoleranz des P2P Systems erh{\"o}ht werden kann.}, language = {de} } @misc{Menne2003, type = {Master Thesis}, author = {Menne, Ulrich}, title = {LP approaches to survivable networks with single path routing}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9989}, school = {Zuse Institute Berlin (ZIB)}, year = {2003}, language = {en} } @misc{Kroeller2003, type = {Master Thesis}, author = {Kr{\"o}ller, Alexander}, title = {Network Optimization: Integration of Hardware Configuration and Capacity Dimensioning}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9952}, school = {Zuse Institute Berlin (ZIB)}, year = {2003}, language = {en} } @misc{Tuchscherer2003, type = {Master Thesis}, author = {Tuchscherer, Andreas}, title = {Dynamical Configuration of Transparent Optical Telecommunication Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10214}, school = {Zuse Institute Berlin (ZIB)}, year = {2003}, abstract = {All-optical telecommunication networks allow for switching connections by lightpaths which can pass several network links without any opto-electronic conversion. Upon arrival of a connection request, it must be decided online, i.e., without knowledge of future requests, if it is accepted and in that case on which lightpaths the connection is routed. This online problem with the goal of maximizing the total profit gained by accepted requests is called Dynamic Singleclass Call Admission Problem (DSCA). We present existing and new algorithms for the DSCA as well as their theoretical and practical evaluation.}, language = {en} } @misc{Orlowski2003, type = {Master Thesis}, author = {Orlowski, Sebastian}, title = {Local and global restoration of node and link failures in telecommunication networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10008}, school = {Zuse Institute Berlin (ZIB)}, year = {2003}, abstract = {This diploma thesis deals with the restoration problem in telecommunication networks. The goal is to find a cost minimal capacity capacity assignment on the edges and nodes of a network such that given demands can be satisfied even in case of the failure of an edge or node in the network. Moreover, restrictions on the routing paths (like length restrictions) and hardware constraints have to be satisfied. A Mixed Integer Programming model is presented which takes into account restoration requirements as well as hardware constraints and which abstracts from a particular restoration protocol and failure situation. This abstraction provides new insight into the structure of the network restoration problem and shows that from a mathematical point of view, the commonly used restoration techniques Link Restoration, Path Restoration and Reservation are not as different as they seem to be from a practical point of view. In addition, our model allows (but is not limited to) optimizing working capacity, intended for normal use, and spare capacity, intended for rerouting purposes in case of a failure, in one step. Furthermore, our formulation of capacity cost allows taking into account the effects of discrete, non-linear cost structures which are common in practice. Up to our knowledge, no publication in the existing literature covers all these aspects, let alone in one model, although they are of major practical interest. The model has been implemented in a Branch and Cut framework. The theoretical background of the algorithmic procedure is presented in detail, including computational complexity investigations on the pricing problem. The abstraction from a particular restoration protocol turns out to be useful both from a theoretical and computational point of view. In fact, our investigations suggest a distinction into Local Restoration and Global Restoration rather than into Link Restoration,Path Restoration, Reservation and mixtures of these concepts. In addition to the theoretical aspects of the algorithmic procedure, some implementational details are briefly discussed. Our implementation has been tested on 14 real world instances, which is described in detail. One part of the computational results consists of a comparison of optimal network cost values using diffeent restoration mechanisms, applied to securing either all single node failures, all single edge failures or both. In addition, the effects of a discrete cost structure are investigated, which has rarely been considered yet in literature. Furthermore, the cost ifference between joint and successive working and spare capacity optimization is investigated. In the second part of the computational results, several heuristics for the network restoration problem are compared with respect to both solution quality and time. This diploma thesis deals with the restoration problem in telecommunication networks. The goal is to find a cost minimal capacity capacity assignment on the edges and nodes of a network such that given demands can be satisfied even in case of the failure of an edge or node in the network. Moreover, restrictions on the routing paths (like length restrictions) and hardware constraints have to be satisfied. A Mixed Integer Programming model is presented which takes into account restoration requirements as well as hardware constraints and which abstracts from a particular restoration protocol and failure situation. This abstraction provides new insight into the structure of the network restoration problem and shows that from a mathematical point of view, the commonly used restoration techniques Link Restoration, Path Restoration and Reservation are not as different as they seem to be from a practical point of view. In addition, our model allows (but is not limited to) optimizing working capacity, intended for normal use, and spare capacity, intended for rerouting purposes in case of a failure, in one step. Furthermore, our formulation of capacity cost allows taking into account the effects of discrete, non-linear cost structures which are common in practice. Up to our knowledge, no publication in the existing literature covers all these aspects, let alone in one model, although they are of major practical interest. The model has been implemented in a Branch and Cut framework. The theoretical background of the algorithmic procedure is presented in detail, including computational complexity investigations on the pricing problem. The abstraction from a particular restoration protocol turns out to be useful both from a theoretical and computational point of view. In fact, our investigations suggest a distinction into Local Restoration and Global Restoration rather than into Link Restoration, Path Restoration, Reservation and mixtures of these concepts. In addition to the theoretical aspects of the algorithmic procedure, some implementational details are briefly discussed. Our implementation has been tested on 14 real world instances, which is described in detail. One part of the computational results consists of a comparison of optimal network cost values using different restoration mechanisms, applied to securing either all single node failures, all single edge failures or both. In addition, the effects of a discrete cost structure are investigated, which has rarely been considered yet in literature. Furthermore, the cost difference between joint and successive working and spare capacity optimization is investigated. In the second part of the computational results, several heuristics for the network restoration problem are compared with respect to both solution quality and time.}, language = {en} } @misc{Schuett2002, type = {Master Thesis}, author = {Sch{\"u}tt, Thorsten}, title = {Synchronisation von verteilten Verzeichnisstrukturen}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10071}, school = {Zuse Institute Berlin (ZIB)}, year = {2002}, abstract = {Das Management von großen Datenmengen spielt eine immer wichtigere Rolle, wie aktuelle Entwicklungen in der Hochenergiephysik [2] zeigen. F{\"u}r das DataGrid-Projekt zum Beispiel ist es notwendig, große Datenmengen auf mehrere Rechenzentren in Europa zu verteilen und die Daten untereinander zu synchronisieren. Auch innerhalb von Clustern gewinnen mit zunehmender Anzahl der Knoten Werkzeuge zur effizienten Synchronisation und Verteilung von Daten an Bedeutung. Im Rahmen dieser Arbeit wurde ein effizientes Verfahren zur Synchronisation von verteilten Verzeichnisstrukturen entwickelt und implementiert. Mit diesem Verfahren ist es m{\"o}glich, unabh{\"a}ngige {\"A}nderungen an beliebigen Repositories gleichzeitig durchzuf{\"u}hren. Das Verfahren ben{\"o}tigt keine zentrale Instanz, wodurch eine gegen{\"u}ber vielen existierenden Verfahren verbesserte Skalierbarkeit erreicht werden konnte. Dabei wurden Erkenntnisse aus der Graphentheorie eingesetzt und weiterentwickelt, um die Netzwerktopolo-gie und -handbreiten zwischen den Rechnern zu ber{\"u}cksichtigen. Durch die Verwendung einer Offline-Synchronisation werden {\"A}nderungen erst dann an andere Rechner propagiert, wenn der Nutzer dies anst{\"o}ßt. Das kann zum Beispiel nach einer abgeschlossenen Transaktion, die {\"A}nderungen an mehreren Dateien beinhaltet, angemessen sein.}, language = {de} } @misc{Schintke2000, type = {Master Thesis}, author = {Schintke, Florian}, title = {Ermittlung von Programmlaufzeiten anhand von Speicherzugriffen, Microbenchmarks und Simulation von Speicherhierarchien}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10063}, school = {Zuse Institute Berlin (ZIB)}, year = {2000}, abstract = {Kostenmodelle dienen der Ermittlung von Programmlaufzeiten, zum Vergleich der Effizienz von Algorithmen und zur Analyse des Verhaltens von Speicherhierarchien. Ein neuartiges Kostenmodell ist das Latency-of-Data-Access (LDA) Modell, das mehrere hierarchische Speicherebenen mit unterschiedlichen Latenzzeiten ber{\"u}cksichtigt. In dieser Diplomarbeit wird ein Simulator f{\"u}r Speicherhierarchien pr{\"a}sentiert, der die Berechnung von Programmausf{\"u}hrungszeiten nach dem LDA-Modell erlaubt. Mit Hilfe des Simulators wird die These gepr{\"u}ft, daß mit diesem Modell die Ausf{\"u}hrungszeit eines Programms ad{\"a}quat abgesch{\"a}tzt werden kann. Mit dem Simulator ist es erstmals praktikabel m{\"o}glich, Programmausf{\"u}hrungszeiten nach dem LDA-Modell zu bestimmen. Der Simulator kann f{\"u}r Systeme mit unterschiedlichen Speicherarchitekturen konfiguriert werden und unterst{\"u}tzt Mehrprozessorsysteme mit gemeinsamem Speicher (SMP-Systeme) mit verschiedenen Koh{\"a}renzprotokollen. Der Simulator kann mit den Ergebnissen von Microbenchmarks konfiguriert werden, die die Architekturparameter einer Speicherhierarchie messen. Die Ergebnisse best{\"a}tigen die These nicht nur f{\"u}r Einzelprozessorsysteme, sondern auch f{\"u}r SMP-Systeme, wo gleichzeitig interagierende Prozessoren gegenseitig ihre Zugriffsse-quenz auf Zwischenspeicher beeinflussen. Zus{\"a}tzlich wurde eine neue Einsatzm{\"o}glichkeit des LDA-Modells entwickelt, um die Ausf{\"u}hrungszeit von Programmteilen zu bestimmen. Einzelne Zugriffskosten k{\"o}nnen einem mehrerer parallel laufender Modelle zugeordnet werden. Dadurch k{\"o}nnen Kosten, die Zugriffe auf einzelne Speicherbereiche verursachen, separat bestimmt werden. Diese Profiling-Technik erlaubt Optimierungen an Datenstrukturen und Speicherzugriffsmustern durch pr{\"a}zise und gezielte Informationsproduktion.}, language = {de} } @misc{Koch1995, type = {Master Thesis}, author = {Koch, Thorsten}, title = {Jack-III Ein Branch \& Cut-Verfahren zur L{\"o}sung des gewichteten Steinerbaumproblems in Graphen}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9946}, school = {Zuse Institute Berlin (ZIB)}, year = {1995}, abstract = {In der vorliegenden Arbeit werden die grundlegenden Gedanken und die Implementierung eines Branch \& Cut-Algorithmus zur L{\"o}sung des gewichteten Steinerbaumproblems in Graphen beschrieben. Der Algorithmus basiert auf der linearen Relaxierung einer bidirektionalen ganzzahligen Formulierung des Problems. Wir werden das Problem einf{\"u}hren, drei ganzzahlige Modellierungen vorstellen, auf Reduktionsverfahren und Heuristiken eingehen sowie das Verfahren und seine Implementierung darstellen. Am Ende werden wir die Implementierung an 191 bekannten Probleminstanzen testen und auch optimale L{\"o}sungen f� ur zwei nach Wissen des Autors bis zu diesem Zeitpunkt ungel{\"o}ste Instanzen liefern.}, language = {de} }