Method and apparatus for minimizing network congestion during large payload delivery

• US 7,177,270 B2
• Filed: 05/18/2001
• Issued: 02/13/2007
• Est. Priority Date: 10/26/2000
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Sim, Siew Yong, Chan, Desmond Cho-Hung
• Primary Examiner(s): Ferris; Derrick W.
• Application Number:
  US09/681,668
• Publication Number:
  US 20020083187A1
• Time in Patent Office: 2,097 Days
• Field of Search: 709/231, 370/254, 370/229
• US Class Current: 370/229
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/188 Virtual file systems
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/1017 based on a round robin mechanism
• CPC Class Codes: H04L 67/1019 Random or heuristic server selection
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/1027 Persistence of sessions during load balancing
• CPC Class Codes: H04L 67/1034 Reaction to server failures by a load balancer
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• 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

Large payload files are selectively partitioned in blocks and the blocks distributed to a plurality of distribution stations at the edge of the network qualified to have the data. Each qualified station decides how much and what portion of the content to save locally, based on information such as network location and environment, usage, popularity, and other distribution criteria defined by the content provider. Different pieces of a large payload file may be available from different nodes, however, when a user requests access to the large payload file, for example, through an application server, a virtual file control system creates an illusion that the entire file is present at the connected node. However, since only selective portions of the large payload file may actually be resident at that node'"'"'s storage at the time of request, a cluster of distribution servers at the distribution station may download the non-resident portions of the file as the application server is servicing the user. The download may be in parallel and usually from the least congested nodes. New nodes added to the network learn from other nodes in the network what content they should have and download the required content, in a desired amount, onto their local storage devices from the nearest and least congested nodes without interrupting network operation. Each node manages its local storage and decides what content to prune based on information such as usage patterns.

Claims

1. A method for minimizing network congestion during large payload delivery comprising:

sending a search request to determine which nodes in a network have content for a requesting node, said network having a plurality of nodes arranged in the form of a virtual tree for passing control information, wherein each node in the virtual tree stores a portion of the content and is configured to appear as if all of the content is stored locally at the node;

receiving a response to said search request from each of one or more responding nodes having said content;

determining from said response which of said responding nodes are a desired set of nodes to download said content from;

downloading said content from said desired set of nodes; and

storing said downloaded content onto said requesting node.

2. The method of claim 1, wherein at least a portion of said content is stored in a plurality of block files in each of said responding nodes.

3. The method of claim 2, wherein more than one of said responding nodes maintain overlapping subset of block files stored in a plurality of local storage devices.

4. The method of claim 2, wherein said downloading of said block files occurs in parallel from said desired set of nodes.

5. The method of claim 1, wherein each node of said plurality of nodes has a set of attributes and a set of rolled up attributes for identification.

6. The method of claim 5, wherein said set of attributes comprises a bitmap and said set of rolled up attributes is a combination of all lineal descendants of said node.

7. The method of claim 6, wherein said combination is the binary OR of said all lineal descendants of said node.

8. The method of claim 5, wherein said sending a search request comprises said requesting node sending a notification to neighbor nodes in said virtual tree to determine the existence of said content, said notification comprising distribution criteria of said content.

9. The method of claim 8, wherein each of said neighbor nodes receiving said search request forwards said search request to nodes that are neighboring said neighbor nodes, excepting said requesting node, wherein said search request is propagated to one or more nodes of said plurality of nodes in said network that satisfy said distribution criteria.

10. The method of claim 1, wherein said response specifies which portion of said content said responding node has and performance characteristics of said responding node.

11. The method of claim 10, wherein said desired set of nodes comprises nodes in close proximity to said requesting node, said desired set of nodes comprising nodes identified as least congested as determined by said performance characteristics.

12. The method of claim 11, wherein said nodes in close proximity comprise nodes having the least latency.

13. A method for minimizing network congestion during large payload delivery comprising:

sending a search request to determine which nodes in a network have content for a requesting node, said network having a plurality of nodes arranged in the form of a virtual tree, wherein each node in the virtual tree stores a portion of the content and is configured to appear as if all of the content is stored locally at the node;

receiving responses to said search request from a plurality of responding nodes having said content, wherein at least a portion of said content is stored in a plurality of block files in each of said plurality of responding nodes, said responses identifying portions of said content in said plurality of responding nodes and performance characteristics of said responding nodes;

determining from said response which nodes of said plurality of responding nodes are a desired set of nodes to download said content from, wherein said desired set of nodes have a threshold level of latency to said requesting node and are identified as least congested nodes as determined by said performance characteristics;

downloading and storing said content from said desired set of nodes onto said requesting node.

14. A method for minimizing network congestion during large payload delivery comprising:

sending a search request to determine which nodes in a network have content for a requesting node, said network having a plurality of nodes arranged in the form of a virtual tree, wherein each node in the virtual tree stores a portion of the content and is configured to appear as if all of the content is stored locally at the node;

receiving a response to said search request from a plurality of responding having said content, wherein at least some portion of said content is stored in a plurality of block files in a plurality of storage devices in each of said responding nodes, said response identifies a portion of said content a responding node has and performance characteristics of said responding node, at least one of said plurality of responding nodes having the same portion of said content;

determining from said response which of said responding nodes are a desired set of nodes to download said content from, wherein said desired set of nodes are those nodes nearest to said requesting node in said network that are least congested as determined by said performance characteristics;

downloading said content in parallel from said desired set of nodes and storing said content in said requesting node.

15. A computer program product comprising:

a computer usable medium comprising computer readable code for minimizing network congestion during large payload delivery, said computer readable program code configured to;

send a search request to determine which nodes in a network have content for a requesting node, said network having a plurality of nodes arranged in the form of a virtual tree, wherein each node in the virtual tree stores a portion of the content and is configured to appear as if all of the content is stored locally at the node;

receive a response to said search request from each of one or more responding nodes having said content;

determine from said response which of said responding nodes are a desired set of nodes to download said content from;

download said content from said desired set of nodes; and

store said downloaded content onto said requesting node.

16. The computer program product of claim 15, wherein at least a portion of said content is stored in a plurality of block files in each of said responding nodes.

17. The computer program product of claim 16, wherein more than one of said responding nodes maintain overlapping subset of block files stored in a plurality of local storage devices.

18. The computer program product of claim 16, wherein said download of said block files occurs in parallel from said desired set of nodes.

19. The computer program product of claim 15, wherein each node of said plurality of nodes has a set of attributes and a set of rolled up attributes for identification.

20. The computer program product of claim 19, wherein said set of attributes comprises a bitmap and said set of rolled up attributes is a combination of all lineal descendants of said node.

21. The computer program product of claim 20, wherein said combination is the binary OR of said all lineal descendants of said node.

22. The computer program product of claim 19, wherein said send a search request comprises said requesting node sending a notification to neighbor nodes in said virtual tree to determine the existence of said content, said notification comprising distribution criteria of said content.

23. The computer program product of claim 22, wherein each of said neighbor nodes receiving said search request forwards said search request to nodes that are neighboring said neighbor nodes, excepting said requesting node, wherein said search request is propagated to one or more nodes of said plurality of nodes in said network that satisfy said distribution criteria.

24. The computer program product of claim 15, wherein said response specifies which portion of said content said responding node has and performance characteristics of said responding node.

25. The computer program product of claim 24, wherein said desired set of nodes comprises nodes in close proximity to said requesting node, said desired set of nodes comprising nodes identified as least congested as determined by said performance characteristics.

26. The computer program product of claim 25, wherein said nodes in close proximity comprise nodes having least latency.

27. An apparatus for minimizing network congestion during large payload delivery comprising:

a network comprising a plurality of nodes arranged in the form of a virtual tree, wherein each node in the virtual tree stores a portion of the content and is configured to appear as if all of the content is stored locally at the node;

a first server in a first server cluster sending a search request to determine which nodes in said network have content for a requesting node of said network, said first server cluster having one or more first servers, said first server receiving a response to said search request from each of one or more responding nodes having said content, said first server cluster determining said response which of said responding nodes are a desired set of nodes to download said content from, and said one or more first servers in said first server cluster downloading said content from said desired set of nodes and storing said downloaded content onto said requesting node.

28. The apparatus of claim 27, wherein at least a portion of said content is stored in a plurality of block files in each of said responding nodes.

29. The apparatus of claim 28, wherein more than one of said responding nodes maintain overlapping subset of block files stored in a plurality of local storage devices.

30. The apparatus of claim 28, wherein said downloading of said block files occurs in parallel from said desired set of nodes.

31. The apparatus of claim 27, wherein each node of said plurality of nodes has a set of attributes and a set of rolled up attributes for identification.

32. The apparatus of claim 31, wherein said set of attributes comprises a bitmap and said set of rolled up attributes is a combination of all lineal descendants of said node.

33. The apparatus of claim 32, wherein said combination is the binary OR of said all lineal descendants of said node.

34. The apparatus of claim 31, wherein said sending a search request comprises said first server in said requesting node sending a notification to neighbor nodes in said virtual tree to determine the existence of said content, said notification comprising distribution criteria of said content.

35. The apparatus of claim 34, wherein a first server in each of said neighbor nodes receiving said search request forwards said search request to nodes that are neighboring said neighbor nodes, excepting said requesting node, wherein said search request is propagated to one or more nodes of said plurality of nodes in said network that satisfy said distribution criteria.

36. The apparatus of claim 27, wherein said response specifies which portion of said content said responding node has and performance characteristics of said responding node.

37. The apparatus of claim 36, wherein said desired set of nodes comprises nodes in close proximity to said requesting node, said desired set of nodes comprising nodes identified as least congested as determined by said performance characteristics.

38. The apparatus of claim 37, wherein said nodes in close proximity comprise nodes having the least latency.