Network architecture, addressing and routing

• US 20030227931A1
• Filed: 11/26/2002
• Published: 12/11/2003
• Est. Priority Date: 06/06/2002
• Status: Active Grant

• Current Assignee: ARRIS Enterprises LLC (CommScope Holding Company, Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Chen, Priscilla, Huang, Yan, Hester, Lance E., Andric, Oleg, Allen, Vernon A.
• Granted Patent: US 6,788,650 B2
• Time in Patent Office: Days
• US Class Current: 370/408
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• CPC Class Codes: H04L 2101/604 Address structures or formats
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 61/50 Address allocation
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership
• CPC Class Codes: H04W 8/26 Network addressing or numbering for mobility support
• CPC Class Codes: H04W 84/00 Network topologies

Abstract

The invention provides methods (300) for organizing and assigning network address to network nodes in clusters (108, 110, 112, 114, 116, 118, 120, 212, 214, 216, 218, 220), and forming new clusters and also provides a method 700 for routing messages in clusters. According to the invention, clusters are organized into hierarchical tree arrangements, with addresses assigned in a manner that facilitates routing messages.

Claims

1. A network comprising:

a cluster, comprising a plurality of network nodes arranged in a hierarchical tree arrangement, the hierarchical tree arrangement comprising;

a cluster head network node at a root position of the hierarchical tree arrangement, and a number of layers each including one or more of the plurality of network nodes, wherein each kth layer is identified by a layer number k that indicates a number of hops from network nodes in the kth layer to the cluster head;

wherein, network nodes in at least each kth layer except for a last layer of the cluster that are children of a particular parent in a k-1th layer are identified by addresses that are assigned by a skipping a number Cskip that is substantially equal to a first number divided by a maximum permissible number of network nodes in the kth layer, wherein the first number is equal to a number of network address allocated for network nodes in the kth layer plus a number of network addresses allocated for network nodes that are decedents of network nodes in the kth layer.

2. The network according to claim 1 wherein:

each network node is permitted to have a limited number Cm of children and the maximum permissible number of network nodes in each jth layer is equal to Cm raised to the jth power; and

the first number is equal to a total number of addresses allocated for the cluster minus a sum of over j ranging from 0 to k−

1 of Cm raised to the jth power.

3. The network according to claim 1 wherein children in at least each jth layer except for the last layer of the cluster, which are children of a parent node that is identified by a parent address NID are identified by addresses that are selected by counting by a value of Cskip for the jth layer starting with the value of the parent address NID plus one.

4. The network according to claim 1 wherein Cskip is equal to the floor function of the first number divided by the maximum permissible number of network nodes in the kth layer.

5. The network according to claim 1 wherein, in the case that for a last layer of the cluster that a value of the floor function of the first number divided by the maximum permissible number of network nodes in the last layer is less than one:

for each ith parent of one or more children in the last layer, assigning addresses to a number of children equal to one less than a value of Cskip used to enumerate network nodes in layer that includes the ith parent of the children; and

assigning addresses to the children nodes in the last layer that are counted by one.

6. A method of assigning addresses to a number N of children of an ith node that is a parent node in a hierarchical tree topology cluster of a network that includes a cluster head node at a root position of the hierarchical tree topology, and a number of nodes arranged in a number Lm of layers, said layers being identified by a layer number index k that is equal to a number of hops from nodes in the kth layer to the cluster head, the method comprising the steps of:

obtaining a value Cskip by which addresses of the N children are to be spaced that is equal to;

the floor function value of a quotient of a number of addresses out of an addresses space for the cluster that remain for use by nodes in a layer that includes the number N of children, and for descendents of nodes in the layer that includes the number N of children, divided by a permissible number nodes in the layer that includes the number N of children;

;

and

using the value Cskip to determine N addresses for the number N of children, and

sending the one or more addresses to the number N of children.

7. The method according to claim 6 wherein the step of obtaining the value of Cskip comprises the step of:

calculating the value of Cskip.

8. The method according to claim 7 wherein:

each node in the cluster in at least all layers except for a last layer of the cluster is allowed to have up to a number Cm of children;

the number of addresses out of an addresses space for the cluster that remain for use by nodes in the layer that includes the number N of children, and for descendents of nodes in the layer that includes the number N of children is calculated by subtracting a sum of over the layer number index k ranging from 0 to a layer number Li associated with the parent node, of Cm raised to the kth power from a total number of address allocated for the cluster; and

the permissible number of nodes in the layer that includes the one more children is calculated by raising the number Cm of children that each node in the cluster is allowed to have to the power of a layer number Li+1 of the layer that includes the children.

9. The method according to claim 6 wherein the step of obtaining the value of Cskip comprises the step of:

reading the value of Cskip from a table in a memory.

10. The method according to claim 6 wherein the step of using the value Cskip to determine N addresses for the number N of children comprises the steps of:

counting out N addresses for the number N of children counting by Cskip starting at an address of the parent node plus one.

11. The method according to claim 6 further comprising the step of:

prior to sending the addresses to each of the N children receiving requests for addresses from the each of the children.

12. A method of routing messages in a network cluster comprising a plurality of nodes arranged in a hierarchical tree arrangement, that includes a cluster head at a root position, and a plurality of nodes arranged layers wherein each layer is designated by a layer index k that indicates a number of hops from nodes in the kth layer to the cluster head, and wherein children of each particular jth parent node are assigned addresses starting at an address value equal to an address of the jth parent node plus one and counting by a value Cskip for the layer of the children, the method comprising the step of:

at an Lth node at which a message is present, comparing a destination address NAD of the message to the Lth node'"'"'s address NAL; and

in the case that the destination address is the Lth nodes address NAL processing the message at the Lth node; and

in the case that the destination address NAD is not equal to Lth nodes address, further comparing the destination address NAD to a second number that is equal to the Lth nodes address plus a value Cskip by which addresses in a layer that includes the Lth node are counted; and

in the case that the destination address NAD is greater than the network address NAL of the Lth node, AND is less than the second number, selecting an appropriate child of the Lth node, and forwarding the message to the appropriate child; and

in the case that the destination address NAD is at least equal to the second number OR is less than the network address NAL of the Lth node, forwarding the message to the parent node of the Lth node.

13. The method according to claim 12 wherein the step of selecting the appropriate child node comprises the step of:

among a set of children of the Lth node selecting the appropriate node which has the highest network address that is less than the destination address NAD.

14. The method according to claim 12 further comprising the step of:

receiving the message at the Lth processing node.

15. A method of assigning network addresses in a cluster of a network, and establishing new clusters in the network, the method comprising the steps of:

starting at a cluster head node of a first cluster which serves as a first parent node, building a hierarchical cluster tree network of nodes that comprises a plurality of nodes arranged in a plurality of layers wherein each layer is identified by a layer index k that indicates a number of hops from nodes in the kth layer to the cluster head node;

for each kth layer in the first cluster obtaining a value Cskip by which addresses of children of parents in the kth layer are to be spaced, which is

equal to a floor function t of first number divided by a maximum permissible number of children of nodes in the kth layer, wherein the first number is equal to a number of addresses remaining to be allocated in the cluster for children of the parents in the kth layer, and descendents of children of parents in the kth layer

in the case that Cskip for the kth layer is greater than one, for each ith parent node in the kth layer having an address NID enumerating up to a number Cm of children nodes, starting at address NID+1 and counting by Cskip; and

in the case that Cskip for the kth layer is less than one, for each ith parent node in the kth layer having an address NID enumerating a number R of children nodes that is equal to a value of Cskip for the (k−

1)th layer minus one, starting at NID+1 and counting by one.

16. The method according to claim 15 further comprising the step of:

after, obtaining a value of Cskip that is less than one for a jth layer, and enumerating children of parents in the jth layer, receiving a request for an address at a node of the first cluster from an additional node; and

sending a message to the additional node instructing the additional node to establish a second cluster.

17. The method according to claim 16 further comprising the steps of:

after receiving a request for the address at the node of the first cluster from the additional node, and prior to sending the message to the additional node instructing the additional node to establish a second cluster;

sending a message to a central control node of the network requesting a new cluster address;

receiving a message including a cluster address for the second cluster from the central control node;

forwarding the cluster address for the second cluster to the additional node.

18. The method according to claim 16 wherein the number Cm is constant throughout the first cluster.