Capítulo 4: Camada de Rede
Metas do capítulo:
r
entender os princípios em r
que se fundamentam os
r
serviços de rede:
m
m
m
m
r
Resumo:
roteamento (seleção de
caminhos)
escalabilidade
como funciona um
roteador
tópicos avançados: IPv6
instanciação e
implementação na
Internet
r
r
r
serviços da camada de rede
princípio de roteamento:
seleção de caminhos
roteamento hierárquico
IP
Protocolos de roteamento da
Internet
m
m
r
r
dentro de um domínio
entre domínios
como funciona um roteador?
IPv6
4: Camada de Rede
4a-1
Funções da camada de rede
r
r
transporta pacote da estação
remetente à receptora
protocolos da camada de rede
em cada estação, roteador
aplicação
transporte
rede
enlace
física
rede
enlace
física
rede
enlace
física
três funções importantes:
r
determinação do caminho: rota
seguida por pacotes da origem
ao destino. Algoritmos de
r
roteamento
comutação: mover pacotes
r
estabelecimento da chamada:
dentro do roteador da entrada à
saída apropriada
algumas arquiteturas de rede
requerem determinar o caminho
antes de enviar os dados
rede
enlace
física
rede
enlace
física
rede
enlace
física
rede
enlace
física
rede
enlace
física
rede
enlace
física
aplicação
transporte
rede
enlace
física
4: Camada de Rede
4a-2
Modelo de serviço de rede
Q: Qual é o modelo de
serviço para o “canal”
que transporta pacotes
do remetente ao
receptor?
r
r
r
r
r
largura de banda garantida?
preservação de temporização
entre pacotes (sem jitter)?
entrega sem perdas?
entrega ordenada?
realimentar informação
sobre congestionamento ao
remetente?
A abstração mais
importante provida
pela camada de rede:
? ?
?
circuito virtual
ou
datagrama?
4: Camada de Rede
4a-3
Circuitos virtuais
“caminho da-origem-ao-destino se comporta como um
circuito telefônico”
m
m
r
r
r
estabelecimento de cada chamada antes do envio dos dados
cada pacote tem ident. de CV (e não endereços origem/dest)
cada roteador no caminho da-origem-ao-destino mantém “estado”
para cada conexão que o travessa
m
r
em termos de desempenho
em ações da rede ao longo do caminho da-origem-ao-destino
conexão da camada de transporte só envolve os 2 sistemas terminais
recursos de enlace, roteador (banda, buffers) podem ser alocados
ao CV
m
para permitir desempenho como de um circuito
4: Camada de Rede
4a-4
Circuitos virtuais:
protocolos de sinalização
usados para estabelecer, manter, destruir CV
r usados em ATM, frame-relay, X.25
r não usados na Internet de hoje
r
aplicação
6. dados recebidos aplicação
transporte 5. começa fluxo de dados
transporte
rede
4. conexão completa
3. chamada aceita
rede
1. inicia chamada
enlace
2. chegada de chamada
enlace
física
física
4: Camada de Rede
4a-5
Rede de datagramas: o modelo da Internet
r
r
r
não requer estabelecimento de chamada na camada de rede
roteadores: não guardam estado sobre conexões fim a fim
m não existe o conceito de “conexão” na camada de rede
pacotes são roteados tipicamente usando endereços de destino
m 2 pacotes entre o mesmo par origem-destino podem seguir
caminhos diferentes
aplicação
transporte
rede
1. envia dados
enlace
física
aplicação
transporte
rede
2. recebe dados
enlace
física
4: Camada de Rede
4a-6
Modelos de serviço da camada de rede:
Arquitetura
de Rede
Internet
r
Modelo de
Banda
serviço
ATM
melhor
esforço
CBR
ATM
VBR
ATM
ABR
ATM
UBR
Garantias ?
Informa s/
Perdas Ordem Tempo congestion.?
nenhuma
não
não
não
taxa
constante
taxa
garantida
mínima
garantida
nenhuma
sim
sim
sim
sim
sim
sim
não
sim
não
não (inferido
via perdas)
sem
congestion.
sem
congestion.
sim
não
sim
não
não
Modelo Internet está sendo estendido: Intserv, Diffserv
m Capítulo 6
4: Camada de Rede
4a-7
Rede de datagramas ou CVs: por quê?
Internet
r
r
r
ATM
troca de dados entre
r
computadores
r
m serviço “elástico”, sem
reqs. temporais estritos
sistemas terminais
“inteligentes” (computadores)
m podem se adaptar, exercer
controle, recuperar de
r
erros
m núcleo da rede simples,
complexidade na “borda”
muitos tipos de enlaces
m características diferentes
m serviço uniforme difícil
evoluiu da telefonia
conversação humana:
m temporização estrito,
requisitos de
confiabilidade
m requer serviço
garantido
sistemas terminais “burros”
m telefones
m complexidade dentro da
rede
4: Camada de Rede
4a-8
A Camada de Rede na Internet
Componentes da camada de rede em estações e roteadores:
Camada de transporte: TCP, UDP
Camada
de rede
Protocolos de
Roteamento
•seleção de rotas
•ex: RIP, OSPF, BGP
Protocolo Roteável
•convenções de endereços
•formato do datagrama
•ex: IP
Tabela
de Rotas
Processo de
Roteamento
Protocolo ICMP
•relata erros
•“sinalização” de roteadores
Camada de enlace
Camada física
4: Camada de Rede
4a-9
Sumário de Arquitetura de Roteadores
Duas funções chave de roteadores:
r
r
“Tendem” a usar protocolos de roteamento (RIP, OSPF, BGP)
Comutam datagramas do enlace de entrada para a saída:
m
m
m
Portas de Entrada e Saída
Matriz de Comutação
Processador de Roteamento
4: Camada de Rede 4a-10
Porta de Entrada
Camada física:
recepção de bits
Camada de enlace:
p.ex.: Ethernet, PPP
Camada de Rede:
r Comutação descentralizada: dado o destino
do datagrama, procura porta de saída
usando tab. de rotas na memória
r Meta: completar processamento da porta
de entrada na ‘velocidade da linha’
r Filas: se datagramas chegam mais rápido
que taxa de re-envio para matriz de
comutação
4: Camada de Rede 4a-11
Filas na Porta de Entrada
Se matriz de comutação mais lenta do que a soma das
portas de entrada juntas -> pode haver filas nas
portas de entrada
r Bloqueio cabeça-de-linha : datagrama na cabeça da
fila impede outros na mesma fila de avançarem
r
r
retardo de enfileiramento e perdas devido ao
transbordo do buffer de entrada!
4: Camada de Rede 4a-12
Três tipos de matriz de comutação
4: Camada de Rede 4a-13
Comutação via Memória
Roteadores da primeira geração:
r pacote copiado pelo processador (único) do sistema
r velocidade limitada pela largura de banda da
memória (2 travessas do barramento por datagrama)
Porta de
Entrada
Memória
Porta de
Saída
Barramento do Sistema
Roteadores modernos:
r processador da porta de entrada consulta tabela,
copia para a memória
r Cisco Catalyst 8500
4: Camada de Rede
4a-14
Comutação via Barramento
r
datagrama da memória da porta de entrada à memória
da porta de saída via um barramento compartilhado
r
contenção pelo barramento: taxa de comutação
limitada pela largura de banda do barramento
r
Barramento de 1 Gbps, Cisco 1900: velocidade
suficiente para roteadores de acesso e corporativos
(mas não regionais ou de backbone)
4: Camada de Rede 4a-15
Comutação via Rede de Interconexão
supera limitações de banda dos barramentos
r Redes Banyan, outras redes de interconexão
desenvolvidas inicialmente para interligar processadores
num multiprocessador
r Projeto avançado: fragmentar datagrama em células de
tamanho fixo, comutar células através da matriz de
comutação.
r Cisco 12000: comuta N Gbps pela rede de interconexão.
r
4: Camada de Rede 4a-16
Porta de Saída
r
Buffers necessários quando datagramas chegam da
matriz de comutação mais rapidamente que a taxa de
transmissão
m
m
r
usa buffers quando taxa de chegada através do comutador
excede taxa de transmissão de saída
enfileiramento (retardo), e perdas devidas ao transbordo do
buffer da porta de saída!
Disciplina de escalonamento escolhe um dos
4: Camada de Rede
datagramas enfileirados para transmissão
4a-17
Protocolo de Roteamento
protocolo de roteamento
meta: determinar caminho
(seqüência de roteadores) “bom”
pela rede da origem ao destino
Abstração de um grafo para
algoritmos de roteamento:
r nos do grafo são
roteadores
r arestas do grafo são os
enlaces físicos
m
custo do enlace: retardo,
financeiro, ou nível de
congestionamento
5
2
A
2
1
r
B
D
3
C
3
1
5
F
1
E
2
caminho “bom”:
m
m
tipicamente significa
caminho de menor custo
outras definições são
possíveis
4: Camada de Rede 4a-18
Classificação de Algoritmos de
Roteamento
Informação global ou
descentralizada?
Global:
r todos roteadores têm info.
completa de topologia, custos
dos enlaces
r algoritmos “estado de enlaces”
Decentralizada:
r roteador conhece vizinhos
diretos e custos até eles
r processo iterativo de cálculo,
troca de info. com vizinhos
r algoritmos “vetor de distâncias”
Estático ou dinâmico?
Estático:
r rotas mudam lentamente
com o tempo
Dinâmico:
r rotas mudam mais
rapidamente
m atualização periódica
m em resposta a mudanças
nos custos dos enlaces
4: Camada de Rede 4a-19
Algoritmo de roteamento de
“Estado de Enlaces”
Algoritmo de Dijkstra
r
r
r
Notação:
r c(i,j): custo do enlace do nó
topologia da rede, custos dos
enlaces conhecidos por todos nós
m realizado através de “difusão
do estado de enlaces”
r
m todos nós têm mesma info.
calcula caminhos de menor custo
de um nó (“origem”) para todos os r
demais
m gera tabela de rotas para
aquele nó
r
iterativo: depois de k iterações,
sabemos menor custo p/ k
destinos
i ao nó j. custo é infinito se
não forem vizinhos diretos
D(V): valor corrente do
custo do caminho da origem
ao destino V
p(V): nó antecessor no
caminho da origem ao nó V,
imediatamente antes de V
N: conjunto de nós cujo
caminho de menor custo já
foi determinado
4: Camada de Rede 4a-20
Algoritmo de roteamento de
“Vetor de Distâncias”
iterativo:
r
r
continua até que não
haja mais troca de
info. entre nós
se auto-termina: não há
“sinal” para parar
assíncrono:
r
r
r
r
r
os nós não precisam
trocar info./iterar de
forma sincronizada!
distribuído:
r
Estrutura de dados: Tabela de
Distâncias
cada nó comunica
apenas com seus
vizinhos diretos
X
cada nós possui sua própria TD
1 linha para cada destino possível
1 coluna para cada vizinho direto
exemplo: no nó X, para destino Y
através do vizinho Z:
D (Y,Z)
distância de X para
= Y, usando Z como caminho
= c(X,Z) + min {DZ(Y,w)}
w
4: Camada de Rede 4a-21
Comparação dos algoritmos EE e VD
Complexidade de mensagens Robustez: o que acontece se
houver falha do roteador?
r EE: com n nós, E enlaces, O(nE)
mensagens enviadas
EE:
r
VD: trocar mensagens apenas
entre vizinhos
m varia o tempo de
convergência
Rapidez de Convergência
r
r
m
nó pode anunciar valores
incorretos de custo de
enlace
m
cada nó calcula sua própria
tabela
VD:
EE: algoritmo O(n**2) requer
O(nE) mensagens
m um nó VD pode anunciar um
custo de caminho incorreto
m podem ocorrer oscilações
m a tabela de cada nó é usada
VD: varia tempo para convergir
pelos outros nós
m podem ocorrer rotas cíclicas
• um erro propaga pela rede
m problema de contagem ao
4: Camada de Rede 4a-22
infinito
Roteamento Hierárquico
Neste estudo de roteamento fizemos uma idealização:
r todos os roteadores idênticos
r rede “não hierarquizada” (“flat”)
… não é verdade, na prática
escala: com > 100 milhões
de destinos:
r
r
impossível guardar todos
destinos na tabela de rotas!
troca de tabelas de rotas
afogaria os enlaces!
autonomia administrativa
r
r
internet = rede de redes
cada admin de rede pode
querer controlar roteamento
em sua própria rede
4: Camada de Rede 4a-23
Roteamento Hierárquico
agregar roteadores em
regiões, “sistemas
autônomos” (SAs)
r roteadores no mesmo
SA usam o mesmo
protocolo de
roteamento
r
m
m
protocolo de
roteamento “intra-SA”
roteadores em SAs
diferentes podem usar
diferentes protocolos
de roteamento intra-SA
roteadores de borda
r
r
r
roteadores especiais no
SA
usam protocolo de
roteamento intra-SA com
todos os demais
roteadores no SA
também responsáveis por
rotear para destinos fora
do SA
m usam protocolo de
roteamento “inter-SA”
com outros roteadores
de borda
4: Camada de Rede 4a-24
Roteamento Intra-SA e Inter-SA
C.b
a
C
Estação
e1
r
b
A.a
roteamento
Inter-SA
entre
B.a
AeB
A.c
a
d
c
b
A
roteamento
Intra-SA no SA A
a
c
B
Estação
e2
b
roteamento
Intra-SA no SA B
Em breve veremos protocolos de roteamento
inter-SA e intra-SA específicos da Internet
4: Camada de Rede 4a-25
Estrutura da Internet: rede de redes
abordagem hierárquica
r provedores (inter)nacionais de
backbone (PNBs)
r
m
m
r
provedores regionais
m
r
p.ex.. Embratel, RNP, IBM
interconexão (peering) privada
bilateral ou em Pontos de Troca
de Tráfego (PTTs)
local
Prov. regional
PNB B
PTT
PTT
PNB A
clientes dos PNBs
provedores locais ou empresas
m
Prov.
clientes dos provedores
regionais
Prov. regional
Prov.
local
4: Camada de Rede 4a-26
Provedor Nacional de Backbone - 1
4: Camada de Rede 4a-27
Provedor Nacional de Backbone - 2
Embratel
http://www.embratel.net.br
4: Camada de Rede 4a-28
Conexões Internacionais
4: Camada de Rede 4a-29
Estrutura da Internet: rede de redes
r
um pacote passa através de diversas redes!
local
ISP
Tier 3
local
local
ISP
Tier-2 ISP
ISP
ISP
ISP
Tier-2 ISP
Tier 1 ISP
Tier 1 ISP
Tier-2 ISP
local
local
ISP
ISP
local
PTT
Tier 1 ISP
Tier-2 ISP
local
ISP
Tier-2 ISP
local
ISP
4: Camada de Rede 4a-30
Roteamento na Internet
r
A Internet Global consiste de Sistemas Autonônomos
(SAs) interligados entre si:
m
m
m
r
SA Folha: empresa pequena
SA com Múltipla Conectividade: empresa grande (sem
trânsito)
SA de Trânsito: provedor
Roteamento em dois níveis:
m
m
Intra-SA: administrador é responsável pela escolha
Inter-SA: padrão único
4: Camada de Rede 4a-31
Hierarquia de SAs na Internet
Inter-AS: roteadores de fronteira (exterior gateways)
Intra-AS: roteadores internos (interior gateways)
4: Camada de Rede 4a-32
Roteamento Intra-SA
r
r
Conhecidos tb como Interior Gateway Protocols (IGP)
Os IGPs mais comuns são:
m RIP: Routing Information Protocol
m OSPF: Open Shortest Path First
m IGRP: Interior Gateway Routing Protocol (proprietário da Cisco)
4: Camada de Rede 4a-33
RIP ( Routing Information Protocol)
Algoritmo vetor de distâncias
r Incluído na distribuição de BSD-UNIX em 1982
r Métrica de distância: Contagem de Saltos (máx = 15)
r
m
Distância infinita = 16 enlaces
Anúncios de Atualização são trocados a cada 30 seg
r Se não for recebido anúncio novo durante 180 seg -->
vizinho/enlace declarados mortos
r
m
m
m
m
m
rotas via vizinho invalidadas
novos anúncios enviados aos vizinhos
na sua vez, os vizinhos publicam novos anúncios (se foram
alteradas as suas tabelas)
informação sobre falha do enlace rapidamente propaga para a
rede inteira
reverso envenenado usado para impedir loops
4: Camada de Rede 4a-34
OSPF (Open Shortest Path First)
“open” (aberto): publicamente disponível
r Usa algoritmo do Estado de Enlaces
m disseminação de pacotes EE
m Mapa da topologia a cada nó
m Cálculo de rotas usando o algoritmo de Dijkstra
r
Anúncio de OSPF inclui uma entrada por roteador
vizinho
r Anúncios disseminados para SA inteiro (via inundação)
r
4: Camada de Rede 4a-35
IGRP (Interior Gateway Routing Protocol)
r
r
r
r
r
Proprietário da CISCO; sucessor de RIP (anos 80)
Vetor de Distâncias, como RIP
Métricas de custo composta (atraso, largura de
banda, confiabilidade, carga, etc)
usa TCP para trocar mudanças de rotas
Roteamento sem loops via Distributed Updating
Algorithm (DUAL) baseado em computação difusa
4: Camada de Rede 4a-36
Roteamento Inter-SA
r
r
Conhecidos tb como Exterior Gateway Protocols (EGP)
O EGP mais comum é o BGP-4
4: Camada de Rede 4a-37
Roteamento inter-SA na Internet: BGP
BGP (Border Gateway Protocol): o padrão de fato
r Protocolo de Vetor de “Caminhos” :
r
m
m
semelhante ao protocolo de Vetor de Distâncias
cada Border Gateway (roteador de fronteira) difunda aos vizinhos
(pares) caminho inteiro (seqüência de SAs) ao destino em função de
políticas
Supomos: roteador X envia seu caminho para roteador W
r
W pode ou não selecionar o caminho oferecido por X
m
r
razões de custo, políticas (não roteia via o SA de um concorrente),
evitar loops.
Note: X pode controlar tráfego de chegada através do
controle dos seus anúncios de rotas aos seus pares:
m
p.ex., se não quero receber tráfego de Z -> não anuncia rotas para Z
4: Camada de Rede 4a-38
Por quê tem diferenças entre
roteamento Intra- e Inter-SA?
Políticas:
Inter-SA: administração quer controle sobre como
tráfego roteado, quem transita através da sua rede.
r Intra-AS: administração única, logo são
desnecessárias decisões políticas
r
Escalabilidade:
r
roteamento hierárquico economiza tamanho de tabela
de rotas, reduz tráfego de atualização
Desempenho:
Intra-AS: pode focar em desempenho
r Inter-AS: políticas podem ser mais importantes do
que desempenho
4: Camada de Rede
r
4a-39