Scalable distributed computing environment

• US 5,793,968 A
• Filed: 03/10/1997
• Issued: 08/11/1998
• Est. Priority Date: 08/19/1994
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: PeerLogic, Inc. (Synchronoss Technologies Incorporated)
• Inventors: Shafiq, Muhammad, Ramakrishnan, Krish, Gregerson, Daniel P., Farrell, David R., Wallis, Ian F., Ahuja, Ratinder P., Gaitonde, Sunil S.
• Primary Examiner(s): Harrell, Robert B.
• Application Number:
  US08/813,276
• Time in Patent Office: 519 Days
• Field of Search: 364/DIG. 1 MS File, 364/DIG. 2 MS File, 395/200.3, 395/200.31, 395/200.33, 395/200.34, 395/200.35, 395/200.38, 395/200.39, 395/200.51, 395/200.53, 395/200.54
• US Class Current: 709/209
• CPC Class Codes: G06F 2209/503 Resource availability
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 69/24 Negotiation of communication capabilities
• CPC Class Codes: H04L 69/32 Architecture of open systems interconnection [OSI] 7-layer type protocol stacks, e.g. the interfaces between the data link level and the physical level
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: H04Q 2213/1305 Software aspects
• CPC Class Codes: H04Q 2213/13107 Control equipment for a part of the connection, distributed control, co-processing
• CPC Class Codes: H04Q 2213/13141 Hunting for free outlet, circuit or channel
• CPC Class Codes: H04Q 2213/13204 Protocols
• CPC Class Codes: H04Q 2213/13353 Routing table, map memory
• CPC Class Codes: H04Q 2213/13383 Hierarchy of switches, main and subexchange, e.g. satellite exchange
• CPC Class Codes: H04Q 2213/13388 Saturation signaling systems

Abstract

A scalable distributed computing network comprises a plurality of nodes each independently executing software components. When a node having a managerial role in the network leaves the network, the remaining nodes negotiate among the nodes to assume the managerial role by broadcasting a message indicating the interest in assuming the managerial role. The node determined to be the best qualified node for the role is then selected by the system to assume the new managerial role.

Claims

1. A scalable distributed digital network interconnecting a plurality of nodes, with at least one of the plurality of nodes being associated with one or more resources, each resource having an active state in which the resource is available to other nodes and an inactive state in which the resource is not available, the network comprising:

means for storing a request by a node for a requested resource if that resource is not available;

means for automatically identifying by the node a resource that becomes available when the resource switches from the inactive to the active state; and

means for automatically informing the node that the requested resource has become available if the resource matches the requested resource.

2. The network of claim 1 wherein said plurality of nodes are arranged in at least two levels, and wherein nodes in a first level contain information relating to the resources present in nodes in a second level.

3. The network of claim 2 wherein:

at least one node in the first level contains a cache for storing requests for resources; and

the means for storing comprises the cache.

4. The network of claim 3 further comprising means for removing the request from the cache when the requested resource becomes available and satisfies the request.

5. The network of claim 2 wherein the first level is a parent level and the second level is a child level, each node in the parent level being associated with one or more nodes in the child level and each node in the child level being associated with one node in the parent level.

6. The network of claim 1 wherein:

at least one of said plurality of nodes contains a cache for storing requests for resources; and

the means for storing comprises the cache.

7. The network of claim 6 further comprising the means for removing the request from the cache when the requested resource becomes available and satisfies the request.

8. A scalable distributed computing network with a plurality of nodes for independently executing software components, a node comprising:

means for generating a logical hierarchy of the roles of the nodes with three or more levels where any node can assume one or multiple roles, with the assumption of which neither requires nor precludes the assumption of any other role; and

means for negotiating its role with other nodes when there is a change in the configuration of the network, such that a node at the lowest level of the hierarchy can assume the role of the highest level of the hierarchy.

9. The network of claim 8 with one of the nodes being a parent, and one of the remaining nodes being a child, the means for generating in the node comprising means for monitoring the status of the parent and the child.

10. The node of claim 9 wherein the means for monitoring further comprises:

means for exchanging status messages between the parent and the child at specified time intervals; and

means for searching for a new parent node when the child does not receive status messages from the parent within a predetermined period of time.

11. The node of claim 9 wherein the means for monitoring comprising means for de-registering the child when the parent does not receive status message from the child within a predetermined period of time.

12. The node of claim 8 wherein the means for generating comprises means for searching for a parent node when the node enters the network.

13. The node of claim 12 wherein the means for searching further comprises:

means for listening to messages for a specified period of time;

means for determining, if a message is received, the entering node'"'"'s parent based on the received message;

means for broadcasting, if no parent is found upon expiration of the specified period of time, a message for searching its parent;

means for determining whether any one of the responses to the broadcasted message originates from its parent; and

means for assuming the role as its own parent when no response is received.

14. The network of claim 8 with one of the nodes being a parent node, the means for generating in the node comprising means for registering a child node upon its entering the network.

15. The node of claim 14 wherein the means for registering comprises:

means for listening to messages sent by entering nodes;

means for determining whether one of the messages is sent by a child node or a duplicate child node;

means for informing the duplicate child node of a role conflict if such a node is detected; and

means for sending an acknowledge message to the child node if such a node is detected.

16. The network of claim 8 with a node having a managerial role leaving the network, and with a remaining node negotiating to assume the managerial role, the means for negotiating in the remaining node comprising:

means for broadcasting a message indicating the participating node'"'"'s interest in assuming the managerial role;

means for listening, subsequent to the said broadcasting step, for messages on the network; and

means for assuming the managerial role if there is no message on the network which indicates that another node is better qualified to assume the managerial role.

17. The remaining node of claim 8 wherein the means for negotiating further comprises means for withdrawing from participating so as to allow the node to withdraw when the node receives messages indicating that there is at least one participating node which is more qualified to assume the managerial role.

18. The node of claim 8 wherein the means for negotiating comprises:

means for setting up a database containing the names of all known nodes participating in the process;

means for transmitting election messages to nodes included in the data base, the election messages containing information relating to the participating nodes known to the sending node;

means for receiving election messages from other participating nodes;

means for updating the database using the information containing in the received election messages; and

means for determining, based on the information contained in the updated database, which one of the participating node assumes the managerial role;

such that when two conflicting nodes claim the same managerial role, at least one of the conflicting nodes can participate in a process to determine which node can assume the managerial role.

19. The network of claim 8 wherein the number of levels is changeable.

20. A scalable distributed computing network with a plurality of nodes for independently executing software components, the network comprising:

means for generating a logical hierarchy of the roles of the nodes with three or more levels where any node can assume one or multiple roles, with the assumption of which neither requires nor precludes the assumption of any other role; and

wherein each node comprises means for negotiating its role with other nodes when there is a change in the configuration of the network, such that a node at the lowest level of the hierarchy being can assume the role of the highest level of the hierarchy.

21. The network of claim 20 wherein:

a node having a managerial role leaves the network;

a remaining node negotiates to assume the managerial role; and

the means for negotiating in the remaining node comprises;

means for broadcasting a message indicating the participating node'"'"'s interest in assuming the managerial role;

means for listening, subsequent to the said broadcasting step, for messages on the network; and

means for assuming the managerial role if there is no message on the network which indicates that another node is better qualified to assume the managerial role.

22. The network of claim 20 wherein the means for negotiating in the remaining node further comprises means for withdrawing from participating so as to allow the node to withdraw when the node receives messages indicating that there is at least one participating node which is more qualified to assume the managerial role.

23. The network of claim 20 wherein the means for negotiating in the remaining node comprises:

means for setting up a database containing the names of all known nodes participating in the process;

means for transmitting election messages to nodes included in the data base, the election messages containing information relating to the participating nodes known to the sending node;

means for receiving election messages from other participating nodes;

means for updating the database using the information containing in the received election messages; and

means for determining, based on the information contained in the updated database, which one of the participating node assumes the managerial role;

such that when two conflicting nodes claim the same managerial role, at least one of the conflicting nodes can participate in a process to determine the node to assume the managerial role.

24. A heterogeneous network with a plurality of nodes, each node having a context bridge, each bridge being able to route packets between nodes having different communication protocols at different levels, a bridge comprising:

means for setting up a list of context bridges and the communication protocols handled by each context bridge in the list;

means for listening for routing information packets which are periodically broadcast by other context bridges informing recipients of the communication protocols handled by the broadcasting context bridge;

means for updating the list using the information contained in the received routing information packets; and

means for determining the routing paths in the context bridges using the updated list.

25. A network as recited in claim 24 wherein:

each node has a routing protocol;

the bridge further comprises;

means for receiving a packet at a source node to be routed to a destination node using at least one context bridge;

means for determining whether the destination node of the packet has a routable protocol;

means for sending a route discovery packet to discover one or more context bridges if the destination has no routable protocol; and

means for routing the packet from the source to the destination using either the routable protocol if the destination has a routable protocol, or through the one or more discovered context bridges if the destination has no routable protocol.