• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 7
  • 3
  • 1
  • Tagged with
  • 11
  • 11
  • 11
  • 10
  • 10
  • 6
  • 6
  • 6
  • 5
  • 5
  • 4
  • 4
  • 4
  • 4
  • 4
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Algebraic dynamic programming over general data structures

Höner zu Siederdissen, Christian, Prohaska, Sonja J., Stadler, Peter F. 29 June 2016 (has links) (PDF)
Background: Dynamic programming algorithms provide exact solutions to many problems in computational biology, such as sequence alignment, RNA folding, hidden Markov models (HMMs), and scoring of phylogenetic trees. Structurally analogous algorithms compute optimal solutions, evaluate score distributions, and perform stochastic sampling. This is explained in the theory of Algebraic Dynamic Programming (ADP) by a strict separation of state space traversal (usually represented by a context free grammar), scoring (encoded as an algebra), and choice rule. A key ingredient in this theory is the use of yield parsers that operate on the ordered input data structure, usually strings or ordered trees. The computation of ensemble properties, such as a posteriori probabilities of HMMs or partition functions in RNA folding, requires the combination of two distinct, but intimately related algorithms, known as the inside and the outside recursion. Only the inside recursions are covered by the classical ADP theory. Results: The ideas of ADP are generalized to a much wider scope of data structures by relaxing the concept of parsing. This allows us to formalize the conceptual complementarity of inside and outside variables in a natural way. We demonstrate that outside recursions are generically derivable from inside decomposition schemes. In addition to rephrasing the well-known algorithms for HMMs, pairwise sequence alignment, and RNA folding we show how the TSP and the shortest Hamiltonian path problem can be implemented efficiently in the extended ADP framework. As a showcase application we investigate the ancient evolution of HOX gene clusters in terms of shortest Hamiltonian paths. Conclusions: The generalized ADP framework presented here greatly facilitates the development and implementation of dynamic programming algorithms for a wide spectrum of applications.
2

Algebraic dynamic programming over general data structures

Höner zu Siederdissen, Christian, Prohaska, Sonja J., Stadler, Peter F. January 2016 (has links)
Background: Dynamic programming algorithms provide exact solutions to many problems in computational biology, such as sequence alignment, RNA folding, hidden Markov models (HMMs), and scoring of phylogenetic trees. Structurally analogous algorithms compute optimal solutions, evaluate score distributions, and perform stochastic sampling. This is explained in the theory of Algebraic Dynamic Programming (ADP) by a strict separation of state space traversal (usually represented by a context free grammar), scoring (encoded as an algebra), and choice rule. A key ingredient in this theory is the use of yield parsers that operate on the ordered input data structure, usually strings or ordered trees. The computation of ensemble properties, such as a posteriori probabilities of HMMs or partition functions in RNA folding, requires the combination of two distinct, but intimately related algorithms, known as the inside and the outside recursion. Only the inside recursions are covered by the classical ADP theory. Results: The ideas of ADP are generalized to a much wider scope of data structures by relaxing the concept of parsing. This allows us to formalize the conceptual complementarity of inside and outside variables in a natural way. We demonstrate that outside recursions are generically derivable from inside decomposition schemes. In addition to rephrasing the well-known algorithms for HMMs, pairwise sequence alignment, and RNA folding we show how the TSP and the shortest Hamiltonian path problem can be implemented efficiently in the extended ADP framework. As a showcase application we investigate the ancient evolution of HOX gene clusters in terms of shortest Hamiltonian paths. Conclusions: The generalized ADP framework presented here greatly facilitates the development and implementation of dynamic programming algorithms for a wide spectrum of applications.
3

Optimal Velocity and Power Split Control of Hybrid Electric Vehicles

Uebel, Stephan, Bäker, Bernard 03 March 2017 (has links) (PDF)
An assessment study of a novel approach is presented that combines discrete state-space Dynamic Programming and Pontryagin’s Maximum Principle for online optimal control of hybrid electric vehicles (HEV). In addition to electric energy storage and gear, kinetic energy and travel time are considered states in this paper. After presenting the corresponding model using a parallel HEV as an example, a benchmark method with Dynamic Programming is introduced which is used to show the solution quality of the novel approach. It is illustrated that the proposed method yields a close-to-optimal solution by solving the optimal control problem over one hundred thousand times faster than the benchmark method. Finally, a potential online usage is assessed by comparing solution quality and calculation time with regard to the quantization of the state space.
4

Energiemanagement für eine parallele Hybridfahrzeugarchitektur

Helbing, Maximilian 06 February 2015 (has links) (PDF)
Durch die Integration mindestens eines weiteren Energiewandlers in den Antriebsstrang gewinnen parallele Hybridfahrzeuge einen zusätzlichen Freiheitsgrad gegenüber konventionellen Fahrzeugen. Neben der Auslegung und Effizienz der einzelnen Antriebskomponenten, ist vor allem die Nutzung dieses zusätzlichen Freiheitsgrades entscheidend dafür verantwortlich, inwiefern die beim Betrieb eines Hybridfahrzeugs erwünschten Ziele, wie die Minimierung des Kraftstoffverbrauchs oder der Abgasemissionen, erreicht werden können. Zuständig dafür sind sogenannte Betriebsstrategien. In einem ersten Schritt gibt die vorliegende Diplomarbeit einen Überblick aktueller Betriebsstrategieansätze für Fahrzeuge mit einer parallelen Hybridarchitektur und stellt ausgewählte Beiträge wertend gegenüber. Anschließend wird mit der optimierungsbasierten Equivalent Consumption Minimization Strategy (ECMS) ein vielversprechender Ansatz in ein MATLAB/Simulink-Längsdynamikmodell umgesetzt. Die für diesen Ansatz maßgebliche Bestimmung des Äquivalenzfaktors erfolgt dabei ohne Verwendung von Prädiktionsdaten. Eine Gegenüberstellung der erzielten Kraftstoffverbrauchswerte zu denen einer regelbasierten Betriebsstrategie, zeigt die Vorteile des implementierten ECMS-Ansatzes. Um den unterschiedlichen Ladezuständen am Fahrtende gerecht zu werden, wird eine ladungsabhängige Kraftstoffkorrektur vorgestellt. / By integrating at least one additional energy converter into the drive train, parallel hybrid vehicles gain an additional degree of freedom compared to conventional vehicles. In addition to the design and efficiency of the individual drive train components, especially the use of this additional degree of freedom is the key responsible to achieve the desired goals in the operation of a hybrid vehicle, such as minimizing fuel consumption and exhaust emissions. Responsible for this are so-called supervisory strategies. In a first step, the present thesis provides an overview of current supervisory control strategies for vehicles with a parallel hybrid architecture and compares selected approaches. In a second step, a promising Equivalent Consumption Minimization Strategy (ECMS) is chosen and implemented in a MATLAB/Simulink-longitudinal dynamics model. This approach relates on the determination of the equivalence factor which is carried out without the use of prediction data. A comparison of the fuel consumption, obtained for a rule-based supervisory strategy, shows the advantages of the implemented ECMS approach. To consider the different states of charge at the end of the trip, a charge-dependent fuel correction will be presented.
5

Optimal Velocity and Power Split Control of Hybrid Electric Vehicles

Uebel, Stephan, Bäker, Bernard 03 March 2017 (has links)
An assessment study of a novel approach is presented that combines discrete state-space Dynamic Programming and Pontryagin’s Maximum Principle for online optimal control of hybrid electric vehicles (HEV). In addition to electric energy storage and gear, kinetic energy and travel time are considered states in this paper. After presenting the corresponding model using a parallel HEV as an example, a benchmark method with Dynamic Programming is introduced which is used to show the solution quality of the novel approach. It is illustrated that the proposed method yields a close-to-optimal solution by solving the optimal control problem over one hundred thousand times faster than the benchmark method. Finally, a potential online usage is assessed by comparing solution quality and calculation time with regard to the quantization of the state space.
6

GLOSA System with Uncertain Green and Red Signal Phases

Typaldos, Panagiotis, Koutsas, Petros, Papamichail, Ioannis, Papageorgiou, Markos 22 June 2023 (has links)
A discrete-time stochastic optimal control problem was recently proposed to address the GLOSA (Green Light Optimal Speed Advisory) problem in cases where the next signal switching time is decided in real-time and is therefore uncertain in advance. However, there was an assumption that the traffic signal is initially red and turns to green, which means that only half traffic light cycle was considered. In this work, the aforementioned problem is extended considering a full traffic light cycle, consisting of four phases: a certain green phase, during which the vehicle can freely pass; an uncertain green phase, in which there is a probability that the traffic light will extend its duration or turn to red at any time; a certain red phase during which the vehicle cannot pass; and an uncertain red phase, in which there is a probability that the red signal may be extended or turn to green at any time. It is demonstrated, based on preliminary results, that the proposed SDP (Stochastic Dynamic Programming) approach achieves better average performance, in terms of fuel consumption, compared to the IDM (Intelligent Driver Model), which emulates human-driving behavior.
7

Fine-Grained Parameterized Algorithms on Width Parameters and Beyond

Hegerfeld, Falko 25 October 2023 (has links)
Die Kernaufgabe der parameterisierten Komplexität ist zu verstehen, wie Eingabestruktur die Problemkomplexität beeinflusst. Wir untersuchen diese Fragestellung aus einer granularen Perspektive und betrachten Problem-Parameter-Kombinationen mit einfach exponentieller Laufzeit, d.h., Laufzeit a^k n^c, wobei n die Eingabegröße ist, k der Parameterwert, und a und c zwei positive Konstanten sind. Unser Ziel ist es, die optimale Laufzeitbasis a für eine gegebene Kombination zu bestimmen. Für viele Zusammenhangsprobleme, wie Connected Vertex Cover oder Connected Dominating Set, ist die optimale Basis bezüglich dem Parameter Baumweite bekannt. Die Baumweite gehört zu der Klasse der Weiteparameter, welche auf natürliche Weise zu Algorithmen mit dem Prinzip der dynamischen Programmierung führen. Im ersten Teil dieser Dissertation untersuchen wir, wie sich die optimale Laufzeitbasis für diverse Zusammenhangsprobleme verändert, wenn wir zu ausdrucksstärkeren Weiteparametern wechseln. Wir entwerfen neue parameterisierte Algorithmen und (bedingte) untere Schranken, um diese optimalen Basen zu bestimmen. Insbesondere zeigen wir für die Parametersequenz Baumweite, modulare Baumweite, und Cliquenweite, dass die optimale Basis von Connected Vertex Cover bei 3 startet, sich erst auf 5 erhöht und dann auf 6, wobei hingegen die optimale Basis von Connected Dominating Set bei 4 startet, erst bei 4 bleibt und sich dann auf 5 erhöht. Im zweiten Teil gehen wir über Weiteparameter hinaus und analysieren restriktivere Arten von Parametern. Für die Baumtiefe entwerfen wir platzsparende Verzweigungsalgorithmen. Die Beweistechniken für untere Schranken bezüglich Weiteparametern übertragen sich nicht zu den restriktiveren Parametern, weshalb nur wenige optimale Laufzeitbasen bekannt sind. Um dies zu beheben untersuchen wir Knotenlöschungsprobleme. Insbesondere zeigen wir, dass die optimale Basis von Odd Cycle Transversal parameterisiert mit einem Modulator zu Baumweite 2 den Wert 3 hat. / The question at the heart of parameterized complexity is how input structure governs the complexity of a problem. We investigate this question from a fine-grained perspective and study problem-parameter-combinations with single-exponential running time, i.e., time a^k n^c, where n is the input size, k the parameter value, and a and c are positive constants. Our goal is to determine the optimal base a for a given combination. For many connectivity problems such as Connected Vertex Cover or Connecting Dominating Set, the optimal base is known relative to treewidth. Treewidth belongs to the class of width parameters, which naturally admit dynamic programming algorithms. In the first part of this thesis, we study how the optimal base changes for these connectivity problems when going to more expressive width parameters. We provide new parameterized dynamic programming algorithms and (conditional) lower bounds to determine the optimal base, in particular, we obtain for the parameter sequence treewidth, modular-treewidth, clique-width that the optimal base for Connected Vertex Cover starts at 3, increases to 5, and then to 6, whereas the optimal base for Connected Dominating Set starts at 4, stays at 4, and then increases to 5. In the second part, we go beyond width parameters and study more restrictive parameterizations like depth parameters and modulators. For treedepth, we design space-efficient branching algorithms. The lower bound techniques for width parameterizations do not carry over to these more restrictive parameterizations and as a result, only a few optimal bases are known. To remedy this, we study standard vertex-deletion problems. In particular, we show that the optimal base of Odd Cycle Transversal parameterized by a modulator to treewidth 2 is 3. Additionally, we show that similar lower bounds can be obtained in the realm of dense graphs by considering modulators consisting of so-called twinclasses.
8

Energiemanagement für eine parallele Hybridfahrzeugarchitektur

Helbing, Maximilian 17 November 2014 (has links)
Durch die Integration mindestens eines weiteren Energiewandlers in den Antriebsstrang gewinnen parallele Hybridfahrzeuge einen zusätzlichen Freiheitsgrad gegenüber konventionellen Fahrzeugen. Neben der Auslegung und Effizienz der einzelnen Antriebskomponenten, ist vor allem die Nutzung dieses zusätzlichen Freiheitsgrades entscheidend dafür verantwortlich, inwiefern die beim Betrieb eines Hybridfahrzeugs erwünschten Ziele, wie die Minimierung des Kraftstoffverbrauchs oder der Abgasemissionen, erreicht werden können. Zuständig dafür sind sogenannte Betriebsstrategien. In einem ersten Schritt gibt die vorliegende Diplomarbeit einen Überblick aktueller Betriebsstrategieansätze für Fahrzeuge mit einer parallelen Hybridarchitektur und stellt ausgewählte Beiträge wertend gegenüber. Anschließend wird mit der optimierungsbasierten Equivalent Consumption Minimization Strategy (ECMS) ein vielversprechender Ansatz in ein MATLAB/Simulink-Längsdynamikmodell umgesetzt. Die für diesen Ansatz maßgebliche Bestimmung des Äquivalenzfaktors erfolgt dabei ohne Verwendung von Prädiktionsdaten. Eine Gegenüberstellung der erzielten Kraftstoffverbrauchswerte zu denen einer regelbasierten Betriebsstrategie, zeigt die Vorteile des implementierten ECMS-Ansatzes. Um den unterschiedlichen Ladezuständen am Fahrtende gerecht zu werden, wird eine ladungsabhängige Kraftstoffkorrektur vorgestellt.:Abbildungsverzeichnis VII Tabellenverzeichnis IX Abkürzungs- und Symbolverzeichnis X 1 Einleitung 1.1 Motivation 1.2 Zielstellung der Arbeit 1.3 Struktur der Arbeit 2 Energiemanagement paralleler Hybridfahrzeugarchitekturen 2.1 Hybridfahrzeuge 2.2 Hybridfahrzeugarchitekturen 2.3 Betriebsstrategien für parallele Hybridfahrzeugarchitekturen 2.3.1 Betriebsstrategie - Begriffsbestimmung und Einordnung in das Energiemanagement 2.3.2 Bewertungskriterien von Betriebsstrategien 2.3.3 Überblick Betriebsstrategien 3 Optimierungsbasierte Betriebsstrategien 3.1 Mathematischer Ansatz 3.1.1 Das parallele HEV als Anwendungsfall 3.1.2 Neben- und Randbedingungen 3.2 Globale optimierungsbasierte Betriebsstrategien 3.2.1 Dynamische Programmierung (DP) 3.2.2 PONTRJAGINsches Maximumsprinzip (PMP) 3.2.3 Approximation der Kennfelder 3.2.4 Suchheuristiken 3.3 Lokale optimierungsbasierte Betriebsstrategien 3.3.1 Equivalent Consumption Minimization Strategy (ECMS) 3.3.2 Gegenüberstellung ECMS und PMP 3.3.3 Bestimmung des Äquivalenzfaktors 3.4 Zusammenfassung der Vor- und Nachteile optimierungsbasierter Ansätze 4 Regelbasierte Betriebsstrategien 4.1 Deterministisch 4.1.1 Regeladaption mittels Suchheuristiken 4.1.2 Regeldefinition mittels PMP/ECMS 4.2 Fuzzy-Logik 4.3 Zusammenfassung der Vor- und Nachteile regelbasierter Ansätze 5 Auswahl eines zu implementierenden Strategieansatzes 6 Vorstellung des verwendeten Simulationsmodells 6.1 Betrachtete Fahrzyklen 6.2 Fahrzeugmodell 6.3 Implementierung der ECMS 6.3.1 Korrektur des Kraftstoffverbrauchs bei Ladungsabweichung 6.3.2 Auswahl der Strafkosten für den Gangwechsel und den VM- Betriebszustand 7 Simulation und Auswertung des implementierten Strategieansatzes. 7.1 Erweiterung der ECMS durch die nichtprädiktive Anpassung des Äquivalenzfaktors nach PEI 7.1.1 Auswahl des Skalierungsfaktors a - ohne Anpassung des Referenzwerts (λref = const) 7.1.2 Auswahl der Proportionalverstärkung Kp - Anpassung des Referenzwerts (λref ≠ const) 7.2 Vergleich der ECMS mit einer regelbasierten Betriebsstrategie 8 Zusammenfassung und Ausblick Quellenverzeichnis Anhang / By integrating at least one additional energy converter into the drive train, parallel hybrid vehicles gain an additional degree of freedom compared to conventional vehicles. In addition to the design and efficiency of the individual drive train components, especially the use of this additional degree of freedom is the key responsible to achieve the desired goals in the operation of a hybrid vehicle, such as minimizing fuel consumption and exhaust emissions. Responsible for this are so-called supervisory strategies. In a first step, the present thesis provides an overview of current supervisory control strategies for vehicles with a parallel hybrid architecture and compares selected approaches. In a second step, a promising Equivalent Consumption Minimization Strategy (ECMS) is chosen and implemented in a MATLAB/Simulink-longitudinal dynamics model. This approach relates on the determination of the equivalence factor which is carried out without the use of prediction data. A comparison of the fuel consumption, obtained for a rule-based supervisory strategy, shows the advantages of the implemented ECMS approach. To consider the different states of charge at the end of the trip, a charge-dependent fuel correction will be presented.:Abbildungsverzeichnis VII Tabellenverzeichnis IX Abkürzungs- und Symbolverzeichnis X 1 Einleitung 1.1 Motivation 1.2 Zielstellung der Arbeit 1.3 Struktur der Arbeit 2 Energiemanagement paralleler Hybridfahrzeugarchitekturen 2.1 Hybridfahrzeuge 2.2 Hybridfahrzeugarchitekturen 2.3 Betriebsstrategien für parallele Hybridfahrzeugarchitekturen 2.3.1 Betriebsstrategie - Begriffsbestimmung und Einordnung in das Energiemanagement 2.3.2 Bewertungskriterien von Betriebsstrategien 2.3.3 Überblick Betriebsstrategien 3 Optimierungsbasierte Betriebsstrategien 3.1 Mathematischer Ansatz 3.1.1 Das parallele HEV als Anwendungsfall 3.1.2 Neben- und Randbedingungen 3.2 Globale optimierungsbasierte Betriebsstrategien 3.2.1 Dynamische Programmierung (DP) 3.2.2 PONTRJAGINsches Maximumsprinzip (PMP) 3.2.3 Approximation der Kennfelder 3.2.4 Suchheuristiken 3.3 Lokale optimierungsbasierte Betriebsstrategien 3.3.1 Equivalent Consumption Minimization Strategy (ECMS) 3.3.2 Gegenüberstellung ECMS und PMP 3.3.3 Bestimmung des Äquivalenzfaktors 3.4 Zusammenfassung der Vor- und Nachteile optimierungsbasierter Ansätze 4 Regelbasierte Betriebsstrategien 4.1 Deterministisch 4.1.1 Regeladaption mittels Suchheuristiken 4.1.2 Regeldefinition mittels PMP/ECMS 4.2 Fuzzy-Logik 4.3 Zusammenfassung der Vor- und Nachteile regelbasierter Ansätze 5 Auswahl eines zu implementierenden Strategieansatzes 6 Vorstellung des verwendeten Simulationsmodells 6.1 Betrachtete Fahrzyklen 6.2 Fahrzeugmodell 6.3 Implementierung der ECMS 6.3.1 Korrektur des Kraftstoffverbrauchs bei Ladungsabweichung 6.3.2 Auswahl der Strafkosten für den Gangwechsel und den VM- Betriebszustand 7 Simulation und Auswertung des implementierten Strategieansatzes. 7.1 Erweiterung der ECMS durch die nichtprädiktive Anpassung des Äquivalenzfaktors nach PEI 7.1.1 Auswahl des Skalierungsfaktors a - ohne Anpassung des Referenzwerts (λref = const) 7.1.2 Auswahl der Proportionalverstärkung Kp - Anpassung des Referenzwerts (λref ≠ const) 7.2 Vergleich der ECMS mit einer regelbasierten Betriebsstrategie 8 Zusammenfassung und Ausblick Quellenverzeichnis Anhang
9

Rabattprobleme aus Konsumentensicht: Eine Online- und Offlineanalyse

Reißner, Michael 19 December 2022 (has links)
Einem Konsumenten werden in verschiedensten Situationen Rabatte angeboten. In dieser Dissertation wird die Frage untersucht, wie solche Rabattsituationen aus konsumentensicht formalisiert werden können und wie Kaufentscheidungen getroffen werden können. Um diese Frage zu beantworten, wird ein formaler Rahmen für Rabattsituationen angegeben und zur Analyse einer neuen Gruppe von acht Problemen, die auf alltäglichen Erfahrungen mit Rabattaktionen basieren, angewendet. Diese Probleme werden hinsichtlich der Rabattgrundlage (Stempel / Punkte), dem Kartentyp (Einzelkarte, Gruppenkarte) und der Frage, ob Stempel/Punkte für Käufe mit Rabatt gesammelt werden, unterschieden. Der inhärenten Planungsunsicherheit für Konsumentenentscheidungen wird explizit durch die Betrachtung jedes Problems als eine Onlinesituation Rechnung getragen. Für die Onlineprobleme wird eine zugeschnittene Methode zur Güteabschätzung präsentiert. Jedes der acht Probleme wird als Entscheidungs-, Optimierungs- und Onlineproblem analysiert. Für alle Entscheidungsprobleme wird NP-Vollständigkeit nachgewiesen. Jedes Optimierungsproblem wird mit ganzzahliger linearer Programmierung und einige stempelbasierte Probleme zusätzlich mit dynamischer Programmierung gelöst. Für die Onlineprobleme wird jeweils eine untere Güteschranke gezeigt und für drei Gruppen von Onlinealgorithmen die Güte abgeschätzt.:1. Einleitung 2. Vorbetrachtungen 3. Problemformulierung und Analysemethodik 4. Die Probleme im Detail 5. Zusammenfassung 6. Ausblick A. Implementationen / A consumer is offered discounts in a variety of situations. The central question investigated in this dissertation is how to formalize such discount situations from a consumer perspective and what methods for deducing purchase decisions are possible. To answer this question a formal framework for discount situations is established and used to explore a new group of eight discount problems based on everyday experience with loyalty programs. These problems are distinguished by discount basis (stamps / points), card type (single / group) and whether stamps/-points are collectable if a discount is granted. The inherent uncertainty in consumer decisions is explicitly taken into account by considering each of these problems as an online situation as well. Regarding the online problems, a method for competitive analysis is presented. Each of the eight problems is examined as a decision, an optimization and an online problem. For all decision problems N P-completeness is shown. Each optimization problem is solved via linear integer programming and some stamp based optimization problems are furthermore solved with dynamic programming. For each online problem a lower bound on the competitive ratio is presented together with three groups of online algorithms and the respective bounds on the competitive ratio.:1. Einleitung 2. Vorbetrachtungen 3. Problemformulierung und Analysemethodik 4. Die Probleme im Detail 5. Zusammenfassung 6. Ausblick A. Implementationen
10

Online Resource Allocation in Dynamic Optical Networks

Romero Reyes, Ronald 13 May 2019 (has links)
Konventionelle, optische Transportnetze haben die Bereitstellung von High-Speed-Konnektivität in Form von langfristig installierten Verbindungen konstanter Bitrate ermöglicht. Die Einrichtungszeiten solcher Verbindungen liegen in der Größenordnung von Wochen, da in den meisten Fällen manuelle Eingriffe erforderlich sind. Nach der Installation bleiben die Verbindungen für Monate oder Jahre aktiv. Das Aufkommen von Grid Computing und Cloud-basierten Diensten bringt neue Anforderungen mit sich, die von heutigen optischen Transportnetzen nicht mehr erfüllt werden können. Dies begründet die Notwendigkeit einer Umstellung auf dynamische, optische Netze, welche die kurzfristige Bereitstellung von Bandbreite auf Nachfrage (Bandwidth on Demand - BoD) ermöglichen. Diese Netze müssen Verbindungen mit unterschiedlichen Bitratenanforderungen, mit zufälligen Ankunfts- und Haltezeiten und stringenten Einrichtungszeiten realisieren können. Grid Computing und Cloud-basierte Dienste führen in manchen Fällen zu Verbindungsanforderungen mit Haltezeiten im Bereich von Sekunden, wobei die Einrichtungszeiten im Extremfall in der Größenordnung von Millisekunden liegen können. Bei optischen Netzen für BoD muss der Verbindungsaufbau und -abbau, sowie das Netzmanagement ohne manuelle Eingriffe vonstattengehen. Die dafür notwendigen Technologien sind Flex-Grid-Wellenlängenmultiplexing, rekonfigurierbare optische Add / Drop-Multiplexer (ROADMs) und bandbreitenvariable, abstimmbare Transponder. Weiterhin sind Online-Ressourcenzuweisungsmechanismen erforderlich, um für jede eintreffende Verbindungsanforderung abhängig vom aktuellen Netzzustand entscheiden zu können, ob diese akzeptiert werden kann und welche Netzressourcen hierfür reserviert werden. Dies bedeutet, dass die Ressourcenzuteilung als Online-Optimierungsproblem behandelt werden muss. Die Entscheidungen sollen so getroffen werden, dass auf lange Sicht ein vorgegebenes Optimierungsziel erreicht wird. Die Ressourcenzuweisung bei dynamischen optischen Netzen lässt sich in die Teilfunktionen Routing- und Spektrumszuteilung (RSA), Verbindungsannahmekontrolle (CAC) und Dienstgütesteuerung (GoS Control) untergliedern. In dieser Dissertation wird das Problem der Online-Ressourcenzuteilung in dynamischen optischen Netzen behandelt. Es wird die Theorie der Markov-Entscheidungsprozesse (MDP) angewendet, um die Ressourcenzuweisung als Online-Optimierungsproblem zu formulieren. Die MDP-basierte Formulierung hat zwei Vorteile. Zum einen lassen sich verschiedene Optimierungszielfunktionen realisieren (z.B. die Minimierung der Blockierungswahrscheinlichkeiten oder die Maximierung der wirtschaftlichen Erlöse). Zum anderen lässt sich die Dienstgüte von Gruppen von Verbindungen mit spezifischen Verkehrsparametern gezielt beeinflussen (und damit eine gewisse GoS-Steuerung realisieren). Um das Optimierungsproblem zu lösen, wird in der Dissertation ein schnelles, adaptives und zustandsabhängiges Verfahren vorgestellt, dass im realen Netzbetrieb rekursiv ausgeführt wird und die Teilfunktionen RSA und CAC umfasst. Damit ist das Netz in der Lage, für jede eintreffende Verbindungsanforderung eine optimale Ressourcenzuweisung zu bestimmen. Weiterhin wird in der Dissertation die Implementierung des Verfahrens unter Verwendung eines 3-Way-Handshake-Protokolls für den Verbindungsaufbau betrachtet und ein analytisches Modell vorgestellt, um die Verbindungsaufbauzeit abzuschätzen. Die Arbeit wird abgerundet durch eine Bewertung der Investitionskosten (CAPEX) von dynamischen optischen Netzen. Es werden die wichtigsten Kostenfaktoren und die Beziehung zwischen den Kosten und der Performanz des Netzes analysiert. Die Leistungsfähigkeit aller in der Arbeit vorgeschlagenen Verfahren sowie die Genauigkeit des analytischen Modells zur Bestimmung der Verbindungsaufbauzeit wird durch umfangreiche Simulationen nachgewiesen. / Conventional optical transport networks have leveraged the provisioning of high-speed connectivity in the form of long-term installed, constant bit-rate connections. The setup times of such connections are in the order of weeks, given that in most cases manual installation is required. Once installed, connections remain active for months or years. The advent of grid computing and cloud-based services brings new connectivity requirements which cannot be met by the present-day optical transport network. This has raised awareness on the need for a changeover to dynamic optical networks that enable the provisioning of bandwidth on demand (BoD) in the optical domain. These networks will have to serve connections with different bit-rate requirements, with random interarrival times and durations, and with stringent setup latencies. Ongoing research has shown that grid computing and cloud-based services may in some cases request connections with holding times ranging from seconds to hours, and with setup latencies that must be in the order of milliseconds. To provide BoD, dynamic optical networks must perform connection setup, maintenance and teardown without manual labour. For that, software-configurable networks are needed that are deployed with enough capacity to automatically establish connections. Recently, network architectures have been proposed for that purpose that embrace flex-grid wavelength division multiplexing, reconfigurable optical add/drop multiplexers, and bandwidth variable and tunable transponders as the main technology drivers. To exploit the benefits of these technologies, online resource allocation methods are necessary to ensure that during network operation the installed capacity is efficiently assigned to connections. As connections may arrive and depart randomly, the traffic matrix is unknown, and hence, each connection request submitted to the network has to be processed independently. This implies that resource allocation must be tackled as an online optimization problem which for each connection request, depending on the network state, decides whether the request is admitted or rejected. If admitted, a further decision is made on which resources are assigned to the connection. The decisions are so calculated that, in the long-run, a desired performance objective is optimized. To achieve its goal, resource allocation implements control functions for routing and spectrum allocation (RSA), connection admission control (CAC), and grade of service (GoS) control. In this dissertation we tackle the problem of online resource allocation in dynamic optical networks. For that, the theory of Markov decision processes (MDP) is applied to formulate resource allocation as an online optimization problem. An MDP-based formulation has two relevant advantages. First, the problem can be solved to optimize an arbitrarily defined performance objective (e.g. minimization of blocking probability or maximization of economic revenue). Secondly, it can provide GoS control for groups of connections with different statistical properties. To solve the optimization problem, a fast, adaptive and state-dependent online algorithm is proposed to calculate a resource allocation policy. The calculation is performed recursively during network operation, and uses algorithms for RSA and CAC. The resulting policy is a course of action that instructs the network how to process each connection request. Furthermore, an implementation of the method is proposed that uses a 3-way handshake protocol for connection setup, and an analytical performance evaluation model is derived to estimate the connection setup latency. Our study is complemented by an evaluation of the capital expenditures of dynamic optical networks. The main cost drivers are identified. The performance of the methods proposed in this thesis, including the accuracy of the analytical evaluation of the connection setup latency, were evaluated by simulations. The contributions from the thesis provide a novel approach that meets the requirements envisioned for resource allocation in dynamic optical networks.

Page generated in 0.4851 seconds