Encaminhadores IP
Sistemas Telemáticos 2002/2003
LESI
Grupo de Comunicações por
Computador
Departamento de Informática
Universidade do Minho
Fontes utilizadas
• Alguns materiais de
–
–
–
–
Scott Karlin and Larry Peterson
Zhenhai Duan
N. Mckeown @ stanford.edu;
S. Keshav @ cornell.edu
• Artigo
– IP Routers Architecture: An Overview , James
Aweya, acessível na net.
A Internet é um grafo de
encaminhadores !
RouterIP de Núcleo
O Núcleo da Internet
Router de IP de
Periferia
Qual o aspecto dos
comutadores /encaminhadores?
Encaminhadores
De acesso
e.g. ISDN,
ADSL
Encaminhador de
Núcleo
Comutador
ATM de
Núcleo
Componentes dum
Encaminhador Genérico
Processamento de um pacote num
encaminhador IP
1. Aceitar o pacote de uma ligação de entrada
2. Localizar o endereço de destino do pacote na
tabela de reenvio, para identificar a(s) porta de
saida .
3. Manipular o cabeçalho do pacote: decrementar o
TTL e calcular a soma de verificação do
cabeçalho.
4. Enviar o pacote para a(s) portas de saída.
5. Colocar o pacote na fila de espera
6. Transmitir o pacote pela linha de saída
Interior dum Encaminhador IP
melhor esforço
Outra visão dum Encaminhador IP
Protocolos de
Encaminhamento
Tabela de
Encaminhamento
Tabela de
Comutação
expedição
Plano de Controlo
Plano de Dados
Processamento por
Pacote
Componentes Arquitecturais Básicos
Plano de dados: processamento por pacote
1. Ingresso
Tabela de
Expedição
Decisão de
expedição
Tabela de
Expedição
Decisão de
expedição
Tabela de
Expedição
Decisão de
expedição
2. Interconexão
3. Egresso
Interconexões
Duas Técnicas Básicas
Filas de Espera de
Entrada
Normalmente uma
switch fabric não bloqueante
(e.g. crossbar)
Filas de Espera de
Saída
Normalmente um barramento rápido
Interconexões
Filas de Espera de Saída
Filas de Saída
Individuais
Memória centralizada
partilhada
LB Memória = 2N.R
1
2
N
1
2
LB da Memória = (N+1).R
N
Interconexões
Comutação via Memória
Partilhada
Inúmeros trabalhos
provaram e tornaram
possível:
Entrada 1
Entrada 2
Entrada N
– Equidade(Fairness)
– Garantia de atraso
Saída
1
– Controlo de jitter
– Garantia de Perdas
– Garantias estatísticas
Saída
2 simples
Um buffer
em memória
alocado dinamicamente :
N escritas por tempo de célula
N leituras por tempo de célula
Limitado pela largura de banda
da memória
Saída N
Filas de Espera de Saída
Quão rápida pode ser a memória partilhada?
SRAM de 5 ns
Memória
Partilhada
1
2
• 5ns por operação de memória
• 2 operações de memória por pacote
• Portanto até um máximo de
160Gb/s
• Na prática próximo de 80Gb/s
N
Barramento de 200 byte
Interconexões
Dados de Entrada
Filas de Espera de Entrada com Crossbar
configuraão
LB Memória = 2R
Arbiter
Dados de Saída
Fila de Espera de Entrada
Atarso
Head of Line Blocking
Carga
58.6%
100%
Head of Line Blocking
Fila de Espera de Entrada
Filas de Espera de Saída Virtuais
Fila de Espera de Entrada
Atraso
Filas de Espera de Saída Virtuais
Carga
100%
Fila de Espera de Entrada
Filas de Espera de Saída Virtuais
LB Memória = 2R
Arbiter
Complexo !
Engenho de Expedição
Pacote
dados
cabeçalho
Router
Endereço
de destino
Estrutura de Dados
para localização do
encaminhamento
Tabela de Expedição
Rede destino
Porta
65.0.0.0/8
3
128.9.0.0/16
1
149.12.0.0/19
7
Porta de
saída
Ex. de Tabela de Expedição
Prefixo IP de Destino
Porta de saída
65.0.0.0/ 8
3
128.9.0.0/16
142.12.0.0/19
Tamanho do
Prefixo
1
7
Prefixo IP : 0-32 bits
65.0.0.0/8
128.9.0.0/16
128.9.16.14
224
65.0.0.0
65.255.255.255
0
142.12.0.0/19
232-1
Prefixos podem sobrepor-se
Maior prefixo
que unifique
128.9.176.0/24
128.9.16.0/21 128.9.172.0/21
65.0.0.0/8
0
128.9.0.0/16
128.9.16.14
142.12.0.0/19
232-1
Lookup de encaminhamento: Encontre o maior
prefixo que unifique (i.e. a rota mais específica)
entre todos os prefixos que unifiquem com
endereço de destino.
Comprimento do
Prefixo
Dificuldade da unificação com o
prefixo mais longo
Busca bi-dimensional:
- Comprimento do prefixo
- Valor do Prefixo
32
24
128.9.176.0/24
128.9.16.0/21
8
65.0.0.0/8
128.9.172.0/21
142.12.0.0/19
128.9.0.0/16
128.9.16.14
Valores de prefixo
Lookup da Tabela de
Encaminhamento
• Não é nada fácil!
• A operação de busca não é uma unificação
exacta
– O lookup directo precisa de 4G entradas (32
bits no endereço IP)
– Unificação com o maior prefixo
• Tabelas de Hash
• Árvores balanceadas
Número de Prefixos
Tamanho da Tabela de
Expedição
100000
90000
80000
70000
60000
50000
10,000/ano
40000
30000
20000
10000
0
95
96
97
Ano
98
Fonte http://www.telstra.net/ops/bgptable.html
99
00
Trees e Tries
Binary Search Tree
<
>
>
<
N entries
>
log2N
<
Binary Search Trie
0
0
1
1
010
0
1
111
Trees and Tries
Multiway tries
16-ary Search Trie
0000, ptr
0000, 0
1111, ptr
000011110000
1111, ptr
0000, 0
1111, ptr
111111111111
Interiores dum Encaminhador IP
com QOS
Componentes Arquitecturais
Básicos dum Router com QoS
Controlo de Congestão
Controlo
de Admissão
Reservas
Controlo
Encaminhamento
Policiamento Comutação
Escalonamento
da Saída
Fluxo de
dados
processamento
por pacote
Componentes arquitecturais básicos
Percurso de dados: processamento por pacote
1. Ingresso
Tabela de
classificação
2. Interconexão
3. Egresso
Tabela de
Expedição
Policiamento
& Contrlo de
Accessos
Decisão de
Expedição
Tabela de
classificação
Tabela de
Expedição
Policiamento
& Contrlo de
Accessos
Decisão de
Expedição
Tabela de
classificação
Tabela de
Expedição
Policiamento
& Contrlo de
Accessos
Decisão de
Expedição
Limitação: LB Memória
Limitação: LB Interconexão
Energia & Arbitragem
Limitação: LB Memória
Evolução dos
Encaminhadores IP
Routers IP de Primeira Geração
Shared Backplane
Buffer
Memory
CPU
DMA
DMA
DMA
Line
Interface
Line
Interface
Line
Interface
MAC
MAC
MAC
 A maioria dos switches Ethernet e routers mais baratos
O
Estrangulamento pode ser o CPU, barramento de I/O ou
host adaptor

O que é mais caro? Barramento? Memória? Interface? CPU?
Routers IP de Primeira Geração
Estrutura de Filas: Memória Partilhada
Entrada 1
Entrada 2
Entrada N
Inúmeros trabalhos
provaram e tornaram
Output
1
possível:
– Equidade(Fairness)
– Garantia de atraso
– Controlo de jitter
– Garantia de Perdas
Output
2 estatísticas
– Garantias
Um buffer simples em
memória alocado
Output
N
dinamicamente
:
N escritas per “cell” time
N leituras per “cell” time.
Limitado pela largura de
banda da memória
Routers IP de Segunda Geração
Buffer
Memory
CPU
DMA
DMA
DMA
Line
Card
Local
Buffer
Memory
Line
Card
Local
Buffer
Memory
Line
Card
Local
Buffer
Memory
MAC
MAC
MAC

Correspondência de portas nas placas de interface

Alta % de acertos na cache local para lookups

O que é mais $? Bus? Memória? Interface? CPU?

Routers IP de Segunda Geração
Estruturas combinadas de filas de entrada e saída
1 escrita por
tempo de célula
Taxa de E/L determinada pela
velocidade do bus
Bus
1 leitura por
tempo de célula
Switches/Routers de 3ª Geração
Switched Backplane
Line
Card
Disponibiliza

CPU
Card
Line
Card
Local
Buffer
Memory
Local
Buffer
Memory
MAC
MAC
percursos paralelos (switching fabric)
O que é mais $? Bus? Memória, CPU?
Switches/Routers de 3ª Geração
Estrutura de filas de espera
1 escrita por tempo
de célula
Taxa de E/L
determinada pela capacidade a
fabric speedup
Switch
Arbiter
Tipicamente <50Gb/s capacidade agregada
1 leitura por tempo de
célula
Routers/Switches de 4ª Geração
Ligações
ópticas
100’s
of feet
Switch Core
Linecards
Separação física entre o núcleo de
comutação e as cartas de linha
• Distribui energia por vários armários.
• Permite todo armazenamento (buffering)
colocado nas placas de linha:
– Reduz energia.
– Coloca a complexidade (escalonamento,
gestão de buffers, política de descarte de
pacotes, etc…) na placa de linha
Routers/Switches de 4ª Geração
Protocolo
LCS
Ligações
ópticas
100’s
of feet
Switch Core
Linecards
Routers/Switches de 4ª Geração
Estruturas de filas de espera
1 escrita por tempo
de célula
Filas de espera de saída virtuais
Velociadade de Escrita/leitura
Determin<das pela velocidade da switching fabric
Lookup
&
Política de
descrate
Lookup
&
Política de
descrate
Lookup
&
Política de
descrate
Linecard
1 leitura por
tempo de célula
Escalonamento
de saída
Switch
Fabric
Escalonamento
de saída
Switch
Arbitration
Switch Core
(Bufferless)
Tipicamente <5Tb/s capacidade agregada
Escalonamento
de saída
Linecard
Problemas dos Fabricantes
• Rápida expedição (lookup de rotas)
• Identificação de Fluxos
– Percurso rápido de expedição
• Suporte de QoS
– Routers de núcleo, empresa ou acesso
– A simplicidade é a chave do sucesso
• Fiabilidade(estabilidade) de routers de alta
velocidade
– Energia dual
– Percursos de dados duplicados
• Facilidade de configuração
– Má configuração é outro problema sério
• Possibilidade de contabilização