Algoritmo De Enrutamiento

Técnicas y Algoritmo de Enrutamiento

Materia: Fundamentos de Redes
Catedrático: L.I. José Francisco Alderete
Alumno: Irán Isaac Gándara Nájera
Matricula: 227266
Carrera: LSCA
Fecha: 05 de Octubre de 2011

ALGORITMOS DE ENCAMINAMIENTO
Los algoritmos de encaminamiento se pueden agrupar en dos clases principales:
No adaptativos y adaptativos.
Los algoritmos no adaptativos no basan susdecisiones de encaminamiento en mediciones o estimaciones del tráfico o topología actuales, más bien, la elección de la ruta utilizable para ir de la i a la j (para toda i y j), se determina anticipadamente, fuera de línea y se carga en los IMP cuando la red se arranca. A este procedimiento se le denomina a veces encaminamiento estático.
Los algoritmos adaptativos, por otra parte, intentancambiar sus decisiones de encaminamiento para reflejar los cambios de topología y de tráfico actual.
A continuación se estudiarán con mayor detalle estas tres clases de algoritmos.
Encaminamiento por el camino más cortó
Comencemos nuestro estudio de los algoritmos de encaminamiento por medio de una técnica que se utiliza ampliamente de maneras diferentes, gracias a su simplicidad y facilidad decomprensión. La idea consiste en construir un grafo de la subred, con cada nodo representando una IMP y cada arco, una línea de comunicación. Para escoger una ruta entre un par de IMP dadas, el algoritmo sólo determina el camino más corto que existe entre ellos.
El concepto de encaminamiento más corto merece una explicación. Una forma de medir la longitud del camino es a través de número de saltos.Empleando esta métrica, los caminos ABC y ABE, en la figura 5-10, tienen la misma longitud. Otra métrica es el camino geográfico expresado en kilómetros, en cuyo caso la trayectoria ABC es claramente mucho más larga que ABE (suponiendo que la figura se ha dibujado a escala).
Sin embargo, existe la posibilidad de utilizar muchos otros tipos de métrica.
Por ejemplo, cada arco podría etiquetarse conel retardo promedio de la espera en la cola y de la transmisión, para un paquete patrón de prueba, determinado en base pruebas de varias horas o días. Con este etiquetado del grafo el camino más corto resulta ser el más rápido en lugar del que representa el menor número de arcos o kilómetros.
Encaminamiento múltiple
Hasta ahora se ha supuesto tácitamente que existe un solo “mejor” camino entrecualquier par de nodos y que todo el tráfico entre ellos deberá utilizarlos. En muchas redes hay varios caminos entre pares de nodos, que son casi igualmente buenos. Con frecuencia, se debe obtener un mejor rendimiento al dividir el tráfico entre varios caminos, para reducir la carga en cada una de las líneas de comunicación. La técnica de utilizar encaminamiento múltiple entre un solo par de nodosse conoce como encaminamiento de camino múltiple, o algunas veces como encaminamiento bifurcado.
El encaminamiento de camino múltiple se aplica tanto en subredes con datagramas, como en subredes con circuitos virtuales. Para el caso de subredes con datagramas, cuando un paquete llega a un IMP para su reexpedición, se hace una selección entre varias alternativas, para ese paquete en particular,en forma independiente de las selecciones que se hicieron par a otros paquetes que se dirigieron al mismo destino en el pasado. Para subredes con circuitos virtuales, cada vez que se establece un circuito virtual se selecciona una ruta, pero el encaminamiento para los diferentes circuitos virtuales (en beneficio de los diferentes usuarios) se lleva a cabo en forma independiente.
El encaminamientode camino múltiple se puede realizar de la siguiente manera.
Cada IMP mantiene una tabla con una ristra reservada para cada uno de los posibles IMP destinatarios; cada ristra ofrece la primera mejor, la segunda mejor, la tercera mejor, etc. línea de salida para ese destino en particular junto con un paso o ponderación relativa. Antes de que se reexpida un paquete, un IMP genera un número...