Use este identificador para citar o ir al link de este elemento:
http://hdl.handle.net/1843/ESBF-9GMP76| Tipo: | Dissertação de Mestrado |
| Título: | Abordagem matemática e algorítmica do problema de roteamento e agregação de tráfego em redes ópticas |
| Autor(es): | Rangel Silva Oliveira |
| primer Tutor: | Geraldo Robson Mateus |
| primer Co-tutor: | Fernanda Sumika Hojo de Souza |
| primer miembro del tribunal : | Daniel Fernandes Macedo |
| Segundo miembro del tribunal: | Mauro Nacif Rocha |
| Tercer miembro del tribunal: | Thiago Ferreira de Noronha |
| Cuarto miembro del tribunal: | Fernanda Sumika Hojo de Souza |
| Resumen: | A necessidade de se transmitir grandes volumes de dados em redes, com o mínimo de atraso possível, impulsionou pesquisas na área de telecomunicações. As redes ópticas proporcionaram, então, uma infraestrutura para comutação e transmissão de dados de alto desempenho, provendo altas taxas de transmissão e pequeno atraso na entrega dos dados. O comprimento de onda, como unidade de transporte na rede, possui um alto potencial de transmissão de dados. Entretanto, ao se atender um conjunto de requisi ções sem a devida preocupação com a melhor utilização de seus recursos, diversos critérios referentes a qualidade de serviço podem ser prejudicados. Por isso, a agrega- ção de tráfego, que possibilita que diversas demandas sejam trafegadas em um mesmo comprimento de onda, é adotada para prover uma melhor utilização do meio óptico. Além disso, estratégias de proteção contra falhas e balanceamento de carga passam a ser necessárias para que as redes ópticas possam ser utilizadas de forma otimizada, garantindo assim confiabilidade e escalabilidade. Este trabalho apresenta modelos matemáticos e algoritmos para o problema de roteamento, atribuição de comprimentos de onda, agregação de tráfego e proteção em redes ópticas. São analisados diversos critérios como minimização do número de saltos e do número de comprimentos de onda alocados, maximização do balanceamento de carga na rede e do número de requisições atendidas. Eles são tratados nos cenários de único domínio e multi-domínio, este último considerando as abordagens integrada e hierárquica. Como o problema é de alta complexidade, sendo sua solução exata inviável para instâncias de grande porte, foram propostos algoritmos polinomiais, um baseado em GRASP e um outro em um algoritmo evolucionário. Eles são testados com diversas instâncias da literatura e seus resultados são comparados entre si e com a solução ótima obtida pela resolução do modelo matemático associado. Este último é resolvido pelo pacote comercial CPLEX. Os algoritmos apresentaram bons resultados para os critérios, alcançando valores xiii de função objetivo bem próximos aos obtidos pelo pacote comercial CPLEX. O que leva a concluir que esses algoritmos podem ser utilizados em cenários mais realistas. |
| Abstract: | The necessity to transmit large amounts of data in networks, with low delay, boosted research in the telecommunications area. Optical networks have provided an infrastructure for high-performance switching and data transmission, providing high transmission rates having a short delays in data delivery. The wavelength, as transport unit in the network, has a high potential for data transmission. However, when a set of requests is routed without concern for the best usage of network resources, various quality of service criteria can be affected. Therefore, techniques for traffic grooming, that enables various demands to be transmitted in the same wavelength, fail-safe protection and load balancing may become necessary for the optical fiber to be used optimally, ensuring reliability and scalability. This paper presents mathematical models and heuristics for the routing and wavelength assignment problem, traffic grooming and fail-safe protection in optical networks. Various criteria are analyzed such as minimizing the number of hops and the number of allocated wavelengths, maximizing the network load balancing and the number of requests served. They are analized in single domain and multi-domain scenarios, the latter considering integrated and hierarchical approaches. Since the problem is of high complexity, and its exact solution is impractical for large instances, polynomial algorithms have been proposed, one being based on GRASP and another based on an evolutionary algorithm. They are tested with several instances of the literature and the results are compared to the optimal solution obtained with the mathematical model resolution. The latter is solved in a commercial package called CPLEX. The algorithms have shown good results for the criteria, achieving objective function values very close to those obtained by the commercial package CPLEX. What leads to the conclusion that these algorithms can be used in more realistic scenarios. |
| Asunto: | Computação |
| Idioma: | Português |
| Editor: | Universidade Federal de Minas Gerais |
| Sigla da Institución: | UFMG |
| Tipo de acceso: | Acesso Aberto |
| URI: | http://hdl.handle.net/1843/ESBF-9GMP76 |
| Fecha del documento: | 24-jun-2013 |
| Aparece en las colecciones: | Dissertações de Mestrado |
archivos asociados a este elemento:
| archivo | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| rangelsilvaoliveira.pdf | 4.82 MB | Adobe PDF | Visualizar/Abrir |
Los elementos en el repositorio están protegidos por copyright, con todos los derechos reservados, salvo cuando es indicado lo contrario.