Slides TD IV - clases (23)

Vista previa del material en texto

TD4 2022TD4 2022 4
Repaso: nivel de red
TD4 2022TD4 2022
Dos enfoques para estructurar el plano de control:
▪ Control en cada router (tradicional)
▪ Control centralizado (Software Defined Networking)
Funciones del nivel de red
5
▪ Forwarding: trasladar paquetes desde 
los enlaces de entrada de un router 
hacia el enlace de salida apropiado
plano de datos
plano de control▪ Routing: determinar la ruta que siguen los paquetes desde el origen hasta el 
destino
TD4 2022TD4 2022
Plano de control en cada router
1
2
0111
3
6
Algoritmos de ruteo distribuidos, implementados en todos los 
routers e interactuando entre sí
tabla de
forwarding local
algoritmo
de ruteo
plano de datos
plano de control
valores en el header 
del paquete
TD4 2022TD4 2022
Plano de control vía SDN
1
2
0111
3
7
Un controlador remoto computa e instala las tablas de forwarding en los 
routers
valores en el header 
del paquete
plano de datos
plano de control
CA
CA CA CA CA
controlador remoto
TD4 2022TD4 2022 8
Protocolos de ruteo
TD4 2022TD4 2022
Objetivo: determinar caminos “buenos” 
entre hosts a través de una red de routers
▪ camino: secuencia de routers que 
atraviesan los paquetes desde un host 
origen hasta un host destino
▪ “bueno”: el de menor “costo”, el “más 
rápido”, el “menos congestionado”...
▪ El ruteo es uno de los problemas más 
importantes en redes de computadoras
Protocolos de ruteo: introducción
 
 
 
 
 
 
 
 
 
 
 
 
 
 
9
aplicación
transporte
red
enlace
física
aplicación
transporte
red
enlace
física
red
enlace
física
red
enlace
física
red
enlace
física
red
enlace
física
red
enlace
física
TD4 2022TD4 2022
Abstracción: grafo con costos en los enlaces
10
u
yx
wv
z
2
2
1
3
1
1
2
5
3
5
Grafo G = (N,E)
c
a,b
: costo del enlace que conecta a con b
 ej., c
w,z 
= 5, c
u,z 
= ∞
el costo lo define el operador de la red: puede 
ser constante, inversamente proporcional al 
ancho de banda, directamente proporcional a 
la congestión, etc.
N: conjunto de routers = { u, v, w, x, y, z }
E: conjunto de enlaces =
{ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }
TD4 2022TD4 2022
Taxonomía de algoritmos de ruteo
11
Centralidad de la información
Global: todos los routers tienen la 
topología completa de la red con 
la información de los costos
• Algoritmos link state
Descentralizado: proceso de cómputo 
iterativo; intercambio de información con 
vecinos (inicialmente, cada router sólo 
conoce el costo a los vecinos directos)
• Algoritmos distance vector
Rapidez de 
cambio de 
las rutas
Dinámico: las rutas 
cambian rápidamente
• Actualizaciones 
periódicas o como 
respuesta a cambios 
en los costos
Estático: las rutas 
cambian lentamente 
a lo largo del tiempo
TD4 2022TD4 2022
Algoritmo de ruteo link state: Dijkstra
12
▪ Centralizado: todos los nodos conocen 
la topología de la red y los costos de los 
enlaces
• Se logra vía broadcasting de estado de 
enlaces
• Todos los nodos tienen la misma 
información
▪ Computa caminos de costo mínimo de 
un nodo origen hacia los nodos 
restantes
• Genera la tabla de forwarding para dicho 
nodo
▪ Iterativo: luego de k iteraciones, se 
conoce el camino de costo mínimo 
hacia k destinos
▪ cx,y: costo del enlace de x a y 
(∞ si no son vecinos)
▪ D(v): estimación actual del 
costo del camino mínimo 
desde el origen al destino v
▪ p(v): nodo predecesor a lo 
largo del camino del origen a 
v
▪ N': conjunto de nodos para 
los que ya se conoce el 
camino mínimo
notación
TD4 2022TD4 2022
Algoritmo de ruteo link state: Dijkstra
13
1 Inicialización 
2 N' = {u} # calcular camino mínimo desde u hacia los otros nodos
3 Para cada nodo v 
4 Si v es vecino de u # u sólo conoce el costo a sus vecinos directos al 
principio
5 D(v) = c
u,v 
# puede no ser el camino de costo mínimo
6 Si no, D(v) = ∞ 
7 8 Repetir
9 
10 
11
12
13
14
15 hasta que todos los nodos estén en N' 
Encontrar w (que no esté en N') tal que D(w) es mínimo
Agregar w a N' 
Actualizar D(v) para todo v vecino de w que no esté en N': 
 D(v) = mín ( D(v), D(w) + cw,v
 
) 
# el nuevo camino mínimo hacia v es, o bien el camino mínimo 
anterior, o bien el camino mínimo conocido a w más el costo de 
ir de w a v
TD4 2022TD4 2022
Algoritmo de Dijkstra: ejemplo
14
Paso
0
1
2
3
4
5
N' D(v),p(v) D(x),p(x) D(y),p(y) D(z),p(z)
u
yx
wv
z
2
2
1
3
1
1
2
5
3
5
4,y
D(w),p(w)
D(w),p(w)
5,u
4,x
3,y
3,y
4,y3,y
5,u ∞∞1,u2,u
∞2,x4,x2,u
4,y3,y2,u
uxyvwz
uxyvw
uxyv
uxy
ux
u
v w x y z
Encontrar a que no esté en N' tal que D(a) es mínimo
Agregar a a N' 
Actualizar D(b) para todo b vecino de a no que no esté en N' : 
 D(b) = mín ( D(b), D(a) + ca,b
 
) 
Inicialización (paso 0): para todo a, si a es vecino, D(a) = cu,a
 
TD4 2022TD4 2022
Algoritmo de Dijkstra: ejemplo
15
u
yx
wv
z
2
2
1
3
1
1
2
5
3
5
D(w),p(w)
5,u
4,x
3,y
3,y
u
yx
wv
z
Árbol de costo mínimo para u Tabla de forwarding para u
v
x
y
w
x
(u,v)
(u,x)
(u,x)
(u,x)
(u,x)
 destino enlace
ruta directa de u a v
ruta vía x hacia 
todos los otros 
destinos
TD4 2022TD4 2022
Algoritmo de Dijkstra: otro ejemplo
16
w3
4
v
x
u
5
3
7 4
y8 z
2
7
9Paso N'
D(v),
p(v)
0
1
2
3
4
5
D(w),
p(w)
D(x),
p(x)
D(y),
p(y)
D(z),
p(z)
u ∞ ∞ 7,u 3,u 5,u
uw ∞ 11,w 6,w 5,u
14,x 11,w 6,wuwx
uwxv 14,x 10,v 
uwxvy 12,y 
Notas
▪ El árbol de costo mínimo se construye siguiendo los nodos predecesores
▪ Puede haber empates (con mecanismos de desempate arbitrarios)
uwxvyz
v w x y z
TD4 2022TD4 2022
Algoritmo de Dijkstra: análisis
17
Complejidad computacional: n nodos, e aristas
▪ Hay n iteraciones; en cada una se revisan los nodos w que no estén en N’
▪ n(n+1)/2 comparaciones: complejidad cuadrática, O(n2)
▪ Se puede implementar en tiempo O(e + n log n) (con Fibonacci heaps) 
Complejidad en mensajes
▪ Cada router debe hacer broadcast de su estado a los otros routers
▪ Algoritmos de broadcasting eficientes permiten diseminar un mensaje 
atravesando O(n) enlaces
▪ Agregando para los n routers, tenemos O(n2) mensajes en total
TD4 2022TD4 2022
Algoritmo de Dijkstra: oscilaciones
18
▪ Si los costos dependen del volumen de tráfico, pueden ocurrir oscilaciones
a
d
c
b
1 1+e
e0
e
1
1
0 0
inicialmente
a
d
c
b
dados dichos costos, 
encontrar nuevas rutas 
(redundando en nuevos 
costos)
2+e 0
00
1+e 1
a
d
c
b
0 2+e
1+e1
0 0
a
d
c
b
2+e 0
00
1+e 1
▪ Ejemplo:
• Ruteando hacia a, tenemos tráfico entrante a d, c, e con tasas 1, e (<1), 1
• Los costos de los enlaces son direccionales y dependientes del tráfico
e
1 1
e
1 1
e
1 1
dados dichos costos, 
encontrar nuevas rutas 
(redundando en nuevos 
costos)
dados dichos costos, 
encontrar nuevas rutas 
(redundando en nuevos 
costos)...
TD4 2022TD4 2022
Basado en la ecuación de Bellman-Ford (programación dinámica)
Algoritmo de ruteo distance vector
19
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
20
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
21
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
22
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
DV de 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
23
g h i
1 1
1 1 1
1 1
1 1
8 1
t0
▪ Los nodos sólo 
tienen estimaciones 
hacia sus vecinos 
directos
Asimetrías
(enlace faltante y 
costo más alto)
d e f
a b c
▪ Envían su vector de 
distancias (DV) local 
a sus vecinos
TD4 2022TD4 2022
Distance vector: ejemplo - iteración
24
Los nodos:
▪ Reciben DVs de 
los vecinos
▪ Computan su 
nuevo DV local
▪ Envían el nuevo 
DV local a sus 
vecinos
t1
g h i
1 1
1 1 1
1 1
1 1
8 1
d e f
a b c
TD4 2022TD4 2022
Distance vector: ejemplo - iteración
25
g h i
1 1
1 1 1
1 1
1 1
8 1
d e f
a b c
Los nodos:
▪ Reciben DVs de 
los vecinos
▪ Computan su 
nuevo DV local
▪ Envían el nuevo 
DV local a sus 
vecinos
t1
TD4 2022TD4 2022
Distance vector: ejemplo - iteración
26
g h i
1 1
1 1 1
1 1
1 1
8 1
d e f
a b c
Los nodos:
▪ Reciben DVs de 
los vecinos
▪ Computan su 
nuevo DV local
▪ Envían el nuevo 
DV local a sus 
vecinos
t1
TD4 2022TD4 2022
Distance vector: ejemplo - iteración
27
… y así sucesivamente en t2, t3, ...
Veamos ahora algunos ejemplos de los cómputos en los nodos
TD4 2022TD4 2022
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
28
g h i
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
▪ b recibe DVs de 
a, c, e
a b c
d e f
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) = ∞
t1
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
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
29
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: ejemplo
30
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) = ∞
g h i
1 1
1 1 1
1 1
1 1
8 1
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) = ∞
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
▪ c recibe DV de b
t1
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: ejemplo
31
g h i
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
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
a b c
d e fDc(a) = mín{cc,b+Db(a}} = 1 + 8 = 9 
D
c
(b) = mín{c
c,b
+D
b
(b)} = 1 + 0 = 1
D
c
(d) = mín{c
c,b
+D
b
(d)} = 1+ ∞ = ∞ 
D
c
(e) = mín{c
c,b
+D
b
(e)} = 1 + 1 = 2
D
c
(f) = mín{c
c,b
+D
b
(f)} = 1+ ∞ = ∞ 
D
c
(g) = mín{c
c,b
+D
b
(g)} = 1+ ∞ = ∞ 
D
c
(i) = mín{c
c,b
+D
b
(i)} = 1+ ∞ = ∞ 
D
c
(h) = mín{c
bc,b
+D
b
(h)} = 1+ ∞ = ∞ 
DV en c
D
c
(a) = 9
D
c
(b) = 1
D
c
(c) = 0
D
c
(d) = 2
D
c
(e) = ∞
D
c
(f) = ∞
D
c
(g) = ∞
D
c
(h) = ∞
D
c
(i) = ∞
▪ c recibe DV de 
b; computa:
t1
TD4 2022TD4 2022
Distance vector: difusión de información
t0 El estado de c en t0 sólo se ve en c
g h i
1 1
1 1 1
1 1
1 1
8 1
d e f
a b c
El estado de c en t0 se propagó a b y puede 
influir en los cómputos de hasta 1 hop de 
distancia (i.e., en b)
t1
El estado de c en t0 puede influir en los 
cómputos de hasta 2 hops de distancia (i.e., 
en b, a y e)
t2
El estado de c en t0 puede influir en los 
cómputos de hasta 3 hops de distancia (i.e., 
en b, a y e, y también en d, h y f)
t3
El estado de c en t0 puede influir en los 
cómputos de hasta 4 hops de distancia (i.e., 
en b, a, e, d, h, f, g, h e i)
t4
El estado de cada nodo se propaga a través de la red de manera iterativa:
 
t1 
t2 
 
t3 
 
t4 
TD4 2022TD4 2022
Distance vector: cambio de costo de enlaces
33
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
34
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 lopone en 9, vía y. Luego notifica a y de este nuevo costo.
…
TD4 2022TD4 2022
Comparación entre link state y distance vector
35
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