Bibliothek

Beschreibung: Asymptotic analyses of the three dimensional compressible flow equations coupled with transport equations for the mixing ratios of water vapour, cloud water and rain water are described. We obtain reduced systems of equations for two particular regimes of length and time scales: Models for the long time evolution of deep convective columns and for the short time evolution of shallow convective layers. The asymptotic deep convective column model is anelastic, yet the vertical motion is pressure free, i.e., it evolves freely in interaction with buoyancy while the horizontal divergence adjusts to fullfil the anelastic constraint. The perturbation pressure guaranteeing compliance with the horizontal divergence constraint obeys a Poisson-type equation. Surprisingly, the vertical velocity plays an important role in the horizontal dynamics through the Coriolis term. The vertical acceleration in a saturated column is directly determined by the buoyancy induced by potential temperature differences relative to the background stratification. This potential temperature deviation is a conserved quantity. Evaporation is the only important microphysical process in the undersaturated regime. The evaporation rate depends on the saturation deficit and the amount of rain water present and determines the (downward) vertical velocity and the distribution of water vapour. To connect the deep convective column solutions to top and bottom boundary conditions, a different flow regime needs to be accounted for. Within shallow layers whose depth is comparable to the column diameters, adjustment to physical boundary conditions can take place. This is the second regime considered in this report. The shallow convective layer regime is shown to be asymptotically described by Boussinesq-type equations. These equations are closed by evolution equations which show that, in the saturated regime, the distributions of potential temperature and cloud water are determined by a condensation rate that is directly proportional to the vertical velocity. In the undersaturated regime, the potential temperature distribution is determined by the amount of rain present, since the water vapour in this case is shown to be a conserved quantity. In both regimes the distribution of rain water depends on the rain water flux.

Beschreibung: By use of asymptotic analysis Carqué et al. [ZIB-Report 08-03] derived an asymptotic column model for deep convective clouds based on the three dimensional compressible flow equations and a bulk microphysics parameterization. In the present study we check the plausibility of the reduced model equations by comparing implications of the model for the scaling of various terms in the governing equations with those extracted from large eddy simulation data based on the computational model UCLA-LES1.1. This code solves an anelastic system of equations with complete droplet based microphysics and LES closures. We observe that the simulation data corroborate the basic assumptions of the asymptotic analysis and the main conclusions implied by the asymptotically reduced model. The code output reflects the scales of space and time: The deep convective clouds show an anisotropic structure where the horizontal scale is considerably narrower than the vertical scale; with a period of about 20 min, from emergence to breakup, the life cycle of one particular deep convective cloud corresponds exactly to the reference time of the reduced model. The characteristic properties of dynamics as predicted by the reduced model are also reflected in the simulation data: The horizontal flow is controlled by the pressure field; the vertical velocity develops freely independent of pressure over the depth of the convective column; the vertical velocity is directly determined by the buoyancy induced by the potential temperature deviation relative to the background stratification. With respect to grid resolution we observe that refining the spatial step size of the equidistant computational grid from 125 m to 62.5 m does not influence the results: Even with the coarser grid the relevant physical phenomena are sufficiently resolved. Somewhat surprisingly, the Coriolis term involving vertical velocity and acting on the horizontal (east-west) velocity component appears at leading order in the asymptotics. Accordingly, we expected to find a nontrivial impact of this Coriolis effect on the horizontal flow velocity components within columns of updrafts. However, switching the term on and off in subsequent simulations did not sizeably affect the results.

Beschreibung: A theoretical and numerical small-scale study of the evaporative cooling phenomenon that might appear in the stratocumulus-topped boundary layers is presented. An ideal configuration of a cloud-top mixing layer is considered as defined by two nonturbulent horizontal layers, stably stratified and with buoyancy reversal within a certain range of mixture fractions due to the evaporative cooling. Linear stability analysis of the shear-free configuration is employed to provide a new interpretation of the buoyancy reversal parameter, namely, in terms of a time-scale ratio between the unstable and the stable modes of the system. An incompressible high-order numerical algorithm to perform direct numerical simulation of the configuration is described and two-dimensional simulations of single-mode perturbations are discussed. These simulations confirm the role of the different parameters identified in the linear stability analysis and show that convoluted flow patterns can be generated by the evaporative cooling even for the low levels of buoyancy reversal found in stratocumulus clouds. They also show that there is no enhancement of entrainment of upper layer fluid in the shear-free configuration, and mixing enhancement by the evaporative cooling is restricted to the lower layer.

Beschreibung: Im Rahmen dieser Arbeit wurde ein individuell anpassungsfähiges Modell entwickelt und implementiert, das die Perfusion in menschlichen soliden Tumoren beschreibt und für verschiedene Zeitpunkte w¨ahrend regionaler Hyperthermie ein lokal abhängiges Temperaturprofil berechnet. Da vor jeder Simulation alle wichtigen Parameter anhand von Ultraschall-, MRT- oder Angiogrammbildern individuell bestimmt werden können, wird eine patientenspezifische Aussage ¨uber das intratumorale Antwortverhalten bereits vor der eigentlichen Behandlung möglich. In Abh¨angigkeit von der Qualität der zur Verfügung stehenden anatomischen Daten über das zu simulierende Gebiet kann das Modell beliebig verfeinert oder bei Mangel an detaillierten Informationen auch mit Minimaldaten und reduzierter räumlicher Genauigkeit benutzt werden. Die für eine Simulation benötigten 2- oder 3- dimensionalen Geometrien können leicht mit der am ZIB entwickelten Software Amira erstellt und zur Berechnung in KARDOS, einem ebenfalls am ZIB implementierten Löser für nichtlineare partielle Differentialgleichungen, eingelesen werden. Mit Hilfe dieses Modells wird eine einfache, aber realistische und aussagekräftige Simulation für die Therapieplanung einer klinischen Hyperthermieanwendung ermöglicht, die innerhalb kurzer Zeit vorbereitet und durchgeführt werden kann.

Beschreibung: In dieser Arbeit werden effiziente Co-Reservierungs-Algorithmen vorgestellt, mit denen Rechenressourcen mehrerer Cluster im Grid reserviert werden können. Es werden fünf Algorithmen vorgestellt, die flexible Co-Reservierungsanfragen ermöglichen. In einer Co-Reservierungsanfrage müssen die angeforderten CPUs der Teilreservierungen exakt festgelegt werden. Die Cluster und die Startzeiten, bei denen die Teilreservierungen durchgeführt werden, ermittelt ein Co-Reservierungs-Algorithmus erst bei der Anfragebearbeitung. Die Benutzer können die Startzeit in der Anfrage eingrenzen, in dem sie eine früheste Startzeit und eine Deadline angeben. In den bisher entwickelten Reservierungsverfahren können Benutzer nur starre Co-Reservierungsanfragen stellen, in denen sie für alle Attribute der Teilreservierungen exakte Werte angeben müssen. Eine flexible Co-Reservierungsanfrage erlaubt einem Grid-Reservierungsdienst optimierte Reservierungsvarianten durchzuführen, da er aus vielen Reservierungsvarianten auswählen kann. Die Anwendungen von lokalen Benutzern können durch die Grid-Reservierungen verzögert werden. Bei der Auswahl der Reservierungsvarianten kann ein Grid-Reservierungsdienst dies berücksichtigen und den negativen Einfluß der Grid-Reservierungen verringern. Bei zwei Co-Reservierungs-Algorithmen werden auch zusä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önnen. Den lokalen Benutzern wurden die Ressourcen weniger oft durch zu früh gestellte Reservierungsanfragen entzogen. Die Grid- Benutzer können ihrerseits komfortabel eine optimierte Reservierungsvariante durchführen lassen.

Beschreibung: 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ätszuweisung beschränkt wird. Es werden parallel drei übliche, aus der Praxis motivierte Möglichkeiten behandelt, die auf gerichteten oder ungerichteten Kanten eines Netzwerkes installierte Kapazitä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ür das Verständnis komplexerer Modelle. Letztere können zusätzliche Erfordernisse berücksichtigen, wie zum Beispiel die Ausfallsicherheit von Netzwerken. Zur Lösung solcher NP-schweren Optimierungsprobleme werden erfolgreich Branch & Bound und Schnittebenenverfahren kombiniert (Branch & Cut). Für die Wirksamkeit dieser Algorithmen ist es sehr nützlich, möglichst genaue Kenntnisse der Struktur der Seitenflächen der zugrundeliegenden Polyeder zu haben, welche die konvexe Hülle der Lösungsmenge beschreiben. Es sind starke gültige Ungleichungen zu finden, welche hochdimensionale Seitenflächen oder sogar Facetten definieren. Diese sollten zudem schnell separiert werden können und die numerische Stabilität der Algorithmen möglichst nicht beeinflussen. Diese Arbeit beschäftigt sich im Wesentlichen mit der sehr allgemeinen Rundungstechnik Mixed- Integer Rounding (MIR) zur Verstärkung gü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ültigen Basisungleichung fü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ührung werden in Kapitel 2 die für uns in dieser Diplomarbeit relevanten Probleme definiert. Kapitel 3 gibt eine ausführliche Übersicht über die Technik MIR.Wir beschäftigen uns vor allen Dingen mit den Begriffen Superadditivität und Lifting und behandeln Aspekte wie Numerik und beschrä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ächlich durch MIR entwickeln wir sowohl neue als auch bekannte Klassen von facetten-definierenden Ungleichungen für cut sets, wobei strukturelle Unterschiede herausgearbeitet werden, die durch die drei verschiedenen Typen der Kapzitätsbereitstellung und durch beschränkte Variablen entstehen. Als ein zentrales Resultat wird bewiesen unter welchen Bedingungen facetten-induzierende Ungleichungen für cut sets auch Facetten der zugehö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ösung von realistischen Problemen der Netzwerkdimensionierung aus der Telekommunikation und diskutieren die Ergebnisse.

Beschreibung: 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ür verteilte Daten in heterogenen Umgebungen [10]. Es soll die einfache Benutzung von Mechanismen zur Replikation sowie neue Möglichkeiten des Zugriffs und der Verwaltung von Metadaten und Datenobjekten ermö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 über Attribut/Wert-Paare referenziert werden. Für den Benutzer transparent, soll sich das System im Hinblick auf die Verfügbarkeit von Daten und Metadaten selbsttätig optimieren. Um Skalierbarkeit gew¨ahrleisten zu können, werden intern Peer-to-Peer- Techniken entwickelt und benutzt. Die NFS-Schnittstelle erhöht die Nutzbarkeit des Systems, da Client- Implementierungen für nahezu alle Betriebssysteme zur Verfügung stehen. Der Benutzer kann so über das gewohnte Dateisystem Daten und Metadaten pflegen, ohne spezifisches Vorwissen zu benötigen. In dieser Arbeit wird untersucht, inwiefern sich die Semantik des ZIBDMS auf jene des NFS-Protokolls übertragen läßt. Weiterhin wird das Konzept von Pseudodateien beschrieben und diskutiert, inwiefern es eine brauchbare Lösung darstellt, den im Vergleich zur NFS-Semantik wesentlich größeren Funktionsumfang des ZIBDMS für den Anwender nutzbar zu machen. Pseudodateien sind nicht-persistente Objekte, welche für den Benutzer als reguläre Datei sichtbar werden und die erweiterte Funktionalitäten wie die Bearbeitung von Metadaten oder die Platzierung von Replikaten über die Dateisystem-Sicht des NFS zur Verfügung stellen sollen. Schließlich werden Leistungsmessungen an den benutzten Komponenten des ZIBDMS vorgenommen und vergleichbaren Systemen gegen übergestellt. Die Aufmerksamkeit liegt hier auf der zugrundeliegenden Katalog-Technologie sowie dem durch das NFS-Protokoll verursachten Overhead.

Beschreibung: 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.

Beschreibung: Mobile cellular communcication is a key technology in today's information age. Despite the continuing improvements in equipment design, interference is and will remain a limiting factor for the use of radio communication. This Ph. D. thesis investigates how to prevent interference to the largest possible extent when assigning the available frequencies to the base stations of a GSM cellular network. The topic is addressed from two directions: first, new algorithms are presented to compute "good" frequency assignments fast; second, a novel approach, based on semidef inite programming, is employed to provide lower bounds for the amount of unavoidable interference. The new methods proposed for automatic frequency planning are compared in terms of running times and effectiveness in computational experiments, where the planning instances are taken from practice. For most of the heuristics the running time behavior is adequate for inter active planning; at the same time, they provide reasonable assignments from a practical point of view (compared to the currently best known, but substantially slower planning methods). In fact, several of these methods are successfully applied by the German GSM network operator E-Plus. The currently best lower bounds on the amount of unavoidable (co-channel) interference are obtained from solving semidefinite programs These programs arise as nonpolyhedral relaxation of a minimum /c-parti tion problem on complete graphs. The success of this approach is made plausible by revealing structural relations between the feasible set of the semidefinite program and a polytope associated with an integer linear programming formulation of the minimum ^-partition problem. Comparable relations are not known to hold for any polynomial time solvable polyhedral relaxation of the minimum ^-partition problem. The appli cation described is one of the first of semidefinite programming for large industrial problems in combinatorial optimization.

Beschreibung: In der vorliegenden Dissertation untersuchen wir die Optimierung von ausfallsicheren Telekommunikationsnetzwerken. Wir präsentieren unterschiedliche gemischt-ganzzahlige Modelle für die diskrete Kapazitätsttruktu,, sowie für die Sicherung des Netzes gegen den Ausfall einzelner Komponenten. Die Modelle wurden in einer Kooperation mit der E-Plus Mobilfunk GmbH verwendet. Die theoretischen Resultate wurden in Algorithmen umgesetzt und in das von uns entiickllte Netzwerksoptimierungswerkzeug Discnet (Dimensioning Survivable Capaiitated NETworks) integriert, welches seit mehreren Jahren in der Planung bei E-Plus eingesetzt wird. Wir betrachten das Transportnetzllanungsproblem eines Telekommunikationsanbieters. Dieses Problem setzt auf logischen Kommunikattonsanforerrungen zwischen den Standorten (Knoten) des zu planenden Netzes und potentiell inslallirrbaren Verbindungen (Kanten) zwischen derselben Knotenmenge auf. Ein Kapazitätsmodell stellt die Information bereit, welche Kapazitäten auf den potentiellen Kanten verfügbar sind. Wir betrachten zwei Modelle. Entweder ist eine explizite Liste der verfügbaren Kapazittten gegeben oder eine Menge von sogenannten Basiskapazitäten, die auf jeder Kante indiviuelll kombiniert werden können. Die Basiskapazitäten müßen paarweise ganzzahlige Vielfache voneinander sein. Man beachte, daß diese Eigenschaft von den internationalen Standards PDH und SDH erfüllt wiid. Ein Ausfallsicherheitsmodell stellt die Information bereit, wie das zu planende Netz gegen den Ausfall einzelner Netzkomponenten geschützt werden soll. Wir betrachten sinnvolle Kombinationen der Modelle Diversification, Reservation und Path Restoration. Das erste Modell garantiert Ausfallsicherheit durch kommunikationsbedarfsabhängige Beschränkung des Prozentsatzes, der durch einzelne Netzkomponenten geroutet werden darf. Bei den beiden anderen Modelle können Kommunikationsbedarfe bei Ausfall einer Netzkomponente auf unterschiedliche Weise neu geroutet werden. Ziel der Planung ist eine ktstenminimlle Kapatitätsentscheidung, die eine Routenllanung aller Kommunikationsbedarfe gemäß den Ausfallsicherheitsanforderungen ermöglicht. Wir entwickeln ein Schnittebenenverfahren zur Lösung der betrachteten Optimiergngsrrobleme. Zu diesem Zweck untersuchen wir Polyeder, die mit den verschiedenen Problemen assoziiert sind. Wir präsentieren neue Klassen von Ungleichungen, entwickeln Separationsalgorithmen und Heuristiken. Mit dem Schnittebenenverfahren werden untere und obere Schranken für den Wert von Oitimallösungen berechnet, und daher ist es möglich, Qualitätsgarantien für die berechneten Löungen anzugeben. Parallel zur Beschreibung der implementierten Algorithmen präsentieren wir umfangreiche Tests mit praktisch relevanten Daten, die zu Problemen mit mehr als 2 Billionen Variablen führen.