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.