Implementation of Viceroy: A Scalable and Dynamic Lookup Network

See:
Description

Packages

viceroy
viceroy.GUI
viceroy.misc.typeSafeCollections
viceroy.net

Implementation of Viceroy: A Scalable and Dynamic Lookup Network

see What's New In Version 3.1 below.

The project consists of 3 packages. The viceroy package contains the algorithms and the main entities in the Viceroy Network. The viceroy.net package contains the communication infrastructure for the Viceroy network. The viceroy.misc.typeSafeCollections contains a set of utility classes which implement the notion of type-safe Collections. The viceroy GUI contains the gui files

We will give a short description of each package:

The viceroy package

All lookup networks consist of LookupPeer's. We supplied this interface in order to support other network topologies, besides the Viceroy network topology. We also supplied an AuthorizedLookupPeer interface, which represents a LookupPeer that can initiate lookup requests, joins and leaves, whereas the LookupPeer only responds to requests. The other interfaces are Viceroy-specific, and refer to the topology of the Viceroy network in the most general way.

The two topology-specific interfaces are ViceroyPeer and AuthorizedViceroyPeer. For most of the API we use ViceroyPeer.

Implementation Notes:
The Viceroy network consists of LocalViceroyPeer's, which is an implementation of AuthorizedViceroyPeer. Each such peer has several connections to the Viceroy network; These links are represented as ViceroyPeer fields. In a distributed system, these fields will actually be ReomteViceroyPeer's, representing a remote peer in a different computer (a stub). In a single computer system, these fields will be LocalViceroyPeer's, however, it does not matter, as those connections are viewed as ViceroyPeer's. Therefore, running and testing our system would not require any change in our source code.

The LocalViceroyPeer uses the ViceroyPeerManager as its communication server. This object is responsible for all communication matters. As we used an Interface to describe it, any specific implementation can be used, e.g., Jxta implementation, TCP/IP, RMI, or even simple single-computer implementation.
After registering itself to the communication manager (and after receiving a real-world address), the peer does not use the ViceroyPeerManager directly. Instead, it calls the appropriate methods in its connection fields (successor, predecessor and such - all are ViceroyPeers). For example, when receiving a lookup message, the peer will do:

(code from LocalViceroyPeer.lookup(Resource valueToLook, ViceroyPeer returnAddress) )

if (this.level != 1)
    this.successor.lookup(valueToLook, returnAddress);

If we are in a distributed system, the successor is actually a RemoteViceroyPeer, so its lookup message will simply create a new LookupMessage, and send it (using the ViceroyPeerManager) to the actual remote peer. The LocalViceroyPeer registers a set of Listeners (specific to each message) which define the behaviour of dealing with incoming messages. Each incoming message is treated as an event, which activates the corrosponding XXXReceived() methods in the LocalViceroyPeer.

The viceroy.net package

We defined a Listener interface, and a set of message-specific interface listeners. The implementing classes are actually private inner classes inside LocalViceroyPeer. We also defined a Message interface, and implemented all relevant messages classes. We haven't implemented 2 interfaces: ViceroyPeerManager and Address. The implementer of those interfaces can do it using Jxta, TCP/IP, RMI etc.

The viceroy.misc.typeSafeCollections package

We implemented a set of classes which supply a better solution to Java's standard Collection Framework. Our classes implements the standard interfaces supplied with the Java SDK (List, Set, Map etc.). We are using those classes for better type-safety.

What's new in version 3.1

• 1. We made an applet version of viceroy, which can be found in:
applet
• 2. We added a new view of the nodes ("Line")
• 3. We added some new lookup algorithms: Now, there are 4 lookup algorithms:

a. The Paper's algorithm - exactly as written in the paper.
b. The PapersPlus Algorithm - As written in the article plus an extra optimization check in The TraverseTree phase.
c. The TraverseTreePlus Algorithm: continue in Traverse Tree phase even if the children overshoot the target. Currently, there is no threshold and it proceeds down the tree as long as there are children.
d. The TraverseTreeAbsolute Algorithm: choose (in Traverse Tree phase) the closest (abs) to the target from the current node and its children.
e. The FindFast Algorithm: the greedy algorithm.

• 4. We used the Strategy pattern for the various lookup algorithms: A LookupAlgorithm object is passed in the lookup process, so that each peer asks for its next move on the lookup using the "nextOnLookup(...)" method. This way, it would be easy to add new lookup algorithms, by extending the current algorithms.
• 5. We added support for viceroy client (per roy's request), which includes listeners for various events, and methods to handle them.
• 6. In the join and leave operations there could be a level change in some peers. As a consequence, the viceroy's butterfly might change.
• 7. We added Unit Testing classes for all main classes. Those tests are an inherent part of every version-release from now.
• 8. We added a small statistics program. It compares the different algorithms and presents the result statistics in a table.

Anat Talmy, anatt@cs.huji.ac.il

Oren Dobzinski, orend@cs.huji.ac.il