Method and system for synchronizing a data base at a plurality of nodes in an ad hoc network

• US 8,385,321 B2
• Filed: 07/31/2009
• Issued: 02/26/2013
• Est. Priority Date: 07/31/2009
• Status: Expired due to Fees

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Tien, Chien-Wen
• Primary Examiner(s): Rinehart, Mark
• Assistant Examiner(s): ANWAR, MOHAMMAD S
• Application Number:
  US12/462,291
• Publication Number:
  US 20110026513A1
• Time in Patent Office: 1,306 Days
• Field of Search: 370/350, 370/338, 370/328
• US Class Current: 370/350
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor

Abstract

A method for synchronizing a data base at a plurality of nodes in an ad hoc network including at least one authentication node group; each authentication node group including a leader node and at least one member node; the method includes: (a) in each respective authentication node group, comparing and identifying differences between the data base at the respective leader node and the data base at each respective member node; (b) for each comparing, if the differences are identified, exchanging data bases between the leader node and the member node; and (c) for each comparing, in no particular order: (1) merging the leader node data base with the member data base at the leader node to create a leader node merged data base; and (2) merging the member node data base with the leader data base at the member node to create a member node merged data base.

Claims

1. A method for performing initial synchronization of databases at each of a plurality of nodes communicatingly linked in an ad hoc network;

said network including at least one authentication authority node group of at least two group member nodes of said plurality of nodes;

the method comprising;

(a) using an autoconfiguration process to select a group leader node from said group member nodes in the authentication authority node group;

(b) coupling said respective group leader node with each respective said group member node in the authentication authority node group;

(c) receiving, at the group leader node, a predetermined aspect of the database at a group member node;

(d) generating a predetermined aspect of the database at the group leader node and comparing and identifying differences between at least one predetermined aspect of said data base at said respective group leader node and said at least one predetermined aspect of said data base at each respective said group member node;

(e) if said differences identified exceed a predetermined measure, synchronizing the data bases of said group leader node and said group member node by;

(1) receiving the database from the group member node;

(2) comparing each entry of the group member node database with each entry of the group leader database;

(3) providing a buffer for the group leader node and the group member node;

(4) when a mismatch between data from the two nodes is found, storing the data with a more up-to-date timestamp in a buffer for the node having the data with a less up-to-date timestamp;

(5) updating said group leader node data base with the buffer for the group leader node to create a group leader node merged data base; and

(6) updating said group member node data base with the buffer for the group member node to create a group member node merged data base;

wherein the entire merged data base is not transmitted over the network thereby minimizing disk I/O;

(f) repeating steps (a)-(e) for each group member node in the authentication authority group.

2. The method for performing initial synchronization of databases at a plurality of nodes communicatingly linked in an ad hoc network as recited in claim 1 wherein at least one node of said plurality of nodes is a primary service node;

the method further comprising, following step (f);

(g) for each synchronization between the data base of the group leader node and the data base of a group member node, providing at least one of said group leader merged data base and said group member merged data base to at least one said primary service node.

3. The method for performing initial synchronization of databases at a plurality of nodes communicatingly linked in an ad hoc network as recited in claim 2 wherein each said respective authentication authority node group has a respective primary service node.

4. The method for performing initial synchronization of databases at a plurality of nodes communicatingly linked in an ad hoc network as recited in claim 3 wherein each respective node of said plurality of nodes includes a plurality of functional components coupled with a data base server unit.

5. The method for performing initial synchronization of databases at a plurality of nodes communicatingly linked in an ad hoc network as recited in claim 4 wherein each said data base server unit is configured for communicating with at least said respective group leader node and at least one respective group member node.

6. The method for performing initial synchronization of databases at a plurality of nodes communicatingly linked in an ad hoc network as recited in claim 1 wherein each respective node of said plurality of nodes includes a plurality of functional components coupled with a data base server unit.

7. The method for performing initial synchronization of databases at a plurality of nodes communicatingly linked in an ad hoc network as recited in claim 6 wherein each said data base server unit is configured for communicating with at least said respective group leader node and at least one respective group member node.

8. A method for synchronizing data bases at a plurality of nodes in an authentication authority node group of an ad hoc network when a new node joins the authentication authority node group;

said authentication authority node group being associated with a primary services node (PSN) including a group leader node and at least one group member node;

the method comprising;

(a) sending, by the new node, a node join notification to the PSN;

(b) receiving, from the PSN, information about the nearest neighbor group member node to the new node;

(c) sending a predetermined aspect of the database at the new node to the nearest neighbor group member node;

(d) comparing and identifying differences between at least one predetermined aspect of said data base at said new node and said at least one predetermined aspect of said data base at said nearest neighbor group member node;

(e) if said differences identified exceed a predetermined measure, synchronizing the data bases of said new node and said nearest neighbor group member node; and

(1) receiving the database from the new node;

(2) comparing each entry of the new node database with each entry of the nearest neighbor group member database;

(3) providing a buffer for the new node and the nearest neighbor group member node;

(4) when a mismatch between data from the two nodes is found, storing the data with a more up-to-date timestamp in a buffer for the node having the data with a less up-to-date timestamp;

(5) updating said new node data base with the buffer for the new node to create a new node merged data base; and

(6) updating said nearest neighbor group member node data base with the buffer for the nearest neighbor group member node to create a nearest neighbor group member node merged data base;

wherein the entire merged data base is not transmitted over the network thereby minimizing disk I/O.

9. The method for synchronizing data bases at a plurality of nodes in an authentication authority node group of an ad hoc network as recited in claim 8 wherein each respective node of said plurality of nodes includes a plurality of functional components coupled with a data base server unit.

10. The method for synchronizing data bases at a plurality of nodes in an authentication authority node group of an ad hoc network as recited in claim 9 wherein each said data base server unit is configured for communicating with at least said respective group leader node and at least one respective group member node.

11. A system for performing initial synchronization of databases at each of a plurality of nodes in an ad hoc network;

said network including at least one authentication authority node group of at least two group member nodes of said plurality of nodes;

each respective authentication authority node group of said at least one authentication authority node group including a respective group leader node and at least one group member node;

the system comprising;

(a) in each respective node, a respective comparing unit;

said respective comparing unit in each respective node of each said respective authentication authority node group comparing and identifying differences between at least one predetermined aspect of said data base at said respective group leader node and said at least one predetermined aspect of said data base at each respective said group member node;

in each respective authentication authority node group said respective group leader node being coupled with each respective said group member node;

(b) in each respective node, a respective communicating unit;

if said differences identified exceed a predetermined measure, said respective communicating units for said respective group leader node and said respective group member node synchronizing the data bases of said group leader node and said group member node in cooperation with a data base server unit in each node, by;

(1) receiving the database from the group member node;

(2) comparing each entry of the group member node database with each entry of the group leader database;

(3) providing a buffer for the group leader node and the group member node;

(4) when a mismatch between data from the two nodes is found, storing the data with a more up-to-date timestamp in a buffer for the node having the data with a less up-to-date timestamp;

(5) updating said group leader node data base with the buffer for the group leader node to create a group leader node merged data base; and

(6) updating said group member node data base with the buffer for the group member node to create a group member node merged data base;

wherein the entire merged data base is not transmitted over the network thereby minimizing disk I/O;

(f) repeating steps (a)-(e) for each group member node in the authentication authority group.

12. The system for performing initial synchronization of databases at each of a plurality of nodes communicatingly linked in an ad hoc network as recited in claim 11 wherein at least one node of said plurality of nodes is a primary service node;

the method further comprising, following step (f);

(g) for each synchronization between the data base of the group leader node and the data base of a group member node, providing at least one of said group leader merged data base and said group member merged data base to at least one said primary service node.

13. The system for performing initial synchronization of databases at each of a plurality of nodes communicatingly linked in an ad hoc network as recited in claim 12 wherein each said respective authentication authority node group has a respective primary service node.

14. The method for performing initial synchronization of databases at each of a plurality of nodes communicatingly linked in an ad hoc network as recited in claim 13 wherein each respective node of said plurality of nodes includes a plurality of functional components coupled with said data base server unit, and wherein each said data base server unit is configured for communicating with at least said respective group leader node and at least one respective group member node.

15. The system for performing initial synchronization of databases at each of a plurality of nodes communicatingly linked in an ad hoc network as recited in claim 11 wherein each respective node of said plurality of nodes includes a plurality of functional components coupled with said data base server unit.

16. The system for performing initial synchronization of databases at each of a plurality of nodes communicatingly linked in an ad hoc network as recited in claim 15 wherein each said data base server unit is configured for communicating with at least said respective group leader node and at least one respective group member node.