Método y dispositivo para disposición de pares en redes superpuestas P2P de flujo continuo restringido.

Un método para disponer una red superpuesta P2P que comprende una fuente de flujo continuo dispuesta para hacer fluir contenido de datos y una pluralidad de pares dispuestos en capas de distribución,

comprendiendo el método las etapas de:

disponer (S401) los pares en las capas de distribución de manera que los requisitos de descarga de contenido de datos de pares en una capa de distribución cualquiera no superen la capacidad de distribución de contenido de datos de pares en una capa de distribución inmediatamente anterior;

categorizar los pares en diferentes categorías, en el que los pares de una categoría se restringen de comunicar con los pares de una categoría diferente:

seleccionar (S402), cuando un primer par tiene capacidad para distribuir un flujo de contenido de datos a otro par en una capa inmediatamente posterior pero se restringe de hacerlo, un segundo par desde una capa de distribución posterior a la del primer par, segundo par que no se restringe distribuir el flujo de contenido de datos a dicho otro par; y

cambiar (S403) las posiciones del primer par y el segundo par seleccionado en la red superpuesta.

Método y dispositivo para disposición de pares en redes superpuestas P2P de flujo continuo restringido Campo técnico

La invención se refiere a un método y un dispositivo para disponer una red superpuesta P2P de flujo continuo restringida.

Antecedentes

Para flujo continuo de vídeo en directo en un enfoque cliente-servidor, el flujo de vídeo se descarga desde el servidor de flujo continuo (es decir, la fuente) hasta el cliente. Un flujo de vídeo consiste en un conjunto de trozos de datos consecutivos que el cliente solicita periódicamente para reproducir el vídeo. Un servicio de flujo continuo en directo escalable requiere alto ancho de banda de servidor de flujo continuo para satisfacer un número creciente de clientes a través de internet. Para reducir el coste del servidor de flujo continuo, se ha desarrollado flujo continuo en directo entre pares (P2P). El concepto básico del flujo continuo en directo P2P es hacer que los clientes, denominados como pares en este contexto, compartan la carga con el servidor de flujo continuo.

Los sistemas de flujo continuo en directo P2P han ganado mucho interés en los últimos años ya que tienen la ventaja de permitir que se difunda una fuente de flujo continuo, por ejemplo, un evento de vídeo en directo a un gran número de pares, sin tener que proporcionar todo el ancho de banda requerido. Esto se hace haciendo uso de la capacidad de carga de los pares para ayudar a la fuente de flujo continuo a difundir el contenido a los pares.

Las redes P2P comprenden cualquier red compuesta de entidades que cada una proporciona acceso a una porción de sus recursos (por ejemplo, capacidad de procesamiento, almacenamiento de disco y/o ancho de banda) a otras entidades. El concepto P2P se diferencia de la arquitectura cliente/servidor tradicional basada en redes donde una o más entidades (por ejemplo, ordenadores) están especializadas para servir a las otras en la red. Típicamente, las entidades en una red P2P ejecutan protocolos y software de interconexión de red similares. Las aplicaciones para redes P2P son numerosas y pueden comprender, por ejemplo, transportar y/o almacenar datos en Internet, tal como distribución de vídeo para propietarios de contenido.

Se han desarrollado muchos enfoques para hacer uso de manera eficaz de la capacidad de carga de los pares. Estos enfoques pueden dividirse en dos categorías principales.

Sistemas basados en árbol están basados en o que construyen uno o más árboles estructurados en una red superpuesta donde los pares en la parte superior de cada árbol alimentan los pares por debajo de ellos. Este enfoque funciona bien cuando los pares no se unen o dejan el sistema a alta frecuencia ya que el flujo de datos se consigue sin ningún mensaje adicional entre los pares. Sin embargo, en un entorno altamente mezclado, el mantenimiento del árbol puede ser muy costoso y en ocasiones es necesaria la destrucción y reconstrucción del árbol o árboles.

Sistemas basados en malla no imponen una construcción en árbol, o en otras palabras; la conectlvldad de pares no forma una superposición especificada, sino que los pares se conectan entre sí de una manera desestructurada. Intercambian datos a través de la denominada comunicación de inspección o enviando mensajes de solicitud de datos entre sí. Una desventaja con los sistemas basados en malla es que pueden tener un largo tiempo de configuración, ya que los nodos necesitan negociar entre sí para encontrar pares. Sin embargo, muchos sistemas usan el enfoque basado en malla ya que es muy robusto a alta mezcla. En tales sistemas cada par tiene un número de vecinos desde los que potencialmente descarga y el fallo de cualquier vecino por lo tanto no es tan crítico como en los enfoques basados en árbol.

Aunque los pares individuales toman decisiones localmente sin una visión local en los enfoques basados en malla, pueden alcanzar aún ahorros comprables a los enfoques basados en árbol cuando se considera mezcla de pares, principalmente puesto que no tienen que llevar la pesada tara de mantener una visión de la estructura de conectividad global.

En redes P2P, los pares de una categoría dada pueden restringirse desde los datos de distribución a los pares de una cierta otra categoría. Por ejemplo, los cortafuegos pueden ser un problema y las restricciones geográficas otro. Un diseñador de sistema puede aplicar restricciones a una red P2P de manera que un par en Europa pueda conectar a cualquier otro par en Europa o Rusia, pero no a un par en China, mientras que un par Ruso podría conectar a uno cualquiera. Por lo tanto, los pares están categorlzados en grupos de conectividad, categorlzaclón que controla a qué otros grupos de conectividad de pares pueden conectarse los pares.

En redes P2P, pueden ocurrir problemas en casos donde los pares están localizados detrás de traductores de dirección red haciendo difícil el establecimiento de las conexiones entre pares y en ocasiones incluso imposible. La traducción de dirección de red (NAT) permite a un dispositivo de red, tal como un encaminador o un cortafuegos,

asignar una dirección pública a un grupo de ordenadores dentro de una red privada tal como una red de área local (LAN), para limitar el número de direcciones IP públicas que una organización o compañía deben usar. Por lo tanto, únicamente se requiere una única dirección IP sencilla para representar todo el grupo de ordenadores. Sin embargo, puesto que la conectividad de extremo a extremo de IP a lo largo de una red se reserva con el uso de NAT, puede no ser posible establecer una conexión entre dos pares dados cualquiera. Existen varios diferentes tipos de NAT (cono total, cono restringido, restringida por puerto, simétrica, etc.), siendo algunos compatibles para comunicación entre sí, mientras que otros no. Existen varios métodos para posibilitar que pares restringidos por NAT establezcan una conexión, tal como por ejemplo STUN, TURN e ICE. Sin embargo, estos métodos no siempre garantizan que funcionen y su efectividad al establecer una conexión entre dos tipos de NAT dados cualquiera puede expresarse de manera probabilística. Para concluir, esta restricción finalmente da como resultado ahorros de ancho de banda reducidos en el servidor de flujo continuo.

El documento US 26/25967 desvela un sistema y método para suministro de datos de difusión a través de una red en árbol aumentada que incluye un servidor de contenido, un servidor en árbol, un servidor de aumento y al menos un nodo. El servidor de contenido hace fluir una fracción de los datos de difusión al servidor de árbol, y hace fluir un complemento a la fracción de los datos de difusión al servidor de aumento. Un nodo conecta al servidor de árbol, recibiendo de esta manera la fracción de los datos de difusión. El nodo conecta al servidor de aumento, recibiendo de esta manera el complemento de la fracción de los datos de difusión desde el servidor de aumento. El nodo ensambla la fracción de los datos de difusión con el complemento para la fracción de los datos de difusión para volver a ensamblar los datos de difusión, por lo que los datos de difusión se suministran al nodo.

Sumario

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

Este objeto se consigue en un primer aspecto de la presente invención mediante un método de acuerdo con la reivindicación 1.

Este objeto se consigue en un segundo aspecto de la presente invención mediante un dispositivo de acuerdo con la reivindicación 9.

Una ventaja de la presente invención es que reduce carga en la fuente de flujo continuo en una red superpuesta P2P donde se imponen restricciones para contenido de datos de flujo continuo.

En la presente invención, los pares en la red superpuesta P2P se disponen en general en capas de distribución de manera que los pares con ancho de banda de carga superior se colocan más cerca de la fuente de flujo continuo para permitir mayores ahorros de ancho de banda en la red. Los pares se disponen en las capas de distribución de tal manera que la suma de la capacidad de carga de los pares en cualquier capa dada es más que suficiente para proporcionar a los pares en una capa inmediatamente posterior. Es decir, se selecciona el número de pares dispuestos en una capa particular de manera que su demanda de ancho de banda total no supere la capacidad de carga de los pares de la capa inmediatamente anterior. Como se ha mencionado anteriormente, en presencia de restricciones de flujo continuo de datos, tales como por ejemplo restricciones de NAT, puede surgir una situación donde aunque los pares tengan ancho de banda disponible, las conexiones no pueden establecerse y por lo tanto algunos pares tienen que... [Seguir leyendo]

1. Un método para disponer una red superpuesta P2P que comprende una fuente de flujo continuo dispuesta para hacer fluir contenido de datos y una pluralidad de pares dispuestos en capas de distribución, comprendiendo el método las etapas de:

disponer (S41) los pares en las capas de distribución de manera que los requisitos de descarga de contenido de datos de pares en una capa de distribución cualquiera no superen la capacidad de distribución de contenido de datos de pares en una capa de distribución Inmediatamente anterior;

categorizar los pares en diferentes categorías, en el que los pares de una categoría se restringen de comunicar con los pares de una categoría diferente:

seleccionar (S42), cuando un primer par tiene capacidad para distribuir un flujo de contenido de datos a otro par en una capa inmediatamente posterior pero se restringe de hacerlo, un segundo par desde una capa de distribución posterior a la del primer par, segundo par que no se restringe distribuir el flujo de contenido de datos a dicho otro par; y

cambiar (S43) las posiciones del primer par y el segundo par seleccionado en la red superpuesta.

2. El método de la reivindicación 1, en el que la etapa para seleccionar comprende adicionalmente:

seleccionar aleatoriamente un segundo par que no se restringe de distribuir el flujo de contenido de datos a dicho otro par, que tiene suficiente capacidad para distribuir el flujo de contenido de datos, y que no se restringe de recibir un flujo de contenido de datos desde un par que estaba distribuyendo contenido de datos al primer par.

3. El método de las reivindicaciones 1 o 2, en el que los pares están categorizados en diferentes categorías de traducción de dirección de red (NAT).

4. El método de una cualquiera de las reivindicaciones anteriores, en el que la disposición de los pares en capas de distribución se realiza para pares sucesivos de capas de manera que se tiene en cuenta el flujo continuo de contenido de datos entre dos capas cualquiera empezando desde la capa inmediatamente posterior a la fuente de flujo continuo y finalizando en la capa inmediatamente anterior de la última capa de distribución.

5. El método de una cualquiera de las reivindicaciones 3 o 4, que comprende adicionalmente la etapa de:

determinar, para la capa de distribución en la que está dispuesto el primer par, qué categoría tienen los pares con menos requisitos de descarga de contenido de datos satisfechos.

6. El método de la reivindicación 5, que comprende adicionalmente la etapa de:

determinar cuál de los pares en la categoría con el menor requisito de descarga de contenido de datos satisfecho que tiene la capacidad de carga más baja.

7. El método de la reivindicación 6, que comprende adicionalmente la etapa de:

determinar, en la capa de distribución inmediatamente anterior a la del primer par, qué categorías no han utilizado capacidad de carga y que tienen adicionalmente capacidad para cargar el número requerido de subflujos de datos de manera que un par de descarga en una capa de distribución inmediatamente posterior pueda representar completamente un contenido de datos.

8. El método de la reivindicación 7, que comprende adicionalmente la etapa de:

identificar el segundo par como el par que tiene la mayor capacidad de carga entre los pares localizados en capas de distribución posteriores a la del primer par, pares que pueden adicionalmente descargar el contenido de datos desde un par en la categoría determinada que tienen capacidad de carga sin utilizar, tienen capacidad de carga disponible y pertenecen a una categoría que se permite cargar contenido de datos al primer par.

9. Un dispositivo (41) para disponer una red superpuesta P2P que comprende una fuente (44) de flujo continuo dispuesta para hacer fluir contenido de datos y una pluralidad de pares dispuestos en capas de distribución, comprendiendo el dispositivo:

una unidad (43) de procesamiento que está configurada para

disponer los pares en las capas de distribución de manera que los requisitos de descarga de contenido de datos de los pares en una capa de distribución cualquiera no superen la capacidad de distribución de contenido de datos de los pares en una capa de distribución inmediatamente anterior;

categorizar los pares en diferentes categorías, en el que los pares de una categoría se restringen de comunicar con los pares de una categoría diferente;

seleccionar, cuando un primer par tiene capacidad para distribuir un flujo de contenido de datos a otro paren una capa inmediatamente posterior pero se restringe de hacerlo, un segundo par desde una capa de distribución posterior a la del primer par, segundo par que no se restringe de distribuir el flujo de contenido de datos a dicho otro par; y

cambiar posiciones del primer par y el segundo par seleccionado en la red superpuesta.

1. El dispositivo de la reivindicación 9, en el que la unidad de procesamiento está configurada adicionalmente para:

seleccionar aleatoriamente un segundo par que no se restringe de distribuir el flujo de contenido de datos a dicho otro par, que tiene suficiente capacidad para distribuir el flujo de contenido de datos, y que no se restringe de recibir un flujo de contenido de datos desde un parque estaba distribuyendo contenido de datos al primer par.

11. El dispositivo de una cualquiera de las reivindicaciones 9 o 1, en el que la unidad de procesamiento está configurada para:

determinar, para la capa de distribución en la que está dispuesto el primer par, qué categoría tiene pares con menos requisitos de descarga de contenido de datos satisfechos.

12. El dispositivo de la reivindicación 11, en el que la unidad de procesamiento está configurada para, cuando se determina qué categoría tiene pares con menos requisitos de descarga de contenido de datos satisfechos:

calcular, para cada par en la categoría, el argumento de la diferencia entre el número de sub-flujos de datos descargados requerido para representar completamente un contenido de datos difundido mediante la fuente de flujo continuo y el número real de sub-flujos de datos descargados.

13. El dispositivo de una cualquiera de las reivindicaciones 11 o 12, en el que la unidad de procesamiento está configurada adicionalmente para:

determinar cuál de los pares en la categoría con el menor requisito de descarga de contenido de datos satisfecho que tiene la capacidad de carga más baja.

14. El dispositivo de una cualquiera de las reivindicaciones 12 o 13, en el que la unidad de procesamiento está configurada adicionalmente para:

determinar, en la capa de distribución inmediatamente anterior a la del primer par, qué categorías tienen capacidad de carga sin utilizar y que tienen además capacidad para cargar el número requerido de sub-flujos de datos de manera que un par de descarga en una capa de distribución inmediatamente posterior pueda representar completamente un contenido de datos.

15. Un producto de programa informático que comprende componentes ejecutables por ordenador para producir que un dispositivo (41) realice las etapas indicadas en una cualquiera de las reivindicaciones 1-8 cuando los componentes ejecutables por ordenador se ejecutan en una unidad (43) de procesamiento incluida en el dispositivo.