Qual o algoritmo de roteamento usado pelo protocolo de roteamento OSPF?

TI Corporativa

Os Protocolos de Roteamento

Determinam o conteúdo das tabelas de roteamento, ou seja, são eles que ditam a forma como a tabela é montada e de quais informações ela é composta. Existem dois tipos de algoritmo atualmente em uso pelos protocolos de roteamento, algoritmo baseado em Vetor de Distancia (Distance-Vector Routing Protocols) e o algoritmo baseado no Estado de Enlace (Link State Routing Protocols).

Protocolos de Roteamento Interno

O RIP foi desenvolvido pela Xerox Corporation no inicio dos anos 80 para ser utilizada nas redes Xerox Network Systems (XNS), é o protocolo intradominio mais comum, e disponível na grande maioria das versões mais atuais do sistema operacional UNIX.
Um de seus benefícios é a facilidade de configuração, alem disso, seu algoritmo não necessita grande poder de computação, funciona bem em pequenos ambientes, porem apresenta limitações quando utilizado em redes grandes. Outra deficiência do RIP é a lenta convergência, um grande consumido de largura de banda, pois a cada 30 segundos, ele faz um broadcast de sua tabela de roteamento.

O IGRP também foi criado pela Cisco nos anos 80, resolveu grande parte dos problemas associados ao uso do roteamento interno. O algoritmo utilizado pelo IGRP determina o melhor caminho entre dois pontos dentro de uma rede examinando a largura de banda e o atraso das redes entre roteadores, converge mais rapidamente que o RIP, evitando loops de roteamento, e não tem a limitação de saltos entre roteadores viabilizando a implementação de redes grandes.

A Cisco aprimorou ainda mais o protocolo IGRP para suportar redes grandes, complexas e criticas, e criou o Enhanced IGRP. Combina protocolos de roteamento baseados em Vetor de Distancia com os mais recentes protocolos baseados no algoritmo de Estado de Enlace (Link-State). Ele também proporciona economia de trafego por limitar a troca de informações de roteamento aquelas que foram alteradas, uma desvantagem do EIGRP, assim como do IGRP, é que ambos são de propriedade da Cisco, não sendo amplamente disponíveis fora dos equipamentos deste fabricante.

Foi desenvolvido pelo IETF (Internet Engineering Task Force) como substituto para o protocolo RIP. Caracteriza-se por ser um protocolo intra-dominio, hierárquico, baseado no algoritmo de Estado de Enlace (Link-State) e foi especificamente projetado para operar com redes grandes.

O OSPF suporta roteamento hierárquico de dois níveis, possibilitando a divisão em áreas de roteamento. Uma área de roteamento é tipicamente uma coleção de uma ou mais sub-redes intimamente relacionadas. Esta hierarquia permite a consolidação dos endereços por área, reduzindo o tamanho das tabelas de roteamento. Redes pequenas podem operar utilizando uma única área OSPF.[RFC 1583]

O IS-IS [OSI 10589], assim como o OSPF, é um protocolo intradomínio, hierárquico e que utiliza o algoritmo de Estado de Enlace. Pode trabalhar sobre varias sub-redes, inclusive fazendo broadcasting para LANs, WANs e links ponto-a-ponto.
O Integrated IS-IS é uma implementação do IS-IS que, alem dos protocolos OSI, atualmente também suporta o IP. Como outros protocolos integrados de roteamento, o IS-IS convoca todos os roteadores a utilizar um único algoritmo de roteamento.
Para rodar o Integrated IS-IS, os roteadores também precisam suportar protocolos como ARP, ICMP e End System-to-Intermediate System (ES-IS).

Protocolo de Roteamento Externo

Roteadores que trocam dados entre Sistemas Autônomos são chamados de roteadores externos (exterior routers), e estes utilizam o Exterior Gateway Protocol (EGP) ou o BGP (Border Gateway Protocol). Para este tipo de roteamento são considerados basicamente coleções de prefixos CIDR (Classless Inter Domain Routing) identificados pelo numero de um Sistema Autônomo.

O BGP [RFCs 1771,1772,1773,1774,1657] assim como o EGP, é um protocolo de roteamento interdominios, criado para uso nos roteadores principais da Internet, foi projetado para evitar loops de roteamento em topologias arbitrarias, o mais serio problema de seu antecessor, o EGP (Exterior Gateway Protocol). Outro problema que o EGP não resolve – e é abordado pelo BGP é o do Roteamento Baseado em Política (policy-based routing), um roteamento com base em um conjunto de regras nao-tecnicas, definidas pelos Sistemas Autônomos. A ultima versão do BGP, o BGP4, foi projetado para suportar os problemas causados pelo grande crescimento da Internet.

NUNCA MAIS PASSE RAIVA POR NÃO CONSEGUIR RESOLVER UM PROBLEMA COM O EXCEL - GARANTIDO!

UNIVERSIDADE DO VBA - Domine o VBA no Excel Criando Sistemas Completos - Passo a Passo - CLIQUE AQUI

Quer receber novidades e e-books gratuitos?

Tutorial de TCP/IP - J�lio Battisti - Parte 15
Protocolos de Roteamento Dinâmico

Esta é a décima quinta parte do tutorial de TCP/IP. Na Parte 1 tratei dos aspectos básicos do protocolo TCP/IP. Na Parte 2 falei sobre cálculos binários, um importante tópico para entender sobre redes, máscara de sub-rede e roteamento. Na Parte 3 falei sobre Classes de endereços, na Parte 4 fiz uma introdução ao roteamento e na Parte 5 apresentei mais alguns exemplos e análises de como funciona o roteamento e na Parte 6 falei sobre a Tabela de Roteamento. Na Parte 7 tratei sobre a divisão de uma rede em sub-redes, conceito conhecido como subnetting. Na Parte 8 fiz uma apresentação de um dos serviços mais utilizados pelo TCP/IP, que é o Domain Name System: DNS. O DNS é o serviço de resolução de nomes usado em todas as redes TCP/IP, inclusive pela Internet que, sem dúvidas, é a maior rede TCP/IP existente. Na Parte 9 fiz uma introdução ao serviço Dynamic Host Configuration Protocol – DHCP. Na Parte 10 fiz uma introdução ao serviço Windows Internet Name Services – WINS. Na Parte 11 falei sobre os protocolos TCP, UDP e sobre portas de comunicação. Na Parte 12, mostrei como são efetuadas as configurações de portas em diversos aplicativos que você utiliza e os comandos do Windows 2000/XP/2003 utilizados para exibir informações sobre portas de comunicação. Na Parte 13 você aprendeu sobre a instalação e configuração do protocolo TCP/IP no Windows 2000 Professional ou Server. Apresentei, em detalhes, a configuração do protocolo TCP/IP no Windows 2000. Mostrei como fazer as configurações do protocolo TCP/IP, desde as configurações básicas de número IP e máscara de sub-rede (em computadores que usarão IP fixo, ao invés de obter as configurações a partir de um servidor DHCP), até configurações mais avançadas, tais como definir filtros para o protocolo TCP/IP.

Nas Partes 4, 5 e 6 falei sobre Roteamento e sobre como todo o processo de roteamento é baseado em Tabelas de Roteamento, existentes em cada roteador da rede. As tabelas de roteamento podem ser criadas manualmente, onde o administrador de cada roteador executa comandos para criar cada uma das rotas necessárias. Essa abordagem só é possível para redes extremamente pequenas, com um número de rotas pequeno e quando as rotas não mudam muito freqüentemente. Para redes maiores, a única abordagem possível é o uso dos chamados protocolos de Roteamento dinâmico. Estes protocolos, uma vez instalados e configurados nos roteadores, permitem que os roteadores troquem informações entre si, periodicamente e que montem as tabelas de roteamento, dinamicamente, com base nestas informações. Esta abordagem é bem mais indicada para grandes redes, pois os próprios protocolos de roteamento dinâmicos, se encarregam de manter as tabelas de roteamento sempre atualizadas, alterando rotas quando necessário e excluindo rotas que apresentam problemas, tais como rotas onde o link de comunicação está fora do ar. Na Parte 14, fiz uma apresentação do protocolo RIP, das suas características, usos e principais problemas. Nesta décima quinta parte será a vez de apresentar o protocolo OSPF e o conceito de roteamento baseada em áreas, roteadores de borda e outros ligados ao OSPF.

OSPF – Open Shorted Path First:

Nesta parte do tutorial você aprenderá sobre o OSPF, suas vantagens em relação ao RIP, o seu uso para roteamento em grandes redes, sobre os conceitos de sistemas autônomos, adjacências e assim por diante.

Uma introdução ao OSPF

O protocolo OSPF - Open Shortest Path First (OSPF, uma tradução, digamos, muito forçada, seria: abrir primeiro o caminho mais curto) é a alternativa para redes de grande porte, onde o protocolo RIP não pode ser utilizado, devido a suas características e limitações, conforme descrito na Parte 14 deste tutorial.

O OSPF permite a divisão de uma rede em áreas e torna possível o roteamento dentro de cada área e entre as diferentes áreas, usando os chamados roteadores de borda. Com isso, usando o OSPF, é possível criar redes hierárquicas de grande porte, sem que seja necessário que cada roteador tenha uma tabela de roteamento gigantesca, com rotas para todas as redes, como seria necessário no caso do RIP. O OSPF é projetado para intercambiar informações de roteamento em uma interconexão de rede de tamanho grande ou muito grande, como por exemplo a Internet.

A maior vantagem do OSPF é que ele é eficiente em vários pontos: requer pouquíssima sobrecarga de rede mesmo em interconexões de redes muito grandes, pois os roteadores que usam OSPF trocam informações somente sobre as rotas que sofreram alterações e não toda a tabela de roteamento, como é feito com o uso do RIP. Sua maior desvantagem é a complexidade: requer planejamento adequado e é mais difícil de configurar e administrar do que o protocolo RIP.

O OSPF usa um algoritmo conhecido como Shortest Path First (SPF, primeiro caminho mais curto) para calcular as rotas na tabela de roteamento. O algoritmo SPF calcula o caminho mais curto (menor custo) entre o roteador e todas as redes da interconexão de redes. As rotas calculadas pelo SPF são sempre livres de loops (laços). O OSPF usa um algoritmo de roteamento conhecido como link-state (estado de ligação). Lembre que o RIP usava um algoritmo baseado em distância vetorial. O OSPF aprende as rotas dinamicamente, através de interação com os roteadores denominados como seus vizinhos.

Em vez de intercambiar as entradas de tabela de roteamento como os roteadores RIP (Router Information Protocol, protocolo de informações do roteador), os roteadores OSPF mantêm um mapa da interconexão de redes que é atualizado após qualquer alteração feita na topologia da rede (é importante salientar novamente que somente informações sobre as mudanças são trocadas entre os roteadores usando OSPF e não toda a tabela de roteamento, como acontece com o uso do RIP). Esse mapa, denominado banco de dados do estado de vínculo ou estado de ligação, é sincronizado entre todos os roteadores OSPF e é usado para calcular as rotas na tabela de roteamento. Os roteadores OSPF vizinhos (neghboring) formam uma adjacência, que é um relacionamento lógico entre roteadores para sincronizar o banco de dados com os estados de vínculo.

As alterações feitas na topologia de interconexão de redes são eficientemente distribuídas por toda a rede para garantir que o banco de dados do estado de vínculo em cada roteador esteja sincronizado e preciso o tempo todo. Ao receber as alterações feitas no banco de dados do estado de vínculo, a tabela de roteamento é recalculada.
À medida que o tamanho do banco de dados do estado de vínculo aumenta, os requisitos de memória e o tempo de cálculo do roteamento também aumentam. Para resolver esse problema, principalmente para grandes redes, o OSPF divide a rede em áreas (conjuntos de redes contíguas) que são conectadas umas às outras através de uma área de backbone. Cada roteador mantém um banco de dados do estado de vínculo apenas para aquelas áreas que a ele estão conectadas. Os ABRs (Area Border Routers, roteadores de borda de área) conectam a área de backbone a outras áreas.

Esta divisão em áreas e a conexão das áreas através de uma rede de backbone é ilustrada na Figura a seguir, obtida na Ajuda do Windows 2000 Server:

Cada anúncio de um roteador OSPF contém informações apenas sobre os estados de ligação dos roteadores vizinhos, isto é, dentro da área do roteador. Com isso a quantidade de informação transmitida na rede, pelo protocolo OSPF, é bem menor do que a quantidade de informação transmitida quando é usado o protocolo RIP. Outra vantagem é que os roteadores OSPF param de enviar anúncios, quando a rede atinge um estado de convergência, ou seja, quando não existem mais alterações a serem anunciadas. O RIP, ao contrário, continua enviando anúncios periodicamente, mesmo que nenhuma alteração tenha sido feita na topologia da rede (tal como um link ou roteador que tenha falhado).

Nota: Na Internet existe a divisão nos chamados Sistemas Autônomos. Um sistema autônomo, por exemplo, pode representar a rede de um grande provedor. Neste caso, o próprio sistema autônomo pode ser dividido em uma ou mais áreas usando OSPF e estas áreas são conectadas por um backbone central. O roteamento dentro de cada sistema autônomo é feito usando os chamados protocolos de roteamento interno (IGP – Interior Gateway Protocol). O OSPF é um protocolo IGP, ou seja, para roteamento dentro dos sistemas autônomos. O roteamento entre os diversos sistemas autônomos é feito  por protocolos de roteamento externos (EGP – Exterior Gateway Protocol) e pelos chamados protocolos de roteamento de borda (BGP – Border Gateway Protocol).

Promo��o: Livro Windows Server 2012 R2 e Active Directory Curso Completo, 2100 p�ginas. Tudo para voc� se tornar um administrador de redes altamente qualificado para o mercado de trabalho e levar a sua carreira para o pr�ximo n�vel! MAIS DETALHES | COMPRAR ESTE LIVRO

Importante: Podem ocorrer situações em que uma nova área que é conectada a rede, não pode ter acesso físico direto ao backbone OSPF. Nestas situações, a conexão da nova área com o backbone OSPF é feita através da criação de um link virtual (virtual link). O link virtual fornece uma caminho “lógico” entre a área fisicamente separada do backbone e o backbone OSPF. Criar o link virtual significa criar uma rota entre a área que não está fisicamente conectada ao backbone e o backbone, mesmo que este link passe por dois ou mais roteadores OSPF, até chegar ao backbone. Para um exemplo passo-a-passo de criação de links virtuais, consulte o Capítulo 8 do livro de minha autoria:Manual de Estudos Para o Exame 70-216, 712 páginas, publicado pela editora Axcel Books (www.axcel.com.br).

Vantages do OSPF em relação ao RIP:

• As rotas calculadas pelo algoritmo SPF são sempre livres de loops.

• O OSPF pode ser dimensionado para interconexões de redes grandes ou muito grandes.

• A reconfiguração para as alterações da topologia de rede é muito rápida, ou seja, o tempo de convergência da rede, após alterações na topologia é muito menor do que o tempo de convergência do protocolo RIP.

• O tráfego de informações do protocolo OSPF é muito menor do que o do protocolo RIP.

• O OSPF permite a utilização de diferentes mecanismos de autenticação entre os roteadores que utilizam OSPF.

• O OSPF envia informações somente quando houver alterações na rede e não periodicamente.

A implementação OSPF como parte dos serviços de roteamento do RRAS – Routing em Remote Access Services, do Windows 2000 Server e no Windows Server 2003, tem os seguintes recursos:

• Filtros de roteamento para controlar a interação com outros protocolos de roteamento.
• Reconfiguração dinâmica de todas as configurações OSPF.
• Coexistência com o RIP.
• Adição e exclusão dinâmica de interfaces.

Importante: O Windows 2000 Server não oferece suporte ao uso do OSPF em uma interface de discagem por demanda (demand-dial) que usa vínculos dial-up temporários.

Dica: Se você está usando vários protocolos de roteamento IP, configure apenas um único protocolo de roteamento por interface.

Operação do protocolo OSPF

O protocolo OSPF é baseado em um algoritmo conhecido com SPF – Short Path First. Depois que um roteador (ou um servidor com o Windows 2000 Server ou Windows Server 2003, configurado como roteador e usando o OSPF) é inicializado e é feita a verificação para detectar se as interfaces de rede estão OK, é utilizado o protocolo OSPF Hello para identificar quem são os “vizinhos” do roteador.

O roteador envia pacotes no formato do protocolo Hello, para os seus vizinhos e recebe os pacotes Hello enviados pelos seus vizinhos.

Conforme descrito anteriormente, uma rede baseada em OSPF é dividia em áreas e as diversas áreas são conectadas através de um backbone comum a todas as áreas. O algoritmo SPF é baseado na sincronização do banco de dados de estados de ligação entre os roteadores OSPF dentro de uma mesma área. Porém, ao invés de cada roteador fazer a sincronização com todos os demais roteadores OSPF da sua área, cada roteador faz a sincronização apenas com seus vizinhos (neghboring routers). A relação entre roteadores OSPF vizinhos, com o objetivo de sincronizar suas bases de dados é conhecida como “Adjacência”. O termo mais comum é “formar uma adjacência”. Porém, mesmo com o uso de adjacências, em uma rede com vários roteadores dentro da mesma área, um grande número de adjacências poderá ser formado, o que implicaria em um grande volume de troca de informações de roteamento. Por exemplo, imagine uma rede com seis roteadores OSPF dentro da mesma área. Neste caso, cada roteador poderia formar uma adjacência com os outros cinco roteadores da área, o que resultaria em um total de 15 adjacências. O número de adjacências é calculado usando a seguinte fórmula, onde n representa o número de roteadores:

Número de adjacências = n*(n-1)/2

Com um grande número de adjacências, o tráfego gerado pela sincronização do OSPF seria muito elevado. Para resolver esta questão é utilizado o conceito de Designated Router (Roteador designado). Um roteador designado é um roteador que será considerado vizinho de todos os demais roteadores da rede. Com isso é formada uma adjacência entre cada roteador da rede e o roteador designado. No nosso exemplo, da rede com 6 roteadores OSPF, dentro da mesma área, seriam formadas apenas cinco adjacências. Uma entre cada um dos cinco roteadores, diretamente com o sexto roteador, o qual foi configurado como roteador designado. Neste caso, cada roteador da rede troca informações com o roteador designado. Como o roteador designado recebe informações de todos os roteadores da área, ele fica com uma base completa e repassa esta base para cada um dos roteadores da mesma área. Observe que com o uso de um roteador designado, obtém-se uma sincronização da base completa dos roteadores e com o uso de um número bem menor de adjacências, o que reduz consideravelmente o tráfego de pacotes do OSPF.

Por questões de contingência, também é criado um Designated Backup Router (Roteador designado de backup), o qual assumirá o papel de roteador designado, no caso de falha do roteador designado principal. A eleição de qual será o roteador designado é feita automaticamente pelo OSPF, mediante uma troca de pacotes Hello, de acordo com as regras contidas no protocolo, um dos roteadores será eleito como roteador designado e um segundo como roteador designado backup.

Conclusão

Nas Partes 4, 5 e 6 falei sobre Roteamento e sobre como todo o processo de roteamento é baseado em Tabelas de Roteamento, existentes em cada roteador da rede. As tabelas de roteamento podem ser criadas manualmente, onde o administrador de cada roteador executa comandos para criar cada uma das rotas necessárias. Essa abordagem só é possível para redes extremamente pequenas, com um número de rotas pequeno e quando as rotas não mudam muito freqüentemente. Para redes maiores, a única abordagem possível é o uso dos chamados protocolos de Roteamento dinâmico. Estes protocolos, uma vez instalados e configurados nos roteadores, permitem que os roteadores troquem informações entre si, periodicamente e que montem as tabelas de roteamento, dinamicamente, com base nestas informações. Esta abordagem é bem mais indicada para grandes redes, pois os próprios protocolos de roteamento dinâmico, se encarregam de manter as tabelas de roteamento sempre atualizadas, alterando rotas quando necessário e excluindo rotas que apresentam problemas, tais como rotas onde o link de comunicação está fora do ar. Na Parte 14 fiz uma apresentação do protocolo RIP. Nesta parte foi a vez do protocolo OSPF, o qual é baseado na divisão de uma rede em áreas conectadas através de backbones de roteamento. Você pode conferir que o protocolo OSPF tem inúmeras vantagens em relação ao protocolo RIP.

Outras partes do Tutorial

Livros Indicados de Redes pelo Júlio Battisti

CURSOS ONLINE DE REDES E TCP/IP

Qual o algoritmo utilizado pelo OSPF para encontrar o melhor caminho?

Qual a camada do protocolo OSPF?

Qual é a métrica de roteamento na qual o OSPF se baseia?

O que é um algoritmo de roteamento?