bamboo.vivaldi
Class Vivaldi

java.lang.Object
  bamboo.util.StandardStage
      bamboo.vivaldi.Vivaldi

All Implemented Interfaces:

EventHandlerIF, SingleThreadedEventHandlerIF

public class Vivaldi
extends StandardStage
implements SingleThreadedEventHandlerIF

A stage that implements the Vivaldi virtual coordinate system on top of bamboo. Vivaldi was developoed by Russ Cox, Frank Dabek, Frans Kaashoek, Jinyang Li, and Robert Morris. See their HotNets II paper for details of the algorithm:

Russ Cox, Frank Dabek, Frans Kaashoek, Jinyang Li, and Robert Morris. "Practical, Distributed Network Coordinate". HotNets II. November, 2003.

There are two ways we collect latency samples to update the local node's virtual coordinate.. (A latency sample made up of the measured latency between a remote node and that node's virtual coordinate.) You can select which sample collection method(s) you wish to use through config variables.

The first way is by eavesdropping on the ping messages sent by the router stage. Everytime a node is ping'ed, we also retreive its virtual coordinate and use that to do updates. The advantage of this method is we get a lot of samples, but the nodes ping'ed are not really random (since we only really ping nodes in the routing table). This can be turned on with the eavesdrop_pings config var.

The second way is to have this stage pick a random node in the overlay network by routing a LocateNodeMsg message to a randomly choosen guid. Once one is found, it then pings it and retreives the virtual coordinate. This means extra network traffic is generated, but the sample nodes are uniformly choosen. A node is picked every ping_period milliseconds. This method can be turned on with the generate_pings config var.

For generate method, you can also have the remote node updates its virtual coordinate, for no extra network traffic. This is turned on using use_reverse_ping.

You may use the update_start config variable to coordinate when the nodes will beginning taking samples. You specify the time as the number of milliseconds after epoch. This is useful when you are bringing up a large network of nodes. You do not want the first few nodes to converge before the rest of the network is brought up -- this leads to longer overall convergence time.

We also currently support three type of virtual coordinates that be used, 3 dimensional, 5 dimensional, 2.5 dimensional. The first two use Euclidean distance with just different number of dimensions, and the third represents points by a two dimensional coordinate and a planar distance. You can specify which type you wish to use by setting vc_type to one of: 3d, 5d,2.5d. I suggest you use the 5d.

Version:

$Id: Vivaldi.java,v 1.3 2004/03/09 22:04:37 czerwin Exp $

Author:

Steven Czerwinski

Field Summary

protected long

_app_id The identifier for vivaldi in bamboo.

Fields inherited from class bamboo.util.StandardStage

acore, classifier, event_types, inb_msg_types, logger, my_node_id, my_sink, outb_msg_types, sim_running

Constructor Summary

Vivaldi()

Method Summary

void	handleEvent(QueueElementIF item) Handle an event for the infrastructure node.
void	init(ConfigDataIF config)

Methods inherited from class bamboo.util.StandardStage

BUG, BUG, BUG, config_get_boolean, config_get_double, config_get_int, config_get_string, configGetInt, destroy, dispatch, enqueue, handleEvents, lookup_stage, now_ms, timer_ms

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

_app_id

protected long _app_id

The identifier for vivaldi in bamboo.

Constructor Detail

Vivaldi

public Vivaldi()
        throws Exception

Throws:

Exception

Method Detail

init

public void init(ConfigDataIF config)
          throws Exception

Specified by:

init in interface EventHandlerIF

Overrides:

init in class StandardStage

Throws:

Exception

handleEvent

public void handleEvent(QueueElementIF item)

Handle an event for the infrastructure node.

Specified by:

handleEvent in interface EventHandlerIF

Overrides:

handleEvent in class StandardStage