Algoritimos de Otimização para Redes de Telecomunicações

Prévia do material em texto

Programa de Pós-Graduação em Engenharia Elétrica 
Centro de Pesquisa e Desenvolvimento em Engenharia Elétrica 
Escola de Engenharia da Universidade Federal de Minas Gerais 
 
 
 
 
 
Algoritmos de Otimização para Redes de 
Telecomunicações
 
 
 
Autor: Sérgio Miguel Ferreira 
Orientador: Prof. Dr. João Antônio de Vasconcelos 
 
 
 
Belo Horizonte 
Fevereiro, 2000. 
 Algoritmos de Otimização para Redes de Telecomunicações 2 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Nenhuma investigação merece o nome de Ciência 
se não passa pela demonstração matemática, 
nenhuma certeza existe onde não se pode aplicar um 
ramo das ciências matemáticas ou se não pode ligar com 
essas ciências. 
 
Leonardo da Vinci 
 Algoritmos de Otimização para Redes de Telecomunicações 3 
Agradecimentos 
Ao Prof. João Antônio de Vasconcelos pelo incentivo e motivação para o 
desenvolvimento deste trabalho, bem como pela sua indiscutível capacidade técnica, 
competência e orientação. 
Ao Programa de Apoio Temporário à Pós-Graduação – Convênio FAPEMIG- 
FIEMG/IEL.MG/98-99 pelo incentivo na forma de bolsa de mestrado. 
A TELEMAR – MG, representada pelo Eng. Eletricista Ubirajara Fumega. 
Aos meus pais – Geraldo Miguel e Amara Rosa. 
 Algoritmos de Otimização para Redes de Telecomunicações 4 
Resumo 
Nos últimos anos observou-se o surgimento de novas tecnologias para redes de 
transporte de dados digitais objetivando responder às necessidades das operadoras. 
Desta forma, surgiram: Hierarquia Digital Síncrona (SDH) como uma rede de transporte 
básica, Redes Digitais de Serviços Integrados (ISDN) para utilização em serviços 
integrados, Modo de Transferência Assíncrono (ATM) para transmissão de dados em 
fibra óptica. A SDH é largamente empregada pelas operadoras de telefonia para o 
transporte de serviços, incluindo vídeo, dados e telefonia. A razão para tal decorre em 
parte da compatibilidade com a PDH (não requerendo mudanças significativas nas 
estruturas ópticas para regiões menos competitivas) e por outro lado, devido a SDH 
constituir-se em uma tecnologia aberta. 
Atualmente, as redes de acesso tradicionais são altamente especializadas e inflexíveis, 
ou seja, cada serviço individual requer equipamentos dedicados de transportes 
especializados. Isto significa que, as redes de dados, telefonia (voz), devem utilizar uma 
infra-estrutura inteiramente separada; utilizam ainda topologia ponto-ponto que limita a 
largura de faixa e a disponibilidade da rede. Adicionalmente, têm interfaces não 
padronizadas e nem modulares, aumentando o custo do ciclo de vida (LCC) e limitando 
a flexibilidade da rede. Em conseqüência, estas se tornaram obsoletas, ineficazes e 
incapazes de atenderem à demanda dos usuários finais, particularmente os setores 
financeiro e comercial. Desta forma, é necessário migrar tais redes para outras de 
transporte mais eficientes e uma das formas de fazer-se isto é através da utilização da 
SDH. Além disso, a nova rede deve ser montada com os tráfegos bem distribuídos e, 
para realizar tal feito, é necessário o emprego de ferramentas de otimização aplicadas a 
redes de transportes. 
Neste trabalho desenvolveu-se um software para a sintetização, otimização e roteamento 
de redes de transportes digitais. A sintetização implementada está restrita às topologias 
de rede tipo árvore. Os algoritmos Genéticos e Dijkstra foram escolhidos para 
solucionar essas três classes de problemas. Os objetivos principais dessa dissertação 
são: 1. Construir topologia em árvore de custo mínimo interligando todas as estações, 
para o problema específico de sintetização de rede; 2. Informar ao administrador de 
redes, a melhor forma de redistribuir os pacotes digitais (grandezas inteiras) entre as 
estações; 3. Rotear todos os agregados STM-N das estações origens para as estações 
destinos. 
 
 
 
 
 Algoritmos de Otimização para Redes de Telecomunicações 5 
Abstract 
In the last years it was observed the explosion of new technologies for transport 
networks of digital data to satisfy the operator necessities. The Synchronous Digital 
Hierarchy (SDH) appeared as a basic network of transport, the Integrated Services 
Digital Network (ISDN) for use of integrated service, the Asynchronous Transfer Mode 
(ATM) for data transmission in optic fiber. However, only the SDH became acceptable 
as the technology currently more adjusted for the carrier of services, including video, 
data and telephony. Others technologies are still being evaluated in the intention to 
dominate the market, but each one of them always uses SDH as the carrier layer or as a 
complement of carrier in the end of the path. 
Currently, the networks of traditional accesses are highly specialized and inflexible, in 
other words, each specific service requires dedicated equipment of specialized carriers. 
This means that the networks of data, telephony (voice), must use a total separate 
substructure; they still use topologies that limit the bandwidth and availability of the 
network. Additionally, they haven’t standardized and neither modular interfaces, 
magnifying the cost of the life cycle (LCC) and limiting the flexibility of the network. 
In consequence, these had become obsolete, inefficacious and incapable to attend the 
demand of the final users, particularly the financial and commercial sectors. 
In this work, it was developed a computational program to perform the tasks of 
synthesis, optimization and routing for digital transport networks. The implemented 
synthesis is applicable in the design of tree-structured networks only. The Simple 
Genetic and Dijkstra algorithms were considered to the solution of the three classes of 
problems. The main objectives in this work were: 1. To build topological tree of 
minimum cost joining all stations, for the specific problem of network synthesis, 2. To 
report to the network administrator the better way to distribute between the stations the 
digital packages (integer greatness), and 3. Routing of all the STM-N aggregates from 
the origin to destination stations. 
 
 
 
 
 Algoritmos de Otimização para Redes de Telecomunicações 6 
Sumário 
AGRADECIMENTOS ...........................................................................................................3 
RESUMO................................................................................................................................4 
ABSTRACT............................................................................................................................5 
ÍNDICE DE FIGURAS..........................................................................................................10 
INTRODUÇÃO ....................................................................................................................12 
I REDE SDH......................................................................................................................15 
INTRODUÇÃO.........................................................................................................................15 
I.1 HIERARQUIA DIGITAL PLESIÓCRONA (PDH)...............................................................15 
I.1.1 DEFINIÇÕES DE REDE PDH ..........................................................................................15 
I.1.2 TAXAS DE DADOS PDH................................................................................................16 
I.1.3 VISÃO GERAL DOS COMPONENTESDE UM SISTEMA ÓPTICO..........................................16 
I.1.4 TECNOLOGIA PDH – LIMITAÇÕES................................................................................17 
I.2 HIERARQUIA DIGITAL SÍNCRONA ................................................................................18 
I.2.1 ESTRUTURA DE MULTIPLEXAÇÃO EM REDES SDH........................................................19 
I.2.2 ESTRUTURA DO FRAME STM-N...................................................................................21 
I.2.3 CAMADAS DA REDE SDH.............................................................................................21 
I.2.4 TAXAS DE TRANSMISSÃO DE DADOS............................................................................22 
I.3 ANÉIS SDH ...................................................................................................................23 
I.3.1 PROTEÇÃO EM ANÉIS...................................................................................................24 
I.3.1.1 Estrutura em anel unidirecional.................................................................................24 
I.3.1.2 Estrutura em anel bidirecional ..................................................................................25 
I.3.2 BLOCOS FUNCIONAIS COMPOSTOS SDH.......................................................................27 
CONCLUSÃO DO CAPÍTULO ...................................................................................................31 
II ROTEAMENTO DE UMA REDE DE TRANSPORTE ..............................................32 
INTRODUÇÃO.........................................................................................................................32 
II.1 ROTEAMENTO E TRÁFEGO EM UMA REDE DE TRANSPORTE .......................................32 
II.1.1 TOPOLOGIA DE UMA REDE..........................................................................................33 
II.1.2 DISTRIBUIÇÃO DE INFORMAÇÕES................................................................................34 
II.1.2.1 Roteamento dependente do tempo ...........................................................................34 
II.1.2.2 Roteamento dependente do estado ...........................................................................35 
II.1.2.3 Roteamento dependente do evento...........................................................................35 
II.1.2.4 Roteamento automático alternativo (irreversível).....................................................36 
 Algoritmos de Otimização para Redes de Telecomunicações 7 
II.1.2.5 Re-roteamento automático.......................................................................................36 
II.2 REPRESENTAÇÃO DE REDES........................................................................................37 
II.2.1 GRAFO INCIDENTE DE NÓ E ARCO...............................................................................37 
II.2.2 GRAFO NÓ-NÓ ADJACENTES.......................................................................................38 
CONCLUSÃO DO CAPÍTULO ...................................................................................................40 
III FORMULAÇÃO..........................................................................................................41 
INTRODUÇÃO.........................................................................................................................41 
III.1 PESQUISA BIBLIOGRÁFICA .........................................................................................41 
III.2 PLANEJAMENTO DO DESENVOLVIMENTO DE REDES DE TELECOMUNICAÇÕES .........44 
III.3 PLANEJAMENTO DA UTILIZAÇÃO DE REDES DE TELECOMUNICAÇÕES .....................45 
III.4 FORMULAÇÃO MATEMÁTICA PARA PROBLEMA DE SÍNTESE DE REDE ......................46 
III.5 FORMULAÇÃO MATEMÁTICA PARA O PROBLEMA DE OTIMIZAÇÃO DE REDES – 
DISTRIBUIÇÃO DOS AGREGADOS STM-N COM CUSTO MÍNIMO ............................................48 
CONCLUSÃO DO CAPÍTULO ...................................................................................................49 
IV ALGORITMOS PARA OTIMIZAÇÃO E ROTEAMENTO.....................................50 
INTRODUÇÃO.........................................................................................................................50 
IV.1 ALGORITMOS GENÉTICOS .........................................................................................50 
IV.1.1 MODELAGEM DO PROBLEMA DE SÍNTESE DE REDE.....................................................52 
IV.1.1.1 População inicial ...................................................................................................53 
IV.1.1.2 Representação das variáveis...................................................................................54 
IV.1.1.3 Seleção ..................................................................................................................55 
IV.1.1.4 Cruzamento ...........................................................................................................56 
IV.1.1.5 Mutação.................................................................................................................57 
IV.1.1.6 Processo de reparo .................................................................................................57 
IV.1.1.7 Avaliação dos indivíduos .......................................................................................57 
IV.1.1.8 Adaptação dinâmica...............................................................................................58 
IV.2 ALGORITMO DE DIJKSTRA .........................................................................................59 
IV.2.1 ANÁLISE DO ALGORITMO..........................................................................................64 
CONCLUSÃO DO CAPÍTULO ...................................................................................................66 
V IMPLEMENTAÇÃO DO OTIMIZADOR DE REDES SDH ......................................67 
INTRODUÇÃO.........................................................................................................................67 
V.1 MODULARIZAÇÃO .......................................................................................................67 
V.2 AMBIENTE GRÁFICO ....................................................................................................73 
V.3 DIFICULDADES NA IMPLEMENTAÇÃO ..........................................................................74 
CONCLUSÃO DO CAPÍTULO ...................................................................................................74 
VI RESULTADOS ............................................................................................................75 
INTRODUÇÃO.........................................................................................................................75 
VI.1 EXEMPLIFICAÇÃO DO ALGORITMO GENÉTICO .........................................................75 
VI.1.1 FUNÇÕES TESTES......................................................................................................76 
VI.1.1.1 Função descontínua ...............................................................................................76 
VI.1.1.2 Rastrigin................................................................................................................77 
VI.2 EXEMPLIFICAÇÃO DO MÓDULO ROTEADOR – ALGORITMO DE DIJKSTRA ...............79 
VI.3 EXEMPLIFICAÇÃO DO MÓDULO OTIMIZADOR – ALGORITMO DE DIJKSTRA .............80 
 Algoritmos de Otimização para Redes de Telecomunicações 8 
VI.4 EXEMPLIFICAÇÃO DO MÓDULO SINTETIZADOR – ALGORITMOS GENÉTICO E 
DIJKSTRA ..............................................................................................................................83VI.5 APLICAÇÃO DO SOFTWARE OPTIMIZED SDH NETWORK BUILDER ..........................86 
VI.5.1 OTIMIZAÇÃO DE REDES DE TRANSPORTES DIGITAIS...................................................86 
VI.5.2 ROTEAMENTO...........................................................................................................88 
VI.5.3 SINTETIZAÇÃO..........................................................................................................89 
CONCLUSÃO – PERSPECTIVAS DE TRABALHOS FUTUROS .....................................................92 
CONCLUSÃO ......................................................................................................................94 
BIBLIOGRAFIA ..................................................................................................................95 
 Algoritmos de Otimização para Redes de Telecomunicações 9 
Índice de tabelas 
 
Tabela 1.1 – Taxas de dados PDH nos EUA e Japão. ............................................................................16 
Tabela 1.2 – Taxas de dados PDH recomendados pelo ITU-T. ..............................................................16 
Tabela 1.3 – Mapeamento de tributários nos contêineres.......................................................................19 
Tabela 1.4 – Composição dos contêineres virtuais de ordem inferior (LO VCs). ....................................20 
Tabela 1.5 – Composição dos contêineres virtuais de ordem superior (HO VCs). ..................................20 
Tabela 1.6 – Conteúdo da Unidade de Tributário (TU)..........................................................................20 
Tabela 1.7 – Conteúdo do Grupo de Unidades de Tributário (TUG). .....................................................20 
Tabela 1.8 – Conteúdo da Unidade Administrativa (AU). ......................................................................20 
Tabela 1.9 – Conteúdo do Grupo de Unidades Administrativas (AUG). .................................................21 
Tabela 1.10 – Camada da rede SDH. ....................................................................................................21 
Tabela 1.11 – Nível do SDH..................................................................................................................23 
Tabela 3.1 – Variação do número de estruturas em árvores...................................................................46 
Tabela 6.1 – Conjunto de parâmetros utilizados no SGA .......................................................................75 
Tabela 6.2 – Resultados numéricos função descontínua.........................................................................76 
Tabela 6.3 – Resultados numéricos função de Rastrigin. .......................................................................78 
Tabela 6.4 – Índices de acertos e erros para cada uma das funções simuladas pelo software. ................79 
Tabela 6.5 – Rotas obtidas a partir da simulação da rede da Fig. 6.2. ...................................................80 
 
 Algoritmos de Otimização para Redes de Telecomunicações 10
Índice de Figuras 
Fig. 1.1 – Componentes ópticos de transmissão / recepção de sinais. ....................................................16 
Fig. 1.2 – Estrutura de multiplexação da SDH. .....................................................................................19 
Fig. 1.3 – Matriz do sinal STM-N..........................................................................................................21 
Fig. 1.4 – Modelo de rede em camadas. ................................................................................................22 
Fig. 1.4a – ULSR sem faltas..................................................................................................................24 
Fig. 1.5 – ULSR com faltas. ..................................................................................................................24 
Fig. 1.6 – UPSR sem faltas. ..................................................................................................................25 
Fig. 1.7 – UPSR com faltas. ..................................................................................................................25 
Fig. 1.8 – BLSR sem faltas. ...................................................................................................................25 
Fig. 1.9 – BLSR com faltas....................................................................................................................25 
Fig. 1.10 – BLSR-F sem faltas...............................................................................................................26 
Fig. 1.11 – BLSR-F com faltas. .............................................................................................................26 
Fig. 1.12 – BSSR sem faltas. .................................................................................................................26 
Fig. 1.13 – BSSR com faltas..................................................................................................................26 
Fig. 1.14 – LOI.....................................................................................................................................27 
Fig. 1.15 – HOI. ...................................................................................................................................27 
Fig. 1.16 – TTF.....................................................................................................................................28 
Fig. 1.17 – LPC....................................................................................................................................28 
Fig. 1.18 – HPC. ..................................................................................................................................28 
Fig. 1.19 – HOA. ..................................................................................................................................29 
Fig. 1.19a – Exemplo de um Cross-Connect. .........................................................................................29 
 Fig. 1.20 – Sem a utilização do bloco HPC. .........................................................................................30 
Fig. 1.21 – Sem a utilização do bloco LPC............................................................................................30 
Fig. 1.22 – Sem a utilização dos blocos HPC e LPC..............................................................................30 
Fig. 1.23 – Exemplo de acesso de tributários de 44.736 Mbits/s a partir de um agregado STM-4. ..........31 
Fig. 2.1 – Exemplo de uma topologia de rede. .......................................................................................33 
Fig. 2.2 – Exemplo de roteamento dependente do tempo........................................................................34 
Fig. 2.3 – Exemplo de roteamento dependente do evento. ......................................................................36 
Fig. 2.4 – Exemplo de re-roteamento automático...................................................................................37 
Fig. 2.5 – Exemplo de montagem numa matriz de um grafo incidente de nó e arco.................................38 
Fig. 2.6 – Exemplo de montagem da matriz de conectividade.................................................................39 
Fig. 2.7 – Exemplo de variação na montagem da matriz de conectividade. ............................................39 
Fig. 3.1 – Efeito foldover. .....................................................................................................................45 
Fig. 4.1 – Diagrama de fluxo / Algoritmo Genético Simples (SGA). .......................................................52Fig. 4.2 Formação da população inicial – exemplo para um indivíduo e quatro estações.......................54 
Fig.4.2 – Representação das variáveis – exemplo para três estações. ....................................................55 
Fig. 4.4 – Cruzamento – exemplo para quatro estações. ........................................................................56 
Fig.4.5 – Mutação - exemplo para três estações. ...................................................................................57 
Fig. 4.6 - Ilustração dos nós intermediários ao longo do caminho mais curto entre os nós i e j. .............60 
Fig. 4.7 – Exemplo base para utilização do algoritmo de Dijkstra. ........................................................61 
Fig. 4.8 – Resultado do exemplo base para utilização do Algoritmo de Dijkstra.....................................64 
Fig. 4.9 – Interfaceamento do Algoritmo de Dijkstra com o SGA. ..........................................................65 
Fig. 4.10 – Diagrama de fluxo / modo de encontrar a rede sintetizada de custo mínimo. ........................66 
Fig.5.1 – Todos os subprogramas e parâmetros que compõem o otimizador de redes SDH ....................68 
Fig. 5.3 – Visualização gráfica da rede – exemplo de resultado obtido para sintetização de uma rede 
digital composta de 13 estações. ...........................................................................................73 
Fig.6.1 – Desempenho do SGA para 41 gerações, tomando como base à execução # 27.........................78 
Fig. 6.2 – Rede composta de sete nós interligados (BALAKRISHMAN, 1995). .......................................79 
Fig. 6.3 – Resultado da simulação do grafo da Fig. 6.2 utilizando o módulo roteador............................80 
Fig. 6.4 – Rede de transporte consistindo de 7 estações digitais. ...........................................................81 
Fig. 6.5 – Resultado final correspondendo à distribuição de todos os agregados STM-N em todos os 
enlaces da rede.....................................................................................................................83 
Fig. 6.6 – Disposição das quatro estações telefônicas digitais. ..............................................................83 
Fig. 6.7 – Desempenho do SGA para 10 gerações e o custo final da estrutura sintetizada. .....................85 
 Algoritmos de Otimização para Redes de Telecomunicações 11
Fig. 6.8 – Planta resultante para a simulação consistindo de 4 estações telefônicas..............................85 
Fig. 6.9 – Rede Metropolitana de dados SDH consistindo de 20 estações digitais, a cargo da RNP (Rede 
Nacional de Pesquisas) e que se constitui num Interporto Temático (dados retirados do site 
www.pop-pe.rnp.br)..............................................................................................................86 
Fig. 6.10 – Resultado final da Rede Metropolitana SDH, consistindo de 20 centrais digitais e onde pode 
ser visto o tráfego ideal a ser respeitado nos enlaces.............................................................88 
Fig. 6.11 – Rede telefônica digital composta de 10 centrais...................................................................89 
Fig. 6.12 – Resultado gráfico do roteamento realizado para uma rede composta de 10 estações, 
considerando a estação 1 (origem) e a estação 10 (destino). .................................................89 
Fig. 6.13 – Planta telefônica composta de 13 centrais digitais + 1 gateway satelital (dados retirados do 
site www.globalstar.com.br) . ...............................................................................................90 
Fig. 6.14 – Desempenho do SGA para 20 gerações e o custo final da estrutura sintetizada. ...................92 
Fig. 6.15 – Resultado final da planta telefônica composta de 13 centrais digitais + 1 gateway satelital. 92 
 
 
 Algoritmos de Otimização para Redes de Telecomunicações 12
Introdução 
Atualmente, muitas organizações independentes estão envolvidas na manutenção de 
uma rede pública de telefonia e estas, tanto por ordem técnica quanto por razões de 
segurança interna, são as maiores causadoras de restrições no desenvolvimento e 
planejamento dos processos de melhorias das qualidades das transmissões de dados 
digitais. Para o desenvolvimento e o planejamento dos processos deve haver total 
independência dos seus participantes para dimensionar a sua própria parte da rede. No 
passado, com a existência do monopólio público havia simplificações nos 
planejamentos, pois as empresas eram comuns e as dificuldades de planejamento 
relativas à segurança de trocas de informações entre as empresas envolvidas limitavam-
se aos troncos internacionais. 
Para o planejamento global de uma rede de transporte devem ser exploradas duas metas 
importantes: 
1. Utilizar interfaces comerciais inteligentes, permitindo escolher rotas alternativas em 
caso de falhas dos enlaces elétricos e/ou ópticos; 
2. Utilizar topologias de redes que abranjam a maior quantidade de nós possíveis, para 
que a sua utilização torne o projeto a ser implementado competitivo e 
economicamente viável. 
Constata-se na literatura especializada que as teorias de desenvolvimento ótimo de redes 
convergem para as idéias de construírem-se redes com custos mercadológicos altamente 
competitivos, dinâmicos e continuamente otimizados. Por outro lado, vê-se que os 
mecanismos de otimização por serem algo novo e /ou talvez ainda não bem 
compreendido pelos projetistas, são aplicados timidamente em redes pequenas, muitas 
vezes no âmbito de instituições governamentais (SEXTO et al., 1997). 
O desenvolvimento ótimo de uma rede caracteriza-se pela obtenção por parte da 
concessionária do máximo lucro através de duas metas: maximização da utilização dos 
equipamentos presentes para a interligação dos clientes às estruturas de transmissão e, 
minimização dos custos inerentes (pessoal, equipamentos). A rede deve ser 
desenvolvida de maneira modular providenciando flexibilidade de modo a permitir 
crescimento gradual de acordo com a demanda do mercado. Os troncos de transmissão 
devem ter múltiplos serviços que compartilhem investimentos com a utilização inicial 
de equipamentos comuns, providenciando expansão planejada de acordo com a 
elevação da receita obtida. 
Esta breve explanação, de caráter introdutório, mostra a necessidade de estudar-se em 
nível de projeto como sintetizar, otimizar e rotear, os recursos disponíveis (agregados do 
Módulo de Transporte Síncrono de índice N) presentes numa rede de Hierarquia Digital 
Síncrona, com o intuito de melhorar o desempenho dos sistemas de transmissões 
existentes e por conseguinte, melhorar o atendimento do cliente final. Neste trabalho, 
desenvolveu-se um software de sintetização / otimização / roteamento de redes 
intitulado Optimized SDH Network Builder em ambiente WINDOWS NT tm e em 
linguagem C++ Orientado para Objeto. Empregaram-se nas tarefas pertinentes os 
 Algoritmos de Otimização para Redes de Telecomunicações 13
seguintes algoritmos: sintetização (Algoritmo Genético Simples acoplado ao Algoritmo 
de Dijkstra); otimização (Algoritmo de Dijkstra); roteamento (Algoritmo de Dijkstra). 
A utilização do Algoritmo Genético para a obtenção de soluções próximas do ótimo 
para uma variedade de problemas de sínteses de redes de comunicações tem sido 
explorada por diversos autores. (LARDIÈS et al., 1998) desenvolveram um programa 
para avaliar e dimensionar a um custo mínimo redes ópticas SDH, com 19 nós e 39 
enlaces interconectados aos backbones de comunicações das principais cidades 
européias, cuja metodologia aplicou-se tanto à camada óptica quantoà camada elétrica; 
(MINOUX, 1989) desenvolveu um trabalho a respeito do tráfego entre as estações 
origem e destino a um custo mínimo, aplicado as MANs, LANs, ISDN, Digital Cellular 
Network; (BERRY et al., 1998) propuseram a utilização de Algoritmos Genéticos 
acoplados a Programação Linear para a resolução do problema referente a sintetização 
de sistemas de comunicações. Relatam que problemas de sintetização de redes são 
conhecidos como NP-completo e a natureza combinatória dos GAs são indicadas como 
uma nova ferramenta capaz de substituir as programações matemáticas clássicas. 
Propuseram uma formulação matemática fundamentada no tráfego requerido entre as 
estações origem e destino, bem como o custo por unidade de fluxo nos enlaces. 
Apontam a vantagem da utilização do GA como uma ferramenta poderosa no sentido de 
fazer múltiplos ajustes na rede a cada iteração. Todos esses trabalhos justificam a 
escolha do GA utilizado. 
No capítulo 1 são feitos estudos comparativos entre as tecnologias PDH e SDH, bem 
como justificativas técnicas do seu largo emprego em redes metropolitanas (MANs). 
Também, dá-se destaque a elaboração de estruturas em anéis e blocos funcionais, como 
forma de motivar a adoção daquelas estruturas nas redes, pois se empregadas 
certamente oferecerão maior fluidez ao tráfego de dados digitais. 
No capítulo 2 estuda-se o problema do roteamento de uma rede de transporte. São 
apresentados tópicos referentes a esquemas de roteamentos e formas matriciais de 
representações de redes. 
No capítulo 3 são apresentadas as formulações matemáticas para as resoluções dos 
problemas de sintetização e otimização de redes de transportes digitais. Já o problema 
de roteamento não tem uma formulação específica, pois há algoritmos determinísticos 
construídos de forma a realizar esta tarefa e que são largamente empregados em redes 
de comunicações (Dijkstra, Floyd e outros). Estes algoritmos investigam os custos 
presentes nos enlaces conectados as estações de modo sucessivo, ou seja, até atingir a 
estação final. Ao final do processo tem-se uma trajetória de custo mínimo para o 
transporte de dados digitais. As formulações matemáticas foram elaboradas a partir das 
idéias apresentadas nos seguintes itens: pesquisa bibliográfica; planejamento do 
desenvolvimento e utilização de redes de telecomunicações. 
No capítulo 4 são estudados os Algoritmos SGA e Dijkstra. A partir deles, são possíveis 
as realizações de três importantes tarefas numa rede de telefonia digital: sintetização 
(somente para topologia em árvore); otimização de frames e roteamento de dados. 
Assim, este capítulo constitui-se no cerne do trabalho de dissertação e ambos os 
Algoritmos garantem o sucesso dos resultados obtidos com o emprego das formulações 
matemáticas. 
 Algoritmos de Otimização para Redes de Telecomunicações 14
O capítulo 5 trata da implementação do software otimizador de redes. São apresentados 
todos os detalhamentos técnicos das confecções dos módulos sintetizador, otimizador e 
roteador. Abordam-se aspectos relevantes a respeito dos tipos de parâmetros utilizados 
em redes de transportes digitais. No final do capítulo, são tratadas as dificuldades da 
implementação computacional. 
Finalmente, no capítulo 6 são apresentados alguns resultados obtidos com o software 
desenvolvido, isto é, resultados na resolução de três aplicações práticas presentes no 
cotidiano das telefônicas. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Algoritmos de Otimização para Redes de Telecomunicações 15
I Rede SDH 
Introdução 
Neste capítulo são abordados temas referentes às redes de comunicação PDH e SDH. 
Nesta apresentação foram considerados três tópicos principais: Redes PDH; Redes SDH 
e Anéis SDH. O objetivo do primeiro tópico é fazer uma explanação sobre redes PDH 
(vantagens, desvantagens e principalmente limitações). O segundo tópico versa sobre a 
estrutura de multiplexação em redes SDH, a estrutura do frame STM-N, camadas de 
redes SDH e taxas de transmissão de dados. No terceiro tópico apresenta-se e se dá 
destaque a elaboração de estruturas em anéis e blocos funcionais como forma de 
proporcionar mais fluidez ao tráfego sobrecarregado de dados, causado por cortes nas 
fibras e/ou panes nos equipamentos pertencentes aos elementos de redes. 
I.1 Hierarquia Digital Plesiócrona (PDH) 
A seguir, apresenta-se o fundamento de redes PDH tendo como objetivo oferecer as 
condições necessárias para a compreensão de redes SDH que serão estudadas 
posteriormente. Inicialmente apresentam-se algumas definições importantes para a 
representação didática desse tema. Em seguida, temas referentes a multiplexagem e 
demultiplexagem de sinais digitais e taxas de dados PDH são vistos, permitindo-se 
assim uma visão geral dos componentes de um sistema óptico e suas limitações. 
I.1.1 Definições de rede PDH 
Constitui-se na tecnologia digital mais simples de ser implementada, desde que se tome 
o cuidado de não distribuí-la por percursos muito longos. Ela surgiu na área de 
transmissão de sinais telefônicos, onde sinais de alto nível (DS-n) (veja Tab.1.1) eram 
obtidos de múltiplos sinais de baixo nível adicionados a bits de enchimento para 
compatibilizar as diferentes velocidades de transmissão (LINDBERG, 1997). Neste 
sistema, o pacote de dados transporta no seu cabeçalho (overhead) informações sobre o 
percurso de todos os nós passados, criando desta maneira, cabeçalhos cada vez mais 
redundantes e pesados. 
Existem em nível mundial dois padrões de redes PDHs. Ambos são obtidos pela 
multiplexação síncrona de uma seqüência básica de 32 canais 64 Kbits/s, diferindo-se 
apenas no número de canais. São os seguintes: 
1. Europa: 32 canais ∗ 64 Kbits/s = 2048 Kbits/s (velocidade primária); 
2. EUA: 24 canais ∗ 64 Kbits/s = 1536 Kbits/s (velocidade primária). 
 
Em ambas as velocidades há a necessidade de correta sincronização nos extremos da 
fibra óptica para a correta multiplexagem e demultiplexagem dos sinais, de tal forma a 
garantir que os sinais possuam as mesmas freqüências. 
 Algoritmos de Otimização para Redes de Telecomunicações 16
I.1.2 Taxas de dados PDH 
Nas tabelas abaixo são mostradas as diferentes taxas de velocidades empregadas nos 
EUA e Japão (Tabela 1.1) e aquelas normalizadas pelo International 
Telecommunication Union – ITU-T, através da recomendação G.702, para a Europa. 
Tabela 1.1 – Taxas de dados PDH nos EUA e Japão. 
Níveis de sinais digitais Taxas de dados brutos 
(Kbits/s) 
Número de canais 
(dados) 
DS-0 64 1 
DS-1 1544 24 
DS-1C 3152 48 
DS-2 6312 96 
DS-3 44378 672 
 
Tabela 1.2 – Taxas de dados PDH recomendados pelo ITU-T. 
Níveis de sinais digitais Taxas de dados brutos 
(Kbits/s) 
Número de canais 
(dados + sinalização) 
1 2048 32 
2 8448 128 
3 34368 512 
4 139264 2048 
 
I.1.3 Visão geral dos componentes de um sistema óptico 
 
Fig. 1.1 – Componentes ópticos de transmissão / recepção de sinais. 
A seguir, listam-se os equipamentos mais comuns utilizados num sistema óptico MUX / 
DEMUX digital de acordo com o padrão ITU-T: 
• MUX: multiplexador; 
• DEMUX: demultiplexador; 
 Algoritmos de Otimização para Redes de Telecomunicações 17
• ELO: equipamento de linha óptica. Realiza a conversão dos sinais elétricos do MUX 
em sinais ópticos (e vice-versa) transmitindo-os e/ou recebendo-os da(s) fibra(s) 
óptica(s); 
• ELO 34: recebe do MUX uma seqüência de bits elétricos de 34 Mbits/s 
(recomendação G.703) e entrega aos cabos ópticos numa seqüência de pulsos de 45 
Mbits/s e vice-versa; 
• Caixa de emendas: acomoda asemendas do cabo óptico; 
• MCP-120: MUX 2 / 8 Mbits/s; 
• MCP-480: MUX 8 / 34 Mbits/s; 
• MCP-1920: MUX 34 / 140 Mbits/s; 
• Duplo-salto: MUX 2 / 34 Mbits/s; 
• Triplo-salto: MUX 2 / 140 Mbits/s. 
 
Foge ao objetivo deste trabalho descrever minuciosamente estes equipamentos. Maiores 
detalhes podem ser obtidos em LINDBERG (1997). 
 
I.1.4 Tecnologia PDH – limitações 
Em seqüência, ilustra-se o problema de flexibilidade de uma rede PDH considerando a 
seguinte situação hipotética: o administrador da rede necessita prover a um cliente 
comercial uma linha dedicada alugada com a taxa de 2 Mbits/s. 
Se um canal de velocidade, de 140 Mbits/s, por exemplo, passa próximo ao cliente, 
ótimo! A operação de fornecer uma linha de 2 Mbits/s dentro desse canal parece ser 
bastante fácil. Na prática, não é tão simples quanto aparenta. 
Para extrair 2 Mbits/s do canal de 140 Mbits/s, deve-se demultiplexá-lo em vias de 34 
ou 2 Mbits/s. Identificada a linha requerida de 2 Mbits/s, os canais devem ser 
remontados, isto é, multiplexados novamente a fim de alcançarem a taxa de transmissão 
de dados brutos de 140 Mbits/s. 
Fica evidente que o problema de retirar e inserir canais não traz flexibilidade e provisão 
rápida dos serviços, pois equipamentos demultiplex e multiplex são extremamente 
caros. 
 
Na tecnologia PDH há várias desvantagens que limitam sua continuidade. Dentre 
outras, pode-se destacar as mais importantes: 
• Falta de flexibilidade na retirada de sinais de dados em diferentes níveis; 
• Inviabilidade econômica; 
 Algoritmos de Otimização para Redes de Telecomunicações 18
• Administração inadequada de equipamentos; 
• Monitoramento ruim; 
• Número elevado de equipamentos MUX / DEMUX, acarretando rotas com custos 
elevados e, por conseguinte, impossibilitando que todos os possíveis clientes 
acessem esta tecnologia. 
Devido a estas desvantagens, outras tecnologias foram desenvolvidas (ISDN, ATM, 
SDH) como forma de tornar o acesso ao mercado de comunicações menos restrito a 
empresas de pequeno porte. 
 
I.2 Hierarquia Digital Síncrona 
A padronização da Hierarquia Digital Síncrona SDH sinaliza o começo da revolução 
nas redes de comunicações em todo o mundo. A SDH, quando empregada na sua 
plenitude, deverá trazer benefícios tanto aos usuários finais, quanto aos operadores de 
redes e equipamentos manufaturados. 
Essa padronização representa um avanço em tecnologia que pode ser comparado em 
escala ao que ocorreu com a Transmissão por Modulação por Pulsos Codificados 
(PCM). 
Atualmente, os usuários finais, particularmente os de negócios, tornam-se cada vez mais 
dependentes de comunicações. Por isso, tem havido uma explosão na demanda de 
serviços de telecomunicações mais sofisticados. Serviços como videoconferência, 
acesso a bases remotas de dados, multimídia, requerem redes cada vez mais flexíveis 
com uma largura de faixa virtualmente ilimitada. Os sistemas plesiócronos de 
transmissão são incapazes de satisfazer esta demanda, pois utilizam ainda topologias 
ponto-ponto e taxas de dados brutos inferiores àquelas conseguidas pela SDH. 
A PDH evoluiu em resposta à demanda por telefonia mais eficiente e com maior banda 
passante. Já a SDH utiliza essencialmente a mesma fibra óptica da PDH, porém, pode 
aumentar significativamente a largura de faixa disponível ao reduzir a quantidade de 
equipamentos presentes na rede. Traz, além disso, maior flexibilidade à gerência de rede 
para a tomada de decisões. A SDH, por ser uma rede de transporte de dados digitais, foi 
concebida desde a sua padronização pelo ITU-T para trabalhar com entrada e saída de 
dados PDH. 
A SDH é estruturada de forma a permitir que os sinais plesiócronos sejam combinados 
juntos e encapsulados dentro de um único sinal padrão. Desta forma, tem-se a proteção 
do investimento das operadoras permitindo-as desdobrar o equipamento síncrono de 
forma que estes possam servir às necessidades particulares de sua rede. 
No momento que o equipamento síncrono encontra-se instalado na rede, os benefícios 
tornam-se visíveis, como economia de custos associada à redução na quantidade de 
elementos de redes, aumento da eficiência e da confiabilidade. O resultado imediato em 
decorrência do aumento da confiabilidade será a redução do número de equipamentos 
de reposição em estoque. 
 Algoritmos de Otimização para Redes de Telecomunicações 19
A seguir, os seguintes pontos serão discutidos: Estrutura de multiplexação em redes 
SDH; Estrutura do frame STM-N; Camada da rede SDH e Taxas de transmissão de 
dados. 
I.2.1 Estrutura de multiplexação em redes SDH 
A multiplexação em redes SDH pode ser ilustrada como na Fig.1.2. Esta estrutura de 
multiplexação foi padronizada pelo ITU-T. 
 
 
Fig. 1.2 – Estrutura de multiplexação da SDH. 
 
 
A descrição de cada bloco componente da estrutura mostrada na Fig.1.2 é feita a seguir: 
1. Contêiner (C): é uma estrutura de informação responsável pelo transporte do sinal 
tributário enquanto este permanece na rede SDH (NEC do BRASIL, 1998). O 
mapeamento de diferentes tributários em contêineres é mostrado na Tabela 1.3. 
Tabela 1.3 – Mapeamento de tributários nos contêineres. 
Contêiner Tributário mapeado (Mbits/s) 
C-4 139.264 
C-3 44.736 
C-12 2.048 
 
2. Contêiner Virtual (VC): é formado por uma estrutura de informação composta por 
uma carga útil (payload) mais o overhead de via (POH), o qual permite a 
monitoração do percurso realizado pelo sinal ao longo de um trajeto (Di-
LORENZO, 1998a). Nas tabelas 1.4 e 1.5, dadas a seguir, temos as possíveis 
combinações de VCs: 
 Algoritmos de Otimização para Redes de Telecomunicações 20
Tabela 1.4 – Composição dos contêineres virtuais de ordem inferior (LO VCs). 
LO VC T(µs) Payload 
VC-3 125 C-3 
VC-12 500 C-12 
 
Tabela 1.5 – Composição dos contêineres virtuais de ordem superior (HO VCs). 
HO VC T(µs) Payload 
VC-4 125 C-4 e/ou 3 TUG-3 
 
Nas tabelas acima, LO VC (VC-12, VC-3) é o contêiner virtual de ordem inferior 
(localizado na camada de via de ordem inferior – veja Tab.1.10); HO VC é o contêiner 
virtual de ordem superior (localizado na camada de via de ordem superior); T é o 
período de montagem do contêiner virtual e payload é a matriz contendo os dados úteis 
a serem transmitidos. 
3. Unidade de Tributário (TU): é uma estrutura de informação que faz a adaptação entre 
a camada de via de ordem inferior e a camada de via de ordem superior (veja Tab.1.10). 
É formada por um payload de informação (LO VC) e um ponteiro de TU que indica 
quantos bytes existem entre o início do quadro do payload em relação ao início do 
Virtual Contêiner de Ordem Superior (HO VC). 
Tabela 1.6 – Conteúdo da Unidade de Tributário (TU). 
Unidade de Tributário Payload 
TU-3 VC-3 
TU-12 VC-12 
 
4. Grupo de Unidade Tributário (TUG): é uma estrutura de informação formada pelo 
entrelaçamento byte a byte de TUs (NEC do BRASIL, 1998). 
Tabela 1.7 – Conteúdo do Grupo de Unidades de Tributário (TUG). 
Grupo de Unidade de Tributário Unidade de Tributário 
TUG-3 1* TU-3 
TUG-2 3* TU-12 
 
5. Unidade Administrativa (AU): é uma estrutura de informação que provê a adaptação 
entre a camada de via de ordem superior e a camada da seção multiplexadora (veja 
Tab.1.10). É formada por um payload de informação (HO VC) e um ponteiro de AU 
que indica quantos bytes existem entre o início do quadro do payload em relação ao 
início do quadro da seção multiplexadora (NEC do BRASIL, 1998). 
Tabela 1.8 – Conteúdo da Unidade Administrativa (AU). 
Unidade Administrativa Payload 
AU-4 VC-4 
 
 Algoritmos de Otimização paraRedes de Telecomunicações 21
6. Grupo de Unidades Administrativas (AUG): faz o entrelaçamento dos bytes das 
unidades administrativas (AUs) para a composição de uma estrutura de informação 
denominada AUG (NEC do BRASIL, 1998). 
Tabela 1.9 – Conteúdo do Grupo de Unidades Administrativas (AUG). 
Grupo de Unidades Administrativas Formato 
AUG 1* AU-4 
 
Na saída deste bloco, temos um sinal STM-N composto por um payload acrescido de 
um Overhead de Seção (SOH) para a monitoração da trajetória do sinal presente na 
camada de seção multiplexadora (NEC do Brasil, 1998). 
I.2.2 Estrutura do Frame STM-N 
Na Fig.1.3 , tem-se a matriz formadora da estrutura básica do sinal STM-N, onde: 
• RSOH é o Overhead da Seção Regeneradora; 
• AU PTR é o Ponteiro de Unidade Administrativa; 
• MSOH é o Overhead da Seção Multiplexadora; 
• AUG é o Grupo de Unidades Administrativas. 
 
Fig. 1.3 – Matriz do sinal STM-N. 
O quadro STM-N é formado por uma matriz de dimensões 9∗(N∗270) bytes 
(nove linhas∗N∗270 colunas), onde as informações são lidas da esquerda para a direita e 
de cima para baixo (NEC do BRASIL, 1998). 
 
I.2.3 Camadas da rede SDH 
Numa rede SDH há seis camadas distintas (NEC do BRASIL, 1998), as quais estão 
identificadas na Tabela 1.10. 
 
 Algoritmos de Otimização para Redes de Telecomunicações 22
Tabela 1.10 – Camada da rede SDH. 
1. Física 
2. Seção regeneradora 
3. Seção multiplexadora 
4. Via de ordem superior 
5. Via de ordem inferior 
6. Circuito 
 
A descrição dessas camadas é feita a seguir: 
1. Camada física: é a camada correspondente ao meio físico de transmissão 
(STM-N); 
2. Seção regeneradora: relaciona-se com a transmissão de informações entre 
multiplexadores e demultiplexadores; 
3. Seção multiplexadora: é a camada relacionada com a transmissão ponto-
ponto da informação entre locais que acessem rotas; 
4. Camada de via de ordem superior: é a camada responsável pela monitoração 
e pelo suporte da camada de circuito. Ela verifica a integridade das 
informações dos contêineres virtuais de ordem superior; 
5. Camada de via de ordem inferior: é a camada responsável pela monitoração e 
pelo suporte da camada de circuito. Ela verifica a integridade das 
informações dos contêineres virtuais de ordem inferior; 
6. Circuito: é a camada responsável pela entrada do sinal tributário proveniente 
de uma rede plesiócrona. 
 
Na Fig.1.4 se vê um exemplo de caminho nas camadas SDH de uma determinada rede 
de telecomunicações. O sinal tributário proveniente de uma rede plesiócrona chega na 
rede SDH pela camada de circuito (NEC do BRASIL, 1998). 
 
Fig. 1.4 – Modelo de rede em camadas. 
 
Da Fig.1.4 pode-se verificar que do ponto de acesso na SDH até a Camada de Seção 
Regeneradora é montado um Módulo de Transporte Síncrono de índice N (STM-N), 
obedecendo a uma estrutura de multiplexação que contempla todas as camadas SDH. O 
sinal STM-N é transmitido via fibra óptica na Camada Física e desce para a Camada de 
Seção Regeneradora para ser regenerado. Após, é transmitido via fibra óptica na 
Camada Física para um equipamento que faz conexão cruzada com outra malha da rede 
 Algoritmos de Otimização para Redes de Telecomunicações 23
SDH em nível da Camada de Via de Ordem Superior. Nessa nova malha o sinal deve 
ser retirado na mesma camada em que foi montado inicialmente, no caso, Camada de 
Via de Ordem Inferior para ser desmontado corretamente (NEC do BRASIL, 1998). 
I.2.4 Taxas de transmissão de dados 
Os dados são transmitidos numa rede SDH em quatro níveis principais, conforme 
mostrado na Tabela 1.11. O nível STM-1 é definido como a estrutura básica de 
transporte de informações. As taxas de bits dos níveis superiores constituem-se 
exclusivamente em múltiplos inteiros dessa velocidade básica (NEC do BRASIL, 1998). 
Tabela 1.11 – Nível do SDH. 
Níveis de sinais Taxas brutas (Mbits/s) 
STM-1 155.520 
STM-4 622.080 
STM-16 2488.320 
STM-64 9953.280 
 
Além destes níveis, há ainda uma estrutura denominada STM-0, com taxa bruta de 
51.840 Mbits/s, utilizada para sistemas de satélite e rádio-enlace, a qual é 
desconsiderada como um nível hierárquico (NEC do BRASIL, 1998). 
I.3 Anéis SDH 
Estruturas em anéis e blocos funcionais (representação unificada em diagrama de blocos 
de interfaces padronizadas pelo ITU-T, de forma que o planejador possa fazer o 
anteprojeto de uma rede SDH sem a necessidade de desenhar todos os circuitos) 
propiciam rotas alternativas para o escoamento de dados, em caso de corte da fibra 
óptica e/ou falha de funcionamento de elementos de rede, garantindo a continuidade do 
serviço prestado e, portanto, a sobrevivenciabilidade do sistema (existência de fibras 
ópticas reservas para transporte de sinais em caso de situações de pane física). 
As configurações em anéis são mais baratas que as configurações em estrelas, pois, 
basicamente são requeridas duas fibras para sistema unidirecional ou quatro fibras para 
sistema bidirecional. A comutação entre fibras se dá a taxas inferiores a 25µs, 
proporcionando maior fluidez ao tráfego. 
A estrutura de multiplexação da SDH foi elaborada prevendo-se uma grande 
flexibilidade, associada a um enfoque muito grande em software para permitir 
flexibilidade e gerência de rede, e além do mais, permitir compatibilidade de 
equipamentos de diferentes fabricantes, respeitando soluções próprias de fabricação de 
circuitos e placas. O ITU-T não definiu layout de placas nem circuitos, e sim blocos 
funcionais padronizados, que todo o fabricante deve prover em seus equipamentos 
SDH. Um bloco funcional não necessariamente necessita estar em uma placa. Pode estar 
em uma ou mais placas, bem como uma placa pode conter vários blocos funcionais 
(NEC do BRASIL, 1998). 
 Algoritmos de Otimização para Redes de Telecomunicações 24
Os blocos funcionais são importantes porque permitem a interligação de redes distintas 
de tal forma que o tráfego de dados se processe tanto num sentido quanto num outro 
(tráfego bidirecional) e, além disso, num mesmo anel, permitem que os nós capturem os 
frames STM-N de interesse e repassem adiante os demais. 
Em virtude do grau de importância dessas estruturas em nível de simulação de 
roteamento é que se detalhou minuciosamente cada uma delas nos itens seguintes. Vale 
ressaltar que no software desenvolvido implementou-se um módulo simulador de 
roteamento que permite o emprego de cada uma delas e dessa forma, propiciou-se ao 
leitor interessado a obtenção de dados de projetos realísticos. 
I.3.1 Proteção em anéis 
A recomendação G.841 do ITU-T trata dos métodos para proteção em anéis (Di-
LORENZO et al., 1998). Neste documento há orientações para se construir duas 
topologias básicas: 
• Estrutura em anel unidirecional; 
• Estrutura em anel bidirecional. 
Estas duas estruturas são descritas a seguir. Para fins de exemplificação considerou-se 
em todos os casos uma arquitetura em anel hipotético, consistindo de seis estações 
nomeadas A, B, C, D, E e F, onde a interrupção dos cabos sempre foi considerada 
ocorrendo entre as estações C e D. 
I.3.1.1 Estrutura em anel unidirecional 
Nesta estrutura os tráfegos de dados são transmitidos somente numa direção, como nas 
duas estruturas mostradas a seguir. 
Unidirectional Line-Switched Ring (ULSR) 
Fig. 1.4a – ULSR sem faltas. 
 Algoritmos de Otimização para Redes de Telecomunicações 25
 
Fig. 1.5 – ULSR com faltas. 
 
O mecanismo de chaveamento funciona da seguinte forma: 
1. Os elementos de rede B e E transmitem na fibra primária (fibra de trabalho); 
2. Uma interrupção é presumida entre os elementosD e C; a direção E → B não 
é afetada. Uma rota alternativa deve ser encontrada para a direção B → E. 
Os MUX C e D são então chaveados manualmente por um operador da 
concessionária, de forma a ligar a fibra de trabalho com a de backup, como 
mostrado na Fig.1.5. Este chaveamento permanece operante até o reparo da 
falha. 
 
Para fazer o chaveamento acima de modo eficaz, isolando a área danificada e dessa 
forma, evitando que dados brutos sejam perdidos, é imprescindível por parte do 
administrador da rede, o conhecimento prévio da configuração do anel 
(HABISREITINGER,1998). 
 
 
 
 
 
 
 
 
 
 Algoritmos de Otimização para Redes de Telecomunicações 26
Unidirectional path-switched ring (UPSR) 
Fig. 1.6 – UPSR sem faltas. 
 
Fig. 1.7 – UPSR com faltas. 
 
O mecanismo de chaveamento de proteção funciona da seguinte maneira: 
1. Os elementos de rede B e E transmitem em ambas as fibras. Os dados fluem 
simultaneamente na fibra 1 e na fibra 2 (Fig.1.6); 
2. Ocorrendo uma falha entre os MUX C e D, o multiplexador E chaveia a 
fibra 1 com a fibra 2, imediatamente restabelecendo o fluxo de dados 
(Fig.1.7). Não há interferência manual do operador de rede para fazer o 
chaveamento das fibras no multiplex. Nesta configuração que permite o 
chaveamento simples de fibras no anel, não é requerido o conhecimento 
prévio da configuração do anel para a restauração do fluxo de dados 
(HABISREITINGER,1998). 
 
 Algoritmos de Otimização para Redes de Telecomunicações 27
I.3.1.2 Estrutura em anel bidirecional 
Nesta estrutura os dados são transmitidos bidirecionalmente como nas quatro estruturas 
seguintes. 
 
Two-fiber bidirectional line-switched ring (BLSR) 
Fig. 1.8 – BLSR sem faltas. 
 
Fig. 1.9 – BLSR com faltas. 
 
Este mecanismo de chaveamento de proteção de linha funciona da seguinte forma: 
1. Uma interrupção é presumida entre os MUX C e D. Uma rota alternativa 
deve ser encontrada em ambas as direções de transmissão. Os MUX C e D 
 Algoritmos de Otimização para Redes de Telecomunicações 28
são então chaveados conforme a Fig.1.9. Este chaveamento permanece 
operante até o reparo da falha; 
2. O mecanismo de chaveamento é complexo e envolve o completo 
conhecimento da configuração do anel de modo a que o administrador de 
rede isole as partes danificadas, evitando que os dados brutos sejam perdidos 
(HABISREITINGER,1998). 
 
Four-fiber bidirectional line-switched ring (BLSR-F) 
 
Fig. 1.10 – BLSR-F sem faltas. 
 
Fig. 1.11 – BLSR-F com faltas. 
 
 Algoritmos de Otimização para Redes de Telecomunicações 29
Este mecanismo de chaveamento de proteção de linha funciona da seguinte maneira: 
1. Se, por exemplo, uma interrupção ocorre entre os elementos de rede C e D, 
as linhas de trabalho desses elementos são chaveadas através da linha de 
proteção; 
2. A conexão é automaticamente restabelecida pelos MUX presentes entre as 
falhas, através do chaveamento de pares de fibras ópticas, como pode ser 
melhor entendido comparado-se as Figuras 1.10 e 1.1. Neste mecanismo, é 
indispensável uma tabela de reconfiguração do anel que deverá estar presente 
nos MUX presentes fisicamente entre as falhas, de modo que eles possam 
interligar de modo automático, através de chaveamentos às fibras ópticas 
(HABISREITINGER,1998). 
 
Four-fiber bidirectional span-switched ring (BSSR) 
Fig. 1.12 – BSSR sem faltas. 
 
Fig. 1.13 – BSSR com faltas. 
 
 Algoritmos de Otimização para Redes de Telecomunicações 30
Este mecanismo de proteção funciona da seguinte forma: 
Se uma interrupção é presumida entre os elementos de rede C e D, somente dois pares 
de fibras são chaveados (presentes entre os MUX C e D). Na Fig.1.13 pode-se entender 
melhor como isto ocorre. 
Constata-se a partir da referida figura que nenhum dos outros MUX do anel são afetados 
pela falha e desta forma, a reconfiguração ocorre localmente em apenas dois 
multiplexadores. 
O mecanismo de chaveamento é complexo e envolve o conhecimento prévio da 
configuração do anel de modo a que o administrador de rede isole as partes danificadas, 
evitando que os dados brutos sejam perdidos (HABISREITINGER,1998). 
 
I.3.2 Blocos funcionais compostos SDH 
Apresentam-se a seguir alguns blocos funcionais compostos e equipamentos 
padronizados pelo ITU-T, com o intuito de mostrar as funcionalidades que estes têm ao 
serem acrescentados ao anel óptico, permitindo desta forma, rotear os dados em casos 
de falha em fibras ópticas e/ou equipamentos. 
Lower Order Interface (LOI) 
Bloco responsável pela realização da montagem / desmontagem de Virtuais Contêineres 
(VCs) de ordem inferior [VC-3, VC-12], também denominado de função de terminação 
de via de ordem inferior (CPqd BRASIL, 1997). A Fig.1.14 ilustra o símbolo padrão 
deste bloco 
 
Fig. 1.14 – LOI. 
 
Este bloco recebe na sua entrada tributários de 2.048 Mbits/s (síncrono ou plesiócrono) 
ou VC-12 e libera na sua saída VC-3. 
Higher Order Interfaces (HOI) 
Este bloco realiza a montagem e desmontagem de Virtuais Contêineres (VC) de ordem 
superior (VC-4) (CPqd BRASIL, 1997). A Fig.1.15 ilustra o símbolo padrão deste 
bloco. 
 Algoritmos de Otimização para Redes de Telecomunicações 31
 
Fig. 1.15 – HOI. 
 
Este bloco aceita na sua entrada, tributários de 140 Mbits/s (plesiócrono); libera na sua 
saída, VC-4. 
Transfer Terminal Function (TTF) 
Realiza a função de terminação das seções regeneradora, de multiplexação, bem como a 
montagem e desmontagem dos sinais STM-1, STM-4, STM-16 dos n*VC-4 (CPqd 
BRASIL, 1997). A Fig.1.16 ilustra o símbolo padrão deste bloco. 
 
Fig. 1.16 – TTF. 
 
Este bloco recebe na sua entrada VC-4 e libera, na sua saída, Módulos Síncronos de 
Transporte (STM-N). 
Lower Order Path Connection (LPC) 
Roteia os VC-12, VC-3, alocando de modo flexível (caso o equipamento SDH tenha 
esta funcionalidade) no VC-4. É um bloco opcional em MUX Add & Drop. Se não, os 
VC-12 e VC-3, possuem alocação fixa no VC-4 (CPqd BRASIL, 1997). A Fig.1.17 
ilustra o símbolo padrão deste bloco. 
 
Fig. 1.17 – LPC. 
 
Provê a alocação flexível de VC-12 ou VC-3 na sua entrada, liberando VCs de ordem 
superior (VC-4), na sua saída. 
 
 
 Algoritmos de Otimização para Redes de Telecomunicações 32
Higher Order Path Connection (HPC) 
Roteia os VC-4, alocando de modo flexível (caso o equipamento SDH tenha esta 
funcionalidade) no frame STM-N. É um bloco opcional em MUX Add & Drop (CPqd 
BRASIL, 1997). A Fig.1.18 ilustra o símbolo padrão deste bloco. 
 
Fig. 1.18 – HPC. 
 
A função HPC provê a alocação flexível do sinal de entrada proveniente de VCs de 
ordem superior (VC-4), obtendo na sua saída, um sinal STM-N (N=1,4,16). 
Higher Order Assembler (HOA) 
Realiza a montagem e desmontagem de VC-4 a partir da combinação de VC-3 e/ou 
VC-12 (CPqd BRASIL, 1997). A Fig.1.19 ilustra o símbolo padrão deste bloco. 
 
Fig. 1.19 – HOA. 
 
A função HOA adapta um VC-M (M=3,12) proveniente da entrada do bloco em um 
VC-M (VC-4), na saída do bloco. O sinal presente na saída do bloco é obtido através do 
processamento do ponteiro da Unidade Tributária (TU) a qual indica a diferença de fase 
entre o POH do VC-M e o POH do VC-4. 
Synchronous Digital Cross-Connect (SDXC) 
O SDXC permite a interligação de anéis e executam funções de conexõescruzadas de 
rotas digitais (CPqd BRASIL, 1997). 
Fig. 1.19a – Exemplo de um Cross-Connect. 
 
 Algoritmos de Otimização para Redes de Telecomunicações 33
Na Fig.1.19a, vê-se que os dados digitais trafegantes bidirecionalmente são 
desmontados ou remontados no SDXC e que para haver compatibilidade de taxas de 
dados diferentes (STM-N) são utilizados para ambas as operações Virtuais Contêineres 
de Ordem Superior (VC-4). 
É um equipamento capaz de interfacear, via portas de sinal digital, um ou mais sinais 
com taxas definidas nas recomendações ITU-T G-702 ou G-707, e permite roteamento 
de qualquer valor e taxa e/ou subtaxa com qualquer outro valor de taxa ou subtaxa de 
sinal. O SDXC é um roteador da tecnologia SDH. Os roteamentos são realizados em 
nível de VCs (Fig.1.19). As interfaces de um SDXC podem ser da PDH ou da SDH ou, 
de ambas. 
Para que um anel óptico apresente a funcionalidade de permitir o roteamento do tráfego 
por novas rotas em caso de falha(s), torna-se imprescindível à utilização no multiplex de 
funções LPC, HPC e roteadores síncronos (SDXC). Sem eles, as informações serão 
perdidas no nó anterior à falha na fibra, pois não será possível o MUX comutar os dados 
para fibras secundárias (backup) ou formar novas configurações de rotas nas fibras 
ópticas. 
 
Interconexões entre redes 
Nos quatro exemplos a seguir, são propostas possíveis formas de interconexão dos 
blocos funcionais. 
• 1° exemplo: sem a utilização do bloco HPC. 
 Fig. 1.20 – Sem a utilização do bloco HPC. 
 
Princípio de funcionamento: 
Neste exemplo, tem-se o interfaceamento de sinais PDH (2, 34, 140 Mbits/s) através de 
blocos funcionais, para a tecnologia SDH (STM-1, STM-4, STM-16). 
O interfaceamento dá-se de duas maneiras: 
1. Para sinais tributários de 2, 34 Mbits/s é necessário a utilização dos blocos 
funcionais LOI, LPC (caso se necessite sinais de VC-3 e/ou VC-12 
combinados deve-se utilizar este bloco; caso contrário, ligar diretamente a 
saída de LOI com a entrada de HOA) e HOA de forma a ter-se na saída de 
HOA, um VC-4 para que o bloco TTF possa converter VC-4 em STM-N; 
 Algoritmos de Otimização para Redes de Telecomunicações 34
2. Para sinais tributários de 140 Mbits/s, recorre-se ao bloco funcional HOI, que 
na sua saída, produz um VC-4 e, dessa forma, pode ser ligado diretamente ao 
bloco TTF, sem a necessidade de passar por LPC e HOA. 
 
• 2° exemplo: sem a utilização do bloco LPC 
Fig. 1.21 – Sem a utilização do bloco LPC. 
 
Princípio de funcionamento: 
Neste exemplo, tem-se o interfaceamento de sinais PDH (2, 34, 140 Mbits/s), através de 
blocos funcionais, para a tecnologia SDH (STM-1, STM-4, STM-16). 
O interfaceamento se processa da seguinte forma: 
1. O bloco HPC recebe VC-4 vindo dos blocos LOI e HOI; 
2. Consultando a tabela de roteamento nele presente (HPC), ele agrega ao VC-4 
presente na sua saída, um nó de destino. 
 
• 3° exemplo: sem a utilização dos blocos HPC e LPC 
Fig. 1.22 – Sem a utilização dos blocos HPC e LPC. 
 
Princípio de funcionamento: 
Neste exemplo, tem-se o interfaceamento de sinais PDH (2, 34, 140 Mbits/s) através de 
blocos funcionais, para a tecnologia SDH (STM-1, STM-4, STM-16). O princípio de 
funcionamento é o mesmo do exemplo apresentado na Fig.1.20 exceto que, com a 
ausência do bloco funcional LPC, não é permitida a combinação de VC-3 e VC-12 e, 
desta forma, na entrada do bloco funcional LOI, necessita-se ter sinais tributários de 2 
ou 34 Mbits/s (um excluindo o outro, nunca, ambos ao mesmo tempo). 
 Algoritmos de Otimização para Redes de Telecomunicações 35
• 4° exemplo: com a utilização de bloco HPC, LPC e Multiplexador Add & Drop 
(ADM). Permite acessar os agregados STM-N derivando e inserindo virtuais 
contêineres e tributários. 
 
 
Fig. 1.23 – Exemplo de acesso de tributários de 44.736 Mbits/s a partir de um agregado 
STM-4. 
 
Observa-se que o bloco HPC permite derivar, inserir e repassar os VC-4 necessários ao 
acesso de informações. Já o bloco LPC permite que VC-3 sejam reinseridos nos 
agregados STM-4 e/ou que VC-3 termine localmente. 
Conclusão do capítulo 
Neste capítulo abordou-se os tópicos relevantes a respeito de Redes de Hierarquia 
Digital (SDH, PDH) e anéis ópticos. Conforme se verificou, as Redes PDH são 
impróprias para o transporte de grande volume de dados digitais, pois têm largura de 
faixa limitada devido aos elevados números de equipamentos multiplexadores / 
demultiplexadores / elementos ópticos (ELOs). A SDH por sua vez é capaz de 
encapsular os dados de diferentes tecnologias e transportá-los em n módulos de 
transportes(n∗STM-N). Além disso, mantém compatibilidade de tráfego nos meios 
ópticos (configurações genéricas de fibras ópticas – BLSR, BSSR, dentre outras), 
elétricos (cabos coaxiais, padrões IEEE) e rádios digitais (microondas, satélites). A 
flexibilidade de retirar e inserir sinais tem motivado as operadoras de telefonia a adotar 
esta tecnologia em MANs. 
Finalmente, deve ser ressaltado que os itens descritos neste capítulo foram 
implementados em nível de software no módulo referente ao roteamento. 
 Algoritmos de Otimização para Redes de Telecomunicações 36
II Roteamento de uma Rede de 
Transporte 
 
Introdução 
O planejamento de uma rede de transporte de longa distância deve envolver as seguintes 
considerações básicas: tráfego que entra e sai dos nós; chaveamento e sinalização 
associados; plano de transmissão; tipo de tráfego; critérios de atendimento; 
sobrevivenciabilidade; previsão de crescimento; qualidade dos serviços prestados. 
Os critérios apresentados devem interagir na busca de: a) economia e eficiência com os 
serviços prestados; b) utilização dos equipamentos de forma otimizada e c) satisfação 
dos clientes, com serviços de qualidade. 
A seguir serão discutidos temas importantes para o entendimento da formulação do 
problema a ser apresentado no próximo capítulo. São eles: roteamento e tráfego de uma 
rede de transporte; representação de redes. 
II.1 Roteamento e tráfego em uma rede de transporte 
O objetivo a ser alcançado com o roteamento é o estabelecimento de conexão entre dois 
nós distintos, digamos i e j, de uma dada rede (KERSHENBAUM, 1997). Em um 
circuito, a sua função é fornecer qual o melhor caminho para escoar ou receber um dado 
pacote de informação, tendo como origem e destino, respectivamente, as estações i e j. 
Esta escolha deve ser feita por intermédio de programas analisadores de tráfego. Na 
literatura especializada, são descritos diversos algoritmos para o tratamento desse 
problema, entre os quais podemos citar Dijkstra, Bellman, Floyd. Destes, somente o 
método de Dijkstra será apresentado no próximo capítulo por ser ele bastante 
empregado na solução de tal problema. 
Como mencionado anteriormente, o algoritmo de roteamento tem como 
responsabilidade determinar a melhor trajetória para se enviar os dados. A escolha do 
algoritmo deverá levar em consideração alguns fatores relacionados ao envio da 
informação de acordo com o tipo da rota, como: 
¾ Utilização de datagramas – topologia em anel (neste caso a trajetória dos 
pacotes será feita dinamicamente para cada nó); 
¾ Utilização de circuitos virtuais – rotas ponto-ponto (neste caso o roteamento 
será empreendido quando novos circuitos forem montados). 
Circuitos virtuais são utilizados em redes baseadas na tecnologia PDH. 
 Algoritmos de Otimização para Redes de Telecomunicações 37
Os algoritmos de roteamento podem ser agrupadosem duas classes quanto ao critério de 
adaptabilidade: 
1. Algoritmos adaptativos – as decisões de roteamento mudam devido às 
variações de tráfego com o tempo; as rotas são escolhidas a partir de 
amostragens de cargas em todos os nós; 
2. Algoritmos não-adaptativos ou de roteamento estático – não é feita nenhuma 
amostragem atual do tráfego entre nós. A montagem da tabela de roteamento 
das informações é feita a partir de um histórico de tráfego médio nos arcos. 
 
Neste trabalho de dissertação foi escolhido o Algoritmo não-adaptativo, pois a partir de 
levantamentos junto às concessionárias de telefonia verificou-se que a montagem da 
tabela de roteamento é feita fundamentada em histórico de tráfego médio nos arcos (os 
critérios de montagem do histórico são sigilosos). 
É desejável que os algoritmos sejam simples, robustos, eficientes e estáveis. A seguir 
passa-se à discussão de dois itens importantes para se entender o problema de 
roteamento: 1) topologias de redes, onde se faz uma breve discussão e 2) análise de 
diferentes tipos de roteamento normalmente encontrados e largamente utilizados em 
redes de comunicações. 
 
II.1.1 Topologia de uma rede 
Uma rede é composta de um número de nós interconectados por equipamentos de 
transmissão (multiplexadores, demultiplexadores, equipamentos de ligações ópticas, 
fibras ópticas), os quais podem formar topologias em anel, estrela ou malha. Diversos 
equipamentos de redes podem ligar-se a esses nós e o sentido das informações nestes, 
podem ser unidirecional ou bidirecional. A Fig.2.1 ilustra o caso de uma rede hipotética 
com circuito bidirecional. 
 
Fig. 2.1 – Exemplo de uma topologia de rede. 
 Algoritmos de Otimização para Redes de Telecomunicações 38
II.1.2 Distribuição de informações 
As informações numa rede podem ser distribuídas segundo um plano de roteamento que 
teria como objetivo definir a melhor rota presente entre um par de nós. Os planos de 
roteamento podem ser fixos ou dinâmicos. Nos planos fixos, o conjunto de rotas que 
serão utilizadas segue uma distribuição preestabelecida e, nos dinâmicos, esse conjunto 
de rotas segue a demanda. 
A atualização das rotas de distribuição pode ser feita pelo exame periódico ou 
aperiódico das demandas dos arcos, dependente do estado da rede, do aumento e 
distribuição das chamadas e de falhas em um determinado percurso. 
Os principais tipos de roteamentos segundo essas diversas possibilidades de distribuição 
da informação são discutidos a seguir. 
II.1.2.1 Roteamento dependente do tempo 
A distribuição das rotas de informações é alterada em determinados períodos fixos 
durante o dia e/ou semana, a partir de um histórico de tráfego (KERSHENBAUM, 
1997). Neste tipo de técnica tem-se a vantagem de fazer-se um levantamento da 
capacidade inativa dos circuitos; não é adequada à Hierarquia Digital Síncrona, pois, 
nesta tecnologia de transporte o tráfego é fundamentado em um histórico de tráfego 
médio. A Fig.2.2 ilustra este tipo de roteamento. 
 
 
 
Intervalo de 
tempo (s) 
Possíveis rotas alternativas 
1 A-C-D-E-H-B 
2 A-C-D-B 
3 A-E-B 
4 A-E-H-B 
5 A-F-G-H-B 
Fig. 2.2 – Exemplo de roteamento dependente do tempo. 
 Algoritmos de Otimização para Redes de Telecomunicações 39
II.1.2.2 Roteamento dependente do estado 
Conhecido também como esquema adaptativo de roteamento. A escolha das rotas para o 
despacho de informações é feita de modo automático de acordo com o estado da rede, 
definido com o auxílio de dois parâmetros: 
¾ Taxa de ocupação do nó de onde partiu a informação; 
¾ Informação sobre o sucesso no atendimento das chamadas. 
Estes parâmetros são obtidos através da análise de dados coletados da rede 
(GREFENSTETTE, 1986). 
Com as informações acima, são tomadas decisões de distribuição da informação pelo 
programa gerenciador de tráfego. Este deve incorporar princípios fundamentais de 
controle de redes como: a) evitar a ocupação total de grupos de circuitos; b) não 
sobrecarregar o trânsito das rotas com mudanças sucessivas de caminhos das cargas e 
c) em circunstâncias de sobrecarga, restringir as conexões de roteamento direto. 
II.1.2.3 Roteamento dependente do evento 
A distribuição de rotas é atualizada localmente no roteador presente em cada estação, o 
qual leva em consideração para o envio de dados adiante, a ocorrência de chamadas 
sucessivas ou situações de falhas num dado percurso. Constitui-se dos seguintes passos: 
1. Inicializar o processo obtendo o número total de estações e a conectividade entre 
todas as estações; 
2. Selecionar aleatoriamente o primeiro trajeto, o qual será responsável no roteador 
pelas chamadas sucessivas de novas rotas; 
3. Verificar a obtenção de sucesso na trajetória escolhida. Caso afirmativo, a 
alteração é retida. Senão, selecionar aleatoriamente novos trajetos; 
4. Repetir o passo 2 até se atingir o número total de estações. 
 
Na Fig.2.3 exemplifica-se este tipo de roteamento, onde se verifica cinco tomadas de 
decisão: a primeira corresponde ao trajeto A-E-B; a segunda corresponde ao trajeto 
A-E-B; a terceira corresponde ao trajeto A-C-D-B; a quarta corresponde ao trajeto 
A-C-D-B e a quinta corresponde ao trajeto A-F-G-H-B. 
 Algoritmos de Otimização para Redes de Telecomunicações 40
 
 
Intervalo de 
tempo (S) 
Rota (inicial) Rota utilizada (final) 
1 A-E-B A-E-B 
2 A-C-D-E-H-B A-E-B 
3 A-C-D-B A-C-D-B 
4 A-E-H-B A-C-D-B 
5 A-F-G-H-B A-F-G-H-B 
Fig. 2.3 – Exemplo de roteamento dependente do evento. 
II.1.2.4 Roteamento automático alternativo (irreversível) 
É denominado também de distribuição progressiva irreversível (KERSHENBAUM, 
1997). Deve ser empregado quando todos os circuitos por onde as informações 
deveriam trafegar estiverem ocupados. Muitos grupos de circuitos podem ser testados 
seqüencialmente. A ordem de teste pode ser fixa ou variável com o tempo. Este tipo de 
roteamento não é conveniente para rede SDH, pois, causaria congestionamento nos 
enlaces. 
II.1.2.5 Re-roteamento automático 
O módulo roteador processa as informações de maneira a distribuí-las progressivamente 
por um determinado percurso; a dinâmica dessa distribuição é a seguinte: inicialmente é 
lançado um pulso pelo roteador como uma forma de verificar se há uma falha na 
trajetória escolhida pelo envio de dados. Duas situações podem ocorrer: 
1. O pulso não retorna do nó destino para o nó de origem, no prazo de escuta 
estabelecido pelo roteador da estação origem; este interpreta como uma falha 
na fibra óptica e então escolhe um novo nó para reenviar o pulso; 
2. O pulso lançado pelo roteador retorna do nó destino para o nó origem; o 
roteador presente no nó origem interpretando este procedimento como 
desobstrução da fibra óptica envia um bloco de dados para o nó destino. 
 
Observe que este procedimento padrão se repete nos nós subsequentes e continua, até 
que o módulo roteador se certifique que o bloco de dados em tela tenha sido entregue ao 
nó destino. A Fig.2.4 ilustra este tipo de roteamento. 
 Algoritmos de Otimização para Redes de Telecomunicações 41
 
 
Rota 
(inicial) 
Re-roteamento 
 (final) 
A-F-G-H-B A-F-G-H-B 
A-C-D-B A-C-D-E-B 
Fig. 2.4 – Exemplo de re-roteamento automático. 
 
 
II.2 Representação de redes 
O desempenho de algoritmos de roteamento não depende somente deles próprios, mas 
também da maneira pela qual a rede é representada (KERSHENBAUM, 1997). 
Utilizando estruturas de dados de maneira inteligente, pode-se diminuir 
consideravelmente o tempo de processamento associado à resolução de um dado 
problema. 
Para a representação de uma