DISTRIBUTED MEANS OF ORGANIZING AN ARBITRARILY LARGE NUMBER OF COMPUTERS

• US 20110202681A1
• Filed: 04/15/2011
• Published: 08/18/2011
• Est. Priority Date: 06/22/2001
• Status: Abandoned Application

• Current Assignee: Russell Fish
• Original Assignee: Russell Fish
• Inventors: Fish, Russell
• Application Number:
  US13/087,916
• Publication Number:
  US 20110202681A1
• Time in Patent Office: Days
• US Class Current: 709/240
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/0894 Policy-based network configuration management
• 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 technique for organizing a plurality of computers such that message broadcast, content searching, and computer identification of the entire collection or a subset of the entire collection may be performed quickly without the use of a controlling computer. The technique describes the creation, operation, and maintenance of a connection scheme by which each computer in the collection appears to be the top level of a hierarchical array. The maintenance of this hierarchical connection scheme allows one to many communications throughout the collection of computers to scale geometrically rather than linearly.

Claims

1. A method comprising receiving an invitation to become a child of a first adjacent node;

if a minimum link bandwidth along a protection path from said current node to a root node of the spanning hierarchical protection tree which visits the first adjacent node is greater than a minimum link bandwidth of any existing protection path from said current node to said root node;

designating said first adjacent node as a primary parent of said current node in said tree; and

from said current node, sending an invitation to become a child of said current node in said tree to each adjacent node of said current node that is not said first adjacent node.

2. The method of claim 1, further comprising:

if said minimum capacity along said protection path from said current node to said root node which visits the first adjacent node is not greater than said minimum link bandwidth of any existing protection path from said current node to said root node;

designating said first adjacent node as a backup parent of said current node in said tree.

3. The method of claim 2, wherein said backup parent is one of a number of backup parents of said current node, each one of said number of backup parents having a priority based on a minimum link bandwidth of a protection path from said current node to said root node which visits said one of said number of backup parents, with a higher minimum link bandwidth being associated with a higher priority.

4. The method of claim 3, further comprising ensuring that said designating of said first adjacent node as a primary parent of said current node does not introduce a loop into said spanning hierarchical protection tree.

5. The method of claim 1 further comprising:

subsequent to said extending, upon a failure of a link between the current node and any adjacent node that neither is designated as the primary parent of the current node in the tree nor designates the current node as its primary parent in the tree, re-routing network traffic intended for said any adjacent node to the adjacent node that is designated as the primary parent of the current node in the tree.

6. A computing device comprising:

a processor;

memory, in communication with said processor, storing processor readable instructions adapting said device to extend a spanning hierarchical protection tree in a mesh network by;

at a current node, receiving an invitation to become a child of a first adjacent node; and

if a minimum link bandwidth along a protection path from said current node to a root node of the spanning hierarchical protection tree which visits the first adjacent node is greater than a minimum link bandwidth of any existing protection path from said current node to said root node;

designating said first adjacent node as a primary parent of said current node in said tree; and

from said current node, sending an invitation to become a child of said current node in said tree to each adjacent node of said current node that is not said first adjacent node.

7. The computing device of claim 6, wherein said memory further comprises instructions adapting said device to:

if said minimum link bandwidth along said protection path from said current node to said root node which visits the first adjacent node is not greater than said minimum link bandwidth of any existing protection path from said current node to said root node, designate said first adjacent node as a backup parent of said current node in said tree.

8. The computing device of claim 7, wherein said backup parent is one of a number of backup parents of said current node, each one of said number of backup parents having a priority based on a minimum capacity of a protection path from said current node to said root node which visits said one of said number of backup parents, with a higher minimum capacity being associated with a higher priority.

9. The computing device of claim 8, wherein said instruction further adapt said device to ensure that said designating of said first adjacent node as a primary parent of said current node does not introduce a loop into said spanning hierarchical protection tree.

10. The computing device of claim 6 wherein said memory further stores processor readable instructions adapting said device to, subsequent to said extending, upon a failure of a link between the current node and any adjacent node that neither is designated as the primary parent of the current node in the tree nor designates the current node as its primary parent in the tree, re-route network traffic intended for said any adjacent node to the adjacent node that is designated as the primary parent of the current node in the tree.

11. A computer readable medium storing computer software that, when loaded into a computing device, adapts said device to extend a spanning hierarchical protection tree in a mesh network by:

at a current node, receiving an invitation to become a child of a first adjacent node; and

if a minimum link bandwidth along a protection path from said current node to a root node of the spanning hierarchical protection tree which visits the first adjacent node is greater than a minimum link bandwidth of any existing protection path from said current node to said root node;

designating said first adjacent node as a primary parent of said current node in said tree; and

from said current node, sending an invitation to become a child of said current node in said tree to each adjacent node of said current node that is not said first adjacent node.

12. The computer readable medium of claim 11, wherein said software is further capable of adapting said device by:

if said minimum link bandwidth along said protection path from said current node to said root node which visits the first adjacent node is not greater than said minimum link bandwidth of any existing protection path from said current node to said root node, designating said first adjacent node as a backup parent of said current node in said tree.

13. The computer readable medium of claim 12, wherein said backup parent is one of a number of backup parents of said current node, each one of said number of backup parents having a priority based on a minimum link bandwidth of a protection path from said current node to said root node which visits said one of said number of backup parents, with a higher minimum capacity being associated with a higher priority.

14. The computer readable medium of claim 13, wherein said software is further capable of adapting said device to extend a spanning hierarchical protection tree in a mesh network by ensuring that said designating of said first adjacent node as a primary parent of said current node does not introduce a loop into said spanning hierarchical protection tree.

15. The computer readable medium of claim 11 wherein said software further adapts said device to, Subsequent to said extending, upon a failure of a link between the current node and any adjacent node that neither is designated as the primary parent of the current node in the tree nor designates the current node as its primary parent in the tree, re-route network traffic intended for said any adjacent node to the adjacent node that is designated as the primary parent of the current node in the tree.

16. A computer readable medium storing computer software that, when loaded into a computing device, adapts said device to:

extend a spanning hierarchical protection tree in a mesh network by;

at a current node, receiving an invitation to become a child of a first adjacent node; and

if a minimum link bandwidth alone a protection oath from said current node to a root node of the spanning hierarchical protection tree which visits the first adjacent node is greater than a minimum link bandwidth of any existing protection path from said current node to said root node;

designating said first adjacent node as a primary parent of said current node in said tree; and

from said current node, sending an invitation to become a child of said current node in said tree to each adjacent node of said current node that is not said first adjacent node; and

reconnect a node disconnected from said spanning hierarchical protection tree in said mesh network to the spanning hierarchical protection tree by;

designating a backup parent of said disconnected node in said tree to be a primary parent of said disconnected node in said tree; and

from said disconnected node, sending an invitation to become a child of said disconnected node in said tree to each adjacent node of said disconnected node that is not said primary parent, said invitation providing an indication of a minimum link bandwidth of a protection path to a root node of the spanning hierarchical protection tree which visits said disconnected node.

17. A computer readable medium storing computer software that, when loaded into a computing device, adapts said device to connect an auxiliary node to a spanning hierarchical protection tree in a mesh network by:

requesting an invitation from each adjacent node of said auxiliary node for said auxiliary node to become a child of said adjacent node;

from each said adjacent node, receiving an invitation to become a child of said adjacent node; and

for each said adjacent node;

if a minimum link bandwidth along a protection path from said auxiliary node to a root node of the spanning hierarchical protection tree which visits said adjacent node is greater than a minimum link bandwidth of any existing protection path from said auxiliary node to said root node;

designating said adjacent node as a primary parent of said auxiliary node in said tree; and

from said auxiliary node, sending an invitation to become a child of said auxiliary node in said tree to each further adjacent node of said auxiliary node that is not said primary parent adjacent node.

18. The computer readable medium of claim 17, wherein said software is further capable of adapting said device to connect said auxiliary node to said tree by:

for each said adjacent node;

if said minimum link bandwidth along a protection path from said auxiliary node to said root node of the spanning hierarchical protection tree which visits said adjacent node is not greater than said minimum link bandwidth of any existing protection path from said auxiliary node to said root node, designating said adjacent node as a backup parent of said auxiliary node in said tree.

19. A computer-readable medium storing computer software that, when loaded into a computing device, adapts said device to extend a spanning hierarchical protection tree in a mesh network, comprising:

executable code for receiving, at a current node, an invitation to become a child of a first adjacent node;

executable code for, if a lowest bandwidth link of links of a protection path from said current node to a root of the spanning hierarchical protection tree which visits the first adjacent node is greater than a lowest bandwidth link of links of any existing protection path from said current node to said root node;

designating said first adjacent node as a primary parent of said current node in said tree; and

from said current node, sending an invitation to become a child of said current node in said tree to each adjacent node of said current node that is not said first adjacent node;

extending a spanning hierarchical protection tree in a mesh network by;

at a current node.