Method and apparatus for establishing a virtual interface for a set of mutual-listener devices

Patent metadata

Field	Value
Publication number	US-2015200852-A1
Application number	US-201414155125-A
Country	US
Kind code	A1
Filing date	Jan 14, 2014
Priority date	Jan 14, 2014
Publication date	Jul 16, 2015
Grant date	—

Abstract

An ad-hoc network device facilitates creating a virtual interface for a set of mutual-listener devices that have a duplex communication with each other. During operation, the network device can receive a packet, and identifies a virtual interface to which the packet is directed. The network device can determine whether the local network device is a member of the virtual interface, and if so, processes the packet as an intended recipient of the packet.

First claim

What is claimed is:

1 . A computer-implemented method, comprising:
receiving, by a network device, a packet; identifying a virtual interface to which the packet is directed, wherein members of the virtual interface include a set of mutually-connected network peers; determining whether the local network device is a member of the virtual interface; and in response to determining that the local network device is a member of the virtual interface, processing the packet as an intended recipient of the packet.

2 . The method of claim 1 , further comprising:
obtaining duplex-neighborhood information from one or more network neighbors, wherein a network neighbor's duplex-neighborhood information indicates at least a set of neighboring devices to the network neighbor; and defining one or more virtual interfaces based on the duplex-neighborhood information, wherein a respective virtual interface's member nodes include the local network node and a set of mutually-connected network peers.

3 . The method of claim 2 , further comprising generating an interface identifier for a respective virtual interface, wherein generating the interface identifier involves one or more of:
computing a hash value for device identifiers that belong to the virtual interface; and constructing a bloom filter for the device identifiers that belong to the virtual interface.

4 . The method of claim 1 , wherein identifying the virtual interface involves obtaining an interface identifier from the packet's header; and
wherein determining whether the local network device is a member of the identified virtual interface involves comparing the interface identifiers to a set of pre-computed identifiers.

5 . The method of claim 4 , wherein the interface identifier includes one or more of:
a hash computed from a set of device identifiers for members of the virtual interface; and an identifier pre-negotiated between the members of the virtual interface.

6 . The method of claim 1 , wherein identifying the virtual interface involves obtaining a bloom filter from the packet's header, wherein the bloom filter is generated based on device identifiers for members of a virtual interface, and wherein determining whether the local network device is a member of the identified virtual interface involves:
querying the bloom filter, using device identifiers for a set of network neighbors of the local network node, to determine a set of device identifiers that are members of the bloom filter; and determining a virtual interface that corresponds to the determined set of device identifiers.

7 . The method of claim 1 , wherein identifying the virtual interface involves obtaining a set of device identifiers from the packet's header, and wherein determining that the local network device is a member of the target interface involves one or more of:
verifying that the local device is a member of the packet header's set of device identifiers; and verifying that the network peers associated with the device identifiers are duplex neighbors of the local network node.

8 . The method of claim 1 , further comprising:
monitoring packets transmitted by one or more network peers to detect a change in a network neighborhood; determining a set of mutual-listener groups in the network neighborhood; determining a set of virtual interfaces to which the local network node is a member; and activating the determined set of virtual interfaces.

9 . The method of claim 1 , further comprising transmitting a packet to negotiate a device membership for one or more virtual interfaces, wherein the packet includes one or more of:
a set of network peers for the local network node; a set of virtual interfaces to which the local network node is a member; a bloom filter of the network peers; and a bloom filter of the virtual interfaces.

10 . A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method, the method comprising:
receiving a packet; identifying a virtual interface to which the packet is directed, wherein members of the virtual interface include a set of mutually-connected network peers; determining whether the local network device is a member of the virtual interface; and in response to determining that the local network device is a member of the virtual interface, processing the packet as an intended recipient of the packet.

11 . The storage medium of claim 10 , the method further comprising:
obtaining duplex-neighborhood information from one or more network neighbors, wherein a network neighbor's duplex-neighborhood information indicates at least a set of neighboring devices to the network neighbor; and defining one or more virtual interfaces based on the duplex-neighborhood information, wherein a respective virtual interface's member nodes include the local network node and a set of mutually-connected network peers.

12 . The storage medium of claim 11 , the method further comprising generating an interface identifier for a respective virtual interface, wherein generating the interface identifier involves one or more of:
computing a hash value for device identifiers that belong to the virtual interface; and constructing a bloom filter for the device identifiers that belong to the virtual interface.

13 . The storage medium of claim 10 , wherein identifying the virtual interface involves obtaining an interface identifier from the packet's header; and
wherein determining whether the local network device is a member of the identified virtual interface involves comparing the interface identifiers to a set of pre-computed identifiers.

14 . The storage medium of claim 13 , wherein the interface identifier includes one or more of:
a hash computed from a set of device identifiers for members of the virtual interface; and an identifier pre-negotiated between the members of the virtual interface.

15 . The storage medium of claim 10 , wherein identifying the virtual interface involves obtaining a bloom filter from the packet's header, wherein the bloom filter is generated based on device identifiers for members of a virtual interface, and wherein determining whether the local network device is a member of the identified virtual interface involves:
querying the bloom filter, using device identifiers for a set of network neighbors of the local network node, to determine a set of device identifiers that are members of the bloom filter; and determining a virtual interface that corresponds to the determined set of device identifiers.

16 . The storage medium of claim 10 , wherein identifying the virtual interface involves obtaining a set of device identifiers from the packet's header, and wherein determining that the local network device is a member of the target interface involves one or more of:
verifying that the local device is a member of the packet header's set of device identifiers; and verifying that the network peers associated with the device identifiers are duplex neighbors of the local network node.

17 . The storage medium of claim 10 , the method further comprising:
monitoring packets transmitted by one or more network peers to detect a change in a network neighborhood; determining a set of mutual-listener groups in the network neighborhood; determining a set of virtual interfaces to which the local network node is a member; and activating the determined set of virtual interfaces.

18 . A computer-implemented method, comprising:
generating, by a network device, a

Assignees

• Palo Alto Res Ct Inc

Inventors

• Solis Ignacio

Classifications

• H04W84/18

  Self-organising networks, e.g. ad-hoc networks or sensor networks · CPC title

• H04L12/1886

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

• H04L45/7453 Primary

  using hashing · CPC title

• H04L5/14

  Two-way operation using the same type of signal, i.e. duplex · CPC title

• H04L12/189

  in combination with wireless systems (selective distribution or broadcast in wireless communication networks H04W4/06) · CPC title