INS/Twine: A Scalable Peer-to-Peer Architecture for Intentional Resource Discovery

Balazinska, Balakrishnan, and Karger

service discovery distributed hashtables dht

@inproceedings{balazinska:pc-2002,
  title={{INS/Twine}: A Scalable Peer-to-Peer Architecture for
         Intentional Resource Discovery},
  author={Balazinska, M. and Balakrishnan, H. and Karger, D.},
  booktitle={International Conference on Pervasive Computing},
  pages={195--210},
  year={2002},
  publisher={Springer-Verlag}
}

Attach:Balazinska-PC2002.pdf

INS/Twine~\cite{balazinska:pc-2002} attempts to extend the scalability of INS~\cite{adjie-winoto:sosp-1999}, the Intentional Naming System, by developing a distributed hashtable over the INS resolvers, which act as service discovery brokers. Service descriptions in INS/Twine take the form of arbitrary, hierarchically structured attribute/values pairs; an example is given in Figure~\ref{fig:ins-twine-description}. Syntactically these are exchanged as mixed XML snippets, as in Figure~\ref{fig:ins-twine-xml}, within an XML container wrapping the registration. Those snippets capture attribute/value trees (AV trees), as in Figure~\ref{fig:ins-twine-avtree}. In storing a registration within the DHT, INS/Twine extracts each path originating from the root in the associated AV tree. Notably, this includes all paths ending at interior values, not just paths from the root to the leaves. Each of those paths are then hashed into keys which are then mapped to nodes by the underlying Chord DHT over the resolvers. Those controlling nodes then store a referent to the service for that path.

Service queries are resolved in INS/Twine in a mirror process. Each is encoded as a similar XML snippet identifying a template to match. Root paths are extracted from that snippet and mapped to nodes in the DHT. The intersection of the referents stored for each of those paths is then the query result. Storing and fetching of all paths in the registrations is the critical element that enables partial queries containing only a subset of the attribute/value structure and wildcards.