Connectivity within ad-hoc and peer-to-peer networks undergoes constant change. One approach to reducing the cost of finding information within these networks is to replicate the information among multiple points within the network. A desirable replication approach should cache copies of all pieces of information as close to each node as possible without exceeding the storage resources of the nodes within the network. In addition, the approach should require minimum communication overhead among participating nodes and should adjust the locations of stored content as connectivity within the network changes. Here, we formulate this caching problem as a graph coloring problem, where the color of the node determines the content that the node should store. We present a distributed algorithm where each node chooses its color in a greedy manner, minimizing its own distance to the color furthest from it. We demonstrate convergence of this algorithm and evaluate its performance in the context of its ability to place information near all nodes in the network.

Date Published: 8 July 2002
PDF: 10 pages
Proc. SPIE 4868, Scalability and Traffic Control in IP Networks II, (8 July 2002); doi: 10.1117/12.475279

Published in SPIE Proceedings Vol. 4868:
Scalability and Traffic Control in IP Networks II
Victor Firoiu; Zhi-Li Zhang, Editor(s)