Accelerated large data distribution in overlay networks

• US 20050015511A1
• Filed: 12/31/2003
• Published: 01/20/2005
• Est. Priority Date: 07/02/2003
• Status: Abandoned Application

• Current Assignee: NEC Laboratories America Inc (NEC Corporation)
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Varsou, Aikaterini, Ganguly, Samrat, Izmailov, Rauf, Tu, Nan
• Application Number:
  US10/749,947
• Publication Number:
  US 20050015511A1
• Time in Patent Office: Days
• US Class Current: 709/238
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/484 using multiple routing trees
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 69/14 Multichannel or multilink protocols
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

A Method and apparatus for dynamically discovering and utilizing unused resources for practical and efficient creation of optimized network mechanisms for data distribution. Proposed techniques for data distribution, assembly, routing and scheduling in broadband networks can be implemented as content-level server platform architecture enabled by application-level control plane. Such a platform accelerates content transfer, mirroring and replication. It applies coordinated data partitioning and resource discovery and sharing of information replication by multiple network systems. Furthermore, it harvests the unutilized bandwidth in the network by disassembling the large content to be distributed into different components. These components are then routed in spatially and temporally diverse routes through multiple paths and trees and assembled at the destination nodes. The result is accelerated content distribution, added security, scalability and robustness. No modifications of existing network communication protocols is required.

Claims

1. A method for distributing data between a source and destination in a network, the method comprising the steps of:

defining, n number of paths between the source and the destination;

splitting the data into n number of blocks independently transmitting the n blocks from the source to the destination; and

reassembling, at the destination, the n blocks into the data.

2. The method according to claim 1 wherein the independent transmission of the n blocks is not started simultaneously.

3. The method according to claim 1 wherein the size of the n blocks remains constant for the duration of the transmission.

4. The method according to claim 1 wherein the size of the n blocks varies during the duration of the transmission.

5. The method according to claim 1 wherein the n number of paths is determined using multicast, depth-first-search technique.

6. The method according to claim 1 wherein the n number of paths is determined using multicast spanning tree technique.

7. The method according to claim 1 wherein the n number of paths is determined using multicast arborescence technique.

8. The method according to claim 1 further comprising the step of:

receiving, at the source, a request for a data transfer to the destination.

9. A method of file transfer in a computer-based communication network by utilizing an overlay network composed of cooperating servers on computer hosts, said computer hosts connected to said communication network, wherein each said server contains instructions which, when executed by said server, cause said server to process and forward data via the transport layer to other servers on said overlay network without modifying the native data transport protocol at transport or lower layers, said method comprising the steps of:

defining a first data forwarding path between two servers, said path comprising of concatenation of overlay links, each of said links established via transport layer between two said servers in said overlay network;

defining a second data forwarding path between two servers, said path different from the first data forwarding path;

dividing the data file in at least two sub-files, first sub-file and second sub-file; and

sending first and second sub-files over the first and second data forwarding paths, respectively.

10. The method according to claim 9 further comprising the steps of:

replicating each sub-file in one or more intermediate servers on said data forwarding paths and forwarding the sub-file to the next server in the path; and

assembling the first and the second sub-files at the second server.

11. The method of claim 9, wherein said sending first and second sub-files over the first and second data forwarding paths are not started simultaneously.

12. The method of claim 10, wherein said sub-files are transmitted from a single source node to a plurality of destination nodes, and said paths form a data forwarding tree, wherein the intermediate nodes of the tree copy the sub-files reaching them from the incoming overlay link to the plurality of outgoing overlay links.

13. The method of claim 9, wherein said sub-files are transmitted from a plurality of source nodes to a plurality of destination nodes, and said forwarding paths form data forwarding trees, wherein the intermediate nodes of the tree copy the data reaching them from the incoming link to the plurality of outgoing links.

14. The method of claim 9, wherein the data forwarding and processing resources are reserved, said resources including one or more metrics from the following group:

bandwidth of overlay link, processing load of the server.

15. The method of claim 9, wherein the data forwarding and processing resources are determined from network monitoring, said resources including one or more metrics from the following group:

bandwidth of overlay link, processing load of the server.

16. The method of claim 9, wherein the said overlay network has static topology and resources, said resources including one or more metrics from the following group:

bandwidth, processing load.

17. The method of claim 9, wherein the said overlay network has dynamic topology and resources, said resources including one or more metrics from the following group:

bandwidth, processing load.

18. The method of claim 9, wherein the data forwarding paths are computed in a single server.

19. The method of claim 9, wherein the data forwarding paths are computed in several servers, with subsequent coordination of computed results.

20. The method of claim 9, wherein the divisions of the data file into sub-files remain constant for the duration of the file transfer.

21. The method of claim 9, wherein the divisions of the data file into sub-files change during the file transfer.

22. The method of claim 11, wherein the data forwarding tree is constructed using multicast depth-first-search method.

23. The method of claim 11, wherein the data forwarding tree is constructed using multicast spanning tree method.

24. The method of claim 11, wherein the data forwarding tree is constructed using multicast arborescence method.

25. The method of claim 9, wherein the established communications protocols include one or more protocols selected from the following group:

Internet Protocol, http, ftp SSL, TCP reliable UDP using erasure coding.

26. The method of assembly of claim 12, wherein the assembly is done at overlay network layer, said method comprising the steps of:

encoding a monotonically increased sequence number in each packet header at data source.

queuing data packet in a sink buffer in destination for each data transport session.

scanning a sink buffer and selecting a data packet that matches the current receiving sequence number maintained at the destination.

clocking out available data packets in the sink buffer selected by step c);

increasing the receiving sequence number at the destination.

delivering the available data packet to the application client; and

repeating the method for all sink buffers.

27. The method of assembly of claim 12, wherein the assembly is done at the overlay application layer by the application, said method comprising the steps of:

encoding an application-specific data object identifier into a data frame;

extracting the application-specific data object identifier at the destination; and

reassembling the application data object according to the data object identifier.

28. The method of data transfer of claim 9, said method comprising the steps of:

using an explicit or implicit method to setup the forwarding table in each overlay node;

forwarding the data by looking up the forwarding table installed by step a) at each node;

scheduling data transport at the data source and at each intermediate node for each path or tree according to their QoS specifications; and

slowing down a particular data flow on a path or tree by using backpressure.

29. The method of claim 9, wherein the transport of data partitions to a plurality of destination nodes is a combined coordination of transport initiated by the sender (push) and transport initiated by the receivers (pull).

30. An overlay network apparatus for determining optimized paths and trees for transmitting data from a source to destinations within a computer-based communications network, the communications network being characterized by one or more established communications protocols, the apparatus comprising:

a set of one or more intermediate nodes, the intermediate nodes being operable to transmit and receive data in conformance with the established communications protocols;

path and trees discovery means, responsive to a request for transmitting data from the sources to the destinations, operable to discover network resources on virtual links between the sources and the destinations passing through one or more of the intermediate nodes, the paths being derived by means of one or more existing routing mechanisms of the communications network, wherein the intermediate nodes define a virtual topology on top of the computer-based communications network;

data processing means for data partitioning, storage and replication at the nodes; and

forwarding means for forwarding the data from the sources to the destinations by way of paths and trees, without requiring a modification of the established communications protocols.