OSPF - Open Shortest Path First

OSPF   Open Shortest Path First

   O OSPF - Open Shortest Path First - é um protocolo de roteamento para redes que operem com protocolo IP; desenvolvido pelo grupo de trabalho de IGPs (Interior Gateway Protocol) da IETF (Internet Engineering Task Force) e descrito inicialmente em 1989 pela RFC 1131. Baseado no algoritmo Shortest Path First (menor rota primeiro), o OSPF foi criado para substituir o protocolo RIP empregado no final da década de 1980 na então Arpanet (atual Internet) e que apresentava diversos problemas e limitações para operar satisfatoriamente em uma rede de grande porte.

PRINCÍPIO DO FUNCIONAMENTO

   - Embora possua inúmeros detalhes de implementação e configuração, o princípio de roteamento do OSPF é relativamente simples. Ao invés de manter uma tabela com todas as rotas possíveis (como faz o protocolo RIP), cada nó (roteador) OSPF contêm dados sobre todos os links da rede. Cada entrada da tabela de roteamento OSPF contém um identificador de interface, um número do link e uma distância ou custo (esse último pode ser atribuído pelo administrador da rede). Com todas essas informações, cada nó possui uma visão da topologia da rede e pode, dessa forma, descobrir sozinho qual é a melhor rota para um dado destino.

    - Caso ocorra uma alteração num dos links de rede, os nós adjacentes avisam seus vizinhos. Esses por sua vez, verificam o número da mensagem ou a hora no cabeçalho do pacote OSPF para saberem se este aviso é novo ou velho. Se o aviso for novo, é feita a verificação da existência da entrada. Caso ela não exista, é adicionada à tabela de roteamento. Se a entrada já existir, são comparados os números da mensagem recebida com a entrada existente na tabela de roteamento.    Se o número da mensagem recebida for maior que a entrada existente, a entrada é substituída, caso contrário, a entrada da tabela é transmitida como uma nova mensagem. Se os números forem iguais, o nó não executa nenhuma ação.

PRINCIPAIS CARACTERÍSTICAS

    - Há duas características principais no OSPF. A primeira, é que se trata de um protocolo aberto, o que significa que suas especificações são de domínio público; suas especificações podem ser encontradas na RFC (Request For Comments) número 1247. A segunda, é que ele se baseia no algoritmo SPF, também chamado de algoritmo de Dijkstra, nome de seu criador.

    - OSPF é um protocolo de roteamento do tipo link-state, que envia avisos sobre o estado da conexão (link-state advertisements, LSA) a todos os outros roteadores em uma mesma área hierárquica. Informações sobre interfaces ligadas, métrica usada e outras variáveis são incluídas nas LSAs. Ao mesmo tempo em que o roteador OSPF acumula informações sobre o estado do link, ele usa o algoritmo SPF para calcular a menor rota para cada nó.

    - Por ser um protocolo do tipo link-state, o OSPF difere-se do RIP e do IGRP, que são protocolos de roteamento baseados em vetores de distância. Os roteadores que trabalham com algoritmos de vetor de distância, a cada atualização, enviam toda ou parte de suas tabelas de roteamento para seus vizinhos.

    - O OSPF suporta os seguintes tipos de redes: redes ponto-a-ponto

pares de roteadores ligados redes non-broadcast

vários roteadores conectados mas que não permitem difusão redes broadcast

vários roteadores conectados e que permitem difusão

    - O algoritmo de caminho mínimo minimiza o custo da transmissão da informação de um roteador origem a um roteador destino. Para tal cálculo, utiliza-se o que se chama de base de dados topológica da rede que nada mais é do que um grafo, considerando os roteadores como nós e as ligações como arcos aos quais pode-se associar pesos. Estes pesos podem representar capacidade, banda, taxa de erros ou qualquer outra medida de interesse.

   A base de dados topológica é montada através de informações enviadas pelos roteadores, chamadas de Link State Advertisements (LSAs). Os LSAs são gerados pelo roteador eleito como Designated Router.

   As tabelas de roteamento são geradas pelos roteadores formando uma ávore de caminhos mínimos tomando a si mesmo como raiz da árvore. Esta árvore indica todos os caminhos mínimos partindo do roteador.

   O OSPF permite a separação de rotas por tipos de serviços (TOS), ou seja, podemos ter diferentes rotas partindo de uma fonte para um destino, dependendo do que se deseja transmitir. Desta maneira, como podemos ter diferentes custos das ligações para cada tipo de serviço, calcula-se uma árvore de caminho mínimo para cada um deles. Além disso, também podemos ter uma métrica externa para cada tipo de serviço. Os tipos são representados exatamente como nos cabeçalhos dos pacotes IP.

    - A sequência desde a inicialização do roteador até o estabelecimento da tabela de roteamento: roteador é ligado.

inicialização das estruturas de dados do protocolo de roteamento

camadas mais baixas indicam que interface está funcional

roteador identifica os vizinhos através do Protocolo Hello

o Designated Router é eleito através do Protocolo Hello formação de adjacências

sincronização de bases topológicas por pares adjacentes

roteadores enviam advertisements sobre seu link states periodicamente ou quando seu estado muda

a alteração é propagada através de um procedimento conhecido como LSA flooding (link state advertisement flooding)

cada roteador calcula a árvore de caminho mínimo

a árvore dá origem às tabelas de roteamento

    - Uma característica muito importante no OSPF é a possibilidade de divisão do Sistema Autônomo em áreas. Uma área é um subconjunto de redes e máquinas do Sistema Autônomo rodando o mesmo algoritmo de roteamento de estado de link. As topologias de cada área são invisíveis umas para as outras, o que permite um isolamento e como consequência uma redução do tráfego em cada área. Obviamente, com essa divisão, os roteadores de um SA não mais apresentam a mesma base de dados topológica.
   Com a divisão do SA em áreas, surge o roteamento intra-área e o inter-área. De acordo com a localização dos roteadores com relação às áreas, podemos classificá-los segundo categorias, não necessariamente mutuamente exclusivas:     Roteadores internos (IR - internal routers):

roteadores ligados a redes pertencentes a uma mesma área ou ligados somente ao backbone

roteadores de borda de área (ABR - area border routers): roteadores ligados a mais de uma área, rodando um algoritmo para cada área a que pertencem e mais um para o backbone

roteadores de backbone (BR - backbone routers): é um roteador ligado ao backbone

roteadores de fronteira do SA (ASBR - AS boundary routers): como o próprio nome indica é um roteador que está na fronteira de dois SAs

   Através do esquema abaixo, os tipos de roteadores classificados segundo a divisão apresentada. A figura representa uma rede onde An é a área n, SAn á o Sistema Autônomo n e os círculos verdes são roteadores.

Foto 1

3,7,10 - ABR

1,2,4,8,9,11,12 - IR

5,6 - ASBR

3,4,5,6,7 - BR

   É interessante notar que roteadores que só tenham interfaces no backbone (caso do roteador 4), são classificados como internos pois o backbone pode ser considerado uma área. Também podemos ver que a classificação de Backbone Router é independe da classificação quanto aos outros 3 tipos, já que um Area Border Router, como 3 e o 7 são também Backbone Routers.

   O Backbone é formado por: redes que não estão em nenhuma das áreas, roteadores ligados a essas redes e roteadores que pertencem a várias áreas.

O backbone não pode ser descontínuo. Caso não haja continuidade, a mesma pode ser restaurada através da configuração de virtual links, que funcionam como redes ponto-a-ponto entre 2 roteadores com interfaces numa área comum. Por exemplo: se tivéssemos os roteadores 10 e 13, como na figura a seguir, poderíamos criar um link virtual até o 10 (ligação em laranja) evitando uma possível descontinuidade. O custo dos virtuais links é dado pela métrica intra-área, ou seja, os "pesos" das ligações através de link virtual são equivalentes a uma ligação comum dentro da área. Os links virtuais também podem ser utilizados pelo administrador de redes como forma de manter algum controle sobre as rotas inter-área, já que este tipo de ligação pode funcionar como uma espécie de "túnel" entre áreas.

Foto 2

   O backbone, apesar de ser responsável por distribuir informação de roteamento entre as áreas (roteamento inter-área), também funciona como uma, já que não enxerga as outras topologias. OSPF suporta endereçamento de sub-redes de vários tamanhos, ou seja, juntamente com o endereço IP, é enviado um endereço de sub-rede.

Desta forma, o envio de um advertisement pode se referir a um conjunto de máquinas e não somente a uma. Uma vantagem que se pode tirar disso é que se fizermos uma área corresponder a um endereço de sub-rede o envio de informações de roteamento pode ser facilitado.

ESCOLHA DO DR E DO BDROUTER

   O Designated Router é responsável pelo envio de LSAs em redes multi-acesso. O Backup Designated Router cumpre a função do Designated Router caso o primeiro falhe, evitando que uma tentativa de acesso seja respondida com "destination unreachable" (destino inalcançável).

   Apresentamos, a seguir, os passos para eleição dos roteadores designados: O algoritmo de eleição do Designated Router e do Backup Designated Router cria uma lista de roteadores pertencentes à rede. Inicialmente, descartamos os roteadores que não são elegíveis, ou seja, roteadores com Router Priority igual a 0.

    - Calcula-se o novo Backup Designated Router:

   Apenas os roteadores que não se declararam como Designated Router podem ser elegíveis para BDR.

  Caso mais de um roteador tenha se declarado BDR, vence aquele que tiver maior prioridade. Se houver empate, vence aquele que possuir o maior Router ID.

Caso ninguém tenha se declarado BDR, o roteador da lista com maior prioridade é eleito BDR. Se houver empate, é eleito aquele que tiver maior Router ID.

    - Calcula-se o novo Designated Router:

   Caso mais de um roteador tenha se declarado DR, vence aquele que tiver maior prioridade. Se houver empate, vence aquele que possuir o maior Router ID.

   Caso ninguém tenha se declarado DR, o roteador da lista com maior prioridade é eleito DR. Se houver empate, é eleito aquele que tiver maior Router ID.

   PACOTE OSPF

  - Há cinco tipos distintos de pacotes OSPF. Cada um dos cinco tipos inicia com um cabeçalho padrão de 24 bytes. E são eles:

   Pacote de aviso. (Hello packet)

   Pacote de informações do Banco de Dados (Database Description packet)

   Requisição de estado de link (Link State Request packet)

   Atualização de estado de link (Link State Update packet)

   Recebimento de informações de link (Link State Acknowledgment packet)

   Os pacotes Hello são utilizados para descobrir e manter relacionamentos de adjacência e para eleição de Designated Routers em redes multi-acesso. Os pacotes Database Description, para formar adjacências e os pacotes Link State Update e Link State Acknowledgement cumprem a função de atualizar as informações de roteamento.

   Os pacotes OSPF, com exceção dos pacotes Hello, são enviados somente para as adjacências. A seguir, o formato dos pacotes e do cabeçalho OSPF (presente em todos os pacotes).
Cabeçalho OSPF  - Estes são os dados que precedem qualquer pacote OSPF. A seguir, descrevemos cada campo.

Foto3

Foto4

Version: é o número da Versão do OSPF
Type: É o tipo do pacote OSPF podendo ser

Packet length: é o tamanho do pacote, em bytes
Router ID: é o identificador do roteador de onde o pacote originou
Área ID: é um número de 32 bits que identifica a área a que o pacote pertence. Este número será 0.0.0.0 em caso de links virtuais
Checksum: é o Checksum padrão do IP, sendo calculado para o conteúdo inteiro do pacote, excetuando-se o campo de autenticação.

Autype: especifica a autenticação utilizada para o pacote, podendo ser:

Authentication: é um campo de 64 bits utilizado para a autenticação

Pacote Hello - Os pacotes Hello são enviados periodicamente para o estabelecimento e manutenção de relacionamentos de adjacência e para eleição de Designated Routers.

Network Mask: é a máscara associada às interfaces para as quais se deseja enviar o pacote
Hello Interval: é o número de segundos entre os pacotes de Hello.
RtrPri: é a prioridade do roteador, sendo utilizada na eleição do Designated Router e do Backup Designated Router.
Router Dead Interval: é o número de segundos antes de considerar que um roteador que está em silêncio (saiu fora do ar).
Designated Router: é o IP do Designated Router nesta rede, sendo 0.0.0.0 quando não houver um Designated Router.
Backup Designated Router: é o IP do Backup Designated Router nesta rede, sendo 0.0.0.0 quando não houver um Backup Designated Router.
Neighbor: são os identificadores de todos os roteadores que mandaram pacotes Hello válidos no último RouterDeadInterval.

Database Description - Esse tipo de pacote é enviado quando se deseja iniciar uma adjacência, tendo como conteúdo a descrição da base de dados topológica, descrição esta que pode necessitar de mais de um pacote.

                              

Options: este campo diz respeito às capacidades opcionais do OSPF que são diferenciação por Tipo de Serviço (Type of Service) e Capacidade de Roteamento Externo (External Routing Capatibility).

I: Quando contendo a valor 1, indica que este pacote é o primeiro de uma sequência de pacotes de descrição da base de dados.

M: Quando contendo o valor 1, indica que há mais pacotes de descrição da base de dados por vir.

MS: Este bit identifica quem é o Master e quem é o slave durante o processo de troca de base de dados. O bit 1 identifica o Master e o 0, o Slave.

DD: identifica a sequência dos pacotes de descrição da base de dados.

LSA header -  é o cabeçalho que precede cada link state advertisement.

LS age: é o tempo em segundos desde que o advertisement foi gerado
Options: este campo se refere às capacidades opcionais do OSPF
LS Type: é o tipo do LS. Há cinco tipos diferentes de link state advertisement:

Tipo                                                                      Descrição

Router link advertisement (tipo 1) - são anúncios originários de todos os roteadores de                     uma determinada área, sendo espalhados pela mesma

Network link advertisement (tipo 2) - são anúncios gerados pelo Designated Router em redes multi-acesso, contendo a lista de roteadores numa determinada rede

Summary link advertisement (tipo 3, 4) - gerado pelos area border routers e espalhados para a área associada, descrevendo rotas para destinos fora desta área, mas pertencente ao mesmo SA. O tipo 3 diz respeito a rotas para redes enquanto que o tipo 4 diz respeito a rotas para roteadores de fronteira do SA (AS bondary routers).

AS External link advertisement (tipo 5) - gerados por AS boundary routers e espalhados para toda o Sistema Autônomo , este tipo de anúncio descrever rotas para destinos fora do SA.

Link State ID - este campo identifica que parte do domínio está sendo descrito pelo link state advertisement. Este campo assumirá valores dependendo do tipo do LS de acordo com a tabela abaixo:

LS Type	Link State ID
1	Router ID do roteador que gerou o LSA
2	IP do DR da rede
3	ID da rede de destino
4	Router ID do ASBR
5	IP da rede de destino

Advertising Router: é o Router ID do roteador que gerou o link state advertisement

LS sequence: este campo funciona como uma espécie de contador de advertisements, sendo utilizado na detecção de link state advertisement antigos ou duplicados

LS checksum: é o checksum do conteúdo completo (com exceção do LS age) do link state advertisement

length: é o comprimento do link statement advertisement em bytes, incluindo o cabeçalho.

Link State Request  - Este pacote é utilizado quando um roteador, tendo recebido as informações da base de dados topológica, envia uma mensagem requerendo informações por "perceber" a existência de informações obsoletas. Estes pacotes são enviados a roteadores que tem base de dados topológica mais atualizada. Pode ser que seja necessário o envio de pacotes desse tipo para mais de um roteador para se ter as informações devidamente atualizadas.

Cabeçalho OSPF (24)

LS Type (4)

Link State ID (4)

Advertising Router (4)

LS Type: é o tipo do LS, podendo ser um dos 5 tipos descritos anteriormente.

Link State ID: este campo identifica que parte do domínio está sendo descrito pelo link state advertisement, podendo assumir um dos valores descritos anteriormente.

Advertising Router: é o Router ID do roteador que gerou o link state advertisement.

Link State Update - este tipo de pacote é utilizado no processo de atualização das bases de dados topológicas.

#advertisements (4)

Link State advertisement 1 (4)

Link State advertisement 2 (4)

.

.

.

#advertisements: é o número de link state advertisements incluído no pacote de update.
Link State advertisement 1,2,3,etc: é uma lista de link state advertisements

Link State Acknowledgement - este tipo de pacote é utilizado no processo de atualização das bases de dados topológicas e é enviado como reconhecimento do recebimento dos Link State Updates.

Cabeçalho OSPF (24)

Link State Advertisement Header 1 (4)

Link State Advertisement Header 2 (4)

.

.

.

Link State Advertisement Header 1,2,3,etc: é uma lista com os cabeçalhos dos link state advertisements recebidos.

OSPF – TIPOS DE LSA’s (Router LSA – Tipo 1)

Todos os Roteadores de uma área OSPF possuem a visão completa dos links daquela área e baseando-se nessa visão, calculam individualmente o melhor caminho para determinado destino.
Para a formação da tabela dos links, chamado de LSDB, o OSPF baseia-se nos LSA’s (Link State Advertisements) para transmitir informações para os Roteadores Vizinhos. Os principais tipos de LSA’s são:
Tipo 1 - Representa um Roteador
Tipo 2 - Representa o DR
Tipo 3 – Representam os links declarados por um ABR de outra Area OSPF
Tipo 4 - Representa um ASBR (Autonomous System Border Router)
Tipo 5 - Representa uma rota externa ao domínio OSPF
Tipo 7 - Usado em áreas NSSA.

                                                       OSPF - LSA Tipo 1 (Router LSA)

Os LSA’s do tipo 1 são gerados pelos Roteadores, dentro da área que pertencem, listando os links, Router ID, custo, etc. O LSA tipo 1 é encaminhado e limitado dentro da própria área.

LS Age: Tempo em segundos que o LSA foi originado.

Options: Identifica  as capacidades opcionais suportadas pelo Roteador, como circuitos por demanda e etc.

LS Type: Representa o tipo do LSA, neste post citaremos o tipo 1

Link-State ID: O uso especifico depende de cada tipo de LSA.

Advertising Router: Identifica o Router ID do Roteador que está gerando o LSA.

LS Sequence Number: Identifica os novos LSAs pelo numero de sequência. Incrementando sequencialmente entre 0x80000001 e 0x7FFFFFFF.

LS Checksum: Verifica o checksum no LSA.

Length: Identifica o tamanho do LSA.

Link State ID: Identifica o ID do Roteador que originou o LSA.

V (Virtual Link): Se marcado como 1 , o Roteador que originou o LSA é um "endpoint" do Virtual Link.

E (External): Se marcado com o valor 1, o Roteador que originou o LSA é um ASBR.

B (Border): Se marcado com o valor 1, o Roteador que originou o LSA é um ABR.

Number of links: Inclui o numero de links descrito no LSA.

Link ID: Descreve o tipo de conexão que do Link; é dependente do Link Type.

Link Data: Baseando-se no campo Link ID indica o “objeto” no qual o link está conectado. O valor 1 indica o Router ID do Roteador vizinho, o valor 2 refere-se ao endereço IP da Interface do Roteador Designado, o valor 3 ao endereço de rede e o 4 o Router ID.

Type: O valor 1 indica uma conexão ponto a ponto com outro Roteador, o valor 2 refere-se uma rede de transito, o valor 3 indicar a conexão com uma rede Stub e 4 a um virtual link. O indicativo do valor 3 refere-se a links declarados no OSPF que não possuem adjacência com outros Roteadores, como por exemplo, uma interface Loopback ( os materiais didáticos alertam para não confundirmos o Link ID com o valor 3 com Area Stub).

Type            Descrição                           Link ID                     Link Data

1          Point-to-point numbered       ID do vizinho              Endereço IP do Link

1          Point-to-point unnumbered   ID do vizinho              MIBII If index value

2          Trânsito                                 Endereço IP do DR   Endereço IP do Link 

3          Stub                                        Endereço de Rede   Máscara

4          Virtual Link                              ID do vizinho            Endereço IP do Link 

#TOS: Especifica o numero TOS identificado para o Link.(Não mais suportado na RFC 2328)

Metric: Custo de uma interface.

TOS: Especifica o tipo de serviço que a métrica se refere.

TOS metric: Métrica especifica para informação do tipo de serviço.

CABEÇALHO DO PACOTE OSPF

Todo pacote OSPF inicia com um cabeçalho de 24 bytes. Esse cabeçalho contem todas as informações necessárias para determinar se o pacote deve ser aceito para futuras operações. O pacote tem a seguinte estrutura:

 - Version - O número da versão do protocolo OSPF.

 - Type - O tipo do pacote OSPF.

                            Tipo        Descrição

                       ________________________________

                      1      Hello

                      2      Database Description

                      3      Link State Request

                      4      Link State Update

                      5      Link State Acknowledgment

Packet length - O tamanho do pacote em bytes. O tamanho inclui também o cabeçalho.

Router ID - O identificador do roteador que enviou o pacote.

Area ID - Um número de 32 bits que indica a área a qual o pacote pertence. Todo pacote é associado a uma única área.

Checksum - O checksum do pacote completo, incluindo o cabeçalho, mas excluindo os 64 bits de autenticação.

AuType - Indica o esquema de autenticação a ser usado no pacote.

Authentication - Um campo de 64 bits usado para informar o esquema de autenticação a ser utilizado.

OSPF – Área única

OSPF – Multiárea

Consiste de áreas;

Diminui as tabelas de roteamento e de topologia;

Consome menos memória e ciclos de processamento;

Necessário projeto hierárquico.

OSPF – Multiárea componentes

OSPF – Tipos de roteadores

TIPOS DE LSA

 - Routerlink LSA (Type1)

Cada roteador gera uma entrada para cada área à qual ele pertence;

Ela descreve os estados de enlace do roteador com a área;

A difusão (flood) ocorre somente dentro de uma determinada área;

O status do enlace e o custo são dois dos descritores conhecidos.

 - Network link LSA (Type2)

Gerada pelos DRs nas redes multiacesso;

Lista de todos os roteadores

Ela descreve o conjunto de roteadores que estão conectados a uma determinada rede;

O flood ocorre apenas dentro da área que contém a rede.

 LSA tipo 1 e 2 são anunciados dentro da mesma área

 - Network summarylink LSA (Type3)

Originada pelos ABRs.

Descreve os enlaces entre o ABR e os roteadores internos de uma rede local.

Essas entradas fazem o flood através da área de backbone até os outros ABRs.;

Os LSAs do tipo 3 descrevem as rotas para as redes que estão dentro da rede local e são enviadas para área backbone

Quando acontece sumarização no OSPF o anuncio é feito através dos LSAsdo tipo 3 e 4;

Os tipos 3 e 4 também são conhecidos por anunciarem rotas do tipo INTER-ÁREA

LSA 4 ASBR Anunciar a ASBR em uma área.

TIPOS DE ÁREAS

 - Área padrão - também conhecida como área normal ou ordinária, conforme discutido na aula de OSPF área simples. Ela aceita anúncios da área interna, resumos de rotas (intra-área) e rotas externas.

 - Área de Backbone - é a área central à qual todas as outras áreas se conectam, através do ABR ou ASBR;

     - A área de backbone tem sempre a identificação zero;

     - Todas as outras áreas DEVEM se conectar nela para trocar informações de roteamento.

 - Área Stub - este tipo de área não aceita as informações sobre as rotas externas. Se os roteadores precisarem rotar para redes externas, eles deverão usar uma rota padrão, anunciada pelo ABR.

 - Área Totally Stubby - este tipo de área não aceita rotas externas ou resumo de rotas (internas);

     - Solução proprietária da Cisco;

     - Apenas rota default.

 - Área Not-So-Stubby - uma área que exporta um número limitado de rotas externas. O número de rotas se limita apenas às rotas requeridas para fornecer a conectividade entre áreas;

LINK VIRTUAL

 - O OSPF determina que todas as área outras áreas se conectem a área 0;

 - Em algumas situações, porém, uma nova área é incluída após a interconexão da rede OSPF e não é possível fornecer acesso à área de backbone para ela.

 - Neste caso, deve-se criar um link virtual para fornecer conectividade com a área 0;

 - O link virtual, como o nome já denota, estabelece um enlace lógico entre uma área distante com a área zero;

 - Quando se usa links virtuais, exige-se um processamento especial durante o cálculo do SPF;

 - Não muito recomendado o uso de links virtuais.

 - Tr.

 - Tv.

 - Tt.

 - Lsa 4 - anuncia sua presença tem que mandar e envia.

 - LSA 5 - originada pelo ASBR inunda todo o AS sistema.

 - LSA 7 - inunda todos os AS. Escreve a rota padrão em todos os AS.

 - No so stub - de LSA 7 para LSA 5 quando vai comunicar com a área 0.