SONAR, a Network Proximity Service

One way to make a network-accessible resource available to a world-wide audience is to provide several copies (or mirrors) of that resource at multiple locations. If a user knows of several locations from which a resource can be accessed, she will obtain better service if she chooses a location which is near to her, than if she chooses one which is distant - provided she has a sufficient knowledge of network topology to inform such a choice. The advantage of choosing a nearby location is illustrated in Figure 3.

Figure 3:

The SONAR service is designed to allow such a choice to be made by an application program. Given several alternative locations from which to access a resource, an application program can query a nearby SONAR server to determine which locations are closer than others. The SONAR server will return, for several of those locations, a metric which provides a rough indication of the proximity of that location to the SONAR server. Using those metrics, the application can then choose a single location from those returned from which to access the resource.

SONAR does not attempt to find the ``best'' location of a resource, nor does it attempt to accurately measure proximity, either in terms of round-trip-time, hop count, or bandwidth. Instead, the goal of SONAR is to provide a ``good'' choice without a long delay or consuming significant network resources in making that choice.

If the time required to access a resource using SONAR is usually less than the time required to access the resource without it, or if the use of SONAR avoids the ``worst case'' selection, users will see SONAR as beneficial. Likewise, if the amount of network resources consumed by a SONAR server in measuring network proximity is less than the amount of resources that would be consumed when accessing a randomly chosen location, SONAR will improve the utilization of the network.

Rather than building SONAR into dozens of applications, it is designed as a separate service, accessible using a well-defined protocol. Implementations of SONAR can thus evolve independently of the applications which use it, and a particular SONAR server may be adjusted to suit the needs of the site which it serves.

The SONAR Protocol

SONAR is implemented using UDP. A SONAR query and response each consist of a single UDP data- gram. In the descriptions below, all numeric quantities are in standard network byte order (``big-endian'' format, most significant byte transmitted first).

The format of a SONAR query is as follows:

        offset              datum
          0        | protocol-version = 0 |
          4        |   request-type = 0   |
          8        |      request-id      |
          12       |     timeout.secs     |
          16       |    timeout.usecs     |
          20       |        count         |
          24       |      address[0]      |
          28       |      address[1]      |
                   |         ...          |
    24+(count-1)*4 |   address[count-1]   |
The protocol-version is used to distinguish this version of the SONAR protocol from other versions. This document describes version 0 of the protocol. A SONAR server MUST check the version-number of each request and return a VERSION_MISMATCH response if that version is not supported.

For SONAR version 0, the only valid request-type is 0, corresponding to a request for proximity information for one or more IP addresses. Future versions of SONAR will allow multiple requests.

The request-id is any 4 bytes chosen by the client, and used to associate a response with the particular request that produced. The request-id will be included in the SONAR server's response.

The timeout is the maximum number of seconds (4 bytes) and microseconds (4 bytes) which the SONAR server should wait before replying The server MAY return a response sooner than requested. A timeout of zero seconds and zero microseconds requests that the SONAR server return a response immediately, based on whatever proximity data it has at hand.

The count (4 bytes) is the number of addresses for which the SONAR client wants the server to determine relative proximity. The count may be any value between 1 and 185, inclusive. SONAR servers MUST ignore queries with a count of zero, and SHOULD ignore the 186th and later addresses in a query that contains more than 185 addresses.

Following the count are that many Internet Protocol (v4) addresses.

Version 0 of the SONAR service has two possible response formats. A SUCCESS response returned by the SONAR server is in the following format:

        offset                 datum
          0        |    protocol-version = 0    |
          4        | response-type = 0x80000000 |
          8        |         request-id         |
          12       |           count            |
          16       |     result-address[0]      |
          20       |         metric[0]          |
          24       |     result-address[1]      |
          28       |         metric[1]          |
                   |            ...             |
    16+(count-1)*8 |  result-address[count-1]   |
    20+(count-1)*8 |      metric[count-1]       |
Protocol-version will also be zero. For all versions of SONAR, the protocol-version of the response will match that of the request.

(All response-types have their most significant bit set to 1, so that responses can be distinguished from queries.) For a SUCCESS response, response-type will be 0x80000000.

The request-id matches the one from the SONAR query.

The count is the number of IP addresses for which proximity data is being returned. The SONAR server MAY return fewer responses than the number of IP addresses for which proximity information was requested.

Following the count are several (address, metric) pairs. Each address is an IP address which appeared in the a query, and the metric is an unsigned 4 byte integer which indicates relative proximity of that host to the SONAR server. The addresses returned in a SONAR response are not in any particular order; the client must sort them if needed. The metrics are not necessarily in any particular units, and should be used only for comparison of locations returned within a single response.

Finding a SONAR Server

SONAR complicates configuration of networked applications, because they need to know the address of one or more SONAR servers to use it. It is therefore desirable to minimize the burden of configuration.

SONAR-aware applications should perform a DNS query of QTYPE=A on the name "sonar-server" to determine if there are any SONAR servers defined for use by the local domain. (This assumes that DNS searches for unqualified names take place relative to the local domain.) Even though the local DNS hierarchy does not necessarily correspond to network topology, this approach will work well for many sites.

Even if a "sonar-server" host is defined in DNS, it is desirable to allow the server to be overriden on a per-host, per-user, or per-process basis. For instance, on UNIX, a /etc/sonar-server file could contain names of SONAR servers to be used by that host in preference to those defined by DNS. These could be overriden for a user by defining a $HOME/.sonar-server file, or on a per-process basis by defining a SONAR_SERVER environment variable. Similar techniques could be used by other operating systems.

A future version of SONAR may support finding servers using broadcast.

Implementation Details

This section describes the initial implementation of SONAR simply as an example. Other implementations may use different proximity metrics, different methods for obtaining proximity data, and different algorithms for filtering that data.

Our initial implementation of SONAR sends ICMP echo requests to each of the addresses for which a proximity measure is desired, and uses the time between when the request is sent, and when an ICMP echo reply is received, as its metric for evaluating relative proximity. Round-trip-time estimates obtained using ICMP are cached for a certain amount of time (currently several hours) so that subsequent SONAR queries within that time do not result in generation of additional ICMP requests. Any ICMP "unreachable" replies are also noted, though these are cached for a smaller amount of time.

The implementation is straightforward: incoming queries are placed on a priority queue which is ordered by timeout value. (A maximum timeout value is imposed so that requests do not stay in the queue forever.) Proximity information about IP addresses is maintained in a hash table which includes the IP address, proximity metric, the time at which the metric was obtained, and a list of all queries which are waiting on proximity information for that address. A response is generated either when proximity data is available for each of the hosts in a query, or when a query times out.

ICMP requests are currently sent to all addresses in a query for which there is not recent proximity data, and for which no ICMP echo requests have recently been sent. A SONAR query with a very small timeout may still result in ICMP requests being sent to several of the addresses in that query (even though they could not possibly respond in time), and the proximity metrics thus obtained will be available on subsequent SONAR queries.

The server ignores queries sent to any IP broadcast address, and ignores requests to obtain proximity information for any IP broadcast address. The server can also be configured to ignore packets not originating from certain sets of addresses.

We plan to experiment with several strategies to reduce the network load imposed by SONAR. Possible strategies include: use of IP TTL field to limit the radius to which ICMP packets are sent, limiting the number of addresses which are probed as the result of any single query, and using round-trip-time estimates from open TCP connections.