How to Interact with a Whois++ Mesh
draft-ietf-wnils-whois-mesh-02

White Pages Requirements Working Group                    P. Faltstrom
draft-ietf-wnils-whois-mesh-02.txt     BUNYIP INFORMATION SYSTEMS, inc
Expires: 12 April 1996                                     R. Schoultz
                                                                KTHNOC
                                                             C. Weider
                                       BUNYIP INFORMATION SYSTEMS, inc
                                                       20 October 1995

                  How to interact with a Whois++ mesh

Status of this Memo

This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), it areas, and
its working groups. Note that other groups may also distribute working
documents as Internet-Drafts.

Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time.  It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress".

To learn the current status of any Internet-Draft, please check the
"1id-abstracts.txt" listing contained in the Internet- Drafts Shadow
Directories on ds.internic.net (US East Coast), nic.nordu.net
(Europe), ftp.isi.edu (US West Coast), or munnari.oz.au (Pacific Rim).

Overview

In the Whois++ architecture [Deutsch94],[Weider94], mesh traversal is
done by the client, since each server 'refers' the client to the next
appropriate server(s). The protocol is simple. The client opens a
connection to a  server, sends a query, receives a reply, closes the
connection, and after parsing the  response the client decides which
server to contact next, if necessary.

So, the client needs to have an algorithm to follow when it interacts
with the Whois++ mesh so that referral loops can be detected, cost is
minimised, and appropriate servers are rapidly and effectively
contacted.

Basic functionality

Each Whois++ client should be configured to automatically send queries
to a specific Whois++ server. The deault Whois++ server can vary
depending on which template is desired, and the location of the client
with respect to the WHOIS++ index mesh,  but as a rule the server
should be as local as possible.

                        A
                       / \
                      B   C
                     / \   \
           Z -----> D   E   F
                   / \
                  G   H

      Fig 1: The client Z is configured to first query server D

After getting responses from a server, the client can act in several
ways. If the number of hits is greater than zero, the response is just
presented to the user. If the client gets one or many servers-to-ask
answers, the client should be able to automatically resolve these
pointers, i.e. query these servers in turn.

                        A
                       / \
                      B   C
                     / \   \
           Z <----- D   E   F
             \     / \
              --> G   H

      Fig 2: The client Z gets a "servers-to-ask G" response from D
             and therefore may automatically queries server G.

Expansion of searches

If the number of hits is zero, or if the user in some way wants to
expand the search, it is recommended for the client to issue a
'polled-by' and 'polled-for' query to the server. The client can then
repeat the original query to the new servers indicated.

                        A
                       / \
              /-----> B   C
             /       / \   \
           Z <----- D   E   F
                   / \
                  G   H

      Fig 3: The client Z gets a "polled-by B" response from D
             and therefore queries server B.

The client must always keep track of which servers it has queried
because it must itself detect loops in the mesh by not querying the
same server more than once.

                        A
                       / \
                   /- B   C
                  /  / \   \
           Z <---/  D   E   F
                   / \
                  G   H

      Fig 4: The client Z gets a "servers-to-ask D" response from B
             but Z does not query D because the server D has already
             been queried.

So, the default expansion of a query by a client causes increasingly
more comprenhensive index servers to be queried; the forward knowledge
contained in the index server mesh allows rapid pruning of these
larger trees.

All loop detection and elimination is done in the client, rather than
in the server mesh. This decision was made because loop detection and
elimination are quite difficult to build into the mesh if we are to
continue to allow each server to participate in multiple hierarchies
within the mesh.

Optimising the mesh

If organization A tends to use organization B's WHOIS++ server
frequently, for example if A is cooperating in a project with B, A may
wish to make B's server locally available by creating a local index
server which retrieves the centroid for both organizations. When A's
client then expands a query which is looking for someone at B, the
client can much more rapidly resolve the query, as it does not have to
find the top level servers for the tree to which A and B both belong.

                        A
                       / \
                      B   C
                     / \   \
           Z        D   --> F
                   / \
                  G   H

      Fig 5: The server B gets a centroid from server F

                        A
                       / \
                      B   C
                     / \   \
           Z <----> D   --- F
                   / \
                  G   H

      Fig 6: The client queries server D, gets zero hits back, expands
             the search and gets a "polled-by B" response back.

                        A
                       / \
                 /--> B   C
                /    / \   \
           Z <-/    D   --- F
                   / \
                  G   H

      Fig 7: The client Z queries server B and gets "servers-to-ask F"
             response back.

                        A
                       / \
                      B   C
                     / \   \
                    D   --- F <-----> Z
                   / \
                  G   H

      Fig 8: The client Z queries server F and gets the answer.

The example given in Fig 5-8 shows that the algorithm works even
though the Whois++ mesh is not a tree. There are many reasons why a
given index server mesh might be 'short-circuited'. For example, in
the case of a multinational company, the Swedish branch of Acme Inc.,
is polled both by the national server in Sweden and the headquarters
server in the USA. By querying the Swedish server, one finds all
persons working at the Swedish branch of Acme Inc., but by querying
the Acme Inc. server in the USA, you will find all employees in the
company, including those in Sweden.

Note that the location of a server does not implicitly narrow the
search, i.e. you have to specify all information when sending a query
to a server. In the example above, one can see that by just querying a
server for companies in the USA, you will not implicitly only get hits
from records in the states, because the Acme Inc. server in the states
has polled a server in Sweden. So, in this case you have to explicitly
include "country=USA" in the query if you are only interested in those
records.

Although the WHOIS++ index service has been designed to make searches
at any location in the index mesh quite effective and efficient,
blindly expanding the query can incur an exponentially growing cost in
resources, and, as charging for responses is implemented in parts of
the WHOIS++ index service mesh, growing cost, automatic expansion is
not recommended. More sophisticated clients  should also be
configurable to "cut off" some servers from a search, i.e. a blacklist
of servers. This might be needed when searching for records and one
server might have a very high cost (in dollars) so one might want to
explicitly forbid the client to send queries to that server.

The algorithm used by the server

By following this algorithm a client finds all records in a mesh which
the first Whois++ server queried belongs to.

The algorithm for the client follows:

      Query := data to search for;
      QueriedServers := {};
      AnswerList := {};
      OriginalServers := { known servers to this client };
      while OriginalServers is not empty do:
            ServerList = OriginalServers;
            while ServerList is not empty do:
                  Server := ServerList[1];
                  if Server is not in QueriedServers then do:
                        send Query to Server;
                        Answer := answer from Server;
                        append ServersToAsk to ServerList;
                        remove Server from ServerList;
                        append Answers to AnswerList;
                  end;
            done;
            if query should be expanded then do:
                  ServerList := OriginalServers;
                  OriginalServers := {};
                  while ServerList is not empty do:
                        Server := ServerList[1];
                        send Polled-For-Query to Server;
                        Answer := answer from Server;
                        append Answer to OriginalServers;
                        remove Server from ServerList;
                  end;
            done;
      done;
      display AnswerList to user;

The Directory of Servers

A second way of finding the correct server to query is to use a
separate service we call the Directory of Servers.

Authors Addresses

   Patrik Faltstrom
   BUNYIP INFORMATION SYSTEMS, inc
   Suite 300
   310 Ste Catherine Street West
   Montreal, Quebec
   CANADA H2X 2A1
   <paf@bunyip.com>

   Rickard Schoultz
   KTHNOC, SUNET/NORDUnet/Ebone Operations Centre
   S-100 44  STOCKHOLM
   SWEDEN
   <schoultz@sunet.se>

   Chris Weider
   BUNYIP INFORMATION SYSTEMS, inc
   Suite 300
   310 Ste Catherine Street West
   Montreal, Quebec
   CANADA H2X 2A1
   <clw@bunyip.com>

References

[Deutsch94]       Deutsch P., Schoultz R., Faltstrom P., Weider C.,
                  Architecture of the Whois++ service, August 1995.
                  RFC 1835

[Weider94]        Weider C., Fullton J., Spero S., Architecture of the
                  WHOIS++ Index Service: Internet Draft, July 1994.
                  < URL:ftp://ds.internic.net/internet-drafts/
                  draft-ietf-wnils-whois-03.txt >