Una distribución de cola larga o de cola pesada es aquella que asigna probabilidades relativamente altas a regiones alejadas de la media o mediana. A continuación se proporciona una definición matemática más formal. En el contexto de la ingeniería de teletráfico, se ha demostrado que varias cantidades de interés tienen una distribución de cola larga . Por ejemplo, si consideramos los tamaños de los archivos transferidos desde un servidor web, entonces, con un buen grado de precisión, la distribución es de cola pesada, es decir, hay una gran cantidad de archivos pequeños transferidos pero, fundamentalmente, la cantidad de archivos muy grandes transferidos sigue siendo un componente importante del volumen descargado.
Muchos procesos son técnicamente dependientes de largo plazo pero no autosimilares . Las diferencias entre estos dos fenómenos son sutiles. La de cola pesada se refiere a una distribución de probabilidad y la dependiente de largo plazo se refiere a una propiedad de una serie temporal, por lo que se deben utilizar con cuidado y se debe hacer una distinción. Los términos son distintos, aunque las superposiciones de muestras de distribuciones de colas pesadas se agregan para formar series temporales dependientes de largo alcance.
Además, existe un movimiento browniano que es autosemejante pero no dependiente de largo alcance.
El diseño de redes y servicios de red robustos y confiables se ha convertido en una tarea cada vez más desafiante en el mundo actual de Internet . Para lograr este objetivo, comprender las características del tráfico de Internet juega un papel cada vez más crítico. Los estudios empíricos de las trazas de tráfico medidas han llevado al amplio reconocimiento de la autosimilitud en el tráfico de la red. [1]
El tráfico Ethernet autosimilar muestra dependencias en un largo rango de escalas de tiempo. Esto contrasta con el tráfico telefónico, que es Poisson en su proceso de llegada y salida. [2]
Con muchas series de tiempo, si se promedia la serie, los datos comienzan a verse más fluidos. Sin embargo, con datos autosimilares, uno se enfrenta a rastros puntiagudos y explosivos, incluso a gran escala. Este comportamiento se debe a una fuerte dependencia de los datos: los valores grandes tienden a aparecer en grupos, y grupos de grupos, etc. Esto puede tener consecuencias de gran alcance para el rendimiento de la red . [3]
Se han observado distribuciones de colas pesadas en muchos fenómenos naturales, incluidos fenómenos físicos y sociológicos. Mandelbrot estableció el uso de distribuciones de cola pesada para modelar fenómenos fractales del mundo real , por ejemplo, los mercados de valores, los terremotos y el clima. [2] El tráfico de vídeo Ethernet, WWW , SS7 , TCP , FTP , TELNET y VBR (vídeo digitalizado del tipo que se transmite a través de redes ATM ) es autosimilar. [4]
La autosimilitud en las redes de datos paquetizados puede deberse a la distribución de tamaños de archivos, interacciones humanas y/o dinámicas de Ethernet. [5] Las características autosemejantes y dependientes de largo alcance en las redes informáticas presentan un conjunto de problemas fundamentalmente diferentes para las personas que realizan análisis y/o diseño de redes, y muchas de las suposiciones previas sobre las cuales se construyeron los sistemas ya no son válidas en la presencia de autosemejanza. [6]
Los procesos dependientes de largo y corto alcance se caracterizan por sus funciones de autocovarianza .
En procesos dependientes de corto alcance, el acoplamiento entre valores en diferentes momentos disminuye rápidamente a medida que aumenta la diferencia de tiempo.
En procesos de largo plazo, las correlaciones en escalas de tiempo más largas son más significativas.
donde ρ( k ) es la función de autocorrelación en un retraso k , α es un parámetro en el intervalo (0,1) y ~ significa asintóticamente proporcional a medida que k se acerca al infinito.
Se puede demostrar que dicha escala de ley de potencia de la función de autocorrelación está bicondicionalmente relacionada con una relación de ley de potencia entre la varianza y la media, cuando se evalúa a partir de secuencias mediante el método de expansión de contenedores . Esta variación de la ley de potencia media es una característica inherente de una familia de distribuciones estadísticas llamadas modelos de dispersión exponencial de Tweedie . Así como el teorema del límite central explica cómo ciertos tipos de datos aleatorios convergen hacia la forma de una distribución normal , existe un teorema relacionado, el teorema de convergencia de Tweedie , que explica cómo otros tipos de datos aleatorios convergerán hacia la forma de estas distribuciones de Tweedie, y en consecuencia, expresan tanto la varianza como la ley de potencia media y la caída de una ley de potencia en sus funciones de autocorrelación.
Antes de introducir matemáticamente la distribución de cola pesada, a continuación se analiza brevemente la distribución de Poisson sin memoria, utilizada para modelar redes telefónicas tradicionales. Para más detalles, consulte el artículo sobre la distribución de Poisson .
Suponiendo llegadas y terminaciones puramente casuales se llega a lo siguiente:
donde a es el número de llegadas de llamadas y es el número medio de llegadas de llamadas en el tiempo T. Por esta razón, el tráfico puramente azaroso también se conoce como tráfico de Poisson.
donde d es el número de salidas de llamadas y es el número medio de salidas de llamadas en el tiempo T.
donde h es el tiempo medio de retención (MHT). [4]
Puede encontrar información sobre los fundamentos de la estadística y la teoría de la probabilidad en la sección de enlaces externos.
Las distribuciones de cola pesada tienen propiedades que son cualitativamente diferentes de las distribuciones comúnmente utilizadas (sin memoria), como la distribución exponencial .
El parámetro de Hurst H es una medida del nivel de autosimilitud de una serie temporal que exhibe dependencia de largo alcance, a la que se puede aplicar la distribución de cola pesada. H toma valores de 0,5 a 1. Un valor de 0,5 indica que los datos no están correlacionados o solo tienen correlaciones de corto alcance. Cuanto más cerca esté H de 1, mayor será el grado de persistencia o dependencia de largo plazo. [4]
Valores típicos del parámetro de Hurst, H :
Se dice que una distribución es de cola pesada si:
Esto significa que, independientemente de la distribución para valores pequeños de la variable aleatoria, si la forma asintótica de la distribución es hiperbólica, es de cola pesada. La distribución de cola pesada más simple es la distribución de Pareto , que es hiperbólica en todo su rango. A continuación se muestran funciones de distribución complementarias para las distribuciones exponencial y de Pareto. A la izquierda se muestra un gráfico de las distribuciones mostradas en ejes lineales, que abarcan un dominio grande. [8] A su derecha hay una gráfica de las funciones de distribución complementarias en un dominio más pequeño y con un rango logarítmico. [5]
Si se toma el logaritmo del rango de una distribución exponencial, la gráfica resultante es lineal. Por el contrario, la distribución de cola pesada sigue siendo curvilínea. Estas características se pueden ver claramente en el gráfico de arriba a la derecha. Una característica de las distribuciones de cola larga es que si se toma el logaritmo tanto del rango como del dominio, la cola de la distribución de cola larga es aproximadamente lineal en muchos órdenes de magnitud. [9] En el gráfico de arriba a la izquierda, la condición para la existencia de una distribución de cola pesada, como se presentó anteriormente, no se cumple con la curva denominada "Cola exponencial gamma".
La función de masa de probabilidad de una distribución de cola pesada viene dada por:
y su función de distribución acumulativa viene dada por:
donde k representa el valor más pequeño que puede tomar la variable aleatoria .
Los lectores interesados en un tratamiento matemático más riguroso del tema pueden consultar la sección de enlaces externos.
En general, existen tres teorías principales sobre las causas del tráfico de cola larga (consulte una revisión de las tres causas [10] ). En primer lugar, hay una causa basada en la capa de aplicación que teoriza que la duración de las sesiones de usuario varía con una distribución de cola larga debido a la distribución del tamaño de los archivos. Si la distribución de tamaños de archivos es muy estricta, entonces la superposición de muchas transferencias de archivos en un entorno de red cliente/servidor dependerá del largo plazo. Además, este mecanismo causal es sólido con respecto a los cambios en los recursos de la red ( ancho de banda y capacidad de búfer ) y la topología de la red . [11] Esta es actualmente la explicación más popular en la literatura de ingeniería y la que tiene la mayor evidencia empírica a través de distribuciones de tamaño de archivos observadas.
En segundo lugar, es una causa de la capa de transporte que teoriza que la retroalimentación entre múltiples flujos TCP debido al algoritmo para evitar la congestión de TCP en situaciones de pérdida de paquetes de moderada a alta provoca un tráfico autosimilar o al menos permite que se propague. Sin embargo, se cree que esto sólo es un factor significativo en plazos relativamente cortos y no la causa a largo plazo del tráfico autosemejante.
Finalmente, se presenta una causa teorizada de la capa de enlace que se basa en simulaciones físicas de redes de conmutación de paquetes en topologías simuladas. A una tasa crítica de creación de paquetes, el flujo en una red se congestiona y presenta ruido 1/f y características de tráfico de cola larga. Sin embargo, ha habido críticas a este tipo de modelos por ser poco realistas en el sentido de que el tráfico de red es de cola larga incluso en regiones no congestionadas [12] y en todos los niveles de tráfico.
La simulación mostró que podría surgir una dependencia de largo alcance en la dinámica de la longitud de la cola en un nodo determinado (una entidad que transfiere tráfico) dentro de una red de comunicaciones incluso cuando las fuentes de tráfico están libres de dependencia de largo alcance. Se cree que el mecanismo para esto se relaciona con la retroalimentación de los efectos de enrutamiento en la simulación. [13]
Es necesario modelar el tráfico de cola larga para que las redes puedan aprovisionarse basándose en suposiciones precisas del tráfico que transportan. El dimensionamiento y aprovisionamiento de redes que transportan tráfico de cola larga se analiza en la siguiente sección.
Dado que (a diferencia del tráfico telefónico tradicional) el tráfico paquetizado presenta características autosemejantes o fractales, los modelos de tráfico convencionales no se aplican a redes que transportan tráfico de cola larga. [4] Trabajos analíticos anteriores realizados en estudios de Internet adoptaron suposiciones tales como llegadas entre paquetes distribuidas exponencialmente, y las conclusiones alcanzadas bajo tales suposiciones pueden ser engañosas o incorrectas en presencia de distribuciones de cola pesada. [2]
Durante mucho tiempo se ha comprendido que la modelización eficiente y precisa de diversos fenómenos del mundo real debe incorporar el hecho de que las observaciones realizadas a diferentes escalas contienen información esencial. En términos más simples, representar datos a gran escala por su media suele ser útil (como un ingreso promedio o un número promedio de clientes por día), pero puede ser inapropiado (por ejemplo, en el contexto de almacenamiento en búfer o colas de espera). [3]
Con la convergencia de voz y datos, la futura red multiservicio se basará en tráfico paquetizado, y se necesitarán modelos que reflejen con precisión la naturaleza del tráfico de cola larga para desarrollar, diseñar y dimensionar futuras redes multiservicio. [4] Buscamos un equivalente al modelo de Erlang para redes de circuitos conmutados. [5]
No abundan los modelos de cola pesada con abundantes conjuntos de técnicas de ajuste de datos que los acompañan. [14] Aún no ha surgido un modelo claro para el tráfico fractal, ni hay una dirección definida hacia un modelo claro. [4] Derivar modelos matemáticos que representen con precisión el tráfico de cola larga es un área de investigación fértil.
Los modelos gaussianos , incluso los modelos gaussianos dependientes de largo alcance, no pueden modelar con precisión el tráfico de Internet actual. [15] Los modelos clásicos de series temporales como los de Poisson y los procesos finitos de Markov se basan en gran medida en el supuesto de independencia , o al menos de dependencia débil. [3] Sin embargo, los procesos relacionados con Poisson y Markov se han utilizado con cierto éxito. Se utilizan métodos no lineales para producir modelos de tráfico de paquetes que pueden replicar flujos dependientes tanto de corto como de largo alcance. [13]
Se han propuesto varios modelos para la tarea de modelar el tráfico de cola larga. Estos incluyen lo siguiente:
No existe unanimidad sobre cuál de los modelos en competencia es apropiado, [4] pero el proceso Poisson Pareto Burst (PPBP), que es un proceso M/G/, es quizás el modelo más exitoso hasta la fecha. Se ha demostrado que satisface los requisitos básicos de un modelo simple pero preciso de tráfico de cola larga. [15]
Finalmente, se presentan los resultados de simulaciones [4] utilizando procesos estocásticos estables para modelar el tráfico en redes de banda ancha. Las simulaciones se comparan con una variedad de datos empíricos (Ethernet, WWW, VBR Video).
En algunos casos, un aumento en el parámetro Hurst puede provocar una reducción en el rendimiento de la red. El grado en que la cola pesada degrada el rendimiento de la red está determinado por qué tan bien el control de la congestión es capaz de transformar el tráfico de origen en un flujo de salida constante en promedio mientras se conserva la información. [17] El control de la congestión del tráfico pesado se analiza en la siguiente sección.
La autosimilitud del tráfico afecta negativamente a las medidas principales de rendimiento, como el tamaño de la cola y la tasa de pérdida de paquetes. La distribución de la longitud de las colas del tráfico de cola larga decae más lentamente que con las fuentes de Poisson. Sin embargo, la dependencia de largo plazo no implica nada acerca de sus correlaciones de corto plazo que afectan el desempeño en colchones pequeños. [16] Para el tráfico de cola pesada, las ráfagas extremadamente grandes ocurren con más frecuencia que con el tráfico de cola ligera. [18] Además, agregar flujos de tráfico de cola larga normalmente intensifica la autosimilitud (" ráfaga ") en lugar de suavizarla, lo que agrava el problema. [1]
El gráfico de arriba a la derecha, tomado de [4] , presenta una comparación del rendimiento de las colas entre flujos de tráfico de distintos grados de autosimilitud. Observe cómo el tamaño de la cola aumenta al aumentar la autosimilitud de los datos, para cualquier utilización de canal determinada, degradando así el rendimiento de la red.
En el entorno de red moderno con multimedia y otros flujos de tráfico sensibles a la QoS que comprenden una fracción cada vez mayor del tráfico de la red, las medidas de rendimiento de segundo orden en forma de " jitter ", como la variación del retraso y la variación de la pérdida de paquetes , son importantes para el aprovisionamiento de la QoS especificada por el usuario. . Se espera que la ráfaga autosimilar ejerza una influencia negativa en las medidas de desempeño de segundo orden. [19]
Los servicios basados en conmutación de paquetes, como Internet (y otras redes que emplean IP ) son servicios de mejor esfuerzo, por lo que se puede tolerar un rendimiento degradado, aunque indeseable. Sin embargo, dado que la conexión está contratada, las redes de cajeros automáticos deben mantener los retrasos y las fluctuaciones dentro de los límites negociados. [20]
El tráfico autosemejante exhibe la persistencia de la agrupación, lo que tiene un impacto negativo en el rendimiento de la red.
Muchos aspectos de la calidad del servicio de la red dependen de hacer frente a los picos de tráfico que podrían causar fallas en la red, como
Los procesos de Poisson se comportan bien porque no tienen estado y los picos de carga no se mantienen, por lo que las colas no se llenan. En el orden de largo alcance, los picos duran más y tienen mayor impacto: el equilibrio cambia por un tiempo. [7]
Debido a las crecientes demandas que el tráfico de cola larga impone a los recursos de las redes, es necesario aprovisionarlas cuidadosamente para garantizar que se cumplan los acuerdos de calidad y nivel de servicio. La siguiente subsección trata del aprovisionamiento de recursos de red estándar, y la subsección siguiente analiza el aprovisionamiento de servidores web que transportan una cantidad significativa de tráfico de cola larga.
Para las colas de red con entradas dependientes de largo alcance, el fuerte aumento de los retrasos en las colas a niveles de utilización bastante bajos y la lenta disminución de la longitud de las colas implica que una mejora incremental en el rendimiento de las pérdidas requiere un aumento significativo en el tamaño del buffer. [21]
Si bien el rendimiento disminuye gradualmente a medida que aumenta la autosimilitud, el retraso en la cola aumenta de manera más drástica. Cuando el tráfico es autosimilar, encontramos que el retraso en la cola crece proporcionalmente a la capacidad del buffer presente en el sistema. En conjunto, estas dos observaciones tienen implicaciones potencialmente nefastas para las provisiones de QoS en las redes. Para lograr un nivel constante de rendimiento o pérdida de paquetes a medida que aumenta la autosimilitud, se necesita una capacidad de búfer extremadamente grande. Sin embargo, un mayor almacenamiento en búfer conduce a grandes retrasos en las colas y, por lo tanto, la autosimilitud aumenta significativamente la curva de compensación entre rendimiento/pérdida de paquetes y retraso. [17]
ATM se puede emplear en redes de telecomunicaciones para superar problemas de medidas de desempeño de segundo orden. La celda corta de longitud fija utilizada en ATM reduce el retraso y, más significativamente, la fluctuación de los servicios sensibles al retraso, como voz y vídeo. [22]
Las complejidades de los patrones de carga de trabajo (por ejemplo, patrones de llegada en ráfagas) pueden afectar significativamente las demandas de recursos, el rendimiento y la latencia encontrada por las solicitudes de los usuarios, en términos de tiempos de respuesta promedio más altos y una mayor variación del tiempo de respuesta . Sin una gestión y un control de los recursos óptimos y adaptables, los SLA basados en el tiempo de respuesta son imposibles. Los requisitos de capacidad en el sitio aumentan mientras que disminuye su capacidad para proporcionar niveles aceptables de rendimiento y disponibilidad . [18] Las técnicas para controlar y gestionar el tráfico de cola larga se analizan en la siguiente sección.
La capacidad de pronosticar con precisión los patrones de solicitudes es un requisito importante de la planificación de capacidad. Una consecuencia práctica de las ráfagas y de las llegadas correlacionadas y con colas pesadas es la dificultad en la planificación de la capacidad. [18]
Con respecto a los SLA, el mismo nivel de servicio para distribuciones de cola pesada requiere un conjunto de servidores más potente, en comparación con el caso del tráfico de solicitudes de cola ligera independiente. Para garantizar un buen rendimiento, es necesario prestar atención a la duración máxima del tráfico porque son las grandes ráfagas de solicitudes las que más degradan el rendimiento. Es por eso que algunos sitios ocupados requieren más espacio libre (capacidad adicional) para manejar los volúmenes; por ejemplo, un sitio de comercio en línea de gran volumen reserva capacidad excedente en una proporción de tres a uno. [18]
En la sección de enlaces externos se puede encontrar referencia a información adicional sobre el efecto de la dependencia de largo alcance en el rendimiento de la red.
Dada la ubicuidad de la ráfaga invariante de escala observada en diversos contextos de redes, encontrar un algoritmo de control de tráfico eficaz capaz de detectar y gestionar tráfico autosimilar se ha convertido en un problema importante. El problema de controlar el tráfico de red autosimilar está todavía en sus inicios. [23]
El control del tráfico para el tráfico autosimilar se ha explorado en dos frentes: en primer lugar, como una extensión del análisis de rendimiento en el contexto del aprovisionamiento de recursos, y en segundo lugar, desde la perspectiva del control del tráfico en múltiples escalas de tiempo, donde se explota activamente la estructura de correlación en grandes escalas de tiempo. para mejorar el rendimiento de la red. [24]
El enfoque de aprovisionamiento de recursos busca identificar la utilidad relativa de los dos tipos principales de recursos de red (ancho de banda y capacidad de buffer) con respecto a sus efectos restrictivos sobre la autosimilitud, y aboga por una política de dimensionamiento de recursos de buffer pequeño/ancho de banda grande. Mientras que el aprovisionamiento de recursos es de naturaleza de bucle abierto , el control del tráfico en múltiples escalas de tiempo explota la estructura de correlación de largo alcance presente en el tráfico autosemejante. [24] El control de la congestión se puede ejercer simultáneamente en múltiples escalas de tiempo y, al involucrar de manera cooperativa la información extraída en diferentes escalas de tiempo, se pueden lograr mejoras significativas en el rendimiento. [23]
Otro enfoque adoptado para controlar el tráfico de cola larga hace que los controles de tráfico sean conscientes de las propiedades de la carga de trabajo. Por ejemplo, cuando se invoca TCP en HTTP en el contexto de interacciones cliente/servidor web, el tamaño del archivo que se transporta (que se conoce en el servidor) se transmite o se hace accesible a los protocolos en la capa de transporte , incluida la selección de protocolos alternativos, para un transporte de datos más eficaz. Para archivos cortos, que constituyen la mayor parte de las solicitudes de conexión en distribuciones de archivos de gran tamaño de servidores web, se puede eludir el control de retroalimentación elaborado en favor de mecanismos livianos con un espíritu de control optimista, que puede resultar en una mejor utilización del ancho de banda. [19]
Se descubrió que la forma más sencilla de controlar el tráfico de paquetes es limitar la longitud de las colas. Invariablemente se producen largas colas en la red en los hosts (entidades que pueden transmitir y recibir paquetes). Por lo tanto, se puede lograr el control de la congestión reduciendo la tasa de producción de paquetes en hosts con largas colas. [13]
La dependencia de largo alcance y su explotación para el control del tráfico es más adecuada para flujos o conexiones cuya vida útil o duración de la conexión es duradera. [19]
![{\displaystyle P[T\geq \ t]=e^{\frac {-t}{h}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ba6809d7fc52695b97877beb09f8c7fa4450cca)
![{\displaystyle P[X>x]\sim x^{-\alpha },\ {\text{as}}\ x\to \infty ,0<\alpha <2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9488e2fcca7911974f04c33904648e02bc1438bc)
![{\displaystyle F(x)=P[X\leq \ x]=1-\left({\frac {k}{x}}\right)^{\alpha }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/604155e7dfd4540a47e2d200c7ceab08f699edd9)
{{cite journal}}: CS1 maint: multiple names: authors list (link)