
Proceedings Paper
Greedy approach to replicated content placement using graph coloringFormat | Member Price | Non-Member Price |
---|---|---|
$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
Published in SPIE Proceedings Vol. 4868:
Scalability and Traffic Control in IP Networks II
Victor Firoiu; Zhi-Li Zhang, Editor(s)
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
