Proceso autosemejante

Los procesos autosemejantes son tipos de procesos estocásticos que exhiben el fenómeno de autosemejanza . Un fenómeno autosemejante se comporta igual cuando se ve con diferentes grados de aumento o diferentes escalas en una dimensión (espacio o tiempo). Los procesos autosemejantes a veces se pueden describir utilizando distribuciones de cola pesada , también conocidas como distribuciones de cola larga . Ejemplos de tales procesos incluyen procesos de tráfico, como tiempos entre llegadas de paquetes y longitudes de ráfagas. Los procesos autosemejantes pueden exhibir una dependencia de largo alcance .

Descripción general

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 autosemejante 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]

En el tráfico tradicional de Poisson, las fluctuaciones a corto plazo se promediarían y un gráfico que abarcara una gran cantidad de tiempo se aproximaría a un valor constante.

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 colas pesadas para modelar fenómenos fractales del mundo real , por ejemplo, los mercados de valores, los terremotos, el clima y el tiempo. ^{[ cita necesaria ]} El tráfico de video Ethernet, WWW , SS7 , TCP , FTP , TELNET y VBR (video digitalizado del tipo que se transmite a través de redes ATM ) es autosimilar.

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. 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 presencia de autosimilitud. ^[3]

La distribución de Poisson

Antes de introducir matemáticamente la distribución de cola pesada, a continuación se analiza brevemente el proceso de Poisson con una distribución de tiempo de espera sin memoria , utilizado para modelar (entre muchas cosas) las redes telefónicas tradicionales.

Suponiendo llegadas y terminaciones puramente casuales se llega a lo siguiente:

• El número de llamadas entrantes en un tiempo determinado tiene una distribución de Poisson, es decir:

${\displaystyle P(a)=\left({\frac {\mu ^{a}}{a!}}\right)e^{-\mu },}$

donde a es el número de llegadas de llamadas en el tiempo T 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. ${\displaystyle \mu }$

• El número de salidas de llamadas en un tiempo determinado, también tiene una distribución de Poisson, es decir:

${\displaystyle P(d)=\left({\frac {\lambda ^{d}}{d!}}\right)e^{-\lambda },}$

donde d es el número de salidas de llamadas en el tiempo T y es el número medio de salidas de llamadas en el tiempo T. ${\displaystyle \lambda }$

• Los intervalos, T , entre llegadas y salidas de llamadas son intervalos entre eventos aleatorios independientes e idénticamente distribuidos. Se puede demostrar que estos intervalos tienen una distribución exponencial negativa, es decir:

${\displaystyle P[T\geq \ t]=e^{-t/h},\,}$

donde h es el tiempo medio de retención (MHT). ^{[ cita necesaria ]}

La distribución de cola pesada

Se dice que una distribución tiene una cola pesada si

${\displaystyle \lim _{x\to \infty }e^{\lambda x}\Pr[X>x]=\infty \quad {\mbox{for all }}\lambda >0.\,}$

Un ejemplo sencillo de distribución de colas pesadas es la distribución de Pareto .

Modelado de tráfico autosemejante

Dado que (a diferencia del tráfico telefónico tradicional) el tráfico paquetizado presenta características autosimilares o fractales, los modelos de tráfico convencionales no se aplican a redes que transportan tráfico autosimilar. ^{[ cita necesaria ]}

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 autosimilar para desarrollar, diseñar y dimensionar futuras redes multiservicio. ^{[ cita necesaria ]}

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]

Derivar modelos matemáticos que representen con precisión el tráfico dependiente de largo alcance es un área de investigación fértil.

Procesos estocásticos autosimilares modelados por distribuciones Tweedie

Leland et al han proporcionado un formalismo matemático para describir procesos estocásticos autosemejantes. ^[4] Para la secuencia de números

${\displaystyle Y=(Y_{i}:i=0,1,2,...,N)}$

con media

${\displaystyle {\hat {\mu }}={\text{E}}(Y_{i})}$,

desviaciones

${\displaystyle y_{i}=Y_{i}-{\hat {\mu }}}$,

diferencia

${\displaystyle {\hat {\sigma }}^{2}={\text{E}}(y_{i}^{2})}$,

y función de autocorrelación

${\displaystyle r(k)={\text{E}}(y_{i},y_{i+k})/{\text{E}}(y_{i}^{2})}$

con retraso k , si la autocorrelación de esta secuencia tiene el comportamiento de largo alcance

${\displaystyle r(k)\sim k^{-d}L(k)}$

como k →∞ y donde L(k) es una función que varía lentamente en valores grandes de k , esta secuencia se llama proceso autosemejante .

El método de expansión de contenedores se puede utilizar para analizar procesos autosemejantes. Considere un conjunto de contenedores no superpuestos de igual tamaño que divide la secuencia original de N elementos en grupos de m segmentos de igual tamaño ( N/m es un número entero) de modo que se puedan definir nuevas secuencias reproductivas, basadas en los valores medios:

${\displaystyle Y_{i}^{(m)}=(Y_{im-m+1}+...+Y_{im})/m}$.

La variación determinada a partir de esta secuencia aumentará a medida que cambie el tamaño del contenedor, de modo que

${\displaystyle {\text{var}}[Y^{(m)}]={\hat {\sigma }}^{2}m^{-d}}$

si y sólo si la autocorrelación tiene la forma limitante ^[5]

${\displaystyle \lim _{k\to \infty }r(k)/k^{-d}=(2-d)(1-d)/2}$.

También se puede construir un conjunto de secuencias aditivas correspondientes.

${\displaystyle Z_{i}^{(m)}=mY_{i}^{(m)}}$,

basado en los contenedores en expansión,

${\displaystyle Z_{i}^{(m)}=(Y_{im-m+1}+...+Y_{im})}$.

Siempre que la función de autocorrelación muestre el mismo comportamiento, las secuencias aditivas obedecerán la relación

${\displaystyle {\text{var}}[Z_{i}^{(m)}]=m^{2}{\text{var}}[Y^{(m)}]=({\hat {\sigma }}^{2}/{\hat {\mu }}^{2-d}){\text{E}}[Z_{i}^{(m)}]^{2-d}}$

Dado que y son constantes, esta relación constituye una ley de potencia de varianza a media ( ley de Taylor ), con p = 2- d . ^[6] ${\displaystyle {\hat {\mu }}}$ ${\displaystyle {\hat {\sigma }}^{2}}$

Las distribuciones Tweedie son un caso especial de modelos de dispersión exponencial , una clase de modelos utilizados para describir distribuciones de error para el modelo lineal generalizado . ^[7]

Estas distribuciones Tweedie se caracterizan por una invariancia de escala inherente y, por lo tanto, para cualquier variable aleatoria Y que obedezca a una distribución Tweedie, la varianza var( Y ) se relaciona con la media E( Y ) según la ley de potencia,

${\displaystyle {\text{var}}\,(Y)=a[{\text{E}}\,(Y)]^{p},}$

donde a y p son constantes positivas. El exponente p de la varianza de la ley de potencia media asociada con ciertos procesos estocásticos autosemejantes oscila entre 1 y 2 y, por lo tanto, puede modelarse en parte mediante una distribución de Poisson-gamma compuesta de Tweedie . ^[6]

La forma aditiva del modelo Poisson-gamma del compuesto Tweedie tiene la función generadora acumulativa (CGF),

${\displaystyle K_{p}^{*}(s;\theta ,\lambda )=\lambda \kappa _{p}(\theta )[(1+s/\theta )^{\alpha }-1]}$,

dónde

${\displaystyle \kappa _{p}(\theta )={\dfrac {\alpha -1}{\alpha }}\left({\dfrac {\theta }{\alpha -1}}\right)^{\alpha }}$,

es la función acumulativa , α es el exponente de Tweedie

${\displaystyle \alpha ={\dfrac {p-2}{p-1}}}$,

s es la variable de la función generadora, θ es el parámetro canónico y λ es el parámetro de índice.

La primera y segunda derivada del CGF, con s=0 , produce la media y la varianza, respectivamente. Por tanto, se puede confirmar que para los modelos aditivos la varianza se relaciona con la media según la ley de potencia,

${\displaystyle \mathrm {var} (Z)\propto \mathrm {E} (Z)^{p}}$.

Mientras que este compuesto de Tweedie Poisson-gamma CGF representará la función de densidad de probabilidad para ciertos procesos estocásticos autosemejantes, no devuelve información sobre las correlaciones de largo alcance inherentes a la secuencia Y.

No obstante, las distribuciones de Tweedie proporcionan un medio para comprender los posibles orígenes de procesos estocásticos autosemejantes debido a su papel como focos de un efecto de convergencia de tipo límite central conocido como teorema de convergencia de Tweedie . En términos no técnicos, este teorema nos dice que cualquier modelo de dispersión exponencial que manifieste asintóticamente una ley de potencia de varianza a media debe tener una función de varianza que entre en el dominio de atracción de un modelo de Tweedie.

El teorema de convergencia de Tweedie se puede utilizar para explicar el origen de la varianza en la ley de potencia media , el ruido 1/f y la multifractalidad , características asociadas con procesos autosemejantes. ^[6]

Rendimiento de la red

El rendimiento de la red se degrada gradualmente a medida que aumenta la autosimilitud. Cuanto más similar sea el tráfico, mayor será el tamaño de la cola. La distribución de la longitud de las colas del tráfico autosimilar 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. Además, agregar flujos de tráfico autosimilar normalmente intensifica la autosemejanza ("ráfaga") en lugar de suavizarla, lo que agrava el problema. ^{[ cita necesaria ]}

El tráfico autosemejante exhibe la persistencia de la agrupación , lo que tiene un impacto negativo en el rendimiento de la red.

• Con el tráfico de Poisson (que se encuentra en las redes de telefonía convencional ), la agrupación se produce en el corto plazo pero se suaviza en el largo plazo.
• Con tráfico autosemejante, el comportamiento de ráfagas puede ser en sí mismo ráfagas, lo que exacerba el fenómeno de agrupamiento y degrada 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

• Pérdida de celda/paquetes y desbordamiento de cola
• Violación de límites de retardo, por ejemplo, en vídeo
• Peores casos en multiplexación estadística

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. ^[8]

Ver también

• Tráfico de cola larga

Referencias

1. Parque, Kihong; Willinger, Walter (2000), Evaluación del rendimiento y tráfico de redes similares , Nueva York, NY, EE. UU.: John Wiley & Sons, Inc., ISBN 0471319740.
2. "Apéndice: Distribuciones de cola pesada". Cs.bu.edu. 2001-04-12 . Consultado el 25 de junio de 2012 .
3. "El sitio web de autosimilitud y dependencia de largo alcance en las redes". Cs.bu.edu . Consultado el 25 de junio de 2012 .
4. Leland, NOSOTROS; Leland, NOSOTROS; MS Taqqu; W. Willinger; DV Wilson (1994). "Sobre la naturaleza autosemejante del tráfico Ethernet". Trans. IEEE/ACM. Red . 2 : 1–15. doi : 10.1109/90.282603. S2CID  6011907.
5. Tsybakov B & Georganas ND (1997) Sobre el tráfico autosimilar en colas de cajeros automáticos: definiciones, límite de probabilidad de desbordamiento y distribución del retardo de celda. Trans. IEEE/ACM. Neto. 5, 397–409
6. Kendal, Wayne S.; Jørgensen, doblado (27 de diciembre de 2011). "Convergencia Tweedie: una base matemática para la ley de potencia de Taylor, el ruido 1/f y la multifractalidad". Revisión física E. 84 (6). Sociedad Estadounidense de Física (APS): 066120. Bibcode : 2011PhRvE..84f6120K. doi :10.1103/physreve.84.066120. ISSN  1539-3755. PMID  22304168.
7. Jørgensen, doblado (1997). La teoría de los modelos de dispersión . Chapman y Hall. ISBN 978-0412997112.
8. "Todo lo que siempre quiso saber sobre el tráfico de red similar y la dependencia de largo alcance, pero le daba vergüenza preguntar *". Cs.kent.ac.uk. ​Consultado el 25 de junio de 2012 .

enlaces externos

• Un sitio que ofrece numerosos enlaces a artículos escritos sobre el efecto del tráfico autosimilar en el rendimiento de la red.