A few weeks ago I provided a brief history of the P2P landscape in which I mentioned several Distributed Hash Table (DHT) implementations. The latest XRing DHT publication from Microsoft Research is dated September 2004. Substantial work has been done since that publication. To my knowledge, the only XRing DHT implementation exists within the Microsoft Research group and is not publicly available.

The XRing design is quite interesting and, unlike most DHT algorithms, isn’t dominated by a minimalist approach and instead focuses on deployment situations where the churn rate (node join and leave rate) is low or the system is of moderate size (between 1 and approximately 1 million nodes). The design of XRing uses a layered routing scheme to deliver O(logN) routing at worse case with a usual 1-hop anywhere route (2 hops for a million nodes), which is facilitated by the Finger Table and Soft-State Routing Table (SSRT), respectively. The third routing table is the Leaf Set, which contains 2L+1 entries, where L is the number of nodes to probe on either side of the home node plus the home node.

Membership in an XRing DHT is guaranteed by a weak and eventual membership protocol, which employs a special anti-entropy protocol that allows the system to coalesce; equilibrium is eventually reached. The membership and routing layer is where all the fun happens. For my implementation, a node may join an existing XRing either (a) by sending a one-way multicast request or (b) by sending a point-to-point request to an existing member. For (a), one common pattern is to send the request over a multicast channel and the response back over a point-to-point binding, which map wonderfully into WCF.

The multicast channel is realized by using the NetPeerTcpBinding class and the point-to-point channel by the NetTcpBinding class.

[ServiceContract(Namespace = "http://ws.idynamicscorp.com/P2P/Dht/XRing")]
public interface IXRingDhtDuplexMembership
{
	[OperationContract]
	void Join(DhtNodeId id);

	[OperationContract]
	void Leave(DhtNodeId id);
}

[ServiceContract(Namespace = "http://ws.idynamicscorp.com/P2P/Dht/XRing", CallbackContract = typeof(IXRingDhtMulticastMembership))]
public interface IXRingDhtMulticastMembership
{
	[OperationContract(IsOneWay = true)]
	void MulticastJoin(DhtNodeId id);

	[OperationContract(IsOneWay = true)]
	void MulticastLeave(DhtNodeId id);
}

An important design goal for any DHT implementation is that of ring simulation. Therefore, it’s important to allow a single process to support multiple nodes. Unfortunately, this meant I couldn’t use WCF configuration files but instead had to programmatically create the contract, binding, and endpoint address for each node. This took a bit of work to accomplish due to two primary reasons:

1. The current documentation is not in-sync with the bits.
2. The WCF samples use configuration-defined bindings, contracts, and endpoints.

Incidentally, working with the WCF configuration files (due to bullet 1) reminded me of a quote from David Hansson that I read on Box’s blog but with a minor modification:

WCF configuration files feel more like the doorknob to the gates of hell. In itself, a doorknob is hardly evil. But once you turn…

Fortunately (for me at least), Lutz Roeder’s .NET Reflector filled in the gaps. After some caffeine, a few frustrating moments, and questioning why I even started down this path, I found myself with a working prototype.

If you run Windows 2003 R2 as the operating system on my primary development machine (as I do), then you currently have one more obstable to overcome. Per the WCF peer channel team, the Peer Name Resolution Protocol (PNRP) service is currently available only on Windows XP (SP1 + networking pack installed), Windows XP (SP2), Windows Vista, and Windows XP Professional (64-bit) [URI]. Fortunately, you are able to leverage the CustomPeerResolver sample, which can be found in the “PeerChannelCustomPeerResolver” folder of the WinFX February CTP.

The following code fragment illustrates how to programmatically reference the custom peer resolver:

NetPeerTcpBinding binding = new NetPeerTcpBinding();
binding.Port = 4242;
binding.Security.Mode = SecurityMode.None;

//
// If the default PNRP service is not available then
// fall back to a custom peer resolver.
//
if (!NetPeerTcpBinding.IsPnrpAvailable)
{
	binding.Resolver.Custom.Address = new EndpointAddress("net.tcp://resolverUri");
	binding.Resolver.Custom.Binding = new NetTcpBinding(SecurityMode.None, true);
	binding.Resolver.Custom.Resolver = new CustomPeerResolver();
	binding.Resolver.Mode = PeerResolverMode.Custom;
}

Overall, I’m quite impressed with the flexibility of WCF and the usability that seemingly went into the consumer API surface. Hopefully, the documentation catches up to the bits.

“In a forest a tree will fade; from a forest a tree is made.”

–Unknown

Over the past several years I’ve focused on application of P2P algorithms for the commercial space. Anyway, I thought I’d share some of my thoughts and tertiary research.

First, what is Peer-To-Peer (P2P)?  P2P [URI] is a decentralized, fault tolerant, self-organizing system architecture comprised of many unreliable and heterogeneous nodes operating in a functionally symmetric manner—frequent joins and leaves are the norm. P2P is not a client / server architecture. P2P is a paradigm shift from coordination to cooperation, from centralization to decentralization, and from control to incentives.

Algorithms

To my knowledge, the Plaxton mesh (1997) was the earliest known proposal for a scalable P2P network. One major problem with a Plaxton mesh is its static—there is no concept of node arrival, departure, or failure. Essentially, nodes act as routers, clients, and servers simultaneously. A Plaxton mesh routes a message to the nodes whose name is numerically closest to the destination.

From 2001 through 2003, P2P algorithms such as Chord, CAN, Pastry, Tapestry, Viceroy, P-Grid, Kademlia, Koorde, SkipGraph, and SkipNet appeared.

Applications

Napster (www.napster.com) was one of the first P2P applications that appeared in 1999—though it’s not really a P2P network. With Napster, a single central server kept the directory of nodes and objects, which made is essentially a large file catalog—the discovery and routing algorithms are not P2P.

Gnutella first appeared in 2000 and then again in 2002. Though a pure P2P application, Gnutella generated far too much search traffic with a [broadcast-based] O(n) complexity—not very scalable.

eDonkey appeared in 2001 and presented a slight architectural improvement over Napster in that no single centralized server held the file catalog. Nevertheless, eDonkey was not a pure P2P application since it relied on status node structures.

Kazaa also appeared in late 2001 but I haven’t studied its architecture at all. I listed it here for completeness.

Gnutella-2 and BitTorrent were the P2P applications of 2002.  In 2003, Skype, Steam, and PS3 appeared.

Architecture

Common characteristics of P2P architectures are:

• No central servers.
• High level of scalability. Discovery and routing is O(log(n)). Routing table size is also O(log(n)).
• Highly resilient.
• Dynamic adaptability to node arrival, departure and failure.

Because of these characteristics, P2P architectures offer challenges in many areas. The most visible of the challenges facing designers of P2P routing algorithms are:

• Scalability. Scalability is a measure of how a system performs when the number of nodes and/or number of messages on the network grows.
• Computational Complexity. Computational complexity is the measure of the order of steps required for a packet to travel from one host to another in a worst case scenario.
• Anonymity. Anonymity is not a requirement of most P2P networks, however if a network is to be designed to provide anonymity then this is a problem that must be solved at the routing level.

Topology

A P2P infrastructure is best described as an overlay network—usually on top of an IP network.  In many ways, you can think of P2P as an application-level router providing services that underlying layers do not (i.e. IP multicast).  Generally speaking, P2P architectures employ one of the following topological structural designs:

1. Centralized (Napster)
2. Decentralized
   1. Unstructured (Gnutella)
   2. Structured (Chord)
3. Hierarchical (Multicast Backbone (MBone))
4. Hybrid (eDonkey)

Different P2P algorithms employ different topological structures. For example, Chord employs a ring topology whereas Kademlia employs a tree and CAN a hypercube.

Routing

Different topologies require different algorithm tactics and strategies. Routing within P2P architectures are very problematic.

Within P2P architectures, algorithms such as flooding, replication and caching, random walkers and probabilistic algorithms, super-peers, Time to Live (TTL), epidemic and gossip protocols, propagation, and dampening algorithms are widely used. These algorithms work well depending on the size of the P2P network. For example, flooding [http://www9.limewire.com/developer/gnutella_protocol_0.4.pdf] is more suited for a small to medium size networks but it has been shown that the cost of searching on a Gnutella style network increases super-linearly as the number of nodes increases.

Distributed Hash Tables (DHT)

DHTs are a class of decentralized distributed systems that partition ownership of a set of keys among participating nodes, and can efficiently route messages to the unique owner of any given key. A hash function (such as SHA-1) accepts a variable length string of bytes and returns a one-way hash. The physical nodes are the hash buckets. Chord is a good example of a DHT algorithm.

Incidentally, in general DHT algorithms will always beat flooding algorithms in the area of routing.

One advantage of the Chord DHT algorithm is that it guarantees receipt of a reply with log(n) time, which is a far better guarantee in terms of computational and time complexity than that offered by flooding techniques.  That said, the Kademlia DHT algorithm does offer advantages over Chord depending on application requirements.

However, DHTs are not without problem:

1. Routing state maintenance algorithms generate overhead.
2. They do not work well when lots of nodes join and leave frequently (churn).
3. Their structured topology and routing algorithms make them frail and vulnerable to security attacks.
4. Network locality problem: Nodes numerically-close are not topologically-close.

Strategies do exist to address these problems. Regardless, structured DHT algorithms provide the most interesting P2P infrastructures.

Semantic Routing

This is a relatively new area of routing as related to P2P infrastructures. Semantic Routing is a method of routing which is more focused on the nature of the query to be routed than the network topology. Essentially, semantic routing improves on traditional routing by prioritizing nodes which have been previously good at providing information about the types of content referred to by the query.

Semantic routing differs fundamentally from other routing techniques because prospective nodes are selected because of another node’s confidence in their ability to respond correctly to a given query irrespective of their position within the network. Neurogrid and Remindin are of the most interesting semantic routing systems with the Remindin system incorporating a semantic routing algorithm developed with the intention of mimicking social networks.

Summary

Overall, the most interesting of the DHT algorithms are Chord, Kademlia, and XRing.  I hope to release .NET implementations of all three of these algorithms (and a few variations) in the near future. You’ll find them here.

BitVault (defined) is a very interesting distributed data retention platform architecture from Microsoft Research. You can read the research paper here.  Another interesting bit of news is an eWeek article documenting a Microsoft announcement of the productizing of BitVault.