@misc{Kettner2006, type = {Master Thesis}, author = {Kettner, Benjamin}, title = {Ein Algorithmus zur prismatoidalen Diskretisierung von unbeschr{\"a}nkten Außenr{\"a}umen in 2D und 3D unter Einhaltung von Nebenbedingungen}, year = {2006}, language = {en} } @misc{Guerler2006, type = {Master Thesis}, author = {G{\"u}rler, A.}, title = {Selection and flexible optimization of binding modes from conformation ensembles.}, year = {2006}, language = {en} } @misc{Heismann2010, type = {Master Thesis}, author = {Heismann, Olga}, title = {Minimum Cost Hyperassignments}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-13371}, school = {Zuse Institute Berlin (ZIB)}, year = {2010}, abstract = {Vehicle rotation planning for long distance passenger railways is a fundamental problem in rail transport. It deals with the allocation of vehicles to trips in a cyclic weekly schedule. Its result is an assignment of each trip to a follow-on trip which will be serviced by the same vehicle. To take so-called regularity, which is an important requirement, into account, vehicle rotation planning can be modeled as a hyperassignment problem. This is a generalization of the assignment problem to directed hypergraphs we propose. We prove that the hyperassignment problem is NP-hard for the practically relevant cases and that the canonical integer linear programming (ILP) formulation results in large integrality gaps and arbitrarily high basis matrix determinants. Our main contribution is an extended ILP formulation, which provably implies important classes of inequalities, e. g., all clique inequalities. Clique inequalities are of great importance, because as calculations with practical data show they highly reduce the LP-IP gap. The extended formulation can be solved by column generation. We propose fast combinatorial algorithms for the pricing subproblem.}, language = {en} } @misc{Schweiger2010, type = {Master Thesis}, author = {Schweiger, Jonas}, title = {Application of Multistage Stochastic Programming in Strategic Telecommunication Network Planning}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12206}, school = {Zuse Institute Berlin (ZIB)}, pages = {149}, year = {2010}, abstract = {Telecommunication is fundamental for the information society. In both, the private and the professional sector, mobile communication is nowadays taken for granted. Starting primarily as a service for speech communication, data service and mobile Internet access are now driving the evolution of network infrastructure. In the year 2009, 19 million users generated over 33 million GB of traffic using mobile data services. The 3rd generation networks (3G or UMTS) in Germany comprises over 39,000 base stations with some 120,000 cells. From 1998 to 2008, the four network operators in Germany invested over 33 billion Euros in their infrastructure. A careful allocation of the resources is thus crucial for the profitability for a network operator: a network should be dimensioned to match customers demand. As this demand evolves over time, the infrastructure has to evolve accordingly. The demand evolution is hard to predict and thus constitutes a strong source of uncertainty. Strategic network planning has to take this uncertainty into account, and the planned network evolution should adapt to changing market conditions. The application of superior planning methods under the consideration of uncertainty can improve the profitability of the network and creates a competitive advantage. Multistage stochastic programming is a suitable framework to model strategic telecommunication network planning. We present mathematical models and effective optimization procedures for strategic cellular network design. The demand evolution is modeled as a continuous stochastic process which is approximated by a discrete scenario tree. A tree-stage approach is used for the construction of non-uniform scenario trees that serve as input of the stochastic program. The model is calibrated by historical traffic observations. A realistic system model of UMTS radio cells is used that determines coverage areas and cell capacities and takes signal propagation and interferences into account. The network design problem is formulated as a multistage stochastic mixed integer linear program, which is solved using state-of-the-art commercial MIP solvers. Problem specific presolving is proposed to reduce the problem size. Computational results on realistic data is presented. Optimization for the expected profit and the conditional value at risk are performed and compared.}, language = {en} } @misc{Woelk2009, type = {Master Thesis}, author = {W{\"o}lk, Bertram}, title = {Generierung hybrider Gitter f{\"u}r die Str{\"o}mungssimulation auf komplexen anatomischen Geometrien}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11588}, school = {Zuse Institute Berlin (ZIB)}, year = {2009}, abstract = {Basierend auf einem vorhandenen Ansatz zur Einf{\"u}hrung von anisotropen Tetraedern im Randbereich eines reinen Tetraedergitters wird ein Gittergenerator f{\"u}r hybride Gitter implementiert. Das hybride Gitter besteht in Randn{\"a}he prim{\"a}r aus anisotropen Prismen und im Inneren der Geometrie aus isotropen Tetraedern. Eine erh{\"o}hte Aufl{\"o}sung im Randbereich soll zu besseren Ergebnissen von numerischen Str{\"o}mungssimulationen f{\"u}hren, f{\"u}r welche eine problemangepasste Diskretisierung des zu untersuchenden Gebietes ben{\"o}tigt wird. In dem zuvor genannten Ansatz wird eine Reihe von {\"U}bergangselementen vorgeschlagen, die an scharfen Kanten der Oberfl{\"a}che platziert werden sollen. Im Rahmen dieser Diplomarbeit wird die Idee der {\"U}bergangselemente aufgegriffen und bei hybriden Gittern eingesetzt, um auch komplexe Eingabegeometrien vergittern zu k{\"o}nnen. Der urspr{\"u}ngliche Gittergenerierungprozess wird {\"u}berarbeitet und erweitert. Eine neue Menge an {\"U}bergangselementen wird eingef{\"u}hrt, es werden gekr{\"u}mmte Extrusionsvektoren verwendet und es wird die Auswertung der medialen Oberfl{\"a}che vorgenommen, um {\"U}berschneidungen im hybriden Gitter zu vermeiden. Der Gittergenerator wird als Modul in das Visualisierungs- und Analyseprogramm Amira implementiert und die erstellten hybriden Gitter werden auf ihre Elementqualit{\"a}t und die G{\"u}te der Str{\"o}mungssimulationsergebnisse hin {\"u}berpr{\"u}ft.}, language = {de} } @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{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{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{Tuschl2009, type = {Master Thesis}, author = {Tuschl, Roland}, title = {Ein Userspace-Dateisystem zur Verwaltung von Grid-Daten}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11483}, school = {Zuse Institute Berlin (ZIB)}, year = {2009}, abstract = {Das Ziel dieser Arbeit ist die Schaffung einer Zugriffs-Komponente f{\"u}r das Grid-Datenmanagement-System ZIB-DMS, das dessen transparente Einbindung in den Verzeichnisbaum eines Linux-Systems erlaubt. Dazu wird unter Verwendung des FUSE-Rahmenwerkes ein Userspace-Dateisystem mit Anbindung an das ZIB-DMS konzipiert und implementiert. Im Fokus stehen dabei die Abbildung der erweiterten Verwaltungsmechanismen des Systems auf die limitierte Schnittstelle hierarchischer Dateisysteme und die dazu notwendigen {\"A}nderungen am ZIB-DMS.}, language = {de} } @misc{Massing2009, type = {Master Thesis}, author = {Massing, Andr{\´e}}, title = {1D-Reduktion thermal signifikanter Aderstr{\"a}nge in der Hyperthermie-Modellierung}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11407}, school = {Zuse Institute Berlin (ZIB)}, year = {2009}, abstract = {In dieser Arbeit wird ein neuer Ansatz zur Modellierung von thermal signifikanten Gef{\"a}ßstr{\"a}ngen im Hyperthermie-Kontext betrachtet. Ausgehend von einer Konvektions-Diffusions-Gleichung wird durch Reskalierung des Massenflussterms eine Reduktion des Adergebietes auf eine 1D-Struktur erreicht. Nach numerischen Vorbetrachtungen wird die Grenzgleichung innerhalb einer verallgemeinerten Sobolev-Algebra formuliert. Die Untersuchung der L{\"o}sungsfamilie in klassischen Funktionenr{\"a}umen zeigt, dass deren schwacher Grenzwert die L{\"o}sung der korrespondierenden Diffusions-Gleichung ist. Die Diskretisierung einer formalen Grenzgleichung mit Linienstromanteil stellt jedoch eine gute Approximation an die Diskretisierung des urspr{\"u}nglichen Problems dar, wenn man die lokale Maschenweite an die Gef{\"a}ßradien koppelt und bei erh{\"o}htem Genauigkeitsbedarf auf ein vollst{\"a}ndiges 3D-Modell umschaltet.}, language = {de} } @misc{Gleixner2009, type = {Master Thesis}, author = {Gleixner, Ambros}, title = {Solving Large-scale Open Pit Mining Production Scheduling Problems by Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11389}, school = {Zuse Institute Berlin (ZIB)}, year = {2009}, abstract = {Since the initial application of mathematical optimisation methods to mine planning in 1965, the Lerchs-Grossmann algorithm for computing the ultimate pit limit, operations researchers have worked on a variety of challenging problems in the area of open pit mining. This thesis focuses on the open pit mining production scheduling problem: Given the discretisation of an orebody as a block model, determine the sequence in which the blocks should be removed from the pit, over the lifespan of the mine, such that the net present value of the mining operation is maximised. In practise, when some material has been removed from the pit, it must be processed further in order to extract the valuable elements contained therein. If the concentration of valuable elements is not sufficiently high, the material is discarded as waste or stockpiled. Realistically-sized block models can contain hundreds of thousands of blocks. A common approach to render these problem instances computationally tractable is the aggregation of blocks to larger scheduling units. The thrust of this thesis is the investigation of a new mixed-integer programming formulation for the open pit mining production scheduling problem, which allows for processing decisions to be made at block level, while the actual mining schedule is still computed at aggregate level. A drawback of this model in its full form is the large number of additional variables needed to model the processing decisions. One main result of this thesis shows how these processing variables can be aggregated efficiently to reduce the problem size significantly, while practically incurring no loss in net present value. The second focus is on the application of lagrangean relaxation to the resource constraints. Using a result of M{\"o}hring et al. (2003) for project scheduling, the lagrangean relaxation can be solved efficiently via minimum cut computations in a weighted digraph. Experiments with a bundle algorithm implementation by Helmberg showed how the lagrangean dual can be solved within a small fraction of the time required by standard linear programming algorithms, while yielding practically the same dual bound. Finally, several problem-specific heuristics are presented together with computational results: two greedy sub-MIP start heuristics and a large neighbourhood search heuristic. A combination of a lagrangean-based start heuristic followed by a large neighbourhood search proved to be effective in generating solutions with objective values within a 0.05\% gap of the optimum.}, language = {en} } @misc{Kinder2008, type = {Master Thesis}, author = {Kinder, Mathias}, title = {Models for Periodic Timetabling}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10887}, school = {Zuse Institute Berlin (ZIB)}, year = {2008}, abstract = {We investigate the computation of periodic timetables for public transport by mixed integer programming. After introducing the problem, we describe two mathematical models for periodic timetabling, the PERIODIC EVENT SCHEDULING PROBLEM (PESP) and the QUADRATIC SEMI-ASSIGNMENT PROBLEM. Specifically, we give an overview of existing integer programming (IP) formulations for both models. An important contribution of our work are new IP formulations for the PESP based on time discretization. We provide an analytical comparison of these formulations and describe different techniques that allow a more efficient solution by mixed integer programming. In a preliminary computational study, on the basis of standard IP solvers, we compare different formulations for computing periodic timetables. Our results justify a further investigation of the time discretization approach. Typically the timetable is optimized for the current traffic situation. The main difficulty with this approach is that after introducing the new timetable the passengers' travel behavior may differ from that assumed for the computation. Motivated by this problem, we examine an iterative timetabling procedure that is a combination of timetable computation and passenger routing. We discuss the algorithmic issues of the passenger routing and study properties of the computed timetables. Finally, we confirm our theoretical results on the basis of an own implementation.}, language = {en} } @misc{Boehner2008, type = {Master Thesis}, author = {B{\"o}hner, D{\"o}rte}, title = {Chancen und Risiken Digitaler Rechtebeschreibung f{\"u}r wissenschaftliche Bibliotheken in Deutschland - M{\"o}glichkeiten und Perspektiven von Digital Rights Management}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9271}, school = {Zuse Institute Berlin (ZIB)}, year = {2008}, abstract = {Wissenschaftliche Bibliotheken sind Vermittler von digitalen Medieninhalten. Sie m{\"u}ssen ihren Nutzern einen Zugang zu ihnen erm{\"o}glichen. Digitales Rechte Management (DRM), eingesetzt von den Verlagen, soll Nutzung und Zugang kontrollieren. Bibliotheken stehen DRM daher misstrauisch gegen{\"u}ber, da dieses als Gefahr f{\"u}r die Wissenschaft und ihre (digitalen) Bibliotheken gesehen wird. Nur eine effektive Auseinandersetzung der wissenschaftlichen Bibliotheken mit der jeweiligen Politik der Verlage und den Verfahrensweisen bei DRM erm{\"o}glicht es ihnen, ihre Rolle als Vermittler und 'Ged{\"a}chtnis der Menschheit' auch weiterhin erfolgreich wahrnehmen zu k{\"o}nnen. Unbestritten ist, dass DRM in seiner restriktiven Form die t{\"a}gliche Arbeit der Bibliotheken erschwert. Deshalb m{\"u}ssen sie sich aktiv an der Standardisierung, der Entwicklung von Nutzungskonzepten und der Gestaltung der Rahmenbedingungen beteiligen.}, language = {de} } @misc{Zilske2008, type = {Master Thesis}, author = {Zilske, Michael}, title = {Adaptives Remeshing von nicht-mannigfaltigen Dreiecksnetzen}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-474}, school = {Zuse Institute Berlin (ZIB)}, year = {2008}, abstract = {In dieser Arbeit wird eine Serie von Remeshing-Verfahren um die Ber{\"u}cksichtigung von nicht-mannigfaltigen Dreiecksvernetzungen und Merkmalskantenz{\"u}gen erweitert. Die betrachteten Verfahren arbeiten im Wesentlichen lokal. Daher k{\"o}nnen die im Rahmen dieser Arbeit entwickelten Erweiterungen, die nicht-mannigfaltige Kantenz{\"u}ge und Merkmalskantenz{\"u}ge betreffen, separat beschrieben werden. Dabei wird ein Ansatz verfolgt, beide Arten von besonderen Kantenz{\"u}gen aufgrund ihrer Gemeinsamkeiten einheitlich zu behandeln. Dieser besteht zum einen darin, eine Korrespondenz zwischen Kantenz{\"u}gen auf der Eingabe- und der Ausgabefl{\"a}che zu erhalten, indem die Remeshing-Operationen auf den Kantenz{\"u}gen in entsprechend eingeschr{\"a}nkter Weise verwendet werden. Zum anderen wird beschrieben, wie die Abtastdichte der Kantenz{\"u}ge dynamisch an die Abtastdichte der Umgebung angepasst werden kann, um f{\"u}r weitgehende Isotropie in der N{\"a}he von Merkmalskantenz{\"u}gen zu sorgen.}, language = {de} } @misc{Plantikow2007, type = {Master Thesis}, author = {Plantikow, Stefan}, title = {Transaktionen f{\"u}r verteilte Wikis auf strukturierten Overlay Netzwerken}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10176}, school = {Zuse Institute Berlin (ZIB)}, year = {2007}, abstract = {Die Diplomarbeit pr{\"a}sentiert ein Transaktionsverfahren f{\"u}r strukturierte Overlay-Netzwerke, das an die Erfordernisse verteilter Informationssysteme mit relationalem Datenmodell angepasst ist. Insbesondere wird der Einsatz von Transaktionen f{\"u}r verteilte Wikis betrachtet, die moderne Funktionalit{\"a}ten, wie Metadaten und zus{\"a}tzliche Indexe f{\"u}r die Navigation, unterst{\"u}tzen. Konsistenz und Dauerhaftigkeit der gespeicherten Daten erfordert die Behandlung von Knotenausf{\"a}llen. Die Arbeit schl{\"a}gt daf{\"u}r das Zellenmodell vor: Das Overlay wird aus replizierten Zustandsmaschinen gebildet, um Verf{\"u}gbarkeit zu gew{\"a}hrleisten. Das Transaktionsverfahren baut darauf auf und verwendet Two-Phase-Commit mit Fehlererkennung und Widerherstellung von ausgefallenen Transaktionsmanagern. Anwendungen wird eine Auswahl an pessimistischen und hybrid-optimistischen Nebenl{\"a}ufigkeitskontrollverfahren geboten, die die Minimierung von Latenzeffekten und die schnelle Ausf{\"u}hrung von Nur-Lese-Transaktionen erm{\"o}glichen. F{\"u}r die Beispielanwendung Wiki wird der erforderliche Pseudocode angegeben und die verschiedenen Nebenl{\"a}ufigkeitskontrollverfahren hinsichtlich ihrer Nachrichtenkomplexit{\"a}t verglichen.}, language = {de} } @misc{Gerber2007, type = {Master Thesis}, author = {Gerber, Susanne}, title = {Perfusionsmodellierung in menschlichen Tumoren}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9923}, school = {Zuse Institute Berlin (ZIB)}, year = {2007}, abstract = {Im Rahmen dieser Arbeit wurde ein individuell anpassungsf{\"a}higes Modell entwickelt und implementiert, das die Perfusion in menschlichen soliden Tumoren beschreibt und f{\"u}r verschiedene Zeitpunkte w¨ahrend regionaler Hyperthermie ein lokal abh{\"a}ngiges Temperaturprofil berechnet. Da vor jeder Simulation alle wichtigen Parameter anhand von Ultraschall-, MRT- oder Angiogrammbildern individuell bestimmt werden k{\"o}nnen, wird eine patientenspezifische Aussage ¨uber das intratumorale Antwortverhalten bereits vor der eigentlichen Behandlung m{\"o}glich. In Abh¨angigkeit von der Qualit{\"a}t der zur Verf{\"u}gung stehenden anatomischen Daten {\"u}ber das zu simulierende Gebiet kann das Modell beliebig verfeinert oder bei Mangel an detaillierten Informationen auch mit Minimaldaten und reduzierter r{\"a}umlicher Genauigkeit benutzt werden. Die f{\"u}r eine Simulation ben{\"o}tigten 2- oder 3- dimensionalen Geometrien k{\"o}nnen leicht mit der am ZIB entwickelten Software Amira erstellt und zur Berechnung in KARDOS, einem ebenfalls am ZIB implementierten L{\"o}ser f{\"u}r nichtlineare partielle Differentialgleichungen, eingelesen werden. Mit Hilfe dieses Modells wird eine einfache, aber realistische und aussagekr{\"a}ftige Simulation f{\"u}r die Therapieplanung einer klinischen Hyperthermieanwendung erm{\"o}glicht, die innerhalb kurzer Zeit vorbereitet und durchgef{\"u}hrt werden kann.}, language = {de} } @misc{Maiwald2007, type = {Master Thesis}, author = {Maiwald, Gunar}, title = {Entity Resolution f{\"u}r Zitationen mit Probabilistischen Relationalen Modellen}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9899}, school = {Zuse Institute Berlin (ZIB)}, year = {2007}, abstract = {In dieser Diplomarbeit wird untersucht, wie auf der Basis von Literaturreferenzen ein Zitationsgraph durch ein automatisches Verfahren aufgebaut werden kann. Zur L{\"o}sung des Problems werden Probabilistische Relationale Modelle herangezogen. Eine problemspezifische Erweiterung des Modells erm{\"o}glicht es, dass bestehende Unsicherheiten im Zitationsgraphen mit Hilfe eines Inferenzverfahrens aufgel{\"o}st werden k{\"o}nnen. Zur Evaluierung des Verfahren werden Experimente auf dem Cora-Datensatz durchgef{\"u}hrt.}, language = {de} } @misc{Lichtenstein2006, type = {Master Thesis}, author = {Lichtenstein, Tom}, title = {Implementation eines Resourcebrokers im Kontext eines Grid-Datenmanagement-Systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9968}, school = {Zuse Institute Berlin (ZIB)}, year = {2006}, language = {de} } @misc{Meltzer2006, type = {Master Thesis}, author = {Meltzer, J{\"o}rg}, title = {Vergleich von Co-Reservierungs-Algorithmen in Grid-Umgebungen}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9972}, school = {Zuse Institute Berlin (ZIB)}, year = {2006}, abstract = {In dieser Arbeit werden effiziente Co-Reservierungs-Algorithmen vorgestellt, mit denen Rechenressourcen mehrerer Cluster im Grid reserviert werden k{\"o}nnen. Es werden f{\"u}nf Algorithmen vorgestellt, die flexible Co-Reservierungsanfragen erm{\"o}glichen. In einer Co-Reservierungsanfrage m{\"u}ssen die angeforderten CPUs der Teilreservierungen exakt festgelegt werden. Die Cluster und die Startzeiten, bei denen die Teilreservierungen durchgef{\"u}hrt werden, ermittelt ein Co-Reservierungs-Algorithmus erst bei der Anfragebearbeitung. Die Benutzer k{\"o}nnen die Startzeit in der Anfrage eingrenzen, in dem sie eine fr{\"u}heste Startzeit und eine Deadline angeben. In den bisher entwickelten Reservierungsverfahren k{\"o}nnen Benutzer nur starre Co-Reservierungsanfragen stellen, in denen sie f{\"u}r alle Attribute der Teilreservierungen exakte Werte angeben m{\"u}ssen. Eine flexible Co-Reservierungsanfrage erlaubt einem Grid-Reservierungsdienst optimierte Reservierungsvarianten durchzuf{\"u}hren, da er aus vielen Reservierungsvarianten ausw{\"a}hlen kann. Die Anwendungen von lokalen Benutzern k{\"o}nnen durch die Grid-Reservierungen verz{\"o}gert werden. Bei der Auswahl der Reservierungsvarianten kann ein Grid-Reservierungsdienst dies ber{\"u}cksichtigen und den negativen Einfluß der Grid-Reservierungen verringern. Bei zwei Co-Reservierungs-Algorithmen werden auch zus{\"a}tzliche Sortiervorgaben des Klienten bei der Auswahl der Reservierungsvarianten beachtet. Die Algorithmen wurden durch Simulationen mit dem Workload eines realen großen Supercomputers ausgewertet. Die Untersuchungen zeigen, daß sowohl die lokalen als auch die Grid-Benutzer von den flexiblen Anfragen profitieren k{\"o}nnen. Den lokalen Benutzern wurden die Ressourcen weniger oft durch zu fr{\"u}h gestellte Reservierungsanfragen entzogen. Die Grid- Benutzer k{\"o}nnen ihrerseits komfortabel eine optimierte Reservierungsvariante durchf{\"u}hren lassen.}, language = {de} } @misc{Moser2006, type = {Master Thesis}, author = {Moser, Monika}, title = {Platzierung von Replikaten in Verteilten Systemen}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9995}, school = {Zuse Institute Berlin (ZIB)}, year = {2006}, language = {de} } @misc{Riemer2006, type = {Master Thesis}, author = {Riemer, Alexander}, title = {Accuracy, Stability, Convergence of Rigorous Thermodynamic Sampling Methods}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10052}, school = {Zuse Institute Berlin (ZIB)}, year = {2006}, language = {en} } @misc{Berthold2006, type = {Master Thesis}, author = {Berthold, Timo}, title = {Primal Heuristics for Mixed Integer Programs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10293}, school = {Zuse Institute Berlin (ZIB)}, year = {2006}, abstract = {A lot of problems arising in Combinatorial Optimization and Operations Research can be formulated as Mixed Integer Programs (MIP). Although MIP-solving is an NP-hard optimization problem, many practically relevant instances can be solved in reasonable time. In modern MIP-solvers like the branch-cut-and-price-framework SCIP, primal heuristics play a major role in finding and improving feasible solutions at the early steps of the solution process. This helps to reduce the overall computational effort, guides the remaining search process, and proves the feasibility of the MIP model. Furthermore, a heuristic solution with a small gap to optimality often is sufficient in practice. We investigate 16 different heuristics, all of which are available in SCIP. Four of them arise from the literature of the last decade, nine are specific implementations of general heuristic ideas, three have been newly developed. We present an improved version of the feasibility pump heuristic by Fischetti et al., which in experiments produced solutions with only a third of the optimality gap compared to the original version. Furthermore, we introduce two new Large Neighborhood Search (LNS) heuristics. Crossover is an LNS improvement heuristic making use of similarities of diverse MIP solutions to generate new incumbent solutions. RENS is an LNS rounding heuristic which evaluates the space of all possible roundings of a fractional LP-solution. This heuristic makes it possible to determine whether a point can be rounded to an integer solution and which is the best possible rounding. We conclude with a computational comparison of all described heuristics. It points out that a single heuristic on its own has only a slight impact on the overall performance of SCIP, but the combination of all of them reduces the running time by a factor of two compared to a version without any heuristics.}, language = {en} } @misc{Clasen2005, type = {Master Thesis}, author = {Clasen, Malte}, title = {Beleuchtung von Landschaften in interaktiver Darstellung}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9906}, school = {Zuse Institute Berlin (ZIB)}, year = {2005}, abstract = {Inhalt dieser Diplomarbeit ist ein Beleuchtungs- und Visualisierungsmodell f{\"u}r Pflanzen im interaktiven Landschaftsrendering. Ziel ist die qualitativ hochwertige Darstellung von einzelnen Individuen nahe des Betrachters, der seine Position in einer ansonsten statischen Szene frei w{\"a}hlen kann. Um dies zu erreichen wird zun{\"a}chst vorgestellt, wie ausgehend von einfachen 3D-Modellen und Materialien ein physikalisch basiertes Reflexionsmodell parametrisiert werden kann. Grund hierf{\"u}r ist der oftmals vorhandene umfangreiche Datenbestand, der auf die OpenGL-Materialien oder {\"a}hnliche Shader optimiert ist. Anschließend wird gezeigt, wie die Echtzeit-Renderingtechniken Shadow Mapping und Precomputed Radiance Transfer kombiniert werden k{\"o}nnen, um sowohl exakte hochfrequente direkte Beleuchtung als auch niederfrequentes indirektes Streulicht zu ber{\"u}cksichtigen. Diese Kombination wird an Hand der Pfad-Notation des Monte-Carlo-Path-Tracing eingef{\"u}hrt und begr{\"u}ndet.}, language = {de} } @misc{Pham2005, type = {Master Thesis}, author = {Pham, The Anh}, title = {Einbettung neuer Verwaltungsmethoden in die hierarchische Dateisystemsicht}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10014}, school = {Zuse Institute Berlin (ZIB)}, year = {2005}, abstract = {Die hierarchische Organisation von Dateien beherrscht Computersysteme seit vielen Jahren und wird sich vermutlich auch in Zukunft weiterhin durchsetzen. Dennoch st{\"o}ßt diese Verwaltungsmethode in einem klassischen hierarchischen Dateisystem bei dem j{\"a}hrlichen rasanten Zuwachs an neuen Daten an ihre Grenzen, auch wenn Nutzer eine ausgefeilte Verzeichnisstruktur mit einer disziplinierten Namensgebung konsequent auf- und ausbauen. Um den {\"U}berblick {\"u}ber die Dateien zu behalten, werden in dieser Arbeit neue Verwaltungsmethoden vorgestellt und in die hierarchische Dateisystemsicht eingebettet. Auf der Basis des hierarchischen Dateisystems bietet ein metadatenbasiertes Dateisystem neben dem hierarchischen Zugriff noch einen flexiblen, assoziativen Zugriff auf Dateien {\"u}ber virtuelle Objekte, indem Suchmethoden in Form einer Anfrage auf in einer Datenbank gespeicherte Index- und Metadaten angewendet werden. Das Ergebnis dieser Abfrage wird mit Hilfe von virtuellen Verzeichnissen und virtuellen Dateien in einer {\"u}bersichtlichen Form dargestellt, so dass eine Nutzung der hierarchischen Sicht weiterhin intuitiv fortgesetzt wird. Das Datenmanagementsystem ZIBDMS, welches einen verteilten Metadatenkatalog und einen Dateireplikationskatalog beinhaltet, erm{\"o}glicht es, die oben genannten Verwaltungsmethoden f{\"u}r die NFS-Schnittstelle, CORBA-Middleware und Web Services transparent zu implementieren. Zudem stellt ZIBDMS weitere neue Dateiverwaltungsmethoden zur Verf{\"u}gung, die sich in die hierarchische Dateisystemsicht integrieren lassen. Metadaten in Form von Attribut-Wert-Paaren lassen sich als virtuelle Datei darstellen und editieren. Eine Collection bietet die M{\"o}glichkeit, Dateien in einem logischen virtuellen Ordner zu organisieren. Mit einem Dependency-Graph lassen sich Dateien zueinander in Relation stellen, so dass eine Linkstruktur zwischen Dateien ausgedr{\"u}ckt werden kann. Das Verweiskonzept eines klassischen hierarchischen Dateisystems wird im ZIBDMS um eine neue Verweisart Weak-Link erweitert, um einen aktualisierbaren, konsistenten und zyklenfreien symbolischen Link anzubieten. In einer hierarchischen Sicht l{\"a}sst sich durch Verweise ein Baum bilden, in dem eine Navigation und Verweisauflistung m{\"o}glich sind, was außer ZIBDMS noch kein anderes System bietet.}, language = {de} } @misc{Witte2005, type = {Master Thesis}, author = {Witte, Jochen}, title = {Implementierung einer NFS Schnittstelle im Kontext eines Grid-Datenmanagement-Systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10081}, school = {Zuse Institute Berlin (ZIB)}, year = {2005}, abstract = {Diese Arbeit dokumentiert den Entwurf und die Implementierung einer NFS-Schnittstelle zum ZIBDMS. Das ZIBDMS, welches derzeit am Zuse-Institut Berlin entwickelt wird, ist ein Managementsystem f{\"u}r verteilte Daten in heterogenen Umgebungen [10]. Es soll die einfache Benutzung von Mechanismen zur Replikation sowie neue M{\"o}glichkeiten des Zugriffs und der Verwaltung von Metadaten und Datenobjekten erm{\"o}glichen. Dem Nutzer bietet das System verschiedene Sichten: Neben der klassischen, hierarchischen Sicht mit Verzeichnissen und Dateien wird auch eine attributbasierte Zugriffsmethode angeboten, in der Datenobjekte ausschließlich {\"u}ber Attribut/Wert-Paare referenziert werden. F{\"u}r den Benutzer transparent, soll sich das System im Hinblick auf die Verf{\"u}gbarkeit von Daten und Metadaten selbstt{\"a}tig optimieren. Um Skalierbarkeit gew¨ahrleisten zu k{\"o}nnen, werden intern Peer-to-Peer- Techniken entwickelt und benutzt. Die NFS-Schnittstelle erh{\"o}ht die Nutzbarkeit des Systems, da Client- Implementierungen f{\"u}r nahezu alle Betriebssysteme zur Verf{\"u}gung stehen. Der Benutzer kann so {\"u}ber das gewohnte Dateisystem Daten und Metadaten pflegen, ohne spezifisches Vorwissen zu ben{\"o}tigen. In dieser Arbeit wird untersucht, inwiefern sich die Semantik des ZIBDMS auf jene des NFS-Protokolls {\"u}bertragen l{\"a}ßt. Weiterhin wird das Konzept von Pseudodateien beschrieben und diskutiert, inwiefern es eine brauchbare L{\"o}sung darstellt, den im Vergleich zur NFS-Semantik wesentlich gr{\"o}ßeren Funktionsumfang des ZIBDMS f{\"u}r den Anwender nutzbar zu machen. Pseudodateien sind nicht-persistente Objekte, welche f{\"u}r den Benutzer als regul{\"a}re Datei sichtbar werden und die erweiterte Funktionalit{\"a}ten wie die Bearbeitung von Metadaten oder die Platzierung von Replikaten {\"u}ber die Dateisystem-Sicht des NFS zur Verf{\"u}gung stellen sollen. Schließlich werden Leistungsmessungen an den benutzten Komponenten des ZIBDMS vorgenommen und vergleichbaren Systemen gegen {\"u}bergestellt. Die Aufmerksamkeit liegt hier auf der zugrundeliegenden Katalog-Technologie sowie dem durch das NFS-Protokoll verursachten Overhead.}, language = {de} } @misc{Raack2005, type = {Master Thesis}, author = {Raack, Christian}, title = {Employing Mixed-Integer Rounding in Telecommunication Network Design}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10023}, school = {Zuse Institute Berlin (ZIB)}, year = {2005}, abstract = {In dieser Diplomarbeit werden grundlegende Probleme der kostenoptimalen Dimensionierung von Telekommunikationsnetzwerken untersucht. Diese werden als lineare gemischt ganzzahlige Programme formuliert, wobei sich in der Modellierung auf die Konzepte Routing und Kapazit{\"a}tszuweisung beschr{\"a}nkt wird. Es werden parallel drei {\"u}bliche, aus der Praxis motivierte M{\"o}glichkeiten behandelt, die auf gerichteten oder ungerichteten Kanten eines Netzwerkes installierte Kapazit{\"a}t zu nutzen. Diese unterscheiden wir als DIrected, BIdirected und UNdirected. Die studierten Probleme treten als Relaxierungen vieler realistischer Fragestellungen der Netzwerkoptimierung auf. Sie enthalten elementare Strukturen, deren Studium ausschlaggebend ist f{\"u}r das Verst{\"a}ndnis komplexerer Modelle. Letztere k{\"o}nnen zus{\"a}tzliche Erfordernisse ber{\"u}cksichtigen, wie zum Beispiel die Ausfallsicherheit von Netzwerken. Zur L{\"o}sung solcher NP-schweren Optimierungsprobleme werden erfolgreich Branch \& Bound und Schnittebenenverfahren kombiniert (Branch \& Cut). F{\"u}r die Wirksamkeit dieser Algorithmen ist es sehr n{\"u}tzlich, m{\"o}glichst genaue Kenntnisse der Struktur der Seitenfl{\"a}chen der zugrundeliegenden Polyeder zu haben, welche die konvexe H{\"u}lle der L{\"o}sungsmenge beschreiben. Es sind starke g{\"u}ltige Ungleichungen zu finden, welche hochdimensionale Seitenfl{\"a}chen oder sogar Facetten definieren. Diese sollten zudem schnell separiert werden k{\"o}nnen und die numerische Stabilit{\"a}t der Algorithmen m{\"o}glichst nicht beeinflussen. Diese Arbeit besch{\"a}ftigt sich im Wesentlichen mit der sehr allgemeinen Rundungstechnik Mixed- Integer Rounding (MIR) zur Verst{\"a}rkung g{\"u}ltiger Ungleichungen unter Verwendung der Ganzzahligkeitsnebenbedingungen. Es wird eine MIR-Prozedur motiviert, bestehend aus den Schritten Aggregieren, Substituieren, Komplementieren und Skalieren, welche durch Ausnutzung der Struktur der gegebenen Parameter zu einer g{\"u}ltigen Basisungleichung f{\"u}hrt, die dann durch MIR eine starke und oft facetten-induzierende Ungleichung gibt. Es werden verschieden Klassen solcher Ungleichungen untersucht und auf ihre Praxistauglichkeit beim Einsatz in Branch \& Cut-Verfahren getestet. Nach einer kurzen Einf{\"u}hrung werden in Kapitel 2 die f{\"u}r uns in dieser Diplomarbeit relevanten Probleme definiert. Kapitel 3 gibt eine ausf{\"u}hrliche {\"U}bersicht {\"u}ber die Technik MIR.Wir besch{\"a}ftigen uns vor allen Dingen mit den Begriffen Superadditivit{\"a}t und Lifting und behandeln Aspekte wie Numerik und beschr{\"a}nkte Variablen. Kapitel 4 und Kapitel 5 umfassen Untersuchungen zu so genannten cut sets. Diese Polyeder werden durch Schnitte in Netzwerken definiert und relaxieren die von uns behandelten Probleme. Haupts{\"a}chlich durch MIR entwickeln wir sowohl neue als auch bekannte Klassen von facetten-definierenden Ungleichungen f{\"u}r cut sets, wobei strukturelle Unterschiede herausgearbeitet werden, die durch die drei verschiedenen Typen der Kapzit{\"a}tsbereitstellung und durch beschr{\"a}nkte Variablen entstehen. Als ein zentrales Resultat wird bewiesen unter welchen Bedingungen facetten-induzierende Ungleichungen f{\"u}r cut sets auch Facetten der zugeh{\"o}rigen relaxierten Polyeder sind. Im Kapitel 6 geben wir weitere Typen von MIR-Ungleichungen an, die auf anderen Netzwerkstrukturen basieren und weisen ferner auf offene Fragen sowie interessante Ideen hin. Das Kapitel 7 widmet sich schließlich der Entwicklung und Implementation von Separationsalgorithmen. Wir testen einige der entwickelten Ungleichungsklassen mit Hinblick auf Ihre Wirksamkeit zur L{\"o}sung von realistischen Problemen der Netzwerkdimensionierung aus der Telekommunikation und diskutieren die Ergebnisse.}, language = {de} } @misc{Heinz2005, type = {Master Thesis}, author = {Heinz, Stefan}, title = {Policies for Online Target Date Assignment Problems: Competitive Analysis versus Expected Performance}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9933}, school = {Zuse Institute Berlin (ZIB)}, year = {2005}, language = {en} } @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} }