Introduction Kad

Latest revision as of 19:11, 10 April 2010

The Kad network, short for Kademilia is a a peer-to-peer network which implements the Kademlia P2P overlay protocol. The majority of users on the Kad network are also connected to servers on the eDonkey network, and Kad Network clients typically query known nodes on the eDonkey network in order to find an initial node on the Kad network.

Overview

The Kad network uses UDP to

• find sources for ed2k hashes
• search for ed2k hashes based on keywords in the file name
• find comments and ratings on files (hashes)
• provide buddy services for firewalled (low ID) nodes
• store locations, comments and (keywords out of) filenames

Note that Kad is not used to actually transfer the file in the ed2k network.

Kad GUI

There is a Kad screen in the official client. This is mainly used for debug purposes. All a user can see is that the peers turn from yellow (unknown) to green (4 successful connects). If all peers in Kad go red(ish) something is likely worng with the UDP communication.

Bootstrap

You need to know first some clients to get into the network. This can be down by downloading a nodes.dat files or (simpler) starting a download via the servers and then boostrap Kad with the clients found there.

The Kad ID is stored in preferencesKad.dat on first Kad startup.

Search

Kad uses the hash of the first word you look for as key where to look in the Kad network. So in general ii is better to look for "Moviename the" than "the Moviename".

Internal working

All lookups and searches are done form the local client. No searches are offloaded to other clients.

All lookups are key/value lookup. -Sources (key=hash of file, value = location of source... KeyID, SourceID, then the data. Sources use IP & port.. ) -Namesearch (key=hash of first keywokrd, value = full filename)

You get a contact. You take his ID and XOR it with your ID. This creates a 128 bit "distance". Lets assume that the tree is level 0 with 10 contacts (bin is full) and we add this new contact. We then split this level 0 tree with 1 bin into a level 1 tree with two bins. All the contacts that started with a "1" goes the the left bin and all the contacts with a "0" goes the the right bin. Let's say the left bin fills up and needs to split. We now have a skewed level 2 tree with 3 bins. All the contacts with the second bit set to "1" goes to the left bin and the ones with "0" go to the right bin. Therefore, the left most contacts in the tree are farthest from you and the right most contacts are closest to you. The right side of the tree will fill up a lot faster because these people are more aware of your presence.

External links

• Distributed hash table
• Kademlia: A Peer-to-peer Information System based on the XOR Metric (PDF)
• [1] Kad forum topic