Distributed means of organizing an arbitrarily large number of computers

• US 20030009512A1
• Filed: 06/21/2002
• Published: 01/09/2003
• Est. Priority Date: 06/22/2001
• Status: Active Grant

• Current Assignee: Viametrix Incorporated
• Original Assignee: Viametrix Incorporated
• Inventors: Fish, Russell H. III
• Granted Patent: US 7,424,524 B2
• Time in Patent Office: Days
• US Class Current: 709/201
• CPC Class Codes: G06F 2209/505 Clust
• 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
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/164 Adaptation or special uses of UDP protocol
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

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 distributed computer network, comprising:

a plurality of processors, and

at least one communication medium for interconnecting the plurality of processors;

wherein the plurality of processors are logically arranged such that a top processor of the plurality of processors operates at a top level of a hierarchy that includes the plurality of processors by sending a message to at least one logically neighboring processor;

wherein the message is disseminated throughout the hierarchy by each processor that receives the message, and that has a logically neighboring downstream processor, forwarding the message to at least one logically neighboring processor such that each processor in the hierarchy receives the message only once.

2. The distributed computer network of claim 1, wherein the at least one communication medium includes at least one physical interconnection unrelated to the logical arrangement of the plurality of processors.

3. The distributed computer network of claim 1, wherein the plurality of processors includes a first set of processors that each forward the received message to one or two logically neighboring processors and a second set of processors that each forward the received message to, at most, one logically neighboring processor.

4. The distributed computer network of claim 3, wherein the first set of processors include processors from the plurality of processors having a bandwidth connection greater than a selected threshold bandwidth and the second set of processors include processors from the plurality of processors having a bandwidth connection less than the selected threshold bandwidth.

5. The distributed computer network of claim 4, wherein the first set of processors are logically arranged in a polygonal configuration having an even number of sides and the second set of processors are logically arranged in a plurality of serial strings, each serial string logically connected to a processor from the first set of processors, wherein at least one serial string includes at least one processor that forwards the received message to a logically neighboring processor in the serial string.

6. The distributed computer network of claim 5, wherein the first set of processors are logically connected along at least one radial and at least one indirect radial, each radial comprising a line of logically adjacent processors that logically extends radially from said top processor and each indirect radial comprising a line of logically adjacent processors that logically extends from a processor on one of the at least one radial but does not logically intersect any of the at least one radial, wherein said message is disseminated by forwarding said message along each said radial, each said indirect radial, and each said serial string.

7. The distributed computer network of claim 5, wherein a processor in each serial string tends to move to a serial string that is logically connected to a processor from said first set of processors that is logically closer to the top processor if said closer serial string includes a number of processors less than one plus a number of processors included in the serial string to which said processor is currently connected.

8. The distributed computer network of claim 5, wherein each processor in a portion of a serial string that loses a logical connection to a corresponding processor from the first set of processors attempts to reconnect to the corresponding processor from the first set of processors.

9. The distributed computer network of claim 1, wherein a master processor of the plurality of processors is physically interconnected with at least one other processor of the plurality of processors via a local area network, said master processor forwarding, via said local area network, said message to at least one additional processor connected to said local area network.

10. The distributed computer network of claim 9, wherein the master processor forwards the message to a plurality of additional processors connected to said local area network via a local area network multicast using a single user datagram protocol packet.

11. The distributed computer network of claim 1, wherein the message relates to one of a broadcast of data and a search for information selected from the group consisting of specified data and a specified processor.

13. The distributed computer network of claim 12, wherein the collection of computers has the same number of radials as there are sides of the concentric polygons.

14. The distributed computer network of claim 12, wherein at least one high bandwidth computer of the collection of computers located on one of said radials or one of said indirect radials further forwards the message along a serial string that logically extends from said high bandwidth computer, said serial string comprising a line of logically adjacent low bandwidth computers, in the collection of computers, that does not logically intersect any of said radials and said indirect radials and each low bandwidth computer in said serial string forwarding the message to, at most, one other computer of said collection of computers.

15. The distributed computer network of claim 14, further comprising a plurality of serial strings, wherein each computer located on said radials and each computer located on said indirect radials comprises a high bandwidth computer and each computer located on said serial strings comprises a low bandwidth computer, said high bandwidth computers having a bandwidth connection above a selected bandwidth threshold and said low bandwidth computers having a bandwidth connection below said selected bandwidth threshold.

16. The distributed computer network of claim 15, wherein the low bandwidth computers tend toward a logical arrangement such that a broadcast path delay is substantially the same for each broadcast path, each broadcast path representing a series of logically adjacent computers from the first computer to a low bandwidth computer at an end of a serial string.

17. The distributed computer network of claim 14, wherein a computer of the collection of computers is connected to a local area network, said computer forwarding said message via a local area network multicast to a plurality of computers connected to said local area network.

18. The distributed computer network of claim 12, wherein said message is selected from the group consisting of broadcast data, a search parameter, and update information.

19. The distributed computer network of claim 12, wherein the first computer has at least one associated parameter for constraining performance, said at least one parameter selected from the group consisting of a maximum streaming bandwidth, a maximum number of connected computers, and an expiration time.

20. The distributed computer network of claim 19, wherein the parameters are encrypted.

12. A distributed computer network comprising:

a collection of computers logically arranged such that a first computer of the collection of computers is situated at a logical center of the collection of computers, wherein a plurality of computers from the collection of computers form a series of concentric polygons around the first computer;

wherein a top computer in a hierarchy of the collection of computers sends a message along each of a plurality of radials, each of said radials comprising a line of logically adjacent computers in the collection of computers that logically extends radially from said top computer; and

wherein each of a plurality of lower level computers, of the collection of computers, located on one of said radials further forwards the message along a corresponding indirect radial, each indirect radial comprising a line of logically adjacent computers in the collection of computers that logically extends radially from said corresponding lower level computer but does not logically intersect any of the radials.

21. A method for communicating in a computer network, comprising:

logically arranging a plurality of computers around a first computer situated at a logical center of the plurality of computers;

initiating a message at a top computer selected from the plurality of computers;

sending the message from the top computer along each of a plurality of series of logically adjacent subordinate computers, each series of logically adjacent subordinate computers logically extending radially from the top computer, the plurality of computers including said subordinate computers; and

forwarding the message, from each of a plurality of the subordinate computers along a corresponding series of logically adjacent secondary computers that logically extends radially from the subordinate computer but that does not intersect any of the series of logically adjacent subordinate computers that logically extends radially from the top computer and that does not intersect any of the other series of logically adjacent secondary computers that logically extend radially from another of the plurality of subordinate computers.

22. The method of claim 21, further comprising the step of forwarding the message from each computer of a set of computers selected from the group consisting of the subordinate computers and the secondary computers along a corresponding serial string of computers that does not include any of the subordinate computers and the secondary computers, each computer in each serial string operating to receive the message from a single logically adjacent upstream computer of said plurality of computers and forward the message to a single logically adjacent downstream computer of said plurality of computers if a logically adjacent downstream computer is present.

23. The method of claim 22, wherein the computers are moved between and among the series of logically adjacent subordinate computers and the series of logically adjacent secondary computers and between the serial strings of computers such that a number of computers in each message path that runs from the first computer to a collection edge tends to be substantially the same for each said message path.

24. The method of claim 22, wherein at least one of the plurality of computers is attached to a local area network, said computer further forwarding the message to at least one other computer attached to the local area network via a local area network multicast, said at least one computer selected from the group consisting of the subordinate computers, the secondary computers, and the computers in said serial strings.

25. The method of claim 21, wherein at least one of the plurality of computers is attached to a local area network, said computer further forwarding the message to at least one other computer attached to the local area network via a local area network multicast.

27. The method of claim 26, wherein the step of adding low bandwidth computers comprises attaching each low bandwidth computer to a particular one of said serial strings in a position closest to the corresponding high bandwidth computer, wherein each low bandwidth computer previously attached to said serial string is pushed down one level in said serial string.

28. The method of claim 26, further comprising the steps of:

comparing a number of low bandwidth computers in a first one of the serial strings to a number of low bandwidth computers in a second one of the serial strings, said second serial string attached to a corresponding second high bandwidth computer that is logically adjacent to a first high bandwidth that corresponds to the first serial string; and

moving a low bandwidth computer from said first serial string to said second serial string, based on said comparison, as necessary to maintain a balanced distribution.

29. The method of claim 28, wherein said balanced distribution comprises a logical configuration such that a number of computers in a broadcast path associated with the first serial string is substantially the same as a number of computers in a broadcast path associated with the second serial string, wherein each said broadcast path includes the computers along the radial, any indirect radial, and the serial string between the logical center computer and a last computer in the serial string.

30. The method of claim 26, further comprising:

identifying a first computer to be added to the collection of computers as being connected to a local area network (LAN);

determining if said LAN includes a second computer that comprises a computer in said collection of computers;

attaching said first LAN-connected computer to said second computer via a LAN multicast if said LAN is determined to include a computer in said collection of computers; and

performing said step of identifying the first LAN-connected computer as being one of a high bandwidth computer and a low bandwidth computer if said LAN is determined to not include a computer in said collection of computers.

31. The method of claim 26, further comprising displaying a representation of the logical configuration of said high bandwidth computers.

32. The method of claim 31, further comprising:

receiving an operator selection of a high bandwidth computer from said displayed representation; and

displaying information relating to the selected high bandwidth computer, said information selected from the group consisting of broadcast parameters, properties, neighbor identifiers, and identifiers of low bandwidth computers forming a serial string that is logically attached to the selected high bandwidth computer.

26. A method for logically configuring a collection of computers, comprising:

selecting a computer to serve as a logical center of the collection of computers;

identifying a computer to be added to the collection of computers as being one of a high bandwidth computer and a low bandwidth computer based on a bandwidth connection capacity associated with the computer to be added;

adding high bandwidth computers to the collection of computers to logically configure the high bandwidth computers into a plurality of concentric polygons, wherein each added high bandwidth computer operates to;

find a high bandwidth computer in the collection of computers;

follow one of a radial and an indirect radial that includes the found computer to a collection edge, said radial comprising a series of logically adjacent radial computers that logically extend from the logical center, and said indirect radial comprising a series of logically adjacent indirect radial computers that logically extend from one of the radial computers, wherein the collection edge comprises a logically outermost computer on said one of the radial and the indirect radial; and

logically attach to a computer in the collection of computers on the collection edge; and

adding low bandwidth computers to the collection of computers to logically configure the low bandwidth computers into a plurality of serial strings, each serial string logically attached to a corresponding one of said high bandwidth computers.

33. A method for logically configuring a collection of computers, comprising:

selecting a computer to serve as a logical center of the collection of computers;

arranging computers from the collection of computers such that the collection of computers are logically configured to form a plurality of successively higher concentric polygon levels around the logical center;

adding a computer to the collection of computers;

determining that the added computer is physically connected to a local area network (LAN);

determining whether the LAN includes a previously added computer of the collection of computers;

if the LAN does not include a previously added computer, logically connecting the added computer to a computer in the collection of computers, located at a collection edge, wherein the collection edge comprises a logical outer edge of the collection of computers and forms at least a partial concentric polygon level around the plurality of concentric polygon levels; and

if the LAN does include a previously added computer, logically connecting said added computer to receive a LAN multicast from said previously added computer.

34. The method of claim 33, further comprising, when the LAN does not include a previously added computer,

repeating the steps of:

changing a logical location of the added computer to a next lower concentric polygon level if a computer in the collection of computers is not situated at a logical position that neighbors the added computer at the next lower concentric polygon level; and

changing a logical location of the added computer to a logically adjacent position on a current concentric polygon level of the added computer if a computer in the collection of computers is not situated at said logically adjacent position.

35. The method of claim 33, further comprising the step of sending a message from a top computer of the collection of computers to each of a plurality of neighboring radial computers, each neighboring radial computer forwarding the message to another neighboring radial computer and to a neighboring indirect radial computer, such that the message is forwarded to each computer in the collection of computers only once.

36. The method of claim 33, further comprising, prior to the step of logically connecting the added computer to a computer located at a collection edge, locating the collection edge by:

identifying a previously connected computer in said collection of computers, and

following one of a radial and an indirect radial to the collection edge, said radial comprising a series of logically adjacent radial computers that logically extend from the logical center, and said indirect radial comprising a series of logically adjacent indirect radial computers that logically extend from one of the radial computers, wherein the collection edge comprises a logically outermost computer on said one of the radial and the indirect radial.

37. The method of claim 33, further comprising, subsequent to said step of logically connecting the added computer to the computer located at the collection edge:

receiving a request via the LAN for a LAN-connected computer of said collection of computers; and

responding to said request with information for connecting to a LAN multicast transmitted by said added computer.

38. The method of claim 33, further comprising displaying a representation of the logical configuration of said collection of computers.

39. The method of claim 38, further comprising:

receiving an operator selection of a computer connected to said LAN from said displayed representation; and

displaying information relating to the selected computer connected to said LAN, said information selected from the group consisting of broadcast parameters, properties, neighbor identifiers, and identifiers of computers of said collection of computers connected to said LAN.

40. A distributed computer network, comprising:

a collection of computers;

means for an added computer to locate the collection of computers;

means for the added computer to establish a connection to the collection of computers;

means for each computer in the collection of computers, including the added computer, to establish a logical arrangement such that each computer in the collection of computers can forward a message to at least one other computer, without any computer receiving the message more than once, for disseminating the message throughout the collection of computers.