A Hypercube-based Routing Algorithm for Scalable Multi-Attribute Range Queries
Nguyen Hoaison, Hiroyuki Morikawa, Tomonori Aoyama · IEICE Technical Report; IEICE Tech. Rep. · 2005
We design a scalable and expressive naming system called SENS, which can retrieve information of computing and content resources distributed widely on the Internet by multi-attribute range queries. Our system utilizes a descriptive naming scheme which names a resource by a tupple of attribute/value pairs. To realize scalable message routing for resource information distribution and queries, our system utilizes a multi-dimensional resource ID space constructed on the overlay network of NSs by hypercube-based CAN routing algorithm. We propose a mapping technique between resource names and resource IDs, which can preserve the locality of resource IDs while still achieves good load balancing of resource information distribution. We also propose a novel broadcasting routing algorithm based on a spanning polynomial tree to route multi- -attribute range query messages to NSs in a resource ID query segment. Our simulation results show that our system can achieve good routing performance and load balancing.