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

• US 9,379,979 B2
• Filed: 01/14/2014
• Issued: 06/28/2016
• Est. Priority Date: 01/14/2014
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Solis, Ignacio
• Primary Examiner(s): TRAN, PHUC H
• Application Number:
  US14/155,125
• Publication Number:
  US 20150200852A1
• Time in Patent Office: 896 Days
• Field of Search: 370/351, 370/395.53, 370/400, 370/408
• US Class Current: 1/1
• CPC Class Codes: H04L 12/1886 with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains
• CPC Class Codes: H04L 12/189 in combination with wireless systems selective distribution or broadcast in wireless communication networks H04W4/06
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 5/14 Two-way operation using the same type of signal, i.e. duplex
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

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.

Claims

1. A computer-implemented method, comprising:

obtaining, by a network device, 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;

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;

receiving, by the 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 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.

3. 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.

4. The method of claim 3, 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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:

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;

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;

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.

10. The storage medium of claim 9, 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.

11. The storage medium of claim 9, 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.

12. The storage medium of claim 11, 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.

13. The storage medium of claim 9, 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.

14. The storage medium of claim 9, 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.

15. The storage medium of claim 9, 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.

16. A computer-implemented method, comprising:

generating, by a network device, a packet for a remote device;

determining a next-hop destination for the packet;

determining a virtual interface for the next-hop destination, based on neighborhood connectivity information for the next-hop destination, and based on one or more of;

historical usage information for one or more virtual interfaces associated with the next-hop destination;

a change to neighborhood connectivity information since a packet was last sent to the next-hop destination; and

a change to neighborhood connectivity information since a packet was last sent to the virtual interface;

setting the virtual interface, and an identifier for the next-hop destination, in the packet; and

sending the packet via the virtual interface.

17. The method of claim 16, wherein the next-hop destination includes one or more of:

a network node;

a set of network nodes;

an anycast address; and

a broadcast address.

18. An apparatus, comprising:

a packet-processing module to generate a packet for a remote device;

a virtual-interface selecting module to determine a next-hop destination for the packet, and determine a virtual interface for the next-hop destination based on neighborhood connectivity information for the next-hop destination, and based on one or more of;

historical usage information for one or more virtual interfaces associated with the next-hop destination;

a change to neighborhood connectivity information since a packet was last sent to the next-hop destination; and

a change to neighborhood connectivity information since a packet was last sent to the virtual interface; and

a communication module;

wherein the packet-processing module is further configured to set the virtual interface, and an identifier for the next-hop destination, in the packet; and

wherein the communication module is configured to send the packet via the virtual interface.

19. The apparatus of claim 18, wherein the next-hop destination includes one or more of:

a network node;

a set of network nodes;

an anycast address; and

a broadcast address.