Gerenciamento de Roteamento BGP em Pontos de Troca de Tráfego - PDF
Download "Gerenciamento de Roteamento BGP em Pontos de Troca de Tráfego"
Leandro Brás Neiva
1 PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO GRANDE DO SUL FACULDADE DE INFORMÁTICA CURSO DE BACHARELADO EM CIÊNCIA DA COMPUTAÇÃO Gerenciamento de Roteamento BGP em Pontos de Troca de Tráfego por ANDREY VEDANA ANDREOLI FABIO FALCI RODRIGUES Relatório de Trabalho de Conclusão II Prof. MSc. Ana Cristina Benso da Silva Orientadora Porto Alegre, dezembro de 2002
2 ii SUMÁRIO Sumário... ii Lista de Abreviaturas...vi Lista de Figuras... viii Lista de Tabelas...xi Agradecimentos... xii Resumo...xiv Abstract...xv 1. Introdução Objetivos gerais e específicos Contribuições Organização do texto Roteamento Algoritmos de roteamento Protocolos IGP Protocolos EGP BGP (Border Gateway Protocol) Introdução Modelo de divulgação e atualização das tabelas de rotas Estados de uma conexão BGP Funcionamento do algoritmo de decisão Utilização de políticas Mensagens do protocolo Mensagem tipo OPEN Mensagem tipo NOTIFICATION Mensagem tipo KEEPALIVE Mensagem tipo UPDATE CIDR Utilização de BGP em sistemas autônomos O Futuro do BGP Organização da Internet em PTT s Conceitos Gerais Arquiteturas de PTTs Ferramentas Utilizadas...47
3 iii Software Zebra Software Gated Traceroute e Ping PTTs no Brasil e a RNP PTT RSIX (RS Internet Exchange) Gerência de Redes Structure of Management Information Abstract Syntax Notation One Tipos de Dados Abstratos Módulos Macros Basic Encondig Rules Management Information Base MIB BGP SNMPv Segurança Protocolo GetRequest GetNextRequest SetRequest Trap Message/Pdu SNMPv Protocolo GetBulkRequest InformRequest Report Messages/PDU SNMPv Segurança Arquitetura da Entidade SNMPv RMON Considerações Sistema de Gerenciamento do Protocolo BGP em PTTs Arquitetura do sistema Informações para Gerenciamento MIB II MIB RMON II MIB BGP MIBs resultantes do trabalho MIB BGPe...78
4 iv MIB BGPe Traps MIB BGPe Conf MIB BGPe RSUtil Modelagem de Entidades SNMP Implementação do sistema Classe Transport Classe Dispatcher Classe Pendente Classe CommandGenerator Classe CommandResponder Classes V1Methods/V2Methods/V3Methods Classe MIB Estrutura da MIB Implementação de MIBs Classe MIB Compiler Classes Message/Pdu Entidade Agente Entidade Dual Simulação do sistema Arquiteturas de validação do sistema Softwares utilizados no protótipo Ativação do protótipo e sistema de gerência Utilização da MIB BGPe Conf Utilização da MIB BGPe Utilização da MIB BGP Traps Simulação de problemas em PTTs Queda da sessão BGP de algum participante Número de anúncios fora do intervalo esperado Número de anúncios e histórico de anúncios de participantes Quantificação da profundidade de anúncios Anúncio de redes inválidas Propagação de anúncios de outros sistemas autônomos Saturação de link de participante do PTT Conclusões Referências Bibliográficas Anexo A Anexo B Anexo C Anexo D Anexo E...133
5 v Anexo F Anexo G Anexo H...147
6 vi LISTA DE ABREVIATURAS AS ASN.1 BER BGP CCITT CMOT CMIP DES DOD DVMRP EGP EIGRP HEMS HMAC HMP IAB ICMP IETF IGP IGRP INOC IP ISO IX MD5 MIB MSDP NAP NRLI NSFNET OID OSI OSPF PDU PIM POP PTT RIP RMON SGMP SHA SMI SMP SMTP Autonomous System Abstract Syntax Notation One Basic Encoding Rules Border Gateway Protocol Community Colleges for Innovative Technology Transfer CMIP over TCP/IP Common Management Information Protocol Data Encryption Standard U.S. Department of Defense Distance Vector Multicast Routing Protocol External Gateway Protocol Enhanced Interior Gateway Routing Protocol High-Level Entity Management System Keyed-Hashing Message Authentication Codes Host Monitoring Protocol Internet Architecture Board Internet Control Message Protocol Internet Engineering Task Force Interior Gateway Protocol Interior Gateway Routing Protocol Internet Network Operations Center Internet Protocol International Organization for Standardization Internet Exchange Message Digest Management Information Base Multicast Source Discovery Protocol Network Access Point Network Layer Reachability Information National Science Foundation Network Object Identifier Open Systems Interconnection Open Shortest Path First Protocol Data Unit Protocol Independent Multicast Ponto de Presença na rede Ponto de Troca de Tráfego Routing Information Base Remote Monitoring Simple Gateway Monitoring Protocol Secure Hash Algorithm Structure of Management Information Simple Management Protocol Simple Mail Transfer Protocol
7 vii SNMP SPF TCP UDP VLSM Simple Network Protocol Shortest Path First Transmission Control Protocol User Datagram Protocol Variable Length Subnet Masks
8 viii LISTA DE FIGURAS Figura Exemplos de utilização de protocolos IGP e EGP em sistemas autônomos...20 Figura Decisão de melhor caminho segundo RIP...22 Figura Máquina de estados finito para sessões do protocolo BGP...26 Figura Exemplo ilustrativo de situação de trânsito BGP com clientes multihomed Figura 2-5 Formato header genérico do BGP...31 Figura 2-6 Mensagem OPEN...32 Figura 2-7 Mensagem NOTIFICATION...33 Figura Mensagem UPDATE...34 Figura Formato do campo PathAttribute...35 Figura Tabela BGP e atributos...38 Figura CIDR...39 Figura Exemplo de utilização de ibgp e ebgp...40 Figura Situação das Conexões entre Brasil, Uruguai e Argentina...41 Figura Exemplo de PTT baseado em acordos bilaterais...43 Figura Exemplo de acordos bilaterais em PTT...43 Figura Ilustração de PTT baseado em acordos multilaterais Figura Exemplo de PTT baseado em Route Server Figura PTT baseado em Route Servers, utilizando Looking Glass...46 Figura 3-7 Configuração BGP no Zebra...48 Figura 3-8 Configuração BGP no Gated...49 Figura Traceroute...50 Figura Conexões entre os backbones da RNP e os PTTs nacionais existentes Figura 4-1 Arquitetura de Gerência...52 Figura 4-2 TLV (Type Length Value)...55 Figura 4-3- BER...56 Figura Codificação de OID...57 Figura 4-5 Árvore da MIB...57 Figura MIB-II...58 Figura MIB BGP...59 Figura 4-8 Operação GetRequest...61 Figura 4-9 Operação GetNextRequest...61 Figura Operação SetRequest...62 Figura Operação Trap...63 Figura Message e PDU SNMPv Figura Message e PDU SNMPv Figura Evolução SNMP...66 Figura Entidade SNMPv Figura SNMPv3 Messages...69 Figura RMON...70 Figura 5-1 Arquitetura do Sistema...73 Figura 5-2 Exemplo de aplicação do conceito de VLAN...75
9 ix Figura 5-3 Exemplo de consulta aos índices das interfaces do Switch...76 Figura 5-4 Exemplo de Get...76 Figura Topologia criada para teste da MIB BGP...77 Figura Saída do snmpwalk...78 Figura MIB BGPe...79 Figura MIB BGPeTrap...82 Figura Ilustração da MIB de configuração do sistema...85 Figura Arquivo da BgpeConf...87 Figura BGPeRSUtil...88 Figura 5-12 Comunicação entre os módulos de um Agente SNMP...89 Figura 5-13 Comunicação entre os módulos de um Gerente SNMP...90 Figura 5-14 Classe Transport...91 Figura 5-15 Classe Dispatcher...92 Figura 5-16 Filas da classe Pendente...93 Figura 5-17 Classe CommandResponder...94 Figura 5-18 Métodos da classe VXMethods...95 Figura 5-19 Métodos da classe V2Methods...95 Figura MIB Exemplo...96 Figura 5-21 Classes empregadas na implementação de grupos (exemplo Bgpe)...97 Figura 5-22 Métodos da Interface Variáveis...97 Figura 5-23 Exemplos de classes tipo Nodo Folha...98 Figura 5-24 MibListener...98 Figura 5-25 Exemplo de classe de MIB (Exemplo da Bgpe.Java) Figura 5-26 Estrutura das classes Message e Pdu Figura Ilustração do protótipo de PTT no laboratório de redes Figura Arquitetura do protótipo final para validação Figura 5-29 Exemplo de Set no objeto BgpeConfMaxPath da MIB BgpeConf Figura 5-30 Exemplo de SnmpGet no objeto BgpeTotalPath da MIB Bgpe Figura 5-31 Trap de sessão BGP down do participante 2, recebida pelo software JopenEyes Figura 5-32 Trap de sessão BGP up do participante 2, recebida pelo software JopenEyes Figura 5-33 Corpo do que sinaliza a normalização da sessão BGP do participante Figura Exemplo de trap enviada quando o número de anúncios ultrapassa o esperado Figura Gráfico que ilustra o número total de anúncios de cada participante Figura Gráfico que ilustra o total de anúncios global no PTT Figura Classificação de anúncios por tamanho de um dos participantes do PTT Figura A-1 - Configuração do participante Figura A-2 - Configuração do Route Server Figura A-3 - Configuração do Looking Glass Figura A-4 - Status das conexões BGP com os Route Servers do participante Figura A-5 - Sessões BGP de Route Server Figura A-6 - Tabela BGP do Route Server Figura A-7 - Tabela BGP do participante 1 (AS 1)...137
10 x Figura A-8 - Tabela BGP do Looking Glass Figura A-9 - Tabela BGP do Route Server 2, sem filtros por AS_PATH Figura A-10 - Configuração do participante Figura A-11 Configuração do RSD Figura A-12 Visão das sessões Figura A-13 Participante Figura A-14 Anúncios recebidos pelo AS Figura A-15 Rotas da tabela do participante Figura A-16 - Diagrama de classes das mensagens SNMP Figura A-17 - Diagrama de classes do MibCompiler Figura A-18 - Diagrama de classes da entidade Agente Figura A-19 - Diagrama de classes da entidade Dual...150
11 xi LISTA DE TABELAS Tabela 2-1 Descrição dos campos do header...31 Tabela 2-2 Descrição dos campos da mensagem OPEN...32 Tabela 2-3 Descrição dos campos da mensagem NOTIFIFCATION...33 Tabela 2-4 Erros da mensagem NOTIFICATION...33 Tabela Descrição do subcampo Atribute flags do campo Path Attribute...35 Tabela Atributos BGP...36 Tabela Relação de alguns atributos, classificação e RFC associada...36 Tabela Descrição dos atributos BGP...37 Tabela 3-1 Portas Zebra...48 Tabela A-1 - Endereçamento de cada participante Tabela A-2 - Definição de rede/bloco CIDR para cada participante Tabela A-3 - Endereçamento dos PCs Tabela A-4 - Definição de rede/bloco CIDR para cada participante Tabela A-5 - Objetos BGPe Tabela A-6 - Objetos BGPeConf Tabela A-7 - Objetos BGPeRSUtil Tabela A-8 - Objetos BGPeTraps...146
12 xii AGRADECIMENTOS Agradeço a todos que contribuíram para o bom andamento deste Trabalho de Conclusão. Em especial para os meus Pais Ronaldo e Márcia que tornaram tudo isso possível. Para os meus irmãos e familiares que sempre me apoiaram. Para a nossa orientadora a professora Ana Benso que conseguiu nos guiar de forma brilhante para a conclusão do trabalho. Para o professor avaliador Avelino Zorzo que avaliou de forma séria e correta o trabalho. Para todos os professores da Faculdade de Informática que contribuíram para a minha formação e para todos os meus amigos e colegas do curso de Ciências da Computação. Em especial ao amigo Andrey com quem tive o privilégio de fazer este belo trabalho. Um sincero abraço. Fabio Ao final de uma caminhada, nada melhor do que compartilhar com aqueles que nos acompanharam lealmente em todos as horas, inclusive nas horas difíceis. Olho para meu ser e vejo uma Mãe e um Pai maravilhosos, abrindo mão de conviver com o único filho para ele poder estudar e sentir o vento da vida bater no rosto. Em todos os momentos, principalmente nos difíceis, vocês sempre estiveram ao meu lado. Em tudo o que lembro de maravilhoso em minha vida, vocês sempre estiveram comigo. E como era bom chegar em casa depois de uma semana de estudos e dar aquele abraço em vocês, matar a saudade, conversar, dividir alegrias e sentir tanto amor. O orgulho de vocês foi aumentando cada vez mais, até o momento que me senti tão fraco, diante da situação de não conseguir fazer vocês ficarem mais tempo nesse Mundo. Senti-me frustrado por procurar vocês no meio de tanta gente e não encontrá-los. Pobre, por não poder abraçar as pessoas mais importantes de minha vida. Em seguida, de lá de cima, comecei a sentir a força que vocês sempre me deram de forma muito mais intensa e ao mesmo tempo em que as lágrimas caiam, aumentar a vontade de tornar os sonhos de vocês realidade. Sinto vocês no meu lado, me envolvendo com tanto amor que me fez voltar a sentir de leve o sabor das coisas boas. Essa conquista, dedico inteiramente a vocês, pois vocês têm sido muito mais do que pais. Por maiores que sejam as vitórias e conquistas do futuro, ser filho de vocês sempre será minha maior conquista. A você Alice, minha namorada, meu profundo agradecimento por toda a compreensão, apoio e amor que tens me dado. A orientadora Prof. Ana Benso meu mais sincero agradecimento pela pessoa maravilhosa que tens sido, pelo apoio nas horas difíceis e pela grande amiga para conversar e me ajudar. Aos demais professores e funcionários, meu muito obrigado por cada lição e cada minuto de convivência.
13 xiii Ao pessoal do CPD da UFRGS, em especial à Prof. Liane Tarouco e ao Leandro Bertholdo, minha gratidão por terem me dado a chance de trabalhar com vocês. Fabrício, Rodrigo, Leandro Rey, meu muito obrigado. Ao colega Fábio Falci Rodrigues, um abraço e o meu sincero muito obrigado, pelas noites fazendo este trabalho, pelos finais de semana discutindo o trabalho e pela sua tão valiosa contribuição no TC e na nossa amizade. A vocês colegas e grandes amigos, obrigado pela força, pelo companheirismo, pelos estudos, pela lealdade, pela convivência e pelos desafios que superamos juntos. A Deus, obrigado pela força, pelas tantas coisas boas que tive em minha vida, pelos amigos, pela saúde e pelos pais eternos que tenho. Sem todos vocês, essa conquista não teria o mínimo valor. Forte abraço, Andrey
14 xiv RESUMO Este trabalho apresenta um estudo de gerenciamento do protocolo de roteamento BGP (Border Gateway Protocol), pois seu correto funcionamento é vital para o sucesso do roteamento do tráfego entre sistemas de redes de computadores de diferentes domínios administrativos. A interconexão de grandes redes e backbones da Internet são chamadas de NAP s (Network Access Points) ou PTTs (Pontos de Troca de Tráfego). Assim sendo, essa proposta utiliza a arquitetura de um PTT para analisar o tráfego BGP, identificar os requisitos de gerenciamento do protocolo e elaborar um conjunto de informações úteis ao seu gerenciamento. Os resultados do trabalho foram a especificação de uma MIB (Management Information Base) experimental para o BGP, baseada em MIBs já existentes e a implementação de agentes SNMP para execução das tarefas de gerenciamento necessárias. Palavras-chave: Protocolos de roteamento, BGP, gerência de redes, PTTs, NAPs.
15 xv ABSTRACT This work describes a management system of BGP (Border Gateway Protocol), because its corrects functioning is very important to traffic routing success between networks of different Autonomous Systems. The interconnection of large Internet networks and backbones is called NAPs (Network Access Point). Therefore, this work uses a PTT architecture to analyses BGP traffic, identify the requirements for protocol management, and collect of information for its management. The results of this work are a specification of an experimental MIB (Management Information Base) based on existing MIBs, and the implementation of SNMP agent to execute the management tasks. Keywords: Routing protocols, BGP, management of networks, PTTs, NAPs.
17 17 1. INTRODUÇÃO Os elementos de interconexão de redes são essenciais para o funcionamento da Internet, em especial os roteadores. Eles estão ligados entre si de forma que uma mensagem possa chegar ao seu destino rapidamente e com eficácia. Logo, o processo de configuração do roteamento deve ser robusto e eficaz. Os roteadores devem ser configurados para que reconheçam o caminho que os pacotes deverão seguir para atingir o seu destino. Essa configuração pode ser realizada através de protocolos de roteamento. Existem vários protocolos de roteamento, os quais são empregados com escopos diferenciados. O BGP (Border Gateway Protocol) é um dos protocolos utilizados para a configuração de roteadores que interligam redes de domínios administrativos diferenciados. Em cada roteador que suporta BGP, tem-se uma tabela de rotas. Cada linha dessa tabela indica para quem este roteador deve enviar cada pacote para alcançar tal destino. Ele consegue esta informação trocando mensagens com os seus roteadores vizinhos e gravando na tabela de roteamento os anúncios que recebe. Isso é feito até se chegar num ponto de convergência, ou seja, quando os roteadores tiverem a mesma tabela de rotas. No começo, estas tabelas eram relativamente pequenas, mas com o crescimento da Internet as tabelas começaram a se tornar grandes e complexas. Outro ponto que interfere diretamente nas tabelas de rotas é a topologia das redes. Isso torna a construção da tabela de rotas uma tarefa difícil e contínua, pois podem existir várias rotas para chegar a um determinado destino e o BGP terá que decidir qual será a melhor rota. Para ter controle sobre toda a rede, é necessário o uso efetivo do gerenciamento. Com a complexidade e a probabilidade de falhas crescendo cada vez mais, a atividade de gerência torna-se essencial para o funcionamento da rede. Se por exemplo, uma rota, calculada de forma errada, for propagada para os roteadores, muitos pacotes importantes podem se perder causando prejuízos a todos. Logo, a atividade de gerenciamento tem condições de perceber que algo de errado está acontecendo e enviar um aviso para o responsável, reportando a situação. Então esse responsável poderá, apoiando-se nas informações de gerência, identificar, corrigir e executar ações preventivas em relação às falhas que poderiam ocorrer. Tais informações, que são utilizadas para armazenar e representar informações relevantes sobre o gerenciamento são denominados MIBs (Management Information Base). 1.1 Objetivos gerais e específicos Assim sendo, o objetivo principal deste trabalho foi desenvolver um sistema de gerenciamento do protocolo BGP, para utilização em locais de redes de computadores de domínios administrativos diferentes. O objetivo deste sistema foi identificar possíveis falhas e situações anômalas a respeito das operações do protocolo BGP, mantendo a equipe de suporte informada sobre esses eventos. O trabalho envolveu o estudo de arquiteturas e protocolos de gerenciamento de redes de computadores, do protocolo de roteamento BGP e de arquiteturas de PTTs (Pontos de Troca de Tráfego),
18 18 que representam umas das formas de interconexão das redes de diferentes domínios administrativos. 1.2 Contribuições Baseado no contexto apresentado, o presente trabalho busca fornecer as seguintes contribuições: Implementação de um agente para captura de informações que não estão presentes em outras MIBs. Implementação de uma MIB para busca de informações complexas. Implementação de um agente Dual para implementação das MIBs. Implementação de um sistema de monitoração que faça o envio de TRAPs. Implementação de agente SNMP versão 2 na linguagem Java, que possa ser estendido para a versão 3, possibilitando seu uso em outros trabalhos da área. Baseado nisso, buscou-se atender às necessidades para uma administração eficiente do protocolo BGP em PTTs. 1.3 Organização do texto O texto encontra-se dividido em capítulos conforme descrito a seguir: o Capítulo 2 apresenta a evolução da Internet, o protocolo BGP; o Capítulo 3 apresenta os Pontos de Troca de Tráfego; o Capítulo 4 aborda o conceito de gerência de redes, a evolução do protocolo SNMP, bem como as suas MIBs; o Capítulo 5 apresenta a proposta detalhada deste trabalho e o Capítulo 6 apresenta a conclusão seguida pelas referências bibliográficas e anexos.
19 19 2. ROTEAMENTO Segundo [COM98], a ARPANET foi a rede que iniciou o backbone da Internet. Nessa época cada participante administrava suas tabelas de roteamento e suas atualizações eram feitas manualmente. Dessa forma, a topologia da Internet poderia ser descrita como um conjunto de roteadores básicos, conhecidos também por core routers ou também por roteadores de borda. Estes roteadores eram controlados pelo INOC (Internet Network Operations Center). Adicionalmente, existia também um conjunto de roteadores, conhecidos como secundários que eram administrados por grupos isolados e eram conectados aos core routers, fornecendo acesso às redes locais de cada instituição. Em seguida, surgiu a NFSNET que inicialmente estabeleceu um único ponto de conexão com a ARPANET, posteriormente aumentando o número dessas conexões. Isso acabou aumentando a complexidade do roteamento global, sem contar que aos poucos o backbone, formado pelos core routers, passou a não ser mais administrado de forma centralizada. Assim, ficou evidente que a arquitetura de roteamento básica não seria suficiente para uma operação e administração satisfatória da rede como um todo. Dessa forma, notou-se que o esquema da rede constituída pelos roteadores básicos interligados não suportaria a conexão de todas as redes através dos roteadores secundários. Por esse motivo o esquema de divisão por hierarquias foi sendo substituído pelo modelo distribuído que é o modelo utilizado até os dias de hoje. Assim sendo, o roteamento não fica mais centralizado em alguns roteadores, como nos roteadores básicos da NFSNET, mas cada roteador é responsável pelas suas redes e pela comunicação com os demais roteadores da Internet. Para acompanhar tais mudanças, foi criado o conceito de sistema autônomo (Autonomous System, ou simplesmente AS), que faz com que as redes e roteadores que estão sob uma mesma política sejam administradas pela própria entidade que os possui. Assim, o que ocorre internamente a um AS não será conhecido por outros sistemas autônomos, diminuindo a complexidade da Internet global. Para a comunicação com o mundo externo, ou seja, com os demais sistemas autônomos, deve ser utilizado pelo menos um dos roteadores do AS para trocar informações com os demais ASs e garantir a alcançabilidade entre suas redes. Para cada AS é atribuído um AS number, que é uma identificação única que o identifica para os demais sistemas autônomos. Dessa forma, a Internet global deixou de ser vista como um grande grupo de redes locais interligadas, mas agora como um conjunto de Sistemas Autônomos que trocam anúncios de rotas para suas redes entre si. Diante de tais inovações e a distribuição desta nova arquitetura, surgiu a necessidade de protocolos de roteamento capazes de manter a consistência e as informações entre os sistemas autônomos da Internet, incluindo também suas redes internas. Assim surgiram diversos protocolos de roteamento com o intuito de atender a estas necessidades e funcionalidades. Por sua vez, esses protocolos baseiam-se em algoritmos de roteamento. Entre os algoritmos de roteamento mais populares, dois deles são apresentados na seção 2.1.
20 20 seguir: Os protocolos de roteamento dividem-se em dois grupos, explicados a EGP (Exterior Gateway Protocol): Grupo de protocolos utilizados para a comunicação inter AS, ou seja, usado para a comunicação entre roteadores que se encontram em diferentes sistemas autônomos. Os protocolos deste tipo garantem que todos os sistemas autônomos pela Internet mantenham informações consistentes para garantir o funcionamento do roteamento global. Exemplo de protocolo deste grupo seria o BGP. IGP (Interior Gateway Protocol): Grupo de protocolos utilizados na comunicação intra AS, ou seja, usados para comunicação entre roteadores em um mesmo sistema autônomo. Hoje este grupo é representado por vários protocolos, como RIP, OSPF, IGRP, entre outros. Através da Figura 2-1 são apresentados exemplos de utilização dos dois grupos de protocolos. Entre o AS 1 e AS 2 é utilizado o grupo de protocolos EGP, utilizando o grupo IGP para propagação das rotas aos demais roteadores de cada sistema autônomo. Figura Exemplos de utilização de protocolos IGP e EGP em sistemas autônomos O processo de configuração do roteamento interno a um AS pode ser feito de duas formas. A primeira delas é estática, ou seja, é baseada na configuração manual de rotas já que em geral não existe mais que um caminho para chegar a determinada rede ou roteador do AS. A desvantagem desta forma de configuração é que, na ocorrência de alguma mudança na rede ou falha em alguma das conexões, o administrador deve fazer todas as alterações necessárias para restabelecimento da comunicação manualmente. Também se torna óbvio que a confiabilidade e o tempo de resposta a problemas podem não ser satisfatórios. Já a forma dinâmica, baseia-se na utilização de protocolos de roteamento que automatizam tal tarefa, ou seja, que fazem o anúncio de rotas e detecção do melhor caminho de forma automática, sem a intervenção do administrador da rede. Caso a decisão seja de utilizar um protocolo dinâmico em um
21 21 AS, deverá ser utilizado um protocolo tipo IGP para tal tarefa. Já para a configuração externa de um AS deverá obrigatoriamente ser utilizado um protocolo tipo EGP, visto que não existe outra forma de propagação das redes pertencentes a ele. 2.1 Algoritmos de roteamento Os protocolos dinâmicos podem implementar diversos algoritmos de roteamento. Alguns destes algoritmos utilizados são apresentados abaixo: a) Vetor distância: Também definido como algoritmo de Bellman-Ford, este algoritmo trabalha baseado na idéia que cada roteador propaga periodicamente uma tabela com todas as redes conhecidas e a distância para alcançá-las. Geralmente, a distância é calculada pelo número de next hops necessários para alcançar uma determinada rede. O termo HOP caracteriza-se pela passagem entre um roteador e outro. Esse termo poderia ser equivalente a palavra salto. Sendo assim, cada roteador, ao receber os anúncios de todos os demais, calcula o caminho ótimo baseado no menor número de HOPs para chegar a determinada rede. Vale lembrar também, que cada roteador ao receber as informações de outras redes incrementa o número de HOPs e anuncia as rotas divulgadas para os demais roteadores. b) Estado de enlace: Também definido como algoritmo Link State, este algoritmo trabalha baseado na idéia de que cada roteador possui informações sobre as redes que estão conectadas a ele e, periodicamente, testa para determinar se cada enlace está ativo. Com estas informações cada roteador divulga uma lista sobre o status de cada conexão, dizendo se estas estão ativas ou inativas. Baseado nessas informações, quando um roteador recebe um conjunto de mensagens sobre o estado dos enlaces das redes próximas a ele, é aplicado o algoritmo SPF de Dijskstra. Este algoritmo é aplicado baseado nas informações de cada roteador e é feito localmente a cada um destes, para o cálculo das melhores rotas para todos os destinos a partir de uma mesma origem. Em termos de expansão, este algoritmo tem vantagem sobre o Vetor Distância, pois o cálculo do melhor caminho é feito localmente e não depende do cálculo de roteadores intermediários. Outra vantagem é que devido a suas características, este algoritmo converge mais rapidamente devido a utilização de flooding para divulgação do estado de seus enlaces, ou seja, divulga de forma mais eficaz os melhores caminhos para suas redes a todos os roteadores conectados. Baseados nesses algoritmos são implementados os protocolos dinâmicos, apresentando nas seções 2.2 e 2.3 os grupos de protocolos IGP e EGP, respectivamente.
22 Protocolos IGP A partir dos algoritmos apresentados na seção 2.1, foram implementados diversos protocolos de roteamento IGP que são largamente utilizados nos dias de hoje, segundo [MAN97], [CIS97] e [COM98]. Os protocolos interiores (IGP) mais conhecidos são apresentados a seguir: a) RIP: O Routing Information Protocol foi um dos primeiros protocolos IGP e foi muito popularizado pela implementação da ferramenta routed, muito usada em sistemas UNIX 4BSD. Basicamente, este protocolo trata da implementação direta do algoritmo de vetor distância. A métrica utilizada para o cálculo do melhor caminho baseia-se no número de roteadores que um pacote iria percorrer até chegar a seu destino, definido por HOP. Um dos problemas deste algoritmo é que pela aplicação da métrica sobre o número de HOPs o caminho ótimo nem sempre é contemplado. Um exemplo mais claro é mostrado pela Figura 2-2, onde de A para C existem dois caminhos. Um deles é pelo roteador B, tendo custo em 2 HOPs e o outro seria diretamente com custo 1. Mesmo que os links pelo roteador B sejam muito superiores em capacidade, ou ainda, mesmo que o link de 64 Kbps esteja totalmente utilizado, o melhor caminho sempre será pelo link de 64 Kbps já que a única métrica é o número de HOPs. Figura Decisão de melhor caminho segundo RIP O funcionamento do protocolo RIP baseia-se no anúncio de rotas feito a cada 30 segundos independente da alteração ou não de alguma rota. As rotas são removidas depois de 180 segundos se não houverem novos anúncios. Isso gera o problema de convergência, já que uma rota pode levar, no pior caso, até 180 segundos para ser removida de um roteador vizinho. Este problema fica ainda mais grave em redes com um grande número de roteadores. Existe também o problema que o RIP não carrega a informação de máscara das redes anunciadas, impossibilitando a divulgação de subredes. A versão 2 deste protocolo apresenta algumas novidades como a inclusão de divulgação da máscara de rede, permitindo a divulgação de subredes e também a possibilidade de autenticação. b) OSPF: O Open Shortest Path First implementa o algoritmo do estado de enlace e, nos dias de hoje, é o mais popular entre os IGPs. Seu funcionamento é