El vector de distancias es un método de enrutamiento. Se trata de uno de los más importantes junto con el de estado de enlace. Utiliza el algoritmo de Bellman-Ford para calcular las rutas. Fue el algoritmo original de ARPANET. Se usó en DECNET, IPX y Appletalk. Lo usa el protocolo RIP (Routing Information Protocol), que hasta 1988 era el único utilizado en Internet. También se utiliza en los protocolos propietarios ampliamente extendidos IGRP y EIGRP de Cisco.
Funcionamiento
El enrutamiento de un protocolo basado en vector de distancias requiere que un router informe a sus vecinos de los cambios en la topología periódicamente y en algunos casos cuando se detecta un cambio en la topología de la red. Comparado a los protocolos de estado de enlace, que necesitan que un router informe a todos los nodos de una red acerca de los cambios en su topología, los algoritmos de vector de distancias tienen mucha menos complejidad computacional. Además, las principales características de los diferentes algoritmos VD (vector de distancias) son siempre las mismas.
El algoritmo VD se basa en calcular la dirección y la distancia hasta cualquier enlace en la red. El costo de alcanzar un destino se lleva a cabo usando cálculos matemáticos como la métrica del camino. RIP cuenta los saltos efectuados hasta llegar al destino mientras que IGRP utiliza otra información como el retardo y el ancho de banda.
Los cambios son detectados periódicamente ya que la tabla de enrutamiento de cada router se envía a todos los vecinos que usan el mismo protocolo. Una vez que el router tiene toda la información, actualiza su tabla e informa a sus vecinos de los mismos. Este proceso se conoce también como “enrutamiento por rumor” ya que los nodos utilizan la información de sus vecinos y no pueden comprobar a ciencia cierta si ésta es verdadera o no.
El algoritmo de Bellman-Ford se adapta perfectamente al modo de aprendizaje de los nodos que “nacen”, es decir, cuando se conectan a la red. A medida que el algoritmo progresa, el nuevo nodo va adquiriendo más información sobre el resto de nodos de la red. Este algoritmo converge rápidamente cuando se conectan nuevos nodos. Por ello se suele decir que las buenas noticias viajan rápido por la red.
Ejemplo
En esta red, tenemos 4 routers A, B, C y D:
Empezamos calculando las matrices de distancias para cada router. El “camino más corto” está marcado con el color verde, un “camino más corto” nuevo está indicado en amarillo
T=0
desde A
vía A
vía B
vía C
vía D
a A
a B
3
a C
23
a D
desde B
vía A
vía B
vía C
vía D
a A
3
a B
a C
2
a D
desde C
vía A
vía B
vía C
vía D
a A
23
a B
2
a C
a D
5
desde D
vía A
vía B
vía C
vía D
a A
a B
a C
5
a D
T=1
desde A
vía A
vía B
vía C
vía D
a A
a B
3
25
a C
5
23
a D
28
desde B
vía A
vía B
vía C
vía D
a A
3
25
a B
a C
26
2
a D
7
desde C
vía A
vía B
vía C
vía D
a A
23
5
a B
26
2
a C
a D
5
desde D
vía A
vía B
vía C
vía D
a A
28
a B
7
a C
5
a D
T=2
desde A
vía A
vía B
vía C
vía D
a A
a B
3
25
a C
5
23
a D
10
28
desde B
vía A
vía B
vía C
vía D
a A
3
25
a B
a C
26
2
a D
31
7
desde C
vía A
vía B
vía C
vía D
a A
23
5
33
a B
26
2
12
a C
a D
33
9
5
desde D
vía A
vía B
vía C
vía D
a A
10
a B
7
a C
5
a D
T=3
desde A
vía A
vía B
vía C
vía D
a A
a B
3
25
a C
5
23
a D
10
28
desde B
vía A
vía B
vía C
vía D
a A
3
7
a B
a C
8
2
a D
31
7
desde C
vía A
vía B
vía C
vía D
a A
23
5
15
a B
26
2
12
a C
a D
33
9
5
desde D
vía A
vía B
vía C
vía D
a A
10
a B
7
a C
5
a D
Limitaciones
Un problema es el de la transmisión de malas noticias por la red tales como la ruptura de un enlace o la desaparición de un nodo. Este algoritmo converge lentamente en estos casos. Aunque el principal inconveniente de este algoritmo es el de la cuenta a infinito.
El algoritmo Bellman-Ford utilizado en VD no previene de la aparición de bucles. Aunque protocolos como IGRP están modificados para detectar bucles en la red. El problema de la cuenta a infinito es que hace que los costes o distancias se incrementen indefinidamente sin que el algoritmo llegue a converger nunca.
Para ilustrarlo, tomemos como ejemplo el de la figura.
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).
Mientras no se interrumpa la cuenta a infinito, el algoritmo no converge. Aunque se han propuesto diversas soluciones a este problema
Recorte por horizonte dividido
Se trata de una de las soluciones utilizadas para solventar el conteo a infinito. Es una modificación del algoritmo VD para evitar que un nodo informe a su vecino sobre la distancia que conoce hasta el nodo X cuando la trayectoria hacia X pasa a través de ese nodo vecino. Lo que realmente hace es informar que dicha distancia es infinita.
El algoritmo por horizonte dividido consigue que las “malas noticias” se propaguen con la misma rapidez que las “buenas noticias”. Sin embargo este algoritmo no funciona para todas las combinaciones de topologías posibles por lo que solo mitiga el problema sin solucionarlo. Esto ha llevado al desarrollo de más complejos algoritmos de encaminamiento tales como los de estado de enlace.
Sección "Link-State Versus Distance Vector" en el capítulo "Routing Basics" en el "Internetworking Technology Handbook" de Cisco (en inglés)
Sección 5.2 "Algoritmos de Ruteo" en el capítulo "5 THE NETWORK LAYER" de "Redes de Computadores", de Andrew S. Tanenbaum, 4.ª edición (en inglés)
Datos:Q1229441
Septiembre 22, 2021
vector, distancias, vector, distancias, método, enrutamiento, trata, más, importantes, junto, estado, enlace, utiliza, algoritmo, bellman, ford, para, calcular, rutas, algoritmo, original, arpanet, usó, decnet, appletalk, protocolo, routing, information, proto. El vector de distancias es un metodo de enrutamiento Se trata de uno de los mas importantes junto con el de estado de enlace Utiliza el algoritmo de Bellman Ford para calcular las rutas Fue el algoritmo original de ARPANET Se uso en DECNET IPX y Appletalk Lo usa el protocolo RIP Routing Information Protocol que hasta 1988 era el unico utilizado en Internet Tambien se utiliza en los protocolos propietarios ampliamente extendidos IGRP y EIGRP de Cisco Indice 1 Funcionamiento 2 Ejemplo 3 Limitaciones 4 Recorte por horizonte dividido 5 Vease tambien 6 Referencias 7 Informacion AdicionalFuncionamiento EditarEl enrutamiento de un protocolo basado en vector de distancias requiere que un router informe a sus vecinos de los cambios en la topologia periodicamente y en algunos casos cuando se detecta un cambio en la topologia de la red Comparado a los protocolos de estado de enlace que necesitan que un router informe a todos los nodos de una red acerca de los cambios en su topologia los algoritmos de vector de distancias tienen mucha menos complejidad computacional Ademas las principales caracteristicas de los diferentes algoritmos VD vector de distancias son siempre las mismas El algoritmo VD se basa en calcular la direccion y la distancia hasta cualquier enlace en la red El costo de alcanzar un destino se lleva a cabo usando calculos matematicos como la metrica del camino RIP cuenta los saltos efectuados hasta llegar al destino mientras que IGRP utiliza otra informacion como el retardo y el ancho de banda Los cambios son detectados periodicamente ya que la tabla de enrutamiento de cada router se envia a todos los vecinos que usan el mismo protocolo Una vez que el router tiene toda la informacion actualiza su tabla e informa a sus vecinos de los mismos Este proceso se conoce tambien como enrutamiento por rumor ya que los nodos utilizan la informacion de sus vecinos y no pueden comprobar a ciencia cierta si esta es verdadera o no El algoritmo de Bellman Ford se adapta perfectamente al modo de aprendizaje de los nodos que nacen es decir cuando se conectan a la red A medida que el algoritmo progresa el nuevo nodo va adquiriendo mas informacion sobre el resto de nodos de la red Este algoritmo converge rapidamente cuando se conectan nuevos nodos Por ello se suele decir que las buenas noticias viajan rapido por la red Ejemplo EditarEn esta red tenemos 4 routers A B C y D Empezamos calculando las matrices de distancias para cada router El camino mas corto esta marcado con el color verde un camino mas corto nuevo esta indicado en amarillo T 0 desde A via A via B via C via Da Aa B 3a C 23a D desde B via A via B via C via Da A 3a Ba C 2a D desde C via A via B via C via Da A 23a B 2a Ca D 5 desde D via A via B via C via Da Aa Ba C 5a DT 1 desde A via A via B via C via Da Aa B 3 25a C 5 23a D 28 desde B via A via B via C via Da A 3 25a Ba C 26 2a D 7 desde C via A via B via C via Da A 23 5a B 26 2a Ca D 5 desde D via A via B via C via Da A 28a B 7a C 5a DT 2 desde A via A via B via C via Da Aa B 3 25a C 5 23a D 10 28 desde B via A via B via C via Da A 3 25a Ba C 26 2a D 31 7 desde C via A via B via C via Da A 23 5 33a B 26 2 12a Ca D 33 9 5 desde D via A via B via C via Da A 10a B 7a C 5a DT 3 desde A via A via B via C via Da Aa B 3 25a C 5 23a D 10 28 desde B via A via B via C via Da A 3 7a Ba C 8 2a D 31 7 desde C via A via B via C via Da A 23 5 15a B 26 2 12a Ca D 33 9 5 desde D via A via B via C via Da A 10a B 7a C 5a DLimitaciones EditarUn problema es el de la transmision de malas noticias por la red tales como la ruptura de un enlace o la desaparicion de un nodo Este algoritmo converge lentamente en estos casos Aunque el principal inconveniente de este algoritmo es el de la cuenta a infinito El algoritmo Bellman Ford utilizado en VD no previene de la aparicion de bucles Aunque protocolos como IGRP estan modificados para detectar bucles en la red El problema de la cuenta a infinito es que hace que los costes o distancias se incrementen indefinidamente sin que el algoritmo llegue a converger nunca Para ilustrarlo tomemos como ejemplo el de la figura Inicialmente A esta 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 traves de C por lo que actualiza su tabla registrando la distancia 2 1 3 hasta AEn 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 Mientras no se interrumpa la cuenta a infinito el algoritmo no converge Aunque se han propuesto diversas soluciones a este problemaRecorte por horizonte dividido EditarSe trata de una de las soluciones utilizadas para solventar el conteo a infinito Es una modificacion del algoritmo VD para evitar que un nodo informe a su vecino sobre la distancia que conoce hasta el nodo X cuando la trayectoria hacia X pasa a traves de ese nodo vecino Lo que realmente hace es informar que dicha distancia es infinita El algoritmo por horizonte dividido consigue que las malas noticias se propaguen con la misma rapidez que las buenas noticias Sin embargo este algoritmo no funciona para todas las combinaciones de topologias posibles por lo que solo mitiga el problema sin solucionarlo Esto ha llevado al desarrollo de mas complejos algoritmos de encaminamiento tales como los de estado de enlace Vease tambien EditarEncaminamiento RIP protocolo IGRP Estado de enlaceReferencias EditarInformacion Adicional EditarSeccion Link State Versus Distance Vector en el capitulo Routing Basics en el Internetworking Technology Handbook de Cisco en ingles Seccion 5 2 Algoritmos de Ruteo en el capitulo 5 THE NETWORK LAYER de Redes de Computadores de Andrew S Tanenbaum 4 ª edicion en ingles Datos Q1229441Obtenido de https es wikipedia org w index php title Vector de distancias amp oldid 129167386, wikipedia, wiki, leyendo, leer, libro, biblioteca,
