Firm real time system with Poisson arrival process, iid exponential service times and iid deadlines till the end of service of a job, operated under the First Come First Served (FCFS) scheduling policy is well studied. In this thesis, we present an exact theoretical analysis of a similar (M/M/1 + G queue) system with exact admission control (EAC). We provide an explicit expression for the steady state workload distribution. We use this solution to derive explicit expressions for the loss ratio and the sojourn time distribution. An exact theoretical analysis of the performance of an M/M/1 + G queue with preemptive deadlines till the end of service, operating under the Earliest Deadline First (EDF) scheduling policy, appears to be difficult, and only approximate formulas for the loss ratio are available in the literature. We present in this thesis similar approximate formulas for the loss ratio in the present of an exit control mechanism, which discards a job at the epoch of its getting the server if there is no chance of completing it. We refer to this exit control mechanism as the Early job Discarding Technique (EDT). Monte Carlo simulations of performance indicate that the maximum approximation error is reasonably small for a wide range of arrival rates and mean deadlines. Finally, we compare the loss ratios of the First Come First Served and the Earliest Deadline First scheduling policies with or without admission or exit control mechanism, as well as their counterparts with deterministic deadlines. The results include some formal equalities, inequalities and some counter-examples to establish non-existence of an order. A few relations involving loss ratios are posed as conjectures, and simulation results in support of these are reported. These results lead to a complete picture of dominance and non-dominance relations between pairs of scheduling policies, in terms of loss ratios.

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.