Routing. Planeamento Montagem e Manutenção de Redes e Equipamentos Informáticos 2 Organização do capítulo Introdução Características e métodos de routing

Routing

Planeamento Montagem e Manutenção de Redes e Equipamentos Informáticos 2

Organização do capítulo

Introdução

Características e métodos de routing

Protocolos de routing internos – RIP, RIP-2, EIGRP e OSPF

Comparação dos protocolos de routing interno


Encaminhamento (Routing) Para encaminhar os pacotes até ao destino, em cada ponto de

interligação de circuitos, um equipamento especial (chamado router nas redes datagrama ou switch nas redes baseadas em circuitos virtuais) toma a decisão sobre qual o próximo circuito pelo qual o pacote deve ser enviado (“next hop”).

Routing é o conjunto de processos (algoritmos e protocolos) usados para decidir qual o next hop, isto é, para tomar a decisão de encaminhamento.

Só é necessário usar routing quando o pacote tem de atravessar diversos circuitos. Em redes baseadas em tecnologias de broadcasting, LANs de pequena dimensão ou WANs baseadas em satélite, não é necessário usar nenhuma política de routing.

Em redes locais mesmo de média dimensão, é possível através de técnicas de aprendizagem ao nível data-link (bridges) dispensar routing, dado que as bridges descobrem dinamicamente os diferentes endereços data-link por detrás de cada interface. Estas técnicas baseiam-se também em broadcasting e na funcionalidade de filtragem ao nível das interfaces ethernet.


Aspectos envolvidos no encaminhamento

Tomar a decisão Pacote a pacote nas redes baseadas em datagramas No momento da abertura do circuito nas redes baseadas em VCs

Actualizar as informações em que se baseia a decisão Lenta ou raramente – routing estático Periodicamente e sempre que se produzem alterações – routing

dinâmico

Quem toma a decisão ? O emissor – source routing ou routing pela origem O conjunto dos routers – situação mais comum

Critérios de decisão Baseados na necessidade de optimizar o rendimento da rede segundo

critérios de custo, velocidade, tempo de trânsito, etc. Baseados em critérios administrativos – policy routing ou baseado na

origem do pacote


Routing IP – redes directamente ligadas

configure!hostname R1!interface ethernet0ip address 10.1.2.254 255.255.255.0!interface ethernet1ip address 10.1.3.254 255.255.255.0!interface ethernet2ip address 10.1.4.254 255.255.255.0!Este tipo de informações permite aosrouters configurarem a parte estática darespectiva tabela de routing (show ip

route permite conhecer a tabela de routing)


Routing estático!hostname R1!ip route 10.1.5.0 255.255.255.0

10.1.3.253!!Este tipo de configuração usa-se

sobretudo para indicar rotas por defeito, isto é,quando não há alternativas:

ip route 0.0.0.0 0.0.0.0 ethernet2


Routing no caso geral

A rede pode ser vista como um grafo: Os nós são os routers Os links são os arcos Etiqueta ou custo de um arco:

tempo, $, carga, velocidade de transmissão.

Em geral usa-se uma função genérica, dita função custo ou métrica de routing

Caminho “bom”:

Tipicamente é o que minimiza a função custo

Essa função pode depender de um ou mais parâmetros


Routing em redes IP

Os algoritmos usados para fazer routing unicasting numa rede IP agrupam-se geralmente em duas filosofias:

Algoritmos “distance-vector” (RIP, IGRP, ...): O router conhece apenas os vizinhos e o custo para os alcançar Um processo iterativo de computação com troca de informação

com os vizinhos permite construir uma tabela de routing e fazê-la evoluir dinamicamente

Algoritmos “link-state” (OSPF, IS-IS, ...): Para divulgar o estado de todos os links a todos os routers

utiliza-se uma técnica de “flooding” Todos os routers conhecem a totalidade da topologia da rede e

usam essa informação para construir uma tabela de routing


Routing com RIP

!hostname Rn!interface ethernet0ip address 172.16.1.1 255.255.255.0 interface ethernet1ip address 192.168.1.1 255.255.255.0interface serial0ip address 172.16.250.1 255.255.255.0Interface serial1ip address 172.16.251.1 255.255.255.0....router ripnetwork 172.16.0.0!

Como repercussão do comando “router rip Network 172.16.0.0” o router Rn passa a enviar anúncios com sub-redes de 172.16 e a aceitar anúncios com sub-redes172.16. No entanto não envia anúncios com 192.168.1.0 nem aceita anúncios via aquela interface.


Funcionamento do RIP

Cada router envia periodicamente aos vizinhos a lista das redes que conhece e a que distância (a métrica do caminho). Cada router, através destas informações, deduz qual o melhor caminho para chegar a cada rede.


Anúncio RIP


Algoritmo “Distance-vector” ou Bellman-Ford

Sempre que recebe um anúncio, um router realiza as seguintes operações:

1. Se desconhece a rede, instala-a na tabela de routing com o endereço do emissor à distância anunciada mais um (excepto se a distância anunciada for 16).

2. Se conhece a rede mas o anúncio revela um melhor caminho, faz uma actualização da tabela de routing, senão ignora o anúncio.

3. Se conhece a rede e o anúncio vem do router já escolhido pela sua tabela de routing corrente, mas o anúncio revela um incremento da métrica, actualiza a tabela de routing de acordo com a nova métrica. Se esta for 16 coloca a rede em hold-down state.

4. Se conhece a rede mas o anúncio revela um novo caminho com o mesmo custo que o que conhece, faz uma actualização da tabela de routing, de forma a dispor de mais do que um caminho equivalente (implementação específica Cisco). Estes caminhos múltiplos permitem fazer balanceamento de carga (load balancing).


Balanceamento de carga

Process switching:Cada pacote faz alternar a escolha do caminho (round-

robin), isto é, a distribuição é feita pacote a pacote.

interface serial0ip no route-cache

Fast switching:Para cada destino é seleccionado um caminho e todos

os pacotes para o mesmo destino usam esse caminho.

interface serial0ip route-cache


Temporizadores RIP

Um router RIP transmite updates todo os 30 segundos e usa vários timers para gerir o seu comportamento:

1. Update timer. Controla a emissão periódica de anúncios, tipicamente de 30 em 30 segundos.

2. Invalid timer. Sempre que um anúncio de uma rota é recebido este timer éinicializado a 180 segundos. Se expira, a rota fica no estado suspeito mascontinua a ser utilizada.

3. Hold-down timer – 180 segundos. Se uma rota entrou no estado suspeito,deixam de se processar anúncios sobre a mesma até este timer expirar. Se umanúncio é recebido com a métrica de 16 a rede entra imediatamente nesteestado.

4. Flush timer. Sempre que um anúncio de uma rota é recebido este timer éinicializado a 240 segundos. Se expira, a rota é retirada da tabela de routingseja qual for o estado em que estiver. O próximo anúncio sobre esta rota seráentão tomado em consideração.


Convergência

Quando existe uma alteração no estado de um link, chama-se tempo de convergência ao período de tempo necessário para que essa alteração seja tomada em consideração por todos os routers.

Um bom algoritmo garante um tempo de convergência curto.

Os algoritmos “distance-vector” têm um problema delicado designado por “good news travel fast, bad news travel slowly”. Esta anomalia chama-se “contagem para o infinito”.


Bad news travel slowly

Caso a ligação do Router 1 à rede172.16.100.0 vá abaixo, o Router 1 receberia do Router 2 um anúncio sobre a rede 172.16.100.0 que o Router 2 conhecia como sendo acessível via o Router 1 !

O Router 2 receberia depois um anúncio do Router 1 sobre a rede e assim sucessivamente, aumentando o custo da rota de uma unidade em cada ciclo.

Este processo só pararia quando um dos routers concluísse que a rede não é acessível pois o custo é infinito.


Aceleração da convergência

Split horizon - Um router não anuncia por uma interface aquilo que aprendeu pela mesma. Apesar de este método garantir que ao fim de um certo tempo o Router 2 “esquece” a rota para a rede 172.16.100.0, a convergência ainda seria relativamente lenta.

Poison reverse ou anúncios de unreachability -Quando um router detecta que uma sua interface foi abaixo ou que uma rota que conhecia passou a ter o custo 16, no próximo anúncio envia um anúncio das rotas que conhecia via a mesma interface com métrica 16 (infinito de acordo com RIP).


As rotas RIP têm sempre um custo em termos do número de hops. Um link a 100 Mbps e um link a 128 Kbps têm o mesmo custo.

Para compensar esta deficiência o administrador da rede pode aumentar ou diminuir a métrica do anúncio de uma rede “manualmente” através do comando:

offset-list {access-list} { in | out } offset [type number]

router ripnetwork 172.16.0.0offset-list 20 in 2 serial1...access-list 20 permit 172.16.1.0 0.0.0.0

Este comando adicionaria um custo de 2 a todos os anúncios recebidos via a interface serial1 que fossem sub-redes de 172.16.1.0

Manipulação manual dos custos


Esta nova versão de RIP suporta várias extensões muito úteis.

Subnet Masks e Classless routing (CIDR). Cada anúncio de uma rede leva a máscara o que permite contornar os problemas encontrados neste contexto com RIP-1 (Variable lenght Subnet Masks)

Autenticação. Cada anúncio pode conter dados de autenticação do emissor do mesmo.

Next hop IP address e route tag. São funcionalidades que interessam quando os anúncios RIP são injectados noutro protocolo de routing.

Os dados suplementares associados a cada anúncio são colocados nos campos livres no pacote RIP-1. O primeiro e o último anúncio podem ser substituídos por informação de autenticação.

O destino de um anúncio pode ser 255.255.255.255 ou 224.0.0.9 um endereço multicast reservado para evitar que os hosts não interessados tenham de ouvir os anúncios RIP.

RIP-2


Protocolo(s) proprietário(s) da CISCO, sucessor(es) do RIP Tal como o RIP são protocolos Distance-vector Calcula o custo de um link através de uma métrica

complexa (delay, bandwidth, reliability, load, etc.) Propaga os anúncios de forma fiável. Só envia anúncios

caso haja alterações da tabela do router e usa autenticação para evitar ataques explícitos ou por inadvertência.

Tem um algoritmo especial com suporte de “loop-free routing” para propagar rapidamente os route updates. Esse algoritmo é chamado DUAL (Distributed Updating Algorithm) e é baseado numa técnica especial chamada diffused computation

[E]IGRP ([Extended] Interior Gateway Routing Protocol)


“Open” - significa normalizado – RFC 2328 Usa um algoritmo Link State

Baseado na disseminação do estado dos links através de anúncios de estado dos links enviados por cada router

Cada router adquire a topologia da rede Cada router calcula as rotas usando o algoritmo de Dijkstra

Cada anúncio OSPF contem uma entrada por link Os anúncios são enviados a todos os routers por

flooding Para escalar necessita de ser organizado em

zonas Escala mais que o RIP mas não é simples nem

leve para os routers ou os administradores da rede

OSPF (Open Shortest Path First)


Os protocolos link-state baseiam-se na seguinte aproximação:

1. Cada router tem uma base de dados com o estado de cada link da rede e uma tabela de routing

2. Periodicamente, e sempre que há uma alteração, são difundidos por flooding pacotes indicando o estado dos links; desta forma todos os routers convergem para uma cópia idêntica da base de dados de links

3. Quando há alterações da base de dados, são calculados os melhores caminhos para cada destino através do algoritmo “Shortes Path First” de Dijkstra; a partir deste calculo é produzida uma nova versão da tabela de routing.

Funcionamento dos protocolos link-state


Ao receber um pacote com um link state, o router analisa o número de sequência:

1. Se o link não está na base de dados, insere-o e difunde a mensagem aos vizinhos

2. Senão, se o nº de sequência na base de dados é inferior, considera o novo estado do link e o novo número de sequência e difunde o pacote aos vizinhos

3. Senão, se o número de sequência na base de dados é superior, transmite o record que está na base de dados ao emissor do pacote de link state

4. Senão, se os dois números de sequência são iguais, ignora o pacote

Os pacotes de link state são acknowledged e retransmitidos para tornar a difusão fiável e incluem mecanismos de autenticação e verificação para evitar a corrupção acidental da base de dados de links dos routers.

O estado dos links é analisado pelos routers através de um protocolo do tipo “hello” que permite avaliar o estado dos links e descobrir vizinhos. Sempre que o estado de um link muda, assim como periodicamente (por exemplo de 30 em 30 minutos), é emitido um novo pacote de link state.

Os links ficam na base de dados enquanto forem refrescados. Se não o forem, são retirados (após várias horas).

O mecanismo de flooding acima detalhado permite a um router recém rebootado saber qual o último número de sequência que usou antes de ir abaixo (se rebootar suficientemente depressa).

Flooding dos pacotes de link-state


Custos OSPF por defeito (Cisco)


A link state database dos routers de uma área baseia-se nos custos dos links os quais são indicados numa escala inteira de 1 a 65535.

Só há necessidade de recalcular os melhores caminhos pelo algoritmo de Dijkstra se estes custos mudarem, isto é, se o link for abaixo ou o administrador mudar o custo de uma interface.

O algoritmo não escala se a dimensão da link state database aumentar, por isso a rede é particionada em várias áreas. Um router só calcula os melhores caminhos para a(s) área(s) a que pertence.

Link State Database


OSPF Hierárquico e áreas OSPF


Hierarquia a dois níveis: local area, backbone. Os anúncios de link-state são geralmente propagados dentro da mesma

área. Cada router tem uma visão detalhada da área. No entanto, no que toca

às outras áreas, tem apenas uma visão limitada – só conhece o custo do shortest path e a lista de redes das outras áreas, não conhece os links.

Area border routers: elaboram “sumários” com a lista das redes da sua área e as distâncias para as mesmas e anunciam-nas para as outras áreas.

Backbone routers: executam o processo de routing OSPF dentro do backbone.

Boundary routers: ligam para o exterior da rede (outros ASs).

O OSPF hierárquico incorpora assim anúncios de link state que dizem respeito a acessibilidade de redes e não só ao estado dos links.

Caracterização do OSPF Hierárquico


Comparação


A Internet global está organizada em Sistemas Autónomos (Autonomous Systems - AS). Um sistema autónomo é um conjunto de routers sob a mesma autoridade administrativa. Existem ASs de vários tipos: Multihomed AS: uma grande instituição (sem trânsito entre

ASs) Transit AS: um operador (ISP) Stub AS: uma pequena instituição (ligado a um único AS)

Routing a dois níveis: Intra-AS: o administrador é responsável pela escolha dos

protocolos Inter-AS: trata-se de uma norma única (sem alternativas)

Routing na Internet global


Hierarquia de ASs na Internet


Protocolos também conhecidos como Interior Gateway Protocols (IGP)

Os mais conhecidos IGPs são os seguintes: RIP: Routing Information Protocol OSPF: Open Shortest Path First [E]IGRP: Interior Gateway Routing Protocol (protocolos

proprietários da Cisco)

Intra-AS Routing


Inter-AS routing: BGP4 ou BGP simplesmente


Que cada AS possa: 1. Obter a informação sobre as redes alcançáveis via

cada um dos seus vizinhos 2. Propagar essa informação para o interior do seu

domínio de encaminhamento 3. Determinar “bons” caminhos para as diferentes redes

com base na acessibilidade e em políticas.

Que cada prefixo (do AS) possa ser anunciado para a Internet

O protocolo BGP(Border Gateway Protocol) é usado para


BGP (Border Gateway Protocol): trata-se do único protocolo que pode ser usado na Internet para encaminhamento externo

O protocolo BGP é um protocolo baseado em vectores de caminhos: do tipo dos protocolos vector de custos ou distâncias mas em que cada Border Gateway difunde para os seus vizinhos (peers) o caminho

completo (Entire path, isto é uma sequência de ASs) até cada prefixo de redede destino

por exemplo o Border Gateway X pode enviar o seu caminho para o destino Z na forma da lista de ASs:

Caminho (X,Z) = AS1,AS2,AS3,…

Caracterização do BGP

Documents

Routing. Planeamento Montagem e Manutenção de Redes e Equipamentos Informáticos 2 Organização do capítulo Introdução Características e métodos de routing