La Capa de Red

Algoritmos de enrutamiento
GG3
2
Tema 4: La Capa de Red
¨ 4. 1 Introducción ¨ 4.5 Algoritmos de
¨ 4.2 Circuitos Virtuales vs. enrutamiento
Datagramas ¤ Link state
¤ Distance Vector
¨ 4.3 Las “tripas” de un router
¤ Enrutamiento jerárquico
¨ 4.4 IP: Internet Protocol
¨ 4.6 Protocolos de
¤ Formato de datagrama
enrutamiento en Internet
¤ Direccionamiento IPv4
¤ RIP
¤ ICMP
¤ OSPF
¤ IPv6
¤ BGP

Capa de Red - Algoritmos de Enrutamiento

 Un algoritmo LS (link state)
3

El algoritmo de Dijkstra (1957)

¨ Cada nodo tiene conocimiento global Notación:
de la red gracias al “proceso de ¨ c(x,y): coste del enlace de x a
difusión del estado de los enlaces” y; = ∞ si x e y no son vecinos
¤ Todos los nodos tienen la misma ¨ D(v): coste de la mejor ruta
información conocida hasta v
¨ p(v): predecesor de v en la
¨ Cada nodo calcula sus rutas de coste ruta
mínimo a todos los demás nodos ¨ N': conjunto de nodos de los
¤ Y deriva la tabla de reenvío que estamos seguros ya
conocemos su mejor ruta
¨ Cálculo iterativo: tras ‘k’ pasos
conoce la ruta de coste mínimo a ‘k’
nodos destino
Capa de Red - Algoritmos de Enrutamiento
 Algoritmo de Dijsktra: pseudocódigo
4

1 Initialization (algoritmo ejecutado en nodo a)

2 N' = {a}
3 For todo nodo b
4 If b es vecino to a
5 then D(b) = c(a,b)
6 else D(b) = ∞
7
8 Loop
9 Encontrar c ∉ N' tal que D(c) es mínima
10 Añadir c a N'
11 Actualizar D(b) para cada vecino de c, tal que b ∉ N' :
12 D(b) = min( D(b), D(c) + c(c,b) )
13 /* si alguno de los vecinos v ofrece una nueva ruta con
14 coste menor a la conocida me quedo con ella */
15 Until N' ≡ N

Capa de Red - Algoritmos de Enrutamiento

 Algoritmo de Dijsktra: ejemplo
5
(3,y)
55 (3,x) (4,x)
(2,u) (5,u) (5,v)

22 vv 33 ww 55
uu 22 33 11 z
(4,y)
11 11 22 (8,w)
x yy
(1,u) (2,x)

paso N’ D(v), p(v) D(w), p(w) D(x), p(x) D(y), p(y) D(z), p(z)
0 u 2,u 5,u 1,u ∞,- ∞,-
1 u,x 2,u 4,x 2,x ∞,-
2 u,x,y 2,u 3,y 4,y
3 u,x,y,v 3,y 4,y
4 u,x,y,v,w 4,y
5 u,x,y,v,w,z
Capa de Red - Algoritmos de Enrutamiento
 Algoritmo de Dijsktra: ejemplo
6

Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z)

0 u 2,u 5,u 1,u ∞ ∞
1 ux 2,u 4,x 2,x ∞
2 uxy 2,u 3,y 4,y
3 uxyv 3,y 4,y
4 uxyvw 4,y
5 uxyvwz

5
3
v w 5
2
u 2 1 z
3
1 2
x 1
y
Capa de Red - Algoritmos de Enrutamiento
 Algoritmo de Dijsktra: consecuencia
7

¨ El conjunto de rutas
mínimas de un nodo a ¨ Tabla de reenvío:
todos los demás nodos de
la red forma un árbol de Nodo
destino
Reenvío
por enlace
confluencia o expansión x u,x
(spanning/sink tree) y
v
u,x
u,v
w u,x
v w z u,x
u z
x y

Capa de Red - Algoritmos de Enrutamiento

 Algoritmo de Dijsktra: discusión
8

¨ Complejidad: para n nodos

¤ Cada paso: comprueba todos los nodos, w, no pertenecientes a N’
¤ n(n+1)/2 comparaciones: complejidad O(n2)
¤ Implementación más eficiente posible de complejidad O(nlogn)

¨ Posibles oscilaciones:
¤ Si se considera la carga como medida del coste por enlace…

1 A A A A
1+e 2+e 0 0 2+e 2+e 0
D 0 0 B D B D B D B
1+e 1 0 0 1+e 1
0 e 0 0 1 1+e 0 e
1
C 1 C 1 1 C 1 C 1
1 1
e e e e
inicio … nuevo cómputo … nuevo cómputo … nuevo cómputo
Capa de Red - Algoritmos de Enrutamiento
 Algoritmo de Dijkstra: difusión del estado de los enlaces
9

¨ Cada nodo difunde la información de la red que conoce

(sus vecinos) almacenada en una estructura denominada
Paquete de estado (link state advertisement, LSA).
¨ Paquete de estado del nodo x :
Cabecera

Nodo origen x
Nº orden 1,2,….
Edad ttl
vecino1 c(x,vecino1)
vecino2 c(x,vecino1)
Vecinos
y coste

… …
vecinoi c(x,vecinoi)

Capa de Red - Algoritmos de Enrutamiento

10
Tema 4: La Capa de Red
¨ 4. 1 Introducción ¨ 4.5 Algoritmos de
¨ 4.2 Circuitos Virtuales vs. enrutamiento
Datagramas ¤ Link state
¤ Distance Vector
¨ 4.3 Las “tripas” de un router
¤ Enrutamiento jerárquico
¨ 4.4 IP: Internet Protocol
¨ 4.6 Protocolos de
¤ Formato de datagrama
enrutamiento en Internet
¤ Direccionamiento IPv4
¤ RIP
¤ ICMP
¤ OSPF
¤ IPv6
¤ BGP

Capa de Red - Algoritmos de Enrutamiento

 Algoritmo DV (distance vector)
11

¨ Basado en la ecuación de Bellman-Ford (57):

dx(y) ≡ coste de la ruta mínima de x a y
dx(y) = minv { c(x,v) + dv(y) }, para todo v vecino de x
5
¨ A ojo podemos calcular que:
dv(z) = 5, dx(z) = 3, dw(z) = 3
3
2 v w 5
¨ Y la ecuación de B-F establece que:
u 2 1 z
3 du(z) = min {c(u,v)+dv(z),
1 2
x 1
y c(u,x)+dx(z), c(u,w)+dw(z) }
du(z) = min {2 + 5, 1 + 3, 5 + 3} = 4
¨ El vecino para el que se alcanza el mínimo coste define el
enlace/interfaz de salida para la tabla de reenvío
Capa de Red - Algoritmos de Enrutamiento
 Algoritmo DV: algunas definiciones
12

¨ Dx(y) = coste mínimo estimado de x a y

¨ Cada nodo x conoce el coste a cada uno de sus
vecinos v: c(x,v)
¨ Cada nodo x mantiene una tabla (vectores de
distancia) con la distancia a cada nodo de la red:
Dx = [Dx(y): y є N ]
¨ Cada nodo mantiene la tabla de vectores de sus
nodos vecinos:
¤ Para cada vecino v de x, x mantiene: Dv = [Dv(y): y є N ]

Capa de Red - Algoritmos de Enrutamiento

 Algoritmo DV: ideas básicas
13

¨ Cada nodo envía a sus vecinos su propia tabla de

vectores, de cuando en cuando
¨ Cuando un nodo recibe una nueva versión de la tabla de
uno de sus vecinos, recalcula su propia tabla aplicando la
ecuación de B-F a la nueva información disponible
¨ Si se produce algún cambio respecto de la tabla antigua
se reenvía la nueva tabla a todos los vecinos para que
también conozcan los cambios realizados
¨ Bajo circunstancias normales los cambios se propagan
por toda la red, vecino a vecino, y las tablas convergen a
las rutas de coste mínimo (aunque lentamente)

Capa de Red - Algoritmos de Enrutamiento

 Algoritmo DV: pseudocódigo
14

¨ Proceso iterativo y asíncrono. Cada nodo:

Nueva iteración debida a:
¤ Cambio en el coste a un vecino Espera cambio en coste a
¤ Nueva tabla recibida de un vecino un vecino o recibir mensaje
de un vecino)
¨ Distribuido:
¤ Cada nodo envía su tabla a sus
vecinos solo si ha sufrido algún
cambio
Recalcula nueva tabla vectores

si hay cambios en la tabla

Notifica a vecinos

Capa de Red - Algoritmos de Enrutamiento

 Algoritmo DV: ejemplo de cálculo
15

coste a coste a
x x y z x y z
Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)}
x 0 2 7 x 0 2 3 = min{2+1 , 7+0} = 3
desde

desde
y ∞∞ ∞ y 2 0 1
z ∞∞ ∞ z 7 1 0
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)}
coste a = min{2+0 , 7+1} = 2
y x y z
x ∞ ∞ ∞
desde

y 2 0 1
z ∞∞ ∞
y
coste a 2 1
z x y z x z
7
x ∞∞ ∞
desde

y ∞∞ ∞
z 7 1 0
Tiempo
Capa de Red - Algoritmos de Enrutamiento
 Algoritmo DV: ejemplo de cálculo
16

coste a coste a
x x y z x y z
Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)}
x 0 2 7 x 0 2 3 = min{2+1 , 7+0} = 3
desde

desde
y ∞∞ ∞ y 2 0 1
z ∞∞ ∞ z 7 1 0
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)}
coste a coste a = min{2+0 , 7+1} = 2
y x y z x y z
x ∞ ∞ ∞ x 0 2 7
from
desde

y 2 0 1 y 2 0 1
z ∞∞ ∞ z 7 1 0
y
coste a coste a 2 1
z x y z x y z x z
7
x ∞∞ ∞ x 0 2 7
desde

y ∞∞ ∞ y 2 0 1
z 7 1 0 z 3 1 0
Tiempo
Capa de Red - Algoritmos de Enrutamiento
 Algoritmo DV: ejemplo de cálculo (ii)
17

coste a coste a coste a

x x y z x y z x y z
x 0 2 7 x 0 2 3 x 0 2 3

desde
desde

desde
y ∞∞∞ y 2 0 1 y 2 0 1
z ∞∞∞ z 7 1 0 z 3 1 0
coste a coste a coste a
y x y z x y z x y z
x ∞ ∞ ∞ x 0 2 7 x 0 2 3
desde

desde
y 2 0 1
desde

y 2 0 1 y 2 0 1
z ∞∞ ∞ z 7 1 0 z 3 1 0

coste a coste a coste a

z x y z x y z x y z y
2 1
x ∞∞ ∞ x 0 2 7 x 0 2 3
x z
desde

desde
desde

y ∞∞ ∞ y 2 0 1 y 2 0 1 7
z 7 1 0 z 3 1 0 z 3 1 0

Capa de Red - Algoritmos de Enrutamiento

 Algoritmo DV: propagación de “buenas noticias”
18

¨ Elnodo y detecta el cambio buenas noticias

¨ Recalcula su tabla de vectores se propagan
rápido !!
¨ Notifica a sus vecinos (x y z) si 1
y
hay cambios 4 1
x z
¨ Ejemplo: 50

¤ En t0, y detecta el cambio de coste, actualiza su tabla e

informa a x y a z
¤ En t1, z recibe la nueva tabla de y. Actualiza la suya propia
(calcula el nuevo coste a x ) e informa a x e y
¤ En t2, y recibe la nueva tabla de z y actualiza la suya propia
(no hay cambios)
Capa de Red - Algoritmos de Enrutamiento
 Algoritmo DV: propagación de “malas noticias”
19

coste a
x x y z y
4 1
x 0 4 5 x z
desde

y 4 0 1 50
z 5 1 0

coste a
y x y z
x 0 4 5
desde

y 4 0 1
z 5 1 0
coste a
z x y z
x 0 4 5
desde

y 4 0 1
z 5 1 0
Tiempo
t0
Capa de Red - Algoritmos de Enrutamiento
 Algoritmo DV: propagación de “malas noticias”
20

coste a coste a 60
x x y z x x y z y
4 1
x 0 4 5 x 0 51 50 x z
desde

desde
y 4 0 1 y 4 0 1 50
z 5 1 0 z 7 1 0

coste a coste a Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)}

y x y z y x y z = min{60+1 , 50+0} = 50
x 0 4 5 x 0 4 5 Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)}
= min{60+0 , 50+1} = 51
desde

y 4 0 1
desde

y 6 0 1
z 5 1 0 z 5 1 0
Dy(x) = min{c(y,x) + Dx(x), c(y,z) + Dz(x)}
coste a coste a = min{60+0 , 1+5} = 6
z x y z z x y z
x 0 4 5 x 0 4 5
desde

desde

y 4 0 1 y 4 0 1 Z no es informado todavía
z 5 1 0 z 5 1 0
Tiempo
to t1 Capa de Red - Algoritmos de Enrutamiento
 Algoritmo DV: propagación de “malas noticias”
21

coste a coste a coste a 60

x x y z x x y z x x y z y
4 1
x 0 4 5 x 0 51 50 x 0 51 50 x z
desde

desde

desde
y 4 0 1 y 4 0 1 y 6 0 1 50
z 5 1 0 z 5 1 0 z 5 1 0 Los vectores Dx NO cambian más

coste a coste a coste a

y x y z y x y z y x y z
x 0 4 5 x 0 4 5 x 0 51 50
desde

y 4 0 1
desde

desde
y 6 0 1 y 6 0 1
z 5 1 0 z 5 1 0 z 5 1 0
coste a coste a coste a
z x y z z x y z z x y z
x 0 4 5 x 0 4 5 x 0 51 50
desde

desde

desde

y 4 0 1 y 4 0 1 y 6 0 1
z 5 1 0 z 5 1 0 z 7 1 0
Tiempo
to t1 t2 Capa de Red - Algoritmos de Enrutamiento
 Algoritmo DV: propagación de “malas noticias”
22

coste a coste a coste a 60

x x y z x x y z x x y z y
4 1
x 0 4 5 x 0 51 50 x 0 51 50 x z
desde

desde

desde
y 4 0 1 y 4 0 1 y 6 0 1 50
z 5 1 0 z 7 1 0 z 7 1 0

coste a coste a coste a coste a

y x y z y x y z y x y z y x y z
x 0 4 5 x 0 4 5 x 0 51 50 x 0 51 50
desde

y 4 0 1
desde

desde
desde
y 6 0 1 y 6 0 1 y 8 0 1
z 5 1 0 z 5 1 0 z 5 1 0 z 7 1 0
coste a coste a coste a coste a
z x y z z x y z z x y z z x y z
x 0 4 5 x 0 4 5 x 0 51 50 x 0 51 50
desde

desde

desde
desde

y 4 0 1 y 4 0 1 y 6 0 1 y 6 0 1
z 5 1 0 z 5 1 0 z 7 1 0 z 7 1 0
Tiempo
to t1 t2 t3
Capa de Red - Algoritmos de Enrutamiento
 Algoritmo DV: propagación de “malas noticias”
23
¨ Las malas noticias son lentas (cuenta a infinito)
¤ Ejemplo 1: 44 iteraciones hasta que se terminan los cambios
60
y
4 1
x z
50
¨ Antes del cambio Dy(x) = 4, Dy(z) = 1, Dz(x) = 5, Dz(y) = 1
¨ t0: se produce el cambio c(y,x)=60 à Dy(x) = minxz{c(y,x)+ Dx(x), c(y,z)+ Dz(x)}=min{60+0, 1+5} = 6
¨ t1: Dy(x) llega al nodo z: Dz(x) = minxy{c(z,x)+ Dx(x), c(z,y)+ Dy(x)}=min{50+0, 1+6} = 7 (y cambia, via z)
¨ t2: Dz(x) llega al nodo y: Dy(x) = minxz{c(y,x)+ Dx(x), c(y,z)+ Dz(x)}=min{60+0, 1+7} = 8
¨ t3: Dy(x) llega al nodo z: Dz(x) = minxy{c(z,x)+ Dx(x), c(z,y)+ Dy(x)}=min{50+0, 1+8} = 9
¨ …
¨ t44: Dz(x) llega al nodo y: Dy(x) = minxz{c(y,x)+ Dx(x), c(y,z)+ Dz(x)}=min{60+0, 1+49} = 50
¨ t45: Dy(x) llega al nodo z: Dz(x) = minxy{c(z,x)+ Dx(x), c(z,y)+ Dy(x)}=min{50+0, 1+50} = 50 (camino a x por
zx)
¨ t46: Dz(x) llega al nodo y: Dy(x) = minxz{c(y,x)+ Dx(x), c(y,z)+ Dz(x)}=min{60+0, 1+50} = 51
¨ A partir de la iteración 44 los nodos y y z se dan cuenta de la nueva situación
Capa de Red - Algoritmos de Enrutamiento
 Algoritmo DV: propagación de “malas noticias”
24
¨ Las malas noticias son lentas (cuenta a infinito) 60
y
¤ Ejemplo 1: 44 iteraciones hasta que se terminan los cambios 4 1
x z
50
A 1 B 1 C 1 1
¤ Ejemplo 2: D E

¨ Inicialmente A está desactivado. Cuando A se activa, B se entera de que A existe al recibir su vector
distancia y actualizar su tabla indicando que A dista 1
¨ El nodo C se entera de que A existe porque B le indica que tiene un enlace hacia A de coste 1. Entonces
C actualiza su tabla registrando una trayectoria hacia A de coste 2
¨ Si el nodo A se desconecta entonces B no recibe el VD de A. Sin embargo el nodo C le dice que tiene una
trayectoria hasta A de distancia 2. B no sabe que la trayectoria de C a A pasa por el mismo y por tanto
cree que puede llegar a A a través de C por lo que actualiza su tabla registrando la distancia 2 + 1 = 3
hasta A
¨ En el siguiente intercambio, el nodo C comprueba que sus vecinos B y D tienen una trayectoria hasta A
de distancia 3. C calcula su propia distancia hasta A en 3 + 1 = 4. En los siguientes intercambios, los
nodos elevan ilimitadamente su distancia a A (cuenta a infinito)

Capa de Red - Algoritmos de Enrutamiento

 Algoritmo DV: propagación de “malas noticias”
25

¨ Solución: Horizonte dividido (split horizon/ poisoned reverse):

¤ Si z/C utiliza y/B como ruta hacia x/A, entonces indica a
y/B que su distancia a x/A es infinito (como si no conociera
ningún camino). De esta manera y/B no utilizará nunca a
z/C como camino hacia x/A (lo que originaba un bucle).
¤ Al resto de vecinos les entrega su tabla con la entrada
hacia x/A correcta.
¤ ¿La solución es definitiva?

60
y
4 1
A 1 B 1 C 1 1
D E x z
50

Capa de Red - Algoritmos de Enrutamiento

 Comparación entre LS y DV
26

Complejidad de mensajes Robustez: ¿qué ocurre si hay

¨ LS: para N nodos y E enlaces, fallos en un router?
O(N*E) mensajes enviados ¨ LS:
¨ DV: intercambio SOLO entre ¤ Un nodo puede anunciar un LSA
vecinos incorrecto: error, sabotaje, etc
¤ Cada nodo calcula sus propias
Tiempo de convergencia rutas (alcance limitado)

¨ LS: complejidad de cómputo ¨ DV:

O(N2) ¤ Un nodo puede anunciar una ruta
de coste erróneo
¤ Puede oscilar
¤ Cada nodo vecino propaga ese
¨ DV: variable error y alcance a toda la red
potencialmente
¤ Puede haber bucles
¤ Problema de cuenta a infinito
Capa de Red - Algoritmos de Enrutamiento
 Vectores de trayecto (path vector, PV)
27

¨ Extensión del paradigma DV (distance-vector), para:

¤ Resolver el problema de la cuenta a infinito
¤ Facilitar la implantación de políticas de enrutamiento

¨ Idea clave: en lugar de intercambiar y almacenar distancias

al destino usamos el camino completo (secuencia de nodos
que atraviesa la ruta). Facilita la detección de bucles (el
nodo ve su ID en la ruta) y la aplicación de políticas (por
dónde quiero o no ir, qué información facilito a mis vecinos)
¨ Se utiliza en enrutamiento entre dominios (ver enrutamiento
jerárquico más adelante).
¤ Ejemplo: protocolo BGP (Border Gateway)
Capa de Red - Algoritmos de Enrutamiento
 Vectores de trayecto (path vector, PV)
28

PV = A PV= A, B PV= A, B, C

A anuncia a B la red B anuncia a C la red C anuncia a D la red

10.1.1.0/24. Router A 10.1.1.0/24. Router B 10.1.1.0/24. Router C
se incluye en el PV se incluye en el PV se incluye en el camino
10.1.1.0/24

A B C D
D anuncia a B la red
10.1.1.0/24. Router D
se incluye en el camino
A rechaza el B rechaza el
anuncio ya que A anuncio ya que B se
D anuncia a A la red
se encuentra encuentra en el PV
10.1.1.0/24. Router D
en el PV
se incluye en el camino

Capa de Red - Algoritmos de Enrutamiento

29
Tema 4: La Capa de Red
¨ 4. 1 Introducción ¨ 4.5 Algoritmos de
¨ 4.2 Circuitos Virtuales vs. enrutamiento
Datagramas ¤ Link state
¤ Distance Vector
¨ 4.3 Las “tripas” de un router
¤ Enrutamiento jerárquico
¨ 4.4 IP: Internet Protocol
¨ 4.6 Protocolos de
¤ Formato de datagrama
enrutamiento en Internet
¤ Direccionamiento IPv4
¤ RIP
¤ ICMP
¤ OSPF
¤ IPv6
¤ BGP

Capa de Red - Algoritmos de Enrutamiento

 Enrutamiento jerárquico
30

¨ Hemos partido de una visión completamente idealizada de

las redes: todos los routers son iguales, la red es plana,
está operado por un único administrador, en un solo país,
etc….
¨ En realidad hay serios problemas:
¤ Heterogeneidad: capacidad de cómputo y almacenamiento,
fabricante, algoritmo/s de enrutamiento,…
¤ Escalabilidad: Internet hoy son cientos de millones de hosts:
tiempo de cómputo de las rutas, tamaño de las tablas de reenvío,
tiempos de selección de la entrada adecuada,…
¤ Autonomía administrativa: cada organización desea controlar el
tráfico que circula por su red (y su algoritmo de encaminamiento)

Capa de Red - Algoritmos de Enrutamiento

 Enrutamiento jerárquico
31

¨ Agrega routers en sistemas autónomos (autonomous systems, AS)

o dominios
¨ Todos los routers de un AS utilizan el mismo algoritmo de
enrutamiento
¨ Hablamos de enrutamiento intradominio o de protocolos de
enrutamiento intradominio o internos
¨ Dominios independientes pueden utilizar distintos protocolos de
enrutamiento ¿cómo se comunican?
¨ En cada dominio existen routers fronteras (gateway router) que
tienen enlaces con otros routers frontera de otros dominios. Ejercen
una función de pasarela entre dominios
¨ ¿Y las rutas entre dominios cómo se calculan?

Capa de Red - Algoritmos de Enrutamiento

 Enrutamiento entre SAs (inter-dominio)
32

¨ Si mi dominio solo dispone de una pasarela, el problema

de enrutar fuera del dominio se reduce a calcular la ruta
hasta la pasarela
¨ Si dispongo de varias pasarelas debo:
¤ Aprender qué dominios se alcanzan a través de cada una de
ellas.
¤ Propagar esa información a cada router del dominio para que
pueda calcular sus propias tablas de reenvío
¨ Un nuevo protocolo de enrutamiento entre sistemas
autónomos (inter-dominio) se encarga de esta tarea.
¤ Todos los dominios deben usar el mismo. BGP4 en Internet

Capa de Red - Algoritmos de Enrutamiento

 Enrutamiento entre SAs (inter-dominio)
33

3c
3a 2c
3b 2a
AS3 2b
1c AS2
1a 1b
1d AS1
¨ Ambos protocolos intra e
interdominio añaden información
a la tabla de reenvío de un router
Protocolo Protocolo interno:
Intra-dominio Inter-dominio
¤ Protocolo intradominio para

Tabla de
destinos del propio SA
Reenvío ¤ Protocolo interdominio para
destinos fuera del SA

Capa de Red - Algoritmos de Enrutamiento

 Enrutamiento entre dominios
34

x
3c
3a 2c
3b 2a
AS3 2b
1c AS2
1a 1b AS1
1d
¨ Cuando existen varias opciones (pasarelas) para alcanzar
un destino x, ¿cómo se selecciona la mejor?
¨ La solución habitual es el método de la “patata caliente”:
¤ Se elige la pasarela más cercana (con ruta de menor coste
intradominio), para sacar el paquete de nuestro dominio lo antes
posible
Capa de Red - Algoritmos de Enrutamiento
 Dominios, política e ISPs
35

¨ El protocolo de enrutamiento interdominio se encarga de trasladar

la información de qué dominios (identificados por su clase CIDR)
son accesibles desde una determinada pasarela
¨ Cada SA decide cuánta información, de la que él conoce, permite
conocer a otros dominios. Por ejemplo, podríamos tener alcance
con un tercero pero no querer que nos usen de puente para llegar
hasta él. Cada dominio (su administrador) implanta su propia
política de interna y de cooperación con otros dominios (acuerdos
comerciales)
¨ Si Internet puede verse como una jerarquía de ISPs
interconectados, ¿qué relación hay entre un ISP y un dominio o
SA?
¤ Habitulamente capa ISP constituye su propio dominio, pero también
los hay que optan por desdoblar su red en múltiples dominios
interconectados
Capa de Red - Algoritmos de Enrutamiento
36
Trabajo personal

¨Estudiar IPv6, pp 345-349 Kurose

¨ Material de apoyo, TP3.pptx

¨Preparación de E1 (S1,S2,S3)

Enrutamiento interno de AS en Internet