Approximate Index Routing: A Case for Content-based Peer-to-Peer Routing

Abstract:

Object location in a distributed peer-to-peer
system has been a challenging problem. Our goal is to
achieve efficient and effective query routing while
imposing little restriction upon the system structure. We
propose the approach of content-based peer-to-peer
routing, in comparison to the highly structured addressbased
routing schemes such as the distributed hash table
(DHT) approaches. By decoupling object content and
their locations, content-based routing retains the
simplicity and flexibility of an unstructured peer-to-peer
system.

We present one implementation of content-based
peerto-peer routing, namely Approximate Index Routing
(AIR). Each AIR node maintains an independent
summarization of the global index. The space
consumption at each node is saved, while high routing
accuracy is achieved by cooperation between nodes with
different summarizations. Because of its simple structure,
AIR is able to exploit application inherent optimization
opportunities, such as resource heterogeneity and content
locality. We show that AIR is able to scale to peer-to-peer
systems with hundreds of millions of objects.