Site hosted by Angelfire.com: Build your free website today!
resumen de reposicion de examen
 
ALGORITMOS DE ENCAMINAMIENTO.
 
 
Los algoritmos de encaminamiento se agrupan en dos tipos principales: no adaptativos y adaptativos. Los algoritmos no adaptativos no basan sus decisiones 
de encaminamiento en mediciones o estimaciones de trafico o topología Actuales.
 
Los algoritmos adaptativos intentan cambiar sus decisiones de encaminamiento para reflejar los cambios de topología y de trafico actual. Existen tres familias
 distintas de algoritmos adaptativas, que se diferencian dé acuerdo con la información que utilizan. Los algoritmos globales utilizan información recogida en 
toda la subred, para intentar tomar decisiones óptimas.
 
ENCAMINAMIENTO POR EL CAMINO MÁS CORTO.
 
El camino mas corto es una forma de medir la longitud del camino. En el caso mas general, las etiquetas de los arcos se podrían calcular como una función 
distinta, ancho de Banda, promedio de trafico, costo de comunicación, longitud promedio de la cola de espera, retardo medido, y  algunos otros factores.
 
ENCAMINAMIENTO DE CAMINO MÚLTIPLE.
 
Existe un solo "mejor" camino entre cualquier par de nodos y que todo él trafico entre ellos deberá utilizar. Con frecuencia, se puede obtener un mejor 
rendimiento al dividir él trafico entre varios caminos, para reducir la carga en cada una de las líneas de comunicación. La técnica se conoce como 
Encaminamiento de camino múltiple, o algunas veces encaminamiento bifurcado. Se aplica tanto en subredes con data gramas, como en subredes con circuitos 
virtuales .
El encaminamiento de camino múltiple se realiza de la siguiente 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 este destino en particular. Una de las ventajas del
encaminamiento del camino múltiple es la posibilidad de poder transmitir diferentes clases de trafico sobre diferentes caminos.
 
ENCAMINAMIENTO CENTRALIZADO.
 
Si la topología es de característica estática y él trafico cambia muy rara vez. Sin embargo, si los IMP y las líneas se desactivan y después se restablecen, o 
bien, si el tráfico varia violentamente durante todo el día, se necesitará algún mecanismo para adaptar las tablas a las circunstancias que imperan en este momento. 
Se estudiaran las técnicas para la construcción de las tablas de encaminamiento en un lugar central. Cuando se utiliza un encaminamiento centralizado, en alguna 
parte de la red hay un RCC (Centro de control del encaminamiento). Periódicamente, cada IMP transmite la información de su estado al RCC. El  RCC recoge 
toda esta información, y después, con base en el conocimiento total de la red completa, calcula las rutas optimas de todo los IMP a cada uno de los IMP 
restantes, el encaminamiento centralizado también tiene algunos serios, si no es que fatales, inconvenientes. La vulnerabilidad del RCC Es un problema muy serio 
y para eso una solución es,  tener una segunda maquina disponible como respaldo. También se necesitará establecer un método de arbitraje para tener la 
seguridad de que el RCC  primario y el de respaldo no lleguen a entrar en conflicto para saber quien es el jefe.
 
Si el RCC calcula la ruta óptima para cada IMP, sin rutas alternas, la pérdida de tan solo una línea o IMP, llegará a desconectar algunos IMP, sin rutas Alternas, 
 la perdida de tan sólo una línea o IMP, llegara a desconectar algunos IMP del RCC, creando así terribles consecuencias para el sistema. 
 
ENCAMINAMIENTO AISLADO
 
En  los algoritmos de encaminamiento, únicamente basados en la información que los mismos hayan reunido. No intercambia información de rutas con otros IMP. 
Sin embargo tratan de adaptarse a los cambios de topología y trafico que se llegan a presentar.  Baran (1964), conocido como el algoritmo de la patata caliente. 
En el momento en que llega un paquete, el IMP trata de deshacerse de él tan rápido como le sea posible, al ponerlo en la cola de espera de salida más corta 
ósea llega un paquete, el IMP cuenta él numero de paquetes que se encuentran en la cola de espera de cada una de las líneas de salida. Entonces instala el nuevo 
paquete al final de la cola de salida más corta, sin tomar en cuenta el lugar al que se dirige esta línea. Una posibilidad consisten utilizar la mejor opción estática, 
a menos que la cola excediera un cierto valor de umbral. Otra posibilidad consiste en utilizar la cola de espera más corta, a menos que, su peso estático sea
demasiado pequeño. Una alternativa adicional consistiría en ordenarlas líneas en términos de sus pesos estáticos, y nuevamente, en términos de las longitudes de 
las colas de espera, tomando en consideración la línea para la cual resulte menor la suma de los dos ordenamientos.
 
También desarrollado por Baran, es el conocido como el de aprendizaje hacia atrás. Una manera de realizar el aprendizaje hacia atrás consiste en incluir las 
identidades del IMP origen en cada paquete, junto con un contador que se incrementa después de cada salto. Desgraciadamente solo se registran los cambios 
hacia lo que sea mejor, no hay mecanismo alguno que permita registrar este hecho. En consecuencia deberán olvidar en forma periódica cualquier cosa que hayan 
aprendido y comenzar todo de nuevo.
 
Rudin (1976) ha descrito un encaminamiento híbrido interesante, el cual se encuentra entre un encadenamiento  centralizado y uno aislado, el cual denomino 
encadenamiento Delta. En este algoritmo, cada  uno de los IMP mide el "costo" de cada línea y periódicamente transmite un paquete al RCC entregándole estos valores.
Utilizando la información enviada calcula las mejores trayectorias. Cuando él calculo del encaminamiento termina, el RCC envía a cada IMP una lista de todos los 
caminos equivalentes, para cada uno de tus posibles destinos; Se les permite seleccionar cualquiera de las trayectorias equivalentes. Puede decidir entre todas ellas la 
forma aleatoria, o bien, utilizar el valor actualmente medido del costo de la línea. Las simulaciones  Que realizó Rudin, han demostrado que el valor de Ç puede escogerse 
para dar un mejor rendimiento que el obtenido con un encaminamiento puramente centralizado o aislado. 
 
-Inundación.
 
La inundación es un caso extremo del encaminamiento aislado, en el cual cada paquete que llega se transmite en todas las líneas de salida, exceptuando aquélla por la 
que llega. Con la inundación se genera un número infinito, a menos que se tomen algunas medidas para amortiguar el proceso. Una de tales medidas consiste en tener un 
contador de saltos contenido en la cabecera de cada uno de los paquetes, el cual sé decremento con cada salto que se lleva a cabo, y el paquete se desecha en el momento 
en que el contador alcance el valor de cero. En varias aplicaciones, la inundación no resulta ser muy practica, pero si tiene algunos usos importantes. En aplicaciones de bases 
de datos distribuidas, algunas veces se necesita actualizar todas las bases de datos en forma concurrente, en cuyo caso la inundación puede ser de gran utilidad. La inundación 
selectiva. En general, es ilógico enviar un paquete hacia el oeste, a través de líneas que van al este, a menos que la topología sea muy extraña. El algoritmo de Camino 
Aleatorio; aquí el IMP se encarga simplemente de seleccionar una línea aleatoriamente y reexpedir el paquete a través de ella. Si la subred tiene una cantidad considerable de 
interconexiones, este algoritmo tiene una cantidad considerable de interconexiones, este algoritmo tiene la propiedad de hacer un uso excelente de los encaminamientos 
alternativos. También es muy robusto. 
 
Encaminamiento distribuido.
 
Intercambia periódicamente información de encaminamiento explicito con cada uno de sus vecinos. Esta entrada consta de dos partes: la línea preferida de salida que se utilice 
para dicho destino, y alguna estimación del tiempo o distancia hacia él.
 
Encaminamiento Optimo.
 
Como una consecuencia directa del principio de optimización, se puede observa que, el conjunto de rutas optimas, procedentes de todos los orígenes a un destino dato, 
forman un árbol cuya raíz sale del destino. A este árbol se le llama árbol sumidero, este no contiene ningún lazo, de tal forma que cada paquete será entregado a través de un 
número limitado finito de saltos.
 
Encaminamiento basado en el flujo.
 
Para utilizar en forma adecuada, es necesario conocer anticipadamente cierto tipo de información. Primero, se deberá conocer la topología de la red. Segundo la matriz  de 
trafico deberá darse a conocer. Tercero, también deberán conocerse la matriz de capacidades en las líneas en Bits por segundo. Por ultimo se deberá seleccionar un algoritmo 
de encaminamiento. El retardo incluye tanto tiempo de espera como el tiempo de servicio. Para calcular el tiempo de retardo medio de la red completa, se toma la suma 
ponderada de cada uno de los ocho enlaces, en donde la ponderación es la fracción del  trafico total.
 
Encaminamiento jerárquico.
 
A medida que crece el tamaño de la red, tablas de encadenamiento de los IMP crecen también en forma proporcional. No solamente se produce un aumento de memoria 
consumida en el IMP al tener tablas más grandes, sino también es necesario tener un mayor tiempo de CPU para explorarlas y más ancho de banda para transmitir los informes 
del estado que guardan.
 
Cuando  se utiliza el encaminamiento jerárquico, los IMP se dividen en regiones, en las cuales cada uno de los IMP conoce todos los detalles sobre la manera de encaminar los 
paquetes para alcanzar sus respectivos destinos dentro de su propia región, pero desconocen la estructura interna de otras regiones. Para redes enormes, la jerarquía de dos 
niveles puede resultar insuficiente. Puede ser necesario agrupar las regiones en conglomerados, estos a su vez en zonas, las zonas en grupos, y así sucesivamente, hasta que
se nos acaben los nombres de las agrupaciones.
 
En la medida en que crece la relación del numero de regiones al numero de IMP dentro de una región. El ahorro de espacio en la tabla crece proporcionalmente. 
Desafortunadamente, la ganancia en espacio no es gratuita; Hay que pagar un precio, y este se presenta bajo la forma de un incremento en la longitud del camino.
 
También descubrieron que el aumento de la longitud promedio efectiva de la trayectoria, provocando por el encaminamiento jerarquizado, es lo suficiente pequeño como para 
resultar no objetable.
 
Encaminamiento por difusión.
 
Para algunas aplicaciones, los hostales necesitan transmitir mensajes a todos los demás hostales. En algunas redes los IMP pueden llegar a necesitar este tipo de servicio, por 
ejemplo, distribuir la actualización de las tablas de encaminamiento. A la transmisión de un paquete, en forma simultanea a todos los destinos, se les conoce como difusión, 
habiéndose ya propuesto varios métodos para desarrollarla. 
 
En un método de difusión en el que no es necesario que la subred tenga características especiales,  el extremo fuente solamente tiene que enviar un paquete distinto de información 
a cada destino. Esto no solo trae como resultado un desperdicio considerable del ancho de banda, sino también requiere que la fuente tenga una lista completa de todos los destinos.
 
Un algoritmo es el encaminamiento multidestino. Si este método se utiliza, cada paquete contiene una lista de destinos o 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 conjunto de líneas de salida que se necesitaran. (Una línea de salida será necesaria, si esta es
la mejor ruta, por lo menos, para uno de los destinos). El IMP genera una nueva copia del paquete para cada una de las líneas de salida que se utilizaran, e incluye en cada paquete sólo 
aquellos destinados que van a utilizar la línea. El conjunto de destinos, se subdivide entre las líneas de salida. Después de un número suficiente de saltos, cada paquete conducirá sólo un 
destino y podrá tratarse como un paquete normal. El encaminamiento multidestino es parecido a tener paquetes direccionados en forma independiente, excepto que, si varios paquetes 
deben seguir la misma ruta, uno de ellos pagará la cuota completa y el resto viajara gratuitamente. El tipo de Algoritmo de difusión hace uso explicito del árbol sumidero para el IMP que 
lleva a cabo  el inicio de la difusión, o bien, de otro árbol de expansión que sea conveniente para tal efecto.
 
Este método hace un excelente uso del ancho de banda, generando él numero mínimo absoluto de paquetes necesarios para realizar el trabajo.  El único problema es que cada  IMP 
deberá tener conocimiento de algún árbol de expansión al que se puede referir, y la mayoría de los algoritmos que se han estudiado no tiene ese tipo de conocimiento. 
 
Él ultimo algoritmo de difusión intenta igualar el comportamiento del algoritmo que se vio anteriormente, aun cuando los IMP no supieran nada acerca de los árboles de expansión.
 
Cuando un IMP llega un paquete de difusión, este comprueba si el paquete llegó por la línea que normalmente se utiliza para transmitir paquetes hacia la fuente de difusión. Sin embargo, 
si el paquete de difusión llegara por una línea diferente a la preferida para alcanzar  el origen, el paquete se desechará, como un probable duplicado. 
 
ALGORITMOS DE CONTROL DE LA GESTION.
 
En esta sección se estudiaran cinco estrategias para el control de la congestión. Estas estrategias toman en consideración la asignación de recursos en forma anticipada, que se desechen 
los paquetes cuando no se puedan  procesar, que se restrinja él numero de paquetes en la subred, utilizar el control de flujo para evitar la congestión y obstruir la entrada de datos cuando 
la subred esté sobrecargada.
 
Preasignación de tampones.
 
Si se utilizan circuitos virtuales  dentro de la subred, es posible resolver por completo el problema de la congestión de la manera siguiente. Cuando se establece 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 él 
trafico subsiguiente ya se ha determinado, así como se han hecho entradas en las tablas de encaminamiento de todos los IMP intermedios.
 
Normalmente, el paquete  de solicitud de llamada no reserva ningún espacio de memoria 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  solicitud de llamada reserve, también, uno o más tampones para datos. Si llega un paquete de solicitud de llamada 
a un IMP  y todos los tampones fueron reservados con anticipación, se deberá proceder a buscar otra ruta alternativa para el proceso, o bien, devolver una "señal de ocupado" al extremo 
que llama. Aun cuando los tampones se reserven algunos de los circuitos que aspiran a ser circuitos virtuales pueden ser reencaminados o rechazados por falta de espacio en la tabla, de tal 
forma que, reservar memorias no agrega ningún problema adicional a los ya existentes.
 
Al asignar permanentemente tampones a cada uno de los circuitos virtuales en cada IMP, siempre habrá un lugar para almacenar cualquier paquete que llegue hasta que pueda ser reexpedido.
 
Es imposible que se llegue a presentar congestión, por que todos los recursos necesarios para procesar él trafico ya se han reservado. Algunas subredes lo utilizan sólo en aquellos casos en 
donde es primordial tener un retardo muy pequeño y un gran ancho de banda.
 
Descarte de paquetes.
 
En lugar de reservar todos los tampones anticipadamente, no se reserva  absolutamente nada por adelantado. Si llega un paquete y no existe un lugar disponible para colocarlo, el IMP 
sencillamente lo descarta. 
 
Descartar paquetes ha voluntad puede llegar demasiado lejos; Resultaría bastante tonto. Este asentimiento le permitiría al IMP abandonar un paquete ya recibido y liberar así un tampón. Si el 
IMP  no  cuenta con tampones disponibles, no podría recibir ningún paquete para ver si contiene asentamientos, si la congestión tiene que ser evitada mediante el descarte del paquete será
necesario tener una regla para indicar cuando se deberá conservar o descartar un paquete. Irland (1978.) La idea de Irland consiste  en eliminar él numero de tampones que pueden vincularse 
a cualquier cola de salida estrategia permitirá que él trafico hacia otras líneas se reexpida inmediatamente con la posibilidad de duplicar o triplicar la tasa de salida del IMP de cualquier modo 
el paquete desechado se retransmitirá pronto si el sistema  se encuentra bien sintonizado, este incluso se retransmitirá antes de que la cola de espera se vacié, así que su rechazo inicial ni siquiera 
se notara.
 
Una idea relacionada con esto producida por Kamoun (1976), evita directamente que cualquier línea o líneas queden privadas de información: en el metodo de Irland se puedan combinar con 
el Kamoun distribuyendo un numero minimo y máximo detampones para cada linea.  Una forma de minimizar el ancho de banda que se desperdicia durante la retransmisión de paquetes 
descardas, consiste en descartar sistemáticamente aquellos paquetes  que no hayan viajado lejos y que,  por consiguiente no representen una fuerte inversión de recursos.
 
Control Isarritmico con la congestión.
 
La congestión tiene lugar cuando haya varios paquetes en la subred. Limitar él numero de paquetes  Davis (1972) propuso el método que utiliza precisamente, dicho limite el isarritmico debido a que mantiene constante él numero de paquetes existe premios que circulan dentro de la subred, siempre que un IMP desee transmitir un paquete recién entregado apenas por su Hostal, deberá de 
capturar un permiso, que circula dentro de la subred. Siempre que un IMP desee transmitir un paquete recién entregado apenas por su Hostal, primero deberá capturar un premio, y después destruirlo, cuando finalmente el IMP designa torio saca el paquete a las subred, regenera el permiso. Estas reglas sencillas aseguran él numero de paquetes de la subred nunca exceda él numero de permisos que inicialmente estén presentes.
 
IMP determinado queda súbitamente abrumado por paquetes los permisos deberán estar uniformemente definidos no es recomendable que el  transmisor tenga que andar buscando por todas partes suficientes permisos seria conveniente que estuvieran centralizados de tal forma que la petición de una cantidad considerable se pudiera cumplir con mayor rapidez. Si por alguna razón los permisos 
llegan a ser distribuidos, la capacidad de transporte de la red se reduce para siempre.
 
Control de flujo.
 
Algunas redes han intentado utilizar mecanismos de control de flujo para eliminar la congestión. En la realidad, el control de flujo no puede llegar ha resolver fácilmente los problemas de congestión, 
por él trafico de unas ráfagas.
 
Cuando varios usuarios soliciten el pico máximo al mismo tiempo cuando el control de flujo se utiliza como un intento para acabar con la congestión se puede aplicar al trafico entre paredes:
 
1.-Procesos de Usuarios.
2.-Hostales.
3.- IMP de origen y destino.
 
Además se puede restringir él numero de circuitos virtuales abiertos.
 
Paquetes reguladores.
 
Lo que en la realidad se necesita por consiguiente es : un mecanismo que se active cuando el sistema sé llege a congestionar. Hay una variable U, asociada  a cada una de las líneas, cuyo valor entre
cero y uno, refleja la utilización de esa línea. Si es el caso, el IMP transmite un paquete regulador, de vuelta al Hostal de origen, tomando el destino del paquete mismo. El paquete se etiqueta dé
tal forma que no pueda generar mas paquetes reguladores después, y se reexpida de manera  normal cuando el hostal de origen recibe al paquete regulador se le solicita que reduzca él trafico, enviado 
al destino especificado de acuerdo a un porcentaje X. Dado que otros  paquetes dirigidos al mismo destino, quizás se encuentren ya en camino, y podrían generar todavía más paquetes reguladores, 
el hostal deberá ignorar los paquetes reguladores que se refieren a este destino, durante un intervalo de tiempo fijo. Después de que haya experimentado ese intervalo de tiempo el Hostal estará a 
tiempo para escuchar la llegada de mas paquetes reguladores durante otro intervalo. Se han propuesto algunas variantes de este algoritmo  de control de la congestión, en una de ellas, el  IMP podría mantener dos niveles elípticos.
 
Otra variante consiste en utilizar las longitudes de las colas de espera, en lugar de la utilización de las líneas; Como medio de disparar la señal.
 
Bloqueos.
 
La congestión máxima es un bloqueo al que también se le conoce como estacionamiento. El primer IMP no puede proseguir hasta que el segundo IMP lleve a cabo una acción, y el segundo IMP 
tampoco puede continuar por que esta esperando que el primero haga algo. Los dos IMP se han bloqueados por completo y permanecerán así en ese estado. Los dos se encuentran bloqueados y 
ha esta función se le conoce como bloqueo de almacenamiento y reenvió directo. Schweitzer(1980)  en este esquema se construye un grafo dirigido, en el cual los tampones son los nodos del grafico, 
los arcos conectan a pares de tampones localizados en el mismo IMP o en  IMP adyacentes el grafo se construye dé tal manera que si todos los paquetes se mueven de un tampón a otro, alo largo 
de los arcos de grafo, entonces no podrían presentarse bloqueos.
 
Un paquete procede de un Hostal solo podrá ser admitido por la subred, si el tampón cero corresponde al IMP de origen, esta desocupado. Solo se podrá mover a un tampón etiquetado con él numero uno, en una IMP adyacente, así sucesivamente, hasta que alcance su destino y quede eliminado de la subred.
 
Por alcance un tampón queda etiquetado con la letra M, en cuyo caso se desechara uno de los tampones se encuentra en uno de los estados posibles; Vació reteniendo un paquete.
 
Merlín y Schweitzer también han presentado una cantidad  considerable demejoras ha estas sencillas estrategias con el objeto de reproducir él numero de tampones necesarios para bajar el rendimiento aunque este algoritmo evite los bloqueos por completo tiene la desventaja, que bajo circunstancias normales, muchas memorias se desperdician gracias a la falta de paquetes apropiados.
Además, las líneas estarán con frecuencia inactivas. Blazewicz y sus colaboradores (1987) a , han publicado un algoritmo completamente diferente, con el cual se evita el bloqueo y no tiene las
propiedades mencionadas. En su algoritmo cada paquete lleva consigo un sello de tiempo globalmente único. Este sello contiene la fecha en la cual se creo el paquete, localizada en los Bits de mayor 
orden y en él numero de maquina que se localiza en los Bits de menor orden. Aunque la sincronización de todos los relojes no es esencial, el algoritmo tiende ha dar un mejor servicio sin embargo, 
cuando los relojes no están demasiados de sincronizados.
 
El algoritmo necesita que  cada IMP un tampón por línea de entrada como una memoria de enreda especial todos los demás tampones se pueden utilizar para enviar los paquetes en trafico, los cuales 
se encolan, según el sello de tiempo en una cola separada para cada línea de salida. Siempre que una línea pase al estado inactivo, los dos IMP de sus dos extremos intercambian paquetes de control, entregado el sello de tiempo correspondiente al paquete más antiguo, que desee utilizar la línea.
 
Aquel que tenga el paquete más antiguo es el que gana y será el paquete que se transmita. A medida que avanza el tiempo, cada paquete llegara ha ser eventualmente, el de mayor antigüedad. Y será entregado.
 
Sin embargo, aun persiste el escabroso problema de cómo evitar que un IMP en mal 4estado provoque la caída de roda la red. Lai(1982) presenta un catalogo exhaustivo de otros  bloqueos de redes así como sus posibles soluciones de Blazewich y sus colaboradores (1987), GoPal(1985), discuten otros métodos de discusión de bloqueo.