SDS Distributed Lookup software package (SDS-DL)
aka, Wide-Area Querying in the Ninja Service Discovery Service (WASDS)

Introduction

SDS-DL is code that is available as part of the Ninja CVS tree.

This package supports data indexing and filtered query routing for distributed free-form XML fragments. It is composed of three basic "entities:"

• WAServers: the main player, a server that sends/receives queries, updates, topology management messages, etc.
• Queriers: entities that generate query traffic to a server
• SrvAnnouncers: entities that announce the XML "Service Descriptions" (SDs) that populate WAServers; queries resolve based on these SDs.

• basic single-node server process, communicating via network messages
• single-node simulation, where all entities communicate via method calls inside the JVM
  and
  
• multi-node (distributed) simulation, where groups of nodes in a single JVM communicate via method calls, but where these single clumps of entities are bridged by having one (or more) servers in the clump communicate across the network to other sever(s).

• Bloom: the Bloom-filter based scheme of the Ninja SDS.
• Centroid: the LDAP/WHOIS++ Common Indexing Protocol (CIP) Centroid scheme of the draft-ietf-find-cip-XX.txt.
• Broker: the brokering approach that is philosophically similar to the mesh-enhanced SLP work (mSLP) and the SLPv2 wide-area extension proposal (WASRV).

The indexing approach assumes that an "index" is an entity that trys to answer the question "if I send my query to the server you are the index of, will it help me resolve the query?". (Thus, the call SrvIdx.mayContain(blah) is used rather than something like SrvIdx.contains(blah)). This, in other words, means that false positives are potentially allowed. Similarly, false negatives can also be allowed. Note, though, that the consequences of allowing false positives and/or negatives are quite different: occurrences of false positives only change the performance and overhead of the system, not the "correctness." Contrawise, allowing false negative must be an application-level choice because the application has to know contradictory results may occur and deal with any resulting confusion. (i.e., the app "knows" it should find an X because it put it in there, but somehow it isn't finding it -- leading to a failed assertion or the like.)

This fundamental index scheme design choice is illustrated in the implemented indices: the BloomIndex and CentroidIndex potentially give false positives, but never give false negatives. The BrokerIndex never gives a false positive, but may (and often must) give false negatives.

Running it

The main starting places are the WAServer and DistSim classes under the ninja.hodes.wasds package in the Ninja CVS tree. Each of these can be run from the command line (i.e., has a main()). Usage is as follows:

• WAServer

  java ninja.hodes.wasds.WAServer
         [-d (on|off)]         debug?
         [-i (Null|Bloom|Centroid|Broker)] index type
         [-fwd (full|pbf)]     forwarding style
             {-test | -cfgfile filename | -cfgURL URL}
  

• DistSim

  java ninja.hodes.wasds.DistSim
         [-d (on|off)]         debug?
         [-log (on|off)]       dump event stream?
         [-dumpstate (on|off)] dump state at end? 
         [-i (Null|Bloom|Centroid|Broker)] index type
         [-fwd (full|pbf)]     forwarding style
         [-srvdesdir (dir)]    dir of XML files
         [-srvdesranges (# # ...)]  tags for workload
             -f {distsim-config-file}
  
  

Index type and forwarding style are described above. The configuration files are specified as follows: (where a speclist is a list of ports or address/port pairs (i.e., 6655 or 224.5.4.3/2222) separated by commas.)

• WAServer

  wasds.query-listeners:     speclist
  wasds.srvann-listeners:    speclist
  wasds.neighbor-listeners:  speclist
  

• DistSim

  The DistSim configuration file is composed of commands along the lines of a scripting language. Comments are preceded by a hashmark (like shell scripts). The commands either specify the instantiation of particular entities in the system...

  WAServer <name> 
  Querier  <name> -n  <number of queries>  
                  -srvr <name of who to query>
               [{ -srvdesranges <list of integer ranges> 
                | -srvdesdir <directory of XML files>}]
  SrvAnn   <name> -n  <number of srvanns>  
                  -srvr <who to announce to> 
               [{ -srvdesranges <list of integer ranges> 
                | -srvdesdir <directory of XML files>}]
  

  ... or string existing entities together:

  Neighbors <child name>  ->  <parent name> -h  <hierarchy name>
  

  ... or configure an entity:

  ConfigServerFromFile <name of server> <config file name>
  ConfigServerFromURL  <name of server> <config URL>
  

Here is an example DistSim config file. Assuming you have a valid wasds.config file, this would setup a tree with a querier at one leaf an announcer at the another leaf, and a middle server that listens for connections to another server node (presumable a server that is connected in another chuck of simulated topology on another machine.)

WAServer s1
WAServer s2
WAServer s3
WAServer s4
#SrvAnn sa1 -n 30 -srvr s1 -srvdesranges 10 50
#Querier q1 -n 20 -srvr s4 -srvdesranges 10 50
SrvAnn sa1 -n 10 -srvr s1 -srvdesdir /home/hodes/freedb/jazz-a0-xml
Querier q1 -n 20 -srvr s4 -srvdesdir /home/hodes/freedb/jazz-a0-xml
Neighbors s1 -> s2 -h TOPO
Neighbors s2 -> s3 -h TOPO
Neighbors s4 -> s3 -h TOPO
ConfigServerFromFile s2 wasds.config
#ConfigServerFromURL s2 http://toddhodes.org/wiq/srvr1

A few more fun things to play with

In addition to the wasds package, there are some networking utilities in ninja.hodes.net that might be of interest.

Todd Hodes, mylastname @ myfullname dot org

Last modified 25 August 2000