Protocolo de roteamento link-state - Link-state routing protocol

Os protocolos de roteamento link-state são uma das duas classes principais de protocolos de roteamento usados ​​em redes de comutação de pacotes para comunicações de computador , sendo a outra os protocolos de roteamento de vetor de distância . Exemplos de protocolos de roteamento link-state incluem Open Shortest Path First (OSPF) e Intermediate System to Intermediate System (IS-IS).

O protocolo link-state é executado por cada nó de comutação na rede (ou seja, nós que estão preparados para encaminhar pacotes; na Internet , são chamados de roteadores ). O conceito básico de roteamento link-state é que cada nó constrói um mapa da conectividade com a rede, na forma de um gráfico , mostrando quais nós estão conectados a quais outros nós. Cada nó, então, calcula independentemente o próximo melhor caminho lógico a partir dele para cada destino possível na rede. Cada coleção de melhores caminhos formará a tabela de roteamento de cada nó .

Isso contrasta com os protocolos de roteamento de vetor de distância , que funcionam fazendo com que cada nó compartilhe sua tabela de roteamento com seus vizinhos. Em um protocolo de estado de link, a única informação passada entre os nós está relacionada à conectividade . Os algoritmos de estado de link às vezes são caracterizados informalmente como cada roteador, "informando ao mundo sobre seus vizinhos".

História

O que se acredita ser a primeira rede de roteamento adaptável de computadores, usando roteamento link-state como seu coração, foi projetada e implementada durante 1976-77 por uma equipe do Plessey Radar liderada por Bernard J Harris; o projeto era para "Wavell" - um sistema de comando e controle de computador para o Exército Britânico.

O primeiro conceito de roteamento link-state foi publicado em 1979 por John M. McQuillan (então na Bolt, Beranek e Newman ) como um mecanismo que calcularia rotas mais rapidamente quando as condições da rede mudassem e, assim, levaria a um roteamento mais estável.

Um trabalho posterior na BBN Technologies mostrou como usar a técnica de link-state em um sistema hierárquico (ou seja, aquele em que a rede era dividida em áreas) de modo que cada nó de comutação não precisasse de um mapa de toda a rede, apenas da área ( s) em que está incluído.

A técnica foi posteriormente adaptada para uso nos protocolos de roteamento de estado de link contemporâneos IS-IS e OSPF. A literatura da Cisco refere-se ao protocolo de roteamento de gateway interior aprimorado (EIGRP) como um protocolo "híbrido", apesar do fato de distribuir tabelas de roteamento em vez de mapas de topologia. No entanto, ele sincroniza as tabelas de roteamento na inicialização como o OSPF faz e envia atualizações específicas apenas quando ocorrem alterações na topologia.

Em 2004, Radia Perlman propôs o uso de roteamento link-state para o encaminhamento de quadros da camada 2 com dispositivos chamados pontes de roteamento ou Rbridges. A Força-Tarefa de Engenharia da Internet padronizou o protocolo de interconexão transparente de muitos links (TRILL) para fazer isso.

Mais recentemente, essa técnica hierárquica foi aplicada a redes em malha sem fio usando o protocolo de roteamento de estado de link otimizado (OLSR). Onde uma conexão pode ter qualidade variável, a qualidade de uma conexão pode ser usada para selecionar conexões melhores. Isso é usado em alguns protocolos de roteamento que usam transmissão de radiofrequência.

Em 2012, o IEEE concluiu e aprovou a padronização do uso de IS-IS para controlar o encaminhamento de Ethernet com IEEE 802.1aq shortest path bridging (SPB).

Distribuindo mapas

Esta descrição cobre apenas a configuração mais simples; ou seja, um sem áreas, de modo que todos os nós tenham um mapa de toda a rede. O caso hierárquico é um pouco mais complexo; consulte as várias especificações de protocolo.

Conforme mencionado anteriormente, o primeiro estágio principal no algoritmo de estado de enlace é fornecer um mapa da rede para cada nó. Isso é feito com várias etapas subsidiárias.

Determinando os vizinhos de cada nó

Primeiro, cada nó precisa determinar a quais outras portas está conectado, em links totalmente funcionais; ele faz isso usando o protocolo de acessibilidade que é executado periodicamente e separadamente com cada um de seus vizinhos diretamente conectados.

Distribuindo as informações para o mapa

Em seguida, cada nó periodicamente (e em caso de alterações de conectividade) envia uma mensagem curta, o anúncio de link-state , que:

  • Identifica o nó que o está produzindo.
  • Identifica todos os outros nós (roteadores ou redes) aos quais está diretamente conectado.
  • Inclui um 'número de sequência', que aumenta cada vez que o nó de origem cria uma nova versão da mensagem .

Esta mensagem é enviada a todos os nós de uma rede. Como um precursor necessário, cada nó na rede lembra, para cada um de seus vizinhos, o número de seqüência da última mensagem de link-state que recebeu daquele nó. Quando um anúncio de link-state é recebido em um nó, o nó procura o número de sequência armazenado para a origem dessa mensagem de link-state: se esta mensagem for mais recente (ou seja, tiver um número de sequência maior), ela será salva , o número de sequência é atualizado e uma cópia é enviada por sua vez para cada um dos vizinhos daquele nó. Este procedimento obtém rapidamente uma cópia da versão mais recente do anúncio de link-state de cada nó para cada nó da rede.

As redes que executam algoritmos de estado de link também podem ser segmentadas em hierarquias que limitam o escopo das alterações de rota. Esses recursos significam que os algoritmos de estado de link escalam melhor para redes maiores.

Criando o mapa

Finalmente, com o conjunto completo de anúncios link-state (um de cada nó na rede) em mãos, cada nó produz o gráfico para o mapa da rede. O algoritmo itera sobre a coleção de anúncios link-state; para cada um, faz links no mapa da rede, desde o nó que enviou a mensagem, a todos os nós que essa mensagem indica serem vizinhos do nó remetente.

Nenhum link é considerado como tendo sido relatado corretamente a menos que as duas pontas concordem; ou seja, se um nó relatar que está conectado a outro, mas o outro nó não relatar que está conectado ao primeiro, há um problema e o link não está incluído no mapa.

Notas sobre esta fase

A mensagem de link state com informações sobre os vizinhos é recalculada e, em seguida, inundada por toda a rede, sempre que houver uma mudança na conectividade entre o nó e seus vizinhos; por exemplo, quando um link falha. Qualquer alteração desse tipo será detectada pelo protocolo de acessibilidade que cada nó executa com seus vizinhos.

Calculando a tabela de roteamento

Como mencionado inicialmente, o segundo estágio principal no algoritmo de estado de link é produzir tabelas de roteamento, inspecionando os mapas. Isso é feito novamente com várias etapas.

Calculando os caminhos mais curtos

Cada nó executa independentemente um algoritmo sobre o mapa para determinar o caminho mais curto de si mesmo para todos os outros nós da rede; geralmente alguma variante do algoritmo de Dijkstra é usada. Isso se baseia em um custo de link em cada caminho, que inclui a largura de banda disponível, entre outras coisas.

Um nó mantém duas estruturas de dados: uma árvore contendo nós que estão "prontos" e uma lista de candidatos . O algoritmo começa com ambas as estruturas vazias; em seguida, adiciona ao primeiro o próprio nó. A variante de um Algoritmo Greedy, então, faz repetidamente o seguinte:

  • Todos os nós vizinhos que estão diretamente conectados ao nó são apenas adicionados à árvore (exceto quaisquer nós que já estão na árvore ou na lista de candidatos). O restante é adicionado à segunda lista (de candidatos).
  • Cada nó da lista de candidatos é comparado a cada um dos nós já existentes na árvore. O nó candidato que está mais próximo de qualquer um dos nós já na árvore é movido para a árvore e anexado ao nó vizinho apropriado. Quando um nó é movido da lista de candidatos para a árvore, ele é removido da lista de candidatos e não é considerado nas iterações subsequentes do algoritmo.

As duas etapas acima são repetidas enquanto houver nós restantes na lista de candidatos. (Quando não houver nenhum, todos os nós da rede terão sido adicionados à árvore.) Este procedimento termina com a árvore contendo todos os nós da rede, com o nó no qual o algoritmo está sendo executado como a raiz da árvore . O caminho mais curto desse nó para qualquer outro nó é indicado pela lista de nós que alguém atravessa para ir da raiz da árvore ao nó desejado na árvore ..!

Preenchendo a tabela de roteamento

Com os caminhos mais curtos em mãos, a próxima etapa é preencher a tabela de roteamento. Para qualquer nó de destino determinado, o melhor caminho para esse destino é o nó que é a primeira etapa do nó raiz, descendo o galho na árvore do caminho mais curto que leva ao nó de destino desejado. Para criar a tabela de roteamento, basta percorrer a árvore, lembrando-se da identidade do nó no topo de cada ramificação e preenchendo a entrada da tabela de roteamento para cada nó que encontrarmos com essa identidade.

Otimizações para o algoritmo

O algoritmo descrito acima foi feito o mais simples possível, para facilitar o entendimento. Na prática, várias otimizações são usadas.

Recomputação Parcial

Sempre que ocorre uma mudança no mapa de conectividade, é necessário recalcular a árvore do caminho mais curto e, em seguida, recriar a tabela de roteamento. O trabalho da BBN Technologies descobriu como recalcular apenas a parte da árvore que poderia ter sido afetada por uma determinada mudança no mapa. Além disso, a tabela de roteamento normalmente seria preenchida conforme a árvore do caminho mais curto é calculada, em vez de torná-la uma operação separada.

Redução de topologia

Em alguns casos, é razoável reduzir o número de nós que geram mensagens LSA. Por exemplo, um nó que possui apenas uma conexão com o grafo da rede não precisa enviar mensagens LSA, pois a informação sobre sua existência já pode estar incluída na mensagem LSA de seu único vizinho. Por esta razão, uma estratégia de redução de topologia pode ser aplicada, na qual apenas um subconjunto dos nós da rede gera mensagens LSA. Duas abordagens amplamente estudadas para redução de topologia são:

  1. Relés MultiPoint que estão na base do protocolo OLSR , mas também foram propostos para OSPF
  2. Conjuntos dominantes conectados que novamente foram propostos para OSPF

Fisheye State Routing

Com o FSR, os LSA são enviados com diferentes valores de TTL para restringir sua difusão e limitar o overhead devido às mensagens de controle. O mesmo conceito é usado também no Protocolo de Roteamento de Estado de Link Hazy Sighted .

Modos de falha

Se todos os nós não estiverem trabalhando exatamente no mesmo mapa, os loops de roteamento podem se formar. São situações em que, da forma mais simples, dois nós vizinhos pensam que o outro é o melhor caminho para um determinado destino. Qualquer pacote dirigido a esse destino que chega em um dos nós fará um loop entre os dois, daí o nome. Os loops de roteamento envolvendo mais de dois nós também são possíveis.

Isso pode ocorrer porque cada nó calcula sua árvore de caminho mais curto e sua tabela de roteamento sem interagir de nenhuma forma com nenhum outro nó. Se dois nós começam com mapas diferentes, é possível ter cenários nos quais os loops de roteamento são criados. Em certas circunstâncias, os loops diferenciais podem ser ativados em um ambiente de várias nuvens. Os nós de acesso variável através do protocolo de interface também podem contornar o problema do nó de acesso simultâneo.

O protocolo de roteamento de estado de link otimizado para redes móveis ad hoc

O protocolo de roteamento de estado de link otimizado (OLSR) é um protocolo de roteamento de estado de link otimizado para redes ad hoc móveis (que também pode ser usado em outras redes ad hoc sem fio ). OLSR é proativo, ele usa mensagens Hello e Topology Control (TC) para descobrir e disseminar informações de estado de link na rede móvel ad hoc . Usando mensagens Hello, cada nó descobre informações de vizinho de 2 saltos e elege um conjunto de retransmissões multiponto (MPRs). Os MPRs tornam o OLSR exclusivo de outros protocolos de roteamento de estado de link. Nós individuais usam as informações de topologia para calcular os próximos caminhos de salto em relação a todos os nós na rede usando os caminhos de encaminhamento de salto mais curtos.

Veja também

Referências

  1. ^ John M. McQuillan , Isaac Richer e Eric C. Rosen, ARPANet Routing Algorithm Improvements , BBN Report No. 3803, Cambridge, abril de 1978
  2. ^ John M. McQuillan , Isaac Richer e Eric C. Rosen, o algoritmo de roteamento novo para a ARPANet , transporte IEEE . em Comm., 28 (5), pp. 711-719, 1980
  3. ^ Eastlake 3Rd, Donald E .; Senevirathne, Tissa; Ghanwani, Anoop; Dutt, Dinesh; Banerjee, Ayan (maio de 2014), Transparent Interconnection of Lots of Links (TRILL) Use of IS-IS , RFC  7176
  4. ^ Nguyen, Dang-Quan; Clausen, Thomas H .; Jacquet, Philippe; Baccelli, Emmanuel (fevereiro de 2009). "Extensão de relé multiponto OSPF (MPR) para redes ad hoc" . Citar diário requer |journal=( ajuda )
  5. ^ Ogier, Richard; Spagnolo, Phil (agosto de 2009). "Extensão de rede móvel ad hoc (MANET) de OSPF usando inundação por conjunto de dominância conectado (CDS)" . Citar diário requer |journal=( ajuda )
  6. ^ Wójcik, R (2016). "Uma pesquisa sobre métodos para fornecer transmissões multipercurso entre domínios". Redes de computadores . 108 : 233–259. doi : 10.1016 / j.comnet.2016.08.028 .
  7. ^ RFC 3626

Leitura adicional