Network Architecture
0 Assignments
0 Petitions
Accused Products
Abstract
A system and method for self-organizing, reliable, multiple path data flow transmission of messages data on a network uses queues to transmit messages between end-user modules (EUMs) on nodes on the network. The EUMs include the end user applications with which queues are associated. A network communications manager (NCM) resident on every node manages all transmission of messages between nodes. The NCM on a given node only has knowledge of nodes that are neighbor nodes to that given node, but has knowledge of all queues associated with all EUMs. Messages are divided into EUM messages, which are placed in queues by the NCM on each node, and system messages, which are not placed in queues but are used by the NCM to determine when and where, i.e. to which neighbor node, messages may be sent. The NCM on each node chooses a neighbor node as a target node for sending EUM messages for each queue, based on the best node latency and at capacity status of each neighbor node. These target nodes are used to provide potential routes to queues and multiple path data flow for queues that carry EUM data messages for user applications. These target nodes are constantly updated to provide the best paths on an adaptive basis and to ensure that all paths are valid, improving network reliability. When choosing when to send data to a target node, each node uses tokens for flow control to ensure that target nodes do not become overloaded. The node also compares node latencies for multiple target nodes to ensure that the lowest node latency target node is chosen. By using neighbor nodes as target nodes, node latency, and at capacity information for determining when and where to send data, there is no need to maintain any global knowledge of all paths in the network. Further, the constant updating of target nodes ensures that the network maintains optimal and valid paths for messages, thus ensuring efficiency and reliability. Finally, the constant updating of target nodes ensures that reliability and efficiency are provided on an adaptive, self-organizing basis.
107 Citations
106 Claims
-
1-18. -18. (canceled)
-
19. A self-organizing network comprising:
-
(a) a plurality of nodes;
(b) at least one link interconnecting neighbouring ones of said nodes;
(c) each of said nodes being operable to maintain information about each of said other nodes that is within a first portion of said nodes, said information including;
(i) a first identity of another one of said nodes within said first portion;
(ii) for each first identity, a second identity representing a neighbouring node that is a desired step to reach the said another one of said nodes respective to said first identity;
(d) each of said nodes being operable to maintain a third identity representing a neighbouring node that is a desired step to send a request for information about said nodes in a second portion of said nodes that is not included in said first portion. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34)
-
-
35. A node for use in a self-organizing network having a plurality of other nodes and at least one link interconnecting neighbouring ones of said nodes;
- said node comprising;
(a) a computing apparatus operable to maintain information about each of said other nodes that is within a first portion of all of said other nodes, said information including;
(i) a first identity of another one of said nodes within said first portion;
(ii) for each said first identity, a second identity representing a neighbouring node that is a desired step to reach the said another one of said nodes respective to said first identity;
said computing apparatus further operable to maintain a third identity representing a neighbouring node that is a desired step to send a request for information about said nodes in a second portion of said nodes that are not included in said first portion.
- said node comprising;
-
36. A computer readable medium for storing a set of programming instructions for execution by, or on behalf of, a node forming part of a self-organizing network having a plurality of other nodes and at least one link interconnecting neighbouring ones of said nodes;
- said programming instructions for causing a computing apparatus within said node to maintain information about each of said other nodes that are within a first portion of all of said other nodes, said information including;
(a) a first identity of another one of said nodes within said first portion;
(i) for each said first identity, a second identity representing a neighbouring node that is a desired step to reach the said another one of said nodes respective to said first identity;
said programming instructions for further causing said computing apparatus to maintain a third identity representing a neighbouring node that is a desired step to send a request for information about said nodes in a second portion of said nodes that are not included in said first portion. - View Dependent Claims (37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 84, 93, 94)
- said programming instructions for causing a computing apparatus within said node to maintain information about each of said other nodes that are within a first portion of all of said other nodes, said information including;
- 57. A computer readable medium for storing a set of programming instructions for execution by, or on behalf of, a first node on a hierarchical network having a plurality of nodes and at least one link interconnecting each of said nodes, said instructions causing a computing apparatus to select and maintain information about a parent node, said parent node comprising a neighbouring node in said network that is above said first node in respect to the hierarchy of said network or equal to said first node when there is no node that is above said first node.
- 63. A computer readable medium for storing a set of programming instructions for execution by, or on behalf of, a first node on a self-organizing network having a plurality of nodes and at least one link interconnecting said nodes, said instructions causing a computing apparatus to select and remove information about one or more missing nodes in said network by delaying the sending of predetermined classes of updates to said network.
- 67. A computer readable medium for storing a set of programming instructions for execution by, or on behalf of, a first node on a self-organizing network having a plurality of nodes and at least one link interconnecting each of said nodes, said instructions causing a computing apparatus to select and remove information about one or more missing nodes in said network by sending predetermined classes of updates to said network when a predetermined internal state is reached.
- 71. A computer readable medium for storing a set of programming instructions for execution by, or on behalf of, a first node on a self-organizing network having a plurality of nodes and at least one link interconnecting each of said nodes, said instructions causing a computing apparatus to identify the route between a source node and a destination node.
- 76. A computer readable medium for storing a set of programming instructions for execution by, or on behalf of, a first node on a self-organizing network having a plurality of nodes and at least one link interconnecting each of said nodes, said instructions causing a computing apparatus to assign an importance value to updates that are to be sent over said network.
- 82. A computer readable medium for storing a set of programming instructions for execution by, or on behalf of, a first node on a self-organizing network having a plurality of nodes and at least one link interconnecting each of said nodes, said instructions causing a computing apparatus to attach a specific node number identifying said first node to data packets being sent by said first node.
- 85. A computer readable medium for storing a set of programming instructions for execution by, or on behalf of, a first node on a self-organizing network having a plurality of nodes and at least one link interconnecting each of said nodes, said instructions causing a computing apparatus to forward messages from a source node to a destination node via neighbors depending on the latency to the destination node via said neighbors.
-
90. A computer readable medium for storing a set of programming instructions for execution on a first node, where said first node forms part of a self-organizing network having a plurality of other nodes executing similar sets of said programming instructions and at least one link interconnecting neighbouring ones of said nodes;
- said programming instructions causing said first node to;
(a) determine the identity of a parent node, wherein said parent node is a neighboring node to said first node that has one or more desired characteristics;
(b) deliver instructions to a neighboring node from said first node that will cause said neighboring node to deliver instructions to its determined parent node; and
(c) deliver instructions in response to said neighboring node that has delivered instruction to said node to deliver instructions to its determined parent node. - View Dependent Claims (91, 92)
- said programming instructions causing said first node to;
-
95. A self-organizing network comprising:
-
(a) a plurality of interconnected nodes, wherein neighbouring nodes are interconnected by at least one link;
(b) each of said nodes being operable to maintain information about at least one of said other nodes, said information including in respect to a representative first node;
(i) a first identity identifying a second node that is a best neighbour to said first node according to one or more pre-determined factors;
(ii) for each first identity, a second identity identifying a third node that is a next best neighbour to said first node according to one or more pre-determined factors.
-
-
96. A computer implemented process for spreading network knowledge within a network having a plurality of nodes, each said node being linked to a neighbouring node by at least one link, said process comprising the steps of:
-
(a) each node determining the presence of at least one neighbouring node in said network;
(b) each said node exchanging information with neighbouring nodes in said network concerning the presence of said neighbouring nodes;
(c) each said node updating its information concerning neighbouring nodes in said network based on said information received from said neighbouring nodes; and
(d) repeating said steps at desired intervals.
-
-
97. A computer implemented process for delivering payload data from an originating node to a destination node in a network having a plurality of nodes, each said node being linked to a neighbouring node by at least one link, and at least some of said nodes having information concerning certain service characteristics for said neighbouring nodes, said process comprising the steps of:
-
(a) identifying one or more desired service characteristics associated with payload data intended for delivery in said network; and
(b) selecting a preferred delivery path among said nodes in said network for said payload data based upon said desired service characteristics and said service characteristic information. - View Dependent Claims (98)
-
-
99. A computer implemented process for spreading instructions that control the spread network knowledge within a network having a plurality of nodes, each said node being linked to a neighbouring node by at least one link, said process comprising the steps of:
-
(a) each node establishing a connection with one or more neighboring nodes;
(b) each node determining the identity of a parent node, wherein said parent node is a neighboring node to said first node that has one or more desired characteristics;
(c) each node that receives particular instructions from a neighboring node delivering instructions to its determined parent node;
(d) each node that receives particular instructions from a parent node in response to instructions it sent to said parent node sending instructions to said neighbor node that sent said node instructions that caused said node to send instructions to said parent node; and
(e) each node repeating said steps at desired intervals.
-
-
100. A computer implemented process for increasing the frequency that a node sends updates about a destination node the closer said node is to a data path to said destination node, said process comprising the steps of:
-
(a) each node establishing a connection with one or more neighboring nodes;
(b) each first node determining a rank to all nodes based on its proximity to said node or a data path heading towards said node;
(c) each first node sending node updates to neighbor nodes more frequently based on rank of said nodes; and
(d) each node repeating said steps at desired intervals.
-
-
101. A computer implemented process for removing information about a node after said node is removed from a network, said process comprising the steps of:
-
(a) each node delaying the sending of a node update to a neighbor if previous update about said node indicated that there was no route to said node through said sending node;
(b) each node delaying the sending of a node update to a neighbor if no previous update about said node had been sent by said sending node to said neighbor node; and
(c) each node repeating said steps at desired intervals.
-
-
102. A computer implemented process for removing information about a node after said node is removed from a network, said process comprising the steps of:
-
(a) each node sending an update about some node in the network indicating that said sending node has no route to said node in the network if said sending node determines that the cumulative service characteristics to reach said network node have reached a specified state; and
(b) each node repeating said step at desired intervals.
-
-
103. A computer implemented process for ranking importance of node updates based on the proximity to structures that affect said nodes, said process comprising the steps of:
-
(a) each node establishing a connection with one or more neighboring nodes;
(b) each node ranking all nodes that it has stored information on based on said nodes proximity to structures that affect said nodes;
(c) each node sending updates about said nodes to said neighbor nodes on a relatively more frequent basis the higher the rank of said nodes; and
(d) each node repeating said steps at desired intervals.
-
-
104. A computer implemented process for sending data to destination nodes via neighbor nodes based on the latency provided by said neighbor nodes to said destination nodes, said process comprising steps of:
-
(a) each node establishing a connection with one or more neighboring nodes;
(b) each node forwarding messages for a destination node to a neighbor node that provides a latency value that is less or equal to the latency of the queue of messages stored on said node for said destination node; and
(c) each node repeating said steps at desired intervals.
-
-
105. A computer implemented process for quickly routing data from node to node by using locally assigned numbers that represent the names of nodes in the network, said process comprising steps of:
-
(a) each node establishing a connection with one or more neighboring nodes;
(b) each node using an internal number to represent the names of nodes that it stores information on;
(c) each node determining which neighbor node to send data packet for said destination node by using its internal number to efficiently look up the preferred neighbor;
(d) each node before sending a data packet for a destination node to a neighbor node sending a message to said neighbor node that allows said neighbor node to determine which internal number represents the name of said destination node;
(e) each node sending a data packet for a destination node to a neighbor node with said nodes internal number representing the name of said destination node attached to said data packet;
(f) each node upon receipt of said internal number performing a lookup to translate said neighbors internal number into said nodes internal number; and
(g) each node repeating said steps at desired intervals.
-
-
106. A computer implemented process for limiting the number of different nodes that a neighbor node is sent updates for, said process comprising the steps of:
-
(a) each node establishing a connection with one or more neighboring nodes;
(b) each node ranking all nodes that it has stored information on based on said nodes proximity to structures that affect said nodes;
(c) each node telling its neighbors the maximum number of nodes it wants to be sent updates for;
(d) each neighbor node sending said node its highest ranked nodes up to the maximum count requested by said node; and
(e) each node repeating said steps at desired intervals.
-
Specification