draft-ietf-wnils-whois-mesh-00.txt

paf@nada.kth.se Mon, 25 July 1994 02:27 UTC

Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa11153; 24 Jul 94 22:27 EDT
Received: from CNRI.RESTON.VA.US by IETF.CNRI.Reston.VA.US id aa11142; 24 Jul 94 22:27 EDT
Received: from ucdavis.ucdavis.edu by CNRI.Reston.VA.US id aa14378; 24 Jul 94 22:27 EDT
Received: by ucdavis.ucdavis.edu (8.6.9/UCD2.50) id TAA06283; Sun, 24 Jul 1994 19:20:48 -0700
X-Orig-Sender: ietf-wnils-request@ucdavis.edu
Received: from staff.nada.kth.se by ucdavis.ucdavis.edu (8.6.9/UCD2.50) id TAA06255; Sun, 24 Jul 1994 19:20:42 -0700
Sender: ietf-archive-request@IETF.CNRI.Reston.VA.US
From: paf@nada.kth.se
Received: by staff.nada.kth.se (5.61-bind 1.4+ida/nada-mx-1.0) id AA15337; Mon, 25 Jul 94 04:20:38 +0200
Date: Mon, 25 Jul 94 04:20:38 +0200
Message-Id: <9407250220.AA15337@staff.nada.kth.se>
To: ietf-wnils@ucdavis.edu
Subject: draft-ietf-wnils-whois-mesh-00.txt

White Pages Requirements Working Group                    P. Faltstrom
draft-ietf-wnils-whois-mesh-00.txt                            NADA/KTH
Expires: 18 January 1995                                   R. Schoultz
                                                                KTHNOC
                                                             C. Weider
                                       BUNYIP INFORMATION SYSTEMS, inc
                                                          24 July 1994

                  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 itself...

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 := { configured server(s) for this template };
      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;

Authors Addresses

   Patrik Faltstrom
   NADA/KTH
   S-100 44  STOCKHOLM
   SWEDEN
   <paf@nada.kth.se>

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

   Chris Weider
   BUNYIP INFORMATION SYSTEMS, inc
   2001 S. Huron Parkway, #12
   Ann Arbor, MI 48104
   USA
   <clw@bunyip.com>

References

[Deutsch94]       Deutsch P., Schoultz R., Faltstrom P., Weider C.,
                  Architecture of the Whois++ service, July 1994.
                  < URL:ftp://ds.internic.net/internet-drafts/
                  draft-ietf-wnils-whois-arch-01.txt>

[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 >