edu.virginia.cs.mng.hypercast.DT
Class DT_Neighborhood

java.lang.Object
  |
  +--edu.virginia.cs.mng.hypercast.DT.DT_Neighborhood

final class DT_Neighborhood

extends java.lang.Object

implements I_Stats

This class keeps track of the Neighborhood table and LogicalAddress of a node in the Delaunay triangulation. It also provides a large variety of helper functions.

The neighbors are kept unsorted in a Vector. The neighbors can be accessed either through their index in the Vector, or by the neighbor's Physical Address. For each neighbor, DT_Neighborhood stores an AddressPair and the time the most recent message was received from that neighbor.

DT_Neighborhood maintains a property on the neighbors. This property is: In a Delaunay triangulation of the node's Logical Address and its neighbors' Logical Addresses, there would be an edge connecting the node's LA to each of its neighbor's LAs. When a node is inserted causes this property to be violate, neighbors are removed to restore the property. For any problems, contact Jorg Liebeherr at jorg@cs.virginia.edu

Field Summary

private I_UnicastAdapter	adapter Network adapter (used for times and Physical Address).
private java.lang.String	addNeighborDebug
private OverlaySocketConfig	config Source of constants & error/log message display
private static double	MIN_ANGLE Corrective value for double arithmetic when calculating CW and CCW neighbors.
private DT_AddressPair	myAddressPair The physical and logical address of this node.
private java.util.Vector	neighbors NeighborhooEntries of the node's neighbors.

Constructor Summary

DT_Neighborhood(OverlaySocketConfig c, I_UnicastAdapter ua, DT_LogicalAddress startingCoords)
Constructor.

Method Summary

void	addNeighbor(DT_AddressPair addr, DT_AddressPair cw, DT_AddressPair ccw, boolean hasThisNodeAsNeighbor) Inserts a neighbor and then removes neighbors to make neighborhood consistent
private boolean	amIParent(DT_NeighborhoodEntry nodeEntry, DT_LogicalAddress root) Returns true if this node is the parent of the neighbor node in a spanning tree rooted at root
boolean	contains(I_PhysicalAddress addr) Returns true if one of the neighbors has a phyiscal address equal to the parameter.
DT_AddressPair[]	getAllNeighbors() Returns the AddressPairs of all the neighbors
DT_AddressPair	getCCWNeighbor(DT_LogicalAddress la) Finds the neighbor with the CCW smallest angle to the parameter with respect to this node.
DT_AddressPair[]	getChildren(DT_LogicalAddress root) Return the AddressPairs of neighbor that are children of this node in a spanning tree rooted at rootCoords.
DT_AddressPair	getCWNeighbor(DT_LogicalAddress la) Finds the neighbor with the CCW smallest angle to the parameter with respect to this node.
private DT_NeighborhoodEntry	getEntry(int i)
long	getLastContactTimeOfNeighborAtIndex(int i) Returns the Nth neighbor's LastContactTime (the last time a message was received from that neighbor).
DT_LogicalAddress	getLogicalAddress() Returns logical address of this node.
DT_AddressPair	getMyAddressPair()
DT_AddressPair	getNeighborAtIndex(int i) Returns the Nth neighbor's AddressPair.
DT_AddressPair	getNeighborAtSameAngle(DT_LogicalAddress la) Returns neighbors that lies as the same angle as the parameter with respect to this node.
DT_AddressPair	getNeighborWithThisPA(I_PhysicalAddress addr) Returns the AddressPair of the neighbor whose physical address equals the parameter.
DT_AddressPair	getNextHopToLeader() Returns the neighbor with the greatest coordinates.
DT_AddressPair	getNodeCCWOfNeighborAtIndex(int i) Returns the Nth neighbor's CCW neighbor's AddressPair.
DT_AddressPair	getNodeCWOfNeighborAtIndex(int i) Returns the Nth neighbor's CW neighbor's AddressPair.
int	getNumOfNeighbors() Returns the number of neighbors.
DT_AddressPair	getParent(DT_LogicalAddress rootCoords) Returns AddressPair of neighbor that is parent of this node in a spanning tree rooted at rootCoords.
I_PhysicalAddress	getPhysicalAddress() Returns physical address of this node.
java.lang.String[]	getSchema() Part of I_Stats interface.
java.lang.String	getStats(java.lang.String name) Part of I_Stats interface.
boolean	hasFourOnCircle() Returns true if any 4 neighbors lie on a circle
int	indexOfNeighbor(I_PhysicalAddress addr) Finds the index of the neighbor whose physical address equals the parameter.
int	isConsistent() Test Function.
boolean	isEmpty() Returns true if there are no neighbors.
boolean	isLeader() Returns true if no neighbor's Logical Address is greaterThan this node's LogicalAddress.
boolean	isStable() Returns true every neighbor's CW and CCW entry are in the neighborhood.
boolean	isThisClosest(DT_Point p) Returns true if this node is at least as close to the point p as any of its neighbors.
boolean	neighborAtIndexHasThisNodeAsNeighbor(int i) Returns if Nth neighbor has this node as a neighbor.
boolean	neighborHasThisLA(DT_LogicalAddress la) Returns true if there exists a neighbor with a LogicalAddress equal to the parameter.
private void	randomShiftMyCoordinates() Changes this node's LogicalAddress by a small amount.
void	removeAllNeighbors() Remove all neighbors from the Neighborhood.
void	removeNeighbor(DT_AddressPair addrs) Removes neighbor identified by the PhysicalAddress of its AddressPair.
void	removeNeighbor(I_PhysicalAddress addr) Removes neighbor identified by its PhysicalAddress.
void	removeNeighbor(int i) Removes neighbor identified by its index
private void	removeNonNeighbors() Returns the neighborhood to consistency.
void	setStats(java.lang.String name, java.lang.String value) Part of I_Stats interface.
boolean	shouldBeNeighbor(DT_LogicalAddress la) Returns true if the node with LogicalAddress la can be added as a neighbor.
java.lang.String	toString() Creates a string containing the state of the neighborhood.
(package private) boolean	updateContactTable(I_PhysicalAddress addr, DT_AddressPair cw, DT_AddressPair ccw, boolean hasThisNodeAsNeighbor) Sets the contact time for the neighbor identified by its PhysicalAddress.

Methods inherited from class java.lang.Object

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

Field Detail

config

private OverlaySocketConfig config

Source of constants & error/log message display

adapter

private I_UnicastAdapter adapter

Network adapter (used for times and Physical Address).

myAddressPair

private DT_AddressPair myAddressPair

The physical and logical address of this node.

neighbors

private java.util.Vector neighbors

NeighborhooEntries of the node's neighbors. This is unordered. If the neighbors were sorted by angleToTheHorizon, many functions implementations could be significantly sped up.

See Also:

DT_NeighborhoodEntry

addNeighborDebug

private java.lang.String addNeighborDebug

MIN_ANGLE

private static double MIN_ANGLE

Corrective value for double arithmetic when calculating CW and CCW neighbors.

Constructor Detail

DT_Neighborhood

public DT_Neighborhood(OverlaySocketConfig c,
                       I_UnicastAdapter ua,
                       DT_LogicalAddress startingCoords)

Constructor.

Parameters:

startingCoords - The starting address of this node.

Method Detail

getEntry

private DT_NeighborhoodEntry getEntry(int i)

getMyAddressPair

public DT_AddressPair getMyAddressPair()

getLogicalAddress

public DT_LogicalAddress getLogicalAddress()

Returns logical address of this node.

getPhysicalAddress

public I_PhysicalAddress getPhysicalAddress()

Returns physical address of this node.

getNumOfNeighbors

public final int getNumOfNeighbors()

Returns the number of neighbors. This is useful when calling getNeighborAtIndex()

isEmpty

public boolean isEmpty()

Returns true if there are no neighbors.

isLeader

public boolean isLeader()

Returns true if no neighbor's Logical Address is greaterThan this node's LogicalAddress.

isStable

public boolean isStable()

Returns true every neighbor's CW and CCW entry are in the neighborhood.

getNeighborAtIndex

public DT_AddressPair getNeighborAtIndex(int i)

Returns the Nth neighbor's AddressPair. The neighbors are not ordered.

getNodeCWOfNeighborAtIndex

public DT_AddressPair getNodeCWOfNeighborAtIndex(int i)

Returns the Nth neighbor's CW neighbor's AddressPair.

getNodeCCWOfNeighborAtIndex

public DT_AddressPair getNodeCCWOfNeighborAtIndex(int i)

Returns the Nth neighbor's CCW neighbor's AddressPair.

neighborAtIndexHasThisNodeAsNeighbor

public boolean neighborAtIndexHasThisNodeAsNeighbor(int i)

Returns if Nth neighbor has this node as a neighbor.

getLastContactTimeOfNeighborAtIndex

public long getLastContactTimeOfNeighborAtIndex(int i)

Returns the Nth neighbor's LastContactTime (the last time a message was received from that neighbor). The neighbors are not ordered.

contains

public boolean contains(I_PhysicalAddress addr)

Returns true if one of the neighbors has a phyiscal address equal to the parameter. Recall, a physical address uniquely identifies a node.

indexOfNeighbor

public int indexOfNeighbor(I_PhysicalAddress addr)

Finds the index of the neighbor whose physical address equals the parameter. Recall, a physical address uniquely identifies a node.

getNeighborWithThisPA

public DT_AddressPair getNeighborWithThisPA(I_PhysicalAddress addr)

Returns the AddressPair of the neighbor whose physical address equals the parameter. Recall, a physical address uniquely identifies a node.

neighborHasThisLA

public boolean neighborHasThisLA(DT_LogicalAddress la)

Returns true if there exists a neighbor with a LogicalAddress equal to the parameter.

getParent

public DT_AddressPair getParent(DT_LogicalAddress rootCoords)

Returns AddressPair of neighbor that is parent of this node in a spanning tree rooted at rootCoords. This is calculated by finding the neighbor that forms the smallest angle with rootCoords.

getChildren

public DT_AddressPair[] getChildren(DT_LogicalAddress root)

Return the AddressPairs of neighbor that are children of this node in a spanning tree rooted at rootCoords. This based on if DT_Neighborhood.getParent() of the neighbor would return this node.

amIParent

private boolean amIParent(DT_NeighborhoodEntry nodeEntry,
                          DT_LogicalAddress root)

Returns true if this node is the parent of the neighbor node in a spanning tree rooted at root

See Also:

getParent

getAllNeighbors

public DT_AddressPair[] getAllNeighbors()

Returns the AddressPairs of all the neighbors

getNextHopToLeader

public DT_AddressPair getNextHopToLeader()

Returns the neighbor with the greatest coordinates.

isThisClosest

public boolean isThisClosest(DT_Point p)

Returns true if this node is at least as close to the point p as any of its neighbors.

hasFourOnCircle

public boolean hasFourOnCircle()

Returns true if any 4 neighbors lie on a circle

shouldBeNeighbor

public boolean shouldBeNeighbor(DT_LogicalAddress la)

Returns true if the node with LogicalAddress la can be added as a neighbor.

getNeighborAtSameAngle

public DT_AddressPair getNeighborAtSameAngle(DT_LogicalAddress la)

Returns neighbors that lies as the same angle as the parameter with respect to this node. If this returns a node, then this node, parameter, and returned node lie on a line.

getCCWNeighbor

public DT_AddressPair getCCWNeighbor(DT_LogicalAddress la)

Finds the neighbor with the CCW smallest angle to the parameter with respect to this node. The angle must be greater than MIN_ANGLE

See Also:

MIN_ANGLE

getCWNeighbor

public DT_AddressPair getCWNeighbor(DT_LogicalAddress la)

Finds the neighbor with the CCW smallest angle to the parameter with respect to this node. The angle must be greater than MIN_ANGLE

See Also:

MIN_ANGLE

isConsistent

public int isConsistent()

Test Function.

addNeighbor

public void addNeighbor(DT_AddressPair addr,
                        DT_AddressPair cw,
                        DT_AddressPair ccw,
                        boolean hasThisNodeAsNeighbor)

Inserts a neighbor and then removes neighbors to make neighborhood consistent

removeNeighbor

public void removeNeighbor(I_PhysicalAddress addr)

Removes neighbor identified by its PhysicalAddress.

removeNeighbor

public void removeNeighbor(int i)

Removes neighbor identified by its index

removeNeighbor

public void removeNeighbor(DT_AddressPair addrs)

Removes neighbor identified by the PhysicalAddress of its AddressPair.

removeAllNeighbors

public void removeAllNeighbors()

Remove all neighbors from the Neighborhood.

updateContactTable

boolean updateContactTable(I_PhysicalAddress addr,
                           DT_AddressPair cw,
                           DT_AddressPair ccw,
                           boolean hasThisNodeAsNeighbor)

Sets the contact time for the neighbor identified by its PhysicalAddress.

randomShiftMyCoordinates

private void randomShiftMyCoordinates()

Changes this node's LogicalAddress by a small amount. Changing the LogicalAddress can make the neighborhood inconsistent.

removeNonNeighbors

private void removeNonNeighbors()

Returns the neighborhood to consistency.

getStats

public java.lang.String getStats(java.lang.String name)
                          throws StatsException

Part of I_Stats interface.

Specified by:

getStats in interface I_Stats

See Also:

I_Stats.getStats(java.lang.String)

setStats

public void setStats(java.lang.String name,
                     java.lang.String value)
              throws StatsException

Part of I_Stats interface.

Specified by:

setStats in interface I_Stats

See Also:

I_Stats.setStats(java.lang.String, java.lang.String)

getSchema

public java.lang.String[] getSchema()
                             throws StatsException

Part of I_Stats interface. Returns an XML schema describing acceptable request messages.

Specified by:

getSchema in interface I_Stats

See Also:

I_Stats.getSchema()

toString

public java.lang.String toString()

Creates a string containing the state of the neighborhood.

Overrides:

toString in class java.lang.Object