Back to results
US 9,179,305 B2Granted
Bloom filter based device discovery
AssigneeQUALCOMM Incorporated
InventorsWassim Haddad, Michaela Vanderveen, Georgios Tsirtsis, Vincent D. Park
Life of this patent
Estimating the term…
Abstract
Aspects describe enabling two peers that have already paired together under some circumstances to re-identify themselves under different circumstances so that the peers can bypass performing another pairing only to discover that they are already paired. A Bloom filter is constructed from an available pool of locally selected identifiers and is sent to a peer node in a first message. Upon receiving the message with the Bloom filter, peer node checks all its known identifiers. If peer node finds that one of its identifiers is a member of the Bloom filter, peer node sends a reply in order to achieve a mutual identification.
Claims49
A method performed by a first peer node in a communication network, comprising:
- filtering, via a hardware-based processor of the first peer node, a plurality of selected identifiers through a Bloom filter to produce a bit vector, the plurality of selected identifiers being a subset of pairing identifiers that identify a subset of previously established pairing relationships between the first peer node and other peer nodes, each pairing identifier of the subset based on a unique identifier selected by the first peer node and another unique identifier selected by a respective one of the other peer nodes;
- inserting, into a first message, the bit vector produced by the Bloom filter;
- transmitting, via a transmitter of the first peer node, the first message to a second peer node of the communication network;
- and
- receiving, via a receiver of the first peer node, second message from the second peer node, the second message comprising a packet and indicating a match to one of the plurality of selected identifiers, the match representing a potential pairing relationship between the first peer node and the second peer node.
2 more elements
A communications apparatus, comprising:
- a processor implemented at least partially in hardware;
- a memory storing processor-executable instructions that, responsive to execution by the processor, cause the processor to implement operations comprising:
- filtering a subset of pairing identifiers through a Bloom filter to obtain a bit vector, the subset of pairing identifiers identifying a subset of previously established pairing relationships between the communications apparatus and peer nodes of a communication network, each pairing identifier of the subset based on a unique identifier selected by the communications apparatus and another unique identifier selected by a respective one of the peer nodes;
- sending, to one of the peer nodes, the bit vector in a message;
- and
- receiving, from the peer node, a reply message that includes a packet and a pairing identifier that corresponds to one of the subset of pairing identifiers indicated in the bit vector.
3 more elements
A communication apparatus for discovering peer nodes of an ad hoc network, comprising:
- means for filtering a subset of pairing identifiers through a Bloom filter mechanism that outputs a bit vector, wherein marked bits of the bit vector correspond to the subset of pairing identifiers that identify a subset of previously established pairing relationship between the communications apparatus and the peer nodes of the ad hoc network, each pairing identifier of the subset based on a unique identifier selected by the communication apparatus and another unique identifier selected by a respective one of the peer nodes;
- means for transmitting, to one of the peer nodes, a first message that includes the bit vector;
- and
- means for receiving, from the peer node, a second message that includes one of the pairing identifiers in the subset of pairing identifiers and a corresponding pairing identifier.
1 more element
One or more non-transitory computer-readable media storing processor executable instructions that, responsive to execution by a processor, implement operations comprising:
- filtering a plurality of pairing identifiers through a Bloom filter to produce a bit vector, the plurality of pairing identifiers identifying a subset of previously established pairing relationship between a first peer node and other peer nodes of a communication network, each pairing identifier of the plurality based on a unique identifier selected by the first peer node and another unique identifier selected by a respective one of the other peer nodes;
- inserting, into a first message, the bit vector produced through the Bloom filter;
- transmitting the first message to a second peer node of the communication network;
- and
- receiving, from the second peer node, a second message comprising a packet that indicates a match to one of the plurality of pairing identifiers represented by the bit vector.
2 more elements
At least one processor configured to implement a filter mechanism, comprising:
- a first module for filtering a subset of pairing identifiers through a Bloom filtering mechanism to obtain a bit vector, the subset of pairing identifiers identifying a subset of previously established pairing relationships between a first peer node and other peer nodes of a communication network, each pairing identifier of the subset based on a unique identifier selected by the first peer node and another unique identifier selected by a respective one of the other peer nodes;
- a second module for transmitting, to a second peer node, a message that includes the bit vector obtained from the Bloom filtering mechanism;
- a third module for receiving, from the second peer node, a reply that includes a packet and an identifier that corresponds to one of the subset of pairing identifiers included in the bit vector;
- and
- a fourth module for exchanging data with the second peer node if the packet is successfully decoded.
2 more elements
A method performed by a communication device for identifying a preexisting pairing relationship, comprising:
- receiving, via a receiver of the communication device, and from a peer node, a first message that comprises a bit vector provided by a Bloom filter, wherein the bit vector indicates a plurality of peer node pairing identifiers that identify a subset of previously established pairing relationships between the peer node and other peer nodes, each pairing identifier of the plurality based on a unique identifier selected by the peer node and another unique identifier selected by a respective one of the other peer nodes;
- evaluating, via a processor of the communication device, the first message against a plurality of communication device pairing identifiers associated with pairing relationships of the communication device to ascertain if one of the communication device pairing identifiers matches one of the peer node pairing identifiers received in the bit vector;
- and
- transmitting, via a transmitter of the communication device and to the peer node, a second message that includes a matched communication device pairing identifier and a peer node pairing identifier received in the bit vector.
1 more element
A communication apparatus, comprising:
- a processor implemented at least partially in hardware;
- a memory storing processor-executable instructions that responsive to execution by the processor, cause the processor to implement operations comprising:
- receiving, from a peer node, a message that includes a bit vector provided by a Bloom filter, the bit vector indicating a plurality of pairing identifiers that identify a subset of previously established pairing relationships between the peer node and other peer nodes, each pairing identifier of the plurality based on a unique identifier selected by the peer node and another unique identifier selected by a respective one of the other peer nodes;
- determining which bits in the bit vector would be activated if the message included one of a plurality of pairing identifiers known by the communication apparatus;
- matching activated bits to a pairing identifier known by the communication apparatus;
- transmitting, to the peer node, a reply message that includes a matched pairing identifier if the bits were activated;
- and
- exchanging data with the peer node if the activated bits match the pairing identifier known by the communication apparatus.
5 more elements
A communications apparatus that implements a bit vector for peer discovery, comprising:
- means for receiving, from a peer node, a first message that includes a bit vector provided by a Bloom filter, the bit vector indicating pairing identifiers of the peer node, the pairing identifiers identifying a subset of previously established pairing relationships between the peer node and other peer nodes, each of the pairing identifiers based on a unique identifier selected by the peer node and another unique identifier selected by a respective one of the other peer nodes;
- means for identifying bits that should be activated in the bit vector if one of the pairing identifiers matches one of a plurality of pairing identifiers known by communications apparatus;
- means for determining a match between one of the pairing identifiers indicated in the bit vector and one of the plurality of pairing identifiers known by the communications apparatus;
- means for transmitting, to the peer node, a second message that includes the one of the pairing identifiers indicated in the bit vector and the one of the plurality of pairing identifiers known by the communication device;
- and
- means for exchanging data with the peer node if one of the pairing identifiers indicated in the bit vector matches one of the plurality of pairing identifiers known by the communications apparatus.
3 more elements
One or more non-transitory computer-readable media storing processor executable instructions that, responsive to execution by a processor, implement operations comprising:
- receiving, from a peer node, a first message that comprises a bit vector provided by a Bloom filter, wherein the bit vector indicates pairing identifiers that identify a subset of previously established pairing relationships between the peer node and other peer nodes, each of the pairing identifiers based on a unique identifier selected by the peer node and another unique identifier selected by a respective one of the other peer nodes;
- evaluating the bit vector of the first message against a plurality of known pairing identifiers to ascertain if a known pairing identifier matches one of the pairing identifiers indicated in the bit vector;
- transmitting, to the peer node, a second message that includes a matched known pairing identifier and the pairing identifier indicated in the bit vector;
- and
- exchanging, responsive to matching the known pairing identifier, data with the peer node.
2 more elements
At least one processor of a first peer node, the at least one processor configured to perform discovery in a peer-to-peer communication network, comprising:
- a first module for receiving, from a second peer node, a message that includes a bit vector provided by a Bloom filter, the bit vector indicating a pairing identifiers that identify a subset of previously established pairing relationships between the second peer node and other peer nodes, each of the pairing identifiers based on a unique identifier selected by the second peer node and another unique identifier selected by a respective one of the other peer nodes;
- a second module for determining which bits in the bit vector would be activated if the message included a pairing identifier that identifies a previously established pairing relationship between the first peer node and the second peer node;
- a third module for matching the set bits to pairing identifiers known by the first peer node;
- a fourth module for transmitting, to the second peer node, a reply message that includes a matched known pairing identifier if the bits were activated;
- and
- a fifth module for exchanging, in response to matching a known pairing identifier, data with the second peer node.
3 more elements
Dependencies are inferred from the claim text.