rice.p2p.splitstream
Class SplitStreamScribePolicy

java.lang.Object
  rice.p2p.splitstream.SplitStreamScribePolicy

All Implemented Interfaces:

ScribePolicy

public class SplitStreamScribePolicy

extends java.lang.Object

implements ScribePolicy

This class represents SplitStream's policy for Scribe, which only allows children according to the bandwidth manager and makes anycasts first traverse all nodes who have the stripe in question as their primary stripe, and then the nodes who do not.

Version:

$Id: SplitStreamScribePolicy.java 2661 2005-07-15 16:06:14Z jeffh $

Author:

Alan Mislove, Atul Singh

Nested Class Summary

Nested classes inherited from class rice.p2p.scribe.ScribePolicy

ScribePolicy.DefaultScribePolicy, ScribePolicy.LimitedScribePolicy

Field Summary

int	DEFAULT_MAXIMUM_CHILDREN The default maximum number of children per channel
protected java.util.Hashtable	policy A mapping from channelId -> maximum children
protected Scribe	scribe A reference to this policy's scribe object
protected SplitStream	splitStream A reference to this policy's splitstream object

Constructor Summary

SplitStreamScribePolicy(Scribe scribe, SplitStream splitStream)
Constructor which takes a splitStream object

Method Summary

boolean	allowSubscribe(SubscribeMessage message, ScribeClient[] clients, NodeHandle[] children) This method implements the "locating parent" algorithm of SplitStream.
void	childAdded(Topic topic, NodeHandle child) Informs this policy that a child was added to a topic - the topic is free to ignore this upcall if it doesn't care.
void	childRemoved(Topic topic, NodeHandle child) Informs this policy that a child was removed from a topic - the topic is free to ignore this upcall if it doesn't care.
void	directAnycast(AnycastMessage message, NodeHandle parent, NodeHandle[] children) This method adds the parent and child in such a way that the nodes who have this stripe as their primary strpe are examined first.
NodeHandle	freeBandwidth(Channel channel, NodeHandle newChild, Id stripeId) This method attempts to free bandwidth from our primary stripe.
java.util.Vector	freeBandwidthUltimate(Id stripeId) This method makes an attempt to free up bandwidth from non-primary, non-root stripes (for which local node is not root).
int	getMaxChildren(ChannelId id) Gets the max bandwidth for a channel.
static int	getPrefixMatch(Id target, Id sample, int digitLength) Helper method for finding prefix match between two Ids.
int	getTotalChildren(Channel channel) Returns the total number of children for the given channel
void	setMaxChildren(ChannelId id, int children) Adjust the max bandwidth for this channel.

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULT_MAXIMUM_CHILDREN

public final int DEFAULT_MAXIMUM_CHILDREN

The default maximum number of children per channel

splitStream

protected SplitStream splitStream

A reference to this policy's splitstream object

scribe

protected Scribe scribe

A reference to this policy's scribe object

policy

protected java.util.Hashtable policy

A mapping from channelId -> maximum children

Constructor Detail

SplitStreamScribePolicy

public SplitStreamScribePolicy(Scribe scribe,
                               SplitStream splitStream)

Constructor which takes a splitStream object

Parameters:

splitStream - The local splitstream

scribe - DESCRIBE THE PARAMETER

Method Detail

getMaxChildren

public int getMaxChildren(ChannelId id)

Gets the max bandwidth for a channel.

Parameters:

id - The id to get the max bandwidth of

Returns:

The amount of bandwidth used

getTotalChildren

public int getTotalChildren(Channel channel)

Returns the total number of children for the given channel

Parameters:

channel - The channel to get the children for

Returns:

The total number of children for that channel

setMaxChildren

public void setMaxChildren(ChannelId id,
                           int children)

Adjust the max bandwidth for this channel.

Parameters:

id - The id to get the max bandwidth of

children - The new maximum bandwidth for this channel

allowSubscribe

public boolean allowSubscribe(SubscribeMessage message,
                              ScribeClient[] clients,
                              NodeHandle[] children)

This method implements the "locating parent" algorithm of SplitStream. Whenever a node receives subscription request, it executes following algorithm : 1) Checks if it has available capacity, if yes, take it if no, go to step 2 2) If subscription is for primary stripe, if no, dont take it, return false if yes, need to drop someone first check if our children list for this topic is non-zero if yes, find a child which shares less prefix match than the new subscriber if found one, send it a drop message and accept newe subscriber, return true if no, dont accept the new subscriber, return false if no, look for children in other stripes which we can drop we select a stripe such that it is not a) primary stripe b) we are not the root for the stripe (may happen in very small networks) c) we have non-zero children for this stripe if found such a stripe, we drop a random child from that stripe and accept the new subscriber, return true. 3) Checks if one of our child for a stripe sent us a request message for dropping it and taking the new subscriber (STAGE_3), then we drop the child and return true to accept the subscriber.

Specified by:

allowSubscribe in interface ScribePolicy

Parameters:

message - The subscribe message in question

children - The list of children who are currently subscribed to this topic

clients - The list of clients are are currently subscribed to this topic

Returns:

Whether or not this child should be allowed add.

directAnycast

public void directAnycast(AnycastMessage message,
                          NodeHandle parent,
                          NodeHandle[] children)

This method adds the parent and child in such a way that the nodes who have this stripe as their primary strpe are examined first.

Specified by:

directAnycast in interface ScribePolicy

Parameters:

message - The anycast message in question

parent - Our current parent for this message's topic

children - Our current children for this message's topic

freeBandwidthUltimate

public java.util.Vector freeBandwidthUltimate(Id stripeId)

This method makes an attempt to free up bandwidth from non-primary, non-root stripes (for which local node is not root).

Parameters:

stripeId - DESCRIBE THE PARAMETER

Returns:

A vector containing the child to be dropped and the corresponding stripeId

freeBandwidth

public NodeHandle freeBandwidth(Channel channel,
                                NodeHandle newChild,
                                Id stripeId)

This method attempts to free bandwidth from our primary stripe. It selects a child whose prefix match with the stripe is minimum, and drops it. If multiple such child exist and newChild has same prefix match as them, then new child is not taken, otherwise a random selection is made. Otherwise, new child is taken and victim child is dropped.

Parameters:

channel - DESCRIBE THE PARAMETER

newChild - DESCRIBE THE PARAMETER

stripeId - DESCRIBE THE PARAMETER

Returns:

The victim child to drop.

childAdded

public void childAdded(Topic topic,
                       NodeHandle child)

Informs this policy that a child was added to a topic - the topic is free to ignore this upcall if it doesn't care.

Specified by:

childAdded in interface ScribePolicy

Parameters:

topic - The topic to unsubscribe from

child - The child that was added

childRemoved

public void childRemoved(Topic topic,
                         NodeHandle child)

Informs this policy that a child was removed from a topic - the topic is free to ignore this upcall if it doesn't care.

Specified by:

childRemoved in interface ScribePolicy

Parameters:

topic - The topic to unsubscribe from

child - The child that was removed

getPrefixMatch

public static int getPrefixMatch(Id target,
                                 Id sample,
                                 int digitLength)

Helper method for finding prefix match between two Ids.

Parameters:

target - DESCRIBE THE PARAMETER

sample - DESCRIBE THE PARAMETER

digitLength - DESCRIBE THE PARAMETER

Returns:

The number of most significant digits that match.