Roteamento na Internet
Juliane Iten Chaves - Mestrado em Telecomunicações

1. Camada de Rede
2. Algoritmos de Roteamento
    2.1 Roteamento Baseado em Tabelas
    2.2 Roteamento pelo Caminho Mais Curto
    2.3 Flooding
    2.4 Roteamento Baseado no Fluxo
    2.5 Roteamento Vector-Distance
    2.6 Roteamento Link-State
    2.7 Outros Tipos de Roteamento
3 Protocolos de Roteamento
   3.1 IGP - Interior Gateway Protocol
   3.2 Exterior Gateway Protocol
   3.3 Border Gateway Protocol
4 Conclusão
 
 
 

1. Camada de Rede

    A camada de rede está relacionada à transferência de pacotes da origem para o destino. Para chegar ao destino, são necessários vários hops em roteadores intermediários ao longo do percurso. Para atingir seus objetivos, a camada de rede deve conhecer a topologia da sub-rede de comunicações e escolher os caminhos mais apropriados através dela, tendo cuidado de escolher rotas que evitem sobrecarregar algumas linhas de comunicação e roteadores, deixando outras ociosas.
    Portanto, a principal função da camada de rede é rotear pacotes da máquina de origem para a máquina de destino.

Retornar ao índice

2. Algoritmos de Roteamento

    O algoritmo do roteamento é a parte do software da camada de rede responsável pela decisão sobre a linha de saída a ser usada na transmissão do pacote de entrada. Se a sub-rede utilizar datagramas internamente, essa decisão deverá ser tomada mais uma vez para cada pacote de dados recebido, pois a melhor rota pode ter sido alterada desde a última vez. Se a sub-rede utilizar circuitos virtuais internamente, as decisões de roteamento serão tomadas somente quando um novo circuito virtual estiver sendo estabelecido. Daí em diante, os pacotes de dados seguirão a rota previamente estabelecida.

    Os algoritmos de roteamento podem ser agrupados em duas classes principais: adaptativos e não-adaptativos. Os algoritmos não-adaptativos ou estáticos não baseiam suas decisões de roteamento em medidas ou estimativas do tráfego e da topologia atuais. Na verdade, a escolha da rota a ser utilizada é previamente calculada off-line, sendo transferida para os roteadores quando a rede é inicializada.

    Os algoritmos adaptativos ou dinâmicos, em comparação, mudam suas decisões de roteamento para refletir mudanças na topologia e, normalmente, no tráfego também. Os algoritmos adaptativos diferem em termos do local que obtêm suas informações (por exemplo, localmente, de roteadores adjacentes ou de todos os roteadores), quando alteram suas rotas ( por exemplo, a cada espaço de tempo em segundos, quando a carga ou topologia muda), e da unidade métrica utilizada para otimização (por exemplo, distância, número de hops ou tempo de trânsito estimado).
Hoje em dia, em termos de uso, os algoritmos estáticos não são mais usados.

Retornar ao índice

    2.1 Roteamento Baseado em Tabelas

    Este algoritmo do protocolo IP utiliza uma tabela de roteamento que armazena informações sobre como atingir cada sub-rede de rede internet. Sempre que a camada IP, em uma estação ou em um gateway, precisa transmitir um datagrama para uma estação que não está diretamente conectada à mesma sub-rede, ela consulta a tabela de roteamento a fim de determinar o gateway para o qual esse datagrama deve ser enviado.
 
 

Figura 1 - Tabela de Roteamento do Gateway B.





    Tipicamente, a tabela de roteamento do IP contém entradas do tipo (N,G), onde N é um endereço IP (endereço de destino) e G é endereço IP do próximo gateway para atingir N. Essa tabela, portanto, só determina o próximo passo no caminho para um destinatário. Nem a estação emissora nem o gateway conhecem a rota completa até a estação a rota completa até a estação destinatária. Vale ressaltar que as entradas dessa tabela só referenciam gateways que podem ser atingidos diretamente, isto é, todos os gateways listados na tabela de roteamento de uma máquina M estão conectados às sub-redes físicas nas quais a máquina M está conectada. Um exemplo de tabela de roteamento é dado na figura 1.

    A tabela de roteamento do IP pode conter informações sobre todos os destinatários de uma rede internet, já que a maioria das máquinas não teria espaço em memória suficiente para isso. Por esse motivo, são armazenados os endereços das sub-redes. Outra técnica utilizada para minimizar o tamanho das tabelas é a utilização de rotas predefinidas (default) para o qual um datagrama deve ser enviado sempre que não for encontrada na tabela uma entrada específica para o endereço IP destino. A utilização de rotas predefinidas é particularmente útil em redes com um único gateway, já que todas as demais sub-redes da rede interne devem ser atingidas mediante esse gateway.

Retornar ao índice

    2.2 Roteamento pelo Caminho Mais Curto - algoritmo estático

    A idéia é criar um gráfico da sub-rede, com cada nó do gráfico representando um roteador e cada arco indicando uma linha de comunicação (ou também chamado de enlace). Para escolher uma rota entre um determinado par de roteadores, o algoritmo simplesmente encontra o caminho mais curto entre eles no gráfico. Uma forma de medir o comprimento do caminho é em números de hops, entretanto, muitas outras unidades também são possíveis.

    Uma das formas para o cálculo do caminho mais curto entre dois nós de um gráfico é o algoritmo de Dijkstra (1959). No algoritmo, cada nó é rotulado por sua distância até o nó de origem ao longo do menor caminho mais conhecido até então. Inicialmente, nenhum caminho é conhecido; portanto todos os nós são rotulados com infinito. À medida que o algoritmo prossegue e os caminhos são encontrados, os labels podem mudar, refletindo melhores caminhos. Um label pode ser provisório ou permanente. No início, todos são provisórios. Quando se descobre que um label representa o caminho mais curto possível até a origem desse nó, ele se torna permanente e não mais é alterado.

Retornar ao índice

    2.3 Flooding (inundação) - algoritmo estático

    Neste algoritmo, cada pacote de entrada é enviado para toda linha de saída, exceto para aquela em que chegou. O flooding gera vários números de pacotes duplicados, na verdade um número infinito. Uma das medidas para amortecer este processo é ter um contador de hops contido no cabeçalho de cada pacote; o contador é decrementado em cada hop, com o pacote sendo descartado quando o contador atingir o zero. O ideal é que o contador de hops seja inicializado com o comprimento do caminho da origem ao destino. Se não souber o tamanho do caminho, o transmissor poderá inicializar o contador, na pior das hipóteses, com o diâmetro total da sub-rede.

    O flooding não é estudado na maioria dos aplicativos, mas tem sua utilidade. Por exemplo, em aplicações militares, onde muitos roteadores podem ser mandados para o espaço a qualquer momento, a grande robustez do flooding é altamente desejável. Em aplicações de bancos de dados distribuídos, às vezes é necessário atualizar todos os bancos de dados ao mesmo tempo, caso em que o flooding pode ser bastante útil. Um terceiro uso possível do flooding é como uma forma de medida a que outros algoritmos de roteamento podem ser comparados. O flooding sempre escolhe o caminho mais curto, pois todos os caminhos possíveis são selecionados em paralelo. Em conseqüência disso, nenhum outro algoritmo é capaz de produzir um retardo menor.

Retornar ao índice

    2.4 Roteamento Baseado no Fluxo - algoritmo estático

    Os algoritmos a cima, só levam em conta a topologia. Eles não consideram a carga. Este algoritmo é um algoritmo estático que utiliza tanto a topologia quanto a carga para o roteador.

    Em algumas redes, o fluxo de dados médio entre cada par de nós é relativamente estável e previsível. Por exemplo, em uma rede corporativa de uma cadeia de lojas de venda a varejo, cada loja pode enviar pedidos, relatórios de vendas, atualizações de estoques e outros tipos de mensagens bem definidas para sites conhecidos em um modelo predefinido de modo que o volume total do tráfego varie pouco dia a dia. Sob condições em que o tráfego médio de i a j seja antecipadamente conhecido e para uma aproximação razoável, constante no decorrer do tempo, é possível analisar matematicamente os fluxos para otimizar o roteamento.

    A idéia básica por trás da análise é que, para uma determinada linha, se a capacidade e o fluxo médio forem conhecidos, é possível calcular o retardo médio de pacote dessa linha. Com base nos retardos médios de todas linhas, é possível calcular facilmente a média ponderada do fluxo para se obter o retardo de pacote médio de toda a sub-rede. Com isso, o problema de roteamento se reduz a encontrar o algoritmo que produz o retardo médio mínimo na sub-rede.

Retornar ao índice

    2.5 Roteamento Vector-Distance - algoritmo dinâmico

    Inicialmente, cada gateway possui uma tabela contendo uma entrada para cada sub-rede à qual está conectado. A cada sub-rede especificada na tabela está associada a distância entre a mesma e o gateway que mantém a tabela. Esta distância pode ser medida em hops (número de gateways a atravessar para atingir uma sub-rede) ou em retardo (tempo necessário para a sub-rede). Inicialmente, os campos de distância devem valer zero, pois somente as sub-redes as quais o gateway está diretamente conectado são especificadas na tabela. Periodicamente, cada gateway envia uma cópia de sua tabela para todo o gateway que possa atingir diretamente. O gateway que recebe a tabela, a compara com a sua própria e modifica esta última nos seguintes casos:

    Na atualização dos campos de distância da tabela do receptor, deve-se considerar a distância entre os gateways emissor e receptor, (por exemplo, é necessário somar 1 no caso da métrica baseada em hops). Vale lembrar que, para cada sub-rede especificada na tabela, existe associada um campo que indica o próximo gateway na rota para essa sub-rede. A figura abaixo ilustra este tipo de roteamento.

    O algoritmo é simples e de fácil implementação; porém, em ambientes dinâmicos, onde novas conexões surgem e outras são desativadas com freqüência, a informação de atualização propaga-se muito lentamente e, durante esse período de propagação, alguns gateways possuem informações de roteamento inconsistentes. Além disso, as mensagens de atualização tornam-se enormes, pois são diretamente proporcionais ao número total de redes e gateways presentes na rede internet (todos os gateways devem participar, senão o algoritmo não converge).
 
 

Retornar ao índico

    2.6 Roteamento Link-State (Shortest Path First) - algoritmo dinâmico

    Neste algoritmo, cada gateways deve conhecer a topologia completa da rede internet. Isto é feito descrevendo-se os gateways interconectados entre si por enlaces (links). Existe um enlace entre dois gateways se ambos puderem comunicar-se diretamente, ou seja se estiverem a mesma rede física.

    Cada gateway exerce duas funções principais. A primeira é testar continuamente o estado dos enlaces com os gateways vizinhos. A segunda é enviar periodicamente os dados de estado de seus enlaces a todos os outros gateways da rede internet. O teste de estado é realizado através do envio de mensagens curtas que exigem resposta. Se acontecer uma resposta, sob condições que variam segundo a implementação do protocolo, o enlace está ativo, senão está inativo. Os dados de estado indicam, simplesmente, se há possibilidade de comunicação entre dois gateways. Estes dados são em geral enviados em modo difusão (broadcast) individualmente.

    Ao receber uma informação de estado, um gateway atualiza seu mapa da rede internet ativado ou desativado os enlaces em questão e recalcula as rotas para todos os destinos possíveis através do algoritmo Shortest-Path-First (SPF), de Dijskstra, aplicado à topologia da rede internet. A figura abaixo ilustra um exemplo deste tipo de roteamento.

    Em relação ao algoritmo Vector-Distance, o SPF possui diversas vantagens. O cálculo das rotas é realizado localmente, não dependendo de máquinas intermediárias. O tamanho das mensagens não depende do número de gateways diretamente conectados ao gateway emissor. Como as mensagens trafegam inalteradas a detecção de problemas torna-se mais fácil.
 
 
 

        Inicialmente, quando o tamanho da Internet ainda permitia, o algoritmo de roteamento implementado no Sistema Core era do tipo Vector-Distance. Em 1988, por causa dos problemas já citados do algoritmo Vector-Distance, a Internet passou a implementar um algoritmo de roteamento do tipo Link-State em seu Sistema Core.

    Os algoritmos descritos anteriormente assumem, a priori, a existência de uma tabela de roteamento devidamente iniciada. Esta iniciação depende do próprio sistema computacional no qual se situa a camada IP. Várias soluções manuais existem como, por exemplo, a carga de uma tabela pré-configurada com dados limitados ou a carga de uma tabelas vazias que são preenchidas através de comandos. Entretanto, o problema principal é a manutenção dessas tabelas devido à dinâmica das redes. Para resolver esse problema torna-se imprescindível o uso de mecanismos automáticos, previstos nos protocolos de roteamento descritos nos itens seguintes.

Retornar ao índice

    2.7 Outros Tipos de Roteamento

 - Roteamento Hierárquico: À medida que as redes aumentam de tamanho, as tabelas de roteamento do roteador crescem proporcionalmente. Não somente a memória do roteador é consumida por tabelas cada vez maiores, como também é necessário mais tempo de CPU para percorrê-la e mais largura de banda para enviar relatórios de status sobre elas. Em um determinado momento, a rede pode crescer até o ponto em que não mais é viável todos os roteadores terem uma entrada para todos os outros roteadores; portanto, o roteador terá de ser feito hierarquicamente, como na rede telefônica.

- Roteamento para Hosts Móveis: Hoje em dia, milhões de pessoas que têm computadores portáteis, desejam ler sua mensagens de correio eletrônico e acessar seus sistemas de arquivos comuns onde quer que estejam. Esses hosts móveis criam uma nova complicação: antes de rotear um pacote para um host móvel, primeiro a rede precisa localizá-lo. A questão da incorporação de hosts móveis em uma rede é muito recente.

- Roteamento por Difusão: Para algumas aplicações, os hosts precisam enviar mensagens a muitos hosts ou a todos os outros hosts. Por exemplo, um serviço de distribuição de relatórios sobre o tempo, atualizações do mercado de ações ou programas de rádio ao vivo podem funcionar melhor enviando dados para todas as máquinas e permitindo que os interessados leiam essas informações. O envio de um pacote a todos os destinos simultaneamente é chamado de difusão (broadcasting); vários métodos foram propostos para implementar esse recurso.

- Roteamento Multicast: Em algumas aplicações, processos amplamente separados funcionam juntos em grupo; por exemplo, um grupo de processos que implementam um sistema de banco de dados distribuídos. Com freqüência, é necessário que um processo envie uma mensagem a todos os outros membros do grupo. Se o grupo for pequeno, será necessário enviar apenas uma mensagem ponto a ponto entre cada membro. Se o grupo for grande, essa estratégia se tornará cara. Às vezes, a difusão pode ser utilizada; no entanto, o uso de difusão para informar 1000 máquinas de uma rede de um milhão de nós é ineficiente, pois a maioria dos receptores não estará interessada na mensagem. Portanto, precisasse de uma forma de enviar mensagens a grupos bem definidos que sejam grandes quando considerados individualmente, mas pequenos se comparando à rede como um todo.

Retornar ao índice

3 Protocolos de Roteamento

    O protocolo de roteamento determina a forma pela qual os gateways devem trocar informações necessárias à execução do algoritmo de roteamento. Por exemplo, se o algoritmo de roteamento implementado for do tipo Vector-Distance, o protocolo de roteamento deve definir como cada gateway envia aos demais a sua distância em relação a cada sub-rede internet.

Retornar ao índice
 
 

    3.1 IGP - Interior Gateway Protocol

    O termo IGP é utilizado para designar o protocolo usado na troca de informações de roteamento entre Interior Gateways (IG).

    Em sistemas autônomos (SA) pequenos, as tabelas de roteamento podem ser determinadas, manualmente, pelo administrador do sistema. O administrador mantém uma tabela de redes do SA que é atualizada sempre que uma rede é removida ou inserida no SA . Além de não ser confiável, esse método torna-se inviável com o crescimento do SA .

    Não existe um protocolo padrão entre os gateways de um mesmo SA . Por esse motivo, o termo IGP é usado para referenciar qualquer protocolo de roteamento entre Interior Gateways (IG). Os protocolos IGP mais conhecidos são: RIP (Routing Information Protocol), Hello Protocol e OSPF (Open Shortest-Path-Frist Protocol).

RIP - Routing Information Protocol

    O RIP foi originalmente desenvolvido pela Universidade da Califórnia em Berkeley. Este protocolo permite a troca de informações utilizadas pelo algoritmo de roteamento Vector-Distance em uma sub-rede dotada do serviço de difusão de mensagens.

    O RIP divide as máquinas da sub-rede em ativas e passivas. As máquinas ativas divulgam informações de roteamento para as outras, enquanto as máquinas passivas recebem as informações e atualizam suas rotas, sem divulga-las. Tipicamente, os gateways executam o RIP no modo ativo, enquanto as estações o executam no modo passivo.

    Um gateway executando o RIP no modo ativo difunde as mensagens a cada 30 segundos e também quando recebe uma solicitação de informação de outro gateway. A mensagem difundida normalmente contém informações sobre todas as sub-redes do SA, extraídas da tabela de roteamento do gateway. Cada mensagem enviada por um gateway G consiste em pares de informações. Cada par é composto de um endereço de sub-rede IP e da distância do gateway G à sub-rede . A métrica utilizada para o cálculo de distância é baseada no número de hops (número de gateways) na melhor rota entre o gateway G e a rede. Curiosamente o RIP assume o valor "1" para a distância de um gateway a uma sub-rede à qual ele está diretamente conectado. Para compensar diferenças de tecnologia de redes, algumas implementações do RIP informam uma distância maior quando a rota atravessa uma rede lenta. Participantes ativos e passivos do RIP, quando recebem uma mensagem, atualizam suas rotas de acordo com o algoritmo de roteamento Vector-Distance, descrito anteriormente. Para evitar que uma rota oscile entre dois ou mais caminhos com a mesma métrica, o RIP especifica que uma rota deve ser atualizada somente quando a nova rota possuir distância menor que a atual.
 
 

OSPF - Open Shortest-Path-First Protocol

    O protocolo OSPF foi elaborado por um grupo de trabalho da Internet Engineering Task Force com o propósito de atender às exigências de roteamento de grandes redes, ou seja, um IGP para sistemas autônomos de porte. É um protocolo que usa o algoritmo SPS e compreende uma série de facilidades adicionais listados a seguir, as quais permitem diminuir a sobrecarga necessária para a manutenção da topologia atualizada de uma rede internet:

    O protocolo OSPF é baseado nas mensagens: Hello, Database Description, Link Status Request e Link Status Uptade. Quando um gateway OSPF é inicializado, sua primeira ação é contatar os gateways vizinhos, através de mensagens Hello. Os gateways trocam mensagens entre si para eleger o gateway mestre (DR -Designated Router). Este gateway torna-se responsável pela notificação de informações de roteamento a todos os gateways presentes na rede (gateways secundários). Nos protocolos de roteamento discutidos anteriormente todos os gateways enviavam e recebiam informações de roteamento, gerando tráfego excessivo. A figura de um gateway mestre, com o função de gerador/distribuidor de informações, reduz significativamente o tráfego relativo às mensagens de roteamento, que são trocadas somente entre o gateway mestre e os demais gateways secundários.

    O OSPF usa o roteamento link state. As informações de roteamento trocados entre gateways, através da mensagem Database Description, indicam o estado e o custo associado às interfaces e aos gateways vizinhos. Estas mensagens são confirmadas pelos gateways que a recebem. Como as bases podem ser grandes, uma base de topologia pode gerar várias mensagens. A mensagem Link Status Request é usada por um gateway na requisição de dados atualizados a outro gateway. Na mensagem Link Status Updade é usada por um gateway no envio de informações sobre o estado de seus enlaces.

    Uma vez estabelecido o gateway mestre da cada sub-rede internet ,realizada a troca de informações de roteamento entre o gateways mestres das várias sub-redes em que esteja conectado, o gateway monta a sua base de dados de roteamento. O algoritmo SPF é, então executado a partir dessa base e, como resultado, é obtida uma árvore de roteamento com o gateway na raiz, indicando a conectividade com outras redes. A partir dos dados de custo, são calculados os custos totais das rotas até cada sub-rede da internet.

Retornar ao índice

    3.2 Exterior Gateway Protocol

    O protocolo EGP não está vinculado a nenhum algoritmo de roteamento. Isto é, para que dois gateways se comuniquem através do EGP não é necessário que eles executem um mesmo algoritmo de roteamento. O EGP define as informações a serem trocadas entre EG (basicamente as tabelas de roteamento) e os elementos de protocolo necessários à troca dessas informações.

    Tais informações permitem que um ou mais sistemas autônomos sejam utilizados como intermediários do tráfego originado em algum sistema autônomo e destinado a outro, sem que o usuário da rede perceba que a rede é composta por mais de um sistema autônomo.

    O EGP é um protocolo de roteamento elaborado para uma rede de sistemas autônomos organizados em uma estrutura tipo árvore, ou seja, uma rede sem loops (ciclos) na sua topologia. As informações trocadas neste protocolo não impedem que ocorram loops no roteamento. Uma situação de loop pode ocorrer, por exemplo, quando uma tabela de roteamento de um gateway G indica o gateway G' como a melhor saída para uma rede N, e a tabela de roteamento de G' indica G como a melhor saída para a rede N.

    As mensagens do EGP são associadas a cada Sistema Autônomo através de uma identificação de 16 bits que é colocada no cabeçalho da cada mensagem do EGP. Essas mensagens trafegam somente entre gateways vizinhos. Dois gateways podem tornar-se vizinhos quando:

    Não faz parte do protocolo EGP determinar quando dois gateways devem tornar-se vizinhos. Esta é uma tarefa do administrador do SA . Dois gateways tornam-se vizinhos através da troca de mensagens de Aquisição de Vizinho.

    Após se tornarem vizinhos, dois gateways passam a trocar mensagens de Disponibilidade, para conhecer o estado do vizinho (conectado/desconectado), e mensagens de Alcance, para identificar quais redes podem ser acessadas através do vizinho.

    O EGP é um protocolo do tipo solicitação (polling). As mensagens são trocadas somente quando ocorre uma solicitação de um dos vizinhos. Por isso, o EGP permite que cada gateway controle a sua taxa de envio e recebimento de informação de roteamento. Além disso, esse protocolo permite que um SA tenha um mecanismo de roteamento interno que não é afetado por falhas em outros sistemas.

Retornar ao índice

    3.3 Border Gateway Protocol

    Com o crescimento da Internet, o uso do EGP tornou-se limitado. Existia a necessidade de acrescentar funções de policiamento no roteamento e o protocolo devia suportar topologias complexas. Consequentemente surgiu o BGP, para suprir as deficiências do EGP no roteamento entre sistemas autônomos.

    Roteadores com BGP se preocupam com critérios políticos de roteamento. Um sistema autônomo deve querer habilidade de enviar pacotes para algum site e receber pacotes de outro site de seu interesse. Entretanto, ele não deve gostar de conduzir pacotes entre sistemas autônomos (SA's) que não seja de seu interesse. Por exemplo, companhias telefônicas devem atuar como portadora de seus clientes, mas não dos outros.

    O protocolo BGP foi projetado para permitir muitos critérios de roteamento a serem aplicadas no tráfego entre SA's. Critérios típicos envolvem considerações de ordem política, de segurança, ou econômicas. Alguns exemplos de limites de roteamento são: nunca coloque o Iraque na rota para o Pentágono; tráfego iniciando ou terminando na IBM, não trafega para Microsoft.

    Os critérios são configurados manualmente em cada roteador BGP.

    Do ponto de vista do roteador BGP, o mundo consiste de outros roteadores BGP interconectados. Dois roteadores BGP são considerados conectados se eles compartilham uma rede comum. Dado o interesse de um BGP especial no tráfego, as redes são grupadas em três categorias. A primeira categoria é stubs networks, na qual somente tem conexão para um roteador BGP. Estas não podem ser usadas para trânsito na rede, porque só tem uma ligação. A segunda é as redes multiconnected networks. Podem ser usadas para tráfego em trânsito, exceto se recusarem. Finalmente, existem as redes transit networks, como um backbone, que estão dispostas a manipular pacotes de outros, possivelmente com algumas restrições.

    Pares de roteadores BGP se comunicam através de conexões TCP. Operando deste modo eles fornecem uma comunicação confiável e escondem os detalhes da rede que os pacotes estão passando.

    BGP é um protocolo que usa o algoritmo vector distance, mas com uma pequena diferença. Ao invés de manter a distância de cada destino, cada roteador BGP mantém o caminho usado. Similarmente, ao invés de periodicamente dar a cada vizinho a distância estimada para cada possível destino, cada roteador diz a seus vizinhos o caminho exato que está usando.

    Como um exemplo, considerar os roteadores conforme a figura. Em particular, considerar a tabela de roteamento de F. Supor que ele usa o caminho FGCD para alcançar D. Quando os vizinhos sua informação de roteamento, eles fornecem seus caminhos completos, como mostra a figura (por simplicidade, somente o destino D é ilustrado).
 
 





    Após todos os caminhos chegarem dos vizinhos. F examina-os para ver qual é o melhor. Rapidamente descarta os caminhos de I e E, porque estes caminhos passam por F. A escolha está entre B e G. Cada roteador BGP contém um módulo que examina rotas para um dado destino e dá um valor a eles, retornando um número da distância para o destino de cada rota. Alguma rota viola um critério de roteamento e seu valor é infinito. O roteador então adota a rota de menor distância.

    BGP facilmente resolve o problema de contagem infinita que causa problema a outros algoritmos de roteamento. Por exemplo, supor que G quebre ou a linha FG esteja desativada. F então recebe rotas dos outros três vizinhos. Estas rotas são BCD, IFGCD e EFGCD. Verifica-se que duas rotas estão sem sentido, porque passam por F, então é escolhido FBCD como a nova rota.

vector-distance, uma diferente estratégia de podar a árvore deve ser seguida. O algoritmo básico é o reverse path forwarding. Entretanto, quando um roteador que não faz parte do grupo, recebe uma mensagem multicast, ele responde para que o emissor não envie mensagens para ele.

    Uma desvantagem deste algoritmo é que para grandes redes muita memória é necessária. Supor que uma rede tem n grupos, cada um com a média de m membros. Para cada grupo, m spanning trees podadas são armazenadas, para um total de m.n árvores. Quando muitos grupos grandes existem, é gasto muito memória para armazenar as árvores.

    Uma alternativa é usar árvores chamadas core-base tree. Aqui uma única árvore spanning tree por grupo é computada, com a raiz ("the core") perto do meio do grupo. Para enviar uma mensagem multicast, uma estação envia-a para a raiz, que então envia para os nós do grupo. Embora esta técnica não seja ótima, ela reduz os custos de armazenagem de m árvores para uma árvore por grupo.

Retornar ao índice

4 Conclusão
    Este trabalho é um pequeno resumo do livro Redes de Computadores/capítulo 5 - Andrew S. Tanenbaum.
Observa-se que o roteador e seu protocolo são basicamente o "coração" da internet. Sem eles não haveria a comunicação entre milhares de computadores espalhados por todo o mundo. E é através de suas melhorias, de acordo com o crescimento da rede mundial, que conseguimos nos comunicar e obter informações diariamente.

Retornar ao índice