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

¿Cómo funcionan los routers?

Area de Ingeniería Telemática

http://www.tlm.unavarra.es

Arquitectura de Redes, Sistemas y Servicios

3º Ingeniería de Telecomunicación

Temario

Introducción

1. 
2.  Arquitecturas, protocolos y estándares
3.  Conmutación de paquetes
4.  Conmutación de circuitos
5. 
6.  Control de acceso al medio en redes de área local
7.  Servicios de Internet

Tecnologías

2

Temario

• 
• 

1. 
2. 
3. 

4. 
5. 
6. 
7. 

Introducción
Arquitecturas, protocolos y estándares
Conmutación de paquetes

Principios
Problemas básicos
• 
• 
• 
• 
• 

Como funcionan los routers (Nivel de red)
Encaminamiento (Nivel de red)
Transporte fiable (Nivel de transporte en TCP/IP)
Control de flujo (Nivel de transporte en TCP/IP)
Control de congestión (Nivel de transoporte en TCP/IP)

Conmutación de circuitos
Tecnologías
Control de acceso al medio en redes de área local
Servicios de Internet

3

En próximas clases…

  Enrutamiento
  Algoritmos y técnicas de enrutamiento

  ¿Cómo construyo la tabla de rutas?

Hoy
  Como funciona un router
  ¿Qué otros problemas hay que resolver para
hacer un router aparte de construir la tabla de
rutas?

4

Material

  Capítulo 4 de
Kurose & Ross,
“Computer Networking a top-down
approach featuring the Internet”
Addison Wesley

  Capítulo 9 de Keshav (poco)

  Presentación basada en transparencias de AsstProf.
Bhichate Chiewthanakul basadas a su vez en las de
Profs. Nick McKeown and Balaji Prabahakar (Stanford)
además de transparencias basadas en el libro de Kurose

5

Contenido

  Background

  Qué es un router?
  Por qué necesitamos routers más rápidos?
  Por qué son dificiles de construir?

  Arquitecturas y técnicas

  Evolución de arquitecturas de routers.
  Búsqueda de dirección IP.
  Almacenamiento de paquetes.
  Conmutación.
  Planificación.

6

¿Qué es un router?

A

B

C

R3

R1

D

R2

Destino
D
E
F

Siguiente
R3
R3
R5

R4

R5

D

E

F

7

¿Qué es un router?

R3

R1

A

1

4

16

R4

32

B



s
e
t
y
b

0
2

C

Ver

T.Service

HLen
Fragment ID

TTL

Flags

Total Packet Length
Fragment Offset
Header Checksum

D
Protocol
R2
Source Address
Destination
Next Hop
Destination Address
D
R3
Options (if any)
E
R3
F
R5

Data

R5

D

E

F

8

¿Qué es un router?

R3

A

B

C

R1

R2

R4

R5

D

E

F

9

Puntos de presencia

(POPs Points of presence)

POP2

POP1

POP3

POP4

POP5

POP6

POP7

POP8

A

B

C

D

E

F

10

Donde son necesarios los routers de

altas prestaciones

(2.5 Gb/s)

R1

R2

(2.5 Gb/s)

R6

R5

R9

R8

R13

(2.5 Gb/s)

R4

R3

R10

R14

R15

R7

R12

R11

R16

(2.5 Gb/s)
11

¿Qué pinta tiene un router?

Cisco GSR 12416

19”

~0.5m

Juniper M160

19”

~0.5m

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

12

El mercado de routers

  Según Dell’Oro (Feb. 17, 2005):

  $1.2 billion in 2004 (up 66%)
 

Includes high-end (10Gbps) router market

  Según Infonetics (March 2, 2005):

  $6.1 billion in 2004 (up 26%)
 

Includes IP core/edge routers and multiservice core/edge
switches

  Mercado de routers de núcleo

  Relativamente pequeño (en comparación con el mercado de
routers para empresas), pero da experiencia a las compañias

  Fabricantes: Cisco, Juniper, Avici, Nortel, Lucent, Alcatel,

Chiaro, Huawei, etc.

13

Router Market

Source: Infonetics (Nov. 2004)

14

Arquitectura básica de un router IP

Routing
Protocols
Routing
Table

Forwarding

Table

Switching

Plano de control

Plano de datos
Procesado
por paquete

15

Proceso por paquete en un Router IP

1.  Aceptar paquetes por las lineas de entrada

2. 

Lookup: búsqueda de la dirección de destino del
paquete en la tabla de reenvío (para identificar puerto
de salida).

3.  Header Processing: Manipulación de la cabecera IP:

decrementar TTL, recalcular checksum.

4.  Switching: Enviar el paquete al puerto de destino

correspondiente.

5.  Buffering: Almacenar paquete en la cola.

6. 

Transmitir paquete en la linea de salida.

16

Arquitectura de un router genérico

Data Hdr

Header Processing

Lookup

IP Address

Update
Header

Queue
Packet

Data Hdr

IP Address Next Hop

~1M prefixes
Off-chip DRAM

Address
Table

Buffer
Memory

~1M packets
Off-chip DRAM

17

Arquitectura de routers

Dos funciones básicas de los routers:
  Correr protocolos/algorimtos de enrutamiento (RIP, OSPF, BGP)
  Dirigir paquetes de los puertos de entrada a los puertos de salida

(forwarding)

18

Arquitectura de routers

Data Hdr

Header Processing
Lookup
Update
Header

IP Address

Address
Table

Data Hdr

Header Processing
Lookup
Update
Header

IP Address

Data Hdr

Address
Table

Header Processing
Lookup
Update
Header

IP Address

Address
Table

Buffer
Manager

Buffer
Memory

Buffer
Manager

Data Hdr

Buffer
Memory

Buffer
Manager

Buffer
Memory

Data Hdr

Data Hdr

19

Puertos de entrada

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: porcesar 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

20

Tipos de conmutación

21

Conmutación por memoria

Primera generación de routers:
  ordenador tradicional con conmutación bajo control de
la CPU
  el paquete se copia a la memoria del sistema al
recibirlo
  velocidad limitada por el ancho de banda a memoria
(2 accesos al bus por paquete)

Memory

Input

Port

Output

Port

System Bus

22

Conmutación via Bus

  El paquete se copia de la memoria
del puerto de entrada a la memoria
del puerto de salida a través de un
bus compartido

  Contención en el bus:

  Si el bus está ocupado el paquete espera

en la memoria del puerto de entrada
(colas a la entrada)

  Velocidad de conmutación limitada por el

bus

  Con bus de 1 Gbps, (Cisco 1900): es

suficiente velocidad para accesos y
routers de empresa (pero no para
regionales o backbone)

23

Conmutación via red de interconexión

  Superar las limitaciónes de un bus
  Redes Banyan y otras redes de interconnexión

pensadas en principio para conectar procesadores
en maquinas multiprocesador

  Diseño avanzado: fragmentar los paquetes en celdas

de longitud fija, y conmutar las celdas por la matriz
de conmutación.

  Cisco serie 12000: conmuta a Gbps a traves de la

red de interconexión

24

Puertos de salida

  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?)

25

Contenido

  Background

  Qué es un router?
  Por qué necesitamos routers más rápidos?
  Por qué son dificiles de construir?

  Arquitecturas y técnicas

  Evolución de arquitecturas de routers.
  Búsqueda de dirección IP.
  Almacenamiento de paquetes.
  Conmutación.
  Planificación.

26

Por qué necesitamos routers más rápidos?

1.  Para evitar que los routers se conviertan

en el cuello de botella de Internet

2.  Para aumentar la capacidad de los

puntos de presencia (POP) y reducir su
coste, tamaño y consumo

27

Por qué necesitamos routers más rápidos?
Evitar que los routers sean el cuello de botella

Single Fiber Capacity

(commercial)
≥ 2x / year

Packet Processing Power

10000

s
t
l
u
s
e
r

U
P
C


t
n
I
5
9
c
e
p
S

1000

100

10

1
1985

0,1

2x / 18 months

1990

1995

2000

Source: SPEC95Int & Coffman and Odlyzko.

28

Por qué necesitamos routers más rápidos?
2: Reducir coste, consumo y complejidad de POPs

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.

29

¿Por qué es dificil hacer routers rápidos?

1.  Es difícil seguir la ley de Moore:

  El cuello de botella es la velocidad de la

memoria

  La velocidad de la memoria no sigue la ley

de Moore

30

¿Por qué es dificil hacer routers rápidos?

Velocidad de la DRAM comercial

1. 

1986

1989

1992

1983

1980

It’s hard to keep up with Moore’s Law:
1995
1000
  The bottleneck is memory speed.
  Memory speed is not keeping up with

1998

100
Moore’s Law.
10

1.1x / 18 months

1

0.1

Moore’s Law
2x / 18 months

i

)
s
n
(

e
m
T

s
s
e
c
c
A

0.01

0.001

2001

31

¿Por qué es dificil hacer routers rápidos?

1.  Es difícil seguir la ley de Moore:

  El cuello de botella es la velocidad de la

memoria

  La velocidad de la memoria no sigue la ley

de Moore

2.  La ley de Moore no es suficiente:

  Los routers necesitan mejorar más rápido

que la ley de Moore

32

Prestaciones de routers y la ley de Moore

Crecimiento de la capacidad de routers

comerciales:
  Capacidad 1992 ~ 2Gb/s
  Capacidad 1995 ~ 10Gb/s
  Capacidad 1998 ~ 40Gb/s
  Capacidad 2001 ~ 160Gb/s
  Capacidad 2003 ~ 640Gb/s

Crecimiento medio: 2.2x / 18 months.

33

Contenido

  Background

  Qué es un router?
  Por qué necesitamos routers más rápidos?
  Por qué son dificiles de construir?

  Arquitecturas y técnicas

  Evolución de arquitecturas de routers.
  Búsqueda de dirección IP.
  Almacenamiento de paquetes.
  Conmutación.
  Planificación.

34

Routers de primera generación

Shared Backplane

CPU

Route
Table