Abstract

nkara : The Department of Electrical and Electronics Engineering and the Institute of Engineering and Sciences of Bilkent University, 2010. Thesis (Ph. D.) -- Bilkent University, 2010. Includes bibliographical references leaves 153-165. We study Traffic Engineering (TE) in Multiprotocol Label Switching (MPLS)/Wavelength Division Multiplexing (WDM) networks and propose a multi-layer TE method. MPLS provides powerful TE features for IP networks and is widely deployed in backbone networks. WDM can increase the transmission capacity of optical fibers to tremendous amounts, therefore it has been the dominant multiplexing technology used in the optical layer. The proposed multi-layer TE solution facilitates efficient use of network resources where the TE mechanisms in the MPLS and WDM layers coordinate. We consider a static WDM layer and available traffic expectation information. The TE problem arising in the considered scenario is the Virtual Topology Design (VTD) problem, which involves the decision of WDM lightpaths to be established, calculation of MPLS Label Switched Paths (LSPs) on the resulting virtual topology, and calculation of the routes and wavelengths in the physical topology that correspond to the lightpaths in the virtual topology. We assume a daily traffic pattern changing with the time of day and aim to design a static virtual topology that satisfies as much of the offered traffic as possible, over the whole day. In our proposed solution, the multi-layer VTD problem is solved by decomposing it into two sub-problems, each involving in a single layer. The decomposition approach is used in the thesis due to the huge computational burden of the combined solution for real-life networks. The sub-problem in the MPLS layer is the design of the lightpath topology and calculation of the LSP routes on this virtual topology. This problem is known to be NP-complete and finding its optimum solution is possible only for small networks. We propose a Tabu Search based heuristic method to solve two versions of this problem, resource oriented and performance oriented. Integer Linear Programming (ILP) relaxations are also developed for obtaining upper and lower bounds. We show that the gap between the produced solutions and the lower and upper bounds are around 10% and 7% for the resource and performance oriented problems, respectively. Since the actual traffic can show deviations from the expected values, we also developed an MPLS layer online TE method to compensate the instantaneous fluctuations of the traffic flows. In the proposed method, the LSPs are rerouted dynamically using a specially designed cost function. Our numerical studies show that using the designed cost function results in much lower blockings than using commonly used Widest Shortest Path First and Available Shortest Path First approaches in the literature. The corresponding sub-problem of the multi-layer VTD problem in the WDM layer is the Static Lightpath Establishment (SLE) problem. Along with the capacity and wavelength continuity constraints, we also consider the Bit Error Rate (BER) constraints due to physical layer impairments such as attenuation, polarization mode dispersion and switch crosstalk. This problem is NP-complete even without the BER constraints. We propose a heuristic solution method and develop an exact ILP formulation to evaluate the performance of the proposed method for small problem sizes. Our proposed method produces solutions close to the optimum solutions for the cases in which the ILP formulation could be solved to optimality. Then, these solution methods for the single layer sub-problems are combined in a multi-layer TE scheme to solve the VTD problem in both layers jointly. The proposed TE scheme considers the physical layer limitations and optical impairments. This TE scheme can be applied by keeping each layer’s information hidden from the other layer, but our simulations show that it can produce more effective and efficient solutions when the physical layer topology information is shared with the MPLS layer. We also investigate the effect of non-uniform optical components in terms of impairment characteristics. The numerical results show that more traffic can be routed when all the components in the network have moderate impairment characteristics, compared to the case in which some components have better and some have worse impairment characteristics. Şengezer, Namık Ph.D.

Abstract

Orientador: Nelson Luis Saldanha da Fonseca Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Made available in DSpace on 2018-08-28T20:53:25Z (GMT). No. of bitstreams: 1 Pontes_AlissonSoaresLimeira_M.pdf: 2584435 bytes, checksum: cbcb6945d130888c12f72f8123e74467 (MD5) Previous issue date: 2015 Resumo: Apesar dos avanços em aprovisionamento de caminhos ópticos intra-domínio em redes Wavelength Division Multiplexing (WDM), esquemas eficientes para cálculo de rota e divulgação de recursos ópticos em redes multidomínio em malha ainda não foram plenamente estabelecidos. Por estarem sujeitos a restrições de escalabilidade e restrições de divulgação de estado da rede, os domínios ópticos precisam de esquemas simples e eficientes. A maioria das soluções apresentadas na literatura não suportam Engenharia de Tráfego e são baseadas em técnicas de inundação periódica de mensagens de controle. Esta dissertação apresenta três propostas de aprovisionamento de caminhos ópticos em redes WDM multi-domínio baseadas na arquitetura Path Computation Element (PCE). As propostas são formadas por um esquema de disseminação de informações sobre o estado da rede combinado a um esquema de cálculo de cadeia de domínios e cálculo de rota fim-a-fim. Considera-se que os comutadores da rede óptica não realizam conversão de comprimento de onda. Desta forma, o cálculo de rota está sujeito ao problema da restrição de continuidade de comprimento de onda. As propostas também apresentam políticas de atribuição de comprimento de onda que provêm balanceamento na distribuição dos caminhos ópticos. Os ganhos obtidos na utilização das propostas apresentadas são avaliados através de simulações usando o simulador de redes WDMSim. A efetividade da primeira proposta foi comparada com a de uma implementação do protocolo OBGP utilizando-se o simulador WDMSim. A probabilidade de bloqueio gerada pelo OBGP foi até 13 pontos percentuais maior que a probabilidade de bloqueio da proposta 1, enquanto que a sobrecarga de controle gerada pelo OBGP foi de até 5 ordens de magnitude maior que a gerada pela proposta 1. A efetividade da segunda solução foi comparada com a da primeira solução utilizando-se o WDMSim. Mostrou-se que a probabilidade de bloqueio da proposta 1 foi até 10 vezes maior que a probabilidade de bloqueio da proposta 2. A sobrecarga gerada pela proposta 2 foi muito baixa para todos os valores de carga considerados, enquanto que para a solução 1 a sobrecarga cresce com o aumento da carga. O desempenho da terceira abordagem é avaliado considerando diferentes parâmetros. As simulações realizadas confirmam que o grande crescimento da sobrecarga de sinalização ao se atingir vários PCEs no processo de atualização vai de encontro ao potencial de diminuição da probabilidade de bloqueio devido a instabilidade gerada nas TEDs. Sendo assim, das três soluções apresentadas, a segunda foi a que se mostrou mais eficiente em termos de probabilidade de bloqueio Abstract: Despite advances in provisioning intra-domain lightpaths in Wavelength Division Multiplexing (WDM) networks, efficient schemes for path computation and advertisement of optical resources in multi-domain mesh networks have not yet been fully established. Because they are subject to scalability constraints, optical domains need simple and efficient schemes. Most of the solutions presented in the literature do not support traffic engineering and are based on periodic flooding of control messages. This work presents three proposals for provisioning lightpaths in multi-domain WDM networks based on the Path Computation Element (PCE) architecture. Proposals are formed by a schema for advertising information about network link state combined with domain chain computation and end-to-end route computation schemes. It is considered that the network optical switches do not perform wavelength conversion. Thus, the route computation is subject to the problem of wavelength continuity constraints. The proposals also present wavelength assignment policies that provide balance in the distribution of optical paths. The gains made in the use of the proposals submitted are evaluated through simulations using the WDMSim networks simulator. The effectiveness of the first proposal was compared to an implementation of the OBGP protocol using the WDMSim simulator. The blocking probability generated by OBGP was up to 13 percentage points higher than the blocking probability of the proposal 1, while the control overhead generated by OBGP was up to 5 orders of magnitude greater than that generated by the first proposal. The effectiveness of the second solution was compared to the first solution using the WDMSim. It was shown that the blocking probability generated by the first proposal was up to 10 times greater than the blocking probability of the second proposal. The control overhead generated by the proposal 2 was very low for all load values considered, while for the solution 1 overloading grows with load increasing. The performance of the third approach is evaluated considering different parameters. The simulations performed confirm that the growth of signaling overhead to achieve several PCEs in the updating process goes against the pontencial decrease of blocking due to instability caused in TEDs. Thus, considering the three solutions presented, the second was the more efficient in terms of blocking probability Mestrado Ciência da Computação Mestre em Ciência da Computação 2010/03020-4 FAPESP CAPES

Abstract

This paper reports a summary of the joint research activities on Optical Core Networks within the e-Photon-ONe+ project. It provides a reasonable overview of the topics considered of interest by the European research community and supports the idea of building joint research activities that can leverage on the expertise of different research groups. Thisworkwas supported by the e-Photon/ONe+ and BONE (“Building the Future Optical Network in Europe”) projects funded by the European Commission through the 6th and 7th ICT-Framework Programme