Network architecture, addressing and routing
AssigneeMotorola, Inc.
InventorsPriscilla Chen, Vernon A. Allen, Oleg Andric, Lance E. Hester, Yan Huang
Life of this patent
Estimating the term…
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.
Claims18
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.
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.
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.
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.
Dependencies are inferred from the claim text.