Share Email Print

Proceedings Paper

Greedy approach to replicated content placement using graph coloring
Author(s): Bong-Jun Ko; Daniel Rubenstein
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

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.

Paper Details

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
Show Author Affiliations
Bong-Jun Ko, Columbia Univ. (United States)
Daniel Rubenstein, Columbia Univ. (United States)

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

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?