Método y dispositivo para la disposición de pares en una red P2P de difusión continua en directo.

Un método para disponer pares en una red P2P que comprende una fuente de flujo continuo y una pluralidad de pares,

cuyo método está caracterizado por cuanto que comprende:

la recepción de una demanda desde un par entrante en la red para recibir contenido de datos;

la determinación con respecto a un punto de reproducción en tiempo real del contenido de datos distribuidos por la fuente de flujo continuo, una latencia con la que el par entrante ha de recibir el contenido de los datos a partir de una distribución de probabilidad determinada para las latencias con las que los pares de la red reciben el contenido de datos distribuido por la fuente de flujo continuo; y

la puesta a disposición del par entrante con una pluralidad de los pares seleccionados, de forma aleatoria, cuyo contenido de datos demandado puede descargarse, con una probabilidad prevista, en función de la latencia determinada y la capacidad de ancho de banda de la pluralidad de los pares seleccionados aleatoriamente, en donde al par entrante le está permitido descargar, con la probabilidad prevista, el contenido de datos demandado a partir de uno seleccionado de entre la pluralidad de pares seleccionados aleatoriamente que tienen una latencia inferior a la determinada para un par entrante.

Método y dispositivo para la disposición de pares en una red P2P de difusión continua en directo CAMPO DE LA INVENCIÓN

La presente invención se refiere a un método de disposición de pares en una red P2P y a un dispositivo para disponer pares en una red P2P.

ANTECEDENTES DE LA INVENCIÓN

Para el flujo continuo de vídeo en directo en un sistema de cliente-servidor, el flujo de vídeo se descarga desde el servidor de flujo continuo (esto es, la fuente) al cliente. Un flujo continuo de vídeo consiste en un conjunto de elementos de datos consecutivos, un subconjunto de datos, que el cliente demanda periódicamente con el fin de reproducir las señales de video. Un servicio de flujo continuo en directo, susceptible de escalamiento, requiere un ancho de banda del flujo continuo de magnitud suficiente para satisfacer a un número creciente de clientes a través de Internet. Con el fin de reducir el coste del servidor de flujo continuo, se ha desarrollado un flujo continuo en directo de par a par (P2P). El concepto básico de flujo continuo en directo P2P es hacer que los clientes, referidos como pares en este contexto, compartan la carga con el servidor de flujo continuo.

Los sistemas de flujo continuo en directo P2P han merecido gran interés en los últimos años y tienen la ventaja de permitir a una fuente de flujo continuo difundir, a modo de ejemplo, una señal de vídeo en directo a un gran número de pares, sin tener que proporcionar la totalidad del ancho de banda requerido. Esta operación se realiza haciendo uso de la capacidad de carga de los pares para prestar asistencia a la fuente de flujo continuo en la difusión del contenido a los pares.

Las redes P2P comprenden cualesquiera redes constituidas por entidades que proporcione cada una acceso a una parte de sus recursos (p.e., capacidad de procesamiento, memorización en disco y/o ancho de banda) a otras entidades. El concepto de P2P difiere de la arquitectura de cliente/servidor tradicional basada en redes en donde una o más entidades operativas (p.e., ordenadores) están dedicadas a prestar servicio a los demás en la red. En condiciones normales, las entidades en una red P2P ejecutan protocolos de gestión de redes similares y programas informáticos afines. Las aplicaciones para las redes P2P son numerosas y pueden incluir, a modo de ejemplo, el transporte y/o memorización de datos en Internet, tal como una distribución de vídeo para propietarios de contenidos.

Numerosos sistemas se han desarrollado para hacer uso eficiente de la capacidad de carga de los pares. Estos sistemas pueden dividirse en dos categorías principales.

Los denominados sistemas basados en árboles de decisión operativa utilizan la construcción de uno o más árboles estructurados en una red de superposición en donde los pares en la parte superior de cada árbol operativo alimenta a los pares situados debajo. Este método funciona adecuadamente cuando los pares no se incorporan o dejan el sistema a alta frecuencia puesto que se consigue el flujo de datos sin necesidad de ningún mensaje adicional entre los pares. Sin embargo, en un entorno de alta rotación de pares, el mantenimiento de los árboles de decisión operativa puede ser muy costoso y a veces, se hacen necesarias la destrucción y reconstrucción de dichos árboles de decisión.

Los sistemas basados en mallas no hacen necesaria una construcción del tipo de árboles de decisión o dicho de otro modo, la conectividad de pares no forma una superposición especificada y están conectados entre sí en una manera no estructurada. Intercambian datos por intermedio de la así denominada comunicación gossip (`rumor) o enviando mensajes de demanda de datos entre sí. Un inconveniente con estos sistemas basados en mallas operativas es que pueden tener un largo tiempo de establecimiento operativo, puesto que los nodos necesitan negociar entre sí para encontrar pares. Sin embargo, numerosos sistemas utilizan el método basado en mallas puesto que es muy sólido para utilizaciones de gran magnitud. En dichos sistemas, cada par tiene varios pares próximos de los que descarga potencialmente y el fallo de cualquier par próximo no es, por lo tanto, tan crítico como en los sistemas basados en árboles de decisión.

Aunque los pares individuales toman decisiones, a nivel local, sin tener una visión global en los sistemas basados en mallas, pueden, no obstante, alcanzar ahorros comparables al que obtienen los sistemas basados en árboles de decisión cuando se considera la rotación de pares denominada peerchurn, principalmente puesto que no tienen que realizar la pesada carga de mantener una visión de la estructura de conectividad global.

En una red de flujo continuo en directo P2P descentralizada, cada par tiene k pares próximos desde los cuales puede intentar descargar el contenido de datos. De este modo, el par intentará encontrar un par próximo desde el que efectuar la descarga en lugar de descargar el contenido de datos desde el servidor de flujo continuo. Dada dicha red de superposición de la técnica anterior, si los pares inician el flujo continuo de contenido de datos desde el mismo punto en el tiempo, todos los pares no encontrarán un par de carga que tenga un contenido útil. En

consecuencia, casi todos los pares efectuarán la descarga desde el servidor de flujo continuo, lo que da lugar, en última instancia, a ahorros mínimos en la utilización del ancho de banda del servidor de flujo continuo.

La ¡dea inventiva de Leyes de escalamiento y soluciones de compromiso en un flujo continuo multimedia en directo par a par por Small et al investiga las leyes de escalamiento de un flujo continuo multimedia P2P en directo estudiando, de forma cuantitativa, los efectos asintóticos y las soluciones de compromiso entre tres parámetros principales en el flujo continuo P2P: coste del ancho de banda del servidor, el número máximo de pares que pueden soportarse y el número máximo de saltos operativos de flujo continuo experimentados por un par.

SUMARIO DE LA INVENCIÓN

Un objetivo de la presente invención es resolver, o al menos mitigar, estos problemas en la técnica anterior.

Este objetivo se alcanza por el método y dispositivo para la disposición de pares en una red P2P en conformidad con las reivindicaciones independientes y las formas de realización preferidas se definen por las reivindicaciones subordinadas.

Con esta finalidad, se recibe una demanda desde un par entrante en la red para recibir un contenido de datos. En adelante, se determina una latencia con la que el par entrante ha de recibir el contenido de datos con respecto a un punto de reproducción en tiempo real del contenido de datos distribuido por la fuente de flujo continuo. Después de que se haya determinado la latencia, el par entrante se proporciona con una pluralidad de pares aleatoriamente seleccionados a partir de los que se puede descargar el contenido de datos demandado con una probabilidad prevista, dependiendo de la latencia determinada. De este modo, al par entrante le está permitido descargar, con la probabilidad prevista, el contenido de datos demandado desde un par seleccionado de entre los pares aleatoriamente seleccionados que tengan una latencia inferior a la determinada para el par entrante.

De este modo, seleccionando adecuadamente una latencia apropiada para el par entrante, puede aumentarse la posibilidad de tener la descarga del par entrante desde uno de sus pares próximos. De forma análoga, lo que antecede disminuye el riesgo de tener un par que descargue el contenido de datos a partir de la fuente de flujo continuo.

Conviene señalar que la invención se refiere a todas las combinaciones posibles de características establecidas en las reivindicaciones. Otras características y ventajas de la presente invención se harán evidentes cuando se constaten los contenidos de las reivindicaciones adjuntas y de la descripción siguiente. Los expertos en esta técnica entenderán que pueden combinarse diferentes características de la presente invención para crear formas de realización distintas a las que se describen a continuación.

BREVE DESCRIPCIÓN DE LOS DIBUJOS

La invención se describe a continuación, a modo de ejemplo, haciendo referencia a los dibujos adjuntos, en donde:

La Figura 1 ilustra un flujo continuo de datos en una red P2P de flujo continuo en directo según la técnica anterior;

Las Figuras 2a y b ¡lustran un flujo continuo de datos en una red P2P de flujo continuo en directo según una forma de realización de la presente invención;

La Figura 3 ilustra la función de un dispositivo de seguimiento según una forma de realización de la presente invención;

La Figura 4 ilustra una distribución de probabilidad de latencias... [Seguir leyendo]

1. Un método para disponer pares en una red P2P que comprende una fuente de flujo continuo y una pluralidad de pares, cuyo método está caracterizado por cuanto que comprende:

la recepción de una demanda desde un par entrante en la red para recibir contenido de datos;

la determinación con respecto a un punto de reproducción en tiempo real del contenido de datos distribuidos por la fuente de flujo continuo, una latencia con la que el par entrante ha de recibir el contenido de los datos a partir de una distribución de probabilidad determinada para las latencias con las que los pares de la red reciben el contenido de datos distribuido por la fuente de flujo continuo; y

la puesta a disposición del par entrante con una pluralidad de los pares seleccionados, de forma aleatoria, cuyo contenido de datos demandado puede descargarse, con una probabilidad prevista, en función de la latencia determinada y la capacidad de ancho de banda de la pluralidad de los pares seleccionados aleatoriamente, en donde al par entrante le está permitido descargar, con la probabilidad prevista, el contenido de datos demandado a partir de uno seleccionado de entre la pluralidad de pares seleccionados aleatoriamente que tienen una latencia inferior a la determinada para un par entrante.

2. El método según la reivindicación 1, en donde la etapa de la determinación de la latencia para el par entrante comprende:

la determinación de la probabilidad de que ninguno de entre la pluralidad de pares seleccionados aleatoriamente tuviere una latencia que es inferior a la determinada para el par entrante formulando una experiencia binómica, en donde cero resultados operativamente satisfactorios se definen en un número de pruebas igual al número de pares seleccionados aleatoriamente; y

la determinación de la probabilidad de que al menos uno de entre la pluralidad de pares seleccionados aleatoriamente tiene una latencia, con respecto a un punto de reproducción en tiempo real del contenido de datos distribuidos por la fuente de flujo continuo, que es inferior a la determinada para el par entrante, sustrayendo de 1 la probabilidad de que ninguno de entre la pluralidad de los pares seleccionados aleatoriamente tuviere un tiempo de latencia inferior al determinado para el par entrante.

3. El método según la reivindicación 1, en donde la probabilidad de que el par entrante sea capaz de descargar el contenido de datos demandado desde uno seleccionado entre la pluralidad de pares seleccionados aleatoriamente se determine como el producto de:

la probabilidad de que el par entrante tenga una descarga operativamente satisfactoria del contenido, a partir de un par seleccionado de entre la pluralidad de pares seleccionados aleatoriamente, que se determina calculando la relación entre un número previsto de respuestas operativamente satisfactorias y un número total de demandas de descarga de los pares de la red; y

la probabilidad de que al menos un par de entre la pluralidad de pares seleccionados aleatoriamente tenga una latencia que sea inferior a la determinada para el par entrante y que una demanda de descarga se trasladará a uno cualquiera de dichos pares que tenga una latencia inferior a la determinada para el par entrante.

4. El método según una de las reivindicaciones precedentes, en donde la etapa de tener en cuenta la capacidad de ancho de banda de la pluralidad de los pares seleccionados aleatoriamente comprende:

la modelización de la latencia y de la capacidad del ancho de banda de la pluralidad de los pares seleccionados aleatoriamente como variables de probabilidad conjunta y la probabilidad de que el par entrante sea capaz de descargar el contenido de datos demandado desde un par seleccionado de entre la pluralidad de pares seleccionados aleatoriamente se determine sobre la base de la probabilidad conjunta de la latencia y de la capacidad de ancho de banda.

5. El método según la reivindicación 4, en donde la probabilidad de que el par entrante sea capaz de descargar el contenido de datos demandado desde un par seleccionado de entre la pluralidad de pares seleccionados aleatoriamente se determine como el producto de:

la probabilidad de que el par entrante realice una descarga de contenido de los datos a partir de un par seleccionado de entre la pluralidad de los pares seleccionados aleatoriamente que tenga una capacidad de carga particular a partir de una pluralidad de las capacidades de carga posibles, que se determina calculando la relación entre un número previsto de respuestas operativamente satisfactorias y el número total de demandas de descarga de los pares de la red; y

la probabilidad de que al menos un par de entre la probabilidad de los pares seleccionados aleatoriamente tenga

una latencia que sea inferior a la determinada para el par entrante y que una demanda de descarga se trasladará a uno cualquiera de dichos al menos un par que tenga una latencia Inferior a la determinada para el par entrante.

6. El método según cualquiera de las reivindicaciones precedentes, en donde la etapa de la determinación de la latencia para el par entrante comprende:

la determinación de una distribución de probabilidad para las latenclas con las que los pares de la red reciben el contenido de datos distribuido por la fuente de flujo continuo;

la optimización de un parámetro de dicha distribución de probabilidad utilizando un algoritmo de optimización evolutiva para todas las latenclas posibles, haciendo así máxima la probabilidad de que el par entrante sea capaz de descargar el contenido de datos demandado desde un par seleccionado entre la pluralidad de los pares seleccionados aleatoriamente que tengan una latencia Inferior a la determinada para el par entrante.

7. El método según la reivindicación 6, en donde la distribución de probabilidad es una distribución de Poisson y el parámetro a optimizares el parámetro de la distribución de Poisson A.

8. El método según cualquiera de las reivindicaciones 1 a 5, en donde la etapa de la determinación de la latencia para el par entrante comprende:

la determinación de un hlstograma de probabilidades para las latenclas con las que los pares de la red reciben el contenido de los datos distribuidos por la fuente de flujo continuo;

la optimización del histograma utilizando un algoritmo de optimización evolutiva para todas las latencias posibles haciendo así máxima la probabilidad de que el par entrante sea capaz de descargar el contenido de datos demandado a partir de un par seleccionado de entre la pluralidad de los pares seleccionados aleatoriamente que tengan una latencia inferior a la determinada para el par entrante.

9. Un dispositivo para disponer pares en una red P2P que comprende una fuente de flujo continuo y una pluralidad de pares, estando dicho dispositivo caracterizado por cuanto que comprende:

una unidad de procesamiento; y

una Interfaz de comunicación, en donde

dicha Interfaz de comunicación está dispuesta para recibir una demanda desde un par entrante en la red para recibir contenido de datos;

estando dicha unidad de procesamiento dispuesta para determinar, con respecto a un punto de reproducción en tiempo real del contenido de datos distribuidos por la fuente de flujo continuo, una latencia con la que el par entrante ha de recibir el contenido de datos a partir de una distribución de probabilidad determinada para las latencias con las que los pares de la red reciben el contenido de datos distribuido por la fuente de flujo continuo; y

estando dicha Interfaz de comunicación dispuesta para proporcionar el par entrante con una pluralidad de los pares seleccionados aleatoriamente de los que el contenido de datos demandado puede descargarse con una probabilidad prevista en función de la latencia determinada y de la capacidad de ancho de banda de la pluralidad de pares seleccionados aleatoriamente, en donde al par entrante le está permitido descargar, con la probabilidad prevista, el contenido de datos demandado a partir de un par seleccionado de entre dicha pluralidad de pares seleccionados aleatoriamente que tenga una latencia inferior a la determinada para el par entrante.

1. El dispositivo según la reivindicación 9, estando, además, dicha unidad de procesamiento dispuesta para determinar la latencia para el par entrante en las etapas siguientes:

determinar la probabilidad de que ninguno de la pluralidad de los pares seleccionados aleatoriamente tuviere un tiempo de latencia Inferior al determinado para el entrante formulando una experiencia blnómlca, en donde los cero resultados operativamente satisfactorios se definen en un número de pruebas igual al número de pares seleccionados aleatoriamente; y

determinar la probabilidad de que al menos un par de entre la pluralidad de pares seleccionados aleatoriamente tenga una latencia, con respecto a un punto de reproducción en tiempo real del contenido de datos distribuidos por la fuente de flujo continuo, que sea inferior a la determinada para el par entrante, sustrayendo de 1 la probabilidad de que ninguno de entre la pluralidad de los pares seleccionados aleatoriamente tuviere una latencia inferior a la determinada para el par entrante.

11. El dispositivo según la reivindicación 9, en donde dicha unidad de procesamiento está dispuesta para determinar la probabilidad de que el par entrante sea capaz de descargar el contenido de datos demandado desde

un par seleccionado de entre la pluralidad de pares seleccionados aleatoriamente que se determine como el producto de:

la probabilidad de que el par entrante realice una descarga de contenido, operativamente satisfactoria, desde un par seleccionado de entre la pluralidad de pares seleccionados aleatoriamente, que se determina calculando la relación entre un número previsto de respuestas operativamente satisfactorias y un número total de demandas de descarga desde los pares de la red; y

la probabilidad de que al menos un par de entre la pluralidad de los pares seleccionados aleatoriamente tenga una latencla que sea Inferior a la determinada para el par entrante y que una demanda de descarga se desplace a uno cualquiera de dichos pares que tengan una latencia inferior a la determinada para el par entrante.

12. El dispositivo según cualquiera de las reivindicaciones 9 a 11, en donde dicha unidad de procesamiento está dispuesta para tener en cuenta la capacidad de ancho de banda de la pluralidad de los pares seleccionados aleatoriamente mediante:

la modellzaclón de la latencia y de la capacidad del ancho de banda de la pluralidad de los pares seleccionados aleatoriamente como variables de probabilidad conjunta y la probabilidad de que el par entrante sea capaz de descargar el contenido de datos demandado desde un par seleccionado de entre la pluralidad de los pares seleccionados aleatoriamente que se determine sobre la base de la probabilidad conjunta de la latencia y de la capacidad de ancho de banda.

13. El dispositivo según la reivindicación 12, en donde la unidad de procesamiento está dispuesta para determinar la probabilidad de que el par entrante sea capaz de descargar el contenido de datos demandado desde un par seleccionado de entre la pluralidad de los pares seleccionados aleatoriamente que se determine como el producto de:

la probabilidad de que el par entrante realice una descarga de contenido de los datos, de forma operativamente satisfactoria, desde un par seleccionado de entre la pluralidad de los pares seleccionados aleatoriamente que tenga una capacidad de carga particular de entre una pluralidad de posibles capacidades de carga, que se determina calculando la relación entre un número previsto de respuestas operativamente satisfactorias y un número total de demandas de descarga de los pares de la red; y

la probabilidad de que al menos un par de entre la pluralidad de los pares seleccionados aleatoriamente tenga una latencia que sea inferior a la determinada para el par entrante y que una demanda de descarga se traslade a un par cualquiera de entre al menos un par que tenga una latencla inferior a la determinada para el par entrante.

14. El dispositivo según cualquiera de las reivindicaciones 9 a 13, estando dicha unidad de procesamiento dispuesta para determinar la latencia para el par entrante mediante la operación:

determinar una distribución de probabilidad para las latenclas con las que los pares de la red reciben el contenido de datos distribuido por la fuente de flujo continuo; y

optimizar un parámetro de dicha distribución de probabilidad utilizando un algoritmo de optimización evolutiva para todas las latencias posibles, haciendo asi máxima la probabilidad de que el par entrante sea capaz de descargar el contenido de datos demandado desde un par seleccionado de entre la pluralidad de los pares seleccionados aleatoriamente que tenga una latencia inferior a la determinada para el par entrante.

15. Un producto de programa Informático que comprende componentes ejecutables por ordenador para hacer que un dispositivo realice las etapas según cualquiera de las reivindicaciones 1 a 8, cuando los componentes ejecutables por ordenador se ejecuten en una unidad de procesamiento incluida en el dispositivo.