Greedy approach to replicated content placement using graph coloring

Bong-Jun Ko; Daniel Rubenstein

doi:10.1117/12.475279

8 July 2002 Greedy approach to replicated content placement using graph coloring

Bong-Jun Ko, Daniel Rubenstein

Proceedings Volume 4868, Scalability and Traffic Control in IP Networks II; (2002) https://doi.org/10.1117/12.475279
Event: ITCom 2002: The Convergence of Information Technologies and Communications, 2002, Boston, MA, United States

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.

Citation Download Citation

Bong-Jun Ko and Daniel Rubenstein "Greedy approach to replicated content placement using graph coloring", Proc. SPIE 4868, Scalability and Traffic Control in IP Networks II, (8 July 2002); https://doi.org/10.1117/12.475279

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available