encaminamiento o ruteo - laboratorio de redes

Teleinformática y RedesEncaminamiento o Ruteo

“Quote here”The author

La red como un grafo

La red como un grafo

Nodos Dispositivos (finales e intermedios)Aristas Enlaces de red

ARPANET - Agosto de 1972

http://www.cybertelecom.org/notes/internet_history70s.htm#72

¿Por dónde se reenvía un paquete?

En circuitos virtuales sólo es un problema en la fase de establecimiento de la conexión. Una vez decidido allí, no varía.

En conmutación de paquetes, por ejemplo, en una red de datagramas, no existe un camino fijo, sino que la decisión del próximo salto se va tomando en cada nodo intermedio,para cada datagrama y en forma independiente.

¿Qué es Encaminamiento o Ruteo?

El ruteo es un proceso de elección de un camino por el cual un dispositivo determina por donde enviar un datagrama a partir de información contenida en una tabla (tabla de rutas) y de verificar el prefijo de red de la dirección IP del destinatario.

El ruteo ocurre en capa 3 y lo realiza el protocolo IP.

110110 ?

¿Qué dispositivos rutean?

Todos los dispositivos IP realizan ruteo.

La principal diferenciación es la siguiente:

● Un host (o un multihomed host) sólo puede rutear datagramas propios.

● Un ruteador (también llamado gateway) puede rutear datagramas propios y de otros hosts.

Tipo de entrega

● Entrega directa

● Entrega indirecta

Entrega directa

● El destinatario del mensaje se encuentra dentro de la misma red que el emisor, entonces se debe enviar el datagrama, encapsulado en una PDU de enlace, directamente al destinatario.

Entrega directa

● El host A debe encapsular el datagrama IP (capa 3)en una trama (capa 2).

● Pero A sólo conoce la dirección IP del destino(la dirección de capa 3).

● Entonces, ¿qué dirección MAC coloca en el campo destinatario de la trama Ethernet?

Entrega directa - ARP

● Se utiliza un protocolo auxiliar llamadoAddress Resolution Protocol para, dada una dirección de capa 3 (IP) de un destinatario, conocer la dirección de capa 2 (MAC) correspondiente.

● El protocolo es muy sencillo y opera en base a peticiones y respuestas.Ambas se encapsulan directamente sobre una PDU de capa 2.

● Las consultas, denominadas ARP Request, suelen ir destinadas a la dirección MAC broadcast FF:FF:FF:FF:FF:FF.

● Las respuestas, denominadas ARP Reply o ARP Response, son dirigidas a la dirección de hardware (MAC) de quien realizó la consulta.

Entrega directa - ARP

ARP - Estructura de la PDU

Tipo de dirección de hardware (Capa 2) Tipo de protocolo (Capa 3)

Longitud n de la dirección de capa 2

Longitud m de la dirección de capa 3

Operación(tipo de mensaje)

Dirección de capa 2 del origen: n bytes

Dirección de capa 3 del origen: m bytes

Dirección de capa 2 del destino: n bytes

Dirección de cpaa 3 del destino: m bytes

ARP - Request y Reply

ARP Requestdestinado a FF:FF:FF:FF:FF:FF

ARP Replydestinado a quien realizó la consulta

0x0001 (Ethernet) 0x8000 (IPv4) 0x0001 (Ethernet) 0x8000 (IPv4)

6 (bytes) 4 (bytes) 0x0001 (Request) 6 (bytes) 4 (bytes) 0x0002 (Reply)

52:54:00:1B:AC:CA(dirección mac del que pregunta)

52:54:00:73:47:C9(mac del que responde)

10.2.5.10(dirección ip del que pregunta)

10.2.5.12(dirección ip del que responde)

00:00:00:00:00:00(dato aún desconocido)

52:54:00:1B:AC:CA(dirección mac de quien preguntó)

10.2.5.12(dirección IP cuya MAC se quiere averiguar)

10.2.5.10(dirección ip de quien preguntó)

Entrega directa

Tabla ARP

Cada entrada asocia una dirección IP de un host adyacente con la MAC address de la interfaz de dicho host, con un TTL (vencimiento) en segundos.

$ ip neighbour↵

190.210.36.186 dev enp1s0 lladdr 52:54:00:b5:8a:3f STALE190.210.36.59 dev enp1s0 lladdr 52:54:00:dc:56:4e STALE190.210.36.1 dev enp1s0 lladdr 54:52:00:73:47:c9 REACHABLE190.210.36.9 dev enp1s0 lladdr 54:52:00:23:68:d6 STALE190.210.36.99 dev enp1s0 lladdr 00:16:3e:11:00:0a REACHABLE190.210.36.208 dev enp1s0 lladdr 52:54:00:3d:dc:f3 STALE190.210.36.214 dev enp1s0 lladdr 00:1b:21:75:82:9c STALE

# ip neighbour flush all↵

Entrega indirecta

● El destinatario del mensaje no se encuentra dentro de la misma red que el emisor, entonces se debe enviar el datagrama, en una PDU de enlace, al gateway.

Entrega indirecta

Entrega indirecta

Las direcciones IP no se modifican

Cambian lasdirecciones MAC

Direcciones en el encabezado IP

Concepto fundamental

La dirección IP destino de un paquete siempre se refiere al destino final. Cuando un dispositivo realiza ruteo y reenvía el datagrama a otro router (próximo salto), la dirección IP de ese router no aparece en ningún campo del paquete.

Tabla de rutas

Contiene información sobre las redes a las que es posible enviar paquetes y el próximo salto (hop) al cual se deberán enviar los datagramas destinados a esa red.Es decir, contiene información sobre las rutas disponibles.

Red Destino Máscara Prox. Salto (GW) Interfaz Capa 210.10.10.0 255.255.255.0 --- eth0192.168.1.0 255.255.255.0 --- eth1192.168.2.0 255.255.255.0 --- eth1172.16.0.0 255.255.0.0 192.168.1.100 eth1default 0.0.0.0 10.10.10.1 eth0

Tabla de rutas en Linux

# route -n ↵Kernel IP routing tableDestination Gateway Genmask Flags Metric Ref Use Iface10.10.10.0 0.0.0.0 255.255.255.0 U 0 0 0 eth0192.168.1.0 0.0.0.0 255.255.255.0 U 0 0 0 eth1192.168.2.0 0.0.0.0 255.255.255.0 U 0 0 0 eth1172.16.0.0 192.168.1.100 255.255.0.0 U 0 0 0 eth00.0.0.0 10.10.10.1 0.0.0.0 UG 100 0 0 eth0

# ip route ↵10.10.10.0/24 dev eth0 proto kernel scope link src 10.10.10.37192.168.1.0/24 dev eth1 proto kernel scope link src 192.168.1.1192.168.2.0/24 dev eth1 proto kernel scope link src 192.168.2.1172.16.0.0/16 via 192.168.1.100 dev eth1 proto staticdefault via 10.10.10.1 dev eth0 proto static

Tabla de rutas - ¿cómo se completa?

en forma estática● definidas por configuración (a mano)

# ip route add 170.210.0.0/16 via 10.4.11.30 dev eth0 ↵

en forma dinámica● definidas por protocolos de ruteo dinámico.● obtenidas a partir de mensajes ICMP Redirect.

¿Cómo se decide a dónde reenviar?

Dado un datagrama que se debe enviar o reenviar.● Se lee su dirección IP destino.● Para cada línea de la tabla de rutas,

○ Se lee la máscara de la fila.○ Se realiza AND binario con la dirección IP destino.○ Se compara el resultado con la dirección de red de la línea.

■ Si son iguales, se utiliza esa ruta.■ Si no son iguales, se analiza la siguiente línea.


# ip route ↵10.10.10.0/24 dev eth0 proto kernel scope link src 10.10.10.37192.168.1.0/24 dev eth1 proto kernel scope link src 192.168.1.1192.168.2.0/24 dev eth1 proto kernel scope link src 192.168.2.1192.168.3.0/24 dev eth2 proto kernel scope link src 192.168.3.1172.16.0.0/16 via 192.168.1.100 dev eth1 proto static

a) Paquete hacia host 10.10.10.17 → a quién se reenvía? por qué interfaz?

b) Paquete hacia host 172.16.0.40 → a quién se reenvía? por qué interfaz?

c) Paquete hacia host 190.104.80.3 → a quién se reenvía? por qué interfaz?

Preguntas al paso

¿Qué pasa si ninguna ruta coincide con la IP destino?

¿Qué pasa si más de una ruta coincide?

¿Por qué no alcanza sólo con definir la interfaz de salida?


# ip route ↵10.10.10.0/24 dev eth0 proto kernel scope link src 10.10.10.37192.168.1.0/24 dev eth1 proto kernel scope link src 192.168.1.1192.168.2.0/24 dev eth1 proto kernel scope link src 192.168.2.1192.168.3.0/24 dev eth2 proto kernel scope link src 192.168.3.1172.16.0.0/16 via 192.168.1.100 dev eth1 proto staticdefault via 10.10.10.1 dev eth0 proto static

a) Paquete hacia host 10.10.10.17 → a quién se reenvía? por qué interfaz?

b) Paquete hacia host 172.16.0.40 → a quién se reenvía? por qué interfaz?

c) Paquete hacia host 190.104.80.3 → a quién se reenvía? por qué interfaz?

Problemas con el ruteo estático

Se cae un enlace


Se cae un enlace

Aparecen nuevos enlaces / nodos


Se cae un enlace


Costos de enlaces se modifican


Se cae un enlace


Costos de enlaces se modifican

En Conclusión: La topología de la Red cambia

Ejemplo de ruteo estático completo

Construir Tabla de Rutas de R1

R1

180.70.65.128/25

180.70.65.192/26

201.4.16.0/22 201.4.22.0/24

eth0

eth1eth3

eth2

210.20.30.0/26

- Asignar IPs a cada interfaz- Construir tabla de rutas en

R1 para redes internas- ¿Como llegar a Internet?

Resto de internet

Construir Tabla de Rutas de R1180.70.65.128/25

180.70.65.192/26

201.4.16.0/

22

201.4.22.0/24

210.20.30.0/26

Internet

Interfaz IP Red

eth0 180.70.65.130/25 180.70.65.128/25

eth1 201.4.16.2/22 201.4.16.0/22

eth2 180.70.65.194/26 180.70.65.192/26

eth3 201.4.22.2/24 201.4.22.0/24

Asignación de IPs a interfaces de R1

Construir Tabla de Rutas de R1180.70.65.128/25

180.70.65.192/26

201.4.16.0/

22

201.4.22.0/24

210.20.30.0/26

InternetRed Gateway Interfaz

180.70.65.128/25 - eth0

201.4.16.0/22 - eth1

180.70.65.192/26 - eth2

201.4.22.0/24 - eth3

210.20.30.0/26 180.70.65.129 eth0

default 180.70.65.193 eth2

Tabla de Rutas en R1

Sistemas Autónomos

Sistemas autónomos

● Arquitectura general de Internet -- ASs.

● ¿Cómo administrar cada vez más redes de capa 3?

○ Administración de las tablas de rutas a mediana/gran escala.

● Protocolos de Ruteo interno vs Ruteo externo

○ IGP (Nodos bajo un mismo control administrativo).

○ EGP (Redes de diferentes "dueños").

Sistemas autónomos

Interior Gateway Protocols (IGP)Exterior Gateway Protocols (EGP)

Ruteo Dinámico

Algoritmos y Protocolos

Protocolos de Ruteo Dinámico

Características

● Dinámicos - Las novedades en la topología son informadas cuando suceden y la red se ajusta en respuesta.

● Distribuidos - Todos los ruteadores de la red reciben las novedades, no hay un nodo que centralice la información.

Diferencias

● Método para distribuir las novedades.● Método para calcular el camino más corto.

Vector de Distancias (algoritmo)

Basado en el Algoritmo de Bellman-Ford.

● Cada router mantiene una lista de las rutas que conoce.

● Al inicio, esa lista sólo incluye las redes a las que está directamente conectado. Cada entrada de la tabla indica la red destino, la distancia (medida en saltos) y el siguiente salto → (dest-network, distance, next-hop)

● Periódicamente, cada router envía una copia de su tabla de rutas a sus vecinos.

● Cuando un router recibe una tabla de un vecino, examina los destinos y las distancias a cada uno. Si a un destino se llega con menos saltos, o si ese destino no figura en su propia tabla, entonces actualiza su tabla con esos datos.

Bellman, R. (1958). On a routing problem. Quarterly of applied mathematics, 16(1), 87-90.Ford Jr, L. R. (1956). Network flow theory (No. P-923). Rand Corp Santa Monica Ca.

Vector de Distancias - Ejemplo

Tabla de A al inicioDest Cost Hop

A 0 -B 1 BC 1 CE 1 EF 1 F

Tabla de C al inicioDest Cost Hop

A 1 AB 1 BC 0 -D 1 D

para este ejemplo, todos los enlaces poseen costo 1



A 0 -B 1 BC 1 CE 1 EF 1 F


A 1 AB 1 BC 0 -D 1 D

Mensaje de C → A(A, 1), (B, 1), (C, 0), (D, 1)



A 0 -B 1 BC 1 CE 1 EF 1 F


A 1 AB 1 BC 0 -D 1 D


Tabla de costos vía CDest Cost

A 1 +1B 1 +1C 0 +1D 1 +1

se suma 1 al costo informado pues llegar a cualquier destino a través de C requiere, primero, llegar a C



A 0 -B 1 BC 1 CE 1 EF 1 F


A 1 AB 1 BC 0 -D 1 D

Tabla de costos vía CDest Cost

A 1 +1B 1 +1C 0 +1D 1 +1

Nueva tabla de ADest Cost Hop

A 0 -B 1 BC 1 CD 2 CE 1 EF 1 F

Com

para

ción

(men

or c

osto

)

Vector de Distancias - Forma alternativa


Tabla de cálculo en A al recibir el anuncio desde CTabla de A antes de recibir anuncio Anuncio de C Cálculo en A Tabla de A actualizada

Destino Costo (Ca) Salto Vector recibido Costo x C (Cc) Mínimo(Ca, Cc) SaltoA 0 - (A, 1) 1 + 1 = 2 Min(0, 2) = 0 -

B 1 B (B, 1) 1 + 1 = 2 Min(1, 2) = 1 B

C 1 C (C, 0) 0 + 1 = 1 Min(1, 1) = 1 C

- - ∞ (D, 1) 1 + 1 = 2 Min(∞, 2) = 2 C

E 1 E - - Min(1, -) = 1 E

F 1 F - - Min(1, -) = 1 F


Tabla de A en t=1Dest Cost Hop

A 0 -B 1 BC 1 CD 2 CE 1 EF 1 F


A 1 AB 1 BC 0 -D 1 D



A 0 -B 1 BC 1 CD 2 CE 1 EF 1 F


A 1 AB 1 BC 0 -D 1 D

Mensaje de A → C(A, 0), (B, 1), (C, 1),(D, 2), (E, 1), (F, 1)



A 0 -B 1 BC 1 CD 2 CE 1 EF 1 F


A 1 AB 1 BC 0 -D 1 D


Tabla de costos vía ADest Cost

A 0 +1B 1 +1C 1 +1D 2 +1E 1 +1F 1 +1



A 0 -B 1 BC 1 CD 2 CE 1 EF 1 F


A 1 AB 1 BC 0 -D 1 D

Tabla de costos vía ADest Cost

A 0 +1B 1 +1C 1 +1D 2 +1E 1 +1F 1 +1

Com

para

ción

(men

or c

osto

)

Nueva tabla de CDest Cost Hop

A 1 AB 1 BC 0 -D 1 DE 2 AF 2 A

Vector de Distancias - Forma alternativa

Tabla de cálculo en C al recibir el anuncio desde ATabla de C antes de recibir anuncio Anuncio de A Cálculo en C Tabla de C actualizada

Destino Costo (Cc) Salto Vector recibido Costo x A (Ca) Mínimo(Cc, Ca) SaltoA 1 A (A, 0) 0 + 1 = 1 Min(1, 1) = 1 A

B 1 B (B, 1) 1 + 1 = 2 Min(1, 2) = 1 B

C 0 - (C, 1) 1 + 1 = 2 Min(0, 2) = 0 -

D 1 D (D, 2) 2 + 1 = 3 Min(1, 3) = 1 D

- - ∞ (E, 1) 1 + 1 = 2 Min(∞, 2) = 2 A

- - ∞ (F, 1) 1 + 1 = 2 Min(∞, 2) = 2 A




A 0 -B 1 BC 1 CD 2 CE 1 EF 1 F

Tabla de C en t=2Dest Cost Hop

A 1 AB 1 BC 0 -D 1 DE 2 AF 2 A

Y así sucesivamente, donde cada nodo anuncia a sus vecinos las rutas en forma periódica

Ejercicio: definir la tabla inicial de B, realizar intercambios A→B y C→B y escribir tabla de B al finalizar

Vector de Distancias - Desventajas

● La principal desventaja del algoritmo vector-distancias es que no escala bien.

● En un entorno completamente estático, los algoritmos de vector de distancia propagan rutas a todos los destinos. Cuando las rutas cambian rápidamente, sin embargo, los cálculos pueden no estabilizarse.

● Cuando una ruta cambia (es decir, aparece una nueva conexión o falla una antigua), la información se propaga lentamente de un enrutador a otro. Mientras tanto, algunos enrutadores pueden tener información de enrutamiento incorrecta.

● Al proceso mediante el cual la información de ruteo queda consistente en todos los nodos de la topología se lo denomina Convergencia.

Problema: Cuenta al Infinito (Estado inicial)

Dest Cost Hop

E 1 E

Dest Cost Hop

E 2 ADest Cost Hop

E 2 A

Cuenta al Infinito (Novedad)

Dest Cost Hop

E 1 E

Dest Cost Hop

E 2 ADest Cost Hop

E 2 A

Enlace caído A - E

Cuenta al Infinito: Actualización y anuncio en A

Dest Cost Hop

E inf -

Dest Cost Hop

E 2 ADest Cost Hop

E 2 A

Enlace caído A - E

E - inf

E - inf

Cuenta al Infinito: Actualización B y anuncia C

Dest Cost Hop

E inf -

Dest Cost Hop

E inf -Dest Cost Hop

E 2 A

Enlace caído A - E

E - inf

E - 2

E - 2

Cuenta al Infinito: Actualización en A y B

Dest Cost Hop

E 3 C

Dest Cost Hop

E 3 CDest Cost Hop

E inf -

Enlace caído A - E

Cuenta al Infinito: Anuncian B y C

Dest Cost Hop

E 3 C

Dest Cost Hop

E 3 CDest Cost Hop

E inf -

Enlace caído A - E

E - inf

E - inf

E - 3

Cuenta al Infinito: Actualiza A y anuncia A,B

Dest Cost Hop

E 4 B

Dest Cost Hop

E inf -Dest Cost Hop

E inf -

Enlace caído A - E

E - 4

E - 4

E - inf

Cuenta al Infinito: Actualizan B y C, anuncio...

Dest Cost Hop

E inf -

Dest Cost Hop

E 5 ADest Cost Hop

E 5 A

Enlace caído A - E

E - inf

E - inf

E - 5

Cuenta al Infinito: Soluciones

● Reducir el número que representa infinito (p.e. 16) en las tablas.Impone una longitud máxima de la red.

● Split Horizon Consiste en no anunciar las rutas a los nodos de los cuales fueron aprendidas.

● Split Horizon with poison reverse Variante de mayor fortaleza, donde en lugar de no anunciar una ruta al nodo del cual la aprendimos, se le envía la misma con información negativa, por ejemplo infinito.

● Esto sólo evitaba los problemas en loops pequeños (2 nodos). En redes más grandes había que implementar técnicas más complejas que hacían que los tiempos de convergencias sean bastantes altos.

Estado del Enlace (algoritmo)

Basado en el algoritmo de camino mínimo (shortest-path-first) de Edsger Dijkstra.

● Cada router posee un mapa de la topología completa. Es decir, posee en memoria un grafo que representa a todos los demás routers, enlaces y redes internas.

● Cada router prueba, mediante mensajes periódicos, si alcanza a todos sus routers vecinos y propaga frecuentemente la información del estado de sus enlaces a los demás routers.

● Estos mensajes no especifican rutas; simplemente informan si la comunicación entre un par de routers vecinos es posible.

Estado del Enlace (algoritmo)

● Cada vez que un router recibe un mensaje de estado de un enlace, utiliza la información para actualizar su propia versión del mapa de red, marcando si el enlace está activo (up) o caído (down).

● A continuación, calcula las rutas aplicando el conocido algoritmo de camino más corto de Dijkstra al grafo resultante.

● Como cada router calcula las rutas de forma independiente utilizando los mismos datos de estado originales y no depende del cálculo en intermediarios, se garantiza una rápida convergencia y por ende una mejor escalabilidad.

Algoritmo de Dijkstra (Ejemplo)

A

B

C

D

5

10

11

3

2

Ejercicio: Tabla de Rutas del Nodo D utilizando el algoritmo de Dijkstra


A

B

C

D

5

10

11

3

2

Paso Confirmados Tentativos

1 (D,0,-)

Nodo en la solución

Nodo no incluido aun

Enlace no procesadoEnlace tentativoEnlace confirmadoEnlace descartado


A

B

C

D

5

10

11

3

2


1 (D,0,-)

2 (D,0,-) (B,11,B)(C,2,C)





A

B

C

D

5

10

11

3

2


1 (D,0,-)

2 (D,0,-) (B,11,B)

3 (D,0,-)(C,2,C) (B,11,B)





A

B

C

D

5

10

11

3

2


1 (D,0,-)

2 (D,0,-) (B,11,B)

3 (D,0,-)(C,2,C) (B,11,B)

4 (D,0,-)(C,2,C) (B,5,C)(A,12,C)





A

B

C

D

5

10

11

3

2


1 (D,0,-)

2 (D,0,-) (B,11,B)

3 (D,0,-)(C,2,C) (B,11,B)

4 (D,0,-)(C,2,C) (B,5,C)(A,12,C)

5 (D,0,-)(C,2,C) (B,5,C)

(A,12,C)Nodo en la solución




A

B

C

D

5

10

11

3

2


1 (D,0,-)

2 (D,0,-) (B,11,B)

3 (D,0,-)(C,2,C) (B,11,B)

4 (D,0,-)(C,2,C) (B,5,C)(A,12,C)

5 (D,0,-)(C,2,C) (B,5,C)

(A,12,C)

6 (D,0,-)(C,2,C) (B,5,C)

(A,10,C)





A

B

C

D

5

10

11

3

2


1 (D,0,-)

2 (D,0,-) (B,11,B)

3 (D,0,-)(C,2,C) (B,11,B)

4 (D,0,-)(C,2,C) (B,5,C)(A,12,C)

5 (D,0,-)(C,2,C) (B,5,C)

(A,12,C)

6 (D,0,-)(C,2,C) (B,5,C)

(A,10,C)

7 (D,0,-)(C,2,C) (B,5,C)(A,10,C)




Algoritmo de Dijkstra: Tabla de Rutas de D

Paso Confirmados

7 (D,0,-) (C,2,C) (B,5,C) (A,10,C)

Nodo Costo A través de

A 10 C

B 5 C

C 2 C

D 0 -

Solución del Algoritmo

Tabla de Rutas de D

Protocolo OSPF (basado en Link-State)

● Los nodos comparten sus enlaces directos a todo el resto.

○ LSP: Link-State Packet

● Cada nodo espera a recibir los enlaces de todos los nodos.

● Se aplica sobre el grafo completo el algoritmo de Dijkstra.

○ Cada nodo conoce toda la red.

● Protocolo con varios tipos de mensaje (bastante complejo)

● Disemina los estados vía flooding.

OSPF: Flooding

Protocolo RIP (basado en Distance-Vector)

● Implementación sencilla.

● Cada nodo comparte con los vecinos su conocimiento de la red

● Actualizaciones periódicas (30 segundos)

● En cada anuncio, se procesa y actualiza la propia tabla de rutas

● Costo de los enlaces = cantidad de saltos (1 por salto)

● Las novedades tardan en llegar a todos los nodos de la red

● La red tiene límites (15 saltos, 16 es infinito)

Bibliografía

● Fall, K. R., & Stevens, W. R. (2011). TCP/IP illustrated, volume 1: The protocols. addison-Wesley. Capítulo 5.

● Kurose, J. F., & (2013). Computer networking: A top-down approach. Pearson. Capítulo 4.

● Peterson, Larry L. & Davie, Bruce S. Computer networks : a systems approach. 5th ed. 2012. Capítulo 3.

encaminamiento o ruteo - laboratorio de redes

Documents