Optical networking has been developing for decades and wavelength-division multiplexing (WDM) is the main technology used to carry signals in fiber-optical communication systems. However, its development has slowed because it is approaching the Shannon limit of nonlinear fiber transmission. Researchers are looking for multi dimensional multiplexing. Space-division multiplexing (SDM) is an ideal way to scale network capacities. The capacity of WDM/SDM network could be expanded to several times the capacity of WDM network but the active hardware devices may also increase by several times. This project aims to answer a practical question: How to construct a WDM/SDM network with less hardware resource? There is no mature research about WDM/SDM network yet. Therefore, the problem can be divided into two parts: (1) how to build a WDM/SDM network and (2) how to allocate resource and compute routes in such a network to minimize hardware resources. First, this thesis proposes a WDM/SDM node which has bypass connections between different fibers and architecture on demand (AoD) to effectively decrease the number of active hardware devices within the node. Then, two types of networks were constructed: one with bypass connections in each node and another one without any bypass connections. These networks were under the control of a software defined network (SDN) controller. The controller knew the wavelength resources within the networks. Several algorithms were applied to these networks to evaluate the effect of a bypass network and to identify the desired characteristics (to find short length path and decrease the probability of spectrum fragmentation) of an algorithm suitable for a network with bypass connections. The results of applying the proposed algorithms in two networks proved that the bypass connections increased the blocking probability in small topology but did not affect the results in large topology. The results in a large-scale network with bypass network were almost the same as the results in a network without bypass connections. Thus, bypass connections are suitable for large-scale network. / Optiskt nätverk har utvecklats i årtionden och våglängdsdelningsmultiplexering (WDM) är den viktigaste tekniken som används för att bära signaler i fiberoptiska kommunikationssystem. Utvecklingen har dock minskat eftersom den närmar sig Shannon-gränsen för olinjär fiberöverföring. Forskare letar efter flerdimensionell multiplexering. Space-division multiplexing (SDM) är ett idealiskt sätt att skala nätverkskapacitet. Kapaciteten för WDM / SDM-nätverk kan utökas till flera gånger WDM-nätverkets kapacitet, men de aktiva hårdvaraenheterna kan också öka med flera gånger. Projektet syftar till att svara på en praktisk fråga: Hur konstruerar jag ett WDM / SDM-nätverk med mindre hårdvara? Det finns ingen mogen forskning om WDM / SDM-nätverk än. Därför kan problemet delas in i två delar: (1) hur man bygger ett WDM / SDM-nätverk och (2) hur man fördelar resurser och beräknar rutter i ett sådant nätverk för att minimera hårdvaruressurser. Först föreslår denna avhandling en WDM / SDM-nod som har förbikopplingsanslutningar mellan olika fibrer och arkitektur på begäran (AoD) för att effektivt minska antalet aktiva hårdvaraenheter inom noden. Sedan konstruerades två typer av nätverk: en med bypass-anslutningar i varje nod och en annan utan några bypass-anslutningar. Dessa nätverk kontrollerades av en mjukvarudefinierad nätverkskontroller (SDN). Styrenheten visste våglängdsresurserna i nätverket. Flera algoritmer applicerades på dessa nätverk för att utvärdera effekten av ett förbikopplingsnätverk och för att identifiera de önskade egenskaperna (för att hitta en kort längdväg och minska sannolikheten för spektrumfragmentering) av en algoritm som är lämplig för ett nätverk med bypass-anslutningar. Resultaten av att tillämpa de föreslagna algoritmerna i två nät visade att förbikopplingsförbindelserna ökade blockeringssannolikheten i liten topologi men inte påverkade resultaten i stor topologi. Resultaten i ett storskaligt nätverk med bypass-nätverk var nästan samma som resultaten i ett nätverk utan bypass-anslutningar. Bypassanslutningar är således lämpliga för storskaliga nätverk.

Η δρομολόγηση και ανάθεση μηκών κύματος (routing and wavelength assignment - RWA) αποτελεί ένα πολύ σημαντικό πρόβλημα, που απασχολεί τους σχεδιαστές WDM οπτικών δικτύων και είναι γνωστό, πως είναι NP-πλήρες. Στην εργασία αυτή σχεδιάζουμε και υλοποιούμε έναν αλγόριθμο για το στατικό RWA, που βασίζεται σε έναν προτεινόμενο σχηματισμό (μη ακέραιου) γραμμικού προγραμματισμού (linear programming - LP). Ισχυριζόμαστε, πως ο σχηματισμός αυτός είναι σε θέση να παρέχει ακέραιες βέλτιστες λύσεις (παρά την εν γένει μη ακέραια φύση του) για ένα μεγάλο ποσοστό στιγμιότυπων εισόδου, οδηγώντας έτσι σε αντίστοιχες ακριβείς λύσεις του RWA. Η πολυπλοκότητα του αλγόριθμου κυριαρχείται από το χρόνο εκτέλεσης του αλγόριθμου Simplex, ο οποίος θεωρείται αποδοτικός για μια μεγάλη πλειοψηφία στιγμιότυπων εισόδου. Στα διαφανή (πλήρως οπτικά) δίκτυα, η ποιότητα του σήματος υπόκειται σε μια ποικιλία από φυσικές εξασθενήσεις, όπως είναι η διασπορά λειτουργίας πόλωσης (polarization mode dispersion - PMD), ο θόρυβος αυθόρμητης εκπομπής ενισχυτή (amplified spontaneous emission - ASE - noise) και η χρωματική διασπορά (chromatic dispersion - CD). Αυτές οι εξασθενήσεις μοντελοποιούνται γραμμικά και μπορούν να αντιμετωπιστούν αποτελεσματικά από ένα σύνολο αναλυτικών τύπων ως επιπρόσθετοι περιορισμοί στο RWA. Εφαρμόζουμε τον αλγόριθμό μας και εκτελούμε RWA βασισμένο σε περιορισμούς εξασθένησης, με σκοπό να παρατηρήσουμε συγκριτικά αποτελέσματα στην απόδοση ενός τυπικού μητροπολιτικού δικτύου υπό διάφορες παραμέτρους του δικτύου και των εξασθενήσεων, όπως είναι ο ρυθμός bit, ο τύπος και το κέρδος των ενισχυτών, η χρησιμοποιούμενη διάταξη διαμόρφωσης, κλπ. / Routing and wavelength assignment (RWA) is a very important problem concerning WDM optical network designers and is known to be NP-complete. In this work, we design and implement an algorithm for the static RWA, that is based on a proposed (not integer) linear programming formulation. We claim, that this formulation is able to provide integer optimal solutions (despite its non integral nature) for a large fraction of input instances, yielding thus to corresponding exact RWA solutions. The algorithm's complexity is dominated by the execution time of Simplex LP-solver, that is considered efficient in the great majority of all possible input instances. In transparent (all-optical) networks, the signal quality is subject to a variety of physical impairments, such as polarization mode dispersion (PMD), amplified spontaneous emission (ASE) noise and chromatic dispersion (CD). Those impairments are linearly modeled and are handled effectively by a set of analytical formulae as additional constraints on RWA. We apply our algorithm to perform impairment-constraint based RWA, in order to obtain comparative results of a typical metropolitan network's performance under various network and impairment parameters, such as bit rate, amplifier gain and type, modulation format used, etc.

The continuous growth of traffic demand driven by the brisk increase in number of Internet users and emerging online services creates new challenges for communication networks. The latest advances in Wavelength Division Multiplexing (WDM) technology make it possible to build Transparent Optical Networks (TONs) which are expected to be able to satisfy this rapidly growing capacity demand. Moreover, with the ability of TONs to transparently carry the optical signal from source to destination, electronic processing of the tremendous amount of data can be avoided and optical-to-electrical-to-optical (O/E/O) conversion at intermediate nodes can be eliminated. Consequently, transparent WDM networks consume relatively low power, compared to their electronic-based IP network counterpart. Furthermore, TONs bring also additional benefits in terms of bit rate, signal format, and protocol transparency. However, the absence of O/E/O processing at intermediate nodes in TONs has also some drawbacks. Without regeneration, the quality of the optical signal transmitted from a source to a destination might be degraded due to the effect of physical-layer impairments induced by the transmission through optical fibers and network components. For this reason, routing approaches specifically tailored to account for the effect of physical-layer impairments are needed to avoid setting up connections that don’t satisfy required signal quality at the receiver. Transparency also makes TONs highly vulnerable to deliberate physical-layer attacks. Malicious attacking signals can cause a severe impact on the traffic and for this reason proactive mechanisms, e.g., network design strategies, able to limit their effect are required. Finally, even though energy consumption of transparent WDM networks is lower than in the case of networks processing the traffic at the nodes in the electronic domain, they have the potential to consume even less power. This can be accomplished by targeting the inefficiencies of the current provisioning strategies applied in WDM networks. The work in this thesis addresses the three important aspects mentioned above. In particular, this thesis focuses on routing and wavelength assignment (RWA) strategies specifically devised to target: (i) the lightpath transmission quality, (ii) the network security (i.e., in terms of vulnerability to physical-layer attacks), and (iii) the reduction of the network energy consumption. Our contributions are summarized below. A number of Impairment Constraint Based Routing (ICBR) algorithms have been proposed in the literature to consider physical-layer impairments during the connection provisioning phase. Their objective is to prevent the selection of optical connections (referred to as lightpaths) with poor signal quality. These ICBR approaches always assign each connection request the least impaired lightpath and support only a single threshold of transmission quality, used for all connection requests. However, next generation networks are expected to support a variety of services with disparate requirements for transmission quality. To address this issue, in this thesis we propose an ICBR algorithm supporting differentiation of services at the Bit Error Rate (BER) level, referred to as ICBR-Diff. Our approach takes into account the effect of physical-layer impairments during the connection provisioning phase where various BER thresholds are considered for accepting/blocking connection requests, depending on the signal quality requirements of the connection requests. We tested the proposed ICBR-Diff approach in different network scenarios, including also a fiber heterogeneity. It is shown that it can achieve a significant improvement of network performance in terms of connection blocking, compared to previously published non-differentiated RWA and ICBR algorithms.  Another important challenge to be considered in TONs is their vulnerability to physical-layer attacks. Deliberate attacking signals, e.g., high-power jamming, can cause severe service disruption or even service denial, due to their ability to propagate in the network. Detecting and locating the source of such attacks is difficult, since monitoring must be done in the optical domain, and it is also very expensive. Several attack-aware RWA algorithms have been proposed in the literature to proactively reduce the disruption caused by high-power jamming attacks. However, even with attack-aware network planning mechanisms, the uncontrollable propagation of the attack still remains an issue. To address this problem, we propose the use of power equalizers inside the network nodes in order to limit the propagation of high-power jamming attacks. Because of the high cost of such equipment, we develop a series of heuristics (incl. Greedy Randomized Adaptive Search Procedure (GRASP)) aiming at minimizing the number of power equalizers needed to reduce the network attack vulnerability to a desired level by optimizing the location of the equalizers. Our simulation results show that the equalizer placement obtained by the proposed GRASP approach allows for 50% reduction of the sites with the power equalizers while offering the same level of attack propagation limitation as it is possible to achieve with all nodes having this additional equipment installed. In turn, this potentially yields a significant cost saving.    Energy consumption in TONs has been the target of several studies focusing on the energy-aware and survivable network design problem for both dedicated and shared path protection. However, survivability and energy efficiency in a dynamic provisioning scenario has not been addressed. To fill this gap, in this thesis we focus on the power consumption of survivable WDM network with dynamically provisioned 1:1 dedicated path protected connections. We first investigate the potential energy savings that are achievable by setting all unused protection resources into a lower-power, stand-by state (or sleep mode) during normal network operations. It is shown that in this way the network power consumption can be significantly reduced. Thus, to optimize the energy savings, we propose and evaluate a series of energy-efficient strategies, specifically tailored around the sleep mode functionality. The performance evaluation results reveal the existence of a trade-off between energy saving and connection blocking. Nonetheless, they also show that with the right provisioning strategy it is possible to save a considerable amount of energy with a negligible impact on the connection blocking probability. In order to evaluate the performance of our proposed ICBR-Diff and energy-aware RWA algorithms, we develop two custom-made discrete-event simulators. In addition, the Matlab program of GRASP approach for power equalization placement problem is implemented. / <p>QC 20120508</p>

O surgimento de novos serviços de telecomunicações tem provocado um enorme aumento no tráfego de dados nas redes de transmissão. Para atender a essa demanda crescente, novas tecnologias foram desenvolvidas e implementadas ao longo dos anos, sendo que um dos principais avanços está na área de transmissão óptica, devido à grande capacidade de transporte de informação da fibra óptica. A tecnologia que melhor explora a capacidade desse meio de transmissão atualmente é a multiplexação por divisão de comprimento de onda ou Wavelength Division Multiplexing (WDM) que permite a transmissão de diversos sinais utilizando apenas uma fibra óptica. Redes ópticas WDM se tornaram muito complexas, com enorme capacidade de transmissão de informação (terabits por segundo), para atender à explosão de necessidade por largura de banda. Nesse contexto, é de extrema importância que os recursos dessas redes sejam utilizados de forma inteligente e otimizada. Um dos maiores desafios em uma rede óptica é a escolha de uma rota e a seleção de um comprimento de onda disponível na rede para atender uma solicitação de conexão utilizando o menor número de recursos possível. Esse problema é bastante complexo e ficou conhecido como problema de roteamento e alocação de comprimento de onda ou, simplesmente, problema RWA (Routing and Wavelentgh Assignment problem). Muitos estudos foram realizados com o objetivo de encontrar uma solução eficiente para esse problema, mas nem sempre é possível aliar bom desempenho com baixo tempo de execução, requisito fundamental em redes de telecomunicações. A técnica de algoritmo genético (AG) tem sido utilizada para encontrar soluções de problemas de otimização, como é o caso do problema RWA, e tem obtido resultados superiores quando comparada com soluções heurísticas tradicionais encontradas na literatura. Esta dissertação apresenta, resumidamente, os conceitos de redes ópticas e de algoritmos genéticos, e descreve uma formulação do problema RWA adequada à solução por algoritmo genético. / The advent of new telecommunication services resulted in a huge increase of data traffic in the transmission networks. New technologies were developed and implemented over the years to attend to this growing demand, and the optical transmission technology stands. It has advanced greatly, due to the optical fibers large capacity of information transmission. Actually, the best technology to exploits the capacity of the fiber is the wavelength-division multiplexing (WDM), allowing the transmission of multiple signals over a single optical fiber. The WDM optical networks have become very complex, with huge capacity (terabits per second), to attend the ever growing need for bandwidth. In this context, it is extremely important to use the networks resources in an intelligent and optimized way. One of the biggest challenges in an optical network is choosing a route, and selecting a available wavelength on the network to attend a connection request using the least amount of resources. This problem is quite complex, and is known as the routing and wavelength assignment problem or simply RWA problem. Many studies were conducted in order to find an efficient solution to this problem, but it is not always possible to combine good performance with low execution time, a fundamental requirement in telecommunications networks. Genetic Algorithms have been used to solve hard optimization problems, as is the case of the RWA problem, and has produced remarkable results when compared to traditional heuristics found in the literature. This work presents an overview of the concepts of optical networks and genetic algorithms, and describes a formulation of RWA problem that is adequate for solution by genetic algorithm.

O surgimento de novos serviços de telecomunicações tem provocado um enorme aumento no tráfego de dados nas redes de transmissão. Para atender a essa demanda crescente, novas tecnologias foram desenvolvidas e implementadas ao longo dos anos, sendo que um dos principais avanços está na área de transmissão óptica, devido à grande capacidade de transporte de informação da fibra óptica. A tecnologia que melhor explora a capacidade desse meio de transmissão atualmente é a multiplexação por divisão de comprimento de onda ou Wavelength Division Multiplexing (WDM) que permite a transmissão de diversos sinais utilizando apenas uma fibra óptica. Redes ópticas WDM se tornaram muito complexas, com enorme capacidade de transmissão de informação (terabits por segundo), para atender à explosão de necessidade por largura de banda. Nesse contexto, é de extrema importância que os recursos dessas redes sejam utilizados de forma inteligente e otimizada. Um dos maiores desafios em uma rede óptica é a escolha de uma rota e a seleção de um comprimento de onda disponível na rede para atender uma solicitação de conexão utilizando o menor número de recursos possível. Esse problema é bastante complexo e ficou conhecido como problema de roteamento e alocação de comprimento de onda ou, simplesmente, problema RWA (Routing and Wavelentgh Assignment problem). Muitos estudos foram realizados com o objetivo de encontrar uma solução eficiente para esse problema, mas nem sempre é possível aliar bom desempenho com baixo tempo de execução, requisito fundamental em redes de telecomunicações. A técnica de algoritmo genético (AG) tem sido utilizada para encontrar soluções de problemas de otimização, como é o caso do problema RWA, e tem obtido resultados superiores quando comparada com soluções heurísticas tradicionais encontradas na literatura. Esta dissertação apresenta, resumidamente, os conceitos de redes ópticas e de algoritmos genéticos, e descreve uma formulação do problema RWA adequada à solução por algoritmo genético. / The advent of new telecommunication services resulted in a huge increase of data traffic in the transmission networks. New technologies were developed and implemented over the years to attend to this growing demand, and the optical transmission technology stands. It has advanced greatly, due to the optical fibers large capacity of information transmission. Actually, the best technology to exploits the capacity of the fiber is the wavelength-division multiplexing (WDM), allowing the transmission of multiple signals over a single optical fiber. The WDM optical networks have become very complex, with huge capacity (terabits per second), to attend the ever growing need for bandwidth. In this context, it is extremely important to use the networks resources in an intelligent and optimized way. One of the biggest challenges in an optical network is choosing a route, and selecting a available wavelength on the network to attend a connection request using the least amount of resources. This problem is quite complex, and is known as the routing and wavelength assignment problem or simply RWA problem. Many studies were conducted in order to find an efficient solution to this problem, but it is not always possible to combine good performance with low execution time, a fundamental requirement in telecommunications networks. Genetic Algorithms have been used to solve hard optimization problems, as is the case of the RWA problem, and has produced remarkable results when compared to traditional heuristics found in the literature. This work presents an overview of the concepts of optical networks and genetic algorithms, and describes a formulation of RWA problem that is adequate for solution by genetic algorithm.

A datacenter hosts hundreds of thousands of servers and a huge amount of bandwidth is required to accommodate communication between thousands of servers. Several packet switched based datacenter architectures are proposed to cater the high bandwidth requirement using multilayer network topologies, however at the cost of increased network complexity and high power consumption. In recent years, the focus has shifted from packet switching to optical circuit switching to build the data center networks as it can support on demand connectivity and high bit rates with low power consumption. On the other hand, with the advent of Software Defined Networking (SDN) and Network Function Virtualization (NFV), the role of datacenters has become more crucial. It has increased the need of dynamicity and flexibility within a datacenter adding more complexity to datacenter networking. With NFV, service chaining can be achieved in a datacenter where virtualized network functions (VNFs) running on commodity servers in a datacenter are instantiated/terminated dynamically. A datacenter also needs to cater large capacity requirement as service chaining involves steering of large aggregated flows. Use of optical circuit switching in data center networks is quite promising to meet such dynamic and high capacity traffic requirements. In this thesis work, a novel and modular optical data center network (DCN) architecture that uses multi-directional wavelength switches (MD-WSS) is introduced. VNF service chaining use case is considered for evaluation of this DCN and the end-to-end service chaining problem is formulated as three inter-connected sub-problems: multiplexing of VNF service chains, VNFs placement in the datacenter and routing and wavelength assignment. This thesis presents integer linear programming (ILP) formulation and heuristics for solving these problems, and numerically evaluate them. / Ett datacenter inrymmer hundratusentals servrar och en stor mängd bandbredd krävs för att skicka data mellan tusentals servrar. Flera datacenter baserade på paketförmedlande arkitekturer föreslås för att tillgodose kravet på hög bandbredd med hjälp av flerskiktsnätverkstopologier, men på bekostnad av ökad komplexitet i nätverken och hög energiförbrukning. Under de senaste åren har fokus skiftat från paketförmedling till optisk kretsomkoppling for att bygga datacenternätverk som kan stödja på-begäran-anslutningar och höga bithastigheter med låg strömförbrukning. Å andra sidan, med tillkomsten av Software Defined Networking (SDN) och nätverksfunktionen Virtualisering (NFV), har betydelsen av datacenter blivit mer avgörande. Det har ökat behovet av dynamik och flexibilitet inom ett datacenter, vilket leder till storre komplexitet i datacenternätverken. Med NFV kan tjänstekedjor åstadkommas i ett datacenter, där virtualiserade nätverksfunktioner (VNFs) som körs på servrar i ett datacenter kan instansieras och avslutas dynamiskt. Ett datacenter måste också tillgodose kravet på stor kapacitet eftersom tjänstekedjan innebär styrning av stora aggregerade flöden. Användningen av optisk kretsomkoppling i datacenternätverk ser ganska lovande ut for att uppfylla sådana trafikkrav dynamik och hög kapacitet. I detta examensarbete, har en ny och modulär optisk datacenternätverksarkitektur (DCN) som använder flerriktningvåglängdsswitchar (MD-WSS) införs. Ett användningsfall av VNF-tjänstekedjor noga övervägd för utvärdering av denna DCN och end-to-end-servicekedjans problem formuleras som tre sammankopplade delproblem: multiplexering av VNF-servicekedjor, VNF placering i datacentret och routing och våglängd uppdrag. Denna avhandling presenterar heltalsprogrammering (ILP) formulering och heuristik för att lösa dessa problem och numeriskt utvärdera dem.

Η πρόσφατη τεχνολογική ανάπτυξη των οπτικών ενισχυτών, πολυπλεκτών/αποπλεκτών, οπτικών διακοπτών καθώς και άλλων οπτικών συσκευών μας οδηγεί στο να ελπίζουμε ότι σύντομα στο μέλλον θα υλοποιηθεί ένα πλήρες οπτικό (all optical), WDM (wavelength division multiplexing) δίκτυο που να ικανοποιεί και την ανάγκη για μεγάλα μεγέθη χωρητικότητας. Σε ένα τέτοιο δίκτυο η μετατροπή του οπτικού σήματος σε ηλεκτρονικό και εκ νέου στο οπτικό (ΟΕΟ) δεν θα χρησιμοποιείται στους ενδιάμεσους κόμβους, και αυτό συμβάλει σε οικονομικότερες υλοποιήσεις των οπτικών δικτύων. Σε ένα WDM δρομολογούμενο δίκτυο, τα δεδομένα μεταφέρονται μέσω ενός οπτικού καναλιού, lightpath, στους κόμβους του δικτύου που συνδέονται με οπτικές ίνες. Στις πλείστες των περιπτώσεων, κατά την άφιξη ενός lightpath σε κάποιο κόμβο, εφαρμόζεται σε αυτό οπτικό-ηλεκτρονική μετατροπή και αντίστροφα, ούτως ώστε το σήμα να αναδημιουργηθεί λόγω των απωλειών που υπέστη κατά την μεταφορά, ή ακόμη για να αναλυθεί από ενδιάμεσες ηλεκτρονικές συσκευές. Στα μη πλήρη οπτικά δίκτυα, η μεταφορά των δεδομένων γίνεται από κόμβο σε κόμβο κατά μήκος του δικτύου, ούτως ώστε το οπτικό σήμα να ενισχύεται και να αναγεννάτε μέσω της OEO επεξεργασίας. Παρ’ όλα αυτά, η κάθε ενδιάμεση ανάλυση του θέματος σε ένα τέτοιο δίκτυο προϋποθέτει πολύ μεγάλα κόστη λόγω των πολλών συσκευών που απαιτούνται για τη OEO επεξεργασία. Το γεγονός αυτό μας οδηγεί στα ημί-πλήρη δίκτυα όπου η ενίσχυση και αναγέννηση του θέματος δε γίνεται σε όλους τους ενδιάμεσους κόμβους αλλά σε μερικούς από αυτούς. Ο τελικός στόχος όμως είναι η απαλοιφή της ηλεκτρονικής μετατροπής και αυτό οδηγεί στην υλοποίηση των πλήρως οπτικών δικτύων. Στα πλήρη οπτικά δίκτυα, ένα σήμα που μεταδίδεται παραμένει, για όλο το lightpath, στο οπτικό επίπεδο. Έτσι, το πλήρες οπτικό δίκτυο μπορεί να απαλείψει την ασύμφορη OEO μετατροπή. Η αναζήτηση των κατάλληλων μονοπατιών με τα κατάλληλα μήκη κύματος που θα ικανοποιούσε ένα πλήρες οπτικό δίκτυο το οποίο δρομολογείται από ligthpaths, ονομάζεται Routing and Wavelength Assignment (RWA) και αποτελεί ένα από τα σημαντικότερα ζητήματα για το σωστό σχεδιασμό των οπτικών δικτύων τέτοιου είδους. Το πρόβλημα γίνεται ιδιαίτερα πολύπλοκο όταν στην τελική απόφαση θα πρέπει να συμπεριληφθούν και τα χαρακτηριστικά του φυσικού επιπέδου του δικτύου, όπως εξασθένιση του σήματος, μη γραμμικά φαινόμενα, διασπορά κ.ά, η συμβολή των οποίων στην τελική δρομολόγηση δεν θεωρείται αμελητέα (Impairment Aware Routing and Wavelength Assignment, ΙΑ-RWA). Σε αυτή την εργασία μελετάται το RWA πρόβλημα και προτείνεται ένας μονού στόχου γενετικός αλγόριθμος (Single Objective Genetic Algorithm - SOGA), ο οποίος επιλύει ικανοποιητικά το πρόβλημα θεωρώντας στατική κίνηση. Επιπλέον τονίζεται η σημασία των φυσικών παραμέτρων του προβλήματος και πως αυτές επηρεάζουν την απόδοση του πλήρους οπτικού δικτυου. Στη συνέχεια προτείνεται ένας νέος, πολλαπλών στόχων γενετικός αλγόριθμος (multi objective genetic algorithm – MOGA) ο οποίος βελτιστοποιεί τις λύσεις του προβλήματος ικανοποιητικά λαμβάνοντας ταυτόχρονα υπόψη, με έμμεσο τρόπο, και τις φυσικές παραμέτρους. Επίσης προτείνεται και ένας μονού στόχου γενετικός αλγόριθμος οποίος χρησιμοποιεί ένα εργαλείο αποτίμηση της ποιότητας μετάδοσης (Q-TOOL) σαν μέτρο κατά τη διαδικασία εύρεσης ικανοποιητικής λύσης. Το υπόλοιπο της εργασίας οργανώνεται ως ακολούθως: Στην ενότητα 2 παρουσιάζεται μια σύντομη αναφορά στα WDM δίκτυα καθώς και η περιγραφή του RWA και IA-RWA προβλήματος, ενώ στην ενότητα 3 παρουσιάζεται η πρόταση επίλυσης του RWA προβληματος με τη χρήση γενετικών αλγορίθμων. Ακολουθεί στην ενότητα 4 η πρότασή μας για επίλυση του IA-RWA προβλήματος με τη χρήση Multi-objective διαδικασιών βελτιστοποίησης, καθώς και η βελτιστοποίηση του προβλήματος με τη χρήση του Q-TOOL. Τέλος στην ενότητα 5 συνοψίζουμε την εργασία και παρουσιάζουμε τα συμπεράσματα. / The recent development of optical amplifiers, multiplexers / de-multiplexers, optical switches and other optical devices leads us to hope that soon in future all optical, WDM (wavelength division multiplexing) networks will be implemented which that will satisfy the needs for large capacity. In such networks a viable conversion of the optical -> Electronic and back to optical (OEO) will not be used at intermediate nodes, and this will contribute to efficient and economical implementation. The search for the appropriate paths with the appropriate wavelengths that meet the requirement in all optical networks is called Routing and Wavelength Assignment (RWA) and is one of the most important issues for proper design of such optical networks. The problem becomes particularly complex when the final decision should include the characteristics of the physical layer of the network, such as attenuation of the signal, nonlinear effects, dispersion, etc., whose contribution to the final result is not considered negligible (Impairment Aware Routing and Wavelength Assignment,IA-RWA). This work studies the RWA problem considering static traffic, and proposes a single-objective genetic algorithm (Single Objective Genetic Algorithm - SOGA), which resolves the problem satisfactorily. Furthermore the work stresses the importance of physical parameters of the problem and how these affect the performance of the all optical networks, and proposes a new, multi-objective genetic algorithm (MOGA) which optimizes the solution of IA-RWA problem adequately taking into account indirectly, and the physical impairments that affect the quality of the signal. In addition, a single objective genetic algorithm is proposed that uses a tool to assess the quality of the transmission signal (Q-TOOL), as a benchmark, in the process of optimization of the solution to the IA-RWA problem.

Τα οπτικά δίκτυα αποτελούν την αποδοτικότερη επιλογή όσον αφορά την εγκατάσταση ευρυζωνικών δικτύων κορμού, καθώς παρουσιάζουν μοναδικά χαρακτηριστικά μετάδοσης. Διαθέτουν τεράστιο εύρος ζώνης, υψηλή αξιοπιστία, ενώ επίσης έχουν μειωμένο κόστος μετάδοσης ανά bit πληροφορίας σε σχέση με τα υπόλοιπα ενσύρματα δίκτυα. Σημαντικές ερευνητικές προσπάθειες έχουν επικεντρωθεί στις προοπτικές μετάβασης από τα παραδοσιακά στατικά δίκτυα κυκλωμάτων, στα οποία χρησιμοποιείται από-σημείο-σε-σημείο οπτική μετάδοση, σε δίκτυα μετάδοσης δεδομένων που προσφέρουν δυναμική και γρήγορη επαναρύθμιση των οπτικών μονοπατιών και πρόσβαση σε χωρητικότητες κάτω του ενός μήκους κύματος, ανάλογα με τις απαιτήσεις των χρηστών και των εκάστοτε εφαρμογών. Τα τελευταία χρόνια υπάρχει η τάση για δημιουργία δυναμικών και επαναρυθμιζόμενων οπτικών δικτύων μεταγωγής κυκλώματος (Optical Circuit Switching), τα οποία θα βασίζονται σε διαφανείς κόμβους μεταγωγής. Η μονάδα μεταγωγής των δικτύων οπτικής μεταγωγής κυκλώματος είναι τα οπτικά μονοπάτια (lightpaths) και το βασικό πρόβλημα βελτιστοποίησης που σχετίζεται με την αποδοτική εκμετάλλευση της χωρητικότητας τέτοιων δικτύων είναι το πρόβλημα της δρομολόγησης και ανάθεσης μήκους κύματος (Routing and Wavelength Assignment - RWA). Στα αμιγώς διαφανή (transparent) οπτικά δίκτυα κυκλώματος η μετάδοση του σήματος υποβαθμίζεται από μια σειρά φυσικών εξασθενήσεων (physical impairments), σε σημείο που η εγκατάσταση ενός οπτικού μονοπατιού να μην είναι αποδεκτή. Για την αντιμετώπιση αυτού του προβλήματος στην παρούσα διατριβή προτείνουμε αλγόριθμους οι οποίοι λαμβάνουν υπόψη τους τις φυσικές εξασθενήσεις (Impairment Aware RWA ή ΙΑ-RWA algorithms) τόσο για στατική όσο και για δυναμική κίνηση. Συγκεκριμένα, παρουσιάζουμε έναν IA-RWA αλγόριθμο για στατική κίνηση, ο οποίος βασίζεται στην τεχνική της LP-χαλάρωσης και χρησιμοποιεί αποδοτικές μεθόδους για την παραγωγή ακεραίων λύσεων. Εκφράζουμε τις φυσικές εξασθενήσεις μέσω επιπλέον περιορισμών στην LP μοντελοποίηση του RWA προβλήματος, επιτυγχάνοντας την διαστρωματική βελτιστοποίηση (cross-layer optimization) πάνω στο φυσικό επίπεδο και στο επίπεδο δικτύου. Στη συνέχεια, προτείνουμε έναν IA-RWA αλγόριθμο πολλαπλών κριτηρίων (multi-cost) για δυναμική κίνηση. Ορίζουμε ένα διάνυσμα από κόστη για κάθε σύνδεσμο και τις πράξεις συσχέτισης αυτών, ώστε να μπορούμε να υπολογίσουμε το διάνυσμα από κόστη ενός μονοπατιού και μέσω αυτού να αξιολογήσουμε την ποιότητα μετάδοσης των διαθέσιμων μηκών κύματος του μονοπατιού. Για την εξυπηρέτηση μιας νέας αίτησης σύνδεσης, ο αλγόριθμος πολλαπλών κριτηρίων υπολογίζει το σύνολο των μη κυριαρχούμενων μονοπατιών, από την πηγή στο ζητούμενο προορισμό, και μετά εφαρμόζει μια πολιτική για να επιλέξει το βέλτιστο οπτικό μονοπάτι. Προτείνουμε και αξιολογούμε την απόδοση μιας σειράς από πολιτικές επιλογής, η κάθε μια από τις οποίες ουσιαστικά αντιστοιχεί σε έναν διαφορετικό δυναμικό IA-RWA αλγόριθμο. Στη συνέχεια, στρέφουμε την προσοχή μας στα δίκτυα οπτικής μεταγωγής καταιγισμών (Optical Burst Switching – OBS), τα οποία θεωρούνται ότι αποτελούν το επόμενο στάδιο των δικτύων οπτικής μεταγωγής κυκλώματος, όπου η δέσμευση της χωρητικότητας γίνεται για μικρότερο χρονικό διάστημα. Στα OBS δίκτυα, τα πακέτα που έχουν τον ίδιο προορισμό και παρόμοιες απαιτήσεις ποιότητας υπηρεσίας συναθροίζονται σε καταιγισμούς (bursts). Οι καταιγισμοί μεταδίδονται πάνω από αμιγώς οπτικά μονοπάτια, τα οποία ρυθμίζονται με τη χρήση πακέτων ελέγχου που μεταδίδονται πριν από τους αντίστοιχους καταιγισμούς και τα οποία επεξεργάζονται ηλεκτρονικά οι ενδιάμεσοι κόμβοι. Επικεντρώνουμε την προσοχή μας σε δυο βασικά στοιχεία ενός δικτύου οπτικής μεταγωγής καταιγισμών, την διαδικασία συναρμολόγησης καταιγισμών και τα πρωτόκολλα σηματοδοσίας, και παραθέτουμε δύο προτάσεις για την αποδοτική ανάθεσης χωρητικότητας σε αυτά τα δίκτυα. Συγκεκριμένα, προτείνουμε και αξιολογούμε ένα νέο αλγόριθμο συναρμολόγησης καταιγισμών που βασίζεται στη μέση καθυστέρηση των πακέτων που αποτελούν έναν καταιγισμό. Δείχνουμε ότι ο προτεινόμενος αλγόριθμος συναρμολόγησης καταιγισμών μειώνει την διασπορά της καθυστέρησης των πακέτων (packet delay jitter), η οποία είναι σημαντική για μια σειρά από εφαρμογές. Στην συνέχεια προτείνουμε ένα νέο αμφίδρομο (two-way) πρωτόκολλο σηματοδοσίας που βασίζεται στις μελλοντικές (in-advance) και χαλαρωμένες χρονικά (relaxed timed) δεσμεύσεις χωρητικότητας. Στο προτεινόμενο πρωτόκολλο, κατά τη φάση εγκατάστασης της σύνδεσης οι δεσμεύσεις χωρητικότητας γίνονται για χρονικό διάστημα μεγαλύτερο από το χρόνο μετάδοσης του καταιγισμού, ώστε να αυξηθεί η πιθανότητα επιτυχούς εγκατάστασης στους επόμενους συνδέσμους του μονοπατιού. Συγκρίνουμε το προτεινόμενο πρωτόκολλο με τυπικά πρωτόκολλα που έχουν προταθεί στη βιβλιογραφία και δείχνουμε οτι μπορεί να χρησιμοποιηθεί για την παροχή διαφοροποιημένης ποιότητα υπηρεσιών (QoS differentiation) στους χρήστες του OBS δικτύου. Στη συνέχεια, εξετάζουμε το πρόβλημα της δρομολόγησης και του χρονοπρογραμματισμού συνδέσεων με χαλαρό - μη συγκεκριμένο χρόνο εκκίνησης, πρόβλημα που εμφανίζεται υπό ελαφρώς διαφορετική μορφή σε δίκτυα οπτικής μεταγωγής κυκλώματος, οπτικής μεταγωγής καταιγισμών αλλά και μεταγωγής πακέτου. Η εξυπηρέτηση αυτών των συνδέσεων γίνεται μέσω μελλοντικών δεσμεύσεων χωρητικότητας, τρόπος ο οποίος είναι τυπικός για να παρεχθεί εγγυημένη ποιότητα υπηρεσίας (QoS) στους χρήστες ενός δικτύου. Θεωρούμε ότι μας δίνεται μια σύνδεση με γνωστή πηγή και προορισμό, γνωστό ή άγνωστο όγκο δεδομένων και γνωστό ρυθμό μετάδοσης και ζητείται να αποφασίσουμε το μονοπάτι που θα ακολουθήσουν τα δεδομένα και το χρόνο που θα αρχίσει η μετάδοση. Διακριτοποιούμε το χρόνο και χρησιμοποιούμε κατάλληλα διανύσματα ως δομές δεδομένων για να αναπαραστήσουμε τη διαθεσιμότητα των συνδέσμων του δικτύου ως συνάρτηση του χρόνου. Χρησιμοποιούμε αυτά τα διανύσματα σε ένα αλγόριθμο πολλαπλών κριτηρίων για τη δρομολόγηση και το χρονοπρογραμματισμό των συνδέσεων. Αρχικά, παρουσιάζουμε έναν αλγόριθμο πολλαπλών κριτηρίων μη πολυωνυμικής πολυπλοκότητας, ο οποίος βασίζεται στην έννοια των μη-κυριαρχούμενων μονοπατιών. Μετά προτείνουμε δύο ευριστικούς αλγορίθμους πολυωνυμικής πολυπλοκότητας, ορίζοντας κατάλληλες σχέσεις ψευδο-κυριαρχίας οι οποίες μειώνουν το χώρο των λύσεων. Επίσης, προτείνουμε ένα μηχανισμό branch-and-bound, ο οποίος μπορεί να μειώσει το χώρο λύσεων στην περίπτωση που χρησιμοποιούμε μια συγκεκριμένη συνάρτηση βελτιστοποίησης για όλες τις συνδέσεις. Η απόδοση των προτεινόμενων αλγορίθμων αξιολογήθηκε σε ένα δίκτυο οπτικής μεταγωγής καταιγισμών, ωστόσο τα συμπεράσματα και η εφαρμοσιμότητα του προτεινόμενου αλγόριθμου επεκτείνεται και σε άλλου είδους οπτικά δίκτυα. Τέλος, εξετάζουμε το πρόβλημα του συνδυασμένου χρονοπρογραμματισμού των δικτυακών και υπολογιστικών πόρων που απαιτούνται για την εκτέλεση μιας διεργασίας σε ένα Δίκτυο Πλέγματος (Grid Network). Τα Δίκτυα Πλέγματος θεωρούνται το επόμενο βήμα στον τομέα των κατανεμημένων συστημάτων, εισάγοντας την έννοια της “κοινής” χρήσης γεωγραφικά κατανεμημένων και ετερογενών πόρων (υπολογιστικών, αποθηκευτικών, δικτυακών, κλπ.). Υποθέτουμε ότι η εκτέλεση μιας διεργασίας αποτελείται από δύο διαδοχικά στάδια: (α) Τη μεταφορά των δεδομένων εισόδου της διεργασίας από μια αποθηκευτική μονάδα σε μια συστοιχία υπολογιστών (cluster), (β) την εκτέλεση της διεργασίας στη συστοιχία υπολογιστών. Επεκτείνουμε τον αλγόριθμο πολλαπλών κριτηρίων για τη δρομολόγηση και το χρονοπρογραμματισμό συνδέσεων που περιγράφηκε προηγουμένως, έτσι ώστε να χειρίζεται με ένα συνδυασμένο τρόπο δικτυακούς και υπολογιστικούς πόρους για την εκτέλεση των διεργασιών. Ο προτεινόμενος αλγόριθμος επιστρέφει: (i) τη συστοιχία υπολογιστών όπου θα εκτελεστεί η διεργασία, (ii) το μονοπάτι το οποίο θα ακολουθήσουν τα δεδομένα εισόδου, (iii) τη χρονική στιγμή εκκίνησης μετάδοσης και (iv) τη χρονική στιγμή εκκίνησης εκτέλεσης της διεργασίας στη συστοιχία υπολογιστών. Ξεκινάμε παρουσιάζοντας έναν αλγόριθμο μη πολυωνυμικού χρόνου και μετά, αφού μειώσουμε κατάλληλα το χώρο λύσεων, δίνουμε έναν ευριστικό αλγόριθμο πολυωνυμικής πολυπλοκότητας. / Optical networks have developed rapidly over the last ten years and are widely used in core networks due to their superior transmission characteristics. Optical networks provide huge available capacity that can be efficiently utilized using wavelength division multiplexing (WDM) and high reliability at the lowest cost per bit ratio when compared to the other wired and wireless networking solutions. Much research has focused on ways to evolve from the typical point-to-point opaque WDM networks that are currently employed in the core to optical networks that are dynamically and quickly reconfigurable and can provide on-demand services to users at subwavelength granularity according to users’ requirements. The most common architecture utilized for establishing communication in WDM optical networks is wavelength routing that fall in the general category of Optical Circuit Switched (OCS) networks. The switched entities in OCS networks are the lightpaths and the basic optimization problem that is related to the efficient allocation of bandwidth is the routing and wavelength assignment problem (RWA). The current optical technology employed in core networks is point-to-point transmission, where the signal is regenerated at every intermediate node via optical-electronic-optical (OEO) conversion. During the recent few years, the trend clearly shows an evolution towards low-cost and high capacity all-optical transparent networks that do not utilize OEO. In transparent OCS networks the signal of a lightpath remains in the optical domain and its quality deteriorates due to a series of physical layer impairments (PLIs). These PLIs may degrade the received signal quality to the extent that the bit-error rate (BER) at the receiver may be so high that signal detection may be infeasible for some lightpaths. To address this problem we proposed algorithms that take into account the PLIs, usually referred in the literature as Impairment Aware RWA or ΙΑ-RWA algorithms, for both offline (static) and online (dynamic) traffic. In particular we propose an IA-RWA algorithm for static traffic that is based on an LP-relaxation formulation and use various efficient methods to obtain integer solutions. The physical layer impairments are included as additional constraint in the LP formulation of the RWA problem, yielding a cross-layer optimization solution between the network and the physical layers. We then proceed and propose a multi-cost IA-RWA algorithm for dynamic traffic. We define a cost vector per link and associative operators to combine these vectors so as to calculate the cost vector of a path. The parameters of these cost vectors are chosen so as to enable the quick and efficient calculation of the quality of transmission of candidate lightpaths. To serve a connection request, the proposed multi-cost algorithm calculates the set of so called non-dominated paths from the given source to the given destination, and then applies an optimization policy to choose the optimal lightpath. We propose and evaluate various optimization policies that correspond to different online IA-RWA algorithms. We then turn our attention to Optical Burst Switched (OBS) networks, which are regarded as the next step from the OCS paradigm towards a more dynamic core network that can provide on demand subwavelength services to users. In OBS networks, the packets that have the same destination and similar quality of service requirements are aggregated into bursts at the ingress nodes. When a burst is aggregated, a control packet is transmitted and is electronically processed at intermediate nodes so as to configure them for the burst that will pass transparently afterwards. We focus on two key elements of an OBS network, and in particular the burst aggregation (or burstification) process and the signaling protocol, and we propose two solutions for the efficient allocation of bandwidth in OBS networks. We propose and evaluate a novel burst assembly algorithm that is based on the average delay of the packets that comprise a burst. We show that the proposed algorithm decreases the packet delay jitter among the packets, which is important for a number of applications, including real-time, video and audio streaming, and TCP applications. Next we propose a two-way reservation signaling protocol that utilizes in-advance and relaxed timed reservation of the bandwidth. In the connection establishment phase of the proposed protocol, bandwidth reservations can exceed the duration of burst transmission (thus, relaxing the timed reservations), so as to increase the acceptance probability for the rest of the path. By controlling the degree of the relaxed timed reservations the protocol can also provide service differentiation to the users. Next we examine the problem of routing and scheduling of connections with flexible starting time in networks that support advance reservations. This problem can arise in slightly different settings in Optical Circuit Switched, Optical Burst Switched, and Optical Packet Switched networks. Such connection requests are served through advanced reservations, a process which is used to provide quality of service to users. We assume that for a connection request we are given the source, the destination, and the size of the data to be transferred with a given rate, and we are asked to provide the path and the time that the transmission should start so as to optimize a certain performance metric. We discretize the time and we use appropriate data structures (in the form of vectors) to map the utilization of the links as a function of time. We use these vectors as cost parameters in a multi-cost algorithm. We initially present a multicost algorithm of non-polynomial complexity that uses a full domination relation between paths. We then propose two mechanisms to prune the solution space in order to obtain polynomial complexity algorithms. In the first mechanism we define pseudo-domination relations that are weaker than the full domination relation. We also propose a branch-and-bound extension to the optimum algorithm that can be used for a given specific optimization function. The performance of the multicost algorithm and its variations are evaluated in an OBS network, but this does not limit the applicability of the algorithm and the conclusions can be extended in the other optical networking paradigms. Finally, we examine the problem of joint reservation of communication and computation resources that are required by a task in a Grid Network. Grid Networks are considered as the next step in distributed systems, introducing the concept of shared usage of geographically distributed and heterogeneous resources (computation, storage, communication, etc.). We assume that the task execution consists of two phases: (a) the transfer of the input data from a data storage resource, or the scheduler to a computation resource (cluster), (b) the execution of a program at the cluster. We extend the multicost algorithm for the routing and scheduling of connections, outlined above, so as to handle the reservation of computation resources as its last leg. In this way the proposed algorithm performs a joint optimization for the communication and computation part required by a task and returns: (i) the cluster to the execute the task, (ii) the path to route the input data, (iii) the time to start the transmission of data, and (iv) the time to start the execution of the task. We start by presenting an algorithm of non-polynomial complexity and then by appropriately pruning the solution space, we give a heuristic algorithm of polynomial complexity. We show that in a Grid network where the tasks are cpu- and data-intensive important performance benefits can be obtained by jointly optimizing the use of the communication and computation resources.