MIME-Version: 1.0 Content-Location: file:///C:/CF5C5D0F/Ruteo.htm Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset="us-ascii"
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.