Roteamento
Referência:
 Slides extraídos do material dos professores Jim
Kurose e Keith Ross relativos ao livro “Redes de
Computadores e a Internet – Uma abordagem topdown”, segunda e terceira edições
 Alterações nos slides, incluindo sequenciamento,
textos, figuras e novos slides, foram realizadas
conforme necessidade
Funções Da Camada De Rede
 Transportar pacotes entre os
sistemas finais da rede
 A camada de rede deve ter uma
entidade em cada sistema final
ou roteador da rede
aplicação
transporter
ede
enlace
fisica
rede
enlace
fisica
rede
enlace
fisica
3 funções importantes:

Determinação de caminhos: rota
escolhida pelos pacotes entre a
origem e o destino. Algoritmos
de roteamento
 Comutação: mover pacotes entre
as portas de entrada e de saída
dos roteadores

rede
enlace
fisica
Estabelecimento de conexão:
algumas arquiteturas de rede
exigem o estabelecimento de
circuitos virtuais antes da
transmissão de dados
rede
enlace
fisica
rede
enlace
fisica
rede
enlace
fisica
rede
enlace
fisica
rede
enlace
fisica
aplicação
transporte
rede
enlace
fisica
Modelo Do Serviço De Rede
Q: como escolher um
modelo de serviço para
o canal transportando
pacotes da origem ao
destino?
 Banda-passante garantida?
 Preservação dos intervalos
entre pacotes?
 Entrega sem perdas?
 Entrega em ordem?
 Realimentação de informação
de congestionamento?
Nível mais geral
de abstração na
camada de rede
? ?
?
circuito virtual
ou
datagrama
Circuitos Virtuais (VC)
“A ligação entre a origem e o destino emula uma
ligação telefônica”


Orientado ao desempenho
A rede controla a conexão entre a origem e o destino
 Estabelecimento da conexão deve proceder o envio de dados.
Liberação da conexão após os dados.
 Cada pacote transporte um identificador do CV, não transporta o
endereço completo do destino
 Cada roteador na rota mantém informação de estado para conexão
que passa por ele.

A conexão de camada de transporte envolve apenas os sistemas finais
 A banda passante e os recursos do roteador podem ser alocados
por VC

Controle de Qualidade de Serviço por VC
Circuitos Virtuais: Sinalização
 Usado para estabelecer, manter e
encerrar Circuitos Virtuais
 Usados em ATM, Frame-Relay e X-25,
mas não na Internet
aplicação
transporte 5. Inicia Fluxo de dados
4. Call connected
rede
enlace 1. Call Request
fisica
6. Recebe Dados aplicação
3. Accept call transporte
rede
2. incoming call
enlace
fisica
Redes Datagrama: o modelo da Internet
 Não existem conexões na camada de transporte
 Não há informação de estado de conexão nos roteadores

Não existe conexão na camada de rede
 Pacotes tipicamente transportam o endereço de destino

Pacotes para o mesmo destino podem seguir diferentes rotas
aplicação
transporte
rede
enlace 1. Envia dados
fisica
aplicação
transporte
rede
2. Recebe dados
enlace
fisica
Datagrama versus Circuito Virtual
Internet
 Dados trocados entre
ATM
 Originário da telefonia
computadores
 Conversação humana:
 Serviço elástico, requisitos
 Tempos estritos,
de atraso não críticos
exigências de
 Sistemas finais inteligentes
confiabilidade
 Podem adaptar-se, realizar
 Necessário para serviço
controle e recuperação de
garantido
erros
 A rede é simples, a
 Sistemas finais “burros”
complexidade fica nas pontas
 Telefones
 Muitos tipos de enlaces
 Complexidade dentro da
 Características diferentes
rede
 Difícil obter um serviço
uniforme
Roteamento
Protocolo de Roteamento
5
OBJ: determinar “bons” caminhos
(seqüência de roteadores) através da
rede da fonte ao destino.
2
A
Algoritmos de roteamento são
descritos por grafos:
 Nós do gráfo são
roteadores
 Arestas do grafo são
enlaces

Custo do enlace: atraso,
preço ou nível de
congestionamento
B
2
1
D
3
C
F
1
3
1
5
E
2
 “bons” caminhos:


tipicamente corresponde
aos caminhos de menor
custo
caminhos redundantes
Classificação dos Algoritmos de Roteamento
Informação global ou
descentralizada
Global:
 Todos os roteadores tem
informações completas da
topologia e dos custos dos
enlaces
 algoritmos “Link state”
Descentralizada:
 Roteadores só conhecem
informações sobre seus
vizinhos e os enlaces para eles
 Processo de computação
interativo, troca de
informações com os vizinhos
 algoritmos “Distance vector”
Estático ou Dinâmico?
Estático:
 As rotas mudam lentamente ao
longo do tempo
Dinâmico:
 As rotas mudam mais
rapidamente
 Atualizações periódicas
 Podem responder a
mudanças no custo dos
enlaces
Algoritmo Link-state
Algoritmo de Dijkstra’s
 Topologia de rede e custo dos
enlaces são conhecidos por
todos os nós.
 Implementado via “link
state broadcast”
 Todos os nós têm a mesma
informação
 Computa caminhos de menor
custo de um nó (fonte) para
todos os outros nós
 Fornece uma tabela de
roteamento para aquele nó
 Convergência: após k
iterações, conhece o caminho
de menor custo para k
destinos.
Notação:
 C(i,j): custo do enlace do nó i
ao nó j. Custo é infinito se não
houver ligação entre i e j
 D(v): valor atual do custo do
caminho da fonte ao destino V
 P(v): nó predecessor ao longo
do caminho da fonte ao nó v,
isto é, antes do v
 N: conjunto de nós cujo
caminho de menor custo é
definitivamente conhecido
Exemplo: Algoritmo de Dijkstra’s
Passo
0
1
2
3
4
5
início N
A
AD
ADE
ADEB
ADEBC
ADEBCF
D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F)
2,A
1,A
5,A
infinito
infinito
2,A
4,D
2,D
infinito
2,A
3,E
4,E
3,E
4,E
4,E
5
2
A
B
2
1
D
3
C
3
1
5
F
1
E
2
Algoritmo “Distance Vector”
Iterativo:
 Continua até que os nós
não troquem mais
informações.
 Self-terminating: Não há
sinal de parada
Assíncrono:
 Os nós não precisam
trocar informações
simultaneamente!
Distribuído:
 Cada nós se comunica
apenas com os seus
vizinhos, diretamente
conectados
Estrutura de Dados da Tabela de
Distância
 Cada nó tem sua própria tabela
 Linha para cada possível destino
 Coluna para cada roteador vizinho
 Exemplo: no nó X, para destino Y via
vizinho Z:
X
D (Y,Z)
distância de X to
= Y, via Z como prox. salto
Z
= c(X,Z) + minw{D (Y,w)}
A Tabela de Distâncias Gera a Tabela
de Roteamento
custo através de
E
A
B
D
A
1
14
5
A
A,1
B
7
8
5
B
D,5
C
6
9
4
C
D,4
D
4
11
2
D
D,2
Tabela de distância
Enlace de saída, cost
destino
destino
D ()
Tabela de Roteamento
Roteamento Vetor-Distância: Resumo
Iterativo, assíncrono:
cada iteração local é
causada por:
 Mudança de custo dos
enlaces locais
 Mensagem do vizinho: seu
caminho de menor custo
para o destino mudou
Distribuído:
 Cada nó notifica seus
vizinhos apenas quando seu
menor custo para algum
destino muda

Vizinhos notificam seus
vizinhos e assim por diante
Cada nó:
espera por mudança no
custo dos enlaces locais ou
mensagem do vizinho
recalcula tabela de
distância
se o caminho de menor custo
para algum destino mudou,
notifica vizinhos
Comparação dos Algoritmos LS e VD
Complexidade
 LS: com n nós, E links, o(ne)
mensagens enviadas
 DV: trocas somente entre
vizinhos
 Tempo de convergência varia
Tempo de convergência
 LS: algoritmo o(n**2) exige
o(ne) msgs
 Pode ter oscilações
 DV: tempo de convergência varia
 Podem haver loops de
roteamento
 Problema da contagem ao
infinito
Robustez: o que acontece se um
roteador funciona mal?
Ls:


Nós podem advertir custos
incorretos para os enlaces.
Cada nó calcula sua própria
tabela de roteamento
Dv:


Nó pode advertir caminhos
com custo incorreto
Tabela de cada nó é usada
por outros
• Propagação de erros pela
rede
Roteamento Hierárquico
Problemas do mundo real
 roteadores não são todos idênticos
 as redes não são “flat” na prática
Escala: com 50 milhões
de destinos:
Autonomia Administrativa
 Não é possível armazenar
 Cada administração de rede
todos os destinos numa
única tabela de rotas!
 As mudanças na tabela de
rotas irão congestionar os
enlaces!
 Internet = rede de redes
pode controlar somente o
roteamento na sua própria
rede
Roteamento Hierárquico
 Agrega roteadores em
regiões, “sistemas
autônomos ” (AS)
 Roteadores no mesmo
AS rodam o mesmo
protocolo de
roteamento


Protocolo de
roteamento “Intra-as”
Roteadores em
diferentes AS podem
rodar diferentes
protocolos de
roteamento
roteadores de borda
 Roteadores de interface
de um AS
 Rodam protocolos de
roteamento intra-as
com os outros
roteadores do AS
 Também responsáveis
por enviar mensagens
para fora do AS
 Rodam protocolo de
roteamento inter-as
com outros roteadores de borda
Roteamento Intra-as and Inter-as
C.b
a
C
Roteadores de Borda
B.a
A.a
b
A.c
d
A
a
b
c
a
c
B
b
•realizam
roteamento interAS entre si
•realizam
roteamento intraAS com outros
roteadores do
mesmo AS
Camada de rede
Roteamento inter-AS,
intra-AS no roteador A.c
Camada de enlace
Camada fisica
Roteamento Intra-AS e Inter-AS
roteamento Inter-AS
entre A e B
B.a
C.b
a
Host
h1
C
b
A.a
A.c
a
d
c
b
A
roteamento Intra-AS
dentro AS A
a
c
B
Host
h2
b
roteamento IntraAS dentro do AS B
A camada de rede da Internet
Entidade de rede em roteadores ou hosts:
Camada de Transporte: TCP, UDP
Camada de
Rede
protocolo IP
•endereçamento
•formato dos datagramas
•tratamento de pacotes
Prot. de roteamento
•escolha de caminhos
•RIP, OSPF, BGP
tabela
de rotas
protocolo ICMP
•aviso de erros
•sinalização de rotas
Camada de enlace
Camada física
Endereçamento IP: Introdução
 endereço IP: identificador
de 32-bits para interfaces
de roteadores e hosts
 Interface: conexão entre
roteador ou host e enlace
físico



223.1.1.1
223.1.2.1
223.1.1.2
223.1.1.4
223.1.1.3
223.1.2.9
223.1.3.27
223.1.2.2
Roteador tem tipicamente
múltiplas interfaces
Hosts podem ter
223.1.3.2
223.1.3.1
múltiplas interfaces
endereços IP são
associados com
interfaces, não com o
host ou com o roteador 223.1.1.1 = 11011111 00000001 00000001 00000001
223
1
1
1
Endereçamento IP
 Endereço IP:



parte de rede (bits mais
significativos)
parte de Host part (bits
menos significativos)
O que é uma rede? (na
prespectiva do endereço)
 Interfaces de
dispositivos com a mesma
parte de rede no
endereço IP
 Podem fisicamente se
comunicar sem o auxílio
de um rotedor
223.1.1.1
223.1.2.1
223.1.1.2
223.1.1.4
223.1.1.3
223.1.2.9
223.1.3.27
223.1.2.2
LAN
223.1.3.1
223.1.3.2
rede consistindo de 3 redes IP
(para endereços IP começando com 223,
os primeiros 24 bits são o endereço de
rede )
Endereçamento IP
Como encontrar as redes
 Separe cada interface de
roteadores e hosts
 Criar ilhas de redes
isoladas
 Técnica de nuvens
223.1.1.2
223.1.1.1
223.1.1.4
223.1.1.3
223.1.9.2
223.1.7.0
223.1.9.1
223.1.7.1
223.1.8.1
223.1.8.0
223.1.2.6
Sistema com seis
redes interconectadas
223.1.2.1
223.1.3.27
223.1.2.2
223.1.3.1
223.1.3.2
Endereços IP
endereçamento “class-full”:
class
A
0 rede
B
10
C
110
D
1110
1.0.0.0 to
127.255.255.255
host
rede
128.0.0.0 to
191.255.255.255
host
rede
host
multicast address
32 bits
192.0.0.0 to
223.255.255.255
224.0.0.0 to
239.255.255.255
Endereçamento IP: CIDR
 Endereçamento “Classful”:


Uso ineficiente do espaço de endereçamento, exaustão do
espaço de endereços
E.G., rede de Classe B aloca endereços para 65K hosts,
mesmo se só existem 2000 hosts naquela rede
 CIDR: classless interdomain routing


A porção de endereço de rede tem tamanho arbitrário
Formato do endereço: a.B.C.D/x, onde x é o número de bits
na parte de rede do endereço
parte de
rede
parte de
host
11001000 00010111 00010000 00000000
200.23.16.0/23
Como obter um endereço IP
Hosts :
 Endereço fixo: definido pelo administrador
 DHCP: dynamic host configuration protocol: permite a
atribuição dinâmica de endereços IP
 Host envia (broadcast) mensagem “DHCP discover”
 DHCP server responde com mensagem “DHCP offer”
 Host pede endereço IP com mensagem : “DHCP request”
 DHCP server envia endereço com a mensagem: “DHCP ack”
Endereçamento Hierárquico: agregação de
rotas
O endereçamento hierárquico permite uma propagação de rotas
mais eficiente:
Organização 0
200.23.16.0/23
Organização 1
“Me envie qualquer coisa com
endereço começando por
200.23.16.0/20”
200.23.18.0/23
Organização 2
200.23.20.0/23
Organização 7
.
.
.
.
.
.
Fly-By-Night-ISP
Internet
200.23.30.0/23
ISPs-R-Us
“Me envie qualquer coisa com
endereço começando por
199.31.0.0/16”
Roteamento Hierárquico:rotas mais
específicas
ISPs-R-Us tem uma rota mais específica para a organização 1
Organização 0
200.23.16.0/23
Organização 2
200.23.20.0/23
Organização 7
.
.
.
.
.
.
“Me envie qualquer coisa
com endereço começando por
200.23.16.0/20”
Fly-By-Night-ISP
Internet
200.23.30.0/23
ISPs-R-Us
Organização 1
200.23.18.0/23
“Me envie qualquer coisa
com endereço começando por
199.31.0.0/16 ou 200.23.18.0/23”
Como obter um endereço IP...
Q: Como o ISP obtém seu bloco de endereço?
A: ICANN: internet corporation for assigned
names and numbers
 Aloca endereços
 Gerencia DNS
 Atribuí nomes de domínios e resolve disputas
Formato do Datagrama IP
versão do Protocolo IP
tamanho do header
(bytes)
Classe de serviço
número máximo
de saltos
(decrementado em
cada roteador)
Protocolo da camada
superior com dados no
datagrama
32 bits
ver head. type of
len service
lenght
fragment
16-bit identifier flgs
offset
time to protoInternet
col
live
checksum
tamanho total
do datagrama
(bytes)
para
fragmentação/
remontagem
32 bit endereço IP de origem
32 bit endereço IP de destino
Opções (se houver)
data
(tamanho variável ,
tipicamente um segmento
TCP ou UDP)
Ex. timestamp,
registro de rota
lista de roteadores a visitar.
IP Fragmentação e Remontagem

enlaces de rede têm MTU
(max.transfer size) - corresponde
ao maior frame que pode ser
transportado pela camada de
enlace.


tipos de enlaces diferentes
possuem MTU diferentes
(ethernet: 1518 bytes)
datagramas IP grandes devem ser
divididos dentro da rede
(fragmentados)



fragmentação
in: um datagrama grande
out: 3 datagramas menores
um datagrama dá origem a
vários datagramas
“remontagem” ocorre apenas
no destino final
O cabeçalho IP é usado para
identificar e ordenar
datagramas relacionados
reassembly
Roteamento na Internet
 A Internet consiste de Sistemas Autônomos (AS)
interconectados entre si:



Stub AS: pequena corporação
Multihomed AS: grande corporação (sem tráfego de trânsito)
com mais de uma saída para a Internet
Transit AS: provedor
 Dois níveis de roteamento:


Intra-AS: o administrador é responsável pela definição do
método de roteamento
Inter-AS: padrão único (BGP)
Hierarquia de AS
Roteador de borda Inter-AS (exterior gateway)
Roteador interno Intra-AS (gateway)
Roteamento Intra-AS
 Também conhecido como Interior Gateway
Protocols (IGP)
 IGPs mais comuns:
 RIP:
Routing Information Protocol
 OSPF:
 ISIS:
Open Shortest Path First
Intermediate System to Intermediate
System
RIP ( Routing Information Protocol)
 Algoritmo do tipo vetor distância
 Incluso na distribuição do BSD-UNIX em 1982
 Métrica de distância: # of hops (max = 15 hops)

motivo: simplicidade
 Vetores de distância: trocados cada 30 sec via
Response Message (também chamado advertisement,
ou anúncio)
 Cada anúncio: indica rotas para até 25 redes de
destino
RIP Processamento da tabela de rotas
 As tabelas de roteamento do RIP são manipuladas
por um processo de aplicação chamado routed
(daemon)
 anúncios são enviados em pacotes UDP com
repetição périódica
OSPF (Open Shortest Path First)
 “open”: publicamente disponível
 Usa algoritmo do tipo Link State

disseminação de pacotes LS

Mapa topológico em cada nó

usa algoritmo de Dijkstra’s para cálculo de rotas
 anúncios do OSPF transportam um registro para cada
roteador vizinho
 Anúncios são distribuídos para todo o AS (via
flooding)
OSPF características avançadas
 Segurança: todas as mensagens do OSPF são autenticadas (para
previnir intrusão de hackers); usa conexões TCP para as suas
mensagens
 Múltiplos caminhos de mesmo custo são permitidos (o RIP só
permite um caminho para cada destino)
 Para cada enlace podem ser calculadas múltiplas métricas uma
para cada tipo de serviço (TOS) (ex, custo de enlace por satélite
definido baixo para tráfego de “melhor esforço” e alto para
serviços de tempo real)
 Integra tráfego uni- e multicast :

Multicast OSPF (MOSPF) usa a mesma base de dados topológica do
OSPF
 Hierarchical OSPF: dois níveis de roteamento para domínios
grandes.
OSPF Hierárquico
Inter-AS routing
Internet inter-AS routing: BGP
 BGP (Border Gateway Protocol): é o padrão de fato
para uso na Internet
 Algoritmo Path Vector :
 similar
ao protocolo Distance Vector
 cada
Border Gateway envia em broadcast aos
seus vizinhos (peers) o caminho inteiro (isto é a
seqüência de ASs) até o destino
 Exemplo:
Gateway X deve enviar seu caminho
até o destino Z:
Path (X,Z) = X,Y1,Y2,Y3,…,Z
Internet inter-AS routing: BGP
Suponha: roteador X envia seu caminho ao roteador
parceiro W
 W pode escolher ou não o caminho oferecido por X
 critérios
de escolha: custo, regras (não rotear
através de AS rivais ), prevenção de loops.
 Se W seleciona o caminho oferecido por X, então:
Path (W,Z) = w, Path (X,Z)
 Nota: X pode controlar o tráfego de entrada
controlando as rotas que ele informa aos seus
parceiros:
 ex.,
se X não quer rotear tráfego para Z, X não
informa nenhuma rota para Z
Internet inter-AS routing: BGP
 As mensagens do BGP são trocadas encapsuladas no TCP.
 mensagens BGP:




OPEN: inicia a conexão TCP com um roteador parceiro e
autentica o transmissor
UPDATE: anuncia novo caminho (ou retira um velho)
KEEPALIVE mantém a conexão viva em caso de ausência de
atualizações; também reconhece mensagens OPEN
NOTIFICATION: reporta erros nas mesnagens anteriores;
também usado para encerrar uma conexão
Porque os protocolos Intra- e Inter-AS são
diferentes ?
Políticas:
 Inter-AS: a administração quer ter controle sobre como seu
tráfego é roteado e sobre quem roteia através da sua rede.
 Intra-AS: administração única: as decisões políticas são mais
simples
Escalabilidade
 O roteamento hierárquico poupa espaço da tabela de rotas e
reduz o tráfego de atualização
Performance:
 Intra-AS: preocupação maior é desempenho
 Inter-AS: regras de mercado podem ser mais importantes que
desempenho
Enfileiramento na Porta de Entrada
 Se a estrutura de comutação for mais lenta que a capacidade
combinada das portas de entrada -> pode ocorrer filas nas
portas de entrada
 Bloqueio Head-of-the-Line (HOL): datagramas enfileirados no
início da fila bloqueiam aqueles que estão atrás na fila

atrasos de filas e perdas são provocados pela saturação do
buffer de entrada!
Três tipos de estruturas de comutação
Filas na porta de saída
 armazenamento quando a taxa de chegada pelo
comutador excede a velocidade da linha de saída

filas(atrasos) e perdas são provocados por um
overflow do buffer da porta de saída!