Connection mechanism for energy-efficient peer-to-peer networks

Abstract

A communications system comprising a plurality of nodes communicatively connected via a communications network, each node comprising a processing circuit and network interface circuitry connected to the processing circuit, each node being configured to connect to the communications network and to communicate with other nodes of the communications system, the communications system comprising at least one cluster of nodes, wherein one of the nodes of the cluster is operable to perform a cluster head role connecting the cluster to the communications network, and wherein the cluster is operable to implement a mechanism for transferring the cluster head role from one node of the cluster to another node of the cluster.

Claims

1. A method of operating a system of a plurality of processing devices communicatively connected via a peer-to-peer overlay network; wherein each processing device is configured to connect to the peer-to-peer overlay network as a peer node or as a client node; wherein a client node is connectable to the peer-to-peer overlay network via a peer node; wherein client nodes do not have routing or storage responsibilities; the method comprising: causing one of a plurality of nodes of a cluster to perform a cluster head role connecting the cluster to the peer-to-peer overlay network, the processing device of the cluster head node thereby acting as a peer while other nodes of the cluster are attached to the cluster head as clients; wherein each node of the cluster is associated with a private node identity and a public node identity; the public node identity being employed during the creation of a new cluster, in which the cluster only has one node, this node being the cluster head; the public node identity of the initial cluster head subsequently identifying the cluster within the overlay network as a cluster node identity; wherein the cluster node having the cluster head role enables the other cluster nodes, which are attached to the cluster head as clients, to sleep in an energy-conserving state; wherein the processing device, as cluster head role, transfers the cluster head role to another node of the cluster, such that the cluster head role is handed over from one node to another among the nodes in the cluster.

2. The method of claim 1, wherein when a node joins the overlay network for creation of a new cluster, there is created a cluster table containing an entry, indexed with the private node identity of the joining node, a next cluster head time; and a pre-configured cluster head period for that node.

3. The method of claim 1, wherein the peer-to-peer communications network is using Resource Location and Discovery Protocol (RELOAD) such that an attach request and an attach answer are used.

4. The method of claim 1: wherein when a subsequent node joins the cluster, the cluster table is updated with a further entry, indexed with the private node identity of the subsequent node, a next cluster head time for the subsequent node and a pre-configured cluster head period for the subsequent node, wherein the subsequent node may act as a client and enter a sleep mode until it is time to initiate a cluster head handover.

5. The method of claim 4: wherein when the cluster head period of the current cluster head is over, a cluster head handover process is initiated, in which a next cluster node according to a further entry in the cluster table is joining the overlay network as a peer cluster head, and is replacing the previous cluster head of the cluster table and is taking over the cluster head role; wherein the handover process comprises the next cluster node getting a routing table from the old cluster head, as well as connecting to all the neighbor nodes of the previous cluster head in the overlay network, wherein the next cluster head employs the same public node identity as the old cluster head.

6. The method of claim 5: wherein the next cluster head node sends an attach request to the previous cluster head node to initiate a cluster handover; wherein the attach request message comprises an indication that the next cluster node is a client and an indication of a request to receive any recurring update messages; wherein the next cluster head uses the cluster node identity as its sender identity instead of the private node identity of the next cluster head.

7. A processing device in a system of a plurality of processing devices communicatively connected via a peer-to-peer overlay network; wherein each processing device In the network is configured to connect to the peer-to-peer overlay network as a peer node or as a client node; wherein client nodes do not have routing or storage responsibilities; wherein a client node is connectable to the peer-to-peer overlay network via a peer node; the processing device comprising: comprising a processing circuit; network interface circuitry connected to the processing circuit; memory containing instructions executable by the processing circuit; the instructions, when executed by the processing circuit, causing the processing device to perform a cluster head role connecting a cluster of nodes to the peer-to-peer overlay network such that the processing device thereby acts as a peer while other cluster nodes are attached to the cluster head as clients; wherein the processing device, as cluster head role, is configured to transfer the cluster head role to another node of the cluster, such that the cluster head role is handed over from one node to another among the nodes in the cluster; wherein the cluster node having the cluster head role enables the other cluster nodes, which are attached to the cluster head as clients, to sleep in an energy-conserving state wherein each of the nodes of the cluster are associated with a private node identity and a public node identity; the public node identity being employed during the creation of a new cluster, in which the cluster only has one node, this node being the cluster head; the public node identity of the initial cluster head subsequently identifying the cluster within the overlay network as a cluster node identity.

8. The processing device of claim 7, wherein the peer-to-peer communications network is using a Resource Location and Discovery Protocol (RELOAD) such that an attach request and an attach answer are used.

9. The processing device of claim 7: wherein a next cluster head node sends an attach request to the previous cluster head node to initiate a cluster handover; wherein the attach request message comprises an indication that the next cluster node is a client and an indication of a request to receive any recurring update messages; wherein the next cluster head uses the cluster node identity as its sender identity instead of the private node identity of the next cluster head.

10. The processing device of claim 7, wherein when a node joins the overlay network for creation of a new cluster, there is created a cluster table containing an entry, indexed with the private node identity of the joining node, a next cluster head time; and a pre-configured cluster head period for that node.

11. The processing device of claim 10: wherein, when a subsequent node joins the cluster, the cluster table is updated with a further entry, indexed with the private node identity of the subsequent node, a next cluster head time for the subsequent node and a pre-configured cluster head period for the subsequent node; wherein the subsequent node may act as a client and enter a sleep mode until it is time to initiate a cluster head handover.

12. The processing device of claim 11; wherein, when the cluster head period of the current cluster head is over, a cluster head handover process is initiated, in which a next cluster node according to a further entry in the cluster table is joining the overlay network as a peer cluster head, and is replacing the previous cluster head of the cluster table and is taking over the cluster head role; wherein the handover process comprises the next cluster node getting a routing table from the old cluster head, as well as connecting to all the neighbor nodes of the previous cluster head in the overlay network, wherein the next cluster head employs the same public node identity as the old cluster head.

13. A computer program product stored in a non-transitory computer readable medium for controlling operation of a system of a plurality of processing devices communicatively connected via a peer-to-peer overlay network; wherein each processing device is configured to connect to the peer-to-peer overlay network as a peer node or as a client node; wherein a client node is connectable to the peer-to-peer overlay network via a peer node; wherein client nodes do not have routing or storage responsibilities; the computer program product comprising software instructions which, when run on one or more processing circuits of the overlay network: causes one of a plurality of nodes of a cluster to perform a cluster head role connecting the cluster to the peer-to-peer overlay network, the processing device of the cluster head node thereby acting as a peer while other nodes of the cluster are attached to the cluster head as clients; wherein each node of the cluster is associated with a private node identity and a public node identity; the public node identity being employed during the creation of a new cluster, in which the cluster only has one node, this node being the cluster head; the public node identity of the initial cluster head subsequently identifying the cluster within the overlay network as a cluster node identity; wherein the cluster node having the cluster head role enables the other cluster nodes, which are attached to the cluster head as clients, to sleep in an energy-conserving state; wherein node performing the cluster head role transfers the cluster head role to another node of the cluster, such that the cluster head role is handed over from one node to another among the nodes in the cluster.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The above and/or additional objects, features and advantages of embodiments of the methods, systems and devices disclosed herein, will be further elucidated by the following illustrative and non-limiting detailed description of embodiments of the methods, systems and devices disclosed herein, with reference to the appended drawings, wherein:

(2) FIG. 1 schematically illustrates parts of an embodiment of a communications system.

(3) FIG. 2 shows a schematic block diagram of a processing device operable as a node of a P2P overlay network as described herein.

(4) FIG. 3 shows an example of a process for connecting a client node to an overlay network.

(5) FIG. 4 shows an example of the message structure of an attach request for attaching a node to another node of a P2P overlay network.

(6) FIG. 5 shows a flow diagram of an example of a process for admitting a new client node by an admitting peer.

(7) FIG. 6 shows a flow diagram of a process, performed by a processing device, for connecting to an overlay network.

(8) FIG. 7 schematically illustrates an example of a part of an overlay network including a cluster as described herein.

(9) FIG. 8 shows a flow diagram of an example of a process for creating a new cluster.

(10) FIG. 9 shows a flow diagram of an example of a process for joining a new cluster, allowing a processing device to join an existing cluster as a new node.

(11) FIG. 10 shows a message flow diagram illustrating the messages exchanged between the cluster head and the new cluster node joining the cluster.

(12) FIG. 11 shows the message flow between the current cluster head and the next cluster head during an example of a cluster head handover.

(13) FIG. 12 shows a processing device comprising a sending module.

(14) FIG. 13 shows a processing device comprising a peer module; a connection request module; a determination module and a rejection module.

(15) FIG. 14 shows a processing device comprising a cluster forming module and a cluster head transfer module.

DETAILED DESCRIPTION

(16) In the following description, reference is made to the accompanying figures, which show by way of illustration how embodiments of the methods, systems and devices disclosed herein may be practiced.

(17) FIG. 1 schematically illustrates parts of an embodiment of a communications system, in particular parts of a P2P overlay network of an underlying communications system. The system comprises processing devices 101, 102, connected to the overlay network as nodes of the overlay network. The nodes are connected to one another by logical links 104 so as to form the topology of the overlay network. It will be appreciated that each link may be implemented by a communications path of the underlying communications network where the path may involve a direct connection between two nodes or it may involve multiple entities of the underlying communications network.

(18) The overlay network comprises a first type of nodes 101, also referred to as peers. Peers 101 and their interconnecting links 104 define the overall topology of the network and the peers 101 participate in the routing of messages between nodes other than messages to from nodes to which a peer is directly connected. The peers further provide storage capacity for information related to the overlay network, such as routing information, network directories, etc.

(19) The overlay network further comprises a second type of nodes 102, also referred to as clients. Each client 102 is connected to the overlay network via an admitting peer 101. Hence, a client only participates in the routing of messages directed to it or originating from it.

(20) In the example of FIG. 1, the peers are arranged in a ring-shaped topology, e.g. using the Chord protocol. The arrangement of nodes and links, as well as the routing and storage tasks to be performed by the nodes may be defined in an overlay algorithm and follow a suitable protocol, such as the RELOAD protocol.

(21) Further details of the RELOAD protocol and examples of an embodiment of a P2P overlay, its components and the conventional attach procedures may be found in the internet draft A Constrained Application Protocol (CoAP) Usage for REsource Location And Discovery (RELOAD) of Aug. 20, 2012 by J. Jimenez, J. Lopez-Vega, J. Maenpaa and G. Camarillo, available online at: http://tools.ietf.org/html/draft-jimenez-p2psip-coap-reload-02, and in the internet draft Resource Location And Discovery Base Protocol of Nov. 5, 2012 by C. Jennings, B. B. Lowekamp, E. K. Rescorla, S. A. Baset, and H. G. Schulzrinne, available online at http://tools.ietf.org/html/draft-ietf-p2psip-base-23.

(22) It will be appreciated, however, that the network may implement a different network topology and/or implement different signalling protocols and/or overlay algorithms.

(23) FIG. 2 shows a schematic block diagram of a processing device 201 operable as a node of a P2P overlay network as described herein, e.g. the overlay network of FIG. 1. The processing device 201 comprises a controller 212 and other circuitry and/or hardware components 213 suitably connected to the controller 212. The controller 212 comprises a processing circuit 216 and a memory 217 connected to the processing circuit. The processing circuit 216 may be a microprocessor, CPU, or other suitable processor. The memory 217 may be any suitable volatile or non-volatile memory or other data storage device. The memory 217 may have stored thereon data 218 and computer program code 219, the program code 219 being adapted to cause the processing circuit 216 to perform processes to be performed by the processing device, such as the steps of embodiments of the method described herein that are performed by the processing device 201, e.g. steps described with reference to FIGS. 3, 6, 8-11 below. In particular, the memory may have stored thereon a private node-ID 261 and a public node-ID 262 and corresponding cryptographic keys 263 and 264, respectively, associated with respective ones of the node-IDs. The other hardware components/circuitry 213 may optionally comprise a sensor device 215 for detecting a physical quantity, a user interface, e.g. a display, keyboard, keypad, touch screen, and/or the like. The processing device 201 further comprises network interface circuitry, such as radio circuitry 214 for radio communication via an antenna 220 with a radio access network. The example of FIG. 2 shows a processor-implemented embodiment, but alternative embodiments could use hardwired elements or a combination of both. The processing device may be connectable to the overlay as a peer or as a client. It will be appreciated, however, that, depending on the computational resources, usage patterns, storage capacity, and/or power supply, some processing devices may be more suitable for connection as clients rather than as peers, while other processing devices may be connectable equally well as peers and as clients or more suitably connectable as peers.

(24) In the following, embodiments will be described in the context of RELOAD and, in particular, modifications to prior art RELOAD systems will be described that facilitate support of resource-constrained peers (e.g. actuators) and battery-powered clients (e.g. sensors) in RELOAD overlays. Moreover, an embodiment of a mechanism will be described in the context of RELOAD that allows battery-powered nodes that cannot connect as clients to build a cluster in order to share the burden of participating on the overlay operations as a peer.

(25) FIG. 3 shows an example of a process for connecting a client node to an overlay network, e.g. the overlay network of FIG. 1 such as a RELOAD overlay network.

(26) In step S301, the processing device 302 requesting to connect to the network sends an attach request 320 to a peer node 301 of the network.

(27) FIG. 4 shows an example of the message structure of the attach request 320, e.g. a modified RELOAD Attach Request message. In particular, the attach request 320 comprises a field 421 indicating whether the requesting device 302 requests attachment as a client node. It will be appreciated that the attach request 320 may comprise a number of additional fields. A specific example of an attach request may have the following structure:

(28) TABLE-US-00001 struct { opaque ufrag<0..2{circumflex over ()}8-1>; opaque password<0..2{circumflex over ()}8-1>; opaque role<0..2{circumflex over ()}8-1>; IceCandidate candidates<0..2{circumflex over ()}16-1>; Boolean send_update; Boolean client_node; } AttachReq;

(29) Where the field 421 is implemented as a Boolean field client_node. This field is set to TRUE when the node 302 wants to attach as a client, and to FALSE otherwise (e.g. when the node 302 is a joining peer or a finger).

(30) The attach request may further comprise a field 422 indicating whether the requesting node 302 wishes to receive periodic or otherwise recurring updated messages. Again, this field may be implemented as a Boolean field and named send_update. An example of the use of such a field will be described in greater detail below.

(31) Again referring to FIG. 3, in step S302, upon receipt of the attach request 320, the admitting node 301 determines whether it still has sufficient resources to admit an additional client attached to it. For example, the admitting node may determine whether a predetermined maximum number of attached clients has already been reached, or the admitting node may make the determination based on other criteria, e.g. current memory usage, etc.

(32) The receiving node can thus choose to accept the new connection, or reject it if the attaching node is a client or a finger, but the peer does not have enough resources to accept it (e.g. too many connections), or the overlay configuration does not allow clients (i.e. <clients-permitted> false </clients-permitted>). A finger is a peer node that is already part of the overlay.

(33) Based on the determination of step S302, the admitting node 301 returns an answer message 330 to the requesting device 302. If the admitting node 301 has determined that the additional client 302 may be admitted, the attach answer is an acceptance message and followed by further connection steps, e.g. as described in the RELOAD specification (ibid.). If the admitting node 301 has determined that the additional client 302 cannot be admitted, the attach answer is a rejection message. It may cause the client to connect as a peer or to start a new cluster of clients or to join an existing cluster, as described herein.

(34) To this end, the rejecting answer message may comprise an error code indicating to the requesting node 302 that the request is rejected. Such an error code Error_Connection_Rejected may be defined as: Error_Connection_Rejected: An attach procedure cannot be performed because the peer does not have enough resources, or the overlay configuration does not allow clients.

(35) This error code is included in an Attach Answer message when the peer does not have enough resources to accept a new connection from a client or a finger connection. In some embodiments, this error is not employed to reject the connection from a joining peer in Chord. Although both fingers and joining peers may send an Attach Request with a client_node=FALSE, they can be distinguished by its node-ID. In Chord, joining peers have a node-ID between the admitting peer and its successor. Otherwise the attaching peer only wants to set up a finger and may be rejected. Notice that in Chord a joining peer replaces the connection to one of the successor peers of the admitting peer, and thus may be accepted without increasing the total number of connections.

(36) In any event, the attach answer message does not need to include the client_node field, but it may include the field, e.g. set to a default value such as FALSE, in order to use the same message structure for both messages.

(37) Rejected fingers may look for a different node in the same section of a Chord ring, whereas a rejected client may try to join as a peer and create a new cluster, as is described in greater detail below. In particular, in the context of Chord, a node may have a finger connection with several alternative nodes. Depending on which node it connects to, routing will work slightly differently since different nodes manage different parts of the overlay. Therefore, depending on which node it connects to, a particular message may be routed through a different set of nodes.

(38) FIG. 5 shows a flow diagram of an example of a process for admitting a new client node by an admitting peer, e.g. admitting peer 301 of FIG. 3.

(39) In initial step S501, the admitting node receives an attach request from a requesting new node, the attach request comprising a client_node field and a send_update field, as described above. In step S502, the admitting node determines whether client_node field is set to TRUE or FALSE. If the client_node field is FALSE, the process continues at step S503 by performing an attach process for a new peer, e.g. as described in the RELOAD specification (ibid.). If the client_node field is set to TRUE, the admitting peer proceeds at step S504 and determines whether the admitting node can admit a further client, e.g. as described in connection with FIG. 3 above. If the admitting peer determines that it cannot admit further clients, the process proceeds at step S505 where the admitting peer sends an attach answer message to the requesting node including the above error code Error_Connection_Rejected. Otherwise, if the admitting peer determines that it can admit an additional client, the process proceeds at step S506 where the admitting peer sends an attach answer message initiating the attach process, e.g. as described in the RELOAD specification (ibid.). In step S507, the process determines whether the send_updates field in the attach request was set to TRUE or FALSE. If the send_update field is set to TRUE, the process proceeds at step S508 where the admitting peer sends periodic update messages to the newly admitted client. Otherwise, if the send_update field is set to FALSE, the process proceeds at step S509 where the admitting peer does not send any periodic update messages to the newly admitted client.

(40) Hence, a mechanism is introduced allowing a client to use the send_update flag to signal to the admitting peer whether it wishes to receive periodic updates. In order to prevent the admitting peer from sending periodic updates to intermittent-connected clients, a client (client_node=TRUE) may set this flag to FALSE. In that case the peer marks that connection as update-free and refrains from sending any update message through it. On the other hand, clients that still want to receive updates, including an immediate one, may set this flag to TRUE (send_update=TRUE). For non-client nodes (client_node=FALSE) the send_update flag may indicate to the admitting peer that the newly attached peer requests an immediate update message once the attach procedure is over.

(41) Clients that do not receive updates may still periodically check whether the current peer they are connected to is still the best one (e.g. the one responsible for its node-ID). This can be done by different means, for example by sending Route Requests to its current peer with send_update=TRUE, or sending a Ping message to its own node-ID in order to know which peer is the responsible one.

(42) FIG. 6 shows a flow diagram of a process, performed by a processing device, for connecting to an overlay network as a client node, e.g. the overlay network of FIG. 1. For example, the processing device may be a battery-powered device such as a sensor, or another resource-constrained device that wishes to connect to the overlay network in a resource-conserving manner.

(43) To this end, in initial step S601, the processing device sends an attach request to its admitting peer, e.g. via a bootstrap node (e.g. the initial peer in the overlay network). The attach request may include a client_node field set to TRUE so as to allow the admitting peer to determine which type of node is attaching by checking its node-ID and the client_node field. Thus, the admitting peer may either accept or reject the attach request and send a corresponding answer message. Accordingly, in step S602, the processing device receives the answer message. If the answer message indicates an acceptance of the attach request, the process proceeds at step S603 performing an attachment as a client, e.g. as described in the RELOAD specification (ibid.). If the answer message indicates a rejection of the request, e.g. by means of an Error_Connection_Rejected error code as explained above, the process proceeds at step S604, where the processing device attaches as a peer and establishes a new cluster of nodes, as described in greater detail in the following.

(44) Generally, it will be appreciated that, as the number of clients in the overlay increases, resource-constrained peers (e.g. actuators) will start rejecting them as clients. Therefore the only way for rejected clients to connect to the overlay is to join it as full peers. However, since being a peer implies being awake all the time in order to forward messages and store resources, disclosed herein is a mechanism allowing battery-powered or otherwise resource-constrained processing devices to group together to build a cluster of devices, where at a given point in time only one of them acts as a peer. This member of the cluster will also be referred to as the cluster head. The other members of the cluster, in the following also called cluster nodes, are attached to the cluster head as clients, and thus can be sleeping most of time, i.e. only one of them needs to be awake at each point in time other than during a cluster head handover or when a new node joins the cluster.

(45) FIG. 7 schematically illustrates an example of a part of an overlay network including a cluster as described herein. The overlay network comprises peer nodes 711 and 713, and a cluster comprising nodes 701, 721, and 751. In the example of FIG. 7, node 701 acts as cluster head while nodes 721 and 751 are cluster nodes.

(46) In order to share the burden of being awake and acting as a peer, the cluster head role is rotated periodically among all nodes forming the cluster. Therefore, when the node being the cluster head ends its shift, a cluster node should awake and become the new cluster head. The period of time a node acts as the cluster head will be referred to as the cluster head period; its length may be application-specific. For instance, in an application that employs smartphones or otherwise rechargeable sensors (e.g. by means of a solar panel), it may be desirable to select the cluster head period to be smaller than the estimated battery duration while being a cluster head. The cluster head period can be statically configured in the nodes or computed dynamically (e.g. choosing the minimum one of all cluster nodes).

(47) The process of transferring the cluster head role from one member of the cluster to another member of the cluster is called cluster head handover; it involves the new cluster head joining the overlay as a peer and the old cluster head leaving it. Although it is possible to use standard RELOAD join and leave procedures to implement the cluster head handover, this would greatly increase the churn and signalling traffic of the overlay, because it would require neighbouring peers to update their routing tables and to copy resources in order to cope with the changes in the overlay topology.

(48) Instead, in some embodiments, the cluster implements an enhanced cluster head handover process, where the cluster head maintains the same node-ID independently of which cluster node is actually being the cluster head peer. Therefore, the proposed cluster head handover process reduces to the new cluster head taking over the connections to neighbouring nodes and fingers of the old cluster head. Thus, the proposed cluster head handover does not generate any unnecessary churn in the overlay, because it is seen by peers outside the cluster just as a peer changing its IP address, and thus they do not need to update their routing tables or copy any resource.

(49) In order to facilitate an efficient cluster head handover process, the client nodes 701, 721, 751 each have stored therein two consecutive node-IDs, 761, 762; 771, 772; 781; 782, respectively. It will be appreciated that, in general, the node-IDs do not need to be consecutive, but consecutive node-IDs allow for particularly simple implementations. Each client may further have stored therein two cryptographic keys 763, 764; 773; 774; 783; 784, respectively associated with respective digital certificates associated with the respective node-IDs; alternatively the security of the overlay may be based on a shared-key, and thus no further keys are necessary. Depending on the overlay security model these two certificates can be self-signed, or assigned by the enrolment server. In any case these two identities have very different purposes. One of the two node-IDs, e.g. the higher node-ID is employed to identify the node itself, and thus its associated key is kept strictly private. This node-ID is also referred to herein as the private node-ID. The other of the two node-IDs will be referred to as the public node-ID; it is employed during the creation of a new cluster. The public node-ID of the node creating a new cluster will be used as the node-ID of the cluster head identifying the cluster within the overlay network. Hence, this node-ID will also be referred to as cluster node-ID. Therefore, this identity, including its associated key, is shared among all nodes of the cluster. The key associated with the public node-ID of the node creating a new cluster will also be referred to as the cluster key. This cluster key is stored in a special single value resource 742 with a newly defined CLUSTER-KEY Data Kind-ID, which is not shared with any node outside the cluster. A second Dictionary resource 741 with the CLUSTER-TABLE Data Kind-ID is employed to store the cluster information in the following manner: the node-IDs of the cluster nodes are employed as index of the respective entries, and each entry has three associated values: The first value represents the next instant when such node will become the cluster head, encoded as a UNIX time; this entry may be 64-bits long. The second value is 32-bits long and specifies the cluster head period of the node, measured in seconds. The value 0xFFFF means that the node could be the cluster head permanently. The third value is 8-bits long and specifies the maximum number of clients and fingers connections the device is able to support. The value 0xFF means that the node supports an unlimited number of connections.

(50) It will be appreciated that the above cluster information may be stored in a different manner and made accessible to the members of the cluster, e.g. using a different data structure. The cluster information 741 may e.g. be stored in the node 701 that has created the cluster and/or by one or more other nodes of the cluster.

(51) In the following, and with continued reference to FIG. 7, examples of the different procedures performed by clustering-enabled nodes will be described in order to: create a new cluster, join a cluster, and perform the cluster head handover.

(52) FIG. 8 shows a flow diagram of an example of a process for creating a new cluster. For the purpose of the description of this example, it is assumed that a battery-powered sensor node 701 with a public node-ID 761 (e.g. having a value 200) and a private node-ID 762 (e.g. having a value 201) has tried to connect to a Chord-based RELOAD overlay network as a client using its private node-ID, e.g. as described with reference to FIG. 6 above, but was rejected by its resource-constrained admitting peer (e.g. node 711 of FIG. 7), which already has too many clients and/or fingers. It will be appreciated, however, that the process described in the following may also be performed by other types processing devices, other than sensors and resource-constrained peers. It will further be appreciated that the specific values of the node-IDs merely serve as illustrative examples.

(53) As the sensor node 701 cannot connect as a client it may connect as a peer but, as it supports clustering, it creates a new cluster, by performing the following steps which are an example of the steps performed by step S604 of FIG. 6 above:

(54) In step S801, the sensor node 701 joins the overlay network, e.g. by a process described in connection with FIG. 5 above, but in order to create a new cluster, the sensor node 701 employs its public node-ID 761 and corresponding certificate 763 to authenticate with all its neighbours (successors, predecessors and fingers). The public node-ID 761 of the node that created the cluster is therefore the cluster node-ID.

(55) In step S802, the node 701 then creates two new resources: a CLUSTER-KEY Single Value resource 742 storing the private key associated with the cluster node-ID certificate 763, and a CLUSTER-TABLE Dictionary resource 741. Initially the CLUSTER-TABLE contains a single entry, indexed with the private node-ID 762 (having value 201 in the present example), that contains the current time, e.g. encoded in UNIX time (e.g. 09:00:00 UTC Sep. 1, 2012=1346482800), the pre-configured cluster head period of the node (e.g. 2 hours=7200 seconds), and the maximum number of supported clients (e.g. unlimited=255). Both resources are stored using the cluster node-ID as its Resource ID. They may be stored at any suitable location, e.g. by a node of the overlay, according to the applicable rules of the overlay.

(56) The following is an example of the values of the values of these resources after creation of the new cluster:

(57) TABLE-US-00002 (200, CLUSTER-KEY): 112233 . . . (200, CLUSTER-TABLE): Node-ID Next CH Time CH Period Max conn. 201 09:00 2 hours 255

(58) The CLUSTER-TABLE resource may be replicated as any other resource according to the resource replication mechanisms of the overlay network, e.g. in at least three successor nodes as specified by Chord. However, the CLUSTER-KEY should not be made accessible to nodes outside the cluster is thus normally not replicated, and any Fetch requests from nodes outside the cluster should return an Error_Forbidden response. It may be stored by one or more nodes of the cluster.

(59) In step S803, the processing device 701 operates as cluster head as the newly created cluster. Since the new cluster only has one node, this node is the cluster head; the node 701 is therefore awake and acts as a full RELOAD peer until another node joins the cluster. While being the cluster head, a node does not employ its private node-ID 762 (here having a value 201) to communicate with other peers of the overlay, but the cluster node-ID (having a value 200 in this example) instead.

(60) FIG. 9 shows a flow diagram of an example of a process for joining a new cluster, allowing a processing device to join an existing cluster as a new node.

(61) In initial step S901, a processing device 751 requests connection to the overlay network as a client with the cluster head 701 as an admitting peer. For the purpose of the description of this example, it is assumed that processing device is a sensor node with public node-ID 781 (e.g. having a value 250) and private node-ID 782 (e.g. having a value 251), and that node 751 tries to connect at a certain point in time (e.g. at 10:00) after creation of the cluster by node 701.

(62) In step S902, after the second node 751 has attached to the first node 701 as a client (client_node=TRUE, send_update=FALSE), e.g. as described above, the newly attached node 751 checks whether the admitting peer is a cluster head or a regular peer (e.g. actuator). To do so, it may try to fetch from the admitting peer the CLUSTER-TABLE Kind-IDs associated to its node-ID 701. If the admitting peer does not support clustering, it would not return any value and the attaching node can proceed to step S903 and behave as simple RELOAD client.

(63) If, as in the present example, the admitting peer 701 is a cluster head, the admitting peer returns the requested cluster information. Once the new node notices that it can join a cluster, it proceeds at step S904 and fetches the CLUSTER-KEY and stores it locally (it already has the associated certificate because it is the one being employed by the cluster head that admitted the node in the first place).

(64) In step S905, the node 751 joins the cluster by adding its private node-ID 782 to the CLUSTER-TABLE 741 using a Store operation. Notice that public node-IDs are only employed to create a new cluster, and thus the public node-ID 781 of the node joining an existing cluster is not used. Instead cluster nodes joining an existing cluster only employ their own private node-ID 782, unless they become the cluster head when they use the cluster node-ID 761. Node 751 further calculates the time when it has to become the cluster head. To this end, node 751 may look for the newest time in the cluster table (in the above example 9:00), and then add the associated cluster head period (e.g. 9:00+2 hours=11:00 when the cluster head period is 2 h).

(65) The resulting cluster table 741 may thus comprise the following information after node 751 has joined the cluster:

(66) TABLE-US-00003 (200, CLUSTER-TABLE): Node-ID Next CH Time CH Period Max conn. 201 09:00 2 hours 255 251 11:00 1 hour 16

(67) If the computed cluster head time is already in the past, node 701 stores the current time in the cluster table and initiates a cluster head handover process immediately, e.g. as described with reference to FIG. 11 below. Otherwise it can behave as a normal client, awakening and sleeping as it desires until the time of the computed cluster head time arrives.

(68) FIG. 10 shows a message flow diagram illustrating the messages exchanged between the cluster head 701 and the new cluster node 751 joining the cluster in the above example. Initially, the new node sends an attach request 1001 to the cluster head which responds with an attach answer 1002. This process is followed by an Interactive Connectivity Establishment (ICE) process (1003). Subsequently, the new node 751 fetches the cluster information by a fetch request 1004 followed by a fetch answer 1005 from the cluster head. The new node then updates the cluster table and causes the cluster head to store the updated information by means of a store request 1006. After receipt of the corresponding acknowledgement (1007), the client may enter a sleep mode until it is time to initiate a cluster head handover 1008.

(69) A corresponding cluster joining process is repeated by all new clustering-enabled nodes, unless the smallest connection limit of all cluster nodes (e.g. 16 in the above example) is reached. For instance a bit later (e.g. at 10:30) a third node 721 (e.g. having a private node-ID of value 221) joins the cluster thus resulting in the structure shown in FIG. 7. Again, the new node 721 fetches the CLUSTER-KEY and CLUSTER-TABLE to compute its cluster head time (e.g. 11:00+1 hour=12:00), resulting in the updated cluster table:

(70) TABLE-US-00004 (200, CLUSTER-TABLE): Node-ID Next CH Time CH Period Max conn. 201 09:00 2 hours 255 221 12:00 2 hours 32 251 11:00 1 hour 16

(71) It is worthwhile noting that at any given time it is possible to know which node is the current cluster head, other than looking for the cluster node-ID, because the cluster head node should have the oldest time in the CLUSTER-TABLE and be the only one in the past.

(72) FIG. 11 shows the message flow between the current (old) cluster head 701 and the next (new) cluster head 751. When the cluster head period of the current cluster head 701 is over, another cluster node awakes and takes over the cluster head role. To do so, the new cluster head initiates a cluster head handover process, joining the overlay network as a peer, and replacing the old cluster head. This involves getting the routing table and all the resources from the old cluster head, as well as connecting to all the neighbours of the old cluster head in the overlay network (predecessors, successors and fingers in Chord). However, when the new cluster head employs the same node-ID as the old cluster head, this peer replacement is almost transparent, in the sense that it does not generate any changes in the overlay topology. The cluster head handover does not require any new message but it may reuse standard RELOAD messages. In particular, an embodiment of the cluster head handover is similar to the RELOAD Join operation, although in order to easily differentiate it from a new peer trying to join the overlay, the new cluster head uses the cluster node-ID instead of its private node-ID.

(73) In the following, an example of the cluster head handover process will be illustrated with reference to the previous example described with reference to FIG. 7 through 11, i.e. assuming that the cluster head period of the initial cluster head node 701 has arrived (i.e. at 11:00 in the present example), and the second node 751 awakes to start the cluster head handover process:

(74) To this end, node 751, which is to become the next cluster head, first attaches to the current cluster head, reusing a previous client connection or creating a new one via a suitable bootstrap node (e.g. a neighbour node with an accessible public IP address). The new cluster 751 head node thus sends an attach request 1101 to the old cluster head 701. The attach request message 1101 includes the flags client_node=FALSE and send_update=TRUE, and it uses the cluster node-ID (in this example having the value 200) as its sender identity, instead of the private node-ID 751 of the new cluster head which was previously used to connect to the cluster head as a client. The old cluster head responds with a corresponding request answer message 1102 followed by an ICE process 1103.

(75) The send_update=TRUE attach flag triggers the old cluster head to send its whole routing table in an update message 1104 immediately after the attach process is over.

(76) Until the cluster head handover process is finished, the new cluster head can employ the thus established connection with the old cluster head to send RELOAD messages to the overlay.

(77) Then, the new cluster head node 701 starts attaching to each of the neighbour and finger peers in the routing table of the current cluster head, in order to replace it. To this end, the new cluster head node 701 exchanges an attach request message 1105 and a request answer 1106, followed by an ICE 1107 with each of the neighbours. Notice that the new cluster head is also employing the same cluster node-ID (including the corresponding cluster key) to connect to the peers. Therefore the peers do not consider these connections to come from a new node, but from the old cluster head.

(78) In some embodiments, two nodes may have multiple connections simultaneously, thus supporting peer mobility (i.e. a peer changing it IP address) while, in other embodiments, they may only have one. In any case, the attach process from the new cluster head either replaces the previous connection, or the two connections will be maintained until the old cluster head closes its own.

(79) Once the new cluster head has connected to all peers in the routing table, it sends a Join message 1108 to the old cluster head (again using the cluster node-ID as its own node-ID) to initiate the copy of resources into the joining node. Notice that in Chord, since the new node is using the cluster node-ID, which by definition is the lowest node-ID of the cluster, all resources of the old cluster head should be copied into the new cluster head.

(80) When receiving the Join operation, the old cluster head responds with a join answer message 1109 and closes all the connections with its previous neighbours. The old cluster head further starts copying all its resources into the new cluster head by means of one or more Store operations 1110, including the CLUSTER-TABLE. However, before sending the table, the old cluster head updates its own entry in the table, computing its next cluster head time as previously described. In the present example, the thus updated cluster table may thus comprise the following information:

(81) TABLE-US-00005 (200, CLUSTER-TABLE): Node-ID Next CH Time CH Period Max conn. 201 14:00 2 hours 255 221 12:00 2 hours 32 251 11:00 1 hour 16

(82) At this point the new cluster head has fully replaced the old cluster head and the cluster head handover process is completed. Thus the old cluster head may send a Leave Request 1111 to the new cluster head and, upon receipt of a corresponding Leave answer 1112, go to sleep until the computed cluster head time arrives. Meanwhile it can behave as a RELOAD client like any other cluster node.

(83) In the above, embodiments of a method, a system and apparatus for an efficient connection of a wireless communications device to a wireless communications network have been described.

(84) Embodiments of the method, a system and apparatus described herein enable battery-powered (e.g. sensors) or otherwise resource-constrained nodes (e.g. actuators) to connect to a P2P overlay network in a resource- and energy-efficient way, without the need of proxies or gateways, by enabling sleeping clients and by grouping battery-powered devices together in clusters to share the burden of being a peer of the overlay.

(85) Some embodiments of the method, system and apparatus described herein further improve the current client specification for RELOAD: They permit explicit limitation of the number of clients and fingers per peer in the overlay. They allow a client node not to receive continuous unnecessary updates from the overlay. They enable a peer to know whether the incoming attach request comes from a client or a peer. Embodiments of the mechanism described herein introduce only minimal changes to RELOAD in order to enable all the proposed clustering and constrained-client functionality.

(86) Although some embodiments have been described and shown in detail, the aspects disclosed herein are not restricted to them, but may also be embodied in other ways within the scope of the subject matter defined in the following claims. In particular, it is to be understood that other embodiments may be utilized and structural and functional modifications may be made. In particular, embodiments of the aspects disclosed herein have mainly been described with reference to networks using the Chord and RELOAD protocols. It will be understood, however, that embodiments of the methods, devices and systems may also be applied to other types of P2P overlay networks, such as overlay networks using a distributed hash table. The mechanism is almost transparent to other peers in the overlay, and no modification to their normal procedures of legacy peers is necessary.

(87) In the following some of the embodiments of the invention shall be described.

(88) There is provided a method for a processing device in a system of a plurality of processing devices 201 communicatively connected via a peer-to-peer overlay network 101, 102, 104; wherein any processing device 201 is configured to connect to the peer-to-peer overlay network as a peer node or 301 as a client node 302, that is, being a peer node or a client node; wherein a client node is connectable to the peer-to-peer overlay network via a peer node. The method comprises, the steps of the processing device 201 sending a connection request 320 to a peer node 301, the connection request 320 comprising an indication 421 that said processing device wants to attach as a client node 302.

(89) The processing device 201 may moreover send to the peer node 301, a message, for instance comprised in the connection request 320, the message being indicative 422 of a request 320; 422 not to receive any recurring update messages.

(90) There is further provided a method for a processing device in a system of a plurality of processing devices 201 communicatively connected via a peer-to-peer overlay network 101, 102, 104; wherein any processing device 201 is configured to connect to the peer-to-peer overlay network as a peer node or 301 as a client node 302, that is, being a peer node or a client node; wherein a client node is connectable to the peer-to-peer overlay network via a peer node.

(91) The method comprises for the processing device being a peer node 301 when receiving a connection request 320 comprising an indication 421 that another processing device wants to attach as a client node 302. determining, whether the processing device can admit S504 further connections of client nodes; andresponsive to the connection request, returning a rejection message 330, S505 to said another processing device, if the processing device receiving the connection request cannot admit further connections of client nodes.

(92) The method may moreover comprisereceiving, from said another processing device 302 from which a connection request 320 was received S501, a message 320, for instance comprised in the connection request, the message being indicative 422 of a request not to receive any recurring update messages; andresponsive to the received message 320, omitting S509 sending recurring update messages to said another processing device from which the message has been received.

(93) According to an embodiment,if not receiving a message being indicative 422 of a request not to receive any recurring update messages, the processing device issending recurring update messages S508 to said another processing device.

(94) Some or all of the processing device or devices may be battery powered.

(95) The peer-to-peer communications network may use the Resource Location and Discovery Protocol, RELOAD. The connection request 320 may be an attach request and the response 330 to the attach request may be an attach answer.

(96) The processing device 201, may be adapted to send a connection request 320 comprising an indication 421 that the processing device wanting to attach as a client node 302, does not have routing or storage responsibilities in respect of the peer-to-peer overlay network.

(97) The rejection message may indicate that an attach procedure cannot be performed because the processing device being a peer node does not have enough resources, or the peer-to-peer overlay network does not allow further clients.

(98) In one embodiment the processing device is configured to form one of the nodes 701 of a cluster and is operable to perform a cluster head role connecting the cluster to the peer-to-peer overlay network, the processing device thereby acting as a peer, while other cluster nodes, are attached to the cluster head as clients, and wherein the processing device, as cluster head role, is configured to transfer the cluster head role to another node 721, 751 of the cluster, such that the cluster head role is handed over from one node to another among the nodes in the cluster.

(99) In a further embodiment, client nodes do not have routing or storage responsibilities. The cluster node having the cluster head role acting as a peer enables the other cluster nodes, which are attached to the cluster head as clients, to sleep, that is, to be in an energy-conserving state.

(100) Each of the cluster nodes may be associated with a private node identity 261; 761; 771; 781 and a public node identity 262; 762; 772; 782; the public node identity being employed during the creation of a new cluster, in which the cluster only has one node, this node being the cluster head 803; said public node identity 761 of the cluster head subsequently identifying the cluster within the overlay network, that is, said public node identity becoming the cluster node identity.

(101) When a node joins S801 the overlay network for creation of a new cluster, there is created a cluster table S802 containing an entry, indexed with the private node identity 762; 201 of the joining node, a next cluster head time; and a pre-configured cluster head period for said node.

(102) When a subsequent node joins 751 the cluster S905, the cluster table is updated 1005, 1006 with a further entry, indexed with the private node identity 772, 221 of the subsequent node, a next cluster head time for the subsequent node and a pre-configured cluster head period for said subsequent node, wherein the subsequent node may act as a client and enter a sleep mode until it is time to initiate a cluster head handover 1008.

(103) When the cluster head period of the current cluster head 701 is over, a cluster head handover process 1008 is initiated, in which a next cluster node according to a further entry in the cluster table is joining the overlay network as a peer cluster head, and is replacing the previous cluster head of the cluster table and is taking over the cluster head role.

(104) This handover process involves the next cluster node getting a routing table from the old cluster head, as well as connecting to all the neighbour nodes of the previous cluster head in the overlay network, wherein the next cluster head employs the same node identity as the old cluster head.

(105) As stated above, the peer-to-peer communications network may be using the Resource Location and Discovery Protocol, RELOAD, wherein 320 attach request and attach answer 330 messages are used.

(106) In an embodiment, the next cluster 751 head node sends an attach request 1101 to the previous cluster head node 701 to initiate a cluster handover, wherein the attach request message 1101 comprises an indication 421 that the next cluster node is a client and an indication 422 of a request to receive any recurring update messages; the next cluster head using the cluster node identity 200 as its sender identity, instead of the private node identity 751 of the next cluster head.

(107) There is further provided according to an embodiment of the invention, a processing device in a system of a plurality of processing devices 201 communicatively connected via a peer-to-peer overlay network 101, 102, 104; wherein any processing device 201 is configured to connect to the peer-to-peer overlay network as a peer node or 301 as a client node 302, that is, being a peer node or a client node; wherein a client node is connectable to the peer-to-peer overlay network via a peer node; the processing device comprising a processing circuit 216; network interface circuitry 214 connected to the processing circuit and a memory 217, said memory containing instructions executable by said processor, whereby the processing device is being operable to sending a connection request 320 to a peer node 301, the connection request 320 comprising an indication 421 that said processing device wants to attach as a client node 302.

(108) The processing device 201 may moreover be operable to sending to the peer node 301, a message, for instance comprised in the connection request 320, the message being indicative 422 of a request 320; 422 not to receive any recurring update messages.

(109) There is further described and shown a processing device in a system of a plurality of processing devices 201 communicatively connected via a peer-to-peer overlay network 101, 102, 104; wherein any processing device 201 is configured to connect to the peer-to-peer overlay network as a peer node or 301 as a client node 302, that is, being a peer node or a client node; wherein a client node is connectable to the peer-to-peer overlay network via a peer node; the processing device comprising a processing circuit 216; network interface circuitry 214 connected to the processing circuit and a memory 217, said memory containing instructions executable by said processor, whereby the processing device being operable to,

(110) when being a peer node 301,

(111) when receiving a connection request 320 comprising an indication 421 that another processing device wants to attach as a client node 302. determining, whether the processing device can admit S504 further connections of client nodes; and responsive to the connection request, returning a rejection message 330, S505 to said another processing device, if the processing device receiving the connection request cannot admit further connections of client nodes.

(112) The processing device may be further operable to receiving, from said another processing device 302 from which a connection request 320 was received S501, a message 320, for instance comprised in the connection request, the message being indicative 422 of a request not to receive any recurring update messages; and responsive to the received message 320, omitting S509 sending recurring update messages to said another processing device from which the message has been received.

(113) For example, the rejection message indicates that an attach procedure cannot be performed because the processing device being a peer node does not have enough resources, or the peer-to-peer overlay network does not allow further clients.

(114) A processing device in a system of a plurality of processing devices 201 communicatively connected via a peer-to-peer overlay network 101, 102, 104; is moreover disclosed, wherein any processing device 201 is configured to connect to the peer-to-peer overlay network as a peer node or 301 as a client node 302, that is, being a peer node or a client node; wherein a client node is connectable to the peer-to-peer overlay network via a peer node. The processing device comprising a processing circuit 216; network interface circuitry 214 connected to the processing circuit and a memory 217, said memory containing instructions executable by said processor, the processing device being operable to

(115) form one of the nodes 701 of a cluster and being operable to perform a cluster head role connecting the cluster to the peer-to-peer overlay network, the processing device thereby acting as a peer, while other cluster nodes, are attached to the cluster head as clients, and wherein the processing device, as cluster head role, is configured to transfer the cluster head role to another node 721, 751 of the cluster, such that the cluster head role is handed over from one node to another among the nodes in the cluster.

(116) For example, the client nodes do not have routing or storage responsibilities, and wherein the cluster node having the cluster head role acting as a peer, enables the other cluster nodes, which are attached to the cluster head as clients, to sleep, that is, to be in an energy-conserving state.

(117) Each of the cluster nodes may be associated with a private node identity 261; 761; 771; 781 and a public node identity 262; 762; 772; 782; the public node identity being employed during the creation of a new cluster, in which the cluster only has one node, this node being the cluster head 803; said public node identity 761 of the cluster head subsequently identifying the cluster within the overlay network, that is, said public node identity is becoming the cluster node identity.

(118) FIG. 12 shows a processing device comprising a sending module.

(119) As shown in FIG. 12, a processing device is provided in a system of a plurality of processing devices 201 communicatively connected via a peer-to-peer overlay network 101, 102, 104; wherein any processing device 201 is configured to connect to the peer-to-peer overlay network as a peer node or 301 as a client node 302, that is, being a peer node or a client node; wherein a client node is connectable to the peer-to-peer overlay network via a peer node; whereby the processing device comprising:a sending module SM for sending a connection request 320 to a peer node 301, the connection request 320 comprising an indication 421 that said processing device wants to attach as a client node 302.

(120) FIG. 13 shows a processing device comprising a peer module; a connection request module; a determination module and a rejection module.

(121) More specifically there is disclosed a processing device in a system of a plurality of processing devices 201 communicatively connected via a peer-to-peer overlay network 101, 102, 104; wherein any processing device 201 is configured to connect to the peer-to-peer overlay network as a peer node or 301 as a client node 302, that is, being a peer node or a client node; wherein a client node is connectable to the peer-to-peer overlay network via a peer node; comprising:a peer module PM for operating as a peer node 301,a connection request reception module CRM for receiving a connection request 320 comprising an indication 421 that another processing device wants to attach as a client node 302;a determination module DM for determining, whether the processing device can admit S504 further connections of client nodes; anda rejection module RM being responsive to the connection request, for returning a rejection message 330, S505 to said another processing device, if the processing device receiving the connection request cannot admit further connections of client nodes.

(122) FIG. 14 shows a processing device comprising a cluster forming module and a cluster head transfer module.

(123) More specifically there is shown a processing device in a system of a plurality of processing devices 201 communicatively connected via a peer-to-peer overlay network 101, 102, 104; wherein any processing device 201 is configured to connect to the peer-to-peer overlay network as a peer node or 301 as a client node 302, that is, being a peer node or a client node; wherein a client node is connectable to the peer-to-peer overlay network via a peer node; the processing device comprising: a cluster forming module CFM for forming one of the nodes 701 of a cluster and being operable to perform a cluster head role connecting the cluster to the peer-to-peer overlay network, enabling the processing device to act as a peer, while other cluster nodes, are attached to the cluster head as clients, and a cluster head transfer module CHTM for effectuating that the processing device, as cluster head role, is transferring the cluster head role to another node 721, 751 of the cluster, such that the cluster head role is handed over from one node to another among the nodes in the cluster.

(124) The embodiments of the invention may be implemented as by means of a computer program product comprising computer program code 219 according to any of the steps of the methods explained above.

(125) The methods explained above may furthermore be constituted a by Program for a computer or processor comprising computer program code 219.

(126) In device claims enumerating several means, several of these means can be embodied by one and the same item of hardware. The mere fact that certain measures are recited in mutually different dependent claims or described in different embodiments does not indicate that a combination of these measures cannot be used to advantage.

(127) It should be emphasized that the term comprises/comprising when used in this specification is taken to specify the presence of stated features, integers, steps or components but does not preclude the presence or addition of one or more other features, integers, steps, components or groups thereof.