D2HCP PROTOCOL IN AD HOC NETWORKS: MERGING OF SUB-NETWORKS AND ADDRESS CONFLICT RESOLUTION

• US 20160127193A1
• Filed: 11/08/2013
• Published: 05/05/2016
• Est. Priority Date: 12/21/2012
• Status: Active Grant

• Current Assignee: Airbus DS SAS (Airbus SE)
• Original Assignee: Airbus DS SAS (Airbus SE)
• Inventors: DENIAUD, Thierry, EL SHABRAWY, Karim
• Granted Patent: US 10,057,130 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 2101/668 Internet protocol [IP] address subnets
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/74 Address processing for routing
• CPC Class Codes: H04L 61/5014 using dynamic host configuration protocol [DHCP] or bootstrap protocol [BOOTP]
• CPC Class Codes: H04L 61/5046 Resolving address allocation conflicts; Testing of addresses testing when self-assigning an address H04L61/5092
• CPC Class Codes: H04L 61/5061 Pools of addresses
• CPC Class Codes: H04L 61/5076 Update or notification mechanisms, e.g. DynDNS
• CPC Class Codes: H04L 63/0876 based on the identity of the terminal or configuration, e.g. MAC address, hardware or software configuration or device fingerprint
• CPC Class Codes: H04L 67/1061 using node-based peer discovery mechanisms static access to replicated servers H04L67/1006; service discovery H04L67/51
• CPC Class Codes: H04L 67/1068 Discovery involving direct consultation or announcement among potential requesting and potential source peers
• CPC Class Codes: H04W 12/009 specially adapted for networks, e.g. wireless sensor networks, ad-hoc networks, RFID networks or cloud networks
• CPC Class Codes: H04W 12/069 using certificates or pre-shared keys
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 84/20 Master-slave selection or change arrangements

Abstract

A method for merging two sub-networks of an ad hoc network implementing the D2HCP routing protocol includes transmitting a first data set from the master node to the slave node, the first set including the identifiers of all the nodes of the sub-network containing the master node, the IP addresses of all the nodes of the sub-network containing the master node, each node identifier being associated with a single IP address, comparing each received IP address of the first set with the IP addresses of the routing table of the slave node in order to identify a list of duplicates corresponding to nodes of each sub-network having the same IP addresses.

Claims

1. A method for detecting a merging situation of two ad-hoc sub-networks implementing a D2HCP addressing protocol, the first sub-network comprising a plurality of nodes and the second sub-network comprising a plurality of nodes, each node of each sub-network comprising a data set comprising

an identifier of said node;

identifiers of the known nodes of an authentication data set of said node;

an IP address associated with the identifier of each node referenced in the authentication data set;

at least one identifier of the sub-network to which said node belongs,

the method comprising;

discovering a second node of the second sub-network by a first node of the first sub-network, by receiving by the first node a so called discovery data frame, transmitted by the second node for determining a situation requiring merging of both sub-networks;

exchanging setup data between the first node and the second node, comprising;

the identifiers of each node;

a size of each sub-network;

the identifier of each sub-network (ID₂₀, ID₂₁);

comparing the sizes of each sub-network enabling a master node and a slave node to be defined from the first and the second nodes, the slave node retrieving a set of identifiers of the nodes of the sub-network of the master node as well as the IP addresses associated with each of said identifiers, the determination of the slave node and the master node enabling the merging of both sub-networks in a single network to be setup.

2. The method according to claim 1, wherein the authentication data set is a table comprising node identifiers and their associated IP addresses.

3. The method according to claim 1, wherein a merging situation requiring to merge both sub-networks is recognized by a first node when a discovery frame of a routing protocol is received from the second node and comprises an identifier unknown to the first node, and when the second node already has an IP address.

4. The method according to claim 1, wherein the setup data further comprise an indication that a merging situation has started.

5. The method according to claim 1, wherein a merging situation requiring to merge both sub-networks is recognized by a second node when it receives, from a first node that discovered it beforehand, a variable indicating that a merging situation has been recognized by the first node.

6. The method according to claim 1, comprising, by the master node, generating a freeze message, to all the nodes known to its authentication data set, including to the slave node, the message comprising the identifiers of both sub-networks and an indication that a merging operation is instantiated.

7. The method according to claim 1, comprising, by the slave node (N_SL) generating a freeze message, to all the nodes known to its authentication data set, the message comprising the identifiers of both sub-networks and an indication that a merging operation is instantiated.

8. The method according to claim 6, wherein each node receiving the freeze message suspends:

any other analysis regarding messages received from unknown nodes;

any IP address assignment of a new node entering a sub-network;

any other merging request from another node.

9. The method according to claim 6, wherein each node receiving the freeze message records the identifiers of both sub-networks and activates a standby state relative to the merging situation until it receives a message indicating that the merging phase has ended.

10. The method according to claim 1, wherein the size of a sub-network corresponds to the number of nodes known in the authentication data set of a node of said sub-network.

11. The method according to claim 1, wherein the slave node is the node belonging to the sub-network having the smallest size.

12. The method according to claim 1, wherein when the sizes of both sub-networks are identical, the slave node is chosen from the one which has the network identifier having the greatest value.

13. The method according to claim 1, wherein the identifier of the single merged network corresponds to the identifier of the node of the sub-network having the greatest value.

20. The merging method according to claim 14, wherein the master node and the slave node are determined by a method according to claim 1.

21. A system for detecting a merging situation and a merging situation of two ad-hoc sub-networks implementing a D2HCP addressing protocol, the first sub-network comprising a plurality of nodes and the second sub-network comprising a plurality of nodes, wherein at least one first node of the first sub-network and a node of the second sub-network enable to carry out the method for detecting a merging situation of claim 1.

14. A method for merging two sub-networks of an ad-hoc network implementing a D2HCP routing protocol, a master node being determined from a first sub-network and a slave node being determined from the second sub-network, the method comprising:

emitting a first data set from the master node to the slave node, said first set comprising;

the identifiers of all the nodes of the sub-network comprising the master node;

the IP addresses of all the nodes of the sub-network comprising the master node, each identifier of the node being associated with a single IP address,

comparing each received IP address of the first set with the IP addresses of a second authentication data set of the slave node, the latter set comprising the identifiers and the IP addresses of the nodes known to the slave node of the second sub-network, so as to identify a list of duplicate nodes corresponding to nodes of the second sub-network having the same IP addresses as nodes of the first sub-network.

15. The merging method according to claim 14, wherein each node comprises a block of free IP addresses, the method comprising:

allocating a new IP address to at least one node having a duplicate IP address comprised in the previously defined list, the new address being chosen from the free IP addresses known to the slave node;

broadcasting the new IP address to the nodes of the second sub-network;

updating the second authentication data set of the slave node of the second sub-network with at least the new IP address of the node having had a new assigned IP address.

16. The merging method according to claim 15, wherein a first allocation of a new block of IP addresses is generated in at least one duplicate node of the second sub-network, the block being built from the IP address of said duplicate node and the block of IP addresses in which the slave node has chosen the new IP address of the duplicate node.

17. The merging method according to claim 16, wherein a second allocation of a new block of IP addresses generated in the node of the first sub-network having a duplicate address with a node of the second sub-network, the new block not comprising IP addresses in common with other existing blocks.

18. The merging method according to claim 16, wherein a third allocation of a new block of IP addresses generated in the node of the first sub-network or of the second sub-network, the initial block of which contains the new IP address affected to at least one duplicate node of the second sub-network, the new block not comprising IP addresses in common with other existing blocks.

19. The merging method according to 14, further comprising

building by the slave node building a new authentication data set of the nodes of both sub-networks;

building a new routing table with all the IP addresses of both sub-networks in each node of the merged network;

assigning by the slave node assigning the new identifier of the merged network comprising the nodes of both sub-networks;

broadcasting the data of the new authentication data set of the slave node to all the nodes of the new merged network.