No description available.

Nous étudions dans cette thèse des problèmes d’optimisation avec applications dans les réseaux optiques. Les problèmes étudiés sont liés à la tolérance aux pannes et à l’utilisation efficace des ressources. Les résultats obtenus portent principalement sur la complexité de calcul de ces problèmes. La première partie de cette thèse est consacrée aux problèmes de trouver des chemins et des chemins disjoints. La recherche d’un chemin est essentielle dans tout type de réseaux afin d’y établir des connexions et la recherche de chemins disjoints est souvent utilisée pour garantir un certain niveau de protection contre les pannes dans les réseaux. Nous étudions ces problèmes dans des contextes différents. Nous traitons d’abord les problèmes de trouver un chemin et des chemins lien ou nœud- disjoints dans des réseaux avec nœuds asymétriques, c’est-à-dire des nœuds avec restrictions sur leur connectivité interne. Ensuite, nous considérons les réseaux avec des groupes de liens partageant un risque (SRLG) en étoile : ensembles de liens qui peuvent tomber en panne en même temps suite à un événement local. Dans ce type de réseaux, nous examinons le problème de recherche des chemins SRLG-disjoints. La deuxième partie de cette thèse est consacrée au problème de routage et d’allocation de spectre (RSA) dans les réseaux optiques élastiques (EONs). Les EONs sont proposés comme la nouvelle génération des réseaux optiques et ils visent une utilisation plus efficace et flexible des ressources optiques. Le problème RSA est central dans les EONs. Il concerne l’allocation de ressources aux requêtes sous plusieurs contraintes. / We study in this thesis optimization problems with application in optical networks. The problems we consider are related to fault-tolerance and efficient resource allocation and the results we obtain are mainly related to the computational complexity of these problems. The first part of this thesis is devoted to finding paths and disjoint paths. Finding a path is crucial in all types of networks in order to set up connections and finding disjoint paths is a common approach used to provide some degree of protection against failures in networks. We study these problems under different settings. We first focus on finding paths and node or link-disjoint paths in networks with asymmetric nodes, which are nodes with restrictions on their internal connectivity. Afterwards, we consider networks with star Shared Risk Link Groups (SRLGs) which are groups of links that might fail simultaneously due to a localized event. In these networks, we investigate the problem of finding SRLG-disjoint paths. The second part of this thesis focuses on the problem of Routing and Spectrum Assignment (RSA) in Elastic Optical Networks (EONs). EONs are proposed as the new generation of optical networks and they aim at an efficient and flexible use of the optical resources. RSA is the key problem in EONs and it deals with allocating resources to requests under multiple constraints. We first study the static version of RSA in tree networks. Afterwards, we examine a dynamic version of RSA in which a non-disruptive spectrum defragmentation technique is used. Finally, we present in the appendix another problem that has been studied during this thesis.

Avec l’avènement de l’ère intellectuelle et de l’Internet of Everything (IoE), les besoins de la communication mondiale et des applications diverses ont explosé. Cette révolution exige que les futurs réseaux de communication soient plus efficaces, intellectuels, agiles et évolutifs. De nombreuses technologies réseau sont apparues pour répondre à la tendance des réseaux de communication de nouvelle génération tels que les réseaux optiques élastiques (EONs) et la virtualisation de réseau. De nombreux défis apparaissent avec les apparences de la nouvelle architecture et de la nouvelle technologie, telles que le routage et l’allocation de ressource spectrale (RSA) dans les EONs et l’intégration de réseaux virtuels (Virtual Network Embedding ou VNE) dans la virtualisation de réseau.Cette thèse traite la conception et l’analyse d’algorithmes d’approximation dans trois problèmes d’optimation du RSA et du VNE : les impacts de la distribution du trafic et de la topologie du réseau sur le routage tout optique, de l’allocation de ressource spectrale, et du VNE dans les topologies des chemins et cycles. Pour le routage tout optique, le premier sous-problème du RSA, il y a toujours un problème en suspens concernant l’impact de la distribution du trafic et de la topologie EON. Comme le routage tout optique joue un rôle essentiel pour la performance globale de la RSA, cette thèse fournit une analyse approfondi théorique sur ces impacts. Pour le deuxième sous-problème du RSA, l’allocation de ressource spectrale, deux chemins optiques quelconques partageant des fibres optiques communes pourraient devoir être isolés dans le domaine spectral avec une bande de garde appropriée pour empêcher la diaphonie et / ou réduire les menaces de sécurité de la couche physique. Cette thèse considère le scénario dans lequel les exigences de bandes de garde réelles optiques sont différentes pour différentes paires de chemins, et étudie comment affecter les ressources spectrales efficacement dans une telle situation. L’hétérogénéité de la topologie des demandes de réseau virtuel (VNR) est un facteur important qui entrave les performances de la VNE. Cependant, dans de nombreuses applications spécialisées, les VNR ont des caractéristiques structurelles communes par exemple, des chemins et des cycles. Pour obtenir de meilleurs résultats, il est donc essentiel de concevoir des algorithmes dédiés pour ces applications en tenant compte des caractéristiques topologiques. Dans cette thèse, nous prouvons que les problèmes VNE dans les topologies de chemin et de cycle sont NP-difficiles. Afin de les résoudre, nous proposons des algorithmes efficaces également analysons leurs ratios d’approximation / With the coming of intellectual era and Internet of Everything (IoE), the needs of worldwide communication and diverse applications have been explosively growing. This information revolution requires the future communication networks to be more efficient, intellectual, agile and scalable. Many technologies have emerged to meet the requirements of next generation communication networks such as Elastic Optical Networks (EONs) and networking virtualization. However, there are many challenges coming along with them, such as Routing and Spectrum Assignment (RSA) in EONs and Virtual Network Embedding (VNE) in network virtualization. This dissertation addresses the algorithm design and analysis for these challenging problems: the impacts of traffic distribution and network topology on lightpath routing, the distance spectrum assignment and the VNE problem for paths and cycles.For lightpath routing, the first subproblem of the RSA, there is always a pending issue that how the changes of the traffic distribution and EON topology affect it. As the lightpath routing plays a critical role in the overall performance of the RSA, this dissertation provides a thoroughly theoretical analysis on the impacts of the aforementioned two key factors. To this end, we propose two theoretical chains, and derive the optimal routing scheme taking into account two key factors. We then treat the second subproblem of RSA, namely spectrum assignment. Any two lightpaths sharing common fiber links might have to be isolated in the spectrum domain with a proper guard-band to prevent crosstalk and/or reduce physical-layer security threats. We consider the scenario with diverse guard-band sizes, and investigate how to assign the spectrum resources efficiently in such a situation. We provide the upper and lower bounds for the optimal solution of the DSA, and further devise an efficient algorithm which can guarantee approximation ratios in some graph classes.The topology heterogeneity of Virtual Network Requests (VNRs) is one important factor hampering the performance of the VNE. However, in many specialized applications, the VNRs are of some common structural features e.g., paths and cycles. To achieve better outcomes, it is thus critical to design dedicated algorithms for these applications by accounting for topology characteristics. We prove the NP-Harness of path and cycle embeddings. To solve them, we propose some efficient algorithms and analyze their approximation ratios.

Made available in DSpace on 2016-04-04T18:31:45Z (GMT). No. of bitstreams: 1 RICARDO VICENTE FAVERO.pdf: 1635235 bytes, checksum: d51f441103ff9f2ad94576b0bdd11b9f (MD5) Previous issue date: 2015-11-13 / The wavelength division multiplexing (WDM) optical network accommodates traffic load in 100, 50 and 25 GHz fixed-grid channel. This fixed-grid condition limits the number of lightpath for each optical fiber (80 channels in c-band) and doesn t allow bit rates with bandwidth over 50 GHz. To improve these factors, the flexibly grid elastic optical network (EON) was proposed, aiming accommodate adequately bit rates demand by customers. This proposal allows efficiency bandwidth and also expands bit rates supported by network. The EON bandwidth efficiency is obtained by routing and spectrum assignment (RSA) algorithm which acts to maximize the bandwidth utilization. Even with RSA, EON still show fragmentation rates substantial. In this context, this work proposes a new elastic optical network defragmentation strategy. This defragmentation strategy selects the lightpaths from the most fragmented link. The defragmentation process is based on RSA (DF-RSA). The DF-RSA determines the new position to reallocate the connection selected and performs. Using computer simulation of EON operation, were submitted several bit rates demands with different modulations format and traffic load between 45 and 100 erlang. Two simulation scenarios were proposed. The first one, compare the performance of RSA algorithm first-fit (FF) with and without defragmentation. It was considered as defragmentation process beginning point (trigger), the number of release connections. This scenario had until 48% of relative gain on minimizing blocking probability. The second scenario compared the performance of the follows RSA algorithms: FF, Maximize Path Spectrum Consecutiveness (MPSC) and Fragmentation Aware (FA). The FF was evaluated with and without defragmentation process and the others just with defragmentation process. The trigger employed was eventual connection blocked. The second scenario reached over the 80% blocking probability relative gain in 50 erlang traffic load. We conclude that the new elastic optical network defragmentation offers substantial gain bandwidth utilization and consequently blocking probability reduction. / As redes ?pticas de multiplexa??o por divis?o de comprimento de onda (WDM) acomodam o tr?fego em canais fixos de 100, 50 e 25 GHz. Esta condi??o de grade fixa limita o n?mero de conex?es por fibra ?ptica (80 canais na banda C), e n?o permite taxas de transmiss?o com ocupa??o espectral acima de 50 GHz. Para melhorar estes fatores, foram propostas as redes ?pticas el?sticas (EON) com canais flex?veis, visando acomodar adequadamente as taxas de transmiss?o demandas pelos usu?rios. Esta proposta possibilita maior efici?ncia espectral e tamb?m amplia as taxas de transmiss?o suportadas pela rede. A efici?ncia espectral nas EONs ? obtida com os algoritmos de roteamento e atribui??o espectral (Routing and Spectrum Assignment, RSA), que atuam para maximizar seu uso espectral. Mesmo com o uso de RSAs, as EONs ainda apresentam ?ndices de fragmenta??o consider?veis. Neste contexto, este trabalho prop?e uma nova estrat?gia de desfragmenta??o espectral para EONs. Esta proposta de desfragmenta??o seleciona as conex?es do enlace mais fragmentado, para o processo de desfragmenta??o. A desfragmenta??o baseia seu processo de realoca??o de conex?es por RSA, denominado DF-RSA. O DF-RSA determina a nova posi??o e realiza a realoca??o das conex?es. Com o uso de simula??o computacional da opera??o de funcionamento da EON, foram submetidas v?rias demandas de taxas de transmiss?o com diferentes modula??es e cargas de tr?fego entre 45 e 100 erlang. Foram propostos dois cen?rios de simula??o. No primeiro, foi comparado o desempenho do algoritmo RSA First-Fit (FF) com e sem o processo de desfragmenta??o. Considerou-se como ponto de inicio das desfragmenta??es (gatilho), o n?mero de conex?es liberadas da rede. Neste cen?rio obteve-se at? 48% de ganho relativo na minimiza??o da probabilidade de bloqueio. No segundo cen?rio, foram comparados os desempenhos dos seguintes algoritmos RSAs: FF, Maximize Path Spectrum Consecutiveness (MPSC) e Fragmentation Aware (FA). O FF foi avaliado com e sem desfragmenta??o e os demais somente com desfragmenta??o. Empregou-se como gatilho o eventual bloqueio de conex?o. O segundo cen?rio alcan?ou mais de 80% de ganho relativo de probabilidade de bloqueio para carga de tr?fego de 50 erlang. Conclui-se que a nova estrat?gia de desfragmenta??o para EONs oferece ganhos consider?veis na utiliza??o espectral e, consequentemente, redu??o na probabilidade de bloqueio.

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.