Service discovery

The service discovery and publish/subscribe data service remove the need for fixed network topologies since each node dynamically tracks system capabilities and uses the reconfigurable meshed networking to maintain data delivery even when individual links change.

To define services, a description language was needed. Most of the existing languages require XML, have too extensive of a library, or do not allow for the proper definition of robot-based services. The entire service discovery protocol is based on "Interface" objects registering their capabilites with the "Data Distribution" object. To read more about this process refer to "application layer networking."

Capabilities Message Structure

Once each capability has been registered, it is then defined using unique ids. Each subsystem was given a 4 bit id. For instance, the GPS subsystem was given 0x40. To further define the capability, hex values were then assigned to available streams or accepted commands. Available streams and accepted commands are defined by two 8 bit bit fields that identify the presence of one or many per subsystem. This 12 bit representation of a capability provides enough flexibility to define all of the current subsystems along with room to define others. Furthermore, by using this unique system, the internal packets can be identified by simply combining the 4 bit hex value of the system in the high nibble with the 4 bit value of the stream or command in the low nibble to get the header. An example of these defines are given below:

/*-----------	autopilot	----------*/
#define	CMD_AUTOPILOT	0x80
#define	CMD_WAYPOINT	0x81
#define	CMD_FLIGHTPLAN	0x83
#define	STREAM_TELEMETRY	0x84

To send these available streams and accepted commands to the rest of the system, a capabilities packet is composed. The structure of the capabilities packet was kept very simple to limit bandwidth and allow for implementation on the resource constrained participants. The packet is composed of an address field and a systems field. The address corresponds to a 32 byte human readable "address" for the node. This is done to allow for the unique identification of a node that might have multiple IP addresses, or other types of addresses depending on the connected networks. The systems field is simply a list of the unique capability ids.

Example

Below is an example of a client outside the internal network using an XML interface to request a stream subscription after receiving a capabilities packet through a gateway node.

Appendix -- Notes on Other Protocols

This is by no means complete, and was formulated after only a cursory study. It is provided here as a rough guide. Feel free to contact me if you feel I have misrepresented any of these.

DEAPspace

DEAPspace was created specifically for use in mobile ad hoc networks. Each node maintains a copy of its own "world view" which consists of the known services and a time to live for each service. This "world view" is broadcast at a given frequency. If a "world view" is received, the local list of services' TTL are updated from the packet and a random amount of time is added until the node's next transmission. This amount of time is small if the service TTL for a node's own services is less than the typical backoff time, or if it notices that any of its services are missing from the "world view." In this manner, nodes that need to update the "world view" information are given priority. This approach also allows for less use of bandwidth because only one node is transmitting during each interval.

UPnP

UPnP is based loosely upon the traditional hardware PnP protocol, and uses SSDP for service discovery. UPnP uses various high level services, such as HTTP and SOAP, and was designed mainly to run upon devices that aren't typically very resource constrained. UPnP also contains AutoIP in its specification to allow devices joining the IP based network to obtain an IP automatically, even in the absence of a DHCP server

Network members are either devices or control points. When devices join a network, they advertise their services to control points. When control points join a network, they request service advertisement from the various devices. To learn more about a device's capabilities, the control point can retrieve the device's information in the form of an XML file from an HTTP server running on the device. Once the control point has determined the capabilities of a device, it can send control messages to the device using SOAP.

Konark

Konark is designed specifically for use in a multi-hop ad hoc network, and uses an XML service description language similar to WSDL. Each node contains a service registry where it stores its own and other nodes services in a tree like directory structure. Access to the services are provided through a light weight HTTP server.

PDP

PDP is designed for ad hoc networks with resource limited nodes. Messages from the constrained nodes have higher priority, forcing them to rebroadcast as little as possible. All devices maintain a cache of known nodes and services, and perform a coordinated broadcast when a service is requested.

Salutation

Salutation is designed for highly heterogeneous networks. The two main parts of Salutation are the "Transport Mangers" and the "Salutation Manager." The "Salutation Manager' maintains a central directory of all services and has methods for registration and query. The "Transport Managers" exist on every node and provide abstraction from the local transport method(s) to the Salutation API. In this manner nodes using many different communications protocols can participate in the service discovery architecture. For nodes unable to run the full Salutation stack, a light version of the protocol is available.

Jini

Jini was created to convert a loosely collected group of Java based software components into a distributed system. A service provider finds a service registry by multicasting a message to the network when it joins. Upon finding a registry, the provider registers its services as service objects, along with some attributes of the service and methods that can be invoked. Once a client desires to use a certain service it may look it up in the registry by using either a Java type or some of the service attributes. Once the desired service is located, the service object is copied to the client and allows for the client to work directly with the service provider.

SLP

The Service Location Protocol (SLP) is designed for service discovery within an enterprise. It allows for services to be limited to a certain segment of the network so as to be able to define such notions as the services available within a particular room. The SLP is conducted by three different agents, User Agents (UA), Service Agents (SA), and Directory Agents (DA). When a DA is present in the network, all services represented by an SA are unicast to the DA. When a UA desires to use a service, it can request information from the DA. When there is not a DA present, the UAs continually multicast requests for services and if present, the respective SAs respond to the request.

Sailhan2005

Sailhan2005 is designed for very large ad hoc networks. Nodes are dynamically elected as directories, and have requirements so that they maintain have a certain coverage of the network along with limiting the number of hops from a device to a directory. The directory caches local services along with a summary of the services available to other known directories. When a local client wishes to use a service, it makes a request to the directory. If the directory does not have an entry for the service, it intelligently multicasts the requests to other directories using the information contained in the summaries. Sailhan2005 also provides for nodes to bridge networks, and thus act as gateways through which service requests and responses may pass.

DSDP

DSDP relies on a set of relatively static nodes to form a backbone for the distributed network. This backbone is set up using a one hop beacon message during a backbone management phase. This phase is repeated at a necessary frequency to maintain the integrity of the backbone. Once the backbone is set up, the clients can register services to the directories contained in the backbone nodes, and make requests which travel along the backbone until a match is found, or all directories have been queried.

VIA

VIA was designed for use in infrastructure based networks. Several nodes are defined as directories in particular domain, and contain a portion of the available services along with links to the other directories. These nodes form a "data cluster." The master directory for a domain has connections with the domain, and also with a "main channel" which connects the domains to each other. The master directory can use multicasting to interact with the other domains to request services not available in their particular domain.

Superstring

Superstring was created to handle networks with highly dynamic services. It is assumed the that underlying architecture possesses a central core that has significant bandwidth and computing power. The directory is created by defining a top level of nodes that possess some service and distributing the directory across them. A hierarchy is then established for further defining services in a tree structure.

GSD

The Group-based Service Discovery protocol (GSD) uses the DARPA Agent Markup Language (DAML) to describe services and define service-based groups. This protocol is very similar to ALLIA as it forms groups and broadcasts services periodically to a certain radius. Service requests are made by intelligently forwarding based upon a concise table of known services outside each group. This table is known as the "Other Groups Field." Service requests are replied to using the reverse of the route taken by the request.

ALLIA

ALLIA is designed to be used on groups of heterogeneous nodes linked by an Ad hoc network. A local policy manager makes various decisions about whether or not to cache available services, and whether to forward service announcements and service requests. By allowing the policy manager to differ between nodes, resource constrained nodes can behave so as to conserve resources.

Messages in ALLIA are limited by having the nodes form "alliances" where their services are only shared to the members of the alliance. Since the alliances are defined by the number of communications hops, changing this parameter will have a direct effect on network overhead for service discovery. Furthermore, in highly mobile networks, it will be desirable to limit the alliance radius as nodes several hops away will be leaving and entering the alliance at a high frequency. The other parameter that can be set is the frequency of the service advertisements. This number also affects the network overhead, and furthermore can be increased to accommodate highly mobile networks.

Besides service announcements, each node sends out a periodic message that serves as a heartbeat. This effectively reduces the overhead of having to always broadcast services, as the services only need to be multicast whenever the alliance topology changes.

Service requests are handled by a forwarding manager, and will either be multicast to alliance members, or dropped.

Twine

Twine is paired with the Intentional Naming System (INS) developed by MIT. Twine stores service attributes by hashing them and placing them in mesh structure directories. In this manner it allows for a scalable system that can handle a directory containing services on the order of millions. INS provides for pairing between service entries and service location.

Pastry

Pastry is paired with a ring based P2P network that relies heavily on infrastructure provided by the collective network. Services are described in a "service certificate" which is signed by using the node's public key. The "service certificate" is then stored in the persistent storage for the ring using the hash of the certificate as the index. If any node wishes to locate the service, it performs a keyword search which returns matching keys. The keys can then be used to retrieve the certificates and then locate the corresponding nodes. Furthermore, a persistent query may be made of the centralized storage that allows for a node to be notified if a particular service becomes available.