Slides TD IV - clases (22)

Vista previa del material en texto

TD4 2022TD4 2022
Agenda
2
▪ Protocolos de ruteo
• Introducción
• Algoritmos link state
• Algoritmos distance vector
▪ Ruteo intra-ISP: OSPF
▪ Ruteo inter-ISP: BGP
▪ Plano de control: SDN
TD4 2022TD4 2022
Basado en la ecuación de Bellman-Ford (programación dinámica)
Algoritmo de ruteo distance vector
3
mínimo tomado sobre
todos los vecinos v de x
 costo del camino mínimo de v a y
 Dx(y) = mínv { cx,v + Dv(y) }
 
costo del enlace de x a v
Si Dx(y) es el costo del camino mínimo de x a y, v es vecino de x:
TD4 2022TD4 2022
Bellman-Ford: ejemplo
4
u
y
z
2
2
1
3
1
1
2
5
3
5
Supongamos que los vecinos de u (x, v y w) conocen sus caminos 
mínimos hacia z:
Du(z) = mín { cu,v + Dv(z),
 cu,x + Dx(z),
 cu,w + Dw(z) }
De la ecuación de Bellman-Ford,
Dv(z) = 5
v
Dw(z) = 3
w
Dx(z) = 3
x
= mín {2 + 5,
 1 + 3,
 5 + 3} = 4
el nodo que ofrece el mínimo (x) es el 
next hop en el camino mínimo 
estimado hacia el destino (z)
TD4 2022TD4 2022
Algoritmo distance vector
5
Idea:
▪ Cada cierto tiempo, los nodos envían a sus vecinos sus propias 
estimaciones de caminos mínimos hacia los demás nodos
▪ Bajo ciertas condiciones, Dx(y) converge al costo mínimo real, dx(y)
Dx(y) ← mínv{ cx,v + Dv(y) } para cada nodo y en N
▪ Cuando x recibe una estimación, actualiza la propia a partir de la 
ecuación de Bellman-Ford:
TD4 2022TD4 2022
Algoritmo distance vector
6
Iterativo y asincrónico: cada 
iteración se genera por:
▪ Cambios en los costos locales
▪ Actualización de los vecinos
Espera: cambios en costos de enlaces 
locales o mensaje de algún vecino
Cada nodo:
Distribuido y auto-regulado: cada 
nodo notifica a sus vecinos sólo 
cuando sus estimaciones 
cambian:
▪ No se producen acciones si no 
se reciben notificaciones
Recomputa estimaciones a partir de la 
información recolectada
Notifica a sus vecinos si la estimación 
a algún destino sufrió cambios
TD4 2022TD4 2022
g h i
DV en a 
D
a
(a)=0
D
a
(b) = 8
D
a
(c) = ∞
D
a
(d) = 1
D
a
(e) = ∞
D
a
(f) = ∞
D
a
(g) = ∞
D
a
(h) = ∞
D
a
(i) = ∞
Distance vector: ejemplo
7
1 1
1 1 1
1 1
1 1
8 1
DV en b
D
b
(f) = ∞
D
b
(g) = ∞
D
b
(h) = ∞
D
b
(i) = ∞
D
b
(a) = 8
D
b
(c) = 1
D
b
(d) = ∞
D
b
(e) = 1
a b c
d e f
DV en b
D
b
(f) =2
D
b
(g) = ∞
D
b
(h) = 2
D
b
(i) = ∞
D
b
(a) = 8
D
b
(c) = 1
D
b
(d) = 2
D
b
(e) = 1
e
b
D
b
(a) = mín{c
b,a
+D
a
(a), c
b,c 
+D
c
(a), c
b,e
+D
e
(a)} = mín{8,∞,∞} = 8 
D
b
(c) = mín{c
b,a
+D
a
(c), c
b,c 
+D
c
(c), c
 b,e 
+D
e
(c)} = mín{∞,1,∞} = 1 
D
b
(d) = mín{c
b,a
+D
a
(d), c
b,c 
+D
c
(d), c
 b,e 
+D
e
(d)} = mín{9,∞,2} = 2 
D
b
(f) = mín{c
b,a
+D
a
(f), c
b,c 
+D
c
(f), c
 b,e 
+D
e
(f)} = mín{∞,∞,2} = 2 
D
b
(i) = mín{c
b,a
+D
a
(i), c
b,c 
+D
c
(i), c
 b,e
+D
e
(i)} = mín{∞,
 
∞, ∞} = ∞ 
D
b
(h) = mín{c
b,a
+D
a
(h), c
b,c 
+D
c
(h), c
 b,e
+D
e
(h)} = mín{∞,
 
∞, 2} = 2 
D
b
(e) = mín{c
b,a
+D
a
(e), c
b,c 
+D
c
(e), c
 b,e 
+D
e
(e)} = mín{∞,∞,1} = 1 
D
b
(g) = mín{c
b,a
+D
a
(g), c
b,c 
+D
c
(g), c
 b,e
+D
e
(g)} = mín{∞,
 
∞, ∞} = ∞ 
▪ b recibe DVs de 
a, c, e; computa:
t1
DV en e
D
e
(a) = ∞
D
e
(b) = 1
D
e
(c) = ∞
D
e
(d) = 1
D
e
(e) = 0
D
e
(f) = 1
D
e
(g) = ∞
D
e
(h) = 1
D
e
(i) = ∞
DV en c
D
c
(a) = ∞
D
c
(b) = 1
D
c
(c) = 0
D
c
(d) = ∞
D
c
(e) = ∞
D
c
(f) = ∞
D
c
(g) = ∞
D
c
(h) = ∞
D
c
(i) = ∞
DV en c
TD4 2022TD4 2022
Distance vector: cambio de costo de enlaces
8
t0 : y detecta un cambio de costo, actualiza su DV y notifica a sus 
vecinos
t1 : z recibe el mensaje de y, computa el nuevo costo mínimo a x y 
envía a sus vecinos su DV
t2 : y recibe la actualización de z pero sus costos mínimos no 
sufren cambios: y no envía nuevos mensajes
Cambio de costos en enlaces:
▪Un nodo detecta un cambio en el costo de uno de 
sus enlaces
▪Recalcula su DV local
▪Si se modifica, envía notificaciones a sus vecinos
x z
14
50
y
1
TD4 2022TD4 2022
Distance vector: cambio de costo de enlaces
9
Cambio de costos en los enlaces:
▪Puede suscitar el problema de cuenta a infinito
x z
14
50
y
60
• y nota que el enlace a x tiene costo 60 pero z informa un camino de costo 5: y 
concluye que puede llegar a x con costo 6 vía z. Luego informa de esto a z.
• z observa que el camino a x vía y tiene nuevo costo 6: z actualiza su 
costo a x y lo pone en 7, vía y. Luego notifica a y de este nuevo costo.
• y observa que el camino a x vía z tiene nuevo costo 7: y actualiza su 
costo a x y lo pone en 8, vía z. Luego notifica a z de este nuevo costo.
• z observa que el camino a x vía y tiene nuevo costo 8: z actualiza su 
costo a x y lo pone en 9, vía y. Luego notifica a y de este nuevo costo.
…
TD4 2022TD4 2022
Comparación entre link state y distance vector
10
Complejidad en mensajes
LS: n routers, O(n2) mensajes
DV: intercambio de mensajes entre 
vecinos; tiempo de convergencia 
variable
Velocidad de convergencia
LS: complejidad linearítmica
• Puede tener oscilaciones
DV: tiempo de convergencia variable
• Puede haber ciclos
• Cuenta a infinito
Robustez: resiliencia ante 
fallas/hacks en los routers
LS: 
• El router puede informar costos 
incorrectos de sus enlaces (solamente)
• Cada router sólo computa su propia 
tabla de ruteo
DV:
• El router puede informar costos 
incorrectos de caminos (fenómeno de 
black-holing)
• Las tablas de los routers son usadas por 
otros routers: los errores pueden 
propagarse a través de la red
TD4 2022TD4 2022 11
Ruteo intra-dominio
TD4 2022TD4 2022
Hasta ahora desarrollamos los conceptos teóricos de los 
algoritmos de ruteo en condiciones “idealizadas”
▪ Routers idénticos
▪ Redes simples, sin estructura
Ruteo en Internet
12
Internet: miles de millones de destinos
▪ No es posible guardar todo en las 
tablas de ruteo
▪ Los mensajes de intercambio 
saturarían todos los enlaces
Autonomía administrativa
▪ Internet es una “red de redes”
▪ Cada red quiere controlar el ruteo 
“puertas adentro”
TD4 2022TD4 2022
En Internet, los routers se agrupan en regiones:
 sistemas autónomos (ASs)
Ruteo escalable
13
Ruteo intra-AS: dentro del mismo AS
▪ Todo router en el AS debe correr el 
mismo protocolo intra-AS (o 
intra-dominio)
▪ Routers en distintos ASs pueden 
correr protocolos intra-AS 
diferentes
▪ Gateway router: emplazado en el 
borde de su propio AS; tiene 
enlaces a routers en otros ASs
Ruteo inter-AS: entre ASs
▪ Los gateways ejecutan tanto 
ruteo inter-AS como intra-AS
TD4 2022TD4 2022
Interconexión de sistemas autónomos
14
3b
1d
3a
1c
2a
AS3
AS1
AS21a
2c
2b
1b
3cruteo intra-AS
ruteo 
intra-AS
ruteo 
intra-AS
ruteo inter-AS
tabla de 
forwarding
La tabla de forwarding la configuran 
ambos protocolos (intra- e inter-AS)
 Ruteo 
Intra-AS
 Ruteo 
Inter-AS ▪ El ruteo intra-AS determina las 
entradas para los destinos en el AS
▪ El ruteo inter-AS determina las 
entradas para los destinos externos
TD4 2022TD4 2022
Alcanzabilidad de destinos externos
15
3b
1d
3a
1c
2a
AS3
AS1
AS21a
2c
2b
1b
3c
otras 
redes
otras 
redes
▪ Si un router en AS1 recibe un 
paquete destinado al exterior,
El ruteo inter-AS de AS1 debe:
1. Aprender cuáles destinos son 
alcanzables vía AS2 y cuáles vía AS3
2. Propagar esta información a todos los 
routers de AS1
• ¿cómo sabe a cuál gateway 
reenviárselo?
TD4 2022TD4 2022
Protocolos de ruteo intra-AS
16
Algunos de los protocolos de ruteo interno más comunes:
▪ RIP: Routing Information Protocol [RFC 1723]
• Distance vector “clásico”: intercambia DVs cada 30 segundos
• No se usa mucho en la actualidad
▪ EIGRP: Enhanced Interior Gateway Routing Protocol
• Basado en un algoritmo distance vector
• Fue propietario de Cisco durante décadas; se hizo abierto en 2013 
[RFC 7868]
▪ OSPF: Open Shortest Path First [RFC 2328]
• Basado en un algoritmo link state
• El protocolo IS-IS (standard ISO, no RFC) es esencialmente equivalente 
a OSPF
TD4 2022TD42022
El protocolo OSPF
17
▪ Es abierto, públicamente disponible (la O de Open)
▪ Link state “clásico”
• Cada router hace flooding a toda la red del AS con mensajes de 
estado de sus enlaces (van sobre IP y no sobre TCP/UDP)
• Permite definir múltiples métricas de costos de enlaces (e.g., 
ancho de banda o delay)
• Cada router tiene la topología completa de la red; utiliza el 
algoritmo de Dijkstra para calcular la tabla de forwarding
▪ Seguridad: define mecanismos de autenticación para los 
mensajes 
TD4 2022TD4 2022
OSPF: diseño jerárquico
18
▪ El AS se puede jerarquizar en dos niveles: áreas locales y backbone
• Los mensajes se floodean sólo en un área local o en el backbone
• Cada router tiene la topología detallada del área; sólo conoce la dirección 
para alcanzar otros destinos
router de borde: 
sintetiza las distancias a los 
destinos en su área; envía 
mensajes en el backbone
área 1 área 2
área 3
backbone
routers 
locales
 
 
 
 
 
 
 
 
 
 
 
 
 
 
router backbone: 
corre OSPF sólo 
dentro del backbone
router límite:
se conecta con otros ASs
router local: 
• Hace flooding en su área
• Calcula ruteo dentro del área
• Envía paquetes al exterior vía 
su router de borde
TD4 2022TD4 2022 19
Ruteo inter-dominio
TD4 2022TD4 2022
▪ BGP (Border Gateway Protocol): el protocolo de-facto de ruteo 
inter-dominio
• El “pegamento” de Internet
▪ Permite que las subnets anuncien a todo Internet su existencia (y 
sus destinos alcanzables)
▪ BGP provee mecanismos para que los ASs puedan:
• Obtener información de alcanzabilidad de redes desde los ASs 
vecinos (eBGP)
• Propagar información de alcanzabilidad a todos los routers dentro 
del AS (iBGP)
• Determinar buenas rutas hacia otras redes a partir de dicha 
información de alcanzabilidad y de políticas
Ruteo inter-dominio: BGP
20
TD4 2022TD4 2022
Conectividad eBGP e iBGP
21
Conectividad eBGP
Conectividad (lógica) iBGP
1b
1d
1c1a
2b
2d
2c2a
3b
3d
3c3a
AS 2
AS 3AS 1
los gateways corren
ambos protocolos
TD4 2022TD4 2022
BGP: conceptos básicos
22
▪ Cuando el gateway 3a en AS3 anuncia el camino AS3, x a 2c:
• AS3 le promete a AS2 que reenviará los datagramas hacia x
▪ Sesión BGP: dos routers BGP (peers) intercambian mensajes 
sobre una conexión TCP semi-permanente
• Anuncio de caminos hacia diferentes destinos (prefijos de redes)
2b
2d
2c2a
AS 2
3b
3d
3c3a
AS 3
1b
1d
1c1a
AS 1
 x
Anuncio BGP:
AS3, x
TD4 2022TD4 2022
2b
2d
2c2a
AS 2
3b
3d
3c3a
AS 3
1b
1d
1c1a
AS 1
 x
Anuncio de caminos
23
▪ A partir de la política del AS2, el router 2c acepta el camino y lo propaga 
(vía iBGP) a todos los routers del AS2
AS2,AS3,x 
▪ El router 2c del AS2 recibe el anuncio AS3, x (vía eBGP) del router 3a de AS3
▪ A partir de la política del AS2, el router 2a anuncia el camino AS2, AS3, x 
(vía eBGP) al router 1c del AS1
AS3,x
TD4 2022TD4 2022
Anuncio de caminos
24
AS2,AS3,x 
▪ El router 1c aprende el camino AS2, AS3, x de 2a
Un gateway puede aprender múltiples caminos hacia un destino:
AS3,x
▪ El router 1c aprende el camino AS3, x de 3a
▪ A partir de la política del AS1, el router 1c elige el camino AS3, x y anuncia 
dicho camino dentro del AS1 vía iBGP
AS3,x
2b
2d
2c2a
AS 2
3b
3d
3c3a
AS 3
1b
1d
1c1a
AS 1
 x
AS3,x
AS3,x
AS3,x
TD4 2022TD4 2022
2b
2d
2c2a
AS 2
3b
3d
3c3a
AS 3
1b
1d
1c1a
AS 1
 x
Anuncio de caminos
25
AS2,AS3,x 
AS3,x
AS3,x
▪ 1a, 1b y 1d aprenden por iBGP cómo llegar a x a través de 1c
▪ en 1d, por OSPF (intra-dominio), se sabe que se llega a 1c 
por la interfaz 1
12
1
2
dest interfaz
…
…
…
…
interfaces 
locales en 
1a y 1d
▪ luego, en 1d, para llegar a x, se debe utilizar la interfaz 1
1c 1
x 1
AS3,x
AS3,x
AS3,x
TD4 2022TD4 2022
2b
2d
2c2a
AS 2
3b
3d
3c3a
AS 3
1b
1d
1c1a
AS 1
 x
Anuncio de caminos
26
1
2
dest interfaz
…
…
…
…
1c 2
x 2
▪ en 1a, por OSPF (intra-dominio), se sabe que se llega a 1c 
por la interfaz 2
▪ luego, en 1a, para llegar a x, se debe utilizar la interfaz 2
TD4 2022TD4 2022
Rutas y atributos
27
▪ Las rutas anunciadas en BGP constan de prefijo + atributos
• Prefijo: el destino siendo anunciado
• Dos atributos importantes:
• AS-PATH: lista de los ASs atravesados por el anuncio del 
prefijo
• NEXT-HOP: indica el router interno que comienza el AS-PATH
▪ Ruteo por políticas:
• Los gateways pueden utilizar políticas para aceptar o rechazar 
anuncios (e.g., no rutear a través del AS N)
• También pueden determinar si corresponde anunciar caminos a 
otros ASs
TD4 2022TD4 2022
Mensajes BGP
28
▪ Los peers BGP intercambian mensajes sobre una conexión TCP
▪ Cuatro tipo de mensajes BGP:
• OPEN: abre una conexión TCP a un peer remoto y autentica al 
peer emisor
• UPDATE: anuncia un nuevo camino (o actualiza/elimina uno 
anterior)
• KEEPALIVE: mantiene la conexión abierta en ausencia de 
UPDATEs; también sirve como ACK de OPEN
• NOTIFICATION: reporta errores en el mensaje anterior; también 
empleado para cerrar la conexión
TD4 2022TD4 2022
2b
2d
2c2a
AS 2
3b
3d
3c3a
AS 3
1b
1d
1c1a
AS 1
 x
Ruteo hot potato
29
▪ 2d aprende (vía iBGP) que puede llegar a x a través de 2a ó 2c
▪ Ruteo hot potato: elegir el gateway con el menor costo intra-dominio 
sin preocuparse por el costo inter-dominio (en este caso, 2d elige 2a 
a pesar de que el camino tenga más hops hacia x)
AS3,x AS1,AS3,x 
costos de enlaces 
en OSPF
201
112
263
TD4 2022TD4 2022
▪ Un router puede aprender más de una ruta hacia un AS
▪ La selección entre estas se da por eliminación aplicando las 
siguientes reglas:
1. Valor de preferencia local (vía política del admin del AS)
2. AS-PATH más corto
3. Router NEXT-HOP más cercano (ruteo hot potato)
4. Criterios adicionales (identificadores BGP)
Selección de rutas
30
TD4 2022TD4 2022
Política vía anuncios 
31
B
Supongamos que un ISP sólo quiere rutear tráfico desde/hacia sus redes cliente 
(y no quiere rutear tráfico en tránsito entre otros ISPs –una política realista)
w A
yC 
x
▪ A, B y C son redes de ISPs backbone (tier 1)
▪ x, w e y son redes cliente (e.g. ISPs de tier 3)
▪ x es dual-homed: conectado a dos proveedores
▪ Si x no quisiera rutear el tráfico de B a C,
▪ x podría dejar de anunciar a B las rutas hacia C
 
 
 
 
Red de ISP cliente
Red de ISP backbone
TD4 2022TD4 2022
Política vía anuncios 
32
B 
Red de ISP cliente
 
Red de ISP backbone 
 
▪ A anuncia el camino A,w a B y a C
▪ B decide no anunciar B,A,w a C
▪ B no obtiene rédito por rutear C,B,A,w dado que ni C, ni A ni w son clientes
▪ C, por ende, no aprende el camino C,B,A,w
▪ C va a rutear C,A,w para llegar a w
Supongamos que un ISP sólo quiere rutear tráfico desde/hacia sus redes cliente 
(y no quiere rutear tráfico en tránsito entre otros ISPs –una política realista)
w A
yC 
x
A,w
A,w
TD4 2022TD4 2022
¿Por qué existe ruteo inter- e intra-dominio?
33
Política
▪ inter-dominio: importante decidir quién rutea a través de la red y 
cómo lo hace
▪ intra-dominio: mismo control administrativo; la política pierde 
relevancia
Escala
▪ El ruteo jerárquico ahorra espacio de tablas y reduce el tráfico en 
las redes
Rendimiento
▪ inter-dominio: se prioriza por debajo de la política
▪ intra-dominio: puede focalizar en optimizar las rutas