6-algoritmos de enrutamiento de internetv2
DESCRIPTION
6-Algoritmos de Enrutamiento de Internetv2TRANSCRIPT
Algoritmos de enrutamiento deInternet
Jhon Jairo Padilla Aguilar, PhD.
Algoritmos de enrutamiento
► Los algoritmos de enrutamiento son diseliados paraalcanzar unos objetivos
1■ Los objetivos dependen del tipo de red► Pueden ser clasificados en dos grander categorias:
❑ Orientados a usuario.❑ Orientados a red.
Tipos de Algoritmos de enrutamientoOrientados a usuario
Una red necesita proveer buen servicio a cada usuarioEl trafico debe moverse rapidamente desde una fuente aldestino.
Orientados a redSe enfocan en cam° proveer un enrutamiento justo yeficienteMuchos usuarios reciben servicio aceptable, en vez deproveer el mejor servicio a unos pocos usuarios.
Algoritmos orientados a usuario
Existen dos algoritmos que tienen profundoimpacto sobre las redes de datos y en particularsobre enrutamiento de Internet:
Algoritmo Belman- FordAlgoritmo Dijkstra
► Ambos son Ilamados Algoritmos del camino mos corto:La meta es encontrar el camino mas corto entre la fuente y eldestino.
Tipos de algoritmos de enrutamientoLos algoritmos delcamino mas amplyson utiles para
Los algoritmos delcamino ma's corto sonaplicables a redes IP
ALGORITMOS DE ENRUTAMIENTO enrutamiento dellamadas dinamico dcredes de telefonia
ALGORITMO DEL CAMINO MASCORTO
rALGORITMO DEL CAMINO MASAMPLIO
NBellman-Ford
VisionCentralizado
Visit:5nDistribuida-
Aproximacion VectorDistancia
Dijsktra
VisionCentralizado
VisionDistribuida
Algoritmo del primercamino mas corto
Aproximacion AproximacionBellman-Ford Dijsktra
Criterios para la escogencia de la ruta► La election de una ruta se realiza con base en un criterio:
Numero de saltosCosto
Retardo
Eficiencia
Criterio del menor nUmero de saltos► Se elige el camino que atraviesa el menor nUmero denodos a traves de la red
► Se puede medir facilmente► Deberla minimizar el consumo de recursos de la red
Criterio del minimo costo
Criterio de minimo costo: EjemploMenor nUmero saltos
Minimo costo
Menor numero de saltos vs. Minimo costo
► Ambos son relativamente justosTiempo de procesamiento similar
El criterio de minim° costo es mas flexible (alas usado)► Ejemplos de minim° costo:Algoritmo de Dijkstra,Algoritmo de Bellman-Ford
Caracteristicas de un Algoritmo deEncaminamiento
• lnstante de decision:Datagrama: Con cada paquete
Circuito virtual: Una vez al establecimiento del circuito virtual• Lugar de decision:
Distribuido: Cada nodo toma una decision a medida que recibelos paquetesCentralizado: Decision tomada en un nodo centro de control dela redEncaminamiento de origen: La estaciOn origen determina laruta y la comunica a la red.
• Fuentes de informacion de la red: De donde se toma lainformacion para las decisiones
• Tiempo de ,actualizacion: Cada cuanto se renueva lainformacion base para tomar decisiones
Enrutamiento Distribuido vs. EnrutamientoCentralizado
Fuente de informaciOn de la red► Las decisiones de encaminamiento se toman con baseen el conocimiento de:
Topologia de la red► Carga de la red
► Costo de los enlaces
Encaminamiento distribuido:Cada nodo toma information local y de los nodosadyacentesEncaminamiento centralizado:
El nodo central usa information de todos los nodos
Tiempo de actualizaciOn
Algoritmos de Enrutamiento delcamino mas corto
Algoritmos del camino mas corto► Estudiaremos dos tipos:
Bellman FordDijkstra
Algoritmo de Bellman Ford
Algoritmo de Bellman Ford► Utiliza el criterio del minim° costo► Puede tener dos modalidades:
CentralizadoDistribuido
► Modalidad Centralizada:Se requiere una entidad que conozca Ia topologia de Ia red y los costosde cada enlaceEl algoritmo se ejecuta en Ia entidad central, quien decide los caminosoptimos ► Modalidad distribuida:
Cada nodo ejecuta un algoritmo de enrutamiento para decidir elsiguiente salto
La ejecucion del algoritmo en cada nodo hace que se complementenunos con otros, obteniendo una operaci6n armoniosa en toda Ia red.
Se requiere un protocolo de enrutamiento para intercambiarinformacion entre nodos
Algoritmo Bellman-Ford Centralizado
Consideraciones
• Para los Nodos que estan
conectados d irectamente:
•El costo del enlace es de
valor finito. Ej: d46= I 5.
•Costo para los Nodos que no
esten conectados directamente:
&Foci.
15
= Costo del enlace entre los nodos I y j.
Dry = Costo total del camino entre los nodos I y j,calculado usando el criterio del minim° costo.
•Ej: D46 = 2 D16 = 3
d46=15 (1,6=co
Algoritmo Bellman-Ford Centralizado
Camino a waves de la redConsideraciones
•Supongamos un Nodo generic° k,conectado directamente al nodo j. Portanto dkj es un valor finito.
• Ecuaciones de Bellman:
Dii = 0, for all
•La OperaciOn de un algoritmo real=Costo minimo del camino desde el nodo ihasta el nodo j cuando se hacen hasta h
saltos.
usa una variation donde se vanhaciendo iteraciones a troves de losdiferentes saltos del camino.
Algoritmo Bellman-Ford Centralizado
ALGORITHM 2.1 Bellman-Ford centralized algorithm.
Initialize for nodes i and j in the network:
—(0) —(0)Dii = 0,
for all i:
For h =0 to N - 1 do—(h+i)
Do = :Do. for i # j. (2.2.2a)
Dii = 0,
= .I4j
for all i (2.2.2b)
{—()hDik dkj}. for i j. (2.2.2c)
-
Ejemplo: AproximaciOn Bellman-Fordmediante iteraciones por saltos.Camino escogido por ser el
Objetivo: Encontrar el camino mas cortodesde nodo I al nodo 6.
• Cuando h=1, significa la consideracion de uncamino mediante enlace directo entre losnodos I y6. Para este caso no hay ningunoentonces: —(1)
de menor costo
()2k=3: +d36=2+1=3
()k=5: 4-d56=3-1-1=4
—(2)k =4: D14 +46=1+15=16.
D16 oo
•Con h=2 , el camino 1-4-6 es un camino dedos saltos 1-4 yminimo es 16.
D(2)
4-6, en este caso el costo
= 1616
•Con h=3, hay tres posibles caminos quedeben ser considerados:4-6
1-4-3-6, 1-4-5-6, 1-2-15
Caracteristicas del Algoritmo Bellman Ford
► Utiliza el criterio del minim costo (no usa el menornumero de saltos)► No se requiere conocer el cannino entero, solo se
requiere conocer el siguiente nodo k Para el cual el costoes minim° (realiza iteraciones). Esto se puede hacer deuna forma simple.
SoluciOn:
r)(1h3) Path r)(1h4)I, DIII," Path
0 x - oo - oo1 1 1-2 oo - 12 1 1-2 2 1-4-3 13 1 1-2 2 1-4-3 14 1 1-2 2 1-4-3 15 1 1-2 2 1-4-3 1
Path T)(115i) Path Dr6) Path
- oo - oo -1-4 ,o - oo -
1-4 3 14-5 16 1-4-61-4 3 14-5 3 14-3-61-4 3 1-4-5 3 1-4-3-61-4 3 1-4-5 3 14-3-6
Algoritmo de Bellman Ford: AproximaciOnDistribuida
La aproximacion centralizada no funciona en redes connaturaleza distribuidaPara lograrlo, se puede hacer un ligero cambio al orden
usadopara el calculo del camino de costo minimo:
Ahora se roman como posibles nodos k, los nodos que estandirectamente conectados al nodo origen 1, es decir, los vecinos
de i (denotados por ).
Cada nodo va haciendo el calculo de alai es su mejor siguientenodo de entre sus vecinos y agrega el costo de este enlace alcosto total hacia el destino. (Aproximacion VectorDistancia, usada originalmente en Arpanet)
VisiOn distribuida:► Se requiere de la distribuciOn periodica de los costos de los enlaces por
parte de los vecinos► Por tanto, los costos dependen del tiempo y pueden cambiar para
diferentes momentos.► Asi se cambian las expresiones para el costo total y el costo por enlace
por: nki(i) y d,k(t) respectivamente.► Los enlaces pueden aparecer y desaparecer con el tiempo (red dinamica)► El costo del camino k-j se puede usar en el camino hacia i siempre y
cuando el enlace i-k este disponible.► Esto se indica en el costo k-j mediante: Dkij(t)
AproximaciOn distribuida del algoritmo deBellman Ford
► Por tanto, el algoritmo puede describirse asi:
A LGORITH M 2.2 Distance vector algorithm (computed at node i).
Initialize
Di, (t) = Dii(t) = oo, (for node j that node i is
aware of).
For (nodes j that node i is aware of) doDii(t) = min Idik(t) + Di .(t)IkJ• for jOi.
(2.2.4a)
(2.2.4b)k directly connected to i
AproximaciOn distribuida: Ejemplo
Ejemplo: Asuma que el nodo k, el cual esta conectado directamente alnodo i, esta enviando los costos Tyk..(0 al mismo instante que otros nodosconectados a i. Asuma que el costojae los enlaces directos, dik(t), no cambiacon el tiempo. Encontrar el costo del camino mas corto desde el nodo I al6.
15
AproximaciOn distribuida: Ejemplo•Supongarnos que tenemos ventanas discretas
de tiempo y que el nodo I recibe lainformacion de costos en cada ventana.
•Cuando t=0,significa que el nodo 4, ve elcosto hacia el nodo 6 a partir de cero saltos.•Cuando t=1, significa que el nodo 4, ve elcosto hacia el nodo 6 cuando ha recibido
informaciOn de un salto y asi sucesivamente.
15
Time, t D44, ( t ) D;6(t) Computation at node I D16(t)
minv114(1) +D4 6(1). di2(1) +V26(010 oc A-.; mint] + s. 1 + x) oc
1 15 oc min{l +15.1 + x} 16
2 2 3 min(1 +2.1 +3) 3
Conclusiones sobre la aproximaciOndistribuida
► La aproximaci6n vector distancia se basa en elconocimiento de un nodo sobre el costo desde susnodos vecinos a un nodo destino para determinar sumejor camino.► El nodo hace calculos periodicos cuando recibeinformation de sus vecinos.La idea principal es que un nodo k necesita distribuirsu costo hasta j, dado por Dkj(0, a todos sus vecinosconectados directamenteLa dependencia de los costos con i y t significa
quecads nodo i podria potencialmente obtener talinformation en instantes de tiempo t diferentes.
Algoritmo de Dijkstra
Dijkstra: Aproximacion centralizada► Suponga una red con N nodos. La lista de todos losnodos se denominard:
OperaciOn del AlgoritmoSe compone de dos procesos principales:
La expansion de la lista SCalculo del camino mas corto para nodos que son vecinos delos nodos de la lista S, Pero que aun no estan en ella.
Operacion del algoritmoCa!cub de la lista S:
La lista S se expande mediante la consideration de un nodo kvecino del nodo 1 con el camino del menor costo desde I. En codaiteration el algoritmo considera los nodos vecinos de k, los cualesno estan at:in en la lista S Para ver si el minimo costo cambiadesde la ultimo iteration.
Ejemplo:Suponga que e/ nodo I desea encontrar el camino mascorto a todos los nodos en la red.Inicialmente S={/} y S'={2,3,4,5,6}
► El camino mas corto a cada uno de los nodos que sonvecinos directos del nodo I puede ser facilmenteencontrado, mientras que el costo del resto es co.
D12 = 1 D14 = Do = D15 =86 =
D13 = min{ D13, D12 + d23} = min{ool 1 + 2} =
3
DI4 = Min1D14, D12 + d24) = minil, 1 + 1) = 1.
Ejemplo: Secuencia de operacion totalit -11 S.11,21
O
S..1 1,2,4, ?•1
Iteration List, S D12 Path D13 Path Di4 Path D15 Path D16 Path
1 (1) 1 1-2 oo - 1 1-4 oo - oo -
2 (1, 2) 1 1-2 3 1-2-3 1 1-4 00 - oo -
3 11, 2, 4) 1 1-2 2 1-4-3 1 1-4 3 1-4-5 16 1-4-6
4 {1, 2, 4, 3} 1 1-2 2 1-4-3 1 1-4 3 1-4-5 3 1-4-3-6
5 11, 2, 4, 3, 5) 1 1-2 2 1-4-3 1 1-4 3 1-4-5 3 1-4-3-6
6 (1, 2, 4, 3, 5,6) 1 1-2 2 1-4-3 1 1-4 3 1-4-5 3 1-4-3-6
Algoritmo de Dijkstra: AproximaciOncentralizada
ALGORITHM 2.3 Dijkstra's shortest path first algorithm (centralized approach).1. Start with source node I in the permanent list of nodes considered, i.e., S = Ii); all the rest
of the nodes are put in the tentative list labeled as 8'. Initialize
D- = d.., for all j Si.
2. Identify a neighboring node (intermediary) k not in the current list S with the minimumcost path from node i, i.e., find k E 8' such that D k = minmEs,
Add k to the permanent list S, i.e., S = S U
Drop k from the tentative list S', i.e., S'Mk}.
If S' is empty, stop.
3. Consider the list of neighboring nodes, M. of the intermediary k (but do not considernodes already in S) to check for improvement in the minimum cost path, i.e.,for j€ Ark n S'
=ming2.,1,Thk + do. (2.3.1)
Go to Step 2.
■
Dijkstra: Aproximacion distribuida► Los pasos son los mismos que para el algoritmocentralizado► Las iteraciones toman en cuenta la information
distribuida por los nodos en el instante en que se toma ladecision
Algoritmo de Dijkstra: AproximaciOnDistribuida
ALGORITHM 2.4 Dijkstra's shortest path first algorithm (a distributed ap-proach).
1. Discover nodes in the network, Ar, and cost of link k-m, dikm(t), as known to node 1 at thetime of computation, f.
2. Start with source node I in the permanent list of nodes considered, i.e., S = (I); all the restof the nodes are put in the tentative list labeled as 5`. Initialize
D (0= di..(t) ' for all j G 8'.
3. Identify a neighboring node (intermediary) k not in the current list S with the minimumcost path from node t, i.e., find k E S' such that ak(t) = (0.
Add k to the permanent list S, i.e., S = S U (k),
Drop k from the tentative list 8', i.e., 5' = S'\(k).
If S' is empty, stop.
4. Consider neighboring nodes Ark of the intermediary k (but do not consider nodes alreadyin S) to check for improvement in the minimum cost path, i.e.,
for j Ark n S'
(2.3.2)
Go to Step 3.
ComparaciOn de los algoritmos Bellman-Ford y Dijkstra
Caracteristica
Objetivo
Principio de operacicin
Complejidad Computacional:
Conocida como la funcion "0".N: niunero total de nodos. L:nUmero total de enlaces.
Complejidad computacionalpara una red completamenteconectada. El niirnero deenlaces bidireccionales es N(N-
1)12
Algoritmo Bellman-Ford
Calcula el camino ma's corto paraun solo par de nodos origen-destino
El nodo intermedio k inicialmentepuede ser cualquiera de todos losnodos vecinos al nodo j. Se escogeel que tenga el camino mas corto.
0(LN).
0(N3).
Algoritmo Dijkstra
Calcula el camino mas corto detodos los destinos desde un mismonodo origen (algunas veces llamadoarbol del camino mas corto).
El nodo k intermedio es el primernodo en el camino entre i y j. Seescoge entre los vecinos de i. Unavez que es seleccionado, queda fijo.Luego, el calculo del camino mascorto se realiza para todo j que antino haya sido cubierto.
0(N2)Pero puede ser mejoradaa0(L+NlogN) usando una buenaestructura de datos.
0 (N2) .
Tarea► Simular alguno de los dos algoritmos (Bellman-Ford,Dijkstra) en sus dos versiones (centralizada y distribuida),suponiendo que ya se tiene la information de los costosen cada nodo.► La topologia de la red es la misma del ejemplo:
15
Calculo del camino mas corto conalmacenamiento de los caminos candidatos
Ejemplo► Supongase la red de la figura. Se quiere it del nodo I al 6.
► Supongase que se tiene el listado de caminos candidatos de la tabla.► Suponga que el costo del enlace 4-3 cambia de I a 5. El camino de
menor costo inicial ya no lo sera (nuevo costo total=7). Loscaminos de la I a y 3a fila reran mar cortos. Se puede elegircualquiera de los dos.
► La bi:isqueda es mar simple.
Path Cost1-2-3-6 (112 + d23 + d36 = 41-4-3-6 d14 + d43 + d36 =1-4-5-6 d14 + d45 + d56 = 414-6 (44 +46= 16
Algoritmo del camino mas corto con pathcaching
► El calculo es realizado en un tiempo t.► p: camino candidato entre los nodos i y
► El costo del camino mas corto en el tiempo t sera:
link !-»t in path p
► ti„,(f) : costo del enlace I-m en el tiempo t tal como se
conoce en el nodo i
► La sumatoria se hace tomando los enlaces del camino p
: lista de caminos candidatos entre i y j
► 1, : el mejor camino
Algoritmo del camino mas corto con pathcaching
ALGORITHM 2.6 Shortest path computation when candidate paths are known.
At source node i, a list of candidate paths Pg to destination node j is available,and link cost, d'im(t), of link 1-m at time t is known:
11 Initialize the least cost:Dij(I) = oo
// Consider each candidate path in the listfor (p in PO do
D;1/P(t) = 0for (link /-m in path p) do // add up cost of links for this path
D,11 (1) = Dil1p(1) (2.5.2)end for
if (billp(t) < Dij(t)) then // if this is cheaper, note itDij(t) = Dwp(t)
P=Pend if
end do
Concluyendo...► La lista de caminos candidatos no contiene todos loscaminos posibles
► El use de la lista de caminos candidatos agiliza Iabusqueda
► Requiere de nnas recursos de memoria para elalmacenamiento de los caminos candidatos
► Se podria ignorar un camino que es mas corto pero queno esti en Ia lista de caminos candidatos
Ej emplo■ Camino nrias corto es I -4-3-6, costo 3
► Otros caminos menos cortos que siguen en ordenascendente:
I -2-3-6 (costo=4)1-4-5-6 (costo=4)
1-2-4-3-6 (costo=4)
15
Algoritmos de Enrutamiento delcamino mas amplio
Enrutamiento del camino mas amplioLos algoritmos del camino nnas corto esta") basados enuna propiedad aditiva del costo
► En muchos entornos de red, no es otil esta aproximacion:Enrutamiento de Ilamadas dinamico (red telefonica)Enrutamiento con Calidad de Servicio
► En estas situaciones, el costo no es aditivo.► Usaremos una propiedad de costo no aditivo: costocOncavo (la analizaremos a continuaciOn)
Ancho de banda de un cammo► El ancho de banda de un camino esti_ dado por el anchode banda del enlace con el minim° ancho de bandadisponible (propiedad no aditiva)
Ancho de bandapara el camino p:
T3illp = min
Enlace I (b= 10)Enlace 3 (b=7)
Enlace 2 (b=5)
Ancho de banda del camino min{10. 5. 7} = 5
I bibn (0link 1-in in path p
Ejemplo: camino mas amplio con pathcaching
► Suponga la red de la figura, con los anchos de bandaespecificados para cada enlace
► Suponga la lista de caminos candidatos entre el nodo I yel nodo 5: Path Cost
1-2-3-5 minfbil, b)3. 1)35 ) = 101-4-3-5 mini/314. b41. b15) = 151-4-5 minfbm, b45) = 20 < - Camino mas amplio
(camino de maxima capacidadResidual)
50
40
Concluyendo...► Se escoge el cannino de maxim° ancho de banda entre loscaminos candidatos► El ancho de banda de un camino es el minimo entre losenlaces del cannino
► Si se asume que el costo de un enlace es el ancho debanda multiplicado por - I(los costos son negativos):
El camino con maxim° ancho de banda sera aquel cuyo costosea mas negativo (el minim° costo): can-lino mas corto noaditivo (concavo)
Algoritmo del camino mas amplio con pathcaching
ALGORITHM 2.7 Widest path computation (non-additive, concave) when candidatepaths are known.
At source node i, a list of candidate paths to destination node j is available,and link bandwidth, bibn(1), of link 1-m at time t is known:II Initialize the least bandwidth:
Bii(0= 0for p in P1.1 do
Billp(t) = ppfor (link 1-m in path p) do II find bandwidth of the bottleneck link
Pijip(t) = min 11341p(t), blm(t) (2.6.2)
end forif (Bwp(t) ^ B4(0) then // if this has more bandwidth, note it
Bzi(t) = Billp(t)P=P
end ifend do
Algoritmo del camino mas ampliosin path caching
Algoritmo del camino mas anchorAproximaciOn basada en Dijkstra
ALGORITHM 2.8 Widest path algorithm, computed at node i (Dijkstra-based).
1. Discover list of nodes in the network, N and available bandwidth of link k-m, bikm(1), asknown to node i at the time of computation, t.
2. Initially, consider only source node i in the set of nodes considered, i.e., S = (i); mark theset with all the rest of the nodes as S'. Initialize
3. Identify a neighboring node (intermediary) k not in the current list S with the maximumbandwidth from node i, i.e., find k E SI such that 13.k(t) = max„ €s, B-m(t)
Add k to the list S, i.e., S = S U (k)
Drop k from 8', i.e., 8' = S'\{k).
If S' is empty, stop.
4. Consider nodes in 5' to update maximum bandwidth path, i.e.,for j E
(2.7.1)
Go to Step 3.
Algoritmo del camino mas anchorAproximaciOn basada en Dijkstra
Para el nodo 2:
1313 = max(/313. min(B12, b23)1= max10, min(30, 10)1= 10 // use 1-2-3
B1 = m a xi B 14 min(B12, b241) = max(20, min(30, 10)) = 20 // stay on 1-2
B = max(Bis, min(B12, b25)) = max(0, min(30, 0)) = 0 // no change
Para el nodo 4:
Iteration List, S
1 (1)
2 {1.2)
3 11,2, 4)
4 11,2, 4, 3)
5 (1. 2. 4. 3. 5}
B12—3030303030
1313= MaXIB13, min(B14. b43)} = max(10, min(20, 15)) = 15 // use 1-4-3
B15 = max{/315. min{B14, bas}} = max(0, min120, 40))= 20 // use 1-4-5
Path B13 Path B14 Path B15 Path
1-2 0 — 20 1-4 0 —
1-2 10 1-2-3 20 1-4 0 —
1-2 15 14-3 20 1-4 20 1-4-51-2 15 1-4-3 20 1-4 20 1-4-5
1-2 15 1-4-3 20 1-4 20 1-4-5
Algoritmo del camino Inas anchorAproximacion basada en Bellman-Ford
ALGORITHM 2.9 Widest path algorithm, computed at node i (Bellman—Ford-based).
Initialize
Wii(1)= 0: TI,j(t) = 0, (for node j that node I is aware of). (2.7.2a)
For (nodes j that node I is aware of) do
Ai(1)= max min Ibik(t).—Biki(01 , for j0 1. (2.7.2b)k directly connected to i
Bibliografia► Este material use como base:
Deepankar Medhi.«Network Routing: Algorithms, Protocolsand Architectures». Ed. Morgan Kaufmann.Informer de Avance de la Tesis Doctoral de la MsC. LineYasmin
Becerra.