Duplicate address detection based on distributed bloom filter

Patent metadata

Field	Value
Publication number	US-9628435-B2
Application number	US-201414516707-A
Country	US
Kind code	B2
Filing date	Oct 17, 2014
Priority date	Oct 17, 2014
Publication date	Apr 18, 2017
Grant date	Apr 18, 2017

Abstract

In one embodiment, a method comprises: generating, by a first network device in a network, a Bloom filter bit vector representing device addresses of devices having attached to at least one of the first network device or a second network device in the network; and determining whether a new device address is not a duplicate of any of the device addresses in the network based on the Bloom filter bit vector.

First claim

What is claimed is:

1. A method comprising:
generating, by a first network device in a network, a Bloom filter bit vector representing device addresses of devices having attached to at least one of the first network device or a second network device in the network;
determining whether a new device address is not a duplicate of any of the device addresses in the network based on the Bloom filter bit vector; and
receiving, by the first network device, a remote Bloom filter bit vector from the second network device, the remote Bloom filter bit vector representing the device addresses of remote devices having attached to the second network device;
the generating including generating a local Bloom filter bit vector based on the device addresses of the devices having attached to the first network device, the Bloom filter bit vector generated based on the local Bloom filter bit vector and the remote Bloom filter bit vector.

2. The method of claim 1 , wherein the determining includes:
identifying the new device address as conflicting with at least one of the local Bloom filter bit vector or the remote Bloom filter bit vector; and
determining whether the new device address is a duplicate based on causing resolution of the new device address relative to an address table associated with the conflicted one Bloom filter bit vector.

3. The method of claim 2 , wherein the causing resolution includes the first network device sending a unicast message to the second network device for resolution of the new device address relative to the address table maintained by the second network device for the remote Bloom filter bit vector.

4. The method of claim 1 , wherein the determining includes confirming the new device address is not a duplicate based on:
generating a device Bloom filter bit vector from the new device address; and
determining the device Bloom filter bit vector does not conflict with the Bloom filter bit vector.

5. The method of claim 1 , wherein if the new device address is not a duplicate of any of the device addresses in the network, the method further includes:
updating the Bloom filter bit vector based on the new device address; and
if the new device address was advertised in a registration request by an identifiable device in the network, sending a registration acknowledgement of the new device address to the identifiable device; or
if the new device address was advertised in a multicast message by the identifiable device, allowing the identifiable device to claim the new device address.

6. The method of claim 1 , further comprising:
receiving remote Bloom filter bit vectors from respective remote network devices in the network, including the second network device;
generating a local Bloom filter bit vector based on the device addresses of the devices having attached to the first network device, the local Bloom filter bit vector and the remote Bloom filter bit vectors forming the Bloom filter bit vector as a distributed Bloom filter.

7. The method of claim 6 , wherein:
the determining includes identifying the new device address conflicting with an identified one of the remote Bloom filter bit vectors;
the method further comprising sending a unicast message to the remote network device associated with the identified one remote Bloom filter bit vector.

8. The method of claim 1 , wherein:
the Bloom filter bit vector is generated based on the first network device applying one or more locally-specific hash functions on the device addresses of the devices having attached to the first network device;
the method further comprising receiving, by the first network device from the second network device, a remote Bloom filter bit vector and one or more remote device-specific hash functions used by the second network device to generate the remote Bloom filter bit vector;
the determining whether the new device address is not a duplicate is based on determining whether the new device address conflicts with the Bloom filter bit vector relative to the one or more locally-specific hash functions, and determining whether the new device address conflicts with the remote Bloom filter bit vector relative to the one or more remote device-specific hash functions.

9. An apparatus comprising:
a memory circuit configured for storing a Bloom filter bit vector;
a processor circuit configured for generating the Bloom filter bit vector representing device addresses of devices having attached to at least one of the apparatus or a second network device in a network, the processor circuit further configured for determining whether a new device address is not a duplicate of any of the device addresses in the network based on the Bloom filter bit vector; and
a device interface circuit configured for receiving a remote Bloom filter bit vector from the second network device, the remote Bloom filter bit vector representing the device addresses of remote devices having attached to the second network device;
the processor circuit configured for generating a local Bloom filter bit vector based on the device addresses of the devices having attached to the apparatus, the Bloom filter bit vector generated based on the local Bloom filter bit vector and the remote Bloom filter bit vector.

10. The apparatus of claim 9 , wherein the processor circuit is configured for:
identifying the new device address as conflicting with at least one of the local Bloom filter bit vector or the remote Bloom filter bit vector; and
determining whether the new device address is a duplicate based on causing resolution of the new device address relative to an address table associated with the conflicted one Bloom filter bit vector.

11. The apparatus of claim 10 , wherein the processor circuit is configured for sending a unicast message to the second network device for resolution of the new device address relative to the address table maintained by the second network device for the remote Bloom filter bit vector.

12. The apparatus of claim 9 , wherein the processor circuit is configured for confirming the new device address is not a duplicate based on:
generating a device Bloom filter bit vector from the new device address; and
determining the device Bloom filter bit vector does not conflict with the Bloom filter bit vector.

13. The apparatus of claim 9 , wherein the processor circuit is configured for:
updating the Bloom filter bit vector based on the new device address if the new device address is not a duplicate of any of the device addresses in the network; and
if the new device address is not a duplicate of any of the device addresses in the network and if the new device address was advertised in a registration request by an identifiable device in the network, sending a registration acknowledgement of the new device address to the identifiable device; or
if the new device address is not a duplicate of any of the device addresses in the network and if the new device address was advertised in a multicast message by the identifiable device, allowing the identifiable device to claim the new device address.

14. The apparatus of claim 9 , further comprising:
a device interface circuit configured for receiving remote Bloom filter bit vectors from respective remote network devices in the network, including the second network device;
the processor circuit configured for generating a local Bloom filter bit vector based on the device addresses of the devices having attached to the apparatus, the local Bloom filter bit vector and the remote Bloom filter bit vectors forming the Bloom filter bit vector as a distributed Bloom filter.

15. The apparatus of c

Assignees

• Cisco Tech Inc

Inventors

• Thubert Pascal
• Wetterwald Patrick
• Levy-Abegnoli Eric Michel

Classifications

• H04L12/185

  with management of multicast group membership · CPC title

• H04L12/1886

  with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains · CPC title

• H04L61/10 Primary

  of different types · CPC title

• H04L45/7459

  using Bloom filters · CPC title

• H04L61/5092 Primary

  by self-assignment, e.g. picking addresses at random and testing if they are already in use · CPC title