Ad-hoc service discovery protocol

• US 20040267876A1
• Filed: 06/30/2003
• Published: 12/30/2004
• Est. Priority Date: 06/30/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Schlimmer, Jeffrey C., Huitema, Christian, Hasha, Richard L., Kakivaya, Gopala Krishna R., Parham, Jeffrey B., Box, Don
• Granted Patent: US 7,685,288 B2
• Time in Patent Office: Days
• US Class Current: 709/200
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/51 Discovery or management thereof, e.g. service location protocol [SLP] or web services
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

Abstract

An ad-hoc discovery protocol improves reliability, security and scalability of multicast and server-based discovery. In switching from multicast to server-based discovery, the discovery client is made responsible for multicast suppression, and not discoverable devices with services. Messages include message identifier and time-to-live parameters to detect recast queries and avoid duplicating replies. A device'"'"'s announcement message includes endpoint identifier, configuration number and stateless boot time parameters to detect changed device configuration and rebooted state for refreshing cached device and service descriptions. Paging parameters allow a discovery client to control the number of discovery responses returned at a time from a discovery server.

Claims

1. A method of reliably discovering devices and services with ad-hoc and server-based operation in a network environment of devices acting as discovery clients and discovery responders, the method comprising:

detecting by a discovery client whether a discovery server is present;

in a detected absence of any discovery server, conducting discovery by the discovery client as a multicast operation;

in a detected presence of any discovery server, suppressing by the discovery client of its multicast operation and conducting discovery by the discovery client directed to the detected discovery server; and

continuing by the discovery responders to respond to multicast discovery regardless of the presence or absence of the discovery server in the network environment.

2. The method of claim 1, wherein the detecting comprises sending by the discovery client of a discovery query as a multicast operation to find any discovery server in the network environment.

3. A method of reliable multicast suppression in service discovery on ad-hoc networks, comprising:

sending a multicast discovery query for discovery servers by a discovery client on a network to find any discovery server present within a scope on the network;

receiving by the discovery client any response to the multicast discovery query;

upon receiving a response of a discovery server to the multicast discovery query, suppressing sending further multicast discovery queries for device services by the discovery client and sending further discovery queries for device services by the discovery client directly to the discovery server, while the discovery server remains present on the network; and

in absence of any response to the multicast discovery query, sending the any further discovery queries for device services by the discovery client as multicast discovery queries on the network.

4. The method of claim 3, wherein discovery responders continue to respond to multicast discovery queries for device services matching the respective discovery responders from the discovery client irrespective of the discovery server being present on the network.

5. A computing device operating as a discovery client in a network architecture for a discovery protocol capable of ad-hoc and server-based operation, the computing device comprising:

a memory storing software programming for an ad-hoc discovery protocol; and

a processor operating to execute the software programming in the memory;

wherein the software programming comprises;

programming code for switching the discovery client between server-based and ad-hoc discovery modes when a discovery server is determined to be present or absent, respectively, in a network in which the computing device is operating;

server-based discovery mode programming code for sending discovery queries of the discovery client directly to the discovery server determined to be present in the network; and

ad-hoc discovery mode programming code for sending discovery queries of the discovery client as a multicast transmission to discovery responders in the network.

6. The computing device of claim 5, wherein the software programming further comprises programming code for detecting the presence or absence of a discovery server in the network.

7. The computing device of claim 6, wherein the programming code for detecting comprises programming code for sending a multicast discovery query to find discovery servers present in the network.

8. A computer-readable media having computer-readable software programming thereon for executing on a discovery client in a network architecture of a discovery protocol capable of server-based and ad-hoc discovery, the software programming comprising:

programming code for switching the discovery client between server-based and ad-hoc discovery modes when a discovery server is determined to be present or absent, respectively, in a network in which the computing device is operating;

server-based discovery mode programming code for sending discovery queries of the discovery-client directly to the discovery server determined to be present in the network; and

ad-hoc discovery mode programming code for sending discovery queries of the discovery client as a multicast transmission to discovery responders in the network.

9. The computer-readable media of claim 8, wherein the software programming further comprises programming code for detecting the presence or absence of a discovery server in the network.

10. The computer-readable media of claim 9, wherein the programming code for detecting comprises programming code for sending a multicast discovery query to find discovery servers present in the network.

11. A distributed system of networked computing devices compliant with an ad-hoc service discovery protocol, the distributed system comprising:

at least one networked computing device operating as a discovery client according to a network architecture of the ad-hoc service discovery protocol, the discovery client having a server-based discovery mode and an ad-hoc discovery mode, the discovery client operating to determine whether any discovery server is present or absent in a network and switch to the server-based discovery mode or ad-hoc discovery mode, respectively, according to the determination, the discovery client operating in ad-hoc discovery mode to send discovery queries as multicast transmissions and operating in server-based discovery mode to suppress multicast transmission of discovery requests by the discovery client; and

at least one networked computing device operating as a discovery responder according to the network architecture of the ad-hoc service discovery protocol, the discovery responder operating regardless of presence or absence of a discovery server in the network to respond to multicast transmissions of discovery queries matching the discovery responder.

12. The distributed system of claim 11 wherein the discovery client has a configured mode, the discovery client operating in the configured mode to suppress multicast transmission of discovery requests by the discovery client and send such discovery requests directly to a specified discovery server specified in its configuration.

13. The distributed system of claim 11 wherein the discovery responder has a configured mode, the discovery responder operating in the configured mode to suppress response to multicast transmission of discovery requests.

14. A method of discovering device services in ad-hoc and server-managed networks of computing devices, the method comprising:

when connected in an ad-hoc network, sending discovery queries as a multicast transmission from a discovery client computing device; and

when connected in a server-managed network having a discovery server, sending discovery queries from the discovery client computing device as a directed transmission to the discovery server using a networking protocol that guarantees message delivery.

15. The method of claim 14 further comprising:

responding to discovery queries received as multicast transmissions by a computing device that match device services of the computing device regardless of whether connected in the ad-hoc or server-managed network.

16. The method of claim 14 wherein the networking protocol is the transmission control protocol (TCP).

17. A computer-readable media having a software program thereon executable on a computing device to perform a method of discovering device services in ad-hoc and server-managed networks of computing devices, the method comprising:

when the computing device is connected in an ad-hoc network, sending discovery queries as a multicast transmission from the computing device; and

when the computing device is connected in a server-managed network having a discovery server, sending discovery queries from the computing device directly to the discovery server using a networking protocol that guarantees message delivery.

18. The computer-readable media of claim 17 wherein the networking protocol is the transmission control protocol (TCP).

19. A computing device for discovering device services in ad-hoc and server-managed networks of computing devices, the method comprising:

means for, when connected in an ad-hoc network, sending discovery queries as a multicast transmission from a discovery client computing device; and

means for, when connected in a server-managed network having a discovery server, sending discovery queries from the discovery client computing device as a directed transmission to the discovery server using a networking protocol that guarantees message delivery.

20. The computing device of claim 19 wherein the networking protocol is the transmission control protocol (TCP).

21. A method of discovering device services in an ad-hoc networking environment of computing devices acting as discovery clients and discovery responders, wherein a discovery client sends a discovery query message as a multicast transmission one or more times, the discovery query message containing a message identifier, the method comprising:

maintaining a list of already processed messages by a discovery responder according to message identifier of the already processed messages;

receiving the discovery query message by a discovery responder;

determining based on the message identifier of the discovery query message and the discovery responder'"'"'s already processed messages list whether the discovery query message is newly received or a duplicate of a previously processed discovery query;

if the discovery query message is determined to be newly received;

sending a response to the discovery query if the query is a match to a device service of the discovery responder; and

adding an entry for the discovery query message to the discovery responder'"'"'s already processed messages list; and

if the discovery query message is determined to be a duplicate, not processing the discovery query of the discovery query message.

22. The method of claim 21 wherein the discovery query message further contains a time parameter indicative to a sending time period in which the discovery client sends the discovery query message one or more times, the method further comprising:

when adding an entry for the discovery query message,

determining by the discovery responder a receiving time period during which transmissions of the discovery query message may be received by the discovery responder based on the time parameter; and

inserting data representing the receiving time period in the entry;

wherein the determining whether the discovery query message is newly received or duplicate further comprises determining whether the received discovery query message was received within the receiving time period represented in an entry in the already processed message list with a matching message identifier.

23. The method of claim 22 further comprising removing entries from the discovery responder'"'"'s list of already processed messages after the receiving time period is expired.

24. A method of discovering device services in an ad-hoc networking environment of computing devices acting as discovery clients and discovery responders, the method comprising:

encoding by a discovery client a message identifier and a time parameter indicative of a sending time interval in a discovery query message; and

sending by the discovery client the discovery query message as a multicast transmission one or more times within the sending time interval.

25. The method of claim 24 further comprising:

maintaining a list of already processed messages by a discovery responder according to message identifier of the already processed messages, in which a receiving time period in which duplicates of respective already processed messages may be received is indicated;

receiving the discovery query message by a discovery responder;

determining based on the message identifier of the discovery query message and the receiving time periods indicated in the discovery responder'"'"'s already processed messages list whether the discovery query message is newly received or a duplicate of a previously processed discovery query;

if the discovery query message is determined to be newly received;

sending a response to the discovery query if the query is a match to a device service of the discovery responder; and

adding an entry for the discovery query message to the discovery responder'"'"'s already processed messages list indicating the receiving time period for the discovery query message based on the time parameter; and

if the discovery query message is determined to be a duplicate, not processing the discovery query of the discovery query message.

26. The method of claim 25 further comprising removing entries from the discovery responder'"'"'s list of already processed messages after the receiving time period is expired.

27. A computing device operating as a discovery client in a network architecture for an ad-hoc discovery protocol, the computing device comprising:

a memory storing software programming for an ad-hoc discovery protocol; and

a processor operating to execute the software programming in the memory;

wherein the software programming comprises;

programming code for encoding by a discovery client a message identifier and a time parameter indicative of a sending time interval in a discovery query message; and

programming code for sending by the discovery client the discovery query message as a multicast transmission one or more times within the sending time interval.

28. A computing device operating as a discovery responder in a network architecture for an ad-hoc discovery protocol, the computing device comprising:

a memory storing software programming for an ad-hoc discovery protocol; and

a processor operating to execute the software programming in the memory;

wherein the software programming comprises;

programming code for maintaining a list of already processed messages by the discovery responder according to message identifier of the already processed messages;

programming code for receiving a discovery query message from a discovery client by the discovery responder;

programming code for processing the received discovery query message, wherein the processing comprises;

determining based on the message identifier of the discovery query message and the discovery responder'"'"'s already processed messages list whether the discovery query message is newly received or a duplicate of a previously processed discovery query;

if the discovery query message is determined to be newly received;

sending a response to the discovery query if the query is a match to a device service of the discovery responder; and

adding an entry for the discovery query message to the discovery responder'"'"'s already processed messages list; and

if the discovery query message is determined to be a duplicate, not processing the discovery query of the discovery query message.

29. A computing device operating as a discovery responder in a network architecture for an ad-hoc discovery protocol, the computing device comprising:

a memory storing software programming for an ad-hoc discovery protocol; and

a processor operating to execute the software programming in the memory;

wherein the software programming comprises;

programming code for maintaining a list of already processed messages by a discovery responder according to message identifier of the already processed messages, in which a receiving time period in which duplicates of respective already processed messages may be received is indicated;

programming code for receiving a discovery query message from a discovery client by the discovery responder;

programming code for processing the received discovery query message, wherein the processing comprises;

determining based on the message identifier of the discovery query message and the receiving time periods indicated in the discovery responder'"'"'s already processed messages list whether the discovery query message is newly received or a duplicate of a previously processed discovery query;

if the discovery query message is determined to be newly received;

sending a response to the discovery query if the query is a match to a device service of the discovery responder; and

adding an entry for the discovery query message to the discovery responder'"'"'s already processed messages list indicating the receiving time period for the discovery query message based on the time parameter; and

if the discovery query message is determined to be a duplicate, not processing the discovery query of the discovery query message.

30. A computer-readable media having a software program thereon executable on a networked computing device acting as a discovery client in an ad-hoc networking environment according to an ad-hoc discovery protocol to effect a method of discovering device services on a network, the method comprising:

encoding by a discovery client a message identifier and a time parameter indicative of a sending time interval in a discovery query message; and

sending by the discovery client the discovery query message as a multicast transmission one or more times within the sending time interval.

31. A computer-readable media having a software program thereon executable on a networked computing device acting as a discovery responder in an ad-hoc networking environment according to an ad-hoc discovery protocol wherein a discovery client sends a discovery query message as a multicast transmission one or more times within a sending time interval to effect a method of discovering device services on a network, the discovery query message including a message identifier and a time parameter indicative of the sending time interval, the method comprising:

maintaining a list of already processed messages by the discovery responder according to message identifier of the already processed messages, in which a receiving time period in which duplicates of respective already processed messages may be received is indicated;

receiving the discovery query message by a discovery responder;

determining based on the message identifier of the discovery query message and the receiving time periods indicated in the discovery responder'"'"'s already processed messages list whether the discovery query message is newly received or a duplicate of a previously processed discovery query;

if the discovery query message is determined to be newly received;

sending a response to the discovery query if the query is a match to a device service of the discovery responder; and

adding an entry for the discovery query message to the discovery responder'"'"'s already processed messages list indicating the receiving time period for the discovery query message based on the time parameter; and

if the discovery query message is determined to be a duplicate, not processing the discovery query of the discovery query message.

32. The computer-readable media of claim 31 wherein the method further comprises removing entries from the discovery responder'"'"'s list of already processed messages after the receiving time period is expired.

33. A method of discovering device services in an ad-hoc networking environment of computing devices acting as discovery clients and discovery responders, the method comprising:

at boot-time of a discovery responder, generating a new value of a stateless boot time parameter of the discovery responder if operating state of the discovery responder since previous operation has been lost;

at time of the discovery responder joining a network,

creating an announcement message by the discovery responder for a device service provided by the discovery responder, the announcement message including the stateless boot time parameter; and

sending the announcement message by the discovery responder as a multicast transmission on the network.

34. The method of claim 33 wherein generating the new value comprises incrementing a boot counter to provide the new value of the stateless boot time parameter.

35. The method of claim 33 wherein generating the new value comprises reading a value from a real-time clock to provide the new value of the stateless boot time parameter.

36. A computing device operating as a discovery responder in a network architecture for an ad-hoc discovery protocol, the computing device comprising:

a memory storing software programming for an ad-hoc discovery protocol; and

a processor operating to execute the software programming in the memory;

wherein the software programming comprises;

programming code executing at boot-time of the discovery responder for generating a new value of a stateless boot time parameter of the discovery responder if operating state of the discovery responder since previous operation has been lost;

programming code executing at time of the discovery responder joining a network for creating an announcement message by the discovery responder for a device service provided by the discovery responder, the announcement message including the stateless boot time parameter, and sending the announcement message by the discovery responder as a multicast transmission on the network.

37. A computer-readable media having a software program thereon executable on a networked computing device acting as a discovery responder in an ad-hoc networking environment according to an ad-hoc discovery protocol to effect a method comprising:

at boot-time of a discovery responder, generating a new value of a stateless boot time parameter of the discovery responder if operating state of the discovery responder since previous operation has been lost;

at time of the discovery responder joining a network,

creating an announcement message by the discovery responder for a device service provided by the discovery responder, the announcement message including the stateless boot time parameter; and

sending the announcement message by the discovery responder as a multicast transmission on the network.

38. A method of discovering device services in an ad-hoc networking environment of computing devices acting as discovery clients and discovery responders, wherein a discovery responder sends a multicast announcement message for a device service and containing a stateless boot time parameter, the method comprising:

maintaining cache data of discovered device services in a discovery client;

receiving the announcement message from the discovery responder by a discovery client;

determining by the discovery client whether the device service of the announcement message matches the cache data; and

if so, determining whether the device service has lost operational state based on the stateless boot time parameter of the announcement message and the cache data.

39. A computing device operating as a discovery client in a network architecture for an ad-hoc discovery protocol, the computing device comprising:

a memory storing software programming for an ad-hoc discovery protocol; and

a processor operating to execute the software programming in the memory;

wherein the software programming comprises;

programming code for maintaining cache data of discovered device services in a discovery client, receiving the announcement message from the discovery responder by a discovery client, determining by the discovery client whether the device service of the announcement message matches the cache data, and if so, determining whether the device service has lost operational state based on the stateless boot time parameter of the announcement message and the cache data.

40. A computer-readable media having a software program thereon executable on a networked computing device acting as a discovery responder in an ad-hoc networking environment according to an ad-hoc discovery protocol to effect a method comprising:

maintaining cache data of discovered device services in a discovery client;

receiving the announcement message from the discovery responder by a discovery client;

determining by the discovery client whether the device service of the announcement message matches the cache data; and

if so, determining whether the device service has lost operational state based on the stateless boot time parameter of the announcement message and the cache data.

41. A method of discovering device services in an ad-hoc networking environment of computing devices acting as discovery clients and discovery responders, the method comprising:

upon a discovery responder joining a network, sending an announcement message of a device service on the discovery responder by the discovery responder as a multicast transmission, wherein the announcement message contains an end point identifier indicative of an identity of the discovery responder and a configuration number parameter indicative of a configuration of the discovery responder;

upon a change in configuration of the discovery responder,

generating a new value of the configuration number parameter by the discovery responder; and

sending a further announcement message of the device service by the discovery responder as a multicast message, wherein the further announcement message contains the end point identifier and the configuration number parameter having the new value.

42. The method of claim 41 further comprising:

maintaining cache data of discovered device services by a discovery node;

receiving by the discovery node an announcement message;

determining whether a configuration of any discovered device service represented in the cache data has changed based on the cache data for that discovered device service matching the endpoint identifier contained in the announcement message but not the configuration number parameter contained in the announcement message; and

if so, retrieving an updated device service description for that discovered device service from the discovery responder, and updating the cache data based on the retrieved device service description.

43. The method of claim 42 wherein the discovery node is one of a discovery client or a discovery server.

44. A method of discovering device services in an ad-hoc networking environment of computing devices acting as discovery clients and discovery responders, wherein discovery responders send a multicast announcement message containing an endpoint identifier and configuration number, the method comprising:

maintaining cache data of discovered device services by a discovery node;

receiving by the discovery node an announcement message;

determining whether a configuration of any discovered device service represented in the cache data has changed based on the cache data for that discovered device service matching the endpoint identifier contained in the announcement message but not the configuration number parameter contained in the announcement message; and

if so, retrieving an updated device service description for that discovered device service from the discovery responder, and updating the cache data based on the retrieved device service description.

45. A distributed system of networked computing devices compliant with an ad-hoc service discovery protocol, the distributed system comprising:

at least one networked computing device operating as a discovery responder according to a network architecture of the ad-hoc service discovery protocol, the discovery responder generating a new configuration number upon a change in its configuration and sending an announcement message containing an endpoint identifier and the new configuration number as a multicast transmission; and

at least one networked computing device operating as a discovery node according to the network architecture of the ad-hoc service discovery protocol, the discovery node having a cache of discovered device service descriptions, and operating upon receiving the announcement message to determine whether a device service represented in a discovered device service description in the cache matching the endpoint identifier of the announcement message has changed configuration based on the configuration number of the announcement message.

46. A computer-readable media having a software program thereon executable on a networked computing device acting as a discovery responder in an ad-hoc networking environment according to an ad-hoc discovery protocol to effect a method comprising:

upon a discovery responder joining a network, sending an announcement message of a device service on the discovery responder by the discovery responder as a multicast transmission, wherein the announcement message contains an end point identifier indicative of an identity of the discovery responder and a configuration number parameter indicative of a configuration of the discovery responder;

upon a change in configuration of the discovery responder,

generating a new value of the configuration number parameter by the discovery responder; and

sending a further announcement message of the device service by the discovery responder as a multicast message, wherein the further announcement message contains the end point identifier and the configuration number parameter having the new value.

47. A computer-readable media having a software program thereon executable on a networked computing device to effect a method, the networked computing device acting as a discovery node in an ad-hoc networking environment according to an ad-hoc discovery protocol wherein discovery responders send a multicast announcement message containing an endpoint identifier and configuration number, the method comprising:

maintaining cache data of discovered device services by a discovery node;

receiving by the discovery node an announcement message;

determining whether a configuration of any discovered device service represented in the cache data has changed based on the cache data for that discovered device service matching the endpoint identifier contained in the announcement message but not the configuration number parameter contained in the announcement message; and

if so, retrieving an updated device service description for that discovered device service from the discovery responder, and updating the cache data based on the retrieved device service description.

48. A method of discovering paged numbers of device services in a networking environment of computing devices, the method comprising:

sending a discovery query by a discovery client to a discovery server on a network to find device services matching certain find criteria, the discovery query specifying a size limit parameter and passing a page context parameter;

returning by the discovery server a response to the discovery query for a number of device services matching the find criteria up to the size limit parameter and returning the page context parameter, the page context parameter being set to identify a context state of the discovery server'"'"'s response to the discovery query; and

repeating the steps of sending the discovery query and returning the response, wherein the further responses by the discovery server return further incremental sets of devices services matching the find criteria up to the size limit parameter specified in the discovery client'"'"'s preceding discovery query.

49. The method of claim 48 wherein the discovery queries sent by the discovery client in different iterations specify different values of the size limit parameter.

50. The method of claim 48 further comprising returning an empty page context parameter by the discovery server in a response to an iteration of the discovery query to indicate an absence of further device services matching the find criteria.

51. The method of claim 48 further comprising specifying by the discovery client a zero-valued size limit parameter in a final iteration of sending the discovery request to indicate no further query iterations are forthcoming from the discovery client.

54. The computer-readable media of claim 48 wherein the method further comprises returning an empty page context parameter in a response to an iteration of the discovery query to indicate an absence of further device services matching the find criteria.

52. A distributed system of networked computing devices compliant with an ad-hoc service discovery protocol, the distributed system comprising:

at least one networked computing device operating as a discovery client according to a network architecture of the ad-hoc service discovery protocol, the discovery client sending a discovery query to a discovery server on a network to find device services matching certain find criteria, the discovery query specifying a size limit parameter and passing a page context parameter;

a networked computing device operating as the discovery server according to the network architecture of the ad-hoc service discovery protocol, the discovery server returning a response to the discovery query for a number of device services matching the find criteria up to the size limit parameter and returning the page context parameter, the page context parameter being set to identify a context state of the discovery server'"'"'s response to the discovery query; and

wherein the discovery client and discovery server repeat the steps of sending the discovery query and returning the response, and the discovery server returns further incremental sets of devices services matching the find criteria up to the size limit parameter specified in the discovery client'"'"'s preceding discovery query in the further responses.

53. A computer-readable media having a software program thereon executable on a networked computing device to effect a method, the networked computing device acting as a discovery server in a networking environment according to a discovery protocol wherein discovery clients send successive iterations of a discovery query to find device services matching certain find criteria and specifying a size limit parameter and passing a page context parameter, the method comprising:

returning a response to the discovery query for a number of device services matching the find criteria up to the size limit parameter and returning the page context parameter set to identify a context state of the discovery server'"'"'s response to the discovery query; and

in response to further iterations of the discovery query, returning further responses to the discovery query for further incremental sets of devices services matching the find criteria up to the size limit parameter specified in the iteration of the discovery query.

55. A computer-readable media having a software program thereon executable on a networked computing device acting as a discovery client in a networking environment according to a discovery protocol to effect a method comprising iteratively sending a discovery query by a discovery client to a discovery server on a network to find device services matching certain find criteria, the discovery query specifying a size limit parameter and passing a page context parameter to control a number of matching device services returned by the discovery server in response to the discovery query.