jueves, junio 11, 2015

Algoritmos de Enrutamiento

ALGORITMOS DE ENRUTAMIENTO POR VECTOR DISTANCIA Y ESTADO DE ENLACE 

ALGORITMOS DE ENRUTAMIENTO
Estos algoritmos permiten la toma de decisión a nivel de la capa de red, de la línea de salida por donde un paquete deberá ser transmitido, garantizando que éste llegue a su destino por la ruta más eficiente. A continuación mencionaremos dos algoritmos de enrutamiento utilizados en las redes actuales. 

ENRUTAMIENTO POR VECTOR DISTANCIA
El algoritmo de enrutamiento por vector distancia, también conocido como algoritmo Bellman-Ford distribuido y algoritmo Ford-Fulkerson, es el algoritmo utilizado en el protocolo RIP (Routing Information Protocol o Protocolo de Información de Enrutamiento), el IGRP (Interior Gateway Routing Protocol, o Protocolo de enrutamiento de gateway interior) es un protocolo propietario patentado y desarrollado por Cisco que se emplea con el protocolo TCP/IP según el modelo (OSI) Internet y el EIGRP (Enhanced Interior Gateway Routing Protocol, Protocolo de enrutamiento de gateway interior mejorado) que es un protocolo de encaminamiento vector distancia avanzado, propiedad de Cisco Systems, que ofrece lo mejor de los algoritmos de vector distancia y del estado de enlace. Este algoritmo es de tipo dinámico, y su funcionamiento consiste en que cada enrutador mantenga una tabla de enrutamiento que contiene un registro de cada nodo de la subred. El registro contiene por lo general las siguientes entradas, una con la línea con la dirección del destino, un registro con la métrica (distancia al destino) y otro registro con la dirección del nodo vecino a través del cual se llega al nodo destino.

La métrica usada puede contener cantidad de saltos, retardo de tiempo en milisegundos, número total de paquetes encolados o largo de la ruta. El enrutador puede medir los retardos con paquetes especiales ECO que el receptor marca con la hora y lo regresa al enrutador que origina la petición de ECO.

Algoritmo
1. Inicializar la tabla colocando distancia al mismo nodo igual a cero
2. Cada nodo calcula la distancia entre él mismo y sus vecinos, almacenando esta información en una tabla.
3. Cada nodo envía su tabla a todos los nodos vecinos.
4. Cuando un nodo recibe las tablas de distancias de sus vecinos, éste calcula la ruta más corta a los demás nodos y actualiza su tabla para reflejar los cambios.



Principales desventajas del algoritmo de Bellman-Ford:
  • Los cambios en la topología de red no se reflejan rápidamente ya que las actualizaciones se distribuyen nodo por nodo.
  • Cuenta hasta el infinito (si un fallo de enlace o nodo hace que un nodo sea inalcanzable desde un conjunto de otros nodos, éstos pueden estar siempre aumentando gradualmente sus cálculos de distancia a él, y mientras tanto puede haber bucles de enrutamiento)
ENRUTAMIENTO POR ESTADO DE ENLACE
Este algoritmo sustituyó al algoritmo de vector distancia ya que este último tenía dos debilidades, una es que no se consideraba el ancho de banda de las líneas y el dos que el algoritmo podía tardar demasiado en converger problema de la cuenta hasta el infinito). Algunos de los protocolos que actualmente usan el algoritmo de estado de enlace son el OSPF (Open Shortest Path First o El camino más corto primero), su medida de métrica se denomina cost y tiene en cuenta diversos parámetros tales como el ancho de banda y la congestión de los enlaces y el IS-IS (Intermediate System-Intermediate System o sistema intermedio-sistema intermedio) diseñado por DECnet y adoptado por la ISO.

Algoritmo
El concepto utilizado en el que se basa el enrutamiento por estado de enlace puede enunciarse en cinco partes:

1. Descubrir a sus vecinos y conocer sus direcciones
2. Medir el retardo o costo para cada uno de sus vecinos
3. Construir un paquete que indique lo aprendido
4. Enviar el paquete anterior a todos los demás enrutadores
5. Calcular la ruta más corta a todos los demás enrutadores.

Para identificar la ruta más corta el algoritmo de enrutamiento de estado de enlace se apoya del algoritmo de Dijkstra para encontrar la ruta más corta a los demás enrutadores. A diferencia del algoritmo de Bellman-Ford, el algoritmo de Dijkstra requiere que el peso de las aristas no sea negativo, gracias a esto puede resolver el problema en tiempo más reducido.

A diferencia del algoritmo de vector distancia en donde cada enrutador intercambia la información de su propia tabla con la de sus vecinos (nodo a nodo), en el algoritmo por estado de enlace la tabla de cada enrutador es enviado a todos los demás enrutadores en el mismo intercambio de tiempo asignado para la actualización de las tablas, esto evita que se presente el problema de la cuenta al infinito. También, debido a esta manera de proceder, el algoritmo de enlace de estado se comporta de manera mucha más eficiente ante posibles cambios en la topología de la red.

COMPARACIÓN ENTRE ALGORITMOS

  

Kill process in one console command line

example:   $ sleep 3600 & [ 1 ] 2225 $ sleep 3600 & [ 2 ] 2226 $ sleep 3600 & [ 3 ] 2227 $ sleep 3600 & ...