windowsxp

UNIVERSIDAD PRIVADA ANTENOR ORREGO FACULTAD DE INGENIERÍA ESCUELA PROFESIONAL DE INGENIERIA DE COMPUTACIÓN Y SISTEMAS REDES DE COMPUTADORAS 2012-I MONOGRAFIA “ALGORITMOS DE CONTROL DE GESTION” Contenido Resumen3 Marco Teórico4 1.CONTROL DE CONGESTIÓN4 1.1.Fenómeno: Congestión4 1.2.Causas de la congestión6 1.3.Agentes del control de la congestión7 1.4.Diferencia entre Control de Flujo y Control de Congestión8 1.5.Gestión de Trafico9 1.6.Control de congestión en redes de conmutación de paquetes10 1.7.Mecanismos de control de congestión.10 1.7.1.Mecanismo: Bucle Abierto10 1.7.2.Mecanismo: Bucle Cerrado12 1.8.Algoritmos de Control de Congestión.13 1.8.1.Algoritmo de Descarte de Paquetes.14 1.8.2.Algoritmo de paquetes reguladores.14 1.8.3.Mecanismo de Traffic Shaping16 Marco Conceptual17 2.Control de Congestión17 Bibliografía19 Resumen El masivo aumento que ha tenido en este último tiempo la conexión a Internet, ha desencadenado un rápido y agitado crecimiento de la cantidad de equipos conectados a una red. Cada ordenador que se suma a la red, demanda recursos y tráfico de datos dentro de un mismo sistema o fuera de este. Si sumamos y sumamos equipos, sin “replantear” el diseño de nuestra red de computadores, lo más probable es que estemos abriendo la puerta a una saturación de nuestro sistema de comunicación. Este fenómeno trae como consecuencia perdida de paquetes, retrasos y en el peor de los casos, una imposibilidad de intercomunicación. Ante una situación de este tipo es imprescindible el desarrollo de un sistema capaz de regular y contrarrestar este fenómeno. El control de congestión, establecido en protocolos de comunicación TCP y ATM, pretende regular el sobre-uso, o mal desempeño de una red. Así, mediante algoritmos y tiempos de espera establecidos, administra nuestra comunicación y envío de información de manera de obtener el mejor rendimiento de nuestra conexión. ¿De qué forma logra esto? ¿Qué ay detrás de esta regulación? ¿Es seguro? Analizaremos su funcionamiento y modo de reacción y operación en el desarrollo de este informe. Marco Teórico 1.CONTROL DE CONGESTIÓN Cuando hay demasiados paquetes presentes en la subred (o en una parte de ella), hay una degradación del desempeño. Esta situación se llama congestión. En la figura 5-25 se muestra este síntoma. Cuando la cantidad de paquetes descargados en la subred por los hosts está dentro de su capacidad de conducción, todos se entregan (excepto unos pocos afligidos por errores de transmisión) y la cantidad entregada es proporcional al número enviado. Sin embargo, a medida que aumenta el tráfico, los enrutadores ya no pueden manejarlo y comienzan a perder paquetes. Esto tiende a empeorar las cosas. Con mucho tráfico, el desempeño se desploma por completo y casi no hay entrega de paquetes. 1.1.Fenómeno: Congestión El caudal depende del tipo de red y tiene un valor nominal máximo, que no podremos superar en ningún caso. Pero además, la red no ofrece el mismo caudal real si se le ofrece poco tráfico o si se le ofrece mucho. Veamos la siguiente figura: Figura 1. Caudal en función del tráfico ofrecido La curva (1) representa el comportamiento ideal de la red: hay linealidad hasta llegar a la capacidad nominal de la red, momento en el que el tráfico cursado se satura. La curva (2) representa el comportamiento real típico de una red. Como puede observarse, al llegar a la zona de saturación, cuanto más tráfico se ofrece menos tráfico se cursa. Esto es debido, por ejemplo, a que los paquetes tardarán mucho tiempo en llegar a su destino, y mientras tanto serán retransmitidos por la fuente, pensando que se han perdido por el camino. Esto, a su vez, origina una explosión de tráfico, ya que cada paquete es retransmitido varias veces, hasta que consigue llegar a tiempo al destino. Para evitar esa degradación, se introduce el control de congestión que trata de aproximar el comportamiento de la red al dado por la curva (3), evitando así entrar en una zona de degradación. El retardo de tránsito en la red sigue la siguiente curva: Figura 2. Retardo de tránsito en función del tráfico ofrecido Vemos que el retardo no aumenta linealmente, sino que el aumento de éste es mayor que el aumento de tráfico ofrecido. 1.2.Causas de la congestión Existen varias causas de congestión. Enumeraremos aquí las más importantes: Memoria insuficiente de los conmutadores. Por ejemplo, veamos la siguiente figura: Figura 3. Saturación del buffer de un nodo En ella se tiene un conmutador en el que tres líneas de entrada mandan paquetes a una de salida. Así puede llenarse el buffer (cola) de la línea de salida. Además, si hay congestión en otros nodos, las colas no liberan la información de los paquetes transmitidos (que se guarda por si hay que retransmitir), con lo que la situación empeora aún más. Insuficiente CPU en los nodos. Puede que el nodo sea incapaz de procesar toda la información que le llega, con lo que hará que se saturen las colas. Velocidad insuficiente de las líneas. Se tiene el mismo problema que en el caso anterior. oTrabajar cerca de la capacidad de los enlaces es ideal desde el punto de vista de la productividad, pero no lo es respecto al retardo. Se experimentan grandes retardos en una cola según la tasa de llegadas de paquetes se acerca a la capacidad del enlace. oComo los búferes no son de tamaño infinito el emisor debe realizar retransmisiones para compensar los paquetes perdidos debido al desbordamiento de los búferes. oLas retransmisiones innecesarias realizadas por el emisor en presencia de grandes retardos, que provocan que venzan los temporizadores de retransmisión antes de que lleguen los asentimientos, hacen que el ancho de banda del enlace se utilice para reencaminar copias innecesarias de los paquetes. oCuando un paquete es desechado a lo largo de un camino, la capacidad de almacenamiento, procesamiento y transmisión que fue utilizada en cada uno de los nodos y enlaces anteriores, para encaminar ese paquete hasta el punto en el que es desechado, está siendo desperdiciada. 1.3.Agentes del control de la congestión Control de congestión entre extremos Con este enfoque la capa de red no proporciona ningún soporte explícito a la capa de transporte para controlar la congestión. La presencia de congestión en la red debe ser inferida por los sistemas finales, basándose en aspectos tales como las pérdidas y los retardos. Ej.: Control de congestión en TCP. Control de congestión asistido por la red Los componentes de la capa de red proporcionan una retroalimentación explícita al emisor sobre el estado de la congestión de la red. La realimentación se puede enviar al emisor directamente desde un conmutador congestionado o en peligro de congestión mediante paquetes especiales, o el conmutador puede indicar la presencia de congestión marcando los paquetes. Cuando un receptor recibe paquetes marcados lo notifica al emisor. Ej.: Control de congestión en el tráfico ABR de ATM. 1.4.Diferencia entre Control de Flujo y Control de Congestión Control de Flujo Es una técnica que permite sincronizar el envío de información entre dos entidades que producen/procesan la misma a distintas velocidades. Por ejemplo, supongamos el caso representado en la siguiente figura: Figura 4. Conexión entre nodo de alta capacidad y PC En este caso, dada la gran velocidad a la que produce y envía información, el nodo desborda al PC, por lo que éste debe enviar información de control (control de flujo) para que el nodo reduzca su tasa de envío de datos. De esta forma, parando a la fuente cada cierto tiempo, el PC puede procesar el tráfico que le envía el nodo. Control de Congestión Es un concepto más amplio que el control de flujo. Comprende todo un conjunto de técnicas para detectar y corregir los problemas que surgen cuando no todo el tráfico ofrecido a una red puede ser cursado, con los requerimientos de retardo, u otros, necesarios desde el punto de vista de la calidad del servicio. Por tanto, es un concepto global, que involucra a toda la red, y no sólo a un remitente y un destinatario de información, como es el caso del control de flujo. Figura 5. Congestión en un nodo El control de flujo es una más de las técnicas para combatir la congestión. Se consigue con ella parar a aquellas fuentes que vierten a la red un tráfico excesivo. Sin embargo, como veremos, hay otros mecanismos. 1.5.Gestión de Trafico Está relacionado con el uso eficiente de una de red con alta carga. Como cuando un nodo se satura y debe rechazar paquetes se puede aplicar alguna regla sencilla tal como la consistente en el rechazo de los paquetes más recientemente recibidos. Así mismo, se pueden utilizar muchas consideraciones para mejorar la aplicación de las técnicas de control de congestión y de la política de rechazo. Idoneidad oCalidad de Servicio: Puede requerir tratamientos diferentes para las diversas conexiones. oReservas: Ejemplo: ATM Acuerdo de tráfico entre el usuario y la red. 1.6.Control de congestión en redes de conmutación de paquetes Envió de un paquete de control hacia todos o algunos nodos emisores: se necesita tráfico adicional mientras dure la congestión. 1.7.Mecanismos de control de congestión. El problema del control de congestión puede enfocarse matemáticamente desde el punto de vista de la teoría de control de procesos, y según esto pueden proponerse soluciones en bucle abierto y en bucle cerrado. 1.7.1.Mecanismo: Bucle Abierto También llamadas soluciones pasivas. Combaten la congestión de las redes mediante un adecuado diseño de las mismas. Existen múltiples variables con las que el diseñador puede jugar a la hora de diseñar la red. Estas variables influirán en el comportamiento de la red frente a la congestión. Las resumiremos en función del nivel del modelo OSI al que hacen referencia: NIVELVARIABLE DE DISEÑO ENLACE•Política de control de flujo: Parando a una fuente que vierte mucho tráfico podemos reducir el riesgo de congestión. R E D •Circuitos Virtuales frente a datagramas: Muchos algoritmos de control de congestión funcionan sólo en modo circuito virtual. •Política de colas y de servicio: Los router pueden diseñarse con una cola por línea de entrada, una cola por línea de salida, o ambos. Además, puede jugarse con el orden en que los paquetes son procesados, dan do más prioridad a los paquetes de control, que contienen información útil desde el punto de vista de la congestión. •Política de descarte de paquetes: De nuevo, la correcta elección de los paquetes que se descartan puede disminuir el riesgo de congestión. •Algoritmo de enrutamiento: Es bueno desde el punto de vista de la congestión el balanceo del tráfico entre todas las líneas de la red. •Tiempo de vida de los paquetes: La correcta elección de esta variable permite reducir el número de retransmisiones, mejorando así el comportamiento de la red desde el punto de vista de la congestión. TRANSPORTE•Análogo al nivel de enlace, pero entre sistemas finales. 1.7.2.Mecanismo: Bucle Cerrado También llamadas soluciones activas. Actúan cuando se detectan problemas. Tienen tres fases: 1.7.2.1.Monitorización de parámetros Se vigilan los siguientes parámetros: Ocupación de los enlaces y de los buffers (colas de espera en los nodos) Porcentaje de descartes Número de retransmisiones Retardos y "jitters". Jitter: oscilaciones de la separación temporal entre paquetes. En aplicaciones que requieren sincronización (videoconferencia, sincronizar audio con video), es muy importante que esas oscilaciones sean pequeñas. 1.7.2.2.Reacción: envío de información a los puntos necesarios. La comunicación se realiza gracias ha: Paquetes especiales. NO están sometidos a control de congestión y se saltan las colas de espera en los nodos. Los envía el nodo que, gracias a la monitorización, ha detectado la congestión. Bits de cabecera. En los paquetes enviados, indico en la cabecera que empieza a haber congestión. (Ejemplo Frame Relay). Información específica. Si se recibe una alerta de congestión (mediante bits de cabecera de paquetes que circulan por la red), se solicita más información. 1.7.2.3.Ajuste del Sistema Hay varias medidas: Reducir la velocidad de envío Control de acceso. No se permiten más conexiones. Tirar paquetes. Controlar ráfagas de paquetes que llegan. 1.8.Algoritmos de Control de Congestión. Veremos dos algoritmos en bucle cerrado llamados algoritmo de descarte de paquetes y algoritmo de paquetes reguladores y un algoritmo en bucle abierto llamado mecanismo de Traffic Shaping. 1.8.1.Algoritmo de Descarte de Paquetes. Es un algoritmo de control de congestión en bucle cerrado. Se basa en que los nodos descartan (tiran) paquetes cuando su ocupación es alta. Para esto los nodos han de conocer sus recursos (CPU y memoria). Hace una asignación dinámica de los buffers en base a las necesidades de cada línea. Sin embargo, cada línea necesita al menos una (o más) posiciones de memoria para gestionar información relevante, tal como asentimientos, que permite la liberación de posiciones de memoria ocupadas por paquetes que estaban esperando por si necesitaban retransmitirse. Si a la línea llegan datos (no asentiminentos u otra información relevante) y el buffer de salida de la línea correspondiente está lleno, se descarta el paquete. Hay varias formas de hacer la asignación de buffers: En base al uso. No es muy eficiente, porque cuando una línea se empieza a cargar acapara todos los recursos. Asignación fija. Tampoco es muy buena, ya que desaprovecha recursos. Asignación subóptima (de Irland). Llamando k al número de posiciones del buffer y s al número de líneas de salida, se tiene que el número de posiciones de memoria asociadas a cada línea es: 1.8.2.Algoritmo de paquetes reguladores. En terminología inglesa, al paquete regulador se le llama choke packet. Se hace en bucle cerrado. Asocia un peso u a cada línea que cambia con el tiempo según la ecuación:< P Dónde: •un: función de peso, que depende del instante actual a través de f y del anterior a través de un-1. •f: tiene un valor "0" si no transmitimos en el instante actual o "1" si transmitimos. •a: constante comprendida entre 0 y 1 y que da más importancia al instante actual o al instante anterior según su valor. Si n supera un cierto umbral, se pone la línea en estado de alerta y se considera que puede haber congestión. Si llegan paquetes a esa línea, se envía un aviso hacia atrás con un paquete regulador que indica esta situación. Además, en los paquetes que se envían hacia delante se pone un flag a "1" para indicar al resto de los nodos que no manden paquetes reguladores hacia atrás, ya que el nodo origen está avisado. Al llegar el paquete regulador al origen, se reduce el flujo (por ejemplo, a la mitad). Si pasa un determinado tiempo sin recibir notificaciones de congestión, se vuelve a subir el flujo que puede cursar el origen. Si por el contrario se supera un umbral mayor, se pasa directamente a hacer descarte de paquetes. Variaciones: •Pueden mandarse paquetes reguladores con información de estado (grave, muy grave, etc.) •En vez de monitorizar las líneas de salida pueden medirse otros parámetros, tales como el tamaño de las colas en los nodos. •Con el mecanismo descrito se tarda mucho en reaccionar. Entonces, puede hacerse regulación salto a salto, en la que se dice al nodo anterior que mande la información por otro sitio si es posible. 1.8.3.Mecanismo de Traffic Shaping Significa conformado de tráfico. Es un mecanismo en bucle abierto. Conforma el tráfico que una fuente puede inyectar a la red. Se usa en redes ATM (Asynchronous Transfer Mode; tecnología de red orientada a conexión; en estas redes, la velocidad de línea es de 155 Mbps y el usuario puede ver una velocidad de unos 10 Mbps. Puede conseguirse información sobre estas redes en [COME 95]). Si se tiene una ráfaga lista para transmitir, el sistema obliga a no transmitir todo seguido (conforma el tráfico). Requiere un acuerdo entre proveedor y cliente: el proveedor garantiza que se cursa el tráfico si se transmite a una tasa determinada y tira el tráfico si se supera. Esto lo realiza mediante una función policía, que es un nodo que tira los paquetes que superan la tasa contratada a la entrada de la red (no se tiran una vez que ya ha entrado). Esto puede realizarse mediante un algoritmo de Leaky Bucket, cuyo nombre se debe a que es como si tuviéramos un bidón que vamos llenando con un caudal determinado y por el que sale el líquido (Leaky: hace aguas) con otro caudal distinto; si llenamos muy deprisa el bidón acabará llenándose y vertiéndose por arriba, lo que asemeja una pérdida de paquetes en una red. Veamos un ejemplo con un sistema codificador de imágenes: Figura 7. Ejemplo de mecanismo de Leaky Bucket Este sistema codifica la señal de video y la envía a ráfagas. Para ser transmitida necesita ser conformada: se almacenan muestras en un buffer y después se transmiten a velocidad constante. Si se sobrepasa el caudal predeterminado, pueden tirarse paquetes en el regulador (por parte del usuario) o en la función policía (por parte del proveedor). Este sistema permite aplanar ráfagas, como puede verse en la siguiente figura, donde la situación de la izquierda representa un sistema con tráfico no conformado y la de la derecha la equivalente si se conforma y se contrata transmisión a 2Mbps (la fuente transmite ráfagas de 1 Mb a 25 Mbps): Figura 8. Ejemplo de aplanamiento de ráfagas con tráfico conformado Marco Conceptual 2.Control de Congestión Se sabe que cualquier red se ve afectada por el congestionamiento, incluso la Internet es afectada por este fenómeno. Y aunque la capa de red trata de manejar este problema, gran parte del trabajo recae sobre TCP, ya que la “solución” real al congestionamiento es la disminución de la tasa de datos. TCP trata de no enviar un paquete nuevo hasta terminar con uno anterior. Pasos para el manejo de congestión: Detección: Antes era difícil detectar un congestionamiento, ya que afectaba mucho el ruido y otros problemas ocasionados por el cableado. Ahora hay una gran probabilidad de que si hay un paquete perdido sea por congestión. Evitar la congestión: Cuando se establece una conexión se debe tener un tamaño de ventana apropiado. Así de esta manera el receptor puede dar la especificación del tamaño de su ventana por medio de buffers, aunque aún podrían ocurrir congestionamientos por problemas internos en la red. Realmente podemos decir que tenemos dos problemas principales: Capacidad de la red Capacidad del receptor. Para poder combatir el congestionamiento, hay que manejar estos dos problemas por separado. Para esto cada transmisor debe tener dos ventanas (la de receptor y de congestión); cada una de estas, refleja la cantidad de bytes que puede enviar el transmisor. Entonces la cantidad mayor de bytes que pueden enviarse será la cifra menor entre las dos ventanas. Así, si el receptor dice “envía 8Kb” pero el transmisor sabe que las ráfagas de más de 4Kb saturan la red, enviará solo 4Kb. Análogamente, si el receptor dice “envía 8Kb” y el transmisor sabe que las ráfagas de hasta 32Kb pueden llegar sin problemas, envía solo los 8Kb solicitados. Al establecerse una conexión, el transmisor asigna a la ventana de congestionamiento el tamaño de segmento máximo usado por la conexión; entonces envía un segmento máximo. Si se recibe el ACK de este segmento antes de terminar el temporizador, el transmisor agrega el equivalente en bytes de este segmento a la ventana de congestionamiento para hacerla de dos El control de congestión es un aspecto de diseño de consideración necesario en las redes de datos, como las de conmutación de paquetes, las de retransmisión de tramas y redes ATM, y en la interconexión de redes (internet). El control de la congestión, como el fenómeno de la propia congestión, es un problema complejo. Esto ocurre cuando el número de paquetes que se transmiten sobre una red comienza a aproximarse al límite de la capacidad de gestión de paquetes de la misma. Uno de los objetivos del control de congestión es mantener el número de paquetes en la red por debajo del nivel para el que decaen dramáticamente las prestaciones. Es por ello que para comprender los elementos involucrados en el control de la congestión se han fijado en base a teorías de colas. Una red de datos o un internet es, esencialmente, una red de colas de modo que en cada nodo (un conmutador en una red de datos, un dispositivo de encaminamiento en una internet) existe una cola de paquetes asociada a cada canal de salida. Esta investigación se centra en el control de gestión en redes de datos conmutadas, incluyendo redes de conmutación de paquetes, de retransmisión de tramas y ATM. Los principios que se examinan son igualmente aplicables a la interconexión de redes (Internet). Además también podremos analizar los diferentes mecanismos con los cuales puede emplearse dentro de la congestión y el control de congestión en TCP. Bibliografía Tanenbaum, A. (2003). Redes de Computadoras, 4a. ed. Madrid: Ed. Pearson Educación.  [COME 95] Comer, Douglas E., Internetworking with TCP/IP, 3a edición, Volumen 1: Principles, Potocols and Architectures, Prentice-Hall, 1995. Kurose, J. & Ross, K. (2003). Redes de Computadoras: un enfoque descendente basado en Internet, 2a. ed. Madrid: Ed. Pearson Educación. Stallings, W. (2004). Comunicaciones y Redes de Computadores, 7a. ed. Madrid: Ed. Prentice-Hall Iberia S.A.  [TANE 96] Tanenbaum, Andrew S., Computer Networks, Prentice-Hall, 1996. [BERT 92] Bertsekas, D. y Gallager, R., Data Networks, 2a edición, Prentice-Hall, 1992.