CMSC 433, Fall 2003

Programming Language Technologies and Paradigms

Project 5


Due Dec 14, 2003 (6pm); late deadline December 19 (6pm)

A Distributed Peer-to-Peer Network

Many standard network services are built around a client-server model: In order to access some service, a client machine contacts a dedicated server on the network. For example, to look at this web page, you are using your web browser (a client) to access the Computer Science department's web server.

In a peer-to-peer network, in contrast, individual machines on the network act as both clients and servers, and they communicate with each other without going through a centralized server. Each node on the network has a set of peers that it talks to directly. If a node wants to talk to another node that is not one of its immediate peers, it needs to relay the message through some peer that it does talk to directly. For example, in the following network, A can send a message to B or C in one "hop," but if A wants to send a message to D, it needs to go through B first, and it takes two "hops." A and B (and A and C) are peers, but A and D are not.

In this project, you will build a simple peer-to-peer networking program using Java RMI. When your code is running, it will connect with other students' code (and the instructors' code) to form a peer-to-peer network. Once operational your code will be able to join the network, broadcast requests for services, receive service references from peers, and remotely invoke the resulting services on remote peers.

An example scenario is that a peer wants to execute some application. In order to carry out the application the peer needs to invoke several services. This peer however does not have access to some or all required services. Therefore, it must search the network for other peer that will let it "borrow" them.

More generally, this organization allows service instances to be registered with specific peers distributed across the network. Individual peers can search for services by names and then assemble them in various ways to carry out applications of interest to that peer .

Start this project now! This is a long and somewhat complicated write-up, and though you don't need to write too many lines of code for this project you do need to understand this document in order to do the project. As usual, javadoc for the classes we've provided you and for the code you need to implement is available.

Joining the Network

Each participant in our peer-to-peer network is represented by a Portal object, implemented in file Portal.java. When a Portal object is constructed, it tries to join the network by finding another Portal object and asking to peer with it. Portals talk to each other using the RemotePortal RMI interface, which Portals implement (they also implement a LocalPortal interface; see below):

Each portal has a unique portal address, which is a URL (encoded as a String) for an entry in an RMI registry. For example, we have a portal registered at rmi://ramen.cs.umd.edu:1099/Portal. Here ramen.cs.umd.edu is the host name, 1099 is the port the RMI registry is listening on, and Portal is the name entered in the registry. A remote client can get access to the portal by invoking Naming.lookup(<portal address>), which returns a RemotePortal stub.

Portals have a constructor Portal(int port) that creates the portal and joins the network. To join the network a Portal p does several things:

First p creates an RMI registry listening on the port specified to the constructor and registers itself under the name Portal (just like our example above).  Portal p can now be found in the registry using some URL u.

Next,  p needs to find a portal q on the network and invoke q.somebodyPeerWithMe(u),. The somebodyPeerWithMe method is used whenever a Portal wants to initiate a peering relationship with some other Portal. In our example, portal p uses this method to ask q to peer with it. (q will find p by calling Naming.lookup(u)).

If q wants to peer with p, then it will invoke p.peerWithMe(<q's address>, <peer for q>, <max # peers>). Note that a peering relationship is managed by a Peer object. This object will be an inner class of Portal an is described in more detail later. The peerWithMe method is used whenever a Portal responds (affirmatively) to a request to peer.  Invoking the peerWithMe method allows p to receive q's peer and returns p's peer to q. So if the call is succesful, q will add p to its set of peers and p adds q to its set. We'll talk about the last argument to peerWithMe later.

Notes: 

Peers and Messages

Notice that the RemotePortal interface contains methods for joining a network but not methods for sending messages over the network. To actually send a message, we use a different interface. When portal q accepts a request to peer with portal p, portal q calls p.peerWithMe(<q's address>, q1, ...) where q1 implements the RemotePeer RMI interface. Conceptually, RemotePeer objects represent a one-way connection from one Portal to another. You will implement RemotePeer as an inner class of Portal.

p.peerWithMe() also returns an object p1 that also implements the RemotePeer RMI interface. When p wants to send a message to q, it uses q1, invoking invokes q1.receive(<some message>). In turn, when q wants to send a message to p, it invokes p1.receive(<some message>).

For example, suppose that portal A peers with portals B and C. Then we will create the following objects:

Notice that there is one peer for each direction of communication and for each pair of connected portals. For example, there are two peers that let a portal send a message to portal A: the peer from C to A and the peer from B to A. We can use the fact that these peers are different objects to detect which portal sent a message.

If p has a RemotePeer for q, the simplest thing p can tell q (using the peer q1) is logoff(). Portal p invokes q1.logoff() to let q know that p is leaving the network. After this call, q should not send any more messages to p unless p rejoins the network later.

Portal p can also send a Message to q using q1.receive(). A Message is an object that supports several methods: process(LocalPortal)  and getTTL(). Notice that messages are code and not data: The only way to use a message is to run its process() method. In particular, when a message m is sent from portal p to portal q, portal q invokes m.process(Portal.this) to "read" the message. For example, here is the process() method for BroadcastTextMessage.java, one of the Messages you can use for testing your project.

    public void process(LocalPortal portal) {
        portal.println(msg);
        portal.forward(this);
}

Another Message you will need to implement is the FindServiceMessage. When a FindServiceMessage is sent to portal q, portal q invokes its process() method, which searches for a named service in q. If q has not previously added that service (by using the addService() method) , it forwards the message to its peers. Otherwise it prepares a FoundServiceMessage and broadcasts it over the network. This message's will add the service to the current portal  when its process method is called.

You may have also noticed that when process() is invoked on a portal, it is passed a LocalPortal as a parameter. The LocalPortal interface encapsulates the methods that Portals support locally. These methods are often called by Message's process method. For example, looking back to the BroadcastTextMessage. It process method calls the println method and forward method of its LocalPortal parameter.

The println method prints to System.out. The forward() method of LocalPortal asks the portal to send msg to all of its peers on the network, except the peer for msg came from. 

LocalPortals also support the addService method which registers services with the LocalPortal. Services can be looked up remotely by other Portals using the getService method. 

Services

For this project services are implemented as subclasses of the Remote interface Service. Services have a transformString method which takes a String as input, processes it in some way and returns a String as output. They should extend NullService, so that you only need to run rmic on NullService. Some services that would be nice to have include:

All students who develop working implementations of these services will get 2 pts extra credit per service (up to 10pts extra).

Time-to-live, Message ids

In order to limit potential problems, each message has a time-to-live, accessible via getTTL(). A message with time-to-live n should be sent only to portals at most n hops away from the message source. More precisely, when a portal gets a message it runs the process method, which may then call forward() to pass the message on to the portal's peers. If the message's time-to-live is negative or zero, then the portal should ignore any calls to forward the message. (It should still invoke the process method---it just shouldn't forward it any more.) You don't need to take care of decrementing the time-to-live---that's taken care of automatically in Message.java---but you do need to check the time-to-live before forward() passes a message on.

We also have to worry about duplicate messages. For example, suppose that there are two paths in the network from portal A to portal B, and suppose A broadcasts a message. Then B will receive A's message twice, once per network path. But we'd like to only process() the message once. Therefore, each message has a public Long id field. Portals should only process each message id exactly once. (If you look at the code in Message.java, you'll see that the message id is set to a value that is unlikely to be duplicated.)

Network Architecture

Whew! OK, so far we've talked about the basics of connecting to a RemotePortal on the network and then sending a message to it via a RemotePeer. Now it's time to go back and answer some questions we've ignored so far: How do you find a RemotePortal on the network? What happens if you ask to peer with a portal and it doesn't want to peer with you? And what is that funny initiatePeering method of LocalPortal for?

In the beginning of this discussion, we said that to join the peer-to-peer network, a portal needs to find a portal q on the network and invoke q.somebodyPeerWithMe(u), where u is a URL for the portal that wants to join the network. But how do we find a portal q if we're not on the network? For this project, the answer is that we will put a portal on the network at a known address: you can get a RemotePortal on the network at rmi://ramen.cs.umd.edu:1099/Portal.

So consider the following. We have roughly 100 students taking this class. If everyone peers with ramen, then to broadcast a message to the network a portal will send a message to ramen, which will in turn send the message to the other 99 of its peers. This isn't much of a peer-to-peer network, since everything needs to go through ramen! In effect, we'll have built a client-server network. Instead, we want a true peer-to-peer network, which means that although everyone will initially ask to peer with ramen, they may wind up peering with another portal.

In our network, each portal will have a maximum of four peers (actually, we may go a bit higher; see below). When q.somebodyPeerWithMe(u) is invoked, if q has fewer than four peers, it does exactly what we said before: it looks up the RemotePortal corresponding to u and invokes its peerWithMe method(). However, if q already has four (or more) peers, then q doesn't peer with p. Instead, it broadcasts p's peer request over the network.

In this case, q sends a PeerWithMe(<q's portal address>, <p's portal address>) message to all of its peers. They in turn will invoke PeerWithMe.process(), which when run on a local portal will invoke initiatePeering() on that portal. When initiatePeering() is invoked, the local portal will check whether it has room for more peers. If it does, then it invokes p.peerWithMe(), and initiatePeering returns true. Otherwise initiatePeering returns false, and the PeerWithMe message forwards itself to the local portal's peers. Note that p.peerWithMe() might fail with an exception if p already has enough peers.

There is one potential problem with this set-up: if we have a hard maximum of four peers, then we could easily get into a situation in which no one can join the network. For example, if our network currently consists of a clique with five portals, then no portal will be willing to peer with anyone else, and no one can join. To solve this problem, a portal with four peers will peer with another portal that has no peers. This is what the last parameter of RemotePortal.peerWithMe() is for: If p has less than or equal to maxPeers peers, then p.peerWithMe() should return as usual; if p already has more than maxPeers peers, then p.peerWithMe() should raise a RemoteException. Note that the portal that invokes p.peerWithMe() is trusting p to tell the truth about its number of peers. Once a portal has five peers, it won't peer with anyone else no matter what.

Synchronization, Threading, and Reliability

As with project 4, you need to worry about synchronization. Any method invoked remotely may potentially be run in a separate thread. For example, two remote machines may invoke RemotePeer.receive() on the same remote object, and the execution of the two calls to receive() may be interleaved unless you use synchronization.

Finally, your code needs to be robust in the presence of network failures. If a peer dies, your code should be able to handle it. If all of your peers die, you should go back to cafe and request to peer with another node.  Furthermore, you should always try to maintain at least three peers on the network.

One way to do this, which we recommend for this project, is to start a separate thread when you create a portal. Every 10 seconds, that thread should check whether it has at least three peers. If it does not, then it should try to find more peers (by sending an appropriate PeerWithMe message to the network).

Dealing with slow portals

Your implementation should deal with slow portals. If you peer with a portal that responds to messages very slowly, your portal should still handle other messages while trying to send a message to the slow portal.

One suggestion is to use a separate thread to send each message.

Final Notes // Under Construction

To submit this project, use a command like

java -jar ~/Submit.jar 5 *.java

As always, submit early and often.

Files

Live updates from well known portal

Hints

Resources

Amendments 

Valid HTML 4.01!