PDF de programación - Arquitectura de routers ¿Cómo funcionan los routers?

REDES
Área de Ingeniería Telemática

Arquitectura de routers

¿Cómo funcionan los routers?

Area de Ingeniería Telemática

http://www.tlm.unavarra.es

Redes

4º Ingeniería Informática

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


S
E
D
E
R

e
d



a
e
r
Á

Hoy...

1. Introducción a las redes
2. Encaminamiento
3. Transporte extremo a extremo
4. Arquitectura de conmutadores de paquetes
5. Tecnologías para redes de área local
6. Conmutación de circuitos
7. Tecnologías para redes de área extensa y última milla

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


S
E
D
E
R

e
d



a
e
r
Á

Hoy...

1. Introducción a las redes
2. Encaminamiento
3. Transporte extremo a extremo
4. Arquitectura de conmutadores de paquetes
5. Tecnologías para redes de área local
6. Conmutación de circuitos
7. Tecnologías para redes de área extensa y última milla

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


S
E
D
E
R

e
d



a
e
r
Á

Problemas en el nivel de red

• Problema de enrutamiento:

Cómo sé a qué vecino debo reenviar?

• Construcción de routers

Se pueden construir conmutadores/encaminadores de paquetes?
Cómo de rápidos/eficientes? cuántos paquetes por segundo puedo
reenviar? Qué funcionalidades necesitan?

2 entradas
de 10Mbps?

10 entradas
de 10Gbps?

¿Qué pinta tiene un router?

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

S
E
D
E
R

I


e
d



a
e
r
Á

Cisco GSR 12416

19”

~0.5m

Juniper M160
~0.5m

19”

6ft
~1.8m

Capacity: 160Gb/s
Power: 4.2kW
Full rack

3ft
~0.9m

Capacity: 80Gb/s
Power: 2.6kW
Half-a-rack

2ft

~0.6m

2.5ft
~0.8m

5

¿Qué pinta tiene un router?

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

S
E
D
E
R

I


e
d



a
e
r
Á

Cisco CSR-3

Capacity: 322Tb/s
Power: ??
Varios racks
Desde $90000 :-)

6

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


S
E
D
E
R

e
d



a
e
r
Á

Arquitectura básica de un router IP

• Plano de control

– Los protocolos de enrutamiento y otra información de control pueden

enviar y recibir información de la red

– Construyen la tabla de rutas y configuran el plano de datos

• Plano de datos

– Los paquetes que pasan por el router deben atravesarlo a la máxima

velocidad posible

Routing
Protocols

Routing
Table

Forwarding

Table

Switching

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

S
E
D
E
R

Arquitectura básica de un router IP

• Plano de datos

– No es una entrada y una salida sino varias entradas y salidas

Routing
Protocols

Routing
Table

Switching

Forwarding

Table

Forwarding

Table

Forwarding

Table

Forwarding

Table

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


S
E
D
E
R

e
d



a
e
r
Á

Proceso por paquete

¿Qué hay que hacer por cada paquete?

• Recibir a nivel de enlace.
• Lookup: buscar la dirección destino del paquete en la tabla

de reenvío (forwarding) para identificar por donde debe salir

• Header processing: manipular cabecera IP: decrementar

TTL, recalcular checksum

• Switching: llevar el paquete a la tarjeta de salida

correspondiente

• Buffering: almacenar el paquete durante los tiempos que

deba esperar

• Transmitir a nivel de enlace

• La velocidad a la que se pueda hacer da las prestaciones

Puertos de entrada

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


S
E
D
E
R

e
d



a
e
r
Á

Nivel físico:
Recepción de bits
Nivel de enlace:
por ejemplo
Ethernet

Decentralized switching:
• A partir de la dirección de destino buscar el
puerto de salida en la tabla de reenvios (se
mantiene una copia de la tabla de rutas en la
memoria del puerto de entrada)
objetivo: procesar paquetes entrantes a
velocidad de linea

•

• Cola de entrada: si los paquetes llegan a mas
velocidad que la velocidad de entrada a matriz
de conmutación

10

Tipos de conmutación

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

S
E
D
E
R

I


e
d



a
e
r
Á

11

a
c
i
t

Puertos de salida

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


S
E
D
E
R

e
d



a
e
r
Á

• Buffer (cola de salida)necesario si los paquetes
pueden llegar a mas velocidad que la del puerto de
salida desde la matriz de conmutación

• Planificación (Scheduling) elige entre los paquetes

disponible para transmision (FIFO, u otras?)

12

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


S
E
D
E
R

e
d



a
e
r
Á

Las dificultades

• En media debemos hacer todo el proceso para cada
paquete en el tiempo en el que la tarjeta de red
recibe el siguiente
De lo contrario estamos acumulando paquetes

• Tiempo para enviar un paquete de 29+14bytes

(ping de 1 byte) a 10Gbps : 34ns

Address lookup

• Buscar una dirección IP en una tabla de rutas

Longest prefix match no vale con encontrar uno que cumpla
La tabla puede tener ~150000 entradas

• Se usan estructuras prefix tree

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


S
E
D
E
R

e
d



a
e
r
Á

0

0

0

1

1

Ejemplo: almacena los prefijos
{*,000*,0000*,0001*,100*,110*,111*}
busquedas de tipo
00010010 -> 0001*
10101001 -> 1*
00101010 -> *
11010101 -> 110*
Se hace en hardware (NSE network search engines)
(Se pueden encontrar circuitos que hacen 100000000
busquedas por segundo ~10ns)

1

0

0

0

1

0

Almacenamiento y cálculo

• No es trivial almacenar y recuperar paquetes en 30ns

velocidades de acceso a memoria?
• No es trivial manipular la cabecera

Packet Processing Power

10000

1000

2x / 18 months

s
t
l
u
s
e
r

U
P
C

100

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


S
E
D
E
R

e
d



a
e
r
Á

•

•

Hardware especifico para routers de alta velocidad
Problemas con la ley de Moore
– Velocidad de procesado se duplica cada 18 meses
– Capacidad de la fibra se duplica cada año
– Velocidad de la memoria solo se multiplica por 1.1 cada 18 meses


t
n
5
9
c
e
p
S

1
1985

0,1

10

I

1990

1995

2000

Single Fiber Capacity

(commercial)
≥ 2x / year

El tráfico de Internet crece más deprisa
Capacidad típica de los routers comerciales
Capacidad 1992 ~ 2Gb/s
Capacidad 1995 ~ 10Gb/s
Capacidad 1998 ~ 40Gb/s
Capacidad 2001 ~ 160Gb/s
Capacidad 2003 ~ 640Gb/s
Media approx 2.2x / 18meses

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

S
E
D
E
R

Distribuyendo la carga

•
•

Siempre podemos usar mas routers e interconexiones para distribuir el tráfico
Interesa más tener pocos routers de gran potencia
– Gestión más simple
– Menos consumo y menos coste: lo que cuesta son los puertos

POP con routers grandes

POP con routers pequeños

•
•

Puertos: precio >$50k, consumo > 400W.
Alrededor de 50-60% de los puertos es para interconexión

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

S
E
D
E
R

Switching

• Problema fundamental
• ¿Como enviamos los paquetes de la entrada a la salida

correspondiente?
Matriz de conmutación / switch fabric

• El problema aparece en conmutación de circuitos primero
– En telefonía es más fácil el circuito se establece con
antelación. Una vez establecido todos los datos que
llegan por un puerto de entrada van al mismo puerto
de salida hasta que se libera

• Necesitamos el mismo tipo de sistemas pero que sean
capaces de cambiar de estado en el tiempo de un
paquete
– La velocidad a la que los paquetes atraviesen esta

matriz de conmutación es fundamental

17

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


S
E
D
E
R

e
d



a
e
r
Á

Switching architectures

• Memoria central y bus

– Ordenador tradicional conmutación bajo control de la CPU
– El paquete se copia del puerto de entrada a la memoria
– El paquete se copia de la memoria al puerto de salida
– Gran flexibilidad y fácil de programar
– El paquete pasa 2 veces por el bus
– La máxima velocidad a la que reenviamos paquetes es la mitad de la velocidad

del bus

– Los paquetes deben esperar en las tarjetas de entrada (Contención)

Shared Backplane

CPU

Route
Table

Buffer
Memory

CPU

Line Interface

M

e

m

ory

– Routers de primera generación

Tipica velocidad agregada < 0.5Gbps

Line

Interface

MAC

Line

Interface

MAC

Line

Interface

MAC

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

S
E
D
E
R

Switching architectures

• Bus compartido y puertos independientes

– El paquete se copia de la memoria del puerto de entrada a la del puerto de

salida

– Más complejo
– El paquete pasa 1 vez por el bus. La máxima velocidad agregada es la del

bus

– Routers de segunda generación

Tipica velocidad agregada < 5Gbps

CPU

Route
Table

Buffer
Memory

– Pero en un instante como mucho

pasa 1 paquete por el bus
si otro puerto de entrada tiene un paquete
debe esperar...

Line
Card
Buffer
Memory
Fwding
Cache
MAC

Line
Card
Buffer
Memory
Fwding
Cache
MAC

Line
Card
Buffer
Memory
Fwding
Cache
MAC

19

Switching architectures

• Tercera generacion ++

– Matriz de conmutación más compleja capaz de tener varias transferencias

a la vez (switched backplane)

–

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


S
E
D
E
R

e
d



a
e
r
Á

CPU

Line Interface

e

M

m

ory

CPU
Card

Routing
Table

Line
Card
Local
Buffer
Memory
Fwding
Table
MAC

Line
Card
Local
Buffer
Memory
Fwding
Table
MAC

20

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

S
E
D
E
R

Switching

•

Switch fabrics capaces de intercambiar varios
flujos al mismo tiempo

• Crossbar (space-switching)

– N veces mas rapido que un bus
– Pero hay problemas si dos quieren enviar un
paquete a la vez al mismo destino
(contencion)
O bien el acceso al puerto de salida es N
veces más rápido o bien puede haber
bloqueo
• Broadcast

– N veces mas rapido que un bus
– El acceso al puerto de salida N veces mas

rápido o bloqueo

• Necesita muchos recursos
•

El cuello de botella es la entrada al puerto de
salida
Escalan mal con el numero de puertos

•

21

a
c
i
t

l



á
m
e