Algoritmos Estáticos
Enviado por knon • 23 de Febrero de 2012 • 763 Palabras (4 Páginas) • 1.627 Visitas
Algoritmos Estáticos
Enrutamiento por trayectoria más corta
Esta es una técnica de amplio uso en muchas formas, ya que es sencilla y fácil de entender. La idea es armar un grafo de la subred en el que cada nodo representa un
enrutador y cada arco del grafo una línea de comunicación (enlace). Para seleccionar
la ruta entre un par dado de enrutadores, el algoritmo simplemente encuentra en el
grafo la trayectoria más corta entre ellos.
El concepto de trayectoria más corta se debe a que la forma de medir la longitud
de la ruta es usando alguna métrica, entendiéndose por métrica al peso relativo que se
da a cada uno de los factores que intervienen en el cálculo de la distancia en una red,
los cuales podrían ser el número de saltos, la distancia física, el retraso de transmisión
por un paquete de prueba, el ancho de banda, el tráfico promedio, el costo de
comunicación, etc.
Se conocen varios algoritmos de cálculo de la trayectoria más corta entre dos
nodos de un grafo. Cada nodo se etiqueta (entre paréntesis) con su distancia al nodo
de origen a través de la mejor trayectoria conocida. Inicialmente no se conocen
trayectorias, por lo que todos los nodos tienen la etiqueta infinito. A medida que
avanza el algoritmo y se encuentran trayectorias, pueden cambiar las etiquetas,
reflejando mejores trayectorias. Una etiqueta puede ser tentativa o permanente.
Inicialmente todas las etiquetas son tentativas. Al descubrirse que una etiqueta
representa la trayectoria más corta posible del origen a ese nodo, se vuelve
permanente y no cambia más.
Inundación
Otro algoritmo estático es la inundación, en la que cada paquete de entrada se envía
por cada una de las líneas de salida, excepto aquella por la que llegó. La inundación
evidentemente genera grandes cantidades de paquetes duplicados, de hecho, una
cantidad infinita a menos que se tomen algunas medidas para limitar ese proceso. Una
de tales medidas puede ser un contador de escalas contenido en la cabecera de cada
paquete, el cual disminuye en cada escala, descartándose al llegar el contador a cero.
Idealmente el contador debe inicializarse a la longitud de la trayectoria; puede
inicializar el contador en el peor de los casos, es decir, el diámetro de la subred.
Una variación de la inundación, un poco más práctica es la inundación selectiva.
En este algoritmo, los enrutadores no envían cada paquete de entrada por todas las
líneas, sino sólo por aquellas que van aproximadamente en la dirección correcta.
La inundación no es práctica en la mayoría de las aplicaciones, pero tiene algunos
usos. Por ejemplo, en aplicaciones militares y en las aplicaciones
...