Node management in scalable distributed computing enviroment

• US 5,526,358 A
• Filed: 08/19/1994
• Issued: 06/11/1996
• 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): Kizou, Hassan
• Assistant Examiner(s): RAO, SEEMA SRINIVAS
• Application Number:
  US08/293,073
• Time in Patent Office: 662 Days
• Field of Search: 370/85.2, 370/85.13, 370/16, 370/94.3, 370/13, 370/60, 340/825.02, 340/827, 395/200
• US Class Current: 709/221
• 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 method for independently executing software components in a node of a network containing many nodes. The method including generating a logical hierarchy of the roles of the nodes where any node can assume one or multiple roles; and negotiating the role of the nodes when there is a change in the configuration of the network. Another technique locates resources requested by a node in a scalable system interconnecting many nodes in a network. The technique includes identifying resources that join the network by switching from an inactive to an active state; and informing the requester the availability of the requested resource. A further technique determines routing paths in a context bridge which is able to route packets between nodes. The technique includes setting up a list of context bridges; listening for routing information packets which are periodically broadcast by other context bridges; and updating the database using the information contained in the received routing information packets. One more technique is on routing packets from a source node to a destination node using a context bridge. The technique includes determining whether the destination node has a routable protocol; if it does not have, then routing the packet using a source route containing the address of the context bridges from the source to the destination; and if it has, then routing the packet through at least one context bridge containing routable protocols.

Claims

1. A method for independently executing software components in a node of a network containing a plurality of nodes, the method comprising the steps of:

generating a logical hierarchy of the roles of the nodes in the network wherein any node can assume one or multiple roles, the assumption of which neither requires nor precludes the assumption of any other role; and

negotiating the role of the nodes when there is a change in the configuration of the network;

wherein at least two conflicting nodes claim the same managerial role and at least one of the conflicting nodes participates in a process of determining a node which assumes the managerial role, the negotiating step further comprising the steps, performed by each participating node, of;

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

transmitting election messages to nodes included in the data base, the election messages containing information relating to the participating nodes;

receiving election messages from other participating nodes;

updating the database using information contained in the received election messages; and

determining, based on the information contained in the updated database, which one of the participating nodes assumes the managerial role.

2. The method of claim 1 wherein a node having a managerial role leaves the network and at least one of the remaining nodes participates in a negotiation process of determining which node assumes the managerial role, the negotiating step further comprising the steps, performed by each participating node, of:

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

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

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.

3. The method of claim 1 further comprising the steps performed by each participating node:

listening, prior to the said broadcasting step, for a specified period of time for messages sent by other participating nodes; and

withdrawing from the process when the messages indicate that there is at least one participating node which is more qualified to assume the managerial role.

4. The method of claim 1 wherein one of the nodes is a parent node, the method further comprising the step of searching for a parent node when a node enters the network.

5. The method of claim 4 wherein the searching step further comprises the steps, performed by the entering node, of:

listening to messages for a specified period of time;

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

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

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

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

6. The method of claim 1 wherein one of the nodes is a parent node, the method further comprising the step of registering a child upon its entering the network.

7. The method of claim 6 wherein said registering step further comprises:

listening to messages sent by entering nodes;

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

if a duplicate child node is detected, informing the duplicate child node of a role conflict; and

if a child node is detected, sending an acknowledge message to the child node.

8. The method of claim 1 wherein one of the nodes is a parent and one of the remaining nodes is a child, said method further comprising the step of monitoring the status of the parent and the child.

9. The method of claim 8 wherein the monitoring step further comprises the step of:

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

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

10. The method of claim 8 further comprising the step of de-registering the child when the parent does not receive status message from the child within a predetermined period of time.

11. The method of claim 1 wherein the logical hierarchy consists of an arbitrary number of levels.

12. The method of claim 11 wherein the number of levels is changeable.

13. The method of claim 1 wherein the roles of the nodes in the network are changeable contingent on the requirements of the network.