Evaluación de Rendimiento de un Algoritmo para Recuperación de Errores en Comunicaciones Multipunto Marta Barría 1 Reinaldo Vallejos 2 Mónica Aguilar 3 Departamento de Computación, Universidad de Valparaíso, Valparaíso, Chile [email protected] 2 Departamento de Electrónica, UTFSM, Valparaíso, Chile [email protected] 3 Departamento de Telemática, UPC, Barcelona, España [email protected]

1

Abstract. In [3,4] the authors of this publication presented an algorithm for error recovery (packets lost) in a multipoint transmission. The aim of the present paper is to analyze the performance of this algorithm. The performance evaluation is valid for any tree topology that connects the participants of the multipoint structure. Performance measures are average value of latency, implosion, number of NACKs sent to recover a given packet and the number of retransmissions that were needed for errorless reception at all the end points.

1. Introducción Las comunicaciones multipunto ofrecen una manera eficiente de difundir información desde un (o varios) transmisor (es) a un grupo de receptores. A grandes rasgos, las aplicaciones multipunto pueden ser divididas en aplicaciones que necesitan que la transmisión de la información sea fiable y aplicaciones que no necesitan de esta fiabilidad. Aplicaciones tales como videoconferencia, audio en Internet, kioscos electrónicos, etc., no requieren que la transmisión sea fiable, ya que pueden aceptar un cierto nivel de pérdida de información sin que el usuario detecte un deterioro significativo en el servicio que recibe. Por otra parte, aplicaciones tales como distribución de software, pizarras compartidas, juegos interactivos, transmisión de cuentas bancarias, replicación de bases de datos, etc., sí necesitan que la transmisión de la información sea fiable, lo cual significa que todos los paquetes transmitidos deben ser recibidos sin errores por todos los receptores de la información [1]. Sin embargo, a causa de la naturaleza de “mejor esfuerzo” de Internet, ésta red no permite entregar un servicio que garantice la fiabilidad de la comunicación, por lo que es crucial desarrollar protocolos que permitan recuperar los paquetes con errores [7]. La solución más simple para generar mecanismos de comunicación multipunto confiable, sería adaptar los protocolos que se usan para este propósito en las comunicaciones punto a punto. Lamentablemente esta estrategia no resulta conveniente, ya que como resultado de esta adaptación se obtienen protocolos muy ineficientes [2], motivo por el cual surge la necesidad de diseñar protocolos en base a otras estrategias. Los mecanismos de recuperación de errores están constituidos básicamente por una fase de detección del error y otra de corrección del mismo. La fase de detección normalmente se lleva a cabo en los receptores, ya que este esquema es más eficiente que

el basado en la fuente [2]. Usualmente los receptores descubren la pérdida de un paquete cuando detectan un salto en la secuencia de la numeración de los paquetes que le están llegando desde una determinada fuente. Para recuperar un paquete, los receptores envían al transmisor (o fuente) un paquete especial llamado NACK, el cual indica a la fuente que debe retransmitir el paquete perdido. Aunque el mecanismo de recuperación de errores recién descrito no parece presentar dificultades, en la práctica si las hay, ya que si cada uno de los receptores afectados por la pérdida de un paquete enviara un NACK a la fuente, en ella se produciría la llegada sincronizada de (posiblemente muchos) NACKs. Este fenómeno se conoce con el nombre de “implosión de NACKs”. La implosión de NACKs es indeseable porque produce congestión en la fuente y alrededor de ella, lo que obviamente causa degradación en las medidas de rendimiento globales de la red, tales como el retardo y el throughput [2]. Otra medida que permite evaluar el rendimiento de un algoritmo de recuperación de errores en una comunicación multipunto, es la latencia. La latencia, corresponde al intervalo de tiempo que transcurre desde el instante en que un determinado paquete se pierde hasta que todos los receptores lo reciben correctamente. Similarmente al caso de la implosión, la latencia también es una medida importante, ya que afecta el rendimiento global de la red. Para resolver en forma óptima el problema de la implosión de NACKs sería necesario que el mecanismo de recuperación de la información consiga, en un tiempo mínimo, que solo uno de los receptores afectados envíe el NACK. Esta no es una tarea fácil cuando se quiere resolverla cumpliendo simultáneamente algunas otras restricciones, como por ejemplo que los nodos de la red no conozcan la topología de ella (lo que simplifica el mecanismo de recuperación de errores). Además, en cualquier mecanismo diseñado

Notación nodo miembro del grupo multipunto

Fuente

nodo que pertenece al árbol de distribución y no es miembro del grupo multipunto

1 3

2

6 4

5

10 9 8 7 11

12

13

15

14

16

Figura 1. Árbol de distribución D. para disminuir el problema de la implosión, el subgrupo de receptores afectados por la pérdida de información debe ponerse de acuerdo (de alguna manera) en quién (o quiénes) enviarán NACKS, lo que con gran probabilidad aumentará el retardo en la recuperación de la información (latencia). En otras palabras: la disminución de la implosión tiende a causar un aumento en la latencia, lo que es indeseable. La situación ideal consiste en que el tamaño de la implosión sea igual a 1 y la latencia sea mínima. Por este motivo, los mecanismos para recuperación de errores que han sido propuestos en la literatura buscan disminuir simultáneamente la implosión y la latencia, pues esto implica mejorar las medidas de rendimiento globales de la red. Sin embargo, como estos objetivos son conflictivos entre sí, los algoritmos intentan obtener un compromiso entre el tamaño de la implosión y el tiempo de latencia. En [3, 4] los autores de este trabajo propusieron un nuevo algoritmo para la recuperación de errores (o pérdida de paquetes) que ocurren en una transmisión multipunto. Este algoritmo tiene algunos atributos que lo hacen competitivo con respecto a los protocolos existentes. En particular, la recuperación del paquete con error se realiza en forma local, es decir, en la zona donde éste se produce; además posee un bajo tiempo de latencia y el tamaño de la implosión es cercano al ideal. Para justificar esta afirmación, en este trabajo se hace un análisis matemático del rendimiento del protocolo propuesto. Específicamente, en este trabajo se evalúan los valores medios de la latencia, la implosión, el número de NACKs enviados para la recuperación de un paquete y el número de retransmisiones efectuadas hasta que todos los miembros del grupo reciben en forma correcta un determinado paquete. Además, el análisis de rendimiento efectuado en este trabajo es válido para cualquier topología del árbol de recuperación, a diferencia del análisis efectuado en [3] donde se supuso que el árbol de recuperación estaba restringido a una topología tipo estrella.

El resto de este escrito está estructurado de la siguiente forma. En primer lugar, con el objeto de que el artículo sea autocontenido, en la sección 2 se describe el algoritmo; luego, en la sección 3 se evalúan las diferentes medidas de rendimiento. En la sección 4 se muestran algunos resultados numéricos, y finalmente, en la sección 5 se entregan las conclusiones del trabajo realizado.

2. Descripción del Algoritmo Para representar la red se utiliza un grafo G=(V, E), donde V={i, 1≤ i ≤ V} corresponde al conjunto de nodos de la red, V es el número total de nodos de la red; y E={ei,j ; ≤ i,j≤ V, i≠j} es el conjunto de arcos representan los enlaces de la red. En una comunicación multipunto el intercambio de información se realiza entre un usuario que transmite información y múltiples usuarios que la reciben. Los usuarios de la comunicación multipunto se denominan miembros del grupo. El miembro que origina la información se denomina fuente, f, y los demás miembros del grupo se denominan receptores. Sea R el conjunto de receptores, con R={r, 1≤ r ≤ R}, donde R es el número de todos los receptores del grupo multipunto. El rol de fuente puede ser asumido por diferentes miembros de la comunicación multipunto en diferentes intervalos de tiempo de la misma. Cada miembro del grupo se conecta a la red a través de algún nodo de ella. Con el objeto de simplificar el escrito, en adelante se usará la expresión “miembro del grupo” para referenciar tanto al usuario que participa de la comunicación multipunto como al nodo a través del cual dicho usuario se conecta a la red. Consecuentemente con la definición anterior, se define M = R U {f} como el conjunto de nodos que son miembros del grupo multipunto, por lo que M ⊆ V. Un determinado nodo i pertenece a M cuando existe al menos un participante de la comunicación multipunto que está conectado a la red a través del nodo i. Además se asume que existe un árbol de distribución de la

información, que es denotado por D, el cual interconecta a todos los nodos de M [1, 2]. Este árbol es generado por algún protocolo de encaminamiento multipunto [5, 6]. Lógicamente, D contiene a todos los miembros del grupo multipunto y, adicionalmente, puede contener a algunos nodos de la red que no son miembros de M, pero que son necesarios para su interconexión. Los nodos de D que no son miembros del grupo, necesariamente son nodos internos del árbol de distribución, tal como se muestra en la Fig. 1. Los paquetes que se originan en la fuente f son transmitidos a cada uno de los miembros de M a través de D. Cuando uno de estos paquetes llega a un nodo del árbol, este nodo envía una copia del paquete a cada uno de sus hijos dentro del árbol. De esta forma los paquetes transmitidos por f llegan a todos los miembros del grupo. Además, cada miembro de M mantiene una copia de los paquetes que ha recibido correctamente, que en caso de ser requerida, puede ser retransmitida a sus descendientes. Por su parte, aquellos nodos de D que no son miembros del grupo multipunto, sólo actúan como transmisores intermediarios de cualquier paquete que reciban. Los receptores son los responsables de mantener la fiabilidad de la comunicación. Esto significa que los receptores tienen la misión de detectar la pérdida de paquetes y solicitar la retransmisión de los paquetes perdidos. La solicitud de la retransmisión la realizan mediante el envío de un NACK hacia su padre en M. La pérdida de paquetes normalmente se detecta por los receptores al notar un salto en la secuencia de numeración de los paquetes que llegan a él desde la fuente. Para modelar la pérdida de paquetes, cada canal de la red tiene asociada una probabilidad de pérdida de paquetes de datos y una probabilidad de pérdida de NACKs. Estas probabilidades son diferentes, debido fundamentalmente a que el tamaño de los paquetes de NACKs es menor que el de los paquetes de datos. Tanto las probabilidades de pérdida de paquetes de datos como de NACKs son homogéneas en el tiempo, lo que significa que dos paquetes del mismo tipo que son transmitidos por un mismo canal en instantes diferentes tienen asociada la misma probabilidad de ser afectados por un error en el canal. Por otro lado, diferentes canales de la red pueden tener asociadas diferentes probabilidades de error. Cuando por algún motivo se produce la pérdida de un paquete, se activa el mecanismo de recuperación de errores. Antes de proceder a definir formalmente este mecanismo, a continuación se definen algunos conceptos auxiliares; luego, en base a estos conceptos se entrega una descripción intuitiva del algoritmo de recuperación de errores, y posteriormente se define formalmente el algoritmo. Árbol de recuperación. Sea Ti el sub-árbol de D cuya raíz es el nodo i ∈M ; todos sus nodos interiores no son miembros del grupo multipunto; y el conjunto de

sus hojas,

H i = {h | h ∈ Ti } corresponde a todos

los miembros del grupo multipunto que son descendientes del nodo i en el árbol D, que cumplen la condición de que en el camino entre el nodo i y alguna hoja h en D no existe ningún miembro del grupo multipunto. Por ejemplo, en el árbol de distribución de la Fig. 1, hay dos árboles de recuperación: el árbol de recuperación T3 , que tiene como raíz al nodo 3, el conjunto H3 de sus hojas son los miembros 10, 11, 12, 13, 15,16 (H3 ={10, 11, 12, 13, 15,16}), y sus nodos interiores (no miembros) son los nodos 6, 8, 9, y 1. El otro árbol de recuperación de D es el árbol T1 , cuya raíz es el nodo 1, H 1 = 4, 7, 3 y los nodos interiores (no pertenecientes al grupo multipunto) son los nodos 2 y 5. Una consecuencia de la definición de árbol de recuperación es que cualquier miembro del grupo multipunto que es un nodo interior de D, es simultáneamente raíz de un árbol de recuperación, y hoja de otro árbol de recuperación; por ejemplo, en la Fig. 1, el nodo 3 es hoja de T1 y raíz de T3 .

{

}

Una observación que se usará más adelante, en la definición del algoritmo de fiabilidad, es notar que la pérdida de un paquete ocurre en un único enlace y dicho enlace pertenece a un único árbol de recuperación. Por ejemplo, si en el árbol de la Fig. 1 se pierde un paquete en el canal e3,6 o en el canal e6,9 , el árbol de recuperación asociado a ambas pérdidas es el mismo, el árbol T3 ; en cambio, si el paquete se pierde en el canal e5,7 , el árbol de recuperación asociado a la pérdida es el árbol T1. Considere que la pérdida de un paquete ocurre en un determinado enlace e j,k ∈ D , donde el nodo j es el padre del nodo k en D. Bajo estas condiciones se define el árbol de error, Fk , al sub-árbol de D, cuya raíz es el nodo i (donde i es el ancestro perteneciente a M más cercano al nodo k) contiene el camino entre el nodo i y el nodo k, y contiene al sub-árbol de Ti cuya raíz es el nodo k. Cabe destacar que los primeros miembros del grupo multipunto que detectan la pérdida de un paquete son las hojas de Fk . Volviendo al ejemplo de la Fig. 1, si el error ocurre en el enlace e3,6 , los primeros miembros que se dan cuenta del error son todas las hojas de T3, en este caso

F6 = T3 . Por otro lado, si el error ocurre en

enlace e6,9 , de las hojas de T3 solamente los miembros 13, 15 y 16 son afectados por el error, en este caso el árbol de error está compuesto por los nodos 3, 6, 9, 13, 14, 15 y 16 y todos los arcos que interconectan a estos nodos. Nótese que en este caso F9 ≠ T3 . Cada hoja h que pertenece a un árbol de error

Fk tiene asociado un único árbol de espera Qh . La raíz de

Qh es el nodo (miembro) h; y además

Qh contiene a todos los descendientes de h ∈ D . Por ejemplo, suponga que en el árbol de la Fig. 1, el

nodo 9 también es miembro del grupo; bajo esta condición se tendrían asociados los siguientes árboles de espera: Q9, Q10 , Q11, y Q12. Las definiciones de árbol de recuperación, árbol de error y árbol de espera son útiles para explicar de manera intuitiva el funcionamiento del algoritmo; sin embargo, para la ejecución del algoritmo ningún nodo del árbol de distribución necesita conocer la existencia de estos árboles. A continuación se entrega una explicación intuitiva del algorit mo usando las definiciones anteriores. Cuando un determinado miembro detecta la pérdida de un paquete, envía un mensaje de inhibición por su árbol de espera. Los miembros del grupo que reciben el mensaje de inhibición quedan imposibilitados de solicitar la repetición del mensaje perdido. El objetivo de esta inhibición es doble: por un lado limitar la implosión (limitando el número de miembros candidatos a enviar el NACK) y, por otro lado, lograr una baja latencia. Esto es debido a que los únicos miembros afectados por el error que no reciben ningún mensaje de inhibición son las hojas del árbol de error, y son éstos los miembros del grupo más cercanos al lugar de ocurrencia del error. Por este motivo éstos son los nodos encargados de solicitar la retransmis ión del paquete perdido. Después de enviar el mensaje de inhibición, cada una de las hojas del árbol de recuperación que fue afectada por el error ejecuta un experimento aleatorio, con distribución Bernoulli. Si el resultado del experimento es exitoso, la hoja envía un NACK hacia arriba del árbol de distribución. El parámetro del experimento Bernoulli se escoge de forma que con alta probabilidad se envíe un único NACK. Los objetivos de la ejecución del experimento aleatorio son lograr simultáneamente baja latencia y baja implosión. Se logra baja latencia debido a que cada nodo decide si enviar o no un NACK de manera casi inmediata (el único retardo corresponde al tiempo que demora una CPU en efectuar el experimento aleatorio), la baja implosión se logra en la medida que efectivamente se logre que se envié solamente un único NACK. Cuando el NACK es propagado hacia arriba del árbol de distribución, el primer miembro que lo recibe es precisamente la raíz del árbol de recuperación asociado al error. Debido a que esta raíz tiene una copia del paquete perdido, elimina el mensaje de la red y retransmite (hacia abajo) el paquete solicitado. Nótese que al eliminar el NACK, la raíz del árbol de recuperación asociado al error es el único miembro, de los que poseen una copia del paquete perdido, que se entera de la pérdida. Al proceder de esta forma el algoritmo consigue que: se retransmita una única copia del paquete perdido (lo que evita implosión de retransmisiones), y que esa copia sea retransmitida por el nodo más cercano al lugar del error que posee una copia del paquete perdido (lo que ayuda a obtener una baja latencia).

Después de que la raíz del árbol de recuperación retransmite el paquete perdido, este paquete se propaga normalmente hacia abajo del árbol de distribución. Cuando el paquete llega a miembros que lo habían perdido, éstos miembros se recuperan del error; y cuando el paquete llega a un miembro que no había perdido el paquete, este miembro descarta el paquete de la red, con lo cual evita que se propague inútilmente hacia abajo del árbol de distribución. 2.1 Algoritmo de fiabilidad Multipunto A continuación se entrega una definición precisa del algoritmo de fiabilidad utilizando la notación introducida anteriormente. 1.

Si un miembro del grupo multipunto detecta la pérdida de un paquete, transmite un mensaje a todos sus nodos descendientes, informándoles de este evento. Este mensaje se propaga normalmente hacia abajo a través de D. Los miembros del grupo que reciben dicho paquete, se auto inhiben de enviar un NACK respecto de ese paquete (delegando de esa forma la responsabilidad de recuperar el paquete perdido a otros miembros del grupo, motivo por el cual este mensaje se denomina mensaje de inhibición). Después de transmitir el mensaje de inhibición, el nodo continúa transmitiendo normalmente a sus descendientes los paquetes correctos que le llegan desde la fuente.

2.

Después de transmitir el mensaje de inhibición, el miembro que detectó el error (suponga que es el nodo h), decide si envía o no un NACK hacia arriba en el árbol de distribución. Para esto, efectúa un experimento aleatorio con distribución Bernoulli de parámetro p 1 (h) (más adelante se explica cómo se escoge el parámetro p 1(h)). Si el resultado del experimento aleatorio es un éxito, entonces el miemb ro envía un NACK hacia su padre en D.

3.

Después, independientemente de haber enviado o no el NACK, el nodo inicia un Timeout, TO (Ti ), con el objeto de esperar la retransmisión del paquete perdido.

4.

Si el TO (T i ) expira antes de que el paquete solicitado sea recibido, el nodo h repite los pasos 2 y 3 de este algoritmo, pero esta vez el parámetro del experimento Bernoulli vale p n (h), donde (n-1) corresponde al número de veces que el nodo h ha efectuado el paso 2 del algoritmo en su intento de recuperar el paquete perdido.

5.

Cuando un nodo del árbol de distribución que no es un miembro del grupo recibe un NACK desde uno de sus hijos en el árbol de distribución, lo retransmite a su padre en el árbol de distribución.

6.

7.

Cuando un miemb ro del grupo recibe un NACK con respecto a un paquete determinado, éste nodo retransmite el paquete solicitado a cada uno de sus hijos en el árbol de distribución y elimina el mensaje NACK de la red. Cuando el nodo h recibe la retransmisión del paquete solicitado, lo retransmite a cada uno de sus hijos en el árbol de espera Qh . Dicho paquete se propaga normalmente hacia abajo en el árbol de distribución (con lo cual cada uno de los miembros del grupo que son descendientes del nodo h recuperan el paquete perdido, sin haber participado activamente en su recuperación).

Finalmente, cuando un nodo que no fue afectado por el error recibe el paquete retransmitido, descarta el paquete de la red.

 N ( Fk )  E L | error en e j,k =  ∑ E L | e j ,k , n P(n | e j ,k )  n=1 

[

]

E[L] =

∑ E[L | error en e ]Pr (error en e ) (1) j ,k

∀ej , k ∈D

j ,k

Suponiendo que la red está compuesta por un mismo tipo de enlace, lo que implica que éstos tienen la misma probabilidad de ser afectados por los errores, se tiene que:

Pr (error en e j, k ) =

1 C ( D)

;

(2)

donde C(D) es el número de enlaces que posee el árbol de distribución D. Para calcular E

[L | error en e ] se condiciona en j,k

la iteración en la cual se envía por primera vez al menos un NACK y se aplica el teorema de probabilidades totales, con lo cual se obtiene:

[

]

pérdida de NACKs ni de paquetes retransmitidos. Esta suposición es razonable ya que la ocurrencia de un error es un fenómeno de baja probabilidad de ocurrencia . Debido a esto, esta suposición no altera de manera significativa el resultado, sin embargo simplifica el análisis (nótese que el error (o perdida de un paquete) que causa la activación del algoritmo de fiabilidad también es un fenómeno que ocurre con baja frecuencia relativa, sin embargo en esta sección se está evaluando la latencia del algoritmo justamente en esas ocasiones). La suposición anterior implica que:

[

]

(

E L n, e j, k = n ⋅ TO Tr( Fk )

)

)

(4)

donde r(Fk) es una función que entrega el nodo raíz del árbol de error Fk . Efectuando los cálculos intermedios necesarios (para más detalles consultar [8]), se concluye que la latencia media está dada por la ecuación (5).

  1     min 1+lg2      h∈Fk   p1 ( h)      TOTr(Fk )    1− ∏(1− p1(h)) + E[L] = ∑ n1− ∏ 1− p1 (h)g n−1 ∑    ∀ej , k∈D C(D) ∀h∈Fk n=2   ∀h∈Fk  

(

(3)

E L n, e j , k , se supone que no existe

Para evaluar

Sea E[L] el valor medio de la latencia. Debido a que la pérdida de un paquete puede ocurrir en cualquier enlace del árbol de distribución D, para evaluar E[L] se condiciona en el enlace en el cual ocurre el error, con lo cual se obtiene:

]

donde n identifica el número de iteraciones efectuadas por el algoritmo hasta que se envía el primer NACK; N(Fk) corresponde al máximo valor de n, dado que el error ocurrió en el enlace ej,k, es decir N(Fk) corresponde al número de la iteración del algoritmo en la cual al menos una de las hojas afectadas por el error (las hojas del árbol Fk) envía con probabilidad igual a uno un NACK; E[L| ek,j ,n] es el valor medio de la latencia dado que el error ocurrió en el enlace ej,k y que se envió por primera vez al menos un NACK en la n-ésima iteración del algoritmo; y P(n|ej,k) es la probabilidad de que se envíe al menos un NACK por primera vez en la nésima iteración del algoritmo, dado que el error ocurrió en el enlace ej,k.

3. Análisis de Rendimiento 3.1 Evaluación de la Latencia

[

(

   (5)   

)∏∏(1− p (h)g ) n−1

m=1 ∀h∈Fk

m−1

1

    1  H (Fk )   1 − ∏(1 − p1 (h)) i ⋅ p ( h ) ( 1 − p ( h ) ) ∑ ∑ ∑ ∏ 1 ∏ 1 r   ∀h∈kr   ∀h∈F  i=1 ∀krH (F ), i∈K ∀e j , k∈D C(D) ∀h∉kH ( Fk ), i H( Fk ),i k  k h (Fk ), i          n−1 1  N ( Fk )  H( Fk )  1 −    + ∑ i ⋅ p ( h ) ( 1 − p ( h ) ) ( 1 − p ( h ) ) ( 1 − p ( h ) ) ∑ ∑ ∑ ∏ n ∏ n ∏ n ∏ ∏ m r r r        i=1 ∀k H( F ), i ∈K  ∀e j, k ∈D C (D) n =2 ∀h∈kH ( Fk ), i ∀h∉kH ( Fk ), i  m=1 ∀h∈Fk k h( Fk ), i    ∀h∈Fk    E[I ] =

(6)

3.2 Evaluación de la Implosión

implosión

Sea E[I] el valor medio de la implosión. Análogamente al procedimiento usado para evaluar la latencia media, para calcular E[I] se condiciona en el enlace en el cual puede ocurrir un error, en el número de hojas que pueden enviar simultáneamente un NACK y en la iteración en que puede acontecer este hecho. Realizando los cálculos intermedios, la implosión media está dada por la ecuación (6), donde K l , u

{

media

está

R −1 R −1 E [I ] = p + (1 − p ) + 1 R

}

dada

por:

corresponde al conjunto de l-tuplas

distintas que pueden formarse a partir de u elementos diferentes. En el caso bajo análisis, l correspondería al número total de hojas de Fk y u correspondería a las hojas que envían un NACK. Sea

r k l ,u una de las l-

K l, u , y h es una de los r componentes de k l ,u . Como ejemplo de la notación tuplas del conjunto

recién definida considere el siguiente caso:

K8, 3

representa al conjunto de todas las 8-tuplas diferentes que se pueden formar a partir 3 elementos diferentes;

r k 8, 3 es una de las 8-tuplas que forman parte de r K8, 3 y h uno de los componentes de k 8, 3 ; y sea H ( Fk ) el número de hojas del árbol Fk .

4. Resultados numéricos

Figura 2. Latencia media en función de α.

En la Fig. 2 se ilustra la latencia media en función de diferentes valores de α, para tamaños de grupo que varían entre 102 y 106 miembros. En el gráfico puede verse que para tamaños de grupo mayores o iguales que 103 miembros la latencia media se mantiene alrededor de 2, independientemente del valor de α. Esto posiblemente se debe a que, con probabilidad cercana a 1, el error afecta sólo a un miembro (fenómeno que para este caso específico ocurre con probabilidad (R-1)/R), el cual envía con probabilidad 1 un NACK en la segunda iteración del algoritmo.

Considere una topología del árbol de recuperación es de tipo estrella, compuesta por R miembros del grupo multipunto, y un nodo que no es miembro. Los canales del árbol de recuperación tienen longitud igual a 1, y la misma probabilidad x de que se pierda un paquete transmitido por ellos. Usando estos valores, se tiene que la probabilidad de que una determinada hoja h envíe un NACK la primera vez que se detecta la pérdida de un determinado paquete (es decir, en la primera iteración del algoritmo), está dada por: p 1 (h )

α   = min 1 , , R − 1  

Figura 3. Implosión media en función de α. 1 ≤ h ≤ R −1

donde α es un parámetro del algoritmo, utilizado para obtener equilibrio entre la latencia y la implosión. La probabilidad de que una hoja envíe un NACK en iteraciones posteriores (n>1) se calcula suponiendo que g= R-1 (el número de hojas del árbol de recuperación) En consecuencia, se tiene que: p n h = 1; 1 ≤ h < R .

( )

A continuación se muestran algunas de las medidas de rendimiento obtenidas para este tipo de topología del árbol de recuperación. Para este caso, el valor de la latencia media está dado por:

{

}

1 E[L] = 1 + (1 − p )( R −1) + (R − 1)(2 − p ) ; y la R

En la Fig. 3 se ilustra la implosión media en función de α, para un árbol de recuperación con más de 100 hojas. En este caso se nota que a medida que el tamaño del grupo de recuperación aumenta la implosión media tiende a 1 (el valor ideal). Esto se debe a que en estos casos E[I] corresponde aproximadamente a (1+e-α). Otra forma, más práctica, de explicar esta tendencia de E[I] es notar que en estos casos con alta probabilidad el error afecta sólo a una hoja.

4.1 Otras medidas de Rendimiento Para el árbol de recuperación tipo estrella se calculan en forma adicional dos nuevas medidas. Estas son: el número medio de retransmisiones de un paquete y el número medio de NACKs enviados hasta que los r receptores reciben correctamente un paquete.

Para este propósito el comportamiento del algoritmo propuesto se puede representar por medio de una cadena de Markov (CM), en la que los estados identifican al número de receptores que todavía no han recibido correctamente un determinado paquete transmitido por la fuente. Esto significa que si la CM se encuentra en el estado i, entonces i receptores no han recibido correctamente el paquete. Lógicamente que el instante en que el transmisor envía el paquete por primera vez, ningún receptor lo ha recibido. Este es el motivo por el cual el estado inicial de la cadena de Markov es el estado R (donde R es el número de hojas del árbol de recuperación). Sea p i,j la probabilidad de que CM transite del estado i al estado j en una transmisión del paquete. Una transmisión del paquete corresponde a una iteración de los pasos 2 y 3 del algoritmo. (En adelante se usará el vocablo "paso" para referirnos a una de estas iteraciones). Evidentemente se cumple que p i,j = 0, i>j. Por otro lado, para que la CM transite del estado i al j en un paso, lo que debe ocurrir es que: (i-j) receptores de los i que no tenían el paquete lo reciban correctamente. Esto ocurre con probabilidad i  i − j ; además, los otros j receptores no lo i − j (1− f (c))   j

deben recibir, lo que ocurre con probabilidad f (c ) . Entonces la transición entre el estado i y el estado j en un paso está dada por:  i  (1 − f(c))(i− j) f(c)j ; 0 ≤ j ≤ i ≤ r  pi, j =  i − j  0 i< j 

(7)

las hojas del árbol de recuperación y no varía en el tiempo, es decir p n (h)=p. Además se define q como la probabilidad de pérdida de un NACK. Entonces, puede escribirse la probabilidad de que un NACK sea enviado por el receptor y recibido efectivamente por el transmisor como ~p = p (1 − q ) . Co mo en el caso anterior, sea

[ ]

que efectivamente llegan al transmisor hasta que los r receptores hayan recibido el paquete perdido. Sea ~ E Nr el número medio de NACKs E [N r ] = q enviados hasta que los r receptores se hayan recuperado del error. Entonces:

[ ]

r −1 r   ~ r− j ~ E[N r ] = r~ p + ∑  f (c) j (1− f (c)) E N j j (9) j =1   ~ + f (c) r E N j

[ ]

[ ]

Luego, usando funciones generadora exponencial y manipulando algebraicamente la expresión resultante, se llega a que la expresión para el número medio de NACKs enviados está dada por: En la Fig. 5 se muestra número medio de NACKs enviados hasta recibir un paquete en forma correcta versus el número de hojas del árbol de recuperación, para diferentes probabilidades de pérdida de paquete en un canal, denotada por x.

E [N r ] =

donde f (c ) es la probabilidad de que un paquete se pierda en el camino c que va entre el transmisor y el receptor [8].

Sea Tr la variable aleatoria que representa el número de transmisiones necesarias para que un paquete sea recibido exitosamente por todos los r receptores pertenecientes al árbol de recuperación mostrado en la Fig. 2. Este número de retransmisiones equivale al número de pas os que la CM demora en transitar por primera vez desde el estado r al estado 0. Sea E[Tr ] el valor medio de Tr . El número medio de retransmisiones está dado por: E[Tr ] =

 r−1  r   1 1 + ∑   f (c) j (1 − f (c) )r − j E[T j ] (8) r  (1 − f (c) )  j=1  i  

donde pr,j está dada por la ecuación (7). Para más detalles ver [8]. Evaluación del número medio de NACKs enviados hasta que los r receptores reciben correctamente un paquete . Se considera un caso especial, en el cual la probabilidad de enviar un NACK es igual para todas

r~ p q (1 − f ( c ) )

(10)

16

Número Medio de Nacks E[Nr]

Evaluación del número medio de retransmisiones de un paquete.

f (c) la probabilidad de perder

~ un paquete. Sea E N r el número medio de NACKs

14 12

X=0,9 X=0,8 x=0,7 x=0,6 x=0,5 X=0,9 X=0,8 x=0,7 x=0,6 x=0,5

10 8 6 4 2 0 10

100

1000

10000

100000

1000000

Numero de Receptores (R)

Figura 4. Número medio de Nacks versus número de hojas del árbol de recuperación.

Puede verse en el gráfico que el número medio de NACKs enviados hasta recuperar un paquete es casi independiente del número de receptores, a partir de 100 receptores y para cualquier valor de x. Esto demuestra la alta escalabilidad del algoritmo propuesto. También se puede observar que a medida que la probabilidad de pérdida de paquetes aumenta, a cantidad de NACKs enviados también se incrementa.

5. Conclusiones En este trabajo se ha realizado el análisis de rendimiento del algoritmo para la recuperación de errores en una transmisión multipunto que fue propuesto en [3]. En este algoritmo, la recuperación de errores se realiza solamente por algunos de los miembros del grupo vecinos al error. Estos nodos delimitan lo que hemos denominado árbol de recuperación. El algoritmo propuesto atribuye mayor probabilidad de solicitar la retransmisión de un paquete perdido a las hojas del árbol de recuperación más lejanas a la raíz de este árbol, pues son ellas quienes tienen mayor probabilidad de ser afectadas por la pérdida de un paquete. El algoritmo consigue una baja latencia y una baja implosión en la recuperación de errores, para cualquier tamaño del grupo multipunto. Esto se debe a que la recuperación de errores se realiza en forma local y por otra parte, a la forma con que se determina la probabilidad de que las hojas del árbol de recuperación afectadas por el error soliciten la retransmisión del paquete perdido. En base a los ejemplos analizados puede decirse que el algoritmo presenta una alta escalabilidad, ya que tanto la latencia como la implosión media presentan valores cercanos al ideal, para cualquier tamaño del grupo multipunto. Entre las medidas de valor medio se calcularon la latencia, la implosión, el número de NACKS y el número de retransmisiones respecto de un paquete perdido. Las medidas fueron evaluadas en base a modelos probabilísticos y de cadenas de Markov. La solución del modelo es válida para cualquier topología del árbol de distribución y para cualquier número de miembros que tenga un grupo multipunto.

Agradecimientos Este trabajo fue financiado en parte por los proyectos FONDECYT Nº 1000055 /2000, por el proyecto DIPUV 19/ 2001 de la Universidad de Valparaíso, por el proyecto 230223 de la Universidad Técnica Federico Santa María, y por el proyecto DISQET (CICYT TIC2002-00818).

Referencias [1] C. Diot, W.Dabbous and J.Crowcroft, “Multipoint Communication: A Survey Protocols, Functions and Mechanism", IEEE Journal on Selected Areas in Communications Vol. 15, No. 3, April, 1997. [2] D. Towsley, J.Kurose and S. Pingali, " A Comparison of Sender-Initiated and ReceiverInitiated Reliable Multicast Protocols", IEEE Journal on Selected Areas in Communications, April 1997 .

[3] M. Barría, R. Vallejos, L.F. Soares, “A Failure Tree Reliable Multicast Algorithm Based on Recovery Tree (RMART)” , in Proceedings 9th IFIP Conference on Performance Modelling and Evaluation of ATM & IP Networks 2001, Julio 2001, Budapest. [4] M. Barría, R. Vallejos, L.F. Soares , Algoritmo para la recuperación de errores de una transmisión multipunto, CLEI 2000, México. [5] T. Ballardie, “Core based tree (CBT) multicast: Architectural overview and specification” Internet Draft RFC, July 1994. [6] T. Bilhartz, J.B. Cain, D. Fieg and S.G. Batsell, “Performance and Resource Cost Comparisons for the CBT and PIM Multicast Routing Protocols ”, IEEE JSAC, 15(3), April 1997. [7] C. Kenneth Miller, "Multicast Networking and Applications", Addisson - Wesley, 1999. [8] M. Barría, R. Vallejos, M. Aguilar. “Evaluación de Rendimiento de un Algoritmo para Recuperación de Errores en Comunicaciones Multipunto”, Informe Técnico Depto. Electrónica Universidad Técnica Federico Santa María, 2003.