Efficient service discovery for peer-to-peer networking devices

• US 8,285,860 B2
• Filed: 01/14/2010
• Issued: 10/09/2012
• Est. Priority Date: 03/16/2009
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: McGuire, Rory L. P., Van Milligan, Michael, Conn, Jason, Graessley, Joshua, Prats, Augustin, Tucker, Brian
• Primary Examiner(s): Meky, Moustafa M
• Assistant Examiner(s): KIM, HEE SOO
• Application Number:
  US12/687,814
• Publication Number:
  US 20100235525A1
• Time in Patent Office: 999 Days
• Field of Search: 709/228
• US Class Current: 709/228
• CPC Class Codes: H04L 2101/30 Types of network names
• CPC Class Codes: H04L 41/50 Network service management, e.g. ensuring proper service fulfilment according to agreements
• CPC Class Codes: H04L 61/4511 using domain name system [DNS]
• CPC Class Codes: H04L 61/4541 Directories for service discovery
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1065 Discovery involving distributed pre-established resource-based relationships among peers, e.g. based on distributed hash tables [DHT] pre-configuration of logical or physical connections H04L67/1053
• CPC Class Codes: H04L 67/51 Discovery or management thereof, e.g. service location protocol [SLP] or web services
• CPC Class Codes: H04W 4/00 Services specially adapted for wireless communication networks; Facilities therefor
• CPC Class Codes: H04W 48/16 Discovering, processing access restriction or access information
• CPC Class Codes: H04W 84/12 WLAN [Wireless Local Area Networks]
• CPC Class Codes: H04W 92/18 between terminal devices

Abstract

Techniques for discovering and/or advertising services are described herein. A first bitmask is received from a remote device over a wireless network, the first bitmask having one or more bits that have a predetermined logical value. Each bit represents a particular service provided by the remote device. A logical operation is performed between the first bitmask and a second bitmask locally generated within a local device, where the second bitmask represents a service being searched by the local device. It is determined whether the remote device is potentially capable of providing the service being searched by the local device based on a result of the logical operation.

Claims

1. A machine-implemented method for discovering a service in a wireless environment, the method comprising:

receiving a service discovery request from a client application of a local device, wherein the service discovery request is to discover a service from one or more remote devices over a wireless network;

computing a key and value pair (key/value pair) based on the service discovery request, the key/value pair representing the service to be discovered;

generating a local bitmask based on the key of the key/value pair, the local bitmask including at least one bit having a predetermined logical value corresponding to a key of the key/value pair;

broadcasting an inquiry message in the wireless network, the inquiry message inquiring possible services possible provided by the remote devices over the wireless network;

receiving one or more remote bitmasks from the remote devices, each of the remote bitmasks including one or more bits corresponding to one or more services possibly provided by the remote devices, including receiving a first bitmask from a first remote device over the wireless network, the first bitmask having one or more bits that have a predetermined logical value, each representing a particular service provided by the first remote device; and

for each of the remote bitmasks, comparing the remote bitmask with the local bitmask to determine whether a respective remote device is potentially capable of providing the requested service, including performing a logical operation between the first bitmask and the local bitmask, and determining whether the first remote device is potentially capable of providing the service being searched by the local device based on a result of the logical operation.

2. The method of claim 1, wherein the service discovery request is a domain name service (DNS) query packet having a service identifier identifying the requested service, and wherein the key/value pair is generated based on the service identifier of the DNS query packet.

3. The method of claim 1, wherein the logical operation is a logical AND operation, and wherein any bit remained in the result of the logical operation that has the predetermined logical value indicates that the first remote device is potentially capable of providing the service being searched.

4. The method of claim 1, further comprising:

establishing a session connection with the first remote device over the wireless network, if it is determined that the first remote device is potentially capable of providing the service being searched; and

receiving one or more key/value pairs from the first remote device over the session connection, each key/value pair corresponding to a bit of the first bitmask having the predetermined logical value.

5. The method of claim 4, wherein a value of a particular key/value pair includes further detailed information associated with a service that is identified by a key of the particular key/value pair.

6. The method of claim 5, further comprising examining each key/value pair received to determine whether the first remote device is actually capable of providing the service being searched.

7. The method of claim 2, wherein the DNS query packet further includes one or more resource records to specify detailed information of the requested service, wherein the key of the key/value pair is generated based on the service identifier of the DNS query packet, and wherein a value of the key/value pair is generated based on the one or more resource records of the DNS query packet.

8. The method of claim 1, wherein generating the local bitmask comprises hashing the key of the key/value pair using a predetermined hash function.

9. A non-transitory machine-readable storage medium having instructions stored therein, which when executed by a machine, cause the machine to perform a method for discovering services in a wireless environment, the method comprising:

receiving a service discovery request from a client application of a local device, wherein the service discovery request is to discover a service from one or more remote devices over a wireless network;

computing a key and value pair (key/value pair) based on the service discovery request, the key/value pair representing the service to be discovered;

generating a local bitmask based on the key of the key/value pair, the local bitmask including at least one bit having a predetermined logical value corresponding to a key of the key/value pair;

broadcasting an inquiry message in the wireless network, the inquiry message inquiring possible services possible provided by the remote devices over the wireless network;

receiving one or more remote bitmasks from the remote devices, each of the remote bitmasks including one or more bits corresponding to one or more services possibly provided by the remote devices, including receiving a first bitmask from a first remote device over the wireless network, the first bitmask having one or more bits that have a predetermined logical value, each representing a particular service provided by the first remote device;

for each of the remote bitmasks, comparing the remote bitmask with the local bitmask to determine whether a respective remote device is potentially capable of providing the requested service, including performing a logical operation between the first bitmask and the local bitmask, and determining whether the first remote device is potentially capable of providing the service being searched by the local device based on a result of the logical operation.

10. The non-transitory machine-readable storage medium of claim 9, wherein the service discovery request is a domain name service (DNS) query packet having a service identifier identifying the requested service, and wherein the key/value pair is generated based on the service identifier of the DNS query packet.

11. The non-transitory machine-readable storage medium of claim 9, wherein the logical operation is a logical AND operation, and wherein any bit remained in the result of the logical operation that has the predetermined logical value indicates that the remote device is potentially capable of providing the service being searched.

12. The non-transitory machine-readable storage medium of claim 9, wherein the method further comprises:

establishing a session connection with the first remote device over the wireless network, if it is determined that the first remote device is potentially capable of providing the service being searched; and

receiving one or more key/value pairs from the first remote device over the session connection, each key/value pair corresponding to a bit of the first bitmask having the predetermined logical value.

13. The non-transitory machine-readable storage medium of claim 12, wherein a value of a particular key/value pair includes further detailed information associated with a service that is identified by a key of the particular key/value pair.

14. The non-transitory machine-readable storage medium of claim 13, wherein the method further comprises examining each key/value pair received to determine whether the first remote device is actually capable of providing the service being searched.

15. The non-transitory machine-readable storage medium of claim 10, wherein the DNS query packet further includes one or more resource records to specify detailed information of the requested service, wherein the key of the key/value pair is generated based on the service identifier of the DNS query packet, and wherein a value of the key/value pair is generated based on the one or more resource records of the DNS query packet.

16. The non-transitory machine-readable storage medium of claim 9, wherein generating the local bitmask comprises hashing the key of the key/value pair using a predetermined hash function.

17. An apparatus for searching a service in a wireless environment, the apparatus comprising:

a service advertisement unit to receive a service discovery request from a client application of a local device, wherein the service discovery request is to discover a service from one or more remote devices over a wireless network;

a key and value (key/value) generator to generate a key/value pair based on the service discovery request, the key/value pair representing the service to be discovered;

a service bitmask generator to generate a local bitmask based on the key of the key/value pair, the local bitmask including at least one bit having a predetermined logical value corresponding to a key of the key/value pair, wherein the service advertisement unit is to broadcast an inquiry message in the wireless network, the inquiry message inquiring possible services possible provided by the remote devices over the wireless network;

a wireless communications interface to receive one or more remote bitmasks from the remote devices, each of the remote bitmasks including one or more bits corresponding to one or more services possibly provided by the remote devices, including a first bitmask from a first remote device over a wireless network, the first bitmask having one or more bits that have a predetermined logical value, each representing a particular service provided by the remote device; and

a wireless processing unit coupled to the wireless communications interface to perform a logical operation between the first bitmask and the local bitmask, and to determine whether the first remote device is potentially capable of providing the service being searched by the local device based on a result of the logical operation.

18. The apparatus of claim 17, further comprising:

an application programming interface (API) to receive a request for searching the service from an application, the request including an identifier identifying the service being searched; and

a service discovery unit coupled to the API to generate a second bitmask based on identifier identifying the service being searched and to pass the second bitmask to the wireless processing unit and wherein the wireless environment provides communication between devices which are compatible with an IEEE 802.11 standard.

19. The apparatus of claim 18, wherein the wireless processing unit is further configured to:

establish a session connection with the remote device over the wireless network, if it is determined that the remote device is potentially capable of providing the service being searched, and

receive one or more key/value pairs from the remote device over the session connection, each key/value pair corresponding to a bit of the first bitmask having the predetermined logical value.

20. A machine-implemented method for advertising a service in a wireless environment, the method comprising:

generating a key/value pair based on an identifier of a service to be advertised by a local device;

performing a hash operation on a key of the key/value pair to generate a bitmask, the bitmask including a bit having a predetermined logical value;

in response to an inquiry message from a remote device over a wireless network for searching for a service, transmitting the bitmask to the remote device over the wireless network to allow the remote device to determine whether the local device is potentially capable of providing a service being searched based on the bitmask, wherein the service is to be performed by the local device and received by the remote device;

establishing a session connection with the remote device over the wireless network, wherein the session connection is established if the remote device determines that the local device is potentially capable of providing the service being searched based on the bitmask; and

transmitting the key/value pair to the remote device over the wireless network to allow the remote device to determine whether the local device is actually capable of providing the service being searched based on the key/value pair, wherein the wireless environment provides communication between devices which are compatible with an IEEE 802.11 standard.

21. The method of claim 20, wherein the key/value pair is generated based on domain name system (DNS) information associated with the service being advertised.

22. A non-transitory machine-readable storage medium having instructions stored therein, which when executed by a machine, cause the machine to perform a method for advertising a service in a wireless environment, the method comprising:

generating a key/value pair based on an identifier of a service to be advertised by a local device;

performing a hash operation on a key of the key/value pair to generate a bitmask, the bitmask including a bit having a predetermined logical value;

in response to an inquiry message from a remote device over a wireless network for searching for a service, transmitting the bitmask to the remote device over the wireless network to allow the remote device to determine whether the local device is potentially capable of providing a service being searched based on the bitmask, wherein the service is to be performed by the local device and received by the remote device;

establishing a session connection with the remote device over the wireless network, wherein the session connection is established if the remote device determines that the local device is potentially capable of providing the service being searched based on the bitmask; and

transmitting the key/value pair to the remote device over the wireless network to allow the remote device to determine whether the local device is actually capable of providing the service being searched based on the key/value pair, wherein the wireless environment provides communication between devices which are compatible with an IEEE 802.11 standard.

23. The non-transitory machine-readable storage medium of claim 22, wherein the key/value pair is generated based on domain name system (DNS) information associated with the service being advertised.

24. An apparatus for advertising a service in a wireless environment, the apparatus comprising:

a service discovery unit to generate a key/value pair based on an identifier of a service to be advertised by a local device; and

a wireless processing unit coupled to the service discovery unit to perform a hash operation on a key of the key/value pair to generate a bitmask, the bitmask including a bit having a predetermined logical value,

wherein in response to an inquiry message from a remote device over a wireless network for searching for a service, the wireless processing unit is configured to transmit the bitmask to the remote device over the wireless network to allow the remote device to determine whether the local device is potentially capable of providing a service being searched based on the bitmask, wherein the service is to be performed by the local device and received by the remote device,

wherein the wireless processing unit is further configured to

establish a session connection with the remote device over the wireless network, wherein the session connection is established if the remote device determines that the local device is potentially capable of providing the service being searched based on the bitmask, and

transmit the key/value pair to the remote device over the wireless network to allow the remote device to determine whether the local device is actually capable of providing the service being searched based on the key/value pair and wherein the wireless environment provides communication between devices which are compatible with an IEEE 802.11 standard.

25. The apparatus of claim 24, wherein the key/value pair is generated based on domain name system (DNS) information associated with the service being advertised.