MIME-Version: 1.0 Content-Location: file:///C:/CF5C5D0F/Ruteo.htm Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset="us-ascii" Algoritmos de Ruteo

= Algoritmos de Ruteo

&nbs= p;

Algoritmo= s de encaminamiento se pueden agrupar en dos clases principales:


1.- Algoritmos no adaptativos (elección = de la ruta utilizable para ir de la i a la j)
2.- Algoritmos adaptativos: existen tres famili= as distintas de algoritmos adaptativos:

a) Los algoritmos globales (para intentar tomar decisiones optimas)
b) Los algoritmos locales (algoritmos aislados)
c) Los algoritmos distribuidos


ENCAMINAMIENTO POR EL CAMINO MAS CORTO

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 solo determin= a el camino más corto que existe entre ellos.
Existe la posibilidad de utilizar muchos otros tipos de métrica por ejemplo, cada arco podría etiquetarse con el retardo promedio de la espera en cola y la transmisión, para un paquete patrón de prueba, determinado en base a pruebas de varias horas o días. Con es= te 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.
En el caso más general, las etiquetas de los arcos se podrían calcular como una función de la distancia, ancho de banda, promedio = de tráfico, costo de comunicación, longitud promedio de la cola = de espera, retardo medido, y algunos otros factores.


Algoritmo de Dijkstra (1959)

Cada uno de los nodos se etiqueta (entre paréntesis), con la distanc= ia que tiene desde el nodo origen a lo largo de un camino conocido como el mej= or. Inicialmente, ningún camino es conocido, así que todos los no= dos se etiquetan con infinito. A medida que el algoritmo avanza y los caminos se comienzan a conocer, las etiquetas pueden cambiar, reflejando mejores trayectorias. Una etiqueta puede ser tentativa o permanente. Al inicio todas son tentativas. Cuando se descubre que una etiqueta representa el camino más corto posible, desde el origen hasta el nodo respectivo, la etiq= ueta se hace permanente y desde ese momento jamás se modifica.


ENCAMINAMIENTO DE CAMINO MÚLTIPLE

La técnica de utilizar el encaminamiento múltiple entre un so= lo par de nodos se conoce como encaminamiento de camino múltiple, o alg= unas veces 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 p= aquete llega a un IMP para una reexpedición, se hace una selección e= ntre varias alternativas, para ese paquete en particular, en forma independiente= de las selecciones que se hicieron para otros paquetes que se dirigieron al mi= smo destino, en el pasado. Para subredes con circuitos virtuales, cada vez que = se establece un circuito virtual, se selecciona una ruta, pero el encaminamien= to para los diferentes circuitos virtuales (en beneficio de losa diferentes usuarios) se lleva a cabo en forma independiente.
El encaminamiento de camino múltiple se puede realizar de la siguien= te manera.
Cada IMP mantiene una tabla con una ristra reservada para cada uno de los posibles IMP destinatarios; cada ristra ofrece la 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, una IMP genera un número aleatorio y después selecci= ona entre las diferentes alternativas que se presentan, haciendo uso de los pes= os como probabilidades. Los operadores calculan las tablas manualmente, cargándolas en los IMP antes de que arranque la red y que no se modi= fique después.
Una de las ventajas del encaminamiento múltiple sobre el encaminamie= nto por camino más corto, es la posibilidad de poder transmitir diferent= es clases de tráfico sobre diferentes caminos. Por ejemplo, una conexión entre una terminal y un ordenador remoto, que consta de paquetes cortos que deben entregarse rápidamente, podría toma= rse una ruta a través de líneas terrestres, en tanto que la transferencia de un archivo grande, que necesita un gran ancho de banda, po= dría transmitirse a través de un enlace vía satélite. No sólo ofrece este método el gran ancho de banda que necesita la transferencia de archivos, si no que también evita que los paquetes cortos de terminales se tarden por esta detrás de una cola larga de paquetes de transferencia de archivos.