Cluster control in network systems

• US 7,120,681 B2
• Filed: 01/29/2002
• Issued: 10/10/2006
• Est. Priority Date: 01/30/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Scotton, Paolo, Iliadis, Ilias, Frelechoux, Laurent, Osborne, Michael
• Primary Examiner(s): DINH, DUNG C
• Application Number:
  US10/059,638
• Publication Number:
  US 20020103893A1
• Time in Patent Office: 1,715 Days
• Field of Search: 709220-222, 709227-229, 370/313, 370/338, 370/349
• US Class Current: 709/221
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04W 4/06 Selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS]; Services to user groups; One-way selective calling services
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership
• CPC Class Codes: H04W 8/24 Transfer of terminal data
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Methods and apparatus are provided for controlling the clustering of nodes which implement a cluster-based routing protocol in a data communications network system where the system comprises a plurality of such nodes which are interconnectable to form a plurality of ad hoc networks. For each node which is a member of a cluster, cluster control information (CCMs) is maintained, this cluster control information being dependent on the size of at least the cluster of which that node is a member. On connection of two nodes which are members of two respective clusters, each of the two nodes transmits its cluster control information to the other node, and then determines whether a clustering condition is satisfied. In each node, the clustering condition is dependent on the cluster control information maintained for that node and the cluster control information received from the other node. In each node, if the clustering condition is satisfied, the node then communicates a clustering agreement to the other node. If the clustering conditions of both nodes are satisfied for the two clusters, the two nodes exchange routing information to merge the two clusters.

Claims

1. A method for controlling the clustering of nodes implementing a cluster-based routing protocol in a data communications network system comprising a plurality of such nodes which are interconnectable to form a plurality of ad hoc networks, the method comprising:

for each node which is a member of a cluster, maintaining cluster control information dependent on the size of at least the cluster of which that node is a member;

on connection of two nodes which are members of two respective clusters, in each of the two nodes transmitting the cluster control information maintained for that node to the other of the two nodes, determining whether a clustering condition, dependent on the cluster control information maintained for that node and the cluster control information received from the other node, is satisfied and, if so, communicating a clustering agreement to the other node; and

if the clustering condition of each of the two nodes is satisfied for said two clusters, in each of the two nodes exchanging routing information with the other node and merging the two clusters.

2. A method according to claim 1 wherein the cluster control information is dependent on at least one of:

the number of nodes in the cluster, the number of links in the cluster, the number of network addresses associated with the cluster and stored in a routing database of the node, and the amount of data stored in said routing database of the node.

3. A method according to claim 1 wherein, for each node which is a member of a cluster in an ad hoc network extending beyond the cluster, the cluster control information is dependent on the size of that ad hoc network.

4. A method according to claim 3 wherein, for each node which is a member of a cluster in an ad hoc network extending beyond the cluster, the cluster control information is dependent on at least one of:

the number of nodes in the ad hoc network, the number of links in the ad hoc network, the number of network addresses associated with the ad hoc network and stored in a routing database of the node, and the amount of data stored in said routing database of the node.

5. A method according to claim 1 wherein the cluster-based routing protocol is such that a node can be a member of only one cluster at any time.

6. A method according to claim 5 wherein the cluster-based routing protocol is PNNI.

7. A method according to claim 5 further comprising the step of maintaining said cluster control information for each node of said plurality of nodes, wherein any node which is not connected in a cluster with any other nodes is notionally a member of a cluster consisting of a single node.

8. A method according to claim 1 wherein the cluster-based routing protocol is such that a node can be a member of a plurality of clusters via respective interfaces with those clusters, and wherein, for a node which has interfaces with a plurality of clusters, the step of maintaining cluster control information comprises maintaining cluster control information for each of the plurality of clusters.

9. A method according to claim 8 wherein the cluster-based routing protocol is one of OSPF and IS-IS.

10. A method according to claim 8 further comprising the step of maintaining said cluster control information for each node of said plurality of nodes, wherein any node which is not connected in a cluster with any other nodes via a said interface of that node for connection in a cluster is notionally a member via that interface of a cluster consisting of a single node.

11. A method according to claim 1 wherein the cluster control information for a node is maintained in latter said node.

12. A method according to claim 1 wherein the step of communicating a clustering agreement comprises transmitting the clustering agreement to said other node.

13. A method according to claim 1 wherein the cluster control information transmitted by said two nodes on connection thereof is transmitted according to a first protocol prior to activation of said routing protocol.

14. A method according to claim 1 wherein the cluster control information transmitted by said two nodes on connection thereof is embedded in Hello messages of said routing protocol.

15. A method according to claim 1 wherein:

for each said node which is a member of a cluster, a predetermined cluster identifier for that cluster is associated with the node;

the method includes, on connection of said two nodes, in each node transmitting the cluster identifier for the cluster of which that node is a member to the other of the two nodes; and

said clustering condition includes a criterion that the cluster identifiers for said two clusters of the two nodes match.

16. A method according to claim 1 wherein:

the routing protocol is a hierarchical routing protocol defining a plurality of hierarchy levels for clustering of nodes;

for each said node which is a member of a cluster, a level identifier, indicative of the hierarchy level of that cluster, is associated with the node;

the method includes, on connection of said two nodes, for each of the two nodes transmitting the level identifier for the cluster of which that node is a member to the other of the two nodes; and

said clustering condition comprises a criterion that the level identifiers for said two clusters of the two nodes match.

17. A method according to claim 16 wherein the clustering condition for a said node comprises a criterion that no node, which is embodied by the same physical node and for which the clustering condition, and that of the connected node on establishment of said connection, is satisfied, exists in a predetermined subset of said hierarchy levels of the routing protocol.

18. A device for connection as a node in a data communications network system comprising a plurality of such nodes which are interconnectable to form a plurality of ad hoc networks, wherein the device comprises control logic for implementing a cluster-based routing protocol, memory for storing routing information in accordance with said routing protocol, and communications circuitry for communication of data with other said nodes with which the device is connected in use, wherein the control logic is configured such that:

when the device is connected as a node which is a member of a cluster, the control logic maintains cluster control information in said memory, the cluster control information being dependent on the size of at least the cluster of which that node is a member;

when the device is connected as a node which is a member of a cluster, on connection of that node to another said node which is a member of another cluster, the control logic controls transmission to the other node, via said communications circuitry, of the cluster control information maintained in said memory, determines whether a clustering condition, dependent on the cluster control information maintained in the memory and cluster control information received from said other node via said communications circuitry, is satisfied, and if so controls communication of a clustering agreement to the other node; and

if said clustering condition is satisfied and a said clustering agreement is communicated to the control logic from said other node, the control logic controls exchange of routing information with the other node to merge the two clusters of the two nodes.

19. A data communications network system comprising a plurality of devices according to claim 18 interconnected to form a plurality of ad hoc networks.

20. A computer program product comprising a computer usable medium having embodied therein computer readable program code means for causing a processor of a device for connection as a node implementing a clusterbased routing protocol in a data communications network system comprising a plurality of such nodes which are interconnectable to form a plurality of ad hoc networks, to perform a cluster control method comprising the steps of:

when the device is connected as node which is a member of a cluster, maintaining cluster control information dependent on the size of at least the cluster of which that node is a member;

when the device is connected as node which is a member of a cluster, on connection of that node to another said node which is a member of another cluster, transmitting said cluster control information to the other node, determining whether a clustering condition, dependent on the cluster control information transmitted to the other node and cluster control information received from the other node, is satisfied and, if so, communicating a clustering agreement to the other node; and

if said clustering condition is satisfied and a said clustering agreement is received from the other node, exchanging routing information with the other node and merging the two clusters of the two nodes.