Linear network coding in a dynamic distributed federated database

• US 9,680,932 B2
• Filed: 10/08/2014
• Issued: 06/13/2017
• Est. Priority Date: 10/10/2013
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Berman, Thomas J. C., Pipes, Stephen D.
• Primary Examiner(s): Zecher, Dede
• Assistant Examiner(s): CHIANG, JASON
• Application Number:
  US14/509,638
• Publication Number:
  US 20150106953A1
• Time in Patent Office: 979 Days
• CPC Class Codes: G06F 16/256 in federated or virtual databases
• CPC Class Codes: H04L 63/18 using different networks or channels, e.g. using out of band channels cryptographic mechanisms or cryptographic arrangements for key distribution involving distinctive intermediate devices or communication paths H04L9/0827; cryptographic mechanisms or cryptographic arrangements for authentication using a plurality of channels H04L9/3215
• 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]
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes

Abstract

A method, system and/or computer program product secures response data sent from a responder to a querier. Path information for query data is collected. The path information identifies paths from the querier to the responder and includes a physical machine identifier for each node hosted by a physical machine. One or more sets of return paths are identified for sending response data. For each set of return paths, any return paths that utilize any nodes sharing a physical machine identifier with any node present in another of the return paths within the set of return paths are discarded. The response data is split into a plurality of portions, and each of the plurality of portions is sent from the responder to the querier using a different return path selected from one of the set of return paths.

Claims

1. A method for use in a distributed federated database for securing response data sent from a responder to a querier, in response to query data sent from a querier through one or more nodes of a network of nodes, hosted on a physical machine, to a responder, the method comprising:

collecting, by one or more processors, path information for the query data, wherein the path information identifies a query path from a querier node to a responder node, wherein the path information includes a physical machine identifier for each of one or more nodes in the query path, wherein each physical machine identifier is a hardware identifier for a physical machine used for each of the one or more nodes in the query path;

identifying, by one or more processors, a plurality of return paths for sending response data from the responder node to the querier node, wherein each one of the return paths from the plurality of return paths utilizes only a subset of nodes not present in any other one of the return paths within the plurality of return paths, and wherein the response data comprises a partial response to the query data;

for each of said plurality of return paths, discarding, by one or more processors, any return paths within the plurality of return paths which utilize any nodes sharing the physical machine identifier with any node present in another of the plurality of return paths, wherein a discarded return path is unavailable as a return path from the responder node to the querier node; and

splitting, by one or more processors, the response data into a plurality of portions and sending each of the plurality of portions from the responder node to the querier node using a different return path selected from one of said plurality of return paths that have not been discarded for having nodes that share the physical machine identifier for the same physical machine, wherein each return path from the plurality of return paths shares at least one intermediate node with the query path, and wherein each return path from the plurality of return paths contains at least one intermediate node that is not in the query path.

2. The method as claimed in claim 1, wherein the distributed federated database is a dynamic distributed federated database in which queriers, nodes and responders are capable of being added while the dynamic distributed federated database is in use.

3. The method as claimed in claim 1, wherein said path information is collected from metadata added by each of the one or more nodes as the query data passes through each of the one or more nodes.

4. The method as claimed in claim 1, wherein a first return path from the plurality of return paths is initially used to return a portion of the response data to the querier node from the responder node, and wherein the method further comprises:

detecting, by the responder node, that an intermediate node from the first return path has disappeared; and

in response to the responder node detecting that the intermediate node from the first return path has disappeared, selecting, by one or more processors, a second return path from the plurality of return paths to replace the first return path.

5. The method of claim 1, further comprising:

restoring, by one or more processors, two of the discarded return paths as restored return paths in which a shared intermediate node is used;

merging, by one or more processors, partial responses from the two restored return paths at the shared intermediate node to create a complete response; and

choosing, by the shared intermediate node, a return path through which the complete response is transmitted from the shared intermediate node to the querier node.

6. A hardware system for use by a distributed federated database for securing response data sent from a responder to a querier, in response to query data sent from a querier through one or more nodes of a network of nodes, hosted on a physical machine, to a responder, the hardware system comprising:

hardware means for collecting path information for the query data, the path information identifying a plurality of paths from the querier to the responder and including a physical machine identifier for each of the nodes in the query path, wherein each physical machine identifier is a hardware identifier for a physical machine used for each of the one or more nodes in the query path;

hardware means for identifying a plurality of return paths for sending response data from the responder node to the querier node, each one of the return paths within the plurality of return paths utilizing only a subset of nodes not present in any other one of the plurality of return paths, and wherein the response data comprises a partial response to the query data;

hardware means for, for each of said plurality of return paths, discarding any of the return paths within the plurality of return paths which utilize any nodes sharing a physical machine identifier with any node present in another of the return paths in the plurality of return paths, wherein a discarded return path is unavailable as a return path from the responder node to the querier node; and

hardware means for splitting the response data into a plurality of portions and sending each of the plurality of portions from the responder to the querier using a different return path selected from one of said plurality of return paths that have not been discarded for having nodes that share the physical machine identifier for the same physical machine, wherein each return path from the plurality of return paths shares at least one intermediate node with the query path, and wherein each return path from the plurality of return paths contains at least one intermediate node that is not in the query path.

7. The hardware system as claimed in claim 6, wherein the distributed federated database is a dynamic distributed federated database in which queriers, nodes and responders are added while the dynamic distributed federated database is in use.

8. The hardware system as claimed in claim 6, wherein said hardware means for collecting path information collect metadata added by each of the one or more nodes as the query data passes through each of the one or more nodes.

9. The hardware system as claimed in claim 6, wherein the response data comprises a partial response to the query data.

10. A computer program product for use in a distributed federated database for securing response data sent from a responder to a querier, in response to query data sent from a querier through one or more nodes of a network of nodes, hosted on a physical machine, to a responder, the computer program product comprising a computer readable storage device, wherein the computer readable storage device is hardware having program code thereupon, the program code readable and executable by a processor to perform a method comprising:

collecting path information for the query data, wherein the path information identifies a plurality of paths from the querier to the responder and includes a physical machine identifier for each of the one or more nodes in the query path, wherein each physical machine identifier is a hardware identifier for a physical machine used for each of the one or more nodes in the query path;

identifying a plurality of return paths, from said plurality of paths, for sending response data, wherein each one of the return paths from the plurality of return paths utilizes only a subset of nodes not present in any other one of the return paths within the plurality of return paths, and wherein the response data comprises a partial response to the query data;

for each of said plurality of return paths, discarding any return paths within the plurality of return paths which utilize any nodes sharing a physical machine identifier with any node present in another of the plurality of return paths, wherein a discarded return path is unavailable as a return path from the responder node to the querier node; and

splitting the response data into a plurality of portions and sending each of the plurality of portions from the responder to the querier using a different return path selected from one of said plurality of return paths that have not been discarded for having nodes that share the physical machine identifier for the same physical machine, wherein each return path from the plurality of return paths shares at least one intermediate node with the query path, and wherein each return path from the plurality of return paths contains at least one intermediate node that is not in the query path.

11. The computer program product of claim 10, wherein the distributed federated database is a dynamic distributed federated database in which queriers, nodes and responders are capable of being added while the dynamic distributed federated database is in use.

12. The computer program product of claim 10, wherein said path information is collected from metadata added by each of the one or more nodes as the query data passes through each of the one or more nodes.

13. The computer program product of claim 10, wherein the response data comprises a partial response to the query data.