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.