Method and apparatus for automatically adapting a node in a network

• US 7,047,287 B2
• Filed: 05/18/2001
• Issued: 05/16/2006
• Est. Priority Date: 10/26/2000
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Chan, Desmond Cho-Hung, Sim, Siew Yong
• Primary Examiner(s): VU, VIET DUY
• Application Number:
  US09/681,672
• Publication Number:
  US 20020078174A1
• Time in Patent Office: 1,824 Days
• Field of Search: 709/201, 709/202, 709/223, 709/224, 709/252, 709/220, 709/221, 709/222
• US Class Current: 709/221
• 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 automatically adapting a node in a network comprising:

changing characteristics of a changed node in a network having a plurality of nodes;

sending a query automatically to each of said plurality of nodes, by said changed node, to determine what content said changed node should have;

receiving a reply to said query from each node of said plurality of nodes having content for said changed node, said reply comprising a list of contents to be learned by said changed node;

generating a list of contents to be deleted from said changed node using information in said list of contents to be learned;

generating a list of contents to be added to said changed node using information in said list of contents to be learned;

deleting from said changed node items in said list of contents to be deleted;

downloading each item from said list of contents to be added from said replying nodes having content for said changed node.

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

3. The method of claim 2, wherein said changing characteristics of said changed node comprises replacing said changed node'"'"'s old set of attributes with a new set of attributes.

4. The method of claim 3, wherein said plurality of nodes is arranged in the form of a virtual tree for passing control information.

5. The method of claim 4, wherein said query includes said new set of attributes and said old set of attributes of said changed node.

6. The method of claim 2, wherein said set of attributes comprises a bitmap and said set of rolled up attributes is a combination of the set of attributes 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 query automatically to said plurality of nodes comprises:

announcing said changed node'"'"'s new set of attributes by sending a notification to neighbor nodes;

forwarding said notification to nodes neighboring said neighbor nodes, said forwarding continuing until each node in said network receives said notification.

9. The method of claim 8, wherein said changed node does not receive said notification.

10. The method of claim 1, wherein said content is stored as block files in a plurality of storage devices in said replying nodes.

11. The method of claim 5, further comprising:

causing each node receiving said query to propagate said query to neighbor nodes such that every node in said network receives said query, said node receiving said query evaluating said old set of attributes and said new set of attributes of said changed node to determine a list of necessary content files for said changed node, and sending a reply directing said changed node to download items from said list of necessary content files.

12. The method of claim 11, wherein said items in said list of necessary content files are downloaded if they do not already exist in said changed node.

13. The method of claim 5, wherein said downloading comprises:

obtaining a file metadata for each content item in said list of contents to be added;

sending a request to determine nodes in said network having said content item, same portion of said content item being available in one or more of said plurality of nodes;

receiving responses from one or more responding nodes, wherein said responding nodes are nodes in said plurality of nodes that have said content item;

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

downloading said content item from said desired set of nodes onto said changed node, said content item comprising a plurality of block files; and

storing said plurality of block files in a distributed manner in a plurality of local storage devices of said changed node.

14. The method of claim 13, wherein said content item is downloaded if it does not already exist in said changed node.

15. The method of claim 13, wherein said desired set of nodes comprises nodes of said network with least congestion.

16. The method of claim 15, wherein said response specifies which portion of said content item said responding node has and performance characteristics of said responding node.

17. The method of claim 16, wherein said least congestion is determined from said performance characteristics.

18. The method of claim 17, wherein said downloading said content item is by parallel downloading of different block files from a plurality of said nodes with least congestion.

19. A method for automatically adapting a node in a network comprising:

replacing an old set of attributes with a new set of attributes of a changed node in a network having a plurality of nodes virtually arranged in the form of a tree for passing control information, each of said plurality of nodes having a set of attributes and a set of rolled up attributes;

said changed node sending a query automatically to its neighbor nodes, to determine what content said changed node should have, said neighbor nodes forwarding said query to their neighbor nodes until each node in said network receives said query;

receiving a reply to said query from each node of said plurality of nodes having content for said changed node, said reply including a list of contents to be learned by said changed node;

generating a list of contents to be deleted from said changed node using information in said list of contents to be learned, wherein said contents to be deleted comprises contents residing in said changed node and not in said list of contents to be learned;

generating a list of contents to be added to said changed node using information in said list of contents to be learned, wherein said contents to be added comprises contents in said list of contents to be learned not residing in said changed node;

deleting from said changed node items in said list of contents to be deleted;

downloading each item from said list of contents to be added from said replying nodes having content for said changed node, said item comprising a plurality of block files stored in a plurality of storage devices in said replying node.

20. A computer program product comprising:

a computer usable medium comprising computer readable code for automatically adapting a node in a network, said computer readable program code configured to;

change characteristics of a changed node in a network having a plurality of nodes;

send a query automatically to each of said plurality of nodes, by said changed node, to determine what content said changed node should have;

receive a reply to said query from each node of said plurality of nodes having content for said changed node, said reply including a list of contents to be learned by said changed node;

generate a list of contents to be deleted from said changed node using information in said list of contents to be learned;

generate a list of contents to be added to said changed node using information in said list of contents to be learned;

delete from said changed node items in said list of contents to be deleted;

download each item from said list of contents to be added from said replying nodes having content for said changed node.

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

22. The computer program product of claim 21, wherein said change characteristics of said changed node comprises replacing said changed node'"'"'s old set of attributes with a new set of attributes.

23. The computer program product of claim 22, wherein said plurality of nodes is arranged in the form of a virtual tree for passing control information.

24. The computer program product of claim 23, wherein said query includes said new set of attributes and said old set of attributes of said changed node.

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

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

27. The computer program product of claim 24, wherein said send a query automatically to said plurality of nodes comprises:

announcing said changed node'"'"'s new set of attributes by sending a notification to neighbor nodes;

forwarding said notification to nodes neighboring said neighbor nodes, said forwarding continuing until all nodes in said network receives said notification.

28. The computer program product of claim 27, wherein said changed node does not receive said notification.

29. The computer program product of claim 20, wherein said content is stored as block files in a plurality of storage devices in said replying nodes.

30. The computer program product of claim 24, further comprising computer readable program code configured to:

cause each node receiving said query to propagate said query to their neighbor nodes such that every node in said network receives said query, said node receiving said query evaluating said old set of attributes and said new set of attributes of said changed node to determine a list of necessary content files for said changed node, and sending a reply directing said changed node to download items from said list of necessary content files.

31. The computer program product of claim 30, wherein said items in said list of necessary content files are downloaded if they do not already exist in said changed node.

32. The computer program product of claim 24, wherein said download comprises:

obtain a file metadata for each content item in said list of contents to be added;

send a request to determine nodes in said network having said content item, same subset of said content item being available in one or more of said plurality of nodes;

receive responses from one or more responding nodes, wherein said responding nodes are nodes in said plurality of nodes that have said content item;

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

download said content item from said desired set of nodes onto said changed node, said content item comprising a plurality of block files; and

store said plurality of block files in a distributed manner in a plurality of local storage devices of said changed node.

33. The computer program product of claim 32, wherein said content item is downloaded if it does not already exist in said changed node.

34. The computer program product of claim 32, wherein said desired set of nodes comprises nodes of said network with least congestion.

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

36. The computer program product of claim 35, wherein said least congestion is determined from said performance characteristics.

37. The computer program product of claim 36, wherein said download said content item is by parallel downloading of different block files from a plurality of said nodes with least congestion.

38. An apparatus for automatically adapting a node in a network comprising:

a network having a plurality of nodes, each node having one or more servers;

a node in said network configured to become a changed node when characteristics change, said changed node sending a query automatically to each of said plurality of nodes to determine what content said changed node should have, said changed node receiving a reply to said query from each node of said plurality of nodes having content for said changed node, said reply including a list of contents to be learned by said changed node, said changed node generating a list of contents to be deleted and a list of contents to be added using information in said list of contents to be learned, said one or more servers in said changed node deleting items in said list of contents to be deleted, said one or more servers in said changed node downloading each item from said list of contents to be added from said replying nodes having content for said changed node.

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

40. The apparatus of claim 39, wherein said changed characteristics of said changed node comprises replacing said changed node'"'"'s old set of attributes with a new set of attributes.

41. The apparatus of claim 40, wherein said plurality of nodes is arranged in the form of a virtual tree for passing control information.

42. The apparatus of claim 41, wherein said query includes said new set of attributes and said old set of attributes of said changed node.

43. The apparatus of claim 39, wherein said set of attributes comprises a bitmap and said set of rolled up attributes is a combination of the set of attributes of lineal descendants of said node.

44. The apparatus of claim 43, wherein said combination is the binary OR of said lineal descendants of said node.

45. The apparatus of claim 42, wherein said sending a query automatically to said plurality of nodes comprises:

announcing said changed node'"'"'s new set of attributes by sending a notification to neighbor nodes;

forwarding said notification to nodes neighboring said neighbor nodes, said

forwarding continuing until each node in said network receives said notification.

46. The apparatus of claim 45, wherein said changed node does not receive said notification.

47. The apparatus of claim 38, further comprising a plurality of storage devices in each node and said content is stored as block files in said plurality of storage devices of said replying nodes.

48. The apparatus of claim 42, further comprising:

each of said plurality of nodes receiving said query to propagate said query to their neighbor nodes such that every node in said network receives said query, said node receiving said query evaluating said old set of attributes and said new set of attributes of said changed node to determine a list of necessary content files for said changed node, and sending a reply directing said changed node to download items from said list of necessary content files.

49. The apparatus of claim 48, wherein said items in said list of necessary content files are downloaded if they do not already exist in said changed node.

50. The apparatus of claim 42, wherein said downloading comprises:

a server in said one or more servers in said changed node obtaining a file metadata for each content item in said list of contents to be added;

said server sending a request to determine nodes in said network having said content item, same subset of said content item being available in one or more of said plurality of nodes;

said server receiving responses from one or more responding nodes, wherein said responding nodes are nodes in said plurality of nodes that have said content item;

said one or more servers of said changed node determining from said responses which of said responding nodes are a desired set of nodes to download said content item from;

said one or more servers of said changed node downloading said content item from said desired set of nodes onto said changed node, said content item comprising a plurality of block files; and

said one or more servers of said changed node storing said plurality of block files in a distributed manner in a plurality of local storage devices of said changed node.

51. The apparatus of claim 50, wherein said content item is downloaded if it does not already exist in said changed node.

52. The apparatus of claim 50, wherein said desired set of nodes comprises nodes of said network with least congestion.

53. The apparatus of claim 52, wherein said response specifies which portion of said content item said responding node has and performance characteristics of said responding node.

54. The apparatus of claim 53, wherein said least congestion is determined from said performance characteristics.

55. The apparatus of claim 54, wherein said downloading said content item is by parallel downloading of different block files from a plurality of said nodes with least congestion.