Efficient routing for peer-to-peer systems

This thesis examines the problem of locating and accessing an item stored in a large and volatile peer-to-peer system, and presents new ways of organizing items and peers to make this operation fast and efficient. Current structured peer-to-peer routing schemes keep routing information about only a small number of peers in the system, typically logarithmic in the size of the system. They do this under the assumption that it is infeasible to keep more routing information up-to-date since the system is highly volatile. As a result, when a node wants to locate an item, several peers have to be contacted in sequence before enough information is available to determine the location of the item. This makes routing a very long operation. In this thesis, we question this assumption and present two fast peer-to-peer routing algorithms. First, we present a "one hop" routing scheme. We show how to disseminate information about membership changes quickly enough so that peers maintain accurate routing tables with information about all peers in the system. Further, we demonstrate the feasibility of the system with analytical results and simulations. Second, we propose a "two hop" routing scheme for large scale systems of more than a few million peers, where the bandwidth requirements of one hop routing can become too large. This scheme keeps a fixed fraction of the total routing state on each peer, chosen such that the additional delay of routing is minimal.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2004

Author dc:creator

• Gupta, Anjali, 1980-

Advisor dc:contributor.advisor

• Barbara Liskov.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

en_US

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/28553

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/28553