Algoritmos de enrutamiento
Páginas: 13 (3080 palabras)
Publicado: 1 de mayo de 2011
Índice
Shortest path routing 2
Distance vector routing 2
Estado de enlace 3
Enrutamiento jerárquico 5
Broadcast routing 5
Enrutamiento Multicast para clientes móviles 6
Algoritmos de control de congestión 7
Algoritmo de descarte de paquetes 7
Algoritmo de paquetes reguladores 7
Mecanismo de Traffic Shaping 8
Shortest path routing
El problema de encontrar las rutas máscortas tiene un papel muy importante en el diseño y análisis de las redes. Muchos de los problemas de ruteo pueden ser solucionados como problemas de las rutas más cortas media ves se le haya asignado un costo apropiado a cada link, reflejando su ancho de banda disponible, retardo por ejemplo.
Existen varios algoritmos para encontrar la ruta más corta si las esquinas de una red estáncaracterizadas por una métrica que no sea negativa. El más popular es el algoritmo de Dijktra's el cual es usado en el protocolo de Internet OSPF.
El algoritmo de Dijkstra's es representado con el siguiente pseudocódigo:
Dada una red G = (N, E), con un costo positivo Dij para todos los extremos (i, j∈N), un nodo de inicio S y un juego de nodos etiquetados permanentemente como P, la ruta más corta empiezadesde el nodo S a cada otro nodo j es encontrado de la siguiente forma:
Inicialmente P = {S}, DS = 0, and Dj = dSj for jj_=S ∈ N.
Paso 1: (encontrar el nodo más cercano) Encontrar ieP de modo que
Di = min
j_∈P
Dj
Asignar P = P∪{i}.Si P contiene todos los nodos entonces se detiene; el algoritmo se ha completado.
Paso 2: (actualizando todas las etiquetas) Para todos los nodos j_∈PDj = min[Dj,Di + dij ]
Ir al paso 1
Debido a que en cada paso del algoritmo se necesita un número de operaciones posicional a N, y los pasos están definidos como N-1 veces, el peor caso computacional es ON2. Usando colas de prioridad en el algoritmo se define como, el cual es una mejora sobre para redes escasas. De todos modos el requerimiento de espacio se incrementa y las operaciones encolas de prioridad se vuelven difíciles de implementar en una lógica de reconfiguración.
Distance vector routing
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.
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 mucho 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 enlaceen 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 en mismo protocolo.Una vez que el router tiene toda la información, actualiza su propia tabla reflejando los cambios y luego 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 cierta ciencia si ésta es verdadera o no.
El algoritmo de Bellman-Ford se adapta perfectamente al modo de...
Shortest path routing 2
Distance vector routing 2
Estado de enlace 3
Enrutamiento jerárquico 5
Broadcast routing 5
Enrutamiento Multicast para clientes móviles 6
Algoritmos de control de congestión 7
Algoritmo de descarte de paquetes 7
Algoritmo de paquetes reguladores 7
Mecanismo de Traffic Shaping 8
Shortest path routing
El problema de encontrar las rutas máscortas tiene un papel muy importante en el diseño y análisis de las redes. Muchos de los problemas de ruteo pueden ser solucionados como problemas de las rutas más cortas media ves se le haya asignado un costo apropiado a cada link, reflejando su ancho de banda disponible, retardo por ejemplo.
Existen varios algoritmos para encontrar la ruta más corta si las esquinas de una red estáncaracterizadas por una métrica que no sea negativa. El más popular es el algoritmo de Dijktra's el cual es usado en el protocolo de Internet OSPF.
El algoritmo de Dijkstra's es representado con el siguiente pseudocódigo:
Dada una red G = (N, E), con un costo positivo Dij para todos los extremos (i, j∈N), un nodo de inicio S y un juego de nodos etiquetados permanentemente como P, la ruta más corta empiezadesde el nodo S a cada otro nodo j es encontrado de la siguiente forma:
Inicialmente P = {S}, DS = 0, and Dj = dSj for jj_=S ∈ N.
Paso 1: (encontrar el nodo más cercano) Encontrar ieP de modo que
Di = min
j_∈P
Dj
Asignar P = P∪{i}.Si P contiene todos los nodos entonces se detiene; el algoritmo se ha completado.
Paso 2: (actualizando todas las etiquetas) Para todos los nodos j_∈PDj = min[Dj,Di + dij ]
Ir al paso 1
Debido a que en cada paso del algoritmo se necesita un número de operaciones posicional a N, y los pasos están definidos como N-1 veces, el peor caso computacional es ON2. Usando colas de prioridad en el algoritmo se define como, el cual es una mejora sobre para redes escasas. De todos modos el requerimiento de espacio se incrementa y las operaciones encolas de prioridad se vuelven difíciles de implementar en una lógica de reconfiguración.
Distance vector routing
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.
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 mucho 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 enlaceen 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 en mismo protocolo.Una vez que el router tiene toda la información, actualiza su propia tabla reflejando los cambios y luego 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 cierta ciencia si ésta es verdadera o no.
El algoritmo de Bellman-Ford se adapta perfectamente al modo de...
Leer documento completo
Regístrate para leer el documento completo.