US6134599A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for organizing devices in a network into a tree using suitability values
Assignee: Oracle America Inc
•
Filing: 1998-04-18
•
Granted: 2000-10-17
•
Expires: 2018-04-18
Abstract
Abstract In a digital data network, a plurality of devices interconnected by a communication link organize themselves into a tree structure. Each of the devices has an associated suitability value that generally relates to the device's suitability for becoming a node in the tree structure. The devices organize themselves into a tree structure in one or more iterations, each iteration comprising two general steps, namely, a node election step and a tree establishment step. In the node election step, the devices whose suitability values are such that they can become nodes in the tree broadcast over the communication link node election messages including their respective suitability values. These devices also receive the node election messages that are broadcast by other devices. Each device determines whether it is elected a node in the tree structure in connection with a comparison between its suitability value and suitability values of node election messages received thereby. During the tree establishment step, the devices in the network communicate with at least one of the device or devices which is or are elected respective nodes in the tree structure to facilitate becoming respective children thereof.
Inventors
- 👤 Dah Ming Chiu
- 👤 Miriam Kadansky
- 👤 Radia J. Perlman
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 20:03
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/48; H04L12/00; H04L12/02; H04L12/16; H04L12/18; H04L12/185; H04L45/16; H04L45/488; H04L12/1863
Claims Analysis
Total Claims: 45
Claim 1
Independent Claim
175 words
A method of logically organizing, in a digital data network comprising a plurality of devices interconnected by a communication link, the devices into a tree structure, each of the devices having an associated suitability value, the method comprising: A. a node election step in which at least one of the devices is enabled to broadcast, over the communication link, at least one node election message including the respective device's suitability value, any devices broadcasting node election messages also being enabled to receive from the communication link any node election messages broadcast by other devices and to determine whether it is elected a node in the tree structure in connection with a comparison between its suitability value and suitability values in any received node election messages; and B. a tree establishment step in which at least one device which is elected a node in the tree structure is enabled to communicate with at least one other device to facilitate the other device becoming a child of the device that is elected a node in the tree.
Claim 2
Independent Claim
175 words
A method of logically organizing, in a digital data network comprising a plurality of devices interconnected by a communication link, the devices into a tree structure, each of the devices having an associated suitability value, the method comprising: A. a node election step in which at least one of the devices is enabled to broadcast, over the communication link, at least one node election message including the respective device's suitability value, any devices broadcasting node election messages also being enabled to receive from the communication link any node election messages broadcast by other devices and to determine whether it is elected a node in the tree structure in connection with a comparison between its suitability value and suitability values in any received node election messages; and B. a tree establishment step in which at least one device which is elected a node in the tree structure is enabled to communicate with at least one other device to facilitate the other device becoming a child of the device that is elected a node in the tree.
Claim 3
Dependent Claim
50 words
A method as defined in claim 1 in which the node election step and the tree establishment step are performed in at least one iteration, in said at least one iteration, during the node election step one device being elected a node, as a root node, in the tree structure.
Claim 4
Dependent Claim
57 words
A method as defined in claim 2 in which the node election step and the tree establishment step are performed in a series of iterations, in a first iteration the root node being elected during the node election step, and each subsequent iteration at least one other device being elected as a node in the tree structure.
Claim 5
Dependent Claim
52 words
A method as defined in claim 3 in which the at least one other device elected as a node in the tree structure, during the tree establishment step of at least one of said iterations, being enabled to communicate with the device elected as root node to facilitate becoming a child thereof.
Claim 6
Dependent Claim
32 words
A method as defined in claim 3 in which the device elected as the root node is enabled to determine the number of additional nodes to be elected during each subsequent iteration.
Claim 7
Dependent Claim
51 words
A method as defined in claim 5 in which the device elected as the root node transmits, in its at least one node election message transmitted during each iteration after the first iteration, a number of nodes value identifying the number of additional nodes to be elected during the respective iteration.
Claim 8
Dependent Claim
51 words
A method as defined in claim 6 in which each of the devices enabled to broadcast at least one node election message transmits, during each iteration after the first iteration, a number of nodes value corresponding to the number of nodes value transmitted by the device elected as the root node.
Claim 9
Dependent Claim
28 words
A method as defined in claim 1 in which each device is assigned a priority value, the respective device's suitability value being a function of its priority value.
Claim 10
Dependent Claim
38 words
A method as defined in claim 1 in which each device has an associated capacity value associated with a number of children that it can accommodate, the respective device's suitability value being a function of its priority value.
Claim 11
Dependent Claim
29 words
A method as defined in claim 1 in which said at least one device is enabled to begin broadcasting at least one node election message after it is initialized.
Claim 12
Dependent Claim
60 words
A method as defined in claim 1 in which said at least one device is enabled to broadcast a plurality of node election messages, the at least one device stopping broadcasting node election messages if it receives a node election message from another device having a higher suitability value than the suitability value associated with the at least one device.
Claim 13
Dependent Claim
50 words
A method as defined in claim 1 in which, during the tree establishment step the at least one device that is elected a node in the tree is enabled to broadcast a node advertising message over the communication link indicating that it is available as a node in the tree.
Claim 14
Dependent Claim
46 words
A method as defined in claim 12 in which the at least one device that is elected a node in the tree is enabled to broadcast a node advertising message in response to receipt of a child solicitation message transmitted by at least one other device.
Claim 15
Dependent Claim
41 words
A method as defined in claim 12 in which at least one other device, after receiving a node advertising message, communicates with the at least one device that is elected a node in the tree to facilitate becoming a child thereof.
Claim 16
Independent Claim
178 words
A system for logically organizing devices, in a digital data network comprising a plurality of devices interconnected by a communication link, into a tree structure, each of the devices having an associated suitability value, the system comprising: A. a node election element configured to enable at least one of the devices to broadcast, over the communication link, at least one node election message including the respective device's suitability value, and to enable any devices broadcasting node election messages to receive from the communication link any node election messages broadcast by other devices and to determine whether it is elected a node in the tree structure in connection with a comparison between its suitability value and suitability values in any received node election messages; and B. a tree establishment element configured to enable at least one device which is not elected a node in the tree structure to communicate with at least one device which is elected a node in the tree structure to facilitate becoming a child of the device that is elected a node in the tree.
Claim 17
Independent Claim
178 words
A system for logically organizing devices, in a digital data network comprising a plurality of devices interconnected by a communication link, into a tree structure, each of the devices having an associated suitability value, the system comprising: A. a node election element configured to enable at least one of the devices to broadcast, over the communication link, at least one node election message including the respective device's suitability value, and to enable any devices broadcasting node election messages to receive from the communication link any node election messages broadcast by other devices and to determine whether it is elected a node in the tree structure in connection with a comparison between its suitability value and suitability values in any received node election messages; and B. a tree establishment element configured to enable at least one device which is not elected a node in the tree structure to communicate with at least one device which is elected a node in the tree structure to facilitate becoming a child of the device that is elected a node in the tree.
Claim 18
Dependent Claim
52 words
A system as defined in claim 15 in which the node election element and the tree establishment element are configured to operate in at least one iteration, in said at least one iteration, during the node election step one device being elected a node, as a root node, in the tree structure.
Claim 19
Dependent Claim
59 words
A system as defined in claim 16 in which the node election element and the tree establishment element are configured to operate in a series of iterations, in a first iteration the root node being elected during the node election step, and each subsequent iteration at least one other device being elected as a node in the tree structure.
Claim 20
Dependent Claim
57 words
A system as defined in claim 17 in which the node election element is configured to enable at least one other device elected as a node in the tree structure, during the tree establishment step of at least one of said iterations, to communicate with the device elected as root node to facilitate becoming a child thereof.
Claim 21
Dependent Claim
35 words
A system as defined in claim 17 in which the node election element enables the device elected as the root node to determine the number of additional nodes to be elected during each subsequent iteration.
Claim 22
Dependent Claim
57 words
A system as defined in claim 19 in which the node election element enables the device elected as the root node to transmit, in its at least one node election message transmitted during each iteration after the first iteration, a number of nodes value identifying the number of additional nodes to be elected during the respective iteration.
Claim 23
Dependent Claim
55 words
A system as defined in claim 20 in which the node election element enables each of the devices to broadcast at least one node election message transmits, during each iteration after the first iteration, a number of nodes value corresponding to the number of nodes value transmitted by the device elected as the root node.
Claim 24
Dependent Claim
28 words
A system as defined in claim 15 in which each device is assigned a priority value, the respective device's suitability value being a function of its priority value.
Claim 25
Dependent Claim
38 words
A system as defined in claim 15 in which each device has an associated capacity value associated with a number of children that it can accommodate, the respective device's suitability value being a function of its priority value.
Claim 26
Dependent Claim
31 words
A system as defined in claim 15 in which said node election element enables at least one device to begin broadcasting at least one node election message after it is initialized.
Claim 27
Dependent Claim
59 words
A system as defined in claim 15 in which said node election element enables at least one device to broadcast a plurality of node election messages, and to stop broadcasting node election messages if it receives a node election message from another device having a higher suitability value than the suitability value associated with the at least one device.
Claim 28
Dependent Claim
48 words
A system as defined in claim 15 in which the tree establishment element enables the at least one device that is elected a node in the tree to broadcast a node advertising message over the communication link indicating that it is available as a node in the tree.
Claim 29
Dependent Claim
48 words
A system as defined in claim 26 in which the tree establishment element enables at least one device that is elected a node in the tree to broadcast a node advertising message in response to receipt of a child solicitation message transmitted by at least one other device.
Claim 30
Dependent Claim
47 words
A system as defined in claim 26 in which the tree establishment element enables at least one other device, after receiving a node advertising message, to communicate with the at least one device that is elected a node in the tree to facilitate becoming a child thereof.
Claim 31
Dependent Claim
201 words
A computer program product for use in connection with a computer, the computer program product enabling said computer to, in a digital data network comprising a plurality of computers interconnected by a communication link, organize themselves into a tree structure, each of the computers having an associated suitability value, the computer program product comprising a computer-readable medium having encoded thereon: A. a node election module configured to enable at least one of the computers to broadcast, over the communication link, at least one node election message including the respective computer's suitability value, and to enable any computers broadcasting node election messages to receive from the communication link any node election messages broadcast by other computers and to determine whether it is elected a node in the tree structure in connection with a comparison between its suitability value and suitability values in any received node election messages; and B. a tree establishment module configured to enable at least one computer which is not elected a node in the tree structure to communicate with at least one computer which is elected a node in the tree structure to facilitate becoming a child of the computer that is elected a node in the tree.
Claim 32
Dependent Claim
201 words
A computer program product for use in connection with a computer, the computer program product enabling said computer to, in a digital data network comprising a plurality of computers interconnected by a communication link, organize themselves into a tree structure, each of the computers having an associated suitability value, the computer program product comprising a computer-readable medium having encoded thereon: A. a node election module configured to enable at least one of the computers to broadcast, over the communication link, at least one node election message including the respective computer's suitability value, and to enable any computers broadcasting node election messages to receive from the communication link any node election messages broadcast by other computers and to determine whether it is elected a node in the tree structure in connection with a comparison between its suitability value and suitability values in any received node election messages; and B. a tree establishment module configured to enable at least one computer which is not elected a node in the tree structure to communicate with at least one computer which is elected a node in the tree structure to facilitate becoming a child of the computer that is elected a node in the tree.
Claim 33
Dependent Claim
54 words
A computer program product as defined in claim 29 in which the node election module and the tree establishment module are configured to operate in at least one iteration, in said at least one iteration, during the node election step one computer being elected a node, as a root node, in the tree structure.
Claim 34
Dependent Claim
61 words
A computer program product as defined in claim 30 in which the node election module and the tree establishment module are configured to operate in a series of iterations, in a first iteration the root node being elected during the node election step, and each subsequent iteration at least one other computer being elected as a node in the tree structure.
Claim 35
Dependent Claim
59 words
A computer program product as defined in claim 31 in which the node election module is configured to enable at least one other computer elected as a node in the tree structure, during the tree establishment step of at least one of said iterations, to communicate with the computer elected as root node to facilitate becoming a child thereof.
Claim 36
Dependent Claim
37 words
A computer program product as defined in claim 31 in which the node election module enables the computer elected as the root node to determine the number of additional nodes to be elected during each subsequent iteration.
Claim 37
Dependent Claim
59 words
A computer program product as defined in claim 33 in which the node election module enables the computer elected as the root node to transmit, in its at least one node election message transmitted during each iteration after the first iteration, a number of nodes value identifying the number of additional nodes to be elected during the respective iteration.
Claim 38
Dependent Claim
57 words
A computer program product as defined in claim 34 in which the node election module enables each of the computers to broadcast at least one node election message transmits, during each iteration after the first iteration, a number of nodes value corresponding to the number of nodes value transmitted by the computer elected as the root node.
Claim 39
Dependent Claim
30 words
A computer program product as defined in claim 29 in which each computer is assigned a priority value, the respective computer's suitability value being a function of its priority value.
Claim 40
Dependent Claim
40 words
A computer program product as defined in claim 29 in which each computer has an associated capacity value associated with a number of children that it can accommodate, the respective computer's suitability value being a function of its priority value.
Claim 41
Dependent Claim
33 words
A computer program product as defined in claim 29 in which said node election module enables at least one computer to begin broadcasting at least one node election message after it is initialized.
Claim 42
Dependent Claim
61 words
A computer program product as defined in claim 29 in which said node election module enables at least one computer to broadcast a plurality of node election messages, and to stop broadcasting node election messages if it receives a node election message from another computer having a higher suitability value than the suitability value associated with the at least one computer.
Claim 43
Dependent Claim
50 words
A computer program product as defined in claim 29 in which the tree establishment module enables the at least one computer that is elected a node in the tree to broadcast a node advertising message over the communication link indicating that it is available as a node in the tree.
Claim 44
Dependent Claim
50 words
A computer program product as defined in claim 40 in which the tree establishment module enables at least one computer that is elected a node in the tree to broadcast a node advertising message in response to receipt of a child solicitation message transmitted by at least one other computer.
Claim 45
Dependent Claim
49 words
A computer program product as defined in claim 40 in which the tree establishment module enables at least one other computer, after receiving a node advertising message, to communicates with the at least one computer that is elected a node in the tree to facilitate becoming a child thereof.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-10-17 | 2004-04-17 | 2004-10-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-10-17 | 2008-04-17 | 2008-10-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-10-17 | 2012-04-17 | 2012-10-17 | $7700.00 | Window Closed / Lapsed |