The following notes (entirely preliminary, subject to change without notice, with absolutely NO GUARANTEE etc.) were written as part of the development of KadC, a C library that will eventually allows the calling application to access an existing Kademlia-based overlay network to publish and retrieve <key, data> pairs. Using an established overlay network eliminates critical-mass issues from day one. These notes are hereby placed in the public domain, in the hope of helping the development of interoperable software.

At present there are three Kademlia-based overlay networks: Overnet (closed source, protocol undocumented but partially reverse-engineered by mldonkey and others); eMule-KAD, part of the opensource filesharing application eMule 0.4x; and RevConnect-KAD, part of the opensource filesharing application RevConnect and obtained by modifying eMule-KAD's code. 

All three implementations use a network protocol based on UDP packets addressed to a single port, which however is not fixed in advance (or "well known"). 

Each UDP packet starts with one byte called ID which identifies the Kademlia "flavour": Overnet uses 0x0E3, eMule-KAD uses 0xE4 and 0xE5 (the latter for compressed packets) and RevConnect 0xD0 and 0xD1 (same). Compressed packets have the third and following bytes zlib-compressed.
The flavour byte is followed by another byte called "opcode" defining the content of the rest of the payload (parameters); some opcodes define "requests", and others "replies". Some opcodes are not followed by any parameter; a particular request always elicits a well-defined set of possible responses.

****** Sessions between peers

Each data exchange is based on short "sessions" between pairs of peers, with an "initiator" initiating the session with exactly one "request" packet, and a "responder" sending back one or more "response" packets. The session may also be aborted for timeout if the expected response does not arrive within a few seconds. From each peer's standpoint, a session is solely identified by the peer's <flavour, IP_address, port_number> triple (Session ID); the protocol does not have anything conceptually similar to RTP's SSRC to assist in identifying packets belonging to the same session. By embedding in the Session ID also the information about who the initiator was, it is possible to hold, concurrently , up to two independent sessions between each pair of peers. A typical case is the overlapping in eMuleKAD between a KADEMLIA_FIREWALLED_REQ and a KADEMLIA_BOOTSTRAP_REQ initiated by the corresponding peer before the completion of the first session: 

1 = Session initiated by A, 2 = Session initiated by B

1	KADEMLIA_FIREWALLED_REQ	 -1->
1   +.......................<-1- KADEMLIA_FIREWALLED_RES
1  	.							  (tries to open TCP connection)
1  	.							  (if OK:) 
1 2`.```````````````````````<-2- KADEMLIA_BOOTSTRAP_REQ
1 2.........................<-1- KADEMLIA_FIREWALLED_ACK
  2```KADEMLIA_BOOTSTRAP_RES -2->

In Overnet flavour, the overlapping is slightly different:

1 = Session initiated by A, 2 = Session initiated by B

1	OVERNET_IP_QUERY (REQ)	 -1->
1   +.......................<-1- OVERNET_IP_QUERY_ANSWER
1 	.							  (tries to open TCP connection)
1 	.							  (if OK, and not always:) 
1 2`.```````````````````````<-2- OVERNET_IDENTIFY (REQ)
1 2 . OVERNET_IDENTIFY_REPLY -2->
1 2 . ``````````````````````<-2- OVERNET_IDENTIFY_ACK (w/ tcp port)
1   ........................<-1- OVERNET_IP_QUERY_END

To capture the protocol's logic, KadC uses "session objects" which track the session state. A session object (SO) is created when a session is started, and destroyed when the session terminates (at least, according to KadC's opinion), and contains as fields (among others):

- Kademlia flavour, peer's IP address and UDP port number, and a "isServerSession" flag (collectively, the "Session ID")
- a (pointer to) a FIFO queue object
- a Pthreads mutex, to ensure atomicity of modifications of the SO
- a pthread_t object (see below)
- a pointer to a session service routine
 
Session objects come in two types: "Client Session Objects" (CSO's) and "Server Session Objects" (SSO's). Of course, the "isServerSession" flag is used to differentiate them.  

CSO's are created by the calling application to start a Client Session, calling newSession(KF, peerIP, peerport); this call returns a pointer to a newly-minted SO, and allocates a FIFO from which the caller's code will be able to read incoming UDP packets relative to that session. Replies will be sent by calling a routine performing a blocking sendto on the same UDP socket (sendbuf() and its derivatives). The pthread_t object and the pointer to a session service routine are unused in Client Sessions.

SSO's, on the other hand, are automatically created when KadC receives UDP packets with a <flavour, IP_address, port_number> triple that does not correspond to an existing server session. If the flavour is supported, AND if the opcode corresponds to one in the "REQuests group", an SO is allocated and a thread started to run the Session Service Routine (SSR); the incoming packet is also deposited in the FIFO queue that the SSR will use for UDP input. 

If the <flavour, IP_address, port_number> triple corresponds to an already existing SSO, the only action taken is to deposit the UDP payload in the SSO's input FIFO queue. Packets that are not in the "REQuests group" and arrive without an open client session are simply discarded.

The calling thread (for client sessions) or the SSR (for server sessions) are responsible for detecting end-of-session conditions (either normal completion, or timeout on input) and deallocate the Session Object. This is largely handled behind the scenes by lower-level routines.

****** The Overnet protocol 

The "publishing" process is the single operation used to inject data in the DHT; conversely. "searching" is the retrieval of such data from the DHT. A logical record for publishing is made of two parts, sequentially stored in a contiguous piece of memory (henceforth called "k-object"): a 16-byte key, and a 16-byte piece of data followed by a composite "List of Meta Tags" data. Typically the key and the other 16-byte data are the MD4 hashes of something (e.g., the file whose name is referenced in the List of Meta Tags) but this is not _syntactically_ required.

A List of Meta Tags is a collection of Meta Tags, each of which is a <name, value> pair. The name may be an arbitrary nstring (see below), or a 3-byte nstring of length 1, i.e. the size indicator 01 00  followed by a "special tag" with a semantic value preassigned in the eDonkey/eMule world (filename, filesize, filetype, fileformat etc.). The value of a meta tag may be an nstring, or, in some cases (filesize, bitrate, availability) a 4-byte unsigned long. (eDonkey has other types like float, and still others undocumented like blob, but they don't seem to be used in Overnet). People familiar with BitTorrent will recognize here the basic types of metadata that in BT are called "dictionaries" and "integers". A k-object is just a binary encoding of a list made of two hashes and a variable number of dictionaries and integers. The equivalent of BT "strings" never occurs, because here keywords are NEVER used as metadata in k-object; instead, they are MD4-hashed, and their hashes are used as indices (for more about it, see below).

Note: "nstring" here is defined as a sequence of bytes in ASCII encoding, prefixed by an unsigned short int in little-endian format representing the length of the string (number of bytes that follow the unsigned short itself). For example, "abc" is encoded as the nstring: 0x03, 0x00, 'a', 'b', 'c' . 
The list of meta tags is prefixed by an unsigned long int in little-endian format indicating the number of meta tags that follow. Summarizing, the structure of a k-object is: key-hash[16], related-hash[16], number-of-metatags[4], meta1, meta2, ... metaN.

A peer receiving a PUBLISH request is supposed to obey and store the k-object in a local database indexed by its key-hash (the first of the two hashes); it is responsibility of the peer issuing the "PUBLISH" request to find the most suitable peers where that piece of data should be stored. This is done with a recursive procedure based on Kademlia's "node lookup" primitive, which in Overnet is implemented through a sequence of "OVERNET_SEARCH / OVERNET_SEARCH_NEXT" sessions.
NOTE: from the behaviour presented by other clients, it appears that the local store (and therefore the DHT) handles re-publishingin the following way:
duplicate keys (i.e., occurrences of different records with a same first hash) are allowed, AS LONG AS the second hash is different. If the second hash is also the same, the previously stored record is deleted before entering th enew record. The list of metatags is irrelevant in this regard.

****** The publishing process

It's important to remember that Overnet is not a general-purpose Kademlia overlay network: it's one specialized to publish information about the location to download files defined by particular attributes (hash of the file content, filename or parts thereof (i.e. keywords), filesize, filetype (audio, video, program, document...), fileformat (mp3, zip etc.) etc. In order to accomodate this requirement, publishing is structured as a two-step process:

1. Metadata search: First a set of strings ("keywords") is obtained from the filename by converting it to lowercase, replacing all non-alphanumerics to blanks, and breaking the string into substrings at blanks boundaries. Then, the MD4 hash of the first few (?) keywords is computed, and, for each of those hashes used as keys, a k-object containing the key hash, the MD4 hash of the file content and the set of meta-tags describing complete filename, type, format, size and possibly other attributes (bitrate, playying time ("length") etc.)  is stored in the distributed directory through recursive OVERNET_SEARCH (actually node lookups) followed by OVERNET_PUBLISH requests. As said before, the keywords themselves are NOT stored in the metatags or elsewhere in the k-objects sent with OVERNET_PUBLISH_REQUESTs: only their hashes are used as keys (a copy of which is also at the beginning of the k-object, as said before). The metatags used in this phase only contain file attributes (complete filename, filelength, fileformat, filetype etc.) that appear to be a subset of the ones used by the traditional eDonkey protocol.

2. Sources search: Separately, using the hash of the file content as key, the hash of the peer containing the file (which normally is the same peer sending the OVERNET_PUBLISH request), plus a single metatag with name "loc", is stored in the distributed directory, again with a recursive OVERNET_SEARCH followed by an OVERNET_PUBLISH. The value of of that "loc" metetag is a URI which may take two forms:
2.1. bcp://ip_addr:port  . In this case, ip_addr is the address of the machine containing the file and port is the TCP port for an edonkey connection to download it.
2.2. bcp://hash:ip_addr:port . In this case, hash is the node ID of the machine containing the file, ip_addr is still its address, but its TCP port is not accessible because the machine is firewalled/NATted, and "port" represents instead its Overnet UDP port number. The download may still proceed _if_ the downloader is NOT firewalled: in that case, it has to send to ip_addr:port a OVERNET_FIREWALL_CONNECTION packet containing its own TCP port; the target host will then try to "call back" by opening a TCP connection to the downloading peer: if successful, it will send back a OVERNET_FIREWALL_CONNECTION_ACK packet to instruct the downloader to send the download request through the newly-established connection. Otherwise, it will send a OVERNET_FIREWALL_CONNECTION_NACK to close the session. Note: the hash in the URI is the same as the second hash in the OVERNET_PUBLISH request that contains it (node ID of the peer hosting the file).
In any case, the purpose of the "loc" URI is to point to the node containing a shared file, and give indications about how to connect to it to initiate the download (normally, with the eDonkey protocol). For applications other than file sharing, this second phase may be replaced by something application-specific, or eliminated altogether.
  
Here are two examples of k-objects, formatted as C source code: 

unsigned char kob1[] = {
	0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
	0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,	/* index hash */
	0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
	0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,	/* related hash */
	3,0,0,0,	/* number of metatags in following list */

	EDONKEY_MTAG_STRING,	/* = 0x02: a string-valued metatag will follow */
	1,0,					/* its name has length 1 */
	EDONKEY_STAG_NAME,		/* = 0x01: means "filename" */
	16,0,					/* its value has length 16 */
	'M','y',' ','f','i','l','e','-','n','a','m','e','.','m','p','3', /* filename value */

	EDONKEY_MTAG_DWORD,		/* = 0x03: next tag is a DWORD (unsigned long int) */
	1,0,					/* its name has length 1 */
	EDONKEY_STAG_SIZE,		/* = 0x02: means "filesize" */
	0x80,0x0d,0,0,			/* its filesize is 0x0d80 = 3456 bytes */

	EDONKEY_MTAG_STRING,	/* = 0x02: a string-valued metatag will follow */
	1,0,					/* its name has length 1 */
	EDONKEY_STAG_TYPE,		/* = 0x03: means "type" */
	5,0,
	'a','u','d','i','o'	/* type value */
};

unsigned char kob2[] = {
	0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
	0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,	/* index hash */
	0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
	0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,	/* related hash */
	4,0,0,0,	/* number of metatags in following list */

	EDONKEY_MTAG_DWORD,		/* next tag is a DWORD (unsigned long int) */
	1,0,					/* its name has length 1 */
	EDONKEY_STAG_SIZE,		/* = 0x03: means "filesize" */
	0x00,0x08, 0x00, 0x00,	/* its filesize is 0x800 = 2048 bytes */

	EDONKEY_MTAG_STRING,	/* = 0x02: a string-valued metatag will follow */
	1,0,					/* its name has length 1 */
	EDONKEY_STAG_NAME,		/* = 0x01: means "filename" */
	12,0,					/* its value has length 12 */
	'f','i','l','e','n','a','m','e','.','t','x','t', /* filename value */

	EDONKEY_MTAG_STRING,	/* = 0x02: a string-valued metatag will follow */
	1,0,					/* its name has length 1 */
	EDONKEY_STAG_TYPE,		/* = 0x03: means "type" */
	3,0,					/* its value has length 3 */
	'd','o','c',			/* type value */

	EDONKEY_MTAG_STRING,	/* = 0x02: a string-valued metatag will follow */
	1,0,					/* its name has length 1 */
	EDONKEY_STAG_FORMAT,		/* = 0x04: means "format" */
	3,0,
	't','x','t'				/* format value */
};


****** The Searching process

1. Keyword search

A Keyword is a string containing only lowercase alphanumeric characters, extracted from a metavalue of type EDONKEY_MTAG_STRING as described in the "Publishing" section (but for publishing, only keywords extracted from the title are hashed and used as indexes!). In filesharing applications keywords are hashed and used as indexes of metadata, so a search will have to mention at least a keyword.

Entering "s paolo conte" results in OvernetClc issuing OVERNET_SEARCHes of type 2 (OVERNET_FIND_VALUE) for the hash 71c5f2429376fc10bfbbff69ec63a29e (the MD4 of the string "paolo" forced to lowercase, whereas the string "conte" has hash f7ed195b79fc5504bf3b08ecfda3d8b2), to which each peer always replies with "OVERNET_SEARCH_NEXT" containing a list of better peers. When such list contains the replying peer itself, the initiator issues to it a "OVERNET_SEARCH_INFO" of type 0 (without a search tree, just the same hash of the string) or, in alternative, a "OVERNET_SEARCH_INFO" of type 1 (with a search tree restricting the search: NOTE: Ethereal 0.10.4 won't decode these correctly!). The host then sends back one or more OVERNET_SEARCH_RESULT containing: 
- string hash, 
- hash of the filename to which the following information refers, 
- a meta-tag list defining the characteristics of the file (name, size, content[audio...], format[mp3], artist, album, bitrate, availability. 
Finally, it sends a "OVERNET_SEARCH_END" with the same hash, to announce that no more OVERNET_SEARCH_RESULTs will arrive for it (this effectively closes the session opened by the OVERNET_SEARCH_INFO request).
The last two unsigned shorts in that packet (after the hash) represent repectively the number of "OVERNET_SEARCH_RESULT" packets sent and, maybe, the ones available(?) if the MAX parameter in OVERNET_SEARCH_INFO had not limited them to MAX-1 (THIS IS HYPOTHETICAL). An extended search could consider relaxing that limit.

2. Sources search

Once the user decides to download a given file, the peer acting as client starts a new round of OVERNET_SEARCHes type 2 for the hash of the _file content_; on peers returning themselves in the list of "better peers" in OVERNET_SEARCH_NEXT, it sends, as usual, OVERNET_SEARCH_INFO (type 0, i.e. without search tree) packets for the same hash, and this time the OVERNET_SEARCH_RESULT replies will return k-object with a tag list made of a single meta tag of type 02 (EDONKEY_MTAG_STRING), name "loc", and value "bcp://ipaddr:port" or "bcp://filehash:ipaddr:port" depending on whether or not it's firewalled (see the section "The publishing process" above).

So, if client looks for "Paolo Conte":

>>> OVERNET_SEARCH(MD4(paolo)) >>>
<<< OVERNET_SEARCH_NEXT(list of suggested peers)

and, to peers suggesting themselves:

>>> OVERNET_SEARCH_INFO(MD4(paolo), srchfilter('conte'), 0, 100) >>>
<<< OVERNET_SEARCH_RESULT(MD4(paolo), MD4(file1), MetaTagList(attr(file1))) <<<