Distributed Master Election

• US 20110188506A1
• Filed: 09/30/2009
• Published: 08/04/2011
• Est. Priority Date: 10/03/2008
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Arribas, Marta San Martin, Jimenez, Jorge Nevado, Henriksen, Dennis
• Granted Patent: US 8,493,978 B2
• Time in Patent Office: Days
• US Class Current: 370/400
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

A transmitting node in a telecommunications network, wherein data are distributed into one or more data storage groups (DSG), and wherein data related to a DSG is replicated into a plurality of data storage elements (DS) distributed along one or more nodes of the network. The transmitting node includes a network interface through which a bi-directional connection is established with a plurality of other nodes in a transport layer of the network, and from which messages are sent to the plurality of other nodes comprising an operational state matrix (OSM), which includes information held by the transmitting node about the operational state of the replicas of the DSs of each DSG. The transmitting node includes a memory for storing data. The transmitting node includes a processing unit which forms a list of the plurality of other nodes as having an answer pending of the node in the memory. The network interface receives an OSM from at least some of other nodes which are interpreted by the processing unit as answer messages from the list of the plurality of other nodes to the messages sent by the network interface, and which indicates that an OSM information exchange with the plurality of the other nodes is complete. The processing unit decides a node hosting the master DS replica of each DSG based on the OSM information exchange. The processing unit detects changes in a view of the world (VOW) which includes an accumulated set of OSMs with respect to each DSG hosted by the transmitting node. The network interface sends messages comprising changes in the VOW to the other nodes.

Claims

1. A method for a transmitting node in a telecommunications network, wherein data is distributed into one or more data storage groups (DSG), and wherein data related to a DSG is replicated into a plurality of data storage elements (DS) distributed along a system comprising one or more nodes of the network, the method comprising the steps of:

establishing a bi-directional connection via a network interface of the transmitting node with a plurality of other nodes in a transport layer of the network;

sending from the network interface messages to the plurality of other nodes comprising an operational state matrix (OSM), which includes information held by the transmitting node about the operational state of all the replicas of the DS of each DSG, wherein the operational state of a replica in an OSM comprises reachability information indicating, for each of the one or more DSGs;

that it is absent in a node, or that it is hosted by a node, or that it is unreachable from a node;

forming a list of the plurality of other nodes as having an answer pending with a processing unit of the transmitting node in a memory of the transmitting node;

receiving at the network interface a message from at least some of the other nodes, each received message comprising an OSM including information held respectively by each of said other nodes about the operational state of all the replicas of the DS of each DSG, and which are interpreted by the processing unit as answer messages from the list of the plurality of other nodes to the messages sent in the sending step, and which indicates that an OSM information exchange with the plurality of the other nodes is complete;

deciding with the processing unit a node hosting the master DS replica of each DSG based on a view of the world (VOW), which is derived based on the received OSMs, and which includes an accumulated set of OSMs with respect to each DSG on every node of the system;

detecting with the processing unit changes in a VOW derived by the transmitting node with respect to each DSG on every node of the system; and

sending from the network interface messages comprising changes in the VOW to the other nodes.

2. The method as described in claim 1 including the step of the processing unit starting a timer when the OSM has been sent to all the other nodes.

3. The method as described in claim 2 including the step of the processing unit stopping the timer when an OSM is received by the network interface from all the plurality of other nodes.

4. A method as described in claim 3 including the step of resending from the network interface the OSM of the node to one of the plurality of other nodes after a predetermined period of time has passed and an OSM from the one of the plurality of other nodes has not been received by the network interface.

5. The method as described in claim 1 including the step of storing a replica of at least one data group of a plurality of data groups of data stored in the DS, in a DS of at least one other node.

6. The method as described in claim 1 including the step of requesting through the network interface data at a data group disposed in at least one other node.

7. The method as described in claim 1 including the step of sending updates from the network interface to the DSs of the plurality of DSGs.

8. The method as described in claim 1 including the step of determining by the processing unit a second node of the plurality of nodes as hosting a master DS replica of a DSG in a third node of the plurality of nodes, which hosted the master DS replica, when communication between the network interface and the third node is lost.

9. The method as described in claim 1 including the step of processing assignation of incoming signaling in a node related to data of a certain DSG with at least one access gateway element (AG) to the plurality of the nodes, the AG knowing which DS of a DSG is the master DS replica of the DSG, each DS of the DSG accessible from the network interface.

10. The method as described in claim 9 including the step of compiling a last update and status of each node of the plurality of nodes by a primary monitoring process with the processing unit to determine the node hosting the master DS replica for a DSG.

11. The method as described in claim 10 wherein the compiling step includes the step of forming a configuration with the primary monitoring process which lists all DS replicas in terms of which DSG each DS belongs to, which node each DS is hosted, and a priority within the DSG the DS is associated with in which it acts as a master replica.

12. The method as described in claim 11 including the steps of:

the processing unit producing an active DS list (ADL) derived from the configuration;

publishing the ADL to the AG; and

the AG processing the assignation of incoming signaling related to data of a certain DSG by using the ADL.

13. The method as described in claim 12 including the step of the processing unit deriving the ADL from the VOW.

26. A computer program on a non-transitory computer readable medium for performing a method as claimed in claim 1, when loaded into one or more computer-based apparatuses.

14. A method for a receiving node in a telecommunications network, wherein data is distributed into one or more data storage groups (DSG), and wherein data related to a DSG is replicated into a plurality of data storage elements (DS) distributed along a system comprising one or more nodes of the network, the method comprising the steps of:

accepting a connection attempt received by a network interface of the receiving node from a transmitting node via the network;

receiving an operational state matrix (OSM) at the network interface from the transmitting node, which includes information held by the transmitting node about the operational state of all the replicas of the DS of each DSG, wherein the operational state of a replica in a OSM comprises reachability information indicating, for each of the one or more DSGs;

that it is absent in a node, or that it is hosted by a node, or that it is unreachable from a node;

sending, responsive to the step of receiving, from the network interface the receiving node'"'"'s OSM to the transmitting node and at least one other node in the network via the network, which includes information held by the receiving node about the operational state of all the replicas of the DS of each DSG;

forming a list with the processing unit in a memory of the node which list includes at least the other node as having an answer pending; and

receiving a message at the network interface from the other node comprising an OSM including information held by said other node about the operational state of all the replicas of the DS of each DSG, which is interpreted by the processing unit as an answer, and which indicates that an exchange with the other node is complete; and

receiving at the network interface from the transmitting node changes in a view of the world (VOW), which is derived by the transmitting node based on the received OSMs, and which includes an accumulated set of OSMs hosted by the transmitting node with respect to each DSG on every node of the system.

15. The method as described in claim 14 including the step of starting a timer by the processing unit when the OSM is sent to the other node by the network interface.

16. The method as described in claim 15 including the step of stopping the timer by the processing unit when the OSM from the other node is received by the network interface.

17. The method as described in claim 14 including the step of updating by the processing unit the node'"'"'s OSM stored in the memory after the OSM from the transmitting node is received by the network interface.

18. A transmitting node in a telecommunications network, wherein data is distributed into one or more data storage groups (DSG), and wherein data related to a DSG is replicated into a plurality of data storage elements (DS) distributed along a system comprising one or more nodes of the network, the transmitting node comprising:

a network interface through which a bi-directional connection is established with a plurality of other nodes in a transport layer of the network, and from which messages are sent to the plurality of other nodes comprising an operational state matrix (OSM), which includes information held by the transmitting node about the operational state of all the replicas of the DS of each DSG, wherein the operational state of a replica in a OSM comprises reachability information indicating, for each of the one or more DSGs;

that it is absent in a node, or that it is hosted by a node, or that it is unreachable from a node;

a memory for storing data; and

a processing unit which forms a list of the plurality of other nodes as having an answer pending of the node in the memory, the network interface receiving a message from at least some of other nodes, each received message comprising an OSM including information held respectively by each of said other nodes about the operational state of all the replicas of the DS of each DSG, which are interpreted by the processing unit as answer messages from the list of the plurality of other nodes to the messages sent, and which indicates that an OSM information exchange with the plurality of the other nodes is complete, the processing unit deciding a node hosting the master DS replica of each DSG based on a view of the world (VOW), which is derived based on the received OSMs, and which includes an accumulated set of OSMs with respect to each DSG on every node of the system, the processing unit detecting changes in a VOW derived by the transmitting node, the network interface sending messages comprising changes in the VOW to the other nodes.

19. The node as described in claim 18 including a timer and wherein the processing unit starts the timer when the OSM in the memory has been sent to all the other nodes.

20. The node as described in claim 19 wherein the processing unit stops the timer when an OSM is received by the network interface from all the plurality of other nodes.

21. The node as described in claim 20 wherein the network interface resends the OSM in the memory to one of the plurality of other nodes after a predetermined period of time has passed and an OSM from the one of the plurality of other nodes has not been received by the network interface.

22. The node as described in claim 18 wherein the network interface sends a replica of at least one data group of a plurality of data groups of data stored in the DS to at least one other node, so the replica is stored in a DS of at least one other node.

23. The node as described in claim 18 wherein the network interface sends a request for data at a data group disposed in at least one other node.

24. A receiving node in a telecommunications network, wherein data is distributed into one or more data storage groups (DSG), and wherein data related to a DSG is replicated into a plurality of data storage elements (DS) distributed along a system comprising one or more nodes of the network, the receiving node comprising:

a network interface which accepts a connection attempt from a transmitting node via the network, receives an operational state matrix (OSM) at the network interface from the transmitting node, which includes information held by the transmitting node about the operational state of all the replicas of the DS of each DSG, wherein the operational state of a replica in a OSM comprises reachability information indicating, for each of the one or more DSGs;

that it is absent in a node, or that it is hosted by a node, or that it is unreachable from a node; and

sends, responsive to having received the OSM from the transmitting node, the receiving node'"'"'s OSM to the transmitting node and at least one other node in the network via the network, which includes information held by the receiving node about the operational state of all the replicas of the DS of each DSG;

a memory for storing data; and

a processing unit which forms a list in the memory which list includes at least the other node as having an answer pending, the network interface receiving an OSM from the other node which is interpreted by the processing unit as an answer, which indicates that an exchange with the other node is complete, after which the network interface receives from the transmitting node changes in a view of the world (VOW), which is derived by the transmitting node based on the received OSMs, and which includes an accumulated set of OSMs hosted by the transmitting node with respect to each DSG on every node of the system.

25. The node as described in claim 24 wherein the processing unit updates the OSM stored in the memory after the OSM from the transmitting node is received by the network interface.