Dan Rubenstein's Distributed Replica/Tasking Research
Return to main research
page
Replication of a configuration, task, or data is common in distributed
network systems, especially as they grow large, making centralized
solutions unscalable (and non-resilient!). Consider the following two
examples of where replication occurs:
- content distribution networks: a piece of content is often
cached at multiple locations, in order to reduce the distance of that
content from any particular node that might be searching for it.
- 802.11 ad-hoc wireless networks: recent efforts that try
to use the entire channel spectrum of 802.11 to reduce interference
among competing transmissions. By assigning the interfering
communications to different channels, they would no longer interfere
with one another. However, there are more communications than there
are channels, so some interfering communications will have to be
assigned to the same channel.
In the first example, given limited buffer space, the goal is to
distribute content so that each content is reached in a short distance
from an arbitrary starting point. In the second example, the goal is
to keep two competing nodes that are near one another (and hence
likely to interfere) assigned to different channels when possible.
We generalized this problem to a non-traditional graph coloring
problem, where the goal is to assign a fixed number k of colors
to nodes such that
- the distance from any point to an arbitrarily chosen color is
small (useful for content distribution).
- the distance between two nodes of the same color is large (useful
for ad-hoc wireless).
While these optimization problems are not identical, it turns out that
their goals are similar: to have a good "mix" of colors inside the
network.
In [KR03], we created a distributed algorithm and
associated protocol where each node chooses its own color, greedily
changing its color whenever it wants to whatever best suits it
locally. We prove that this process converges such that all nodes are
"happy" with their own color, and prove that the resulting coloring is
within a constant factor 3 from the optimal solution. This work is
extended in [KR05], and is extended to a mesh
network application setting in [KPMR05].
- [KR03] Bong-Jun Ko and Dan Rubenstein. A distributed, self-stabilizing protocol for placement of
replicated resources in emerging networks. In Proceedings of the 11th
IEEE International Conference on Network Protocols (ICNP), Atlanta,
GA, November 2003. Best Paper Award
Recipient.
- [KR05] Bong-Jun Ko and Dan
Rubenstein. A
distributed, self-stabilizing protocol for placement of replicated
resources in emerging networks. IEEE/ACM Transactions on
Networking, 13(3), June 2005.
- [KMPR05] Bong Jun Ko, Vishal Misra,
Jitendra Padhye,
and Dan Rubenstein. Distributed channel assignment in multi-radio
802.11 mesh networks. Technical
report, Columbia University, November 2005.
Return to main research
page