MIME-Version: 1.0 Content-Location: file:///C:/658BB227/routing.htm Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset="us-ascii" ROUTING

 

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) <= /span>

 

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 oacute;n, longitud promedi= o de la cola de espera, retardo medido, y algunos otros factores.=

 

 

 

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 una=3D   reexpedición, se hace una selección entre varias alternativas, para ese paquete en particular,=3D en forma independiente de = las selecciones que se hicieron para otros paquetes =3D 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 independien=3D te.

 

 

 

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.<= /p>

 

 

 

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 pun=3D to a punto, es dec= ir también  genera demasia= dos paquetes  y  consume demasiado an=3D cho de banda.

 

 

 

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. 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 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 =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> <= /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>