Privacy preserving query method and system for use in federated coalition networks

• US 9,667,530 B2
• Filed: 05/06/2013
• Issued: 05/30/2017
• Est. Priority Date: 05/06/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Vyvyan, David R., Calo, Seraphin B., Berman, Thomas J. C., Su, Lu, Ye, Fan
• Primary Examiner(s): Zecher, Dede
• Assistant Examiner(s): Almamun, Abdullah
• Application Number:
  US13/887,873
• Publication Number:
  US 20140328342A1
• Time in Patent Office: 1,485 Days
• CPC Class Codes: H04L 45/24 Multipath

Abstract

In at least one embodiment, a method and a system include a node potentially having information responsive to an information request distributed into, for example, a federated coalition network where the node receives at least one information request packet, conducts a search of information at the node to determine if requested information is present, when the requested information is present, then the node sends an acknowledgement to a requesting node, linear network codes the requested information into m packets where m is greater than or equal to k, which is the number of packets needed to be received by the requesting node to reconstruct the requested information, selects multiple paths between the node and the requesting node such that no third party will see more than k−1 different packets, and transmits the m packets distributed over the selected paths. In a further embodiment, the method and system include operation of the network to have the capability to provide responsive information in a protected way.

Claims

1. A method comprising:

receiving at least one information request packet at a node from at least one neighboring node in a federated computer network,

conducting a search of information at the node by the node to determine if requested information is present,

when the requested information is present, then the node

sends an acknowledgement to a requesting node using header information present in the information request packet to route the acknowledgement back to the requesting node,

linear network codes the requested information into m packets where m is greater than or equal to k, which is the number of packets needed to be received by the requesting node to reconstruct the requested information,

selects multiple paths between the node and the requesting node such that no third party to the node and the requesting node will have more than k−

1 different packets pass through any one or more node controlled by that third party, and

transmits the m packets distributed over the selected paths, and

storing a path of any received information request packet in a memory of the node.

2. The method according to claim 1, further comprising when the requested information is not present, then

updating a header information of the information request packet to include identification of the node including identity of a party owning the node, and

forwarding the information request to at least one other node other than the neighboring node that sent the information request packet.

3. The method according to claim 1, further comprising:

checking a header of each received information request packet for a path to determine whether the node is present in the path,

when the node is present in the path, disregarding the information request packet.

4. The method according to claim 1, further comprising:

checking a header of each received information request packet for a path to determine whether a second neighboring node other than the neighboring node that sent the information request packet is present in the path,

when the second neighboring node is present in the path, disregarding the information request packet.

5. The method according to claim 1, further comprising:

receiving by the node a stop packet for the information request packet,

stopping by the node the sending of the information request packet, and

forwarding by the node the stop packet to a neighboring node other than the neighboring node that sent the stop request.

6. The method according to claim 1, further comprising

counting by the node the number of paths for the information request packets received by the node,

when the number equals n, the node stopping the sending of the information request packet to neighboring nodes if the information request packet is received again.

7. The method according to claim 1, further comprising when n paths are collected by the node that has sent the acknowledgement, sending a ready notification to the requesting node.

8. The method according to claim 1, wherein selecting multiple paths includes

setting a counter for each other third party present in the federated coalition network equal to k−

1,

selecting a first path between the node and the requesting node based at least in part on stored paths for the information request packet,

reducing the counter for each third party present along the first path by a number of packets to be sent over the first path,

selecting at least one second path between the node and the requesting node based at least in part on stored paths for the information request packet, and

reducing the counter for each third party present along the at least one second path by a number of packets to be sent over the at least one second path.

9. The method according to claim 8, wherein the first path and the at least one second path are selected based on at least a length of the paths such that a shortest path is selected for the first path and a next shortest path is selected for the second path.

10. The method according to claim 8, further comprising sending a notification from the node to the requesting node regarding being unable to send requested information if insufficient paths exist to send m packets containing the requested information.

11. The method according to claim 1, wherein selecting n paths includes

retrieving paths for the federated coalition network between the node and the requesting node where the paths are based on topology for the federated coalition network derived from link state flooding messages,

setting a counter for each other third party present in the federated coalition network equal to k−

1,

selecting a first path between the node and the requesting node based at least in part on retrieved paths,

reducing the counter for each third party present along the first path by a number of packets to be sent over the first path,

selecting at least one second path between the node and the requesting node based at least in part on retrieved paths, and

reducing the counter for each third party present along the at least one second path by a number of packets to be sent over the at least one second path.

12. The method according to claim 11, wherein the first path and the at least one second path are selected based on at least a length of the paths such that a shortest path is selected for the first path and a next shortest path is selected for the second path.

13. The method according to claim 1, wherein selecting multiple paths includes

setting by a central processor a counter for each other third party present in the federated coalition network equal to k−

1,

selecting by the central processor a first path between the node and the requesting node based at least in part on stored paths for the information request packet at the node,

reducing by the central processor the counter for each third party present along the first path by a number of packets to be sent over the first path,

selecting by the central processor at least one second path between the node and the requesting node based at least in part on stored paths for the information request packet at the node, and

reducing by the central processor the counter for each third party present along the at least one second path by a number of packets to be sent over the at least one second path.

14. A method comprising:

sending an information request packet from a requesting node into a federated coalition network having a plurality of nodes owned by at least two other parties,

receiving the information request packet by at least one neighboring node of the requesting node,

updating a header information of the information request packet to include identification of the node that received the information request including identity of a party owning the recipient node,

sending the information request packet from the node that received the information request packet to nodes in communication with it other than the requesting node,

receiving at least one information request packet at a recipient node from at least one neighboring node,

conducting a search of information at the recipient node by the recipient node to determine if the requested information is present,

when the requested information is present, then the recipient node

sends an acknowledgement to a requesting node using header information present in the information request packet to route the acknowledgement back to the requesting node,

linear network codes the requested information into m packets where m is greater than or equal to k, which is the number of packets needed to be received by the requesting node to reconstruct the requested information,

selects paths between the recipient node and the requesting node such that no third party to the recipient node and the requesting node will have more than k−

1 different packets pass through any one or more node controlled by that third party, and

transmits the m packets distributed over the selected paths, and

storing a path of any received information request packet in a memory of the node.

15. The method according to claim 14, further comprising:

collecting any acknowledgement sent in response to the information request packet for a period of time equal to twice a network traversal time for the federated coalition network by the requesting node,

sending a stop packet by the requesting node to any node neighboring the requesting node after receiving a ready packet from any node that sent the acknowledgement,

receiving a stop packet for the information request packet by the at least one neighboring node,

stopping the sending of the information request packet by the neighboring node in response to receiving the stop packet, and

forwarding the stop packet to each neighboring node other than the neighboring node that sent the stop request.

16. The method according to claim 14, further comprising:

checking a header of each received information request packet for a path to determine whether the recipient node or the neighboring node of the requesting node is present in the path or a second neighboring node other than the neighboring node that sent the information request packet is present in the path, and

when the determination is positive, disregarding the information request packet.

17. The method according to claim 14, further comprising

wherein selecting paths includes

setting a counter for each other third party present in the federated coalition network equal to k−

1,

selecting a first path between the recipient node and the requesting node based at least in part on stored paths for the information request packet,

reducing the counter for each third party present along the first path by a number of packets to be sent over the first path,

selecting at least one second path between the recipient node and the requesting node based at least in part on stored paths for the information request packet, and

reducing the counter for each third party present along the at least one second path by a number of packets to be sent over the at least one second path.

18. The method according to claim 17, wherein the first path and the at least one second path are selected based on at least a length of the paths such that a shortest path is selected for the first path and a next shortest path is selected for the second path.

19. A method comprising:

sending a request for information from a requesting node into a federated coalition network having a plurality of nodes owned by at least two other parties,

collecting any acknowledgement sent in response to the information request for a period of time equal to twice a network traversal time for the federated coalition network by the requesting node,

sending a stop packet by the requesting node to any node neighboring the requesting node after receiving a ready packet from any node that sent the acknowledgement,

receiving at least k linear network coded packets by any node that sent an acknowledgement to the requesting node such that no other party in the federated coalition network received more than k−

1 different packets,

reconstructing the information from the at least k linear coded packets, and

storing a path of any received information request packet in a memory of the node.