Proceso auto-similar

Los procesos auto-similares son tipos de procesos estocásticos que exhiben el fenómeno de auto-similitud . Un fenómeno auto-similar se comporta igual cuando se ve con diferentes grados de aumento, o diferentes escalas en una dimensión (espacio o tiempo). Los procesos auto-similares a veces se pueden describir usando 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 auto-similares pueden exhibir una dependencia a largo plazo .

Resumen

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, la comprensión de las características del tráfico de Internet juega un papel cada vez más crítico. Los estudios empíricos de los rastros de tráfico medidos han llevado a un amplio reconocimiento de la auto-similitud en el tráfico de la red. ^[1]

El tráfico de Ethernet auto-similar exhibe dependencias en un amplio rango de escalas de tiempo. Esto debe contrastarse 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 cubriera una gran cantidad de tiempo se acercaría a un valor constante.

Se han observado distribuciones de colas pesadas en muchos fenómenos naturales, incluidos los 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, mercados de valores, terremotos, clima y el tiempo. ^{[ cita requerida ] 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 auto-similar.

La autosimilitud en las redes de datos empaquetados puede deberse a la distribución de tamaños de archivos, interacciones humanas y / o dinámicas de Ethernet. Las características autosimilares y dependientes de largo alcance en las redes de computadoras presentan un conjunto de problemas fundamentalmente diferente para las personas que realizan análisis y / o diseño de redes, y muchas de las suposiciones anteriores sobre las que se han construido los sistemas ya no son válidas en presencia de auto-semejanza. ^[3]

La distribución de Poisson

Antes de que se introduzca matemáticamente la distribución de cola pesada , a continuación se revisa brevemente el proceso de Poisson con una distribución de tiempo de espera sin memoria , que se utiliza para modelar (entre muchas cosas) las redes de telefonía tradicionales.

Asumir llegadas por pura casualidad y terminaciones por pura casualidad conduce a lo siguiente:

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

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

donde una es el número de las llamadas entrantes en el tiempo t , y es el número medio de llamadas entrantes en el tiempo t . Por esta razón, el tráfico de pura casualidad 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 tiempo T y es la media del número 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 distribuidos de forma idéntica. 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 mantenimiento (MHT). ^{[ cita requerida ]}

La distribución de la cola pesada

Artículo principal: 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 simple de una distribución de cola pesada es la distribución de Pareto .

Modelado de tráfico auto-similar

Dado que (a diferencia del tráfico de telefonía tradicional) el tráfico en paquetes exhibe características auto-similares o fractales, los modelos de tráfico convencionales no se aplican a las redes que transportan tráfico auto-similar. ^{[ cita requerida ]}

Con la convergencia de voz y datos, la futura red multiservicio se basará en tráfico empaquetado, y se requerirán modelos que reflejen con precisión la naturaleza del tráfico auto-similar para desarrollar, diseñar y dimensionar futuras redes multiservicio. ^{[ cita requerida ]}

El trabajo analítico anterior realizado en estudios de Internet adoptó suposiciones tales como entre llegadas de paquetes distribuidos exponencialmente, y las conclusiones a las que se llega bajo tales suposiciones pueden ser engañosas o incorrectas en presencia de distribuciones de colas pesadas. ^[2]

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

Procesos estocásticos auto-similares modelados por distribuciones Tweedie

Leland et al han proporcionado un formalismo matemático para describir procesos estocásticos auto-similares. ^[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)}$

cuando k → ∞ y donde L (k) es una función que varía lentamente con valores grandes de k , esta secuencia se denomina proceso auto-similar .

El método de expansión de contenedores se puede utilizar para analizar procesos auto-similares. 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) para que se puedan definir nuevas secuencias reproductivas, basadas en los valores medios:

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

La varianza determinada a partir de esta secuencia se escalará a medida que cambie el tamaño del contenedor de manera que

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

si y solo 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 de expansión,

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

Siempre que la función de autocorrelación exhiba 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 que se utilizan 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 obedece a una distribución Tweedie, la varianza var ( Y ) se relaciona con la media E ( Y ) por la ley de potencia,

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

donde un y p son constantes positivas. El exponente p para la varianza de la ley de potencia media asociada con ciertos procesos estocásticos auto-similares varía 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 de Poisson-gamma compuesto de Tweedie tiene la función de generación 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 Tweedie

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

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

La primera y segunda derivadas del CGF, con s = 0 , producen la media y la varianza, respectivamente. Por tanto, se puede confirmar que para los modelos aditivos la varianza se relaciona con la media por la ley de potencia,

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

Considerando que este compuesto Tweedie Poisson-gamma CGF representará la función de densidad de probabilidad para ciertos procesos estocásticos auto-similares, 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 auto-similares debido a su papel como focos para un efecto de convergencia de tipo límite central conocido como el teorema de convergencia de Tweedie . En términos no técnicos, este teorema nos dice que cualquier modelo de dispersión exponencial que manifiesta asintóticamente una ley de potencia de varianza a media debe tener una función de varianza que se encuentre dentro del dominio de atracción de un modelo Tweedie.

La convergencia Tweedie teorema puede ser utilizado para explicar el origen de la varianza de la ley de potencia media , 1 / f ruido y multifractality , características asociadas con los procesos de auto-similares. ^[6]

Rendimiento de la red

El rendimiento de la red se degrada gradualmente al aumentar la auto-similitud. Cuanto más auto-similar sea el tráfico, mayor será el tamaño de la cola. La distribución de la longitud de la cola del tráfico auto-similar decae más lentamente que con las fuentes de Poisson. Sin embargo, la dependencia a largo plazo no implica nada acerca de sus correlaciones a corto plazo que afectan el desempeño en pequeñas reservas. Además, la agregación de flujos de tráfico auto-similar típicamente intensifica la auto-similitud ("explosión") en lugar de suavizarla, agravando el problema. ^{[ cita requerida ]}

El tráfico auto-similar exhibe la persistencia de la agrupación en clústeres 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 convencionales ), la agrupación se produce a corto plazo, pero se suaviza a largo plazo.
• Con tráfico auto-similar, el comportamiento de ráfagas en sí mismo puede ser de ráfagas, lo que agrava los fenómenos 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 pueden causar fallas en la red, como

• Pérdida de celdas / paquetes y desbordamiento de cola
• Violación de los límites de demora, por ejemplo, en video
• Peores casos en multiplexación estadística

Los procesos de Poisson se comportan bien porque no tienen estado y la carga máxima no se mantiene, por lo que las colas no se llenan. Con el orden de largo alcance, los picos duran más y tienen un 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 de rendimiento y tráfico de red de autosimilares , 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. "La autosimilitud y la dependencia de largo alcance en el sitio Web de redes" . Cs.bu.edu . Consultado el 25 de junio de 2012 .
4. Leland, WE; Leland, WE; MS Taqqu; W. Willinger; DV Wilson (1994). "Sobre la naturaleza auto-similar del tráfico ethernet". IEEE / ACM Trans. Netw . 2 : 1-15. doi : 10.1109 / 90.282603 . S2CID 6011907 . 
5. Tsybakov B & Georganas ND (1997) Sobre tráfico auto-similar en colas ATM: definiciones, límite de probabilidad de desbordamiento y distribución de demora de celda. IEEE / ACM Trans. Netw. 5, 397–409
6. Kendal, Wayne S .; Jørgensen, Bent (27 de diciembre de 2011). "Convergencia Tweedie: una base matemática para la ley de potencia de Taylor, ruido 1 / f y multifractalidad" . Revisión E física . Sociedad Estadounidense de Física (APS). 84 (6): 066120. doi : 10.1103 / physreve.84.066120 . ISSN 1539-3755 . PMID 22304168 .  
7. Jørgensen, Bent (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 auto-similar y la dependencia de largo alcance, pero se avergonzó de 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 auto-similar en el rendimiento de la red.