Hardware independent hierarchical cluster of heterogeneous media servers using a hierarchical command beat protocol to synchronize distributed parallel computing systems and employing a virtual dynamic network topology for distributed parallel computing system

• US 7,287,180 B1
• Filed: 03/19/2004
• Issued: 10/23/2007
• Est. Priority Date: 03/20/2003
• Status: Active Grant

• Current Assignee: InfoValue Computing, Inc.
• Original Assignee: InfoValue Computing, Inc.
• Inventors: Chen, Monsong, Chen, Alex, Pappu, Aparna, Mukherjee, Bodhi
• Primary Examiner(s): Bonzo; Bryce P.
• Assistant Examiner(s): Manoskey; Joseph D
• Application Number:
  US10/804,657
• Time in Patent Office: 1,313 Days
• Field of Search: 714/4, 714/5, 714/11, 714/12, 714/13, 714/43
• US Class Current: 714/4.3
• CPC Class Codes: G06F 11/1425 by reconfiguration of node membership
• CPC Class Codes: G06F 11/1482 by means of middleware or OS functionality
• CPC Class Codes: G06F 11/2033 switching over of hardware resources
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 15/16 Combinations of two or more digital computers each having at least an arithmetic unit, a program unit and a register, e.g. for a simultaneous processing of several programs coordinating program control therefor G06F9/52; in regulating and control system G05B
• CPC Class Codes: H04L 41/0677 Localisation of faults
• CPC Class Codes: H04L 41/08 Configuration management of networks or network elements address allocation H04L61/50
• CPC Class Codes: H04L 41/082 the condition being updates or upgrades of network functionality
• CPC Class Codes: H04L 41/0843 based on generic templates
• CPC Class Codes: H04L 41/0869 Validating the configuration within one network element
• CPC Class Codes: H04L 41/122 of virtualised topologies, e.g. software-defined networks [SDN] or network function virtualisation [NFV]
• CPC Class Codes: H04L 41/5022 by giving priorities, e.g. assigning classes of service
• CPC Class Codes: H04L 43/0817 by checking functioning
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46

Abstract

A video distribution system is implemented on a hierarchical parallel processing system that has clusters that are automatically formed from nodes of computer processing systems. Each cluster has a cluster supervising processor or group leader system that controls cluster configuration, fault detection and isolation, and data distribution. The group leader is determined according to a priority determined during the configuring of the hierarchical parallel processing system. The clusters are able to be reconfigured to allow removal and addition of nodes without impact on operation of the parallel processor system. The cluster provide a node status or heartbeat message that which provides detection and isolation of failure of nodes and disk storage devices within a cluster. The nodes within the cluster are able to join or leave a cluster and not affect performance.

Claims

1. A hierarchical clustered parallel processing system comprising:

a plurality of cluster nodes, each cluster node comprising at least one computer system cluster, each computer system cluster comprising at least one computer processing system;

a physical network connected to allow any of said computer processing systems incorporated within said plurality of cluster nodes to communicate with any other of said computer processing systems within said cluster nodes and connected to allow communication between each cluster node;

a plurality of virtual networks, each virtual network comprising a plurality of said computer processing systems, wherein each computer processing system includes at least one neighbor'"'"'s listing, each neighbor'"'"'s listing defining said computer processing system as a member of one of said plurality of said virtual networks and virtually connected through a virtual multicast bus to other member computer processing systems of said virtual network to allow direct and shared communication with the member processors; and

a configuration service apparatus in communication with each of said computer processing systems to provide each of said plurality of computer processing systems with;

a neighbor'"'"'s listing for each of said plurality of virtual networks that each of said plurality of computer systems is a member computer system;

a node identification to identify one cluster node that each member computer processing system is a member computer processing system,

a multicast bus address to broadcast communications to said member computer processing systems of said hierarchical cluster by way of said virtual networks to which said member computer processing systems, and

a cluster node priority list designating a priority for each cluster node within said hierarchical cluster; and

a cluster supervising processor to provide operational control services for each of said cluster nodes, said cluster supervising processor being selected of said member computer processing systems of each of said cluster nodes according to the priority from said priority list.

2. The hierarchical clustered parallel processing system of claim 1 wherein the configuration service apparatus further provides a disk access list.

3. The configuration service apparatus of claim 2 wherein the disk access list comprises identification of accessible disks, disk mount points, and failure detection locations.

4. The hierarchical clustered parallel processing system of claim 1 wherein the cluster supervising processor maintains:

a cluster topology table detailing connectivity for each computer processing system of the cluster node and a disk access status for each disk within said cluster node;

a disk usage table describing current capacity and loading for each disk within said cluster node;

a node usage table describing a streaming capacity for each computer processing system of said cluster and a current loading for each computer processing system of said cluster; and

a cluster map describing network addresses for each of a plurality of servers in communication with said cluster node and listing of computer processing systems within said cluster, network addresses for said computer processing systems, and an operational status of said computer processing systems.

5. The hierarchical clustered parallel processing system of claim 4 wherein the each cluster node of computer processing systems further comprises a fault detection apparatus within each member computer processing system:

to periodically receive a first processor status message from a first adjacent node;

to append a second processor status message of a current node to said first processor status message; and

to periodically transmit said first and second processor status message to a second adjacent node.

6. The hierarchical clustered parallel processing system of claim 5 wherein said cluster supervising processor receives an accumulation of the processor status messages from all cluster nodes.

7. The hierarchical clustered parallel processing system of claim 5 wherein, if the fault detection apparatus does not receive said first processor status message for a number of periods, said first adjacent node is declared to have failed and a failure declaration is appended to said second processor status message.

8. The hierarchical clustered parallel processing system of claim 7 wherein, upon receipt of said failure declaration, the cluster supervising processor modifies said cluster map to reflect failure of the cluster node.

9. The hierarchical clustered parallel processing system of claim 4 wherein the cluster supervising processor periodically posts a supervisor notification message on said virtual multicast bus, said supervisor notification message comprises a node identification and a network address for said cluster supervising processor.

10. The hierarchical clustered parallel processing system of claim 9 wherein the supervisor notification message further comprises the cluster topology and a current cluster map.

11. The hierarchical clustered parallel processing system of claim 9 wherein, if one cluster node does not receive said supervisor notification message within a notification time, said node becomes said cluster supervising processor, updates said cluster topology table and said cluster map, transmits a cluster supervising processor update message, and the supervisor notification message.

12. The hierarchical clustered parallel processing system of claim 9 wherein a new cluster node joins said virtual network by the steps of:

listening to said virtual multicast bus for a supervisor notification message from the present cluster supervising processor;

posting on said virtual multicast bus a join request message providing a node identification, a network address for said node, and a disk access list for said cluster node;

updating by the present cluster supervising processor the cluster map and the cluster topology; and

placing a new supervisor notification message upon said virtual multicast bus including said new cluster node.

13. The hierarchical clustered parallel processing system of claim 12 wherein the new cluster node joins said virtual network further by the step of:

ceasing posting on said virtual multicast bus said join request message.

14. The hierarchical clustered parallel processing system of claim 12 wherein the new cluster node becomes the cluster supervising processor, if said new cluster node has a priority that supercedes said present cluster supervising processor.

15. The hierarchical clustered parallel processing system of claim 14 wherein the new cluster node acting as the present cluster supervising processor transmits the supervisor notification message and the original cluster supervising processor ceases transmitting said supervisor notification message.

16. The hierarchical clustered parallel processing system of claim 15 wherein if the new cluster node does not transmit the supervisor notification message by the notification time, the original cluster supervising processor resumes transmission of the supervisor notification message.

17. The hierarchical clustered parallel processing system of claim 9 wherein one cluster node leaves one virtual network by the steps of:

posting a leave message on said virtual multicast bus, said leave message containing the node identification and the network address for said cluster node;

updating by the cluster supervising processor of the cluster map and the cluster topology; and

posting on the virtual multicast bus the supervisor notification message with the updated cluster map and cluster topology.

18. The hierarchical clustered parallel processing system of claim 17 wherein the node leaving the virtual network ceases posting the leave message upon receipt of the supervisor notification message with the updated cluster map and cluster topology.

19. The hierarchical clustered parallel processing system of claim 17 wherein if the cluster node leaving the virtual network is the cluster supervising processor, the cluster node with the highest priority on the priority list then becomes the cluster supervising processor.

20. The hierarchical clustered parallel processing system of claim 4 wherein:

each cluster node periodically determines whether each disk to which said cluster node has access is functioning and if any disk is not functioning;

the cluster node creates a disk failure message for the disk not functioning for transfer to an adjacent cluster node;

wherein said adjacent cluster node transfers said disk failure message to subsequent adjacent cluster nodes until said cluster supervising processor receives said disk failure message;

wherein upon receipt of multiple disk failure messages from multiple cluster nodes for the disk not functioning, the cluster supervising processor declares a disk failure, updates the disk usage table, and reassigns all the transfer of data files from a failing node to an active node.

21. The hierarchical clustered parallel processing system of claim 1 wherein a group of said member computer processing systems of said cluster nodes are configured as a sub-cluster, said sub-cluster being a sub-node of said virtual network.

22. The hierarchical clustered parallel processing system of claim 1 wherein said virtual network is formed and said cluster supervising processor is designated by the steps of:

listening to said virtual multicast bus for a supervisor notification message from the cluster supervising processor by each cluster node of the virtual network;

if no supervisor notification message is received, designating each cluster node a single node virtual network of its own;

designating each cluster node the cluster supervising processor of its single node virtual network;

transmitting by each cluster supervising processor of each single node virtual network the supervisor notification message for each single node cluster;

ceasing by those cluster nodes having a lower priority from transmitting supervisor notification messages such that the cluster node with a highest priority is the cluster supervising processor; and

joining said virtual network by those nodes with lower priority by posting on said virtual multicast bus a join request message providing a node identification, a network address for said cluster node, and a disk access list for said cluster node.

23. A virtual network formed within a plurality of clusters of computer processing systems interconnected by a physical network to allow each computer processing system of the clusters of computer processing systems to transfer data between any of the plurality of computer processing systems, said virtual network comprising:

a plurality of nodes, each node comprising at least one computer system cluster designated to be a member of said virtual network, each computer system cluster comprising at least one of said computer processing systems;

a virtual multicast bus to provide communication between member nodes of said virtual network; and

a configuration service apparatus in communication with each of the computer systems to provide each of the plurality of computer systems with;

a neighbor'"'"'s listing for each of said computer processing systems included in a member node of said virtual network, a separate neighbor'"'"'s listing associated with any virtual network included within said a plurality of clusters;

a node identification to identify a node for each member computer processing system within said cluster,

a multicast bus address to broadcast communications to said member nodes of said virtual network by way of said virtual multicast bus, and

a node priority list designating a priority for each member node within said virtual network; and

a cluster supervising processor to provide operational control services for each of said member nodes, said cluster supervising processor being selected of said computer systems within said nodes according to the priority from said priority list.

24. The virtual network of claim 23 wherein the configuration service apparatus further provides a disk access list.

25. The virtual network of claim 24 wherein the disk access list comprises identification of accessible disks, disk mount points, and failure detection locations.

26. The virtual network of claim 23 wherein the cluster supervising processor maintains:

a cluster topology table detailing connectivity for each node of the virtual network and a disk access status for each disk within said virtual network;

a disk usage table describing current capacity and loading for each disk within said virtual network;

a node usage table describing a streaming capacity for each node of said virtual network and a current loading for each node of said virtual network; and

a cluster map describing network addresses for each of a plurality of servers in communication with said virtual network and listing of nodes within said virtual network, network addresses for said nodes, and an operational status of said nodes.

27. The virtual network of claim 26 further comprising a fault detection apparatus within each computer processing system of said member nodes:

to periodically receive a first processor status message from a first adjacent node;

to append a second processor status message of a current node to said first processor status message; and

to periodically transmit said first and second processor status message to a second adjacent node.

28. The virtual network of claim 27 wherein said cluster supervising processor receives an accumulation of the processor status messages from all nodes of said virtual network.

29. The virtual network of claim 27 wherein, if the fault detection apparatus does not receive said first processor status message for a number of periods, said first adjacent node is declared to have failed and a failure declaration is appended to said second processor status message.

30. The virtual network of claim 29 wherein, upon receipt of said failure declaration, the cluster supervising processor modifies said cluster map to reflect failure of the node.

31. The virtual network of claim 26 wherein the cluster supervising processor periodically posts a supervisor notification message on said virtual multicast bus, said supervisor notification message comprises a node identification and a network address for said cluster supervising processor.

32. The virtual network of claim 31 wherein the supervisor notification message further comprises the cluster topology and a current cluster map.

33. The virtual network of claim 31 wherein, if one node of said virtual network does not receive said supervisor notification message within a notification time, said node becomes said cluster supervising processor, updates said cluster topology table and said cluster map, transmits a cluster supervising processor update message, and the supervisor notification message.

34. The virtual network of claim 31 wherein a new node joins said virtual network by the steps of:

listening to said virtual multicast bus for a supervisor notification message from the present cluster supervising processor;

posting on said virtual multicast bus a join request message providing a node identification, a network address for said node, and a disk access list for said node;

updating by the present cluster supervising processor the cluster map and the cluster topology; and

placing a new supervisor notification message upon said virtual multicast bus including said new node.

35. The virtual network of claim 34 wherein the new node joins said virtual network further by the steps of:

ceasing posting on said virtual multicast bus said join request message.

36. The virtual network of claim 34 wherein the new node becomes the cluster supervising processor, if said new node has a priority that supercedes said present cluster supervising processor.

37. The virtual network of claim 36 wherein the new node acting as the present cluster supervising processor transmits the supervisor notification message and the original cluster supervising processor ceases transmitting said supervisor notification message.

38. The virtual network of claim 37 wherein if the new node does not transmit the supervisor notification message by the notification time, the original cluster supervising processor resumes transmission of the supervisor notification message.

39. The virtual network of claim 31 wherein a node leaves said virtual network by the steps of:

posting a leave message on said virtual multicast bus, said leave message containing the node identification and the network address for said node;

updating by the cluster supervising processor of the cluster map and the cluster topology; and

posting on the virtual multicast bus the supervisor notification message with the updated cluster map and cluster topology.

40. The virtual network of claim 39 wherein the node leaving the virtual network ceases posting the leave message upon receipt of the supervisor notification message with the updated cluster map and cluster topology.

41. The virtual network of claim 39 wherein if the node leaving said virtual network is the cluster supervising processor, the node with the highest priority listed the priority list then becomes the cluster supervising processor.

42. The virtual network claim 26 wherein:

each node of said virtual network periodically determines whether each disk to which said node has access is functioning and if any disk is not functioning;

the node creates a disk failure message for the disk not functioning for transfer to an adjacent node;

wherein said adjacent node transfers said disk failure node to subsequent adjacent nodes until said cluster supervising processor receives said disk failure message;

wherein upon receipt of multiple disk failure messages from multiple nodes for the disk not functioning, the cluster supervising processor declares a disk failure, updates the disk usage table, and reassigns all the transfer of data files from a failing node to an active node.

43. The virtual network of claim 23 wherein a group of said computer systems of said plurality of clusters of computer processing systems are configured as a sub-cluster, said sub-cluster being a node of said virtual network.

44. The virtual network of claim 23 wherein said virtual network is formed and said cluster supervising processor is designated by the steps of:

listening to said virtual multicast bus for a supervisor notification message from the cluster supervising processor by each node of the cluster;

if no supervisor notification message is received, designating each node a single node virtual network of its own;

designating each node the virtual network supervising processor of its single node cluster;

transmitting by each cluster supervising processor of each single node virtual network the supervisor notification message for each single node cluster;

ceasing by those nodes having a lower priority from transmitting supervisor notification messages such that the node with a highest priority is the virtual network supervising processor; and

joining said virtual network by those nodes with lower priority by posting on said virtual multicast bus a join request message providing a node identification, a network address for said node, and a disk access list for said node.

45. A method for forming a virtual network within a plurality of clusters of computer processing systems interconnected by a physical network to allow each computer processing system of the clusters of computer processing systems to transfer data between any of the plurality of computer systems, said method for forming said virtual network comprising steps of:

creating a plurality of nodes such that each node comprises at least one computer system cluster designated to be a member of said virtual network, each computer system cluster comprising at least one of said computer processing systems;

providing communication between member nodes of said virtual network through a virtual multicast bus; and

establishing a configuration service apparatus communicating with each of said computer systems;

transferring from said configuration service apparatus to each of the plurality of computer processing systems;

a neighbor'"'"'s listing for each of said computer processing systems included in a member node of said virtual network, a separate neighbor'"'"'s listing associated with any virtual network included within said a plurality of clusters;

a node identification to identify a node for each member computer processing system within said cluster,

a multicast bus address to broadcast communications to said member nodes of said virtual network by way of said virtual multicast bus, and

a node priority list designating a priority for each member node within said virtual network; and

selecting one of said computer systems within said nodes according to the priority from said priority list to be a cluster supervising processor to provide operational control services for each of said member nodes.

46. The method for forming said virtual network of claim 45 wherein transferring from said configuration service apparatus to each of the plurality of computer systems a disk access list.

47. The method for forming said virtual network of claim 46 wherein the disk access list comprises identification of accessible disks, disk mount points, and failure detection locations.

48. The method for forming said virtual network of claim 45 further comprising the step of maintaining by said cluster supervising processor:

a cluster topology table detailing connectivity for each node of the virtual network and a disk access status for each disk within said virtual network;

a disk usage table describing current capacity and loading for each disk within said virtual network;

a node usage table describing a streaming capacity for each node of said virtual network and a current loading for each node of said virtual network; and

a cluster map describing network addresses for each of a plurality of servers in communication with said virtual network and listing of nodes within said virtual network, network addresses for said nodes, and an operational status of said nodes.

49. The method for forming said virtual network of claim 48 further comprising the step of:

detecting faults within each computer processing system of said member nodes by the steps of;

periodically receiving a first processor status message from a first adjacent node and transmit;

appending a second processor status message of a current node to said first processor status message; and

periodically transmitting said first and second processor status message to a second adjacent node.

50. The method for forming said virtual network of claim 49 wherein detecting faults within each computer processing system further comprises the step of receiving an accumulation of the processor status messages from all nodes of said virtual network.

51. The method for forming said virtual network of claim 49 wherein, detecting faults within each computer processing system further comprises the step of:

declaring said first adjacent node to have failed, if said first processor status message for a number of periods is not received;

appending a failure declaration to said second processor status message.

52. The method for forming said virtual network of claim 51 wherein detecting faults within each computer processing system further comprising the step of modifying said cluster map to reflect failure of the node, upon receipt of said failure declaration.

53. The method for forming said virtual network of claim 48 wherein maintaining by said cluster supervising processor comprises the step of posting a supervisor notification message on said virtual multicast bus, said supervisor notification message comprises a node identification and a network address for a cluster supervising processor.

54. The method for forming said virtual network of claim 53 wherein the supervisor notification message further comprises the cluster topology and a current cluster map.

55. The method for forming said virtual network of claim 53 wherein maintaining by said cluster supervising processor further comprises the steps of:

becoming said cluster supervising processor by one node of said virtual network if said one node does not receive said supervisor notification message within a notification time;

updating by said one node said cluster topology table and said cluster map; and

transmitting by said one a cluster supervising processor update message, and the supervisor notification message.

56. The method for forming said virtual network of claim 53 further comprising the step of joining a new node to said virtual network by the steps of:

listening to said virtual multicast bus for a supervisor notification message from the present cluster supervising processor;

posting on said virtual multicast bus a join request message providing a node identification, a network address for said node, and a disk access list for said node;

updating by the present cluster supervising processor the cluster map and the cluster topology; and

placing a new supervisor notification message upon said virtual multicast bus including said new node.

57. The method for forming said virtual network of claim 56 wherein joining a new node to said virtual network further by the step of:

ceasing posting on said virtual multicast bus said join request message.

58. The method for forming said virtual network of claim 56 wherein joining a new node to said virtual network further comprises the step of establishing said new node as the cluster supervising processor, if said new node has a priority that supercedes said present cluster supervising processor.

59. The method for forming said virtual network of claim 58 wherein establishing said new node as the cluster supervising processor comprises the steps of transmitting by said present cluster supervising processor said supervisor notification message and ceasing transmitting by said original cluster supervising processor said supervisor notification message.

60. The method for forming said virtual network of claim 59 wherein establishing said new node as the cluster supervising processor further comprises the step of resuming transmission of the supervisor notification message by the original cluster supervising processor, if said new node does not transmit the supervisor notification message by said notification time.

61. The method for forming said virtual network of claim 53 wherein further comprising the step of leaving said virtual network by one node by the steps of:

posting a leave message on said virtual multicast bus, said leave message containing the node identification and the network address for said node;

updating by the cluster supervising processor of the cluster map and the cluster topology; and

posting on the virtual multicast bus the supervisor notification message with the updated cluster map and cluster topology.

62. The method for forming said virtual network of claim 61 wherein leaving said virtual network by a node further comprises the step of ceasing posting the leave message upon receipt of the supervisor notification message with the updated cluster map and cluster topology by the node leaving the virtual network.

63. The method for forming said virtual network of claim 61 wherein leaving said virtual network by a node further comprises the step of establishing the cluster supervising processor as the node with the highest priority listed the priority list, if the node leaving said virtual network is the cluster supervising processor.

64. The virtual network claim 48 wherein maintaining by said cluster supervising processor comprises the steps of:

periodically determining by each node of said virtual network whether each disk to which said node has access is functioning and if any disk is not functioning;

creating by said node a disk failure message for the disk not functioning for transfer to an adjacent node;

transferring by said adjacent node said disk failure node to subsequent adjacent nodes until said cluster supervising processor receives said disk failure message;

declaring by said cluster supervising processor a disk failure, updating the disk usage table, and reassigning all the transfer of data files from a failing node to an active node, upon receipt of multiple disk failure messages from multiple nodes for the disk not functioning.

65. The method for forming said virtual network of claim 45 wherein creating a plurality of nodes comprises the steps of:

configuring a group of said computer systems of said plurality of clusters of computer processing systems are as a sub-cluster; and

creating one node of said virtual network from said sub-cluster.

66. The method for forming said virtual network of claim 45 wherein forming said virtual network and selecting one of said computer systems within said nodes to be said cluster supervising processor further comprise the steps of:

listening to said virtual multicast bus for a supervisor notification message from the cluster supervising processor by each node of the cluster;

if no supervisor notification message is received, designating each node a single node virtual network of its own;

designating each node the virtual network supervising processor of its single node cluster;

transmitting by each cluster supervising processor of each single node virtual network the supervisor notification message for each single node cluster;

ceasing by those nodes having a lower priority from transmitting supervisor notification messages such that the node with a highest priority is the virtual network supervising processor; and

joining said virtual network by those nodes with lower priority by posting on said virtual multicast bus a join request message providing a node identification, a network address for said node, and a disk access list for said node.