MIME-Version: 1.0 Content-Location: file:///C:/658BB227/routing.htm Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset="us-ascii"
ROUTING
|AL=3D =
GORITMOS DE
ENCAMINAMIENTO
Algoritmos de encaminamiento se pue=
den
agrupar en dos cl=3D ases principales:
1.- Algoritmos no adaptativos
(elección de la ruta utilizable para ir de la i a la j)
2.- Algoritmos adaptativos:
existen tres familias distin=3D tas de algoritm=
os adaptativos:
a) Los algoritmos globales (para in=
tentar
tomar decision=3D es optimas)
b) Los algoritmos locales (algoritm=
os
aislados)
c) Los algoritmos distribuidos
ENCAMINAMIENTO POR EL CAMINO MAS CORTO=3D
La idea consiste en construir =3D u=
n grafo de
la subred, con cada nodo representando una IMP y cada arco, una líne=
a de
comunicación. Para escoger una ruta entre un par de =3D IMP dadas, el
algoritmo solo determina el camino más corto que existe en=3D tre ellos.
Existe la posibilidad de utili=3D zar muchos otros tipos de métrica por
ejemplo, cada arco podría
etiquetarse con el retardo promedi=3D o =
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=3D te etiquetado del grafo el camino más co=
rto
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,=3D l=
as
etiquetas de los arcos se podrían calcular como una función <=
span
class=3DSpellE>d=3D e la distancia, ancho de banda, promedio de
tráfico, costo de comunicaci&=3D
Algoritmo de D=
ijkstra
(1959)=3D
Cada uno de los nodos se etiqu=3D eta (entre
paréntesis), con la distancia que tiene desde el nodo origen =3D a lo
largo de un camino conocido como el mejor. Inicialmente, ningún cami=3D no es conocido, así que todos los nodo=
s se
etiquetan con infinito. A me=3D dida
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 =
=3D
que una etiqueta representa el camino más corto posible, desde el or=
igen
hasta el nodo respectivo, la etiqueta se hace permanente y desde ese momento
jamás se modifica.
ENCAMINAMIENTO DE CAMINO MÚL=
TIPLE
La técnica de utilizar =3D el
encaminamiento múltiple entre un solo par de nodos se conoce como
encaminamiento de camino múltiple, o algunas veces encaminamiento
bifurcado.
El encaminamiento de camino m&uacut=
e;ltiple
se aplica tanto en subredes con datagr=3D amas,=
como en
subredes con circuitos virtuales. Para el caso de subredes con datagramas, cuando un paquete llega a un IMP para
El encaminamiento de camino m&uacut=
e;ltiple
se puede realizar de la siguiente manera.=3D
Cada IMP mantiene una tabla con una ristra
reservada para cada uno de los posibles IMP destinatarios; cada ristra ofre=3D ce la mejor, la segunda mejor, la tercera mej=
or, etc.
línea de salida p=3D ara 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 a=
leato=3D
rio y después selecciona entre las difer=
entes
alternativas que se presen=3D tan, haciendo uso=
de los
pesos como probabilidades. Los operadores calculan las tablas manualmente,
cargándolas en los IMP antes de que arranque la =3D red y que no se
modifique después.
Una de las ventajas del encaminamie=
nto
múltiple sobre el encaminamiento por camino más corto, es la
posibilidad de poder transmitir diferentes clases de tráfico sobre
diferentes caminos. Por ejemplo, una conexión e=
=3D
ntre una terminal y un ordenador remoto, que co=
nsta
de paquetes cortos que deben entregarse rápidamente, podría
tomarse una ruta a travé=3D=
;s de líneas terrestres, en tanto que la
transferencia de un archivo grande, que necesita un gran ancho de banda,
podrí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 e=
vita
que los paquetes cortos de termina=3D les se ta=
rden por
esta detrás de una cola larga de paquetes de tr=
ansfere=3D
ncia de archivos.
2
3
4
Encaminamiento Jerárquico
A medida que crece el tamaño=
de la
red, las tabla=3D s de encaminamiento de los IM=
P crecen
también en forma proporcional. No s=3D <=
span
class=3DSpellE>olo se produce un aumento de memoria consumida en el IMP al tener tablas
más grandes, sino también es necesario t=3D <=
span
class=3DSpellE>ener un mayor tiempo de CPU para explorarlas y mas an=
cho de
banda para transmitir los informes del estado que guardan. En cierto moment=
o la
red puede crecer a tal grado que ya no sea factible que el IMP pueda tener =
un
puntero para cada uno de los demás IMP, de tal forma que el
encaminamiento tendr&aacut=3D e; que
realizarse jerárquicam=
ente,
como en el caso de la red telefónica.=3D
Cuando se utiliza el encaminamiento
jerárquico, l=3D os IMP se dividen en
REGIONES<=3D /b>. Cuando se interconectan diferentes redes&n=3D
bsp; se considera a cada una e ellas como una
región separada.
Para redes enormes puede ser necesa=
rio
agrupa las region=3D es en conglomerados, estos=
a su
vez en zonas, estas en grupos, y así sucesivamente, hasta que se nos
acaben los=3D nombres de agrupaciones.
Cuando se hace un encaminamiento
jerárquico, hay entradas disponibles para todos los IMP locales, pero
todas las demás regiones se han condensado en un solo IMP. En la med=
ida
que crece la relación del número de regiones al número=
de
IMP dentr=3D o de una región, el ahorro =
de
espacio en la tabla crece proporcionalmente=3D =
..
Encaminamiento p=3D
or Difusión
para algunas aplicaciones, los hos=3D =
tales
necesitan transmitir mensajes a todos los demás hostales. Un hostal
desea determinar quienes son los otros hostales que desean, y son capaces de, ejec=3D utar una cierta t=
area para
él ó pueden actual=3D izar
bases de datos distribuidas. En algunas redes los IMP pueden necesitar este
tipo de servicio.
A la transmisión de un paque=
te, en
forma simultánea a todos los de=3D stinos se le conoce como DIFUSION.
En un método de difusiones e=
l que no
es necesario=3D que la subred tenga
características especiales, el extremo fuente solo t=3D
iene que enviar un paquete distinto de
información a cada destino.
El método de inundación no es=
=3D
muy adecuado para la comunicación punto a punto, para el caso de la difusión podría considerase con mayor
seriedad, el problema de inundación como una técnica de
difusión es el mismo que se tiene con el algoritmo de encaminamiento de
Un tercer algoritmo es el ENCAMINMI=
ENTO
MULTIDESTINO<=3D /i>. Si este método se utiliza, cada paquete
contiene una lista de destin=3D os ó un =
mapa de
bits, mediante el cual se indican los destinos deseados. Cuando un paquete
llega a un IMP, este comprueba todos los destinos para determinar el conjun=
to
de líneas de salida qu=
e se
necesitaran.
El IMP genera una nueva copia del p=
aquete
para cada una =3D de las líneas de salía que se utilizara, e
incluye en cada paque=3D te sólo aquellos
destinos que va a ocupar la línea.
Después de un número
suficiente de saltos, cada paquete conducirá solo un destino y
podrá tratarse como =3D un paquete normal. El encaminamiento multidestino =3D es parecido a tener paquetes direccionados
en forma independiente excepto que=3D si=
varios
paquetes deben seguir la misma ruta, uno de ellos pagara la cuota completa =
y el
resto viajara gratis.
El cuarto tipo de algoritmo de
difusión hace uso explicito del árbol sumidero para el IMP que
lleva a cabo el inicio =3D de la difusión. Si cada uno de lo IMP
conociera que líneas p=
ertenecen
al árbol se expansión, podría copiar un paquete de dif=
usión
de entrada sobre todas líneas del árbol de expansión c=
on
excepción de aquella por la que llego, este m&a=
mp;e=3D
acute;todo hace un e=
xcelente
uso del ancho de banda.
Este último algoritmo de
difusión intenta igualar el comportamiento del anterior, aun cuando =
los
IMP no supieran nada acerca de los árboles de expansión. Cuan=
do a
un IMP llega un paquete de difusión, esta comprueba si el paquete ll=
ego
por la línea que normalmente se utiliza para transmitir paquetes hac=
ia
la fuente de la difusión. Si es así, hay grandes probabilidad=
es =3D
de que el mismo paquete de difusión haya seguido la mejor trayectori=
a d=3D esde el IMP y es por=
lo tanto
la primera copia que llega al
IMP. Siendo este el caso, él=
IMP
reexpide copias del paquete sobre t=3D odas las
líneas, exceptuando aquella por la cual llego. Sin embargo, si el
paquete de difusión llegara por una línea diferente a la
preferida para alcanzar el origen, el paquete se desechara, como un probable dup=
licado.
5
ALG=3D<=
/span> ORITMO DE CONTROL DE LA CONGESTION
Est=3D<=
/span> udiaremos estrategias para el con=
trol de
la congestión. Tomando en cuenta la asignación de recursos en
forma anticipada, que se desechen los paqu=3D <=
span
class=3DSpellE>etes cuando no se puedan procesar, que se restrinjan =
el
número de paquete=3D s en la subred, uti=
lizando
el control de flujo para evitar la congestión y obstruir la entrada =
de
datos cuando la subred este sobrecargada.=3D
PRE=3D<=
/span> ASIGNACIÓN DE TAMPONES
Si =3D se utilizan circuitos virtua=
les dentro
de la subred, es posible resolver por completo el problema de la
congestión, de la manera siguiente. Cuando se e=
stable=3D
ce un circuito virtual, el paquete de solicitud de llamada sigue su camino a
través de la subred, produciendo entradas en las tablas según
avanza. En el momento en que llega a su destino, la ruta que deberá
seguir todo el trafico subsiguiente ya se ha determinado, así como se
han hecho entradas en las tablas de encaminamiento de todos los IMP
intermedios.
Nor=3D<=
/span> malmente, el paquete de solicitud=
de
llamada no reserva ningún espacio de memo=3D ria en los IMP intermedios, sino solo ranuras en las
tablas. Sin embargo una sencilla modificación del algoritmo de
establecimiento podría hacer que cada uno de los paquetes de solicit=
ud
de llamada reserve, también, uno o más tampones para datos. Si
llaga un paquete de solicitud de llamada a un IMP y todos los tampones fuer=
on
reservados con anticipación, se procederá a buscar otra ruta
alternativa par=3D a el proceso, o bien, devolv=
er una
"señal de ocupado". Aun cuan=3D do los
tampones se reserven algunos de los circuitos que aspiran a ser circuit=3D os virtuales pueden ser reencaminados o re=
chazados
por falta de espacio el la tabla, reservar memorias no agrega ningún
problema adicional a los ya existentes.
Al =3D asignar permanentemente tamp=
ones a
cada uno de los circuitos virtuales en cada IMP, siempre habrá un lu=
gar
para almacenar cualquier paquete que llegue h=3D asta
que pueda ser reexpedido. Un tampón por circuito virtual por IMP es
suficiente para circuito simplex, y uno por cada
dirección es suficiente para circuitos duplex=
span>.
Cuando llega un paquete, el asentimiento no se devuelve al IMP transmisor, =
=3D
sino hasta que el paquete se haya reexpedido.
Si =3D el protocolo IMP-IMP permite
múltiples paquetes pendientes, cada IMP tendrá que dedicar una
ventana completa de tampones para cada circui=3D to virtual, para poder eliminar por completo la posib=
ilidad
de congestió=3D ;n.
Cua=3D<=
/span> ndo cada uno de los circuitos vir=
tuales
que pasan por el IMP tiene suficiente espaci=3D=
o de
tampones dedicados a él, la conmutación de paquetes llega a <=
span
class=3DSpellE>s=3D er muy parecida a la
conmutación de circuitos. En los dos casos, al =
fin=3D
al hay un uso de recursos de recursos potencialmente ineficiente, por que l=
os
recursos que no llegan a ser utilizados por la conexión a la que
están asignados, sin embargo, no están disponibles para nadie
más.
Deb=3D<=
/span> ido a que dedicar un conjunto completo de tampones a un circu=
ito
virtual inactivo=3D es extraordinariamente cost=
oso,
algunas subredes lo utilizan solo en aquellos casos en donde es primordial
tener un retardo muy pequeño y un gran ancho de banda. Si el
tampón permaneciera inactivo demasiado tiempo,=3D se llegaría
liberar, para ser adquirido de nuevo, cuando llegara el siguiente paquete,
así los paquetes tendrán que reexpedirse s=3D
in tener tampones dedicados a ese momento, sino hasta que la cadena de tamp=
ones
pueda establecerse de nuevo.
DES=3D<=
/span> CARTE DE PAQUETES
El =3D segundo mecanismo de control=
de la
congestión en lugar de reservar todos los tampones anticipadamente n=
o se
reserva nada absolutamente por adelantado. Si llega un paquete y no existe
lugar disponible para colocarlo, el IMP simplemente lo descarta, el problem=
a de
la congestión se resuelve simplemente al descartar los paquetes a
voluntad. Si la subred ofrece un se=3D rvicio de circuito virtual, en algún lugar se
deberá una copia del paquete para que pueda transmitirse despu&eacut=
e;s.
Una posibilidad consist=3D e en hacer que el IM=
P que
transmitió el paquete descartado espere un tiem=
=3D
po y retransmita el paquete hasta que sea recib=
ido.
Otra posibilidad es que el I=3D MP emisor renun=
cie,
después de realizar varios intentos. Resultar&a=
mp;iacut=3D
e;a bastante tonto i=
gnorar
la llegada de un paquete que contenga un asentimiento procedente de un IMP
vecino. Este asentimiento le permitirá al IMP abandonar un paquete ya
recibido y liberar así un tampón. Sin embargo, si el IMP no
cuenta con tampones disponibles no podrá recib=
=3D
ir ningún paquete para ver si contiene asentimientos. La soluci&oacu=
te;n
consiste en reservar permanentemente un tampón por línea de
entrada con objeto de permitir que se inspeccione todos los paquetes que
llegan. Para el IMP resulta bastante justificable examinar el paquete
recién llegado, el portador de buenas noticias puede ser recompensad=3D o y usar el tampón que desocupo=
como
nueva memoria de entrada.
La =3D congestión debe ser e=
vitada,
una sola línea de salida acaparar en un IMP todos =3D los tampones
disponibles, dado que asigna sencillamente bajo la regla del prime=3D ro que llega es =
el primero
en ser atendido.
Aun=3D<=
/span> cuando dos líneas de salida estén inactivas,
cualquier paquete de entrada destinado a alguna de ellas, deberá
descartarse debido a que=3D no hay tampones dis=
ponibles.
Esto es un desperdicio. Una idea consiste en limi=3D=
span> tar el número de tampones que puedan vinculars=
e a
cualquier cola de sali=3D da. Después de=
todo,
esa línea de salida ya esta operando a su máxima capacidad. El
hecho de tener 7 paquetes en una cola de espera=3D en
lugar de 4 no bombeara bits a una velocidad mayor, sino que más bien
permitirá que el trafico a otras lí=3D ;neas se reexpida
inmediatamente, con la posibilidad de duplicar o triplicar la t=3D asa de la salida del IMP. De cualquier modo, el =
paquete
desechado se retransmitirá antes de que la cola de espera se =3D
vacié, así que su rechazo inicial ni siquiera se notara.<=3D /p>
Aun=3D<=
/span> que descartar paquetes sea sencillo tiene algunas desventajas=
; unas
de las mas importantes es el ancho de banda que se necesita para los
duplicados, si es=3D te es muy corto, los dupli=
cados
podrían ser generados cuando no se necesiten, empeorando todav&iacut=
e;a
mas la congestión. Si por otra parte es muy largo, el retardo
sufrirá las consecuencias.=3D
CON=3D<=
/span> TROL ISARÍTMICO DE LA CONGESTIÓN
La congestión tiene lugar cu=
ando hay
demasiados paquetes en la subred. =3D Un planteamiento directo para control=
arlo
consistirá en limitar el numero de paquetes presentes en la subred.<=3D /span>
Un método llamado, isarítmico, debid=3D o a que
mantiene constante el numero de paquetes, existen permisos, que circulan de=
ntro
de la subred, siempre que un IMP desee transmitir un paquete recién
entregado apenas por su hostal, primero deberá =
captura=3D
r un permiso y después destruirlo. Cuando finalmente, el IMP
destinatario saca el paquete de la subred, regenera el permiso. Estas reglas
sencillas asegura que el numero de paquetes de la subred n=3D
unca exceda el número de permisos que
inicialmente están presentes=3D ..
Este método tiene algunos pr=
oblemas.
Pri=3D<=
/span> mero, aunque garantiza que la subred como un todo nunca llega=
ra a
congestionarse,=3D no garantiza que un IMP determinado súbitamente q=
ueda
abrumado por paquetes.
Seg=3D<=
/span> undo, como distribuir permisos es=
ta legos
de ser obvio=3D .. P=
ara evitar
que un nuevo paquete generado sufra de un gran retardo mientras el I=3D MP local trata de obtener un permiso, los primer=
os
deberán estar uniformemente distribuidos, de tal manera que cualquier
IMP tenga algunos. =3D Por otra parte, para permitir la transferencia de ar=
chivos
con un gran ancho de banda, no es deseable que el IMP transmisor tenga que
andar buscando por to=3D das partes suficientes
permisos. Seria mucho mas conveniente que todos
estuvieran centralizados, de tal forma que la petición de una cantid=
ad
considerable se pudiera cumplir con mayor rapidez.
Ter=3D<=
/span> cero si por alguna razón los permisos llegan a ser
destruidos la capacidad de transporte de la red se reducirá para
siempre. No hay ninguna manera sencilla de determinar cuantos permisos exis=
ten
todavía, mientras la=3D red este funcion=
ando.
CON=3D<=
/span> TROL DE FLUJO
Alg=3D<=
/span> unas redes han intentado utilizar mecanismos de control de fl=
ujo
para eliminar la congestión. Aunque la capa de transporte puede lleg=
ar a
utilizar esquemas de control de flujo para impedir que un hostal sature a o=
tro
y, además, los esquemas de control de flujo puedan utilizarse para <=
span
class=3DSpellE>evit=3D ar que un IMP sat=
ure a sus
vecinos, es extremadamente difícil controlar=3D=
la cantidad total de trafico en la red, si los hostales se ven forzados a <=
span
class=3DSpellE>dete=3D ner la transmisi&=
oacute;n
debido a las estrictas reglas de control de flujo, la =
su=3D
bred llegara a estar suficientemente cargada.
El =3D control de flujo no puede ll=
egar a
resolver fácilmente los problemas de congestión, el trafico d=
e un
ordenador es=3D a ráfagas.
Cua=3D<=
/span> ndo se desea explorar un archivo =
muy
grande. El pico de tráfico potencial es bast=3D=
ante mayor que el valor promedio. Cualquier esquema de control de flujo, qu=
e se
ajuste para restringir al usuario al valor medio, dará en definitiva=3D un mal servicio cuando este solicite un=
trafico
a ráfagas.
Si =3D el límite del control=
de flujo
se establece con un valor suficientemente alto, para permitir que el pico d=
el
trafico se l=3D ogre,
tendrá poco valor como control de congestión.
Cua=3D<=
/span> ndo el control de flujo se utiliz=
a como
intento para acabar con la congestió=3D ;n, se puede apl=
icar al
trafico entre pares de:=3D
procesos=
de usuario<=3D /o:p>
Hostales, sin tomar en cu=3D
enta el numero de circuitos virtuales abiertos<=
span
class=3DGramE>.<=3D o:p>
IMP de origen, sin consid=3D
erar a los hostales.
Ade=3D<= /span> más se puede restringir el número de circuitos = virtuales abiertos.<=3D /o:p>