Service Discovery
Todd Hodes 
22 June 1998

Papers:

M. van Steen, F.J. Hauck, P. Homburg, and A.S. Tanenbaum. 
  "Locating Objects in Wide-Area Systems." 
   http://www/~hodes/papers/globe.ps   (12pp)

IETF SrvLoc group (Perkins, et al), 
  "Service Location Protocol (SLP) white paper,"
   http://playground.sun.com/srvloc/slp_white_paper.html  

Rosenberg, Schulzrinne, 
  "Internet Telephony Gateway Location,"   [one version of a wide-area SLP]
   http://www/~hodes/papers/infocom_gwloc_camera.ps  (9pp)


---------------

I couched the discussion as ten questions followed by a list of
"interesting axes" for investigation of a complete solution.  My
version of the answers are included below each question.

[Glo = Globe ; GWLoc = Internet Telephony Gateway Location]

---------------


--- Q1. Why can't we just use DNS?

 - query language
 - static hierarchy configuration
 - cache timer granularity


--- Q2. Draw each system architecture, indicating a advertising "server",
querying "client", and which internal nodes have cached information or
guaranteed references.

[have to draw this...]


--- Q3. What is the query format?  What is the reply format?  What is
   an "advertisement" 

  Query:
DNS: name -w- encoded location info
Glo: name hashed to OID 
SLP: attrib-based query grammar
GWLoc: SLP or LDAP query grammar

  Reply:
DNS: addr
Glo: ORef (addr)
SLP: attributes + reference
GWLoc: attributes + reference

  Advert:
DNS: none ; requires reverse lookup or out-of-band notification
Glo: as above ; could somehow be encoded in name-to-addr mappings
SLP: periodic registration with DA
GWLoc: periodic mcast to SAP address hashed from country code


--- Q4. How are mobile objects handled in each system

DNS: aren't; use DHCP/MIP
Glo: stable pointer locations with cached pointers to them
SLP: registration timeouts + re-registrations
GWLoc: next SAP channel broadcast re-advertises new bindings


--- Q5. What is the scalability model?  

DNS: manually configured hierarchy  [draw picture]
Glo: partitioning of OID space via prefix matching for parent lookup;
     aggressive pointer caching
SLP: the SCOPE model
GWLoc: small number of SAP channels + caching at brokers


--- Q6. Which scalability assumptions are weakest in each system?

DNS: stable cache entries
Glo: stable parent/partition mappings
SLP: punts on scalable SCOPE delivery model
GWLoc: update interval on SAP channels limits change (ie mobility) rate

--- Q7. How do we assess a workload on a small number of SAP channels?

Parameters: 
  # channels 
  # of advertisements 
  average size of adverts 
  global bandwidth allocated to channels 
  max acceptable refresh latency 
    (or, "mobility rate", or, rate of change of adverts, ...)

  so, for 1 billion objects on 100 channels of 100Kbps, with average ad 
size 500B, the update freq =  (10000000 * 4000b / 100Kbps) = ~111 hours

max # of objects per 100Kbps channel supported for update times < 1 hr =
  (x) objects * 4000 bits/objects / 100Kbps <= 3600 s
   ==>  (x) <= 90000 


--- Q8. Describe a single failure condition and indicate severity

DNS: node failure -- manual adaptation required
Glo: leaf failure -- bad: registrations are hard-state
SLP: DA crash --  no problem, can use mcast to query
GWLoc: broker crash -- need to configure new broker, or could 
   just listen on mcast address if client is mcast-capable and configured.

 [this is a weak question with weak answers...  the point was 
to delineate where soft and hard state live in each system.]


--- Q9. How do these relate to COM,CORBA,...?  to JNDI, SQL, CORBA traders?  

  COM/CORBA/...: these need an scalable infrastructure 
for finding referenced objects, not just a registry

  JNDI, SQL, CORBA traders: these are just query interfaces -- they don't 
solve the resolution problem or name-to-OID mapping problem.  


--- Conclusions

I claim that  none of these papers provide the complete Ninja/Iceberg
SDS solution; each gives a lot of hints on how to solve individual
subproblems in the space though.  


Main points:
 - apply soft-state to enable adaptivity and fault-tolerance
 - employ hierarchy for scalability

Some axes of interest:
- multiple hierarchies vs. a single topology-based hierarchy
- adaptive parent mappings vs. intermediate nodes are "bases"
- localized caching; stable intermediate-node caching 
- low refresh intervals (support for mobility)
- push (advertise new services)
- attribute-based queries:
   - separation of name-to-OID mapping from OID-to-ORef mapping
     - OID contain resolution path information; names do not
     - How do we provide name-to-objectID hashing?  (ie, deal -w- 
       attribute ordering, optional attributes, etc.)
   - is it possible to adaptively aggregate attributes to generate
     efficient *name* resolution paths (cf, IP address aggregation for
     IP routing)