Algoritmos e Protocolos

de Encaminhamento

FEUP/DEEC
Redes de Banda Larga
MIEEC – 2009/10
José Ruela
Encaminhamento vs. comutação
• Encaminhamento (routing)
– Descobrir e seleccionar rotas numa rede (ou num conjunto de redes
interligadas) com o objectivo de construir tabelas de encaminhamento
nos nós
– Operação global – envolve os nós da rede
– Requer algoritmos e protocolos de encaminhamento

• Comutação (switching / forwarding)

– Transferir pacotes entre interfaces de entrada e saída
– Operação local – envolve apenas um nó (router ou comutador)
– A tabela que controla a operação de comutação (switching / forwarding
table) num router é determinada pelo conteúdo da respectiva tabela de
encaminhamento (routing table)
Sistemas Autónomos (Autonomous Systems)
• A Internet está actualmente organizada (é vista) como uma colecção de Sistemas
Autónomos (AS – Autonomous Systems)
• Definição clássica de AS – conjunto de routers e redes sob uma única administração
técnica, que usam um protocolo interior (IGP – Interior Gateway Protocol) e métricas
comuns para encaminhar pacotes no AS e um protocolo exterior (Exterior Gateway
Protocol) para encaminhar pacotes para outros ASs
– Tornou-se no entanto comum o uso num único AS de vários IGPs e mesmo várias métricas
• O uso actual do termo (definido no RFC 1930) põe a tónica no modo como um AS é
visto por outros ASs
– Um AS deve ter internamente um plano coerente de encaminhamento
– Um AS deve apresentar uma visão consistente das redes alcançáveis através do próprio AS
• Segundo o RFC 1930 “Guidelines for creation, selection, and registration of an
Autonomous System (AS)”, um AS é um grupo de um ou mais prefixos IP suportados
por um ou mais operadores de rede, e que tem uma única política de encaminhamento
(routing policy) claramente definida
– Uma política de encaminhamento refere-se à forma como as decisões de encaminhamento
são tomadas actualmente na Internet
– A troca de informação de encaminhamento entre Sistemas Autónomos está sujeita a
políticas de encaminhamento
Sistemas Autónomos (Autonomous Systems)
Internet service provider

Border routers

Border routers
Autonomous
Interdomain level
system or
domain

LAN level
Intradomain level
Encaminhamento intra e inter domínios
• Encaminhamento intra domínio (intra domain routing)
– Interior Gateway Protocols (IGP) – encaminhamento num AS
• RIP (Routing Information Protocol) – protocolo do tipo “vector de
distâncias” (distance vector)
• OSPF (Open Shortest Path First) – protocolo do tipo “estado de ligações”
(link state)
• Encaminhamento inter domínios (inter domain routing)
– Exterior Gateway Protocols (EGP) – encaminhamento entre ASs
• BGP-4 (Border Gateway Protocol version 4) – protocolo do tipo “vector de
percursos” (path vector)

• Um router pode executar um ou mais IGPs mas apenas um EGP

– Um EGP é executado por routers de fronteira (border router ou border
gateway)
Encaminhamento intra e inter domínios

IGP
R EGP IGP
R R
R
R
R
AS A AS C
EGP

R
R
IGP
AS B
Encaminhamento em redes em malha
• Numa rede com topologia em malha existem percursos alternativos entre um
qualquer par de nós (em particular entre pares de nós periféricos que dão
acesso a equipamentos terminais ou asseguram a ligação a outras redes)
• Na topologia representada, e como exemplo, existem várias rotas possíveis
(isentas de ciclos) entre 1 e 6:
– Estão representadas três, entre outras possíveis: 1-3-6, 1-4-5-6, 1-2-5-6

1 3
6

Nó (comutador
ou router)
4

2
5
Selecção de rotas
• Numa rede em malha coloca-se a questão de seleccionar as “melhores”
rotas, mas para tal é necessário definir um critério que pode basear-se numa
métrica ou numa combinação de métricas
– Menor atraso, maior débito, maior capacidade, menor custo, menor distância,
maior fiabilidade
• A atribuição de pesos às ligações entre nós directamente ligados (de acordo
com o critério adoptado) permite associar um “custo” (em sentido lato) às
rotas possíveis na rede, podendo então definir-se, como objectivo, encontrar
as rotas de menor “custo” (na acepção da métrica utilizada)
• A adopção de um critério de “distância”, no sentido estrito de “número de
saltos” (hops) traduz-se na atribuição de pesos unitários às ligações entre
nós e neste caso o “custo” de uma rota é o número de hops (hop count) e a
rota de menor “custo” é a que tiver o menor número de hops, isto é, a mais
curta (shortest path)
– Em sentido lato a designação shortest path pode ser usada para designar a rota
de menor “custo” (na acepção da métrica utilizada) e as expressões “menor
custo” e “menor distância” serão usadas com idêntico significado
Criação de tabelas de encaminhamento
• É necessário conhecer informação sobre o estado de cada ligação
– Activa ou inactiva
– Carga (nível de utilização e possível estado de congestionamento)
– Atraso (ou outras métricas)
• É necessário trocar informação entre nós (com base num protocolo)
– Qual o tipo de informação a trocar e significado – e.g., local ou global
– Qual a regularidade da troca – e.g., de forma periódica (e qual a
periodicidade), quando ocorrerem alterações ou em resposta a pedidos
– Quais os nós com os quais a informação é trocada – e.g., apenas com
os vizinhos ou com todos os nós da rede
• A informação trocada entre nós permite calcular rotas (e assim criar
as tabelas de encaminhamento)
– O cálculo de rotas pode basear-se numa métrica ou numa combinação
de métricas e pode produzir uma única rota ou rotas alternativas (com
uma ordem de preferência)
Requisitos de algoritmos de encaminhamento
Os algoritmos de encaminhamento devem ter um conjunto de propriedades
que lhes permitam operar em condições adversas e ambientes dinâmicos,
caracterizados por frequentes alterações topológicas (adição, remoção ou
indisponibilidade temporária com posterior reposição de nós e/ou ligações)
ou do estado de carga das ligações (risco de congestionamento)
• Capacidade de resposta a mudanças
– Devem permitir convergência rápida no cálculo de novas rotas e garantir
operação estável (sem oscilações), o que exige que a informação mantida nos
nós seja coerente e consistente
– Devem evitar ciclos (loops) persistentes
• Robustez
– Devem ser capazes de operar em condições adversas – carga elevada ou mesmo
congestionamento, interrupções (temporárias ou persistentes), avarias de
equipamentos, implementações deficientes ou incorrectas
• Optimalidade
– Devem garantir utilização eficiente de recursos (distribuição equilibrada da
carga na rede) e minimização do “custo” das rotas (ou seja, dos recursos
envolvidos)
• Simplicidade
– Devem permitir implementações eficientes (em software) com consumo
reduzido de recursos de processamento
Algoritmos centralizados vs. distribuídos
• Algoritmos centralizados
– As rotas são calculadas por um nó central
– Toda a informação de estado exigida pelo algoritmo é enviada para o nó
central, que divulga (anuncia) as rotas (tabelas de encaminhamento) pelos
restantes nós
• Aumenta o tráfego de e para o nó central, bem como a respectiva carga de
processamento
• O nó central é um ponto único de falha (soluções redundantes obrigam a
replicar informação e manter coerente a informação replicada)
– Têm dificuldade de adaptação a alterações topológicas frequentes
– Não são escaláveis
• Algoritmos distribuídos
– As rotas são calculadas pelos nós com base num algoritmo distribuído
(cada nó constrói a sua tabela de encaminhamento)
– A informação de estado é trocada entre nós
– Adaptam-se facilmente a mudanças (topológicas ou outras)
– São mais facilmente escaláveis
Encaminhamento estático vs. dinâmico
• Encaminhamento estático
– As tabelas de encaminhamento são configuradas “manualmente” (por
procedimentos administrativos, após computação prévia)
• São fixas – não são alteradas a não ser por reconfiguração (o que, em
princípio, não deve ocorrer com frequência)
– É aceitável quando a natureza do tráfego é previsível e a rede é simples
(pequeno número de nós e topologia pouco sujeita a alterações)
– Pode ser usado para forçar a substituição de algumas rotas estabelecidas
por um algoritmo dinâmico
• Usado como técnica de Engenharia de Tráfego (e.g., MPLS)
– Pode ser usado para estabelecer uma rota para um router por omissão
(default) como complemento de rotas obtidas por um algoritmo dinâmico
• Encaminhamento dinâmico
– Adapta-se a alterações das condições de operação da rede
– O processo pode ser automatizado
– Calcula rotas com base em informação actualizada do estado da rede,
trocada entre nós
Encaminhamento de Circuitos Virtuais
• As rotas são determinadas durante o estabelecimento do circuito virtual (e
mantêm-se fixas por circuito virtual enquanto este estiver activo)
• As entradas das tabelas de comutação (switching tables) associadas em cada
nó a um circuito virtual permitem reconstituir a rota a seguir pelos pacotes
correspondentes (com base em identificadores de circuito virtual ao longo do
percurso)

2
1 7 8
1 3 B
A 3
5 1 6 5
4 2
VCI
host 4

3 5 switch / router
2
C 5
6
2 D
Tabelas de comutação de circuitos virtuais
Nó 3
Entrada Saída
Nó 1 Nó VCI Nó VCI Nó 6
Entrada Saída 1 2 6 7 Entrada Saída
Nó VCI Nó VCI 1 3 4 4 Nó VCI Nó VCI
A 1 3 2 4 2 6 1 3 7 B 8
A 5 3 3 6 7 1 2 3 1 B 5
3 2 A 1 6 1 4 2 B 5 3 1
3 3 A 5 4 4 1 3 B 8 3 7

Nó 4
Entrada Saída
Nó VCI Nó VCI
Nó 2 2 3 3 2 Nó 5
3 4 5 5
Entrada Saída 3 2 2 3 Entrada Saída
Nó VCI Nó VCI Nó VCI Nó VCI
5 5 3 4
C 6 4 3 4 5 D 2
4 3 C 6 D 2 4 5

• Exemplo: Circuito Virtual estabelecido entre A (ligado ao nó 1, VCI = 5) e D

(ligado ao nó 5, VCI = 2)
Encaminhamento de Datagramas
• Na forma clássica de comutação de datagramas, os pacotes (datagramas)
são encaminhados pela rede de forma independente, podendo
eventualmente usar percursos diferentes (o “melhor” no momento)
• A decisão em cada nó é igualmente tomada de forma independente,
embora as decisões dos nós devam ser coerentes e consistentes (o que
deve ser assegurado pelos algoritmos e protocolos de encaminhamento)
– Deste ponto de vista trata-se de encaminhamento passo a passo (hop by
hop routing)
• As decisões de encaminhamento num nó são tomadas tendo em atenção
o endereço de destino transportado em cada pacote e o conteúdo da
tabela de encaminhamento do nó
– Trata-se de encaminhamento baseado no destino (destination based
routing)
Tabelas de comutação de datagramas
Nó 3
Nó 1 Destino Nó seguinte Nó 6

Destino Nó seguinte 1 1 Destino Nó seguinte

2 2 2 4 1 3
3 3 4 4 2 5
4 4 5 6 3 3
6 6 4 3
5 2
6 3 5 5

Nó 4
Destino Nó seguinte
1 1
Nó 2 2 2
Nó 5
3 3
Destino Nó seguinte Destino Nó seguinte
5 5
1 1 6 3 1 4
3 1 2 2
4 4 3 4
5 4 4 4
6 5 6 6
Endereçamento não hierárquico e encaminhamento

0000 0001
0111 0100
1010 1 4 1011
1101 1110
3
R1 R2
2 5
0011 0011
0110 0000 1 0001 4 0101
1001 0111 1 0100 4 1000
1100 1010 1 1011 4 1111
… … … …

• Não existe qualquer relação entre endereços e proximidade geográfica do ponto

de vista de encaminhamento, o que impede a agregação de prefixos / rotas
• No exemplo, cada tabela de encaminhamento requer 16 entradas, uma por cada
rede representada
Endereçamento hierárquico e encaminhamento

0000 0100
0001 0101
0010 1 4 0110
0011 0111
3
R1 R2
2 5
1000 1100
1001 00 1 00 3 1101
1010 01 3 01 4 1110
1011 10 2 10 3 1111
11 3 11 5

• O endereçamento hierárquico permite a agregação de prefixos / rotas e

portanto uma divulgação eficiente de informação de encaminhamento
• Cada tabela de encaminhamento requer 4 entradas (no exemplo)
Encaminhamento plano vs. hierárquico
• Plano (flat)
– Todos os routers estão no mesmo nível (peers entre si)
– Solução não escalável

• Hierárquico
– O sistema global é dividido em Sistemas Autónomos (Autonomous
Systems), áreas, etc.
• Alguns routers fazem parte do backbone de encaminhamento
• Alguns routers apenas comunicam numa área
– É eficiente uma vez que este modelo tem correspondência com padrões
de tráfego típicos (do ponto de vista da localização relativa das fontes e
destinos de tráfego)
– Solução escalável
Algoritmos especiais de encaminhamento
• Flooding
– A rede é inundada com cópias do mesmo pacote
– Pode ser útil no arranque da rede
– Permite distribuir (propagar) informação para todos os nós

• Deflection Routing
– Baseado num procedimento predefinido (que pode dar origem a
percursos diferentes)
– Não há cálculo de rotas por parte dos nós

• Source routing
– O percurso para um destino é determinado pelo nó de origem e incluído
no cabeçalho dos pacotes
– Os routers no percurso limitam-se a despachar os pacotes de acordo com
o prescrito no respectivo cabeçalho
Flooding
• O algoritmo de flooding envia cópias de um pacote para todos os nós da rede
– Embora possa ser usado para garantir a entrega de pacotes num nó de destino
alvo, esta aplicação do algoritmo é pouco interessante
– Pode ser usado quando um nó pretende enviar pacotes para todos os nós da rede
• Uma aplicação possível é a de difundir (propagar) informação de estado de um nó para
todos os outros (por exemplo, em algoritmos de encaminhamento do tipo link state)
• Realização
– O método não requer a existência de tabelas de encaminhamento nos nós
• Um nó difunde (replica) cada pacote em todas as portas excepto naquela em que o
pacote foi recebido
• Problema
– O número de pacotes em trânsito na rede cresce exponencialmente
• Um nó recebe por vias diferentes cópias de um mesmo pacote original e a respectiva
difusão multiplica o número de pacotes que inundam a rede
– É necessário um mecanismo que limite ou controle esse crescimento
• Torna-se desnecessário que um nó propague novamente cópias de um pacote que o
tenha visitado anteriormente
 Flooding – exemplo (três passos)
1 3
6
2
1 4
1 3
6
2
5
4

2
1 3 5
6

3
4

2
5
Flooding limitado
É possível usar várias técnicas para controlar o número de cópias do
mesmo pacote em trânsito na rede – referem-se a seguir três exemplos

• A utilização do campo TTL (Time To Live) em cada pacote permite

limitar o alcance (número de nós visitados) pelo pacote – mas não
impede que uma ou mais cópias de um pacote visitem de novo um nó
e sejam por este novamente difundidas
– O valor do campo TTL pode ser inicialmente configurado com um valor
igual ou ligeiramente superior ao diâmetro da rede (menor número de
hops entre os nós mais afastados)

• Cada nó adiciona um identificador próprio ao pacote, antes de o

difundir, o que permite eliminá-lo numa próxima visita

• O nó de origem inclui um número de sequência em cada pacote e cada

nó visitado pelo pacote regista o endereço e o número de sequência de
origem e descarta duplicados
Deflection Routing
• Proposto inicialmente com a designação hot potato routing
• Os nós tentam despachar os pacotes para uma porta preferida
• Se a porta preferida estiver ocupada, os pacotes são desviados para
outra porta, pelo que não se garante a entrega ordenada de pacotes
• Funciona de forma aceitável em redes com topologias regulares que
ofereçam múltiplos percursos entre cada par origem-destino, como é o
caso de redes do tipo Manhattan
– Estas redes são constituídas por um array rectangular de nós
– Os nós são identificados por um par de índices (i, j)
– As linhas e as colunas representam, respectivamente, “ruas” e “avenidas”
de sentido único, mas alternado
• É possível a operação sem buffers
– Uma aplicação possível é em redes ópticas de pacotes (uma vez que não é
viável actualmente recorrer a buffers totalmente ópticos)
Deflection Routing – rede Manhattan

0,0 0,1 0,2 0,3

1,0 1,1 1,2 1,3

2,0 2,1 2,2 2,3

3,0 3,1 3,2 3,3

Source Routing
• O nó de origem (source) determina o percurso a seguir pelos pacotes para um
dado destino
– Strict – a sequência completa de nós no percurso é inserida no cabeçalho de cada
pacote
– Loose – é apenas especificado um sub-conjunto dos nós no percurso
• Os nós intermédios lêem o endereço do next hop e removem-no do cabeçalho
antes de despacharem o pacote
– Nalguns casos pode ser necessário preservar a informação completa do percurso
(por exemplo, para enviar um pacote do destino para a origem pelo percurso
inverso)
• O nó de origem necessita de aprender e seleccionar o percurso a seguir pelos
pacotes ou aceder a um servidor (route server) para obter o percurso
• O algoritmo de source routing permite controlar os percursos seguidos pelos
pacotes na rede
– Em MPLS é possível estabelecer rotas explícitas (explicit routing), que é uma
variante de source routing – o mecanismo é usado como forma de sinalização
para estabelecer percursos “etiquetados” na rede (label switched paths) e não
para auto-encaminhar pacotes
Source Routing

3,6,B 6,B
1,3,6,B
1 3
B
6
A
4 B
Source host
2 Destination host
5
Rotas de menor custo (shortest path routing)
• Em topologias em malha existem múltiplos percursos possíveis entre
um nó de origem e um nó de destino
• Um algoritmo de encaminhamento tem como objectivo seleccionar
rotas para transferir pacotes entre pares de nós (origem, destino)
– O protocolo associado permite trocar informação entre nós de modo a
criar e actualizar as tabelas de encaminhamento resultantes da execução
do algoritmo
• A associação de um custo ou distância (em sentido lato) a cada ligação
entre dois nós permite formular o problema do encaminhamento como
um problema de escolha do caminho com menor custo (least cost) ou
mais curto (shortest path), expressões que serão usadas com o mesmo
significado
• A maior ou menor adequação de uma rota pode ser avaliada pelo seu
“custo” ou “comprimento” (path length) calculado pela soma dos
custos das ligações que a constituem
– A atribuição de custos pode ser feita com base em diferentes métricas
Métricas
• Número de saltos (hop count) – em primeira aproximação fornece uma medida dos
recursos consumidos para transferir um pacote
• Fiabilidade – depende do grau de disponibilidade das ligações e da respectiva
qualidade, medida por exemplo pelo BER (Bit Error Ratio)
• Atraso – soma dos atrasos ao longo do percurso, que inclui uma componente fixa
(essencialmente o atraso de propagação) e uma componente variável, que depende do
nível de carga em cada ligação, da respectiva capacidade e do tamanho dos pacotes
• Largura de banda – representa a capacidade oferecida pelas ligações ao longo da rota
– A capacidade de uma ligação constitui (à parte os overheads) um limite superior para o
débito (throughput) possível nessa ligação
– A capacidade ao longo de uma rota está limitada pela da ligação com menor capacidade
– Uma ligação entre dois nós pode fazer parte de múltiplas rotas pelo que a respectiva
capacidade é por elas partilhada
– Rotas que incluam ligações de elevada capacidade nem sempre oferecem melhor
desempenho, uma vez que este depende também da carga efectiva das ligações usadas
• Carga – representa o nível de utilização das ligações e influencia, conjuntamente com a
capacidade, o desempenho global (atraso, probabilidade de perda de pacotes, etc.)
• Custo da comunicação – no sentido estrito (custo administrativo ou de operação)
• Podem ainda ser usadas políticas de natureza administrativa
Algoritmos shortest path – princípio geral
Os algoritmos do tipo shortest path baseiam-se no princípio seguinte

• Considerando um nó de destino d e dois nós i e j directamente ligados, se j

fizer parte do percurso de menor custo entre i e d (next hop de i na rota para
d), isso significa que i e j partilham a partir de j o mesmo percurso até d e
então
Di = Cij + Dj
sendo Di e Dj as distâncias (custos) de i e j para d, e Cij o custo da ligação
entre i e j
Cij
i j d
Di Dj

• A consequência deste facto é que os percursos de menor custo de todos os

nós até um nó de destino d formam uma árvore com raiz nesse nó d
Algoritmos shortest path – variantes
• Algoritmos de encaminhamento de menor custo (shortest path) são usados no
mesmo AS (encaminhamento interior) e são basicamente de dois tipos
– Vector de distâncias (distance vector)
– Estado das ligações (link state)
• Distance vector
– Cada router envia para os seus vizinhos uma lista de custos (vector de distâncias)
das rotas de si próprio para todos os restantes nós (valores estimados pelo próprio
router com base nos vectores recebidos dos seus vizinhos)
– O algoritmo determina o melhor nó adjacente (next hop) no percurso para cada
destino
– É usado o algoritmo de Bellman-Ford (distribuído) para cáculo do shortest path

• Link state
– Cada router difunde por todos os restantes nós informação de estado relativa
apenas às ligações com os seus vizinhos
– Os routers obtêm informação topológica completa da rede, com base na qual
podem calcular o shortest path e portanto o next hop para cada destino
– É usado o algoritmo de Dijkstra (centralizado) para cáculo do shortest path
Algoritmos Distance Vector
Algoritmos do tipo distance vector têm as seguintes propriedades

• São distribuídos (descentralizados)

– Um nó recebe informação de um ou mais dos seus vizinhos aos quais
está directamente ligado, actualiza o seu vector de distâncias (custos) de
forma independente de todos os outros nós e distribui o resultado
(vector) para os seus vizinhos

• São iterativos
– O processo inclui uma sucessão de passos até que os cálculos convergem
(excepto em casos excepcionais)

• São assíncronos
– A operação do algoritmo não exige que os nós estejam sincronizados
 Distance Vector – operação
• Cada nó mantém uma tabela de encaminhamento (Destino, Custo, Next Hop)
– A entrada associada a cada nó de destino inclui o next hop no percurso
seleccionado e o respectivo custo estimado
• Cada nó anuncia apenas para os seus vizinhos uma lista (vector) actualizada
com a sua estimativa de custos para todos os destinos (Destino, Custo)
– A distância para si próprio é nula
• A tabela de encaminhamento de um nó é actualizada com base na informação
recebida dos vizinhos
– Uma entrada é eliminada se a respectiva rota não for refrescada durante um
intervalo de tempo determinado
• As listas (vectores de custo) trocadas entre nós são enviadas em duas situações
– Periodicamente (períodos típicos da ordem de alguns segundos)
– Sempre que ocorrer uma mudança e portanto uma actualização (triggered update)
• No cálculo das distâncias um nó tem em conta percursos para cada nó de
destino através dos seus vizinhos, seleccionando o que tiver menor custo
– Para isso usa as estimativas de distâncias (custos) comunicadas pelos seus
vizinhos e os custos das ligações com cada um deles
Distance Vector – selecção do next hop
• Considerando um nó i, três nós adjacentes j, k e l e um nó de destino d, o nó i
calcula a distância mínima para d com base nos custos que conhece para os
nós adjacentes e nas estimativas que estes lhe fornecem sobre as respectivas
distâncias (custos) para d e selecciona como next hop o nó adjacente que lhe
oferece o percurso de menor custo entre os três (e anuncia o valor Di aos nós
adjacentes)
Di = min (Cij + Dj, Cik + Dk, Cil + Dl)

j
Cij Dj
Cik
i k d
Di Dk
Cil
l
Dl
Processamento de um vector de custos
Procedimentos num nó após recepção de um vector de custos

Começar por adicionar ao custo para cada destino anunciado no vector

recebido o custo da ligação para o nó adjacente que enviou a mensagem
(se a métrica for o hop count, adicionar um ao hop count)
Repetir os passos seguintes para cada destino anunciado
Se o destino não constar da tabela de encaminhamento
Adicionar a informação respectiva à tabela
Se não
Se o campo next hop for o mesmo
Substituir a entrada na tabela pela anunciada
Se não
Se o custo calculado com base no anúncio for menor que o da
tabela
Substituir a entrada na tabela pela anunciada
Terminar
Algoritmo de Bellman-Ford
• O algoritmo de Bellman-Ford permite calcular os shortest paths para
um dado nó de destino, sendo por isso a sua utilização adequada a
algoritmos do tipo distance vector

• O algoritmo é executado em paralelo e de forma independente por

todos os nós

• Considerando genericamente um nó de origem i e um nó de destino j,

cada nó i realiza o seguinte cálculo iterativamente até convergir
Dii = 0
Dij = mink (Cik + Dkj) para k ≠ i
(Cik é infinito se não existir ligação entre os nós i e k)

• Depois de feita a actualização, o vector Dij é enviado pelo nó i aos seus

vizinhos
 Algoritmo de Bellman-Ford – exemplo

2 3 • Na figura estão representados

1 1 os custos Cij das ligações entre
5 2
um nó i e um nó j adjacente
4 • No exemplo considera-se como
3 1 3 6 destino o nó 6 e o cálculo das
2 rotas dos outros nós para o nó 6
2 5
4

Iteração Nó 1 Nó 2 Nó 3 Nó 4 Nó 5
• Cada entrada (n, Di) representa o
next hop e o custo corrente estimado Inicial (-1, ) (-1, ) (-1, ) (-1, ) (-1, )
do percurso do nó i para o nó 6
1 (-1, ) (-1, ) (6, 1) (-1, ) (6,2)
• n = - 1 significa que o next hop ainda
não está definido e Di = ∞ significa 2 (3,3) (5,6) (6, 1) (3,3) (6,2)
que, por essa razão, ainda não existe
um custo estimado do percurso do 3 (3,3) (4,4) (6, 1) (3,3) (6,2)
nó i para o nó 6
Algoritmo de Bellman-Ford – shortest paths
2 3
1 1
5 2

4
Topologia com indicação 3 6
1 3
dos custos das ligações
2
2 5
4

2 3
1 1
2
d
4
Árvore de shortest paths 6
com destino d no nó 6 1
2
2 5
Convergência do algoritmo de Bellman-Ford
• Para cada nó de destino e a partir dum estado inicial em que os nós não
têm qualquer informação da distância a esse destino, o algoritmo
propaga informação em passos sucessivos a partir dos nós mais
próximos do destino para os mais afastados
• A árvore de percursos vai-se construindo a partir do destino (raiz)
aplicando directamente as equações de cálculo de distâncias
– Neste caso a convergência é rápida (número de passos igual ao número
máximo de hops até ao destino) – “as boas notícias propagam-se depressa”
• Em condições estáveis não se formam loops
– Se i e j forem adjacentes e o percurso mínimo de i para d passar por j, é
óbvio que o inverso não ocorre
• Esta situação altera-se quando ocorrem interrupções que originam
alterações topológicas e a necessidade de calcular novos percursos com
base na informação que se propaga a partir da zona afectada
Convergência – análise
• Consideremos novamente dois nós adjacentes i e j que partilham o mesmo
percurso a partir de j para um nó de destino d, verificando-se portanto
Di = Cij + Dj
• Se ocorrer uma interrupção na ligação de j ao seu next hop na direcção de d,
o valor de Dj deixa de ser válido, pelo que terá de ser actualizado
• O nó j recorre então à informação veiculada pelo nó i sobre a respectiva
distância (custo) igual a Di, mas
– Esse custo pressupunha um percurso através de j (que agora está comprometido)
– Esse custo baseava-se numa estimativa Dj que deixou de ser válida (ao ponto de
j não poder recorrer a ela)
• Então j vai assumir erradamente um novo custo
D*j = Cji + Di = 2 * Cij + Dj (admitindo Cji = Cij)
– O novo valor de custo é incorrecto, porque se induziu um loop – j assume que i é
o next hop no percurso para d, ao passo que Di foi calculado com base no oposto
(j como next hop de i)
• O algoritmo pode acabar por convergir, mas lentamente – “as más notícias
propagam-se devagar”
• Nalguns casos pode ocorrer um deadlock (referido como count to infinity)
Convergência – alteração topológica
• Para analisar o problema da convergência do algoritmo numa situação
em que a topologia se altera, considera-se o exemplo em que a ligação
entre os nós 3 e 6 é interrompida

• Após o algoritmo ter convergido (iteração 3 na topologia inicial), é

necessário calcular novamente os percursos de cada nó para o nó 6
(apenas o nó 5 não é afectado, como se conclui facilmente)

2 3
1 (1)
5 2

4
3 1 3 6

2
2 5
4
Convergência – formação de loops
• Após a alteração topológica, o processo de actualização é despoletado pelo
nó 3 que, deixando de ter ligação ao nó 6, vai usar a informação anunciada
pelos nós 1 e 4 sobre os custos dos respectivos percursos para o nó 6 – neste
caso são iguais (3), seleccionando (por exemplo) o nó 4 como next hop
• O nó 3 não sabe, no entanto, que o percurso de 4 para 6 anunciado pelo nó 4
passava por si próprio e portanto incluía a ligação que foi interrompida – deste
modo cria-se um loop
• O problema agrava-se a partir do momento em que o nó 3 começa a anunciar o
novo custo do seu percurso para o nó 6, podendo criar-se novos loops
• O algoritmo acaba por estabilizar ao fim de algumas iterações, mas nem sempre
isso acontece

Iteração Nó 1 Nó 2 Nó 3 Nó 4 Nó 5

1 (3,3) (4,4) (4, 5) (3,3) (6,2)

2 (3,7) (4,4) (4, 5) (2,5) (6,2)
3 (3,7) (4,6) (4, 7) (5,5) (6,2)
4 (2,9) (4,6) (4, 7) (5,5) (6,2)
5 (2,9) (4,6) (4, 7) (5,5) (6,2)
Convergência – count to infinity
1 2 3 4 Antes da interrupção
1 1 1

1 2 3 X 4 Depois da interrupção
1 1
• Os nós 2 e 3 pensam que o melhor percurso para 4 é através do outro, o que ocasiona
(devido ao loop criado) incrementos sucessivos de duas unidades dos custos, por cada
par de iterações
• Se a ligação entre 3 e 4 for restaurada, a convergência é rápida
Actualização Nó 1 Nó 2 Nó 3
Antes da interrupção (2,3) (3,2) (4, 1)
Após a interrupção (2,3) (3,2) (2,3)
1 (2,3) (3,4) (2,3)
2 (2,5) (3,4) (2,5)
3 (2,5) (3,6) (2,5)
4 (2,7) (3,6) (2,7)
5 (2,7) (3,8) (2,7)
… … … …
Split Horizon e Poisoned Reverse
Foram propostas alterações ao algoritmo para evitar o problema count
to infinity, mas nenhuma funciona satisfatoriamente em todos os casos

• Split Horizon
– O custo estimado por um nó para um dado destino não é anunciado para
um nó vizinho se este for o next hop para o destino (isto é, se for o nó
através do qual o percurso foi “aprendido”)

• Split Horizon with Poisoned Reverse

– Um nó pode anunciar para todos os nós adjacentes os custos estimados,
mas indicando um custo infinito para um dado destino no caso em que o
nó adjacente é o next hop para esse destino
– Evita imediamente loops directos
– Não funciona em alguns casos de loops indirectos
 Algoritmos Link State
• Princípio de funcionamento
– Cada nó obtém um mapa topológico de toda a rede, que inclui todos os
nós e custos das ligações (isto é, o estado das ligações – link state)
• Com uma topologia estável todos os nós obtêm o mesmo mapa da rede
– Com base nessa informação, cada nó (considerado deste ponto de vista
como nó de origem) calcula o shortest path para cada um dos outros nós
(vistos como nós de destino)
• O algoritmo comporta-se como um algoritmo centralizado no que se refere
aos cálculos realizados por cada nó (origem dos percursos a calcular)
• O algoritmo requer que o estado das ligações seja divulgado a todos os
nós (por um processo de difusão)
– Cada nó i na rede divulga para todos os outros a seguinte informação
• Os identificadores dos seus vizinhos (Ni designa o conjunto dos vizinhos de i)
• As distâncias (custos) aos seus vizinhos: {Cij | j  Ni}
– Um nó não divulga toda a sua tabela de encaminhamento mas apenas os
custos das ligações com os seus vizinhos
– A difusão pode ser feita com recurso a flooding
Estratégia de divulgação do estado
• O estado das ligações de um nó é transportado num pacote designado
Link State Packet (LSP) que contém
– O identificador (id) do nó que criou o LSP
– O custo das ligações para cada um dos seus nós vizinhos
– Um número de sequência
– Um valor TTL (Time To Live)

• A divulgação de um LSP é feita com recurso a flooding, indicando-se

a seguir uma possível realização
– Cada nó gera LSPs periodicamente e envia-os para os seus vizinhos
• Por cada novo LSP criado o número de sequência é incrementado (sendo o
valor inicial igual a zero)
– Após receber um LSP, um nó reenvia-o para todos os seus vizinhos com
excepção do nó do qual o LSP foi recebido
• Cada nó guarda o LSP mais recente proveniente de cada nó origem
• Para cada LSP guardado num nó, o respectivo TTL é decrementado, sendo o
LSP descartado quando TTL = 0
Algoritmo de Dijkstra
• O algoritmo de Dijkstra permite calcular os percursos mais “curtos”
ou de menor custo (shortest paths) de um nó origem para todos os
outros nós na rede
• A ideia é determinar sucessivamente os nós da rede por ordem de
proximidade ao nó de origem
– Numa primeira iteração é obtido o nó mais próximo (que tem de ser um
nó vizinho do próprio nó)
– Numa segunda iteração é obtido o segundo nó mais próximo (que é um
outro nó vizinho de si próprio ou do nó obtido no passo anterior)
– O algoritmo continua de forma idêntica nos passos seguintes
• O algoritmo de Dijkstra parte de um nó de origem e vai acrescentando
nós à árvore de percursos com raiz na origem até incluir todos os nós
de destino (ao contrário do algoritmo de Bellman-Ford que calcula a
árvore de todos os nós de origem para um dado nó de destino)
• O algoritmo usa os custos reais (não estimados) das ligações entre nós
vizinhos
– Estes custos são comunicados por cada nó a todos os restantes
Algoritmo de Dijkstra – passos sucessivos
1. Começar com o nó de origem em causa (raiz da árvore)
2. Associar custo zero a este nó e torná-lo o primeiro nó permanente

Repetir os passos 3 a 5 até que todos os nós sejam permanentes

3. Examinar cada vizinho do nó que foi o último a tornar-se permanente

4. Associar um custo acumulado a cada um destes nós e considerar estes
nós provisórios (numa tentativa de os vir a tornar permanentes)
5. Na lista de nós provisórios
1. Encontrar o nó com o menor custo acumulado e torná-lo permanente
2. Se um nó puder ser alcançado de mais do que uma maneira (direcção)
1. Seleccionar a direcção com o menor custo acumulado
Algoritmo de Dijkstra – formulação
M – conjunto de nós já adicionados à árvore (para os quais o percurso
mais curto desde a origem s já foi encontrado no momento)

1. Início (começar com o nó de origem s)

– M = {s}, Ds = 0 (a distância de s a si próprio é nula)
– Dj = Csj para todos os j  s
2. Passo A (encontrar o nó i seguinte mais próximo de s)
– Encontrar i  M tal que
Di = min Dj para j  M
– Acrescentar i a M
– Terminar se M contiver todos os nós
3. Passo B (actualizar os custos mínimos após i ter sido adicionado a M)
– Para cada nó j  M
Dj = min (Dj, Di + Cij) – verifica se a inclusão de i melhora Dj anterior
– Voltar ao passo A
 Algoritmo de Dijkstra – execução
s (1)
2 3 2 3
1 2 1 1 2 1
5
(3)
4 4
3 1 3 6 3 (4) 6
2 5 2 2 5 2
4 (2) (5)

Iteração M D2 D3 D4 D5 D6
Inicial {1} 3 2 5 ∞ ∞
1 {1,3} 3 2 4 ∞ 3
2 {1,2,3} 3 2 4 7 3
3 {1,2,3,6} 3 2 4 5 3
4 {1,2,3,4,6} 3 2 4  5 3
5 {1,2,3,4,5,6} 3 2 4 5 3
Convergência após falhas
• Se uma ligação falhar
– Os routers que partilham a ligação actualizam o respectivo custo com
um valor infinito e disseminam (propagam) a informação actualizada
através de um LSP
– Os restantes routers actualizam as suas bases de dados com informação
do estado das ligações e calculam de novo os shortest paths
– A recuperação é rápida
• É no entanto necessário ter atenção a mensagens de actualização
antigas que podem ainda estar a circular na rede (devido a flooding)
– Deve incluir-se uma marca temporal (timestamp) ou um número de
sequência em cada mensagem de actualização
– Deve verificar-se se uma mensagem de actualização recebida num nó é
nova
• Se for nova deve ser adicionada à base de dados do nó e difundida
• Se for antiga, não deve ser propagada e deve ser enviada uma mensagem de
actualização ao nó que a enviou
Vantagens de algoritmos Link State
Os algoritmos do tipo link state têm propriedades que os tornam
vantajosos em relação a algoritmos do tipo distance vector

• A convergência é mais rápida, sem criação de loops

• Usam informação rigorosa e não necessitam de divulgar informação
relativa a todos os nós da rede
• São mais flexíveis, uma vez que conhecem a topologia da rede e o
custo das ligações
– É possível suportar métricas rigorosas e métricas múltiplas, se necessário
– É possível suportar percursos múltiplos para um destino
– É possível suportar encaminhamento por classe de tráfego e com QoS
com recurso a múltiplas tabelas
– Facilitam o uso de source routing ao providenciar informação do estado
das ligações (link state)
– Podem ter em conta restrições relativas a um percurso entre uma origem
e um destino (por exemplo, evitar uma ligação pouco fiável)
Protocolos de encaminhamento exterior
• Os protocolos de encaminhamento interior (IGP – Interior Gateway Protocol)
dão consistência ao processo de encaminhamento num AS

• A coerência a nível global da Internet, constituída por um número elevado de

ASs, é conferida por protocolos de encaminhamento exterior (EGP – Exterior
Gateway Protocol) que operam entre ASs

• Um EGP tem como objectivo a troca de informação de encaminhamento entre

dois ASs de forma a permitir o transporte de tráfego entre ambos
– A informação de encaminhamento trocada entre dois ASs inclui as redes contidas
em cada um e os ASs que podem ser alcançados através de cada um deles

• Requisitos típicos a satisfazer por um EGP

– Deve ser escalável ao nível da Internet
– Deve permitir o anúncio de rotas agregadas (com base em CIDR – Classless
Inter-Domain Routing)
– Deve ser flexível e permitir a selecção de rotas com base em políticas
– Deve ser totalmente distribuído
Encaminhamento baseado em políticas
• Uma vez que cada AS tem uma administração independente, a selecção de
rotas externas é essencialmente determinada por políticas de encaminhamento
(routing policies), que envolvem, entre outras, relações de confiança e o
estabelecimento de acordos, e não por critérios de menor custo (shortest
path), na acepção dos algoritmos distance vector e link state
– Para além das limitações conhecidas dos algoritmos do tipo distance vector, os
algoritmos do tipo link state têm também problemas de escalabilidade à escala
global da Internet (tamanho das bases de dados topológicas e tempo de cálculo
de rotas com base no algoritmo de Dijkstra)
• As políticas de encaminhamento são caracterizadas por atributos
– Os atributos associados a uma rota anunciada podem incluir, por exemplo, a
sequência de ASs que formam a rota, o endereço do next hop, uma lista de
métricas que indicam o grau de preferência da rota, informação sobre a criação
da rota pelo AS de origem, etc.
• O protocolo normalizado para encaminhamento entre ASs (BGP-4) pode ser
classificado como sendo do tipo path vector, uma vez que a informação
transportada inclui a sequência de ASs que os pacotes devem atravessar para
atingir uma rede de destino ou um grupo de redes com um mesmo prefixo
Exemplo de políticas

R2 R3

AS2

R1 R4
N1
AS1 AS3

1. R4 anuncia que a rede N1 pode ser alcançada através de AS3

• R3 analisa o anúncio e decide (com base nas suas políticas) se aceita encaminhar
pacotes para N1 através de R4
• Caso afirmativo a tabela de encaminhamento de R3 é actualizada (R4 é o next hop para
N1) e um protocolo interior (IGP) propaga através de AS2 a informação sobre como
alcançar N1
2. Caso AS2 aceite transportar tráfego de trânsito entre AS1 e N1, R2 anuncia a
AS1 que a rede N1 pode ser alcançada através de AS2
• R1 decide (com base nas suas políticas) se quer usar AS2 para comunicar com N1
Protocolos de encaminhamento
RIP, OSPF, BGP
Sistemas Autónomos (AS) – identificação e tipos
• Um Sistema Autónomo (AS – Autonomous System) necessita de possuir um
identificador global único (ASN – AS Number)
– Até 2007 um ASN era um inteiro de 16 bits
– O RFC 4893 introduziu ASNs de 32 bits (escritos na forma x.y, sendo x e y
inteiros de 16 bits; 0.y refere-se aos antigos ASNs de 16 bits)
– Os identificadores são atribuídos em blocos pela Internet Assigned Numbers
Authority (IANA) a Regional Internet Registries (RIRs), por exemplo
• American Registry for Internet Numbers (ARIN), Réseaux IP Européens Network
Coordination Centre (RIPE NCC)

• Tipos de AS
– Stub AS – tem uma única ligação para o exterior (isto é, a um único AS)
– Multi-homed AS – tem múltiplas ligações para o exterior mas não transporta
tráfego de trânsito (tráfego entre dois outros ASs)
– Transit AS – tem múltiplas ligações para o exterior e transporta tráfego de trânsito
e tráfego local
• Um ISP (Internet Service Provider) é necesariamente um Transit AS
RIP – Routing Information Protocol
• A versão original do RIP está definida no RFC 1058
• Usa o algoritmo distance vector
• Corre sobre UDP, na porta 520
• Usa como métrica o número de hops, podendo o hop count ter um
valor entre 1 e 15
– É adequado para redes pequenas (redes locais)
– O valor 16 é reservado para representar um hop count infinito
– Valores pequenos de hop count atenuam o problema de count to infinity
• Existem dois tipos de mensagens RIP
– Request – para solicitar a um vizinho o respectivo vector de custos
– Response – para anunciar um vector de custos
• Uma mensagem Response pode ser enviada periodicamente, após uma
alteração (triggered update) ou em resposta a um Request
• A versão 2 (RIPv2) está definida no RFC 2453
RIP – formato das mensagens
0 8 16 31
Comando Versão Zero

Família do endereço Zero

Endereço IP

Zero Entrada
RIP
Zero

Métrica

...
• Uma mensagem RIP pode incluir no máximo 25 entradas com o mesmo
formato da primeira (20 octetos)
RIPv2 – formato das mensagens
0 8 16 31
Comando Versão Domínio de routing

Família do endereço Etiqueta da rota (AS)

Endereço IP

Máscara da sub-rede Entrada

RIPv2
Endereço IP do next hop

Métrica

...
• Uma mensagem RIPv2 pode incluir no máximo 25 entradas com o formato
indicado (20 octetos)
• A primeira entrada pode, no entanto, transportar informação de autenticação
RIP e RIPv2 – campos das mensagens
• As mensagens RIP e RIPv2 incluem um conjunto de campos comuns
– Comando – Request ou Response
– Versão – 1 ou 2
– Uma ou mais entradas com 20 octetos (no máximo 25 entradas)
• Família do endereço – o valor é igual a 2 para IP
• Endereço IP – endereço de host ou rede de destino
• Métrica – número de hops até ao destino

• As mensagens RIP não incluem informação de máscaras de subrede

nem podem ser usadas com CIDR (Classless Inter-Domain Routing),
isto é, com máscaras de subredes com comprimento variável

• As mensagens RIPv2 incluem informação adicional

– Máscaras de subrede, next hop, domínio de routing e etiqueta da rota
– Funcionam com CIDR
RIP – operação
• Os routers enviam mensagens de actualização para os vizinhos a intervalos
nominais de 30 s
• Um router espera receber mensagens de actualização dos seus vizinhos no
máximo ao fim de 180 s
– Se não receber uma mensagem de actualização de um vizinho nesse intervalo de
tempo, assume que a ligação com esse nó falhou e coloca o valor do custo para
atingir esse nó em 16 (representa um hop count infinito)
– Se posteriormente receber através de outro vizinho um valor válido de custo para
o nó em causa, substitui o valor 16 pelo valor actualizado (após adicionar 1 hop
ao custo anunciado)
• Usa a variante split horizon with poisoned reverse
• A convergência é acelerada com triggered updates
– Os vizinhos de um nó são imediatamente notificados de alterações no respectivo
vector de custos
• Os pacotes que transportam mensagens RIP são difundidos em LANs
(endereço broadcast) e são epecificamente endereçados (endereço unicast)
em redes de acesso múltiplo sem difusão ou em redes ponto-a-ponto
– RIPv2 usa em LANs o endereço multicast [Link]
OSPF – Open Shortest Path First
• O protocolo OSPF (versão 2) está descrito no RFC 2328
• É um protocolo do tipo link state
– Cada router monitoriza o estado da ligação (link state) com cada um dos seus
vizinhos e divulga (por meio de flooding) essa informação por todos os routers
que fazem parte do seu domínio de encaminhamento
– Esta informação permite a cada router aprender a topologia completa da rede
– Em situação estável os routers conhecem a mesma topologia, isto é, possuem a
mesma base de dados topológica (link state database)
• O conhecimento é exacto e não baseado em “rumores” (como em algoritmos do tipo
distance vector)
– Cada router calcula a árvore de shortest paths cuja raiz é o próprio router (com
base no algoritmo de Dijkstra) com o objectivo de criar a sua tabela de
encaminhamento
• A cada entrada correspondente a uma rede está associado o next hop e o custo da rota
até ao destino
• O OSPF tipicamente converge mais rapidamente que o RIP quando ocorre
uma alteração na rede e não tem os problemas que caracterizam os algoritmos
do tipo distance vector
OSPF – propriedades
• Suporta rotas múltiplas para um dado destino (por exemplo, uma por tipo de
serviço)
• Suporta subredes com prefixos de tamanho variável, uma vez que transporta
a máscara associada a cada subrede na mensagem de encaminhamento
• Permite maior flexibilidade na atribuição de custos às ligações (com base em
qualquer métrica), podendo o custo variar ente 1 e 65535
• Permite distribuir tráfego (load balancing) sobre múltiplas rotas de igual
custo
• Suporta autenticação com o objectivo de garantir que os routers trocam
informação com vizinhos de confiança (trusted)
• Cria uma hierarquia em dois níveis pela divisão de um AS em áreas, ligadas
por uma área central (backbone area), o que melhora a escalabilidade
• Suporta rotas específicas para hosts e para redes
• Introduz o conceito de router designado (designated router) em redes que
suportam difusão (de forma nativa ou emulada) com o objectivo de reduzir o
número de mensagens trocadas
OSPF – divisão de um AS em áreas
• O OSPF permite dividir um AS em áreas constituídas por grupos contíguos de
redes e hosts e que inclui os routers com interfaces para cada uma dessas redes
– Um área é identificada por um Area ID de 32 bits
• Cada área corre uma cópia separada do algoritmo de encaminhamento link
state e tem a sua própria base de dados topológica (link state database)
– A base de dados topológica só é idêntica para os routers da mesma área
– Routers ligados a mais do que uma área têm uma base de dados topológica por
cada área
• A divisão dum AS em áreas permite melhorar a escalabilidade do protocolo
pelo isolamento de conhecimento entre áreas que lhe está subjacente
– A topologia de uma área é escondida do resto do AS
– Um router numa área só conhece a topologia completa da sua área e só divulga
informação (link state) na sua área
• Cada área deve estar ligada a uma área central de backbone ([Link])
– A informação de encaminhamento entre áreas é distribuída através do backbone
OSPF – tipos de routers
• Internal Router (IR) – tem todas as interfaces para redes na mesma área
– Executa uma cópia do algoritmo básico de encaminhamento

• Area Border Router (ABR) – tem interfaces a mais do que uma área
– Executa múltiplas cópias do algoritmo básico de encaminhamento, uma por cada
área a que está ligado
– Sumariza a informação das áreas a que está ligado para distribuição através do
backbone (que, por sua vez, a distribui a outras áreas)

• Backbone Router (BBR) – tem interface à área de backbone

– Inclui routers com interface a mais do que uma área (um Area Border Router é
um Backbone Router) e routers com todas as suas interfaces ligadas ao backbone

• AS Boundary Router (ASBR) – router que troca informação de encaminhamento

com routers pertencentes a outros ASs
– Esta classificação é independente das anteriores, isto é, um router deste tipo pode
ser um Internal Router ou um Area Border Router, podendo ou não participar
num backbone
Divisão em áreas – exemplo
Ligação a
outro AS Área [Link]
N1 R1 N5

R – Router
N2 R3 R6 N4 R7
N – Network
R2 N6
R4
R5
N3

Área [Link] R8 Área [Link]

ASBR – AS Boundary Router

ABR – Area Border Router N7
IR – Internal Router
BBR – Backbone Router

ASBR: 4 Área [Link]

ABR: 3, 6, 8
IR: 1, 2, 7
BBR: 3, 4, 5, 6, 8
OSPF – tipos de redes
Na operação do OSPF consideram-se três tipos de redes

• Redes ponto a ponto (point to point networks)

– Redes que ligam um par de routers

• Redes de difusão (broadcast networks)

– Redes que suportam a ligação de mais de dois routers e que têm capacidade de
endereçar uma mensagem a todos os routers em difusão (broadcast)
– Routers vizinhos são descobertos dinamicamente por meio de mensagens Hello
(parte do OSPF)

• Redes sem difusão (non broadcast networks)

– Redes que suportam a ligação de mais de dois routers mas que não têm
capacidade de difusão (e.g., uma rede ATM)
– As relações de vizinhança entre routers são mantidas por mensagens Hello
– OSPF pode ser executado num de dois modos
• NBMA (Non Broadcast Multiple Access) – é emulada a operação numa rede de difusão
• Ponto a multiponto – trata a rede como uma colecção de ligações ponto a ponto
 Vizinhança e adjacência
• Routers vizinhos (neighbouring routers)
– São routers que têm interfaces para uma rede comum
• Todos os routers ligados a um rede de difusão (broadcast network) são
vizinhos (no que se refere às interfaces ligadas a essa rede)
– As relações de vizinhança são mantidas e dinamicamente descobertas por
meio de mensagens Hello
• Adjacência
– É uma relação formada entre routers vizinhos seleccionados com o
objectivo de trocarem informação de encaminhamento
• Nem todos os routers vizinhos se tornam adjacentes (depende do tipo de rede)
– O OSPF requer que apenas os routers adjacentes mantenham sincronizadas
as respectivas bases de dados topológicas (link state database)
– Para lidar com o problema da adjacência em redes de difusão e no modo
NBMA foi introduzido o conceito de router desigando (designated router)
• O conceito permite reduzir o número de adjacências nestas redes, o que por
sua vez reduz o volume de tráfego do protocolo de encaminhamento e o
tamanho das bases de dados topológicas
Router designado (designated router)
• Cada rede de difusão ou NBMA que tenha pelo menos dois routers ligados
tem um router designado
– Existe também um router designado de reserva (backup designated router) que
assume o papel de designated router no caso de falha do router que tinha essa
função
• Um router designado não é um novo tipo de router mas apenas um papel
desempenhado por um router normal escolhido para o efeito e que por isso
realiza um conjunto de funções específicas (é um nó virtual que representa
uma rede em que existem múltiplas adjacências)
– O router designado cria adjacências com cada um dos outros routers
– O router desigando assume responsabilidades especiais no processo de
divulgação (anúncio) do estado das ligações (link state) na respectiva rede
• O router designado e o de reserva são eleitos pelo protocolo Hello (com base
em campos de prioridade e de identificação) após a descoberta de vizinhança
• Em redes ponto a ponto e no modo ponto a multiponto não existe qualquer
router designado
– Neste caso, routers vizinhos tornam-se adjacentes (ou permanecem isolados)
Link State Advertisement (LSA)
• Para construir a base de dados topológica de um domínio de encaminhamento
é necessário divulgar a todos os routers do domínio o estado das ligações entre
routers que criaram adjacências e das redes que os interligam
• A divulgação é feita por meio de anúncios – Link State Advertisement (LSA)
• Um LSA é uma unidade de dados que descreve o estado de um router ou rede
– No caso de um router inclui o estado das suas interfaces e adjacências
• Cada router gera LSAs para divulgação do respectivo estado
– Para além dos seus próprios LSAs, o router designado na rede em que foi eleito
gera também LSAs em representação dos routers adjacentes e LSAs relativos a
essa rede (contém a lista dos routers que a constituem)
– O estado de cada ligação é verificado e actualizado permanentemente por meio de
mensagens Hello
– Apenas são gerados LSAs para comunicar alterações de estado
• Um LSA é disseminado em todo o domínio de encaminhamento por meio dum
mecanismo de difusão fiável (baseado em flooding)
• A base de dados topológica do protocolo (presente em cada router) é formada
pelo conjunto de LSAs de todos os routers e redes divulgados no domínio
Tipos e funções de LSAs
Os anúncios divulgados por diversos tipos de LSAs permitem manter a base
de dados topológica de uma área e anunciar rotas entre áreas e entre ASs

• Router LSA (tipo 1) – gerado por todos os routers OSPF

– Descreve o estado das interfaces de um router numa área
– Disseminado apenas numa área
• Network LSA (tipo 2) – gerado por routers designados
– Contém a lista de routers ligados à rede a que pertence o router designado
– Disseminado apenas numa área
• Summary LSA (tipos 3 e 4) – gerado por Area Border Routers
– Descreve rotas para destinos fora da área, mas dentro do AS
• Tipo 3 – rotas para redes
• Tipo 4 – roats para AS Boundary Routers
– Disseminado apenas na área correspondente
• AS external LSA (tipo 5) – gerado por AS Boundary Routers
– Descreve rotas para destinos externos ao AS (e rotas por omissão para o AS)
– Disseminado em todas as áreas do AS
OSPF – fases de operação
• A operação do protocolo pode ser descrita em três fases
– Descoberta de vizinhos e eleição do designated router (se aplicável)
– Estabelecimento de adjacências e sincronização das bases de dados topológicas
– Troca de LSAs entre routers adjacentes e sua disseminação pela área respectiva
e consequente geração das tabelas de encaminhamento

• Os pacotes OSPF são transmitidos directamente em datagramas IP (sendo

identificados pelo valor 89 no campo Protocol ID do cabeçalho IP)
– Existem 5 tipos de pacotes OSPF

• O protocolo faz uso, nalguns casos, de dois endereços multicast

– [Link] – designado allSPFRouters
– [Link] – designado allDRouters
OSPF – tipos de pacotes
O protocolo usa 5 tipos diferentes de pacotes (que têm um cabeçalho comum)

• Hello
– Usado para descoberta e manutenção de relações de vizinhança
• Database Description
– Usado na formação de adjacências e sincronização da base de dados topológica
– Permite sumarizar o conteúdo da base de dados topológica
• Link State Request
– Usado na formação de adjacências e sincronização da base de dados topológica
– Solicita o download de LSAs para sincronização da base de dados topológica
• Link State Update
– Usado para actualização da base de dados topológica
– Contém LSAs que são enviados por meio de flooding numa área
• Link State Ack
– Usado para actualização da base de dados topológica
– Suporta o mecanismo de difusão fiável (confirmação de LSAs enviados por
flooding)
Cabeçalho OSPF
0 8 16 31

Version Type Packet length

Router ID

Area ID
OSPF
common
Checksum Authentication type
header

Authentication

Authentication
OSPF
Data packet
body

• Tipo de pacote (Type)

1 – Hello, 2 – Database Description, 3 – Link State Request
4 – Link State Update, 5 – Link State Ack
• Router ID
– Um número de 32 bits que identifica univocamente o router no AS – pode ser, por
exemplo, o menor endereço IP de uma das suas interfaces
Descoberta de vizinhança
• Os routers usam pacotes Hello para descobrir vizinhos com os quais
conseguem estabelecer contacto
– Em redes ponto a ponto e de difusão os pacotes Hello são enviados com o
endereço de destino multicast allSPFRouters
– Em redes que não suportam difusão é necessário configurar os routers que têm
uma relação de vizinhança
• Os pacotes Hello são enviados periodicamente (tipicamente com um período
de 10 s)
• Quando um router recebe um pacote Hello de um vizinho, responde com
outro pacote Hello que contém o identificador de cada router que conhece
• Quando um router recebe um pacote Hello que contém o seu identificador
num dos campos de identificação de vizinhos (Neighbor #) assume que a
vizinhança está estabelecida (é possível comunicação bidireccional)
• A relação de vizinhança é quebrada com um vizinho se deixar de receber
pacotes Hello desse vizinho ao fim de um dado intervalo (Dead interval)
• Em redes de difusão e no modo NBMA, as mensagens Hello são também
usadas para eleição do router designado e do respectivo backup
– A eleição é baseada no valor mais elevado dos campos de Prioridade (Priority) e
de Identificação do router (Router ID)
Hello
0 16 24 31

Network mask

Hello interval Options Priority

Dead interval

Designated router

Backup designated router

Neighbour 1

.....

Neighbour n
Formação de adjacências
• Em redes ponto a ponto e no modo ponto a multiponto as adjacências
correspondem às vizinhanças estabelecidas
• Em redes de difusão e no modo NBMA as adjacências são formadas entre o
router designado e cada um dos restantes routers na mesma rede
• A disseminação de LSAs entre routers numa área é feita exclusivamente com
base em adjacências e não em vizinhanças, pelo que a sincronização das bases
de dados topológicas de routers adjacentes é essencial para evitar ciclos
• Uma vez estabelecida comunicação bidireccional entre os routers envolvidos
na formação de uma adjacência, estes trocam pacotes Database Description
para sincronizar as respectivas bases de dados topológicas
– Neste processo um dos routers actua como master e o outro como slave (o que é
determinado por um processo de negociação baseado no Router ID)
• Os pacotes Database Description não contêm a totalidade da base de dados
topológica mas apenas os cabeçalhos dos LSAs (um ou mais)
– O vizinho pode então solicitar os LSAs que não possui por meio de pacotes Link
State Request, recebendo os LSAs solicitados em pacotes Link State Update que,
por sua vez, são confirmados com pacotes Link State Ack
Database Description
0 16 24 29 31

Interface MTU Options Zero I M M

S

Database Description Sequence Number

LSA Header

• I – Init (bit igual a 1 se se tratar do primeiro pacote DD numa sequência)

• M – More (bit igual a 1 se não for último pacote DD numa sequência)
• MS – Master / Slave (bit igual a 1 indica Master)
• LSA header – contém informação que permite identificar univocamente a ligação a que
se refere (tipo, link state ID, router que originou o LSA)
– Nos pacotes Link State Update, cada LSA contém um corpo (LSA body) para além do
cabeçalho (LSA header)
• Podem existir múltiplos LSA headers num pacote DD
 Database Description – LSA Header
0 16 24 31

Link-state age Options Link-state type

Link-state ID

Advertising router

Link-state sequence number

Link-state checksum Length

• Link-state type
1 – Router LSA, 2 – Network LSA, 3 – Summary LSA (para redes)
4 – Summary LSA (para ASBRs), 5 – AS external LSA
• Link-state ID – identifica a ligação descrita pelo LSA (depende do tipo, mas é tipicamente
o endereço IP do router ou da rede que a ligação representa)
• Advertising router – identificador do router que originou o LSA
• Link-state sequence number – número de sequência para detectar LSAs antigos ou
duplicados
• Link-state checksum – protege o conteúdo do LSA com excepção do campo Link-state age
Link State Request
0 31

Link-state type

Link-state ID

Advertising router

...

• Pacotes Link State Request são enviados por um router a um vizinho com
o qual está a formar uma adjacência para obter informação que permita
actualizar parte da sua base de dados topológica (e completar a respectiva
sincronização)
• O pacote inclui grupos de três campos (um por cada LSA solicitado)
– Link-state type
– Link-state ID
– Advertising router
Link State Update e Link State Ack
0 31

Number of LSAs

LSA 1

...

LSA n

• Os pacotes Link State Update contêm actualizações de LSAs

– O número de LSAs é indicado no primeiro campo do corpo do pacote
– Cada LSA é constituído pelo LSA header e por um LSA body
• Os pacotes Link State Update são confirmados por pacotes Link State Ack
– Os pacotes Link State Ack são constituídos por uma lista de LSA headers
• Os pacotes Link State Update são enviados em resposta a pacotes Link State
Request e quando ocorrem alterações (detectadas periodicamente com Hellos)
– São ainda gerados com períodos de 30 m para refrescamento das bases de dados
Uso de endereços multicast em OSPF
• O processo de flooding pode ser optimizado em redes de difusão, tirando
partido do papel desempenhado pelo router designado e recorrendo aos
endereços multicast atribuídos ao OSPF

• Em redes de difusão o endereço multicast AllSPFRouters ([Link]) é usado

como endereço de destino nos seguintes casos
– Por todos os routers em pacotes Hello
– Pelo router designado (ou pelo seu backup, caso necessário) em pacotes
enviados para os restantes routers (Link State Update e Link Sate Ack)

• Em redes de difusão o endereço multicast AllDRouters ([Link]) é usado

como endereço de destino nos seguintes casos
– Em pacotes enviados ao router designado (e backup) pelos restantes routers
(Database Description, Link State Request, Link State Update e Link Sate Ack)

• Em redes ponto a ponto o endereço IP de destino é sempre o endereço

multicast AllSPFRouters, o que evita o desperdício de endereços unicast
– Nas ligações ponto a ponto não é necessário atribuir endereços IP às interfaces
dos routers e, caso isso aconteça, a rede diz-se não numerada (unnumbered)
BGP – Border Gateway Protocol
• O BGP é um protocolo de encaminhamento entre ASs – a versão 4 (BGP-4)
está definida no RFC 4271
• A função principal de routers BGP (designados BGP speakers) é trocarem
entre si informação relativa ao alcance de redes (network reachability)
– Esta informação inclui a lista de ASs atravessados pela informação de alcance
(ou, noutros termos, a sequência de ASs que os pacotes têm de atravessar para
atingirem uma rede de destino)
– Esta informação é suficiente para construir um grafo de conectividade, de que
podem ser eliminados eventuais ciclos (loops) e sobre o qual podem ser tomadas
decisões de encaminhamento baseadas em políticas
• O BGP-4 fornece mecanismos para suportar Classless Inter-Domain Routing
(CIDR), em particular o anúncio de conjuntos de destinos sob a forma de
prefixos IP (eliminando o conceito de classes de endereços) e a agregação de
rotas (com a consequente redução da informação de encaminhamento)
• A informação de encaminhamento trocada por routers BGP apenas suporta o
paradigma de encaminhamento baseado no endereço de destino transportado
no cabeçalho de pacotes IP
BGP – principais conceitos
• BGP speaker – um router que implementa BGP
• BGP Identifier – inteiro (4 octetos) que identifica o emissor de mensagens BGP
• Rota (route) – unidade de informação que associa um conjunto de destinos com
os atributos do caminho (path attributes) para esses destinos
– O conjunto de destinos é formado pelos sistemas cujos endereços IP estão contidos
num prefixo presente no campo NLRI (Network Layer Reachability Information)
de uma mensagem UPDATE
– O caminho (path) é a informação transportada no campo path attributes da mesma
mensagem UPDATE
– As rotas são anunciadas entre speakers BGP em mensagens UPDATE
• Múltiplas rotas com os mesmos path attributes podem ser anunciadas numa única
mensagem UPDATE por inclusão de múltiplos prefixos no campo NLRI
• NLRI (Network Layer Reachability Information) – lista de prefixos IP que
representam destinos alcançáveis através de rotas com path attributes comuns
• Feasible route – rota anunciada que está disponível para uso pelo destinatário
• Unfeasible route – rota previamente anunciada que deixou de estar disponível
• External BGP (EBGP) – ligação BGP entre peers externos (em ASs diferentes)
• Internal BGP (IBGP) – ligação BGP entre peers internos (no mesmo AS)
BGP interno e externo

EBGP EBGP
R IBGP R
R R
IBGP IBGP
IBGP IBGP

R IBGP R R
EBGP
R EBGP

• EBGP é usado para troca de informação entre ASs diferentes

• IBGP é usado para garantir que a informação de alcance a redes se mantém
consistente no conjunto de speakers BGP no mesmo AS
– Os routers IBGP trocam informação aprendida de outros routers IBGP (peers no
mesmo AS)
BGP – principais características
• O BGP é um protocolo do tipo path vector – as rotas para redes de
destino são anunciadas como uma sequência de ASs
– A informação presente no vector permite eliminar ciclos (loops)

• O BGP permite agregação de rotas (com base em CIDR)

• O BGP permite a aplicação de políticas de encaminhamento (quer

para selecção quer para anúncio de rotas)

• Principais funções do protocolo

– Abertura, confirmação e manutenção de ligações entre peers BGP
– Envio de informação de alcance a redes
– Notificação de erros
RIB – Routing Information Base
Um speaker BGP guarda a informação sobre rotas numa base de dados de
rotas (RIB – Routing Information Base) que é formada por três partes

• Adj-RIBs-In – guarda informação de encaminhamento aprendida em

mensagens UPDATE recebidas de outros speakers BGP e o seu conteúdo
representa rotas que estão disponíveis para o processo de decisão
• Loc-RIB – contém a informação (local) de informação de encaminhamento que
o speaker BGP seleccionou por aplicação das suas políticas à informação
contida na Adj-RIBs-In
– O next hop para cada rota é definido na tabela de encaminhamento do speaker
• Adj-RIBs-Out – guarda a informação de encaminhamento que o speaker BGP
seleccionou para anunciar aos seus peers e que transmite em mensagens
UPDATE por si geradas
– Um speaker BGP anuncia aos seus peers apenas rotas que ele próprio usa e a
selecção de rotas a anunciar é determinda pela sua política de exportação
– Inicialmente é enviado o conteúdo de Adj-RIBs-Out, mas subsequentemente
apenas são enviadas actualizações incrementais, o que reduz a largura de banda
consumida e o overhead de processamento
Políticas de encaminhamento e selecção de rotas
• O BGP permite a aplicação de políticas de encaminhamento por meio da
selecção de rotas e do controlo da forma como é distribuída a informação de
encaminhamento
– Exemplos de políticas: 1) Nunca usar o AS X; 2) Nunca usar o AS X e o AS Y no
mesmo caminho; 3) Nunca usar o AS X para alcançar um destino no AS Y
• Através da recepção de mensagens UPDATE dos seus peers, um speaker BGP
fica a conhecer rotas possíveis para diferentes destinos
– Quando existirem múltiplas rotas para um destino, um speaker BGP mantém a
informação sobre todas elas mas não mantém qualquer custo associado às rotas
aprendidas
• Um speaker BGP selecciona rotas para uso próprio e para anúncio aos peers
– Decisão sobre rotas para uso próprio
• Um speaker BGP atribui uma ordem de preferência a cada rota que conhece para um
dado destino e, em conformidade com as políticas configuradas, selecciona a que tiver
ordem de preferência mais elevada
– Decisão sobre o anúncio de rotas
• Um speaker BGP apenas anuncia aos seus peers rotas que seleccionou para seu uso
(isto é, a rota preferida para cada destino), mas o anúncio de uma rota específica está
condicionado à sua política de exportação
Mensagens BGP
• Os peers BGP comunicam sobre sessões TCP na porta 179
• As mensagens BGP têm um cabeçalho comum constituído por três
campos (com tamanho total igual a 19 octetos)
– Marker (16 octetos) – incluído por razões de compatibilidade com
versões anteriores (deve ser preenchido com 1s)
– Length (2 octetos) – indica o comprimento total da mensagem (em
octetos) incluindo o cabeçalho
– Type (1 octeto) – identifica o tipo de mensagem através dum código
• Existem quatro tipos de mensagens, identificadas pelo respectivo
código
1 – OPEN
2 – KEEPALIVE
3 – NOTIFICATION
4 – UPDATE
Utilização de mensagens BGP
• OPEN
– É a primeira mensagem enviada por qualquer dos peers após estabelecimento da
sessão TCP
– Caso aceite, é confirmada por uma mensagem KEEPALIVE em sentido oposto
• KEEPALIVE
– Mensagens regularmente trocadas entre peers para confirmar alcance mútuo
• NOTIFICATION
– Mensagem enviada quando é detectada uma condição de erro
– A ligação BGP é fechada após o envio desta mensagem
• UPDATE
– Mensagem usada para transferir informação de encaminhamento entre peers
BGP, o que permite construir um grafo que descreve as relações entre ASs
– Permite anunciar a um peer rotas viáveis que têm um conjunto de atributos (path
attributes) comuns e/ou eliminar rotas que deixaram de ser viáveis
• Uma mensagem pode anunciar no máximo um conjunto de atributos, mas pode
incluir múltiplos destinos que partilhem esses atributos (os atributos aplicam-se a
todos os destinos indicados no campo NLRI)
OPEN
0 8 16 24 31

Marker

Length Type: OPEN Version

My autonomous system Hold time

BGP identifier
Optional
parameters length Optional parameters

Optional parameters

• Hold time – valor proposto pelo router que envia a mensagem, sendo escolhido o menor
dos dois valores, o proposto e o recebido (deve ser 0 ou, no mínimo, 3 s)
– Limite superior do intervalo máximo entre mensagens NOTIFICATION e/ou UPDATE
• BGP ID – identifica o router que envia a mensagem (endereço IP de uma interface local
do router)
KEEPALIVE
0 16 24 31

Marker

Length Type: KEEPALIVE

• As mensagens KEEPALIVE apenas contêm o cabeçalho

• Devem ser enviadas com regularidade tal que o temporizador associado ao
parâmetro hold time não expire
– O intervalo de tempo máximo sugerido entre mensagens é um terço do hold time
mas a frequência não deve ser superior a 1 mensagem por segundo
NOTIFICATION
0 8 16 24 31

Marker

Length Type: NOTIFICATION Error code

Error subcode Data

• O tipo de erro é indicado por meio dum código, sendo a informação mais
específica sobre a natureza do erro dada por um sub-código
UPDATE

Unfeasible routes length (two octets)

Withdrawn routes (variable)

Total path attribute length (two octets)

Path attributes (variable)

Network layer reachability information (variable)

• As mensagens UPDATE são usadas para troca de informação de encaminhamento entre

routers BGP e contêm
– Rotas a descartar (não viáveis)
– Atributos de caminho (path attributes)
– Informação de alcance a redes (Network Layer Reachability Information – NLRI)
• Os atributos descrevem as caracteríticas de uma rota e são usados para influenciar o
comportamento dos routers e o processo de encaminhamento
Atributos de caminhos (path attributes)
• As mensagens UPDATE contêm uma sequência de comprimento variável de
atributos de caminhos (path attributes), sendo cada atributo definido na forma
TLV (type, length, value)
• O campo tipo é constituído por dois octetos (o segundo é o código do atributo)
O T P E 0 Attribute Type Code

– O – flag que indica se o atributo é opcional (O = 1) ou reconhecido (well known)

• Um atributo well known deve ser reconhecido por todos os speakers BGP, podendo ou
não ser obrigatória a sua inclusão
• Os atributos well known obrigatórios devem ser incluídos nas mensagens UPDATE
– T – flag que indica se o atributo é transitivo (T = 1) ou não transitivo (local)
• Atributos reconhecidos (well known) são sempre transitivos (O = 0, T = 1)
– P – flag que indica se a informação num atributo opcional transitivo (O = T = 1) é
parcial (P = 1) ou completa
• A informação deve ser completa em atributos well known (O = 0, T = 1, P = 0) e em
atributos opcionais não transitivos (O = 1, T = 0, P = 0)
– E – flag que indica se o campo attribute length tem um octeto (E = 0) ou dois
Lista de atributos
• ORIGIN (código = 1)
– Well known, obrigatório
• AS_PATH (código = 2)
– Well known, obrigatório
• NEXT_HOP (código = 3)
– Well known, obrigatório
• MULTI_EXIT_DISC (código = 4)
– Opcional, não transitivo
• LOCAL_PREF (código = 5)
– Well known, não obrigatório
• ATOMIC_AGGREGATE (código = 6)
– Well known, não obrigatório
• AGGREGATOR (código = 7)
– Opcional, transitivo
Caracterização dos atributos
• ORIGIN – gerado pelo router que originou a informação de encaminhamento relativa
aos destinos indicados no campo NLRI, definindo qual a origem dessa informação
– O valor 0 (para IGP) indica que o NLRI é interior ao AS de origem, enquanto o valor 1
(EGP) indica que o NLRI foi aprendida via EGP
• AS_PATH – identifica os ASs pelos quais passou a informação de encaminhamento
presente na mensagem UPDATE
• NEXT_HOP – define o endereço IP do router que deve ser usado como next hop para
os destinos listados no campo NLRI da mensagem UPDATE
• MULTI_EXIT_DISC – pode ser usado em ligações entre ASs para discriminar entre
múltiplos pontos de entrada ou saída num AS vizinho (fornece ao processo de decisão
de um router BGP pistas para o caminho preferido)
• LOCAL_PREF – usado por um router BGP para informar peers internos sobre o seu
grau de preferência (com base numa política local) em relação a uma rota externa
• ATOMIC_AGGREGATE – informa outros routers BGP que a rota anunciada no
AS_PATH pode não ser a mais específica para os destinos indicados no NLRI
• AGGREGATOR – adicionado pelo router BGP que formou uma rota agregada,
especificando o número do seu AS e o seu endereço IP