Self Similarity

  • Published on
    16-Oct-2015

  • View
    7

  • Download
    0

Embed Size (px)

Transcript

  • 1Auto-similaridad

    Ivn Bernal, Ph.D.bernal_carrillo@hotmail.com

    Quito Ecuador

    Copyright @2010, I. Bernal

    AgendaAgenda

    Ivn Bernal, Ph.D.Ivn Bernal, Ph.D.Revisin Junio 2010Revisin Junio 2010 22

  • 2BibliografaBibliografaBibliografaBibliografa Kihong Park, Walter Willinger, Self-Similar Network Traffic and

    Performance Evaluation, 2000 John Wiley & Sons, Inc.

    Marco Aurelio Alzate Monroy Introduccin al Trfico AutosimilarMarco Aurelio Alzate Monroy, Introduccin al Trfico Autosimilaren Redes de Comunicaciones, Revista INGENIERIA, Universidad Distrital, 2001, Vol. 6(2), pp. 6 - 17

    Carey Williamson, Network Traffic Self-Similarity, Department of Computer Science, University of Calgary (presentacin).

    Ivn Bernal, Ph.D.Ivn Bernal, Ph.D.Revisin Junio 2010Revisin Junio 2010

    p , y g y (p )

    33

    IntroduccinIntroduccinIntroduccinIntroduccin Originalmente se consideraban como secuencias de variables independientes:

    Los tiempos entre llegadas de las demandas de los usuarios.De igual manera las cantidades representativas de la demanda:

    Duracin de las llamadas Longitud de los paquetes Tamao de los archivos etc Tamao de los archivos, etc.

    Posteriormente se vio que la correlacin existente entre estas variables era tan importante que se desarrollaron nuevos modelos ms elaborados en los que la correlacin decaa exponencialmente con el tiempo.

    Recientemente se ha evidenciado que en las redes modernas de comunicaciones, la correlacin entre estas variables no decae tan rpidamente y puede persistir a travs de

    Ivn Bernal, Ph.D.Ivn Bernal, Ph.D.Revisin Junio 2010Revisin Junio 2010

    correlacin entre estas variables no decae tan rpidamente y puede persistir a travs de muchas escalas de tiempo. Este fenmeno, que afecta significativamente el desempeo de las redes de comunicaciones, se puede

    representar adecuadamente mediante modelos de trfico fractal o auto-similar.

    44

  • 3IntroduccinIntroduccinIntroduccinIntroduccin El trabajo seminal que condujo a considerar la auto-similaridad una nocin importante en el

    entendimiento del trfico de redes fue el de Leland, Taqqu, Willinger and Wilson [1992-1994].Estudio basado en mediciones que indic que trfico agregado de una LAN Ethernet es self-

    similar.

    Se recolectaron trazas de gran longitud de LANs Ethernet en Bellcore.g g Estampillas de tiempo de alta resolucin. Se analizaron las propiedades estadsticas de las series de tiempo obtenidas.

    Incluyendo el Modelamiento y anlisis del performance de redes.Se deben revisar los esquemas de asignacin de recursos, control de congestin y dimensionamiento

    de redes a la luz de este fenmeno observado en el trfico de las redes de comunicaciones

    Desafortunadamente, el fenmeno de la autosimilaridad puede conducir a estructuras complejas de correlacin en las que la variabilidad se extiende a muchas escalas de tiempo, invalidando las tcnicas

    Ivn Bernal, Ph.D.Ivn Bernal, Ph.D.Revisin Junio 2010Revisin Junio 2010

    de control diseadas para los modelos tradicionales de trfico.

    El paradigma que se ha mantenido por mucho tiempo en la comunidad de comunicaciones y performance de redes ha sido que el trfico de voz y, por extensin, el trfico de datos son descritos adecuadamente con ciertos modelos Markovianos (es decir de Poisson).

    55

    ModelamientoModelamiento de trficode trficoModelamientoModelamiento de trficode trfico Trfico: la medida de la demanda que los usuarios de una red de

    comunicaciones imponen sobre los recursos de la red

    Modelos matemticos del comportamiento de los usuarios:Se representan los patrones de llegada de las demandas que los usuarios:

    Las demandas se pueden medir en trminos de paquetes, celdas, llamadas, flujos, conexiones, bits, o cualquier otra unidad de informacin adecuada.

    Los patrones de llegada se representan mediante alguna secuencia de tiempo que los identifique:9 Los instantes de llegada, {Tn, n Z}, o 9 El nmero de llegadas hasta el instante t, {N(t), t R}, o 9 La secuencia de tiempo entre llegadas, {An, n Z}, etc.

    P t t i t i d l i f t

    Ivn Bernal, Ph.D.Ivn Bernal, Ph.D.Revisin Junio 2010Revisin Junio 2010

    Por supuesto, como estas secuencias son representaciones del mismo fenmeno, se encuentran ntimamente relacionadas entre s:

    66

  • 4ModelamientoModelamiento de trficode trficoModelamientoModelamiento de trficode trfico Modelos matemticos del comportamiento de los usuarios:La Figura 1(a) muestra un minuto de dos secuencias del tipo {N(t), t R}.

    Se trata de la llegada de paquetes de voz y datos en una red local con servicios integrados de voz y datos.y

    Ivn Bernal, Ph.D.Ivn Bernal, Ph.D.Revisin Junio 2010Revisin Junio 2010 77

    ModelamientoModelamiento de trficode trficoModelamientoModelamiento de trficode trfico Modelos matemticos del comportamiento de los usuarios:Las Figuras 1(b) y 1(c) muestran los primeros cuatro segundos de las

    correspondientes secuencias del tipo {Tn, n Z}.

    Ivn Bernal, Ph.D.Ivn Bernal, Ph.D.Revisin Junio 2010Revisin Junio 2010 88

  • 5ModelamientoModelamiento de trficode trficoModelamientoModelamiento de trficode trfico Modelos matemticos del comportamiento de los usuarios:

    Se observa claramente la impredectibilidad de las secuencias, lo que obliga a modelar las series de tiempo {Tn, n Z}, {N(t), t R} o {An, n Z}, como realizaciones de procesos estocsticos.

    Los correspondientes modelos estocsticos deben capturar las principales caractersticas estadsticas del trfico en cuanto a su impacto en el desempeo de las redes. As:

    9 L ll d d t d d t d l Fi 1( ) d d l i l d9 Las llegadas de paquetes de datos de la Figura 1(c) pueden modelarse como un simple proceso de Poisson con una intensidad adecuada.

    9 Las llegadas de paquetes de voz de la Figura 1(b) debern modelarse mediante un proceso que tenga en cuenta la correlacin entre las llegadas impuesta por los intervalos de actividad e inactividad del usuario.

    Este simple ejemplo ilustra, la necesidad de desarrollar distintos

    Ivn Bernal, Ph.D.Ivn Bernal, Ph.D.Revisin Junio 2010Revisin Junio 2010 99

    desarrollar distintos modelos de trfico para diferentes tipos de servicio.

    ModelamientoModelamiento de trficode trficoModelamientoModelamiento de trficode trfico Modelos matemticos del comportamiento de los usuarios:

    Desde los comienzos de la telefona hasta inicio de los 80s se consider que la llegada de llamadas a una central telefnica obedeca a un proceso de Poisson y que la duracin de las llamadas estaba exponencialmente distribuida, con total independencia entre llamadasindependencia entre llamadas.

    Estas suposiciones resultaron ampliamente validadas por las mediciones reales de trfico. Permitieron desarrollar mtodos de diseo para asegurar una calidad de servicio dada.

    9 Probabilidad de bloqueo. En un proceso de Poisson las llegadas se producen a intervalos exponencialmente distribuidos con

    total independencia entre ellos.

    Esta total independencia hace que la aplicacin de este modelo resulte muy fcil en

    Ivn Bernal, Ph.D.Ivn Bernal, Ph.D.Revisin Junio 2010Revisin Junio 2010

    Esta total independencia hace que la aplicacin de este modelo resulte muy fcil en anlisis de desempeo y diseo de redes de comunicaciones.

    El xito de este modelo en redes telefnicas motiv su aplicacin al trfico de datos durante los 70s, con igual xito a pesar de que las predicciones del modelo no resultaban tan exactas.

    9 La medida de la QoS era una sola para todos los usuarios: el retardo promedio9 Resultaba fcil desarrollar mtodos de diseo para asegurar una QoS dada.

    1010

  • 6ModelamientoModelamiento de trficode trficoModelamientoModelamiento de trficode trfico Modelos matemticos del comportamiento de los usuarios:Con el aumento de las capacidades de transmisin de los enlaces, adems de

    la voz y los datos surgieron nuevos tipos de servicio como imgenes y video, los cuales empezaron a integrarse en una misma red de comunicacioneslos cuales empezaron a integrarse en una misma red de comunicaciones. El modelo de Poisson para estos nuevos tipos de trfico resulta invlido, dado que no

    puede esperarse independencia entre los tiempos entre llegadas.

    A partir de los 80s se han venido desarrollando nuevos modelos de trfico que tienen en cuenta esta correlacin entre tiempos de llegada. El proceso de llegada de paquetes de voz de la Figura 1(b), por ejemplo, podra

    modelarse mediante un Proceso Determinstico Markovianamente Modulado (MMDP):

    Ivn Bernal, Ph.D.Ivn Bernal, Ph.D.Revisin Junio 2010Revisin Junio 2010

    ( )

    9El abonado transita de activo a inactivo de acuerdo con una cadena de Markov de dos estados:En el estado activo genera paquetes a una tasa constante.En el estado inactivo no genera paquetes.

    1111

    ModelamientoModelamiento de trficode trficoModelamientoModelamiento de trficode trfico Modelos matemticos del comportamiento de los usuarios:

    Proceso de Poisson Markovianamente Modulado (MMPP). La figura muestra el trfico sobre una red LAN con datos interactivos permanentes y sesiones espordicas de

    transferencia de archivos.

    Este trfico compuesto se podra modelar mediante una cadena de Markov de dos estados:9 En cada estado, la llegada forma un proceso de Poisson con distinta intensidad, por lo que se trata de un

    MMPP.

    9 Estos tipos de modelos capturan mucha de la correlacin entre llegadas que impacta el desempeo de la red y cuyo efecto no se observa con el modelo de Poisson.

    Ivn Bernal, Ph.D.Ivn Bernal, Ph.D.Revisin Junio 2010Revisin Junio 2010 1212

  • 7ModelamientoModelamiento de trficode trficoModelamientoModelamiento de trficode trfico Mod