PDF de programación - Routers de Altas Prestaciones

Routers de Altas Prestaciones
Routers de Altas Prestaciones

José Duato
José Duato
Román García
Román García

DISCA

Departamento de Informática de

Sistemas y Computadores

Índice

• Marco operativo de un router de altas prestaciones
• Bloques funcionales
•

IP forwarding
– Direccionamiento IP

• Subnetting
• Supernetting

– Algoritmos y estructuras de datos para consulta rápida en tabla forwarding

• Trie
• Patricia

– Otros esquemas de direccionamiento

IPX / IPX+

•
• CNLP
IPv6
•

BIBLIOGRAFIA

2.

1. R. PERLMAN, Interconections (2º edition): Bridges, Routers, Switches and

Internetworking Protocols. Ed: Addison-Wesley 1999.
L. PETERSON & B.S. DAVIE, Computer Networks: a systems approach (2º edition),
Morgan Kaufmann Publishers, 2000.

3. D. COMER, Internetworking with TCP/IP (vol-1). 4ªEdición, Ed: Prentice-Hall, 2000.
4.

5. 6. … http://www.redes.disca.upv.es/rap

1

2

Routers de altas prestaciones (RAP)

SONET / RPR / ...

DWDM:Dense Wavelength Division Mxing
• Multiplexación de varias señales de diferente longitud de onda en

una única fibra.

• Cada señal puede tener diferentes velocidades (p.ej. OC–3/12/24,

etc.) y diferentes formatos (SONET, ATM, etc.)
– Ejemplo: una red DWDM con un mix de señales SONET que funcionan a
OC–48 (2.5 Gbps) y OC–192 (10 Gbps) puede alcanzar capacidades de
más de 40 Gbps.

• Se prevé que en el futuro DWDM podrá llevar hasta 80 señales de

tipo OC–192, por un total de 800 Gbps.

3

4

DWDM

5

6

Inyección de datos en fibra

7

8

Synchronous Optical Network (SONET)

Multiplexación TDM síncrona

• Elementos:

– Multiplexores n:1 y 1:n
– Convertidores y repetidores.
– Multiplexores ADM.

34 RDSI

PRI

M
U
X

STS-1

STS-3

STS-1

M
U
X

STS-1

ADM

M
U
X

Convertidor
electro-óptico

STS-12

OC-12

SONET: Tasas de datos

• Canal básico SONET: STS-1

– Una trama de 810 bytes cada 125useg (51.84Mbps)
– El resto de canales es múltiplo del básico

SONET

Optico
OC-1
OC-3
OC-9
OC-12
OC-18
OC-24
OC-36
OC-48
OC-192

Eléctrico
STS-1
STS-3
STS-9
STS-12
STS-18
STS-24
STS-36
STS-48
STS-192



SDH
Optico



STM-1
STM-3
STM-4
STM-6
STM-8
STM-12
STM-16
STM-64

Tasa de datos

Mbps
51.84
155.52
466.56
622.08
933.12
1202.688
1866.24
2488.32
9953,28

9

10

SONET vs Resilient Packet Ring (RPR)

11

12

Detalle de conexión de routers

physical location where an interexchange carrier installed equipment to interconnect with a local exchange carrier

13

14

Packet Over Sonet

(6 marzo del 2001)(Fuente: Juniper Networks)

15

16

Juniper M40

17

18

Abilene Architecture: Core

• Router Nodes located at Qwest PoPs

– Cisco 12008 GSR
– ICS Unix PC: IPPM and Network Mgmt
– Cisco 3640 Remote Access for NOC
– 100BaseT LAN and ‘console port’ access
– Remote 48v DC Power Controllers
Initially, ten Router Nodes
– Seattle, Sacramento, Los Angeles, Denver,

Kansas City, Houston, Indianapolis, Cleveland,
New York City, Atlanta

– And, coming this Fall - Washington, DC
Interior lines connect core nodes
– OC-12 and OC-48 Sonet
– IP-over-Sonet interfaces

•

•

19

20

21

22

Routers de altas prestaciones (RAP)

• Encaminamiento “wired-speed”

– switches (ATM – Ethernet)

• tramas (celdas) de tamaño fijo
• búsqueda en tablas con direcciones de tamaño fijo

– routers mas complejo

• paquetes de tamaño variable
• longest-match lookups

• Evolución de Internet

– best-effort service fiable (QoS) MPLS

23

24

MPLS

Route At Edge, Switch In Core

IP

IP

#L1

IP #L2

IP #L3

IP

IP Forwarding

LABEL SWITCHING

IP Forwarding

LABEL SWITCHED PATH (vanilla)

#216

#612

#5

#14
#99
#963

#311
#311
#311

#963

#14

#99

#462

#311

25

26

HOP-BY-HOP(Vanilla) LDP

#216

#612

#5

#14

#99

#963

#462

#311

- Ultra fast, simple forwarding a.k.a switching
- Follows same route as normal IP datapath
- So like IP, LDP will over-utilize best paths and
under-utilize less good paths.

Label Switched Path (Two Types)

#216

#427

#18

#612

#5

#819

#963

#311

#77

#462

#14

#99

Two types of Label Switched Paths:

•
•

Hop by hop (“Vanilla” LDP)
Explicit Routing (LDP+”ER”)

27

28

Índice

• Marco operativo de un router de altas prestaciones
• Bloques funcionales
•

IP forwarding
– Direccionamiento IP

• Subnetting
• Supernetting

• Trie
• Patricia

IPX / IPX+

•
• CNLP
IPv6
•

– Algoritmos y estructuras de datos para consulta rápida en tabla forwarding

– Otros esquemas de direccionamiento

RAP: Bloques funcionales

• 2 TAREAS FUNDAMENTALES:

1) Routing
2) Packet forwarding

• 4 ELEMENTOS ESENCIALES:

1) Routing software

routing protocols (OSPF, BGP4,…)
routing tables
+ system control

2) Packet processing

de-encapsulado
longest-match route
encolado en salida
re-encapsulado

3) Switch fabric

4) Line cards

mover paquetes inout

crossbar, banyan, Clos, …

Adaptar a N-1 y N-2

SONET, ATM, 10GE,…

29

30

Juniper M40

Índice

• Marco operativo de un router de altas prestaciones
• Bloques funcionales
•

IP forwarding
– Direccionamiento IP

• Subnetting
• Supernetting

• Búsqueda binaria
• Trie
• Patricia

– Algoritmos y estructuras de datos para consulta rápida en tabla forwarding

– Otros esquemas de direccionamiento

IPX / IPX+

•
• CNLP
IPv6
•

31

32

IP forwarding

• Hosts y routers realizan encaminamiento indirecto (a través de otros
routers)

• Frecuentemente hosts sólo utilizan un router (default), pero en
general hosts y routers pueden hacer uso de múltiples routers

• Pregunta : ¿ Que router (next-hop) usar ?

• ¿Cómo se informa un router de cual es el mejor camino a usar ?

• Si la tabla de encaminamiento es muy grande…¿Qué algoritmo
y que estructura de datos son necesarios para que un router
encamine eficientemente a su next-hop ?

33

IP forwarding: Tablas de encaminamiento

• Hosts y routers mantienen tablas que
contienen la información de encaminamiento

• Siendo precisos…

• Tablas de routing usadas para calcular

rutas óptimas

• Tablas de forwarding utilizadas para

consultar el next-hop

• Las tablas de forwarding se generan por los
protocolos de routing, que utilizan las tablas de
routing para el calculo de las rutas óptimas.

34

Encaminamiento

Búsqueda en la tabla de forwarding función crítica

El tamaño y la complejidad de las tablas de forwarding depende de

• Tipo direccionamiento utilizado

• plano o jerarquizado

• direcciones tipo Seguridad Social, MAC, …
• n-niveles de jerarquía, tipo red telefónica

• direcciones de tamaño fijo o variable

• Tamaño (número de redes/hosts) de Internet

• 200.000 redes (año 2002)
• El número de hosts se dobla cada año

Objetivo routers IP

Otros esquemas de direccionamiento N-3:

• IPX
• CLNP
• IPv6

Direccionamiento IPv4

• 3 clases primarias: A, B y C
• Direccionamiento jerarquizado a 2 niveles: NET-ID + HOST-ID

35

36

IPv4: Problemas

Problemas del direccionamiento IP tradicional

• Tablas de encaminamiento muy grandes en routers

• +2M redes clase C

• Clases muy rígidas

• Problema si red > 254 hosts
• Problema si red << 65534 hosts
• Agotamiento de las dir. IP

¿ Como minimizar el nº de dir. de red (especialmente el de clase B) ?
• Compartiendo el mismo net-id para varias redes Subnetting

¿ Como gestionar más eficientemente las clases (A, B, C) ?

• Eliminándolas Supernetting

Subnetting (RFC 950)

• Red clase B 65.534 host

– técnicamente posible pero
– impracticable por acumulación de tráfico de difusión

• Solución: 1 dir NET-ID multiples redes físicas

37

38

Subnetting tamaño fijo

• El estándar TCP/IP permite elegir cuantos bits se utilizan para subnetting

Subnetting tamaño variable

Preguntar

• Técnica recursiva
• Máxima flexibilidad
• Problemas de ambigüedad desaconsejado (?)

39

40

Encaminamiento con subnetting
• Direccionamiento jerárquico Encaminamiento jerárquico
• No queda afectado el encaminamiento desde fuera de la red lógica

siempre y cuando las redes físicas sean contiguas.
– Muy complicado propagar la información de subnetting. No todos los

protocolos lo permiten

– Empresas ubicadas en distintas poblaciones NO subnetting (ver ejemplo)
• Todos los hosts y routers conectados a redes que utilizan subnetting

deben utilizar “subnet routing”.

Algoritmo Subnet Routing

• Algoritmo normal sabe cuantos bits corresponden a “red” y

cuantos a “estación”
– tabla… (net, next-hop)
– búsqueda sencilla y eficiente

• Algoritmo con subnetting (purista)

– tabla … (subnet-mask, subnet, next-hop)

PARA CADA ENTRADA EN LA TABLA (subnet-mask, network, next-hop)
IF (( dir_IP_destino AND subnet_mask) == subnet )

IF (next_hop) es una interface de red

mandar datagrama directamente a destino

ELSE

mandar datagrama a next_hop

41

42

Preguntar

43

44

Supernetting (CIDR) (RFC1519)

•

•

•

Clases A, B, C no dividen el espacio de direccionamiento de forma útil.
Poca demanda de direcciones de clase C.
Muy alta demanda de direcciones de clase B.

ROADS (Running Out of ADdress Space)
1.
2.
3.
Ejemplo: Organización con 4000 ordenadores
–
–

1 clase C 254 direciones para hosts. 16 clase C 4064
problema: 16 rutas en routers en vez de una. Existen 2.097.152 redes clase C Tablas de
encaminamiento demasiado grandes

CIDR (Classless Inter-Domain Routing)
–
–
–

Ya no se interpretan las clases (A, B, C)
4000 hosts 12 bits HOST-ID de 12 bits y NET-ID de 20 Máscara de subred = 20 bits
La dir. IP se ve como un entero. Permite asignar direcciones en bloques contiguos potencia de 2

contiguos

45

46

Supernetting (CIDR) y encaminamiento
• CIDR requiere que los protocolos de encaminamiento publiquen

también la máscara de red
– RIP-2, OSPF, BGP-4

• Encaminamiento sin clase enrutador nunca supone que la máscara

de red se base en la clase.
– compatible con subnetting fijo y variable

47

Encaminar por concordancia más larg