Last updated at 5:19 pm UTC on 3 March 2005
The formal name is 'unstructured overlay network'. Nodes know certain other nodes, and pass this information around on the network. The goal is to do this in such a way that the resulting network is stable, well-connected, and relatively immune to nasty things like partitioning.
We used research data to come to the implementation of network construction, which can be found in the AWGPeerList class. We select a random peer, and send it our list of known nodes (peer id and TCP location information, plus a number of hops); the peer responds with its list and proceeds to merge in our information. During the merge, lower-hop peers are preferred (the list is fixed-length, so if peers must be removed, it's the higher-hop peers). In the paper, this is the (rand, pushpull, head) strategy.
Of every peer, we keep both 'observed' and 'claimed' UDP information. The 'claimed' host and port are what the peer gets from the system; the 'observed' host and port is what a peer that received a packet from that peer observed to be the actual information. In case of a NAT environment (typical these days) these values will be different. The observed information is normally used to send UDP traffic to the peer; with the rule being 'full cone' NAT for UDP traffic, this means that if peer B observes an UDP host:socket for peer A, peer C can then use this same host:socket to send traffic to peer A.
To aid in bootstrapping, every peer periodically uploads its peer list to a (currently central) HTTP server. The server merges these lists and keeps the most 100 recent entries around. When a peer starts, it fetches the list, uses it to seed its peer list, and then it'll fire off a peer list exchange packet with every peer. This'll help to get the node into the network in a matter of seconds.