Un método y dispositivo para transferir datos en masa en redes tolerantes al retardo.

Un metodo para transferir datos en masa en redes tolerantes al retardo,

que comprende modelar una red tolerante al retardo como un grafo y gestionar la transferencia de datos en masa basandose en dicho grafo, en el que dicho modelado se realiza para transformar una red dinamica que comprende enlaces variables en el tiempo en un grafo de red expandido en el tiempo estatico caracterizado por que dicha red dinamica comprende al menos un nodo de origen (v1), un nodo de destino (v4), nodos intermedios (v2, v3) y arcos dirigidos que enlazan dichos nodos (v1, v2, v3, v4), comprendiendo el metodo generar dicho grafo de red expandido en el tiempo estatico creando:

T copias ( , J ) de cada uno de dichos nodos (v1, v2, v3, v4);

- T copias de cada uno de dichos arcos que conectan dichas T copias de nodos ( , J ) diferentes y consecutivas que no se refieren al mismo nodo, y asociando cada arco con una capacidad y/o coste , J , );

en el que cada una de dichas T copias corresponde a un intervalo de tiempo (t) del grafo de red expandido en el tiempo estatico.

Campo de la técnica

La presente invención se refiere en general, en un primer aspecto, a un método para transferir datos en masa en redes tolerantes al retardo, que comprende gestionar dicha transferencia de datos basándose en un grafo de red, y más particularmente a un método que comprende generar dicho grafo para modelar una red dinámica, en forma de un grafo expandido en el tiempo.

Un segundo aspecto de la invención se refiere a un dispositivo para transferir datos en masa en redes tolerantes al retardo con una unidad de planificador que implementa el método del primer aspecto.

Estado de la técnica anterior

En los últimos años, ha habido un interés renovado en el problema de transferir datos en masa (habitualmente terabytes) usando ISP comerciales. La necesidad de transferir datos en masa se debe a diversas aplicaciones científicas (como transferir terabytes de datos desde el colisionador de hadrones en CERN) y comerciales (como realizar copias de seguridad por centros de datos geográficamente distantes). La clave en este caso es que muchas de las aplicaciones que utilizarían datos en masa son tolerantes a los retardos. Así, los datos pueden transferirse a un coste mínimo mientras se utiliza un ancho de banda fuera de horas punta ya pagado que resulta de patrones de tráfico diurno usando almacenar y reenviar a través de nodos de almacenamiento intermedios.

La última década ha alterado fundamentalmente la forma de distribuir contenido y la forma de interactuar entre sí y consumir información. La llegada de los servicios P2P en la última década ha mostrado cómo distribuir contenido y permitir rápidamente servicios nuevos. La observación de que una gran cantidad de contenido multimedia descargado (o enviado por correo a través de un servicio de tipo Netflix) no se consume de inmediato, y así, es tolerante al retardo (DT, "delay-tolerant") ha abierto la posibilidad de ofrecer descargas en masa como un servicio que pueden ofrecer los ISP. Esto ha significado que los ISP han tenido que replantear sus redes más allá de meramente encaminar y reenviar paquetes. Los ISP pueden permitir una diversidad de servicios para una gama de aplicaciones que se aprovechan de las transferencias de datos en masa, tanto para consumidores como para negocios. En la actualidad, como ejemplo, Amazon proporciona un servicio (Amazon Import/Export [2]), que permite a un usuario transferir un gran volumen de datos por el país a través de la red Interna de Amazon (evitando así los elevados costes de tránsito en Internet). Claramente, existe una demanda de un servicio de este tipo. La popularidad de servicios como Netflix ha significado que como servicio de siguiente generación, las películas pueden estar disponibles para su descarga desde la cola de Netflix del usuario a una Xbox [14] o un dispositivo similar en lugar de a través de correo ordinario.

El caso para la transferencia en masa de datos tolerantes al retardo se realizó en una serie de dos artículos [9] [1]. El enfoque general de modelado de redes como grafos y resolver el problema de encaminamiento usando flujos se encuentra en mucha bibliografía [1], La programación lineal también es un campo muy estudiado con algoritmos de tiempo polinomial bien entendidos tales como el algoritmo elipse o los algoritmos de punto Interior [6] [14]. Tanto [13] como [8] son una fuente óptima de redes ópticas que incluyen enlaces semldúplex, y el área general de redes. El problema de los enlaces variables en el tiempo en el contexto de redes se estudió anteriormente, en el contexto de retardo [12] más que en el de rendimiento global. En [11], los autores estudian redes con enlaces que varían de manera estocástlca. En este trabajo, se trata de redes que tienen enlaces variables en el tiempo que tienen capacidades sobrantes determinísticas que se conocen de antemano (esto es una aproximación porque se conoce que el tráfico en los enlaces de red principal no fluctúa de manera apreclable de una semana a otra).

El documento de la técnica anterior "Optimal routing and schedullng for determlnlstlc delay tolerant networks", por David Hay et al, se refiere a un método para transferencia de datos en masa en redes tolerantes al retardo que incluye modelar una red tolerante al retardo como un grafo, gestionar la transferencia de datos en masa basándose en dicho grafo, estando dicho modelado realizado para transformar una red dinámica que comprende enlaces variables en el tiempo en un grafo de red expandida en el tiempo estática. Este documento de la técnica anterior supone que la red es determlnístlca, es decir, que el ancho de banda en cada enlace se conoce para todo el futuro, y supone además una única limitación de capacidad para cada enlace.

Los presentes inventores no conocen ninguna propuesta que estudie el Impacto de los costes de enlaces y/o almacenamiento en redes variables en el tiempo para el problema de la transferencia de datos en masa.

Descripción de la invención

Es necesario ofrecer una alternativa al estado de la técnica que cubra los vacíos encontrados en la misma, particularmente los relacionados con la falta de propuestas centradas en el problema de las redes variables en el tiempo para transferir datos en masa.

Para ello, la presente invención se refiere a un método para transferir datos en masa en redes tolerantes al retardo, que comprende modelar una red tolerante al retardo como un grafo y gestionar la transferencia de datos en masa basándose en dicho grafo.

A diferencia de las propuestas conocidas, según el método del primer aspecto de la invención, dicho modelado de red se realiza para transformar una red dinámica que comprende enlaces variables en el tiempo en un grafo de red expandido en el tiempo estático.

Otras realizaciones del método del primer aspecto de la invención se describen con referencia a las reivindicaciones 2 a 13 adjuntas, y en una sección posterior relacionada con la descripción detallada de varias realizaciones, en la que se describen técnicas para transformar cualquier red dinámica en una red expandida en el tiempo estática.

El método de la invención se ocupa del problema de representar de manera eficaz el almacenamiento en gratos expandidos en el tiempo. La clave en este caso es que como el caso de las curvas espacio-tiempo [3], el grafo expandido en el tiempo es una representación en espacio-tiempo de un objeto espacial (el grafo). Esto permite representar los nodos de almacenamiento en el grafo expandido en el tiempo estático de la red dinámica original.

Un segundo aspecto de la invención se refiere a un dispositivo para transferir datos en masa en redes tolerantes al retardo, que comprende una unidad de planificador con capacidades de procesamiento.

La unidad de planificador del dispositivo del segundo aspecto de la invención implementa un algoritmo que procesa costes de arco (es decir, coste para atravesar un enlace) y costes de almacenamiento según el método de la reivindicación 5 o la reivindicación 13 para hallar un plan óptimo para transferir datos en masa.

Para una realización, el dispositivo es un encaminador o un dispositivo asociado con un encaminador, que puede usar el grafo expandido en el tiempo para planificar datos entre encaminadores (a través de ISP o a través de PoP y dentro del mismo PoP).

Breve descripción de los dibujos

Las ventajas y características anteriores y otras se entenderán mejor a partir de la siguiente descripción detallada de realizaciones, con referencia a los dibujos adjuntos, que deben considerarse de manera ilustrativa y no limitativa, en los que:

la figura 1 muestra esquemáticamente, en forma de grafo convencional, una topología de red con un nodo de origen y un nodo sumidero interconectados a través de nodos intermedios;

la figura 2 muestra un grafo expandido en el tiempo obtenido a partir del grafo de la figura 1 mediante el método del primer aspecto de la invención, para una realización relacionada con una red con costes de enlace y capacidades de enlace variables en el tiempo;

la figura 3 muestra enlaces semidúplex y sus transformaciones (vista a la derecha) realizadas según una realización del método del primer aspecto de la invención;

la figura 4 muestra esquemáticamente una realización del método del primer aspecto de la invención en relación con la forma en que las limitaciones de nodo de la red dinámica se representan en el grafo expandido en el tiempo;

la figura 5 muestra el grafo expandido en el tiempo de la figura 2 con la inclusión de información relativa a nodos de almacenamiento con almacenamiento infinito y coste cero;

la figura 6 difiere de la figura 5 en que los nodos de almacenamiento tienen costes y capacidades... [Seguir leyendo]

1. Un método para transferir datos en masa en redes tolerantes al retardo, que comprende modelar una red tolerante al retardo como un grato y gestionar la transferencia de datos en masa basándose en dicho grato, en el que dicho modelado se realiza para transformar una red dinámica que comprende enlaces variables en el tiempo en un grato de red expandido en el tiempo estático caracterizado porque dicha red dinámica comprende al menos un nodo de origen (vi), un nodo de destino (v4), nodos intermedios (v2, v3) y arcos dirigidos que enlazan dichos nodos (v-i, v2, v3, v4), comprendiendo el método generar dicho grato de red expandido en el tiempo estático creando:

lili TTTT

T copias (Tí , ví,vj,v4... vlJv2,vJív4 ) de cada uno de dichos nodos (v-i, v2, v3, v4);

- T copias de cada uno de dichos arcos que conectan dichas T copias de nodos (vi , v2jv3jv4... TTTT

vl'v2'v3'v4 ) diferentes y consecutivas que no se refieren al mismo nodo, y asociando cada arco con una

, l 111 1 T-l T-l T-l T-l T-1

capacidad y/o coste lcn, ciucn> c24> c34... cn , cu ,cit ,c24 1 c34 );

en el que cada una de dichas T copias corresponde a un intervalo de tiempo (t) del grato de red expandido en el tiempo estático.

2. Un método según la reivindicación 1, que comprende además representar nodos de almacenamiento, incluyendo su capacidad de almacenamiento, en dicho grato de red expandido en el tiempo estático.

3. Un método según la reivindicación 1 o 2, en el que dichas capacidades disponibles respecto a enlaces variables en el tiempo son determinísticas y se conocen de antemano a partir de datos históricos recientes de utilización de enlaces.

4. Un método según cualquiera de las reivindicaciones anteriores, que comprende usar dicho grato de red expandido en el tiempo estático para planificar dicha transferencia de datos en masa entre nodos.

5. Un método según la reivindicación 4, en el que dicha red dinámica incluye costes variables en el tiempo asociados con dichos enlaces variables en el tiempo, comprendiendo el método hallar un plan óptimo para dicha transferencia de datos en masa resolviendo un problema de flujo de coste mínimo en el grafo de red expandido en el tiempo estático.

6. Un método según la reivindicación 5 cuando depende de la reivindicación 2, en el que dicha red dinámica incluye costes variables en el tiempo asociados al almacenamiento en dichos nodos de almacenamiento.

7. Un método según la reivindicación 1, en el que cuando dicha red dinámica incluye enlaces semidúplex, el método comprende representar cada enlace entre dos nodos (v¡, v¡) mediante dos arcos con respectivas capacidades

(rí1, rii ) que se suman para dar una constante (r1).

8. Un método según la reivindicación 1, en el que cuando dicha red dinámica incluye un nodo limitado (ví), el método comprende representar un nodo de este tipo para cada intervalo de tiempo t, como un nodo de entrada (v¡`) y un nodo de salida (v¡) enlazados mediante un arco con limitación de capacidad (r¡*) y/o limitación de coste (c¡) asociadas, en el que todos los arcos entrantes originales se conectan con dicho nodo de entrada (v¡`) y todos los arcos salientes originales se conectan con dicho nodo de salida (v2*).

9. Un método según la reivindicación 1 que comprende representar nodos de almacenamiento en dicho grafo de red expandido en el tiempo estático con su capacidad de almacenamiento, conectando, a través de arcos respectivos,

dichas T copias de nodos (ví , vl>v£> v4... vÍjvIi'v3i VJ) diferentes y consecutivas que se refieren al mismo nodo en intervalos de tiempo (t) diferentes, y asociar cada arco con una capacidad de almacenamiento (r¡`) y un coste de almacenamiento (p¡`).

1. Un método según la reivindicación 9, en el que dicha capacidad de almacenamiento (r¡*) es infinita y dicho coste de almacenamiento (p*) es cero.

11. Un método según la reivindicación 9 cuando depende de la reivindicación 5, en el que dicha capacidad de almacenamiento (r¡) y dicho coste de almacenamiento (p¡`) son variables en el tiempo.

12. Un método según la reivindicación 11, que comprende hallar dicho plan óptimo resolviendo dicho problema de flujo de coste mínimo teniendo en cuenta ambos costes: el asociado con los arcos (c¡j*) para atravesar el enlace y el coste asociado con el almacenamiento (p¡`).

13. Un dispositivo para transferir datos en masa en redes tolerantes al retardo, que comprende una unidad de planificador con capacidades de procesamiento, en el que el dispositivo está caracterizado por que dicha unidad de planificador implementa un algoritmo que procesa costes de arco (cy*) y costes de almacenamiento (p¡*) según el

método según la reivindicación 5 o la reivindicación 12 para hallar un plan óptimo para transferir datos en masa.

14. Un dispositivo según la reivindicación 13, en el que dicha unidad de planificador es un encaminador o un dispositivo asociado con un encaminador.