1.4 A home on the Internet — Ludovic Courtès — Peer-to-Peer Data Placement and Lookup
  • Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems [rowstron01:pastry]
    Antony Rowstron, Peter Druschel (Microsoft Research Ltd, Cambridge, UK; Rice University, Houston, Texas, USA), Proceedings of the 18th IFIP/ACM International Conference on Distributed Systems Platforms (Middleware 2001), November 2001

    This paper presents Pastry, a peer-to-peer routing substrate that routes to the numerically closes node in at most log2(N) hops. As in Chord, the (128 bit) node ID space is viewed as a circle. However, nodes not only store pointers to their neighbors plus fingers to nodes located further in the ID space: here, each node maintains the pointers to nodes numerically close to itself (the leaf set), a routing table where it keeps track of the nodes whose ID share a prefix of a given length with its own ID, and finally a neighborhood set that contains the list of nodes close to the current node according to the proximity metric. Each node's routing table entries are chosen to be close to the current node, according to the proximity metric. A section of the paper briefly addresses tolerance to malicious faults and to network partitions. Basically, the authors state that randomness could be added to the choice of the next node at each routing step so that eventually bad nodes will be avoided. This scheme, however, seems to assume that few nodes in the network will behave incorrectly. Network partitions could be tolerated by using IP multicast to discover disconnected networks and eventually re-integrating them into the current overlay network.

  • GAP - practical anonymous networking [bennett03:gap]
    Krista Bennett, Christian Grothoff (Department of Computer Sciences, University of Purdue, USA), Proceedings of the 3rd Workshop on Privacy Enhancing Technologies (PET 2003), March 2003

    This paper describes the GNUnet anonymity protocol (GAP), i.e. the routing protocol. GAP supports only two types of messages: requests (for a data block bennett04:gnunet-ecrs) and replies. The routing protocol is similar to mixes. Each node routes other nodes' packets (unless it is a request that can be answered by the node itself) and rewrites the source address of that packet. If a node also sends requests, an outside observer can only know that one of the messages sent by that node was actually initiated by that node. Therefore, the more packets a node routes, the more it can "hide" its own messages. Given that connections between every two node are ciphered and that nodes may delay for a random amount time messages that it routes, an outside observer cannot correlate the messages a node receives and the messages it sends. This actually requires that the node is at least connected with a node that is not under the adversary's control. Each node may tradeits own anonymity (not others') for improved overall routing efficiency by deciding not to rewrite the source address of every packet (Freenet does not provide this flexibility). As a consequence, routing may improve over time. Nodes that route replies may decide to store locally replies, hence improving data availability and (potentially) locality. Therefore, as data migrates and gets replicated, paths to a given piece of data change, making it harder to censor accesses to it. The main scalability problem of GAP is that each node must keep information about the origin of messages it routed on behalf of other nodes in order to be able to send them the reply. However, this problem is tempered by the fact that (i) under memory pressure and high network load, nodes have the option of not rewriting a message's source, and (ii) messages all have a time-to-live (TTL).

  • Making Gnutella-like P2P Systems Scalable [chawathe03:making]
    Yatin Chawathe, Sylvia Ratnasamy, Lee Breslau, Scott Shenker (AT&T Research; Intel Research; UC Berkeley, USA), Proceedings of ACM SIGCOMM 2003, 2003
  • An Overview of the Content-Addressable Network D2B [fraigniaud03:d2b]
    Pierre Fraigniaud, Philippe Gauron (Laboratoire de Recherche en Informatique, Universit? Paris-Sud, Orsay, France), January 2003
  • Survey of Locating & Routing in Peer-to-Peer Systems [harrell01:survey]
    Fox Harrell, Yuanfang Hu, Guilian Wang, Huaxia Xia (UCSD, USA), December 2001
  • A Scalable Content-Addressable Network [ratnasamy01:can]
    Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker (University of California, Berkeley, USA; AT&T Center for Internet Research at ICSI, Berkeley, USA), Proceedings of ACM SIGCOMM 2001, August 2001

    This paper deals with the algorithmic foundations of content-addressable networks and DHTs. Unlike in the CFS/Chord paper dabek01:cfs which considers a circle as the overlay network topology, Ratnasamy et al. generalize this design to a d-dimensional torus (for d=1, the torus is a circle). The torus forms a coordinate space that is dynamically partitioned among all nodes, where each node has 2.d neighbors. There exists a function that maps keys in the DHT to points in the space and each node is responsible for a "zone", i.e. a range of keys. Therefore, requests are routed towards the neighbor with coordinates closest to the destination. Each node entering the system randomly chooses a point within the coordinate space and sends a JOIN request to that point that is received by the occupant of the region where that point is. The occupant splits its zone into two and transfers the corresponding half of its key-value pairs to the new node; it then notifies its former neighbors about the topological change. Nodes periodically send update messages to their neighbors, containing their zone and neighbors; should one fail to do so for some time, it will be considered as unavailable and one of its neighbors will soon take over its zone. The authors then describe a number of improvements (mostly in terms of performance and fault-tolerance):

    • increasing the number of dimensions of the coordinate space increases fault-tolerance (each node has more neighbors) and decreases the routing path length;
    • using multiple coordinate spaces ("realities") reduces the path length and increases FT as well;
    • round-trip time (RTT) weighted routing reduces the per-hop latency by accounting for inter-neighbor latency (nodes can use the latency information in addition to their distance to the destination to choose among neighbors);
    • sharing a coordinate zone among several peers with redundancy improves fault-tolerance;
    • using multiple hash functions which I consider as close to using multiple hash tables, i.e. probably not the most elegant way to improve FT and performance;
    • using the latency information when building the network so that nodes physically close are closed in the coordinate space as well;
    • choosing the most loaded zone when partitioning a zone when a new node joins;
    • caching and replication.
    The paper contains interesting simulation results, no experimental results.

  • Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications [stoica04:chord]
    Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, Hari Balakrishnan (MIT Laboratory for Computer Science), appeared in IEEE/ACM Transactions on Networking, 2005?
  • When Multi-Hop Peer-to-Peer Lookup Matters [rodrigues04:multihop]
    Rodrigo Rodrigues, Charles Blake (MIT Computer Science and Artificial Intelligence Laboratory), 2004
  • Security Considerations for Peer-to-Peer Distributed Hash Tables [sit02:security]
    Emil Sit, Robert T. Morris (MIT Laboratory for Computer Science), Proceedings of the First International Workshop on Peer-to-Peer Systems (IPTPS '02), March 2002
  • Efficient Content Location Using Interest-Based Locality in Peer-to-Peer Systems [sripanidkulchi03:interest]
    Kunwadee Sripanidkulchai, Bruce Maggs, Hui Zhang (Carnegie Mellon University, Pittsburgh, USA), Proceedings of INFOCOMM 2003, 2003
(made with skribilo)