Introducing the Distributed Routing Table in Windows 7

In Windows 7, we’ve added support for key based routing with a new peer-to-peer platform piece called the Distributed Routing Table (DRT). Applications can use a new Windows API to publish numeric keys, and resolve keys to network endpoints without the aid of servers. This functionality can be the basis of a Distributed Hash Table (DHT) and is fundamental in Microsoft’s Peer Name Resolution Protocol (PNRP). Key based routing can also be used to build peer-to-peer networks of many topologies, greatly simplifying the development applications needing serverless synchronization, flooding or content distribution.

The DRT protocol is based on version 2 of the Peer Name Resolution Protocol. If you’ve read our PNRP whitepaper, and you’re familiar with PNRP concepts, you will have a much easier time understanding the DRT. PNRP allows applications to publish and resolve names without the aid of servers. When resolving a name, PNRP first converts the name to a 256 bit numeric key, and then uses an iterative lookup procedure to traverse a structured overlay and locate the machine publishing the precise target name. The DRT, on the other hand, leaves the application free to define how keys are derived, and provides a rich search API that allows applications to find the nearest keys to a target, or search for keys falling within a range of values. The DRT uses the same iterative lookup procedure and multi-level cache proven successful in PNRP.

DRT keys are a fixed size: 256 bits. Your application is free to define what these keys mean, how they are generated and how they are secured. During initialization, your application must supply the DRT engine with a module known as a security provider. Your security provider understands the meaning of DRT keys in your system, and will be called upon by the DRT engine to process certain messages during the key publication and resolution processes.

The DRT platform includes two fully implemented security providers that are suitable for a broad range of applications. The derived key security provider (DKSP for short) secures keys using X.509 certificates. In a DRT configured with the DKSP, each machine must possess a certificate chaining to a common root, and can only publish a 256 bit key derived from the SHA-2 hash of the public key embedded in that certificate. The DRT platform also includes a NULL security provider, which allows all machines participating in the DRT mesh to publish any 256 bit key. This security provider is not suitable for internet deployments, but is great for prototyping and some applications that will be used in private networks.

Several types of searches are possible using the DRT API. We’ll begin by describing the exact match search, where the application supplies a 256 bit key and the DRT engine locates the node publishing that key. This type of search uses two phases: endpoint determination and key authentication.

During endpoint determination, the resolving node attempts to determine the IPv6 address of the machine publishing the target key. The resolving node communicates with other nodes participating in the DRT, each of which attempts to provide the resolver with the IP address of a node publishing a key numerically close to the target. Each node maintains a structured cache of IP addresses and keys published by other nodes in the cloud, and takes special measures to learn about many nodes publishing keys numerically close to its own.

In the second phase of the lookup, key authentication, the resolving node authenticates the key found in phase one. The security provider on the publishing node’s machine generates a blob of data that can be used to prove ownership of the key. This might be a credential, like a certificate chain. This blob is passed from the publisher to the resolver by the DRT protocol. The security provider on the resolving node’s machine receives the blob, parses it and verifies that the publishing node is indeed authorized to publish the target key.

In addition to the exact match search, the DRT supports nearest match searches, where the DRT protocol locates the nearest N nodes to a target key, and a range search, where the DRT protocol locates N nodes publishing keys within a range of values.

All applications that use PNRP on the internet, participate in one, large peer-to-peer system. With the DRT, application developers can define their own distinct peer-to-peer clouds. The DRT requires the application developer to provide a bootstrap module during initialization time. This bootstrap module is responsible for retrieving the IP addresses of some nodes already active in the DRT system. The bootstrap module might contact a server, or use another protocol like SSDP or PNRP.

Over the next few weeks, we’ll follow up with more posts, diving into the various aspects of the DRT in more detail. In the mean time, feel free to contact me with any questions. tylbart@microsoft.com.

Have fun!

Tyler