{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/28553"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/28553","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Efficient routing for peer-to-peer systems","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Gupta, Anjali, 1980-"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.","school":null,"contributors":[],"advisors":["Barbara Liskov."],"committee_chairs":[],"committee_members":[],"year":2004,"date_issued":"2004","date_published":"2004","updated_at":"2026-07-22T22:22:24Z","subjects":["Electrical Engineering and Computer Science."],"languages":["en_US"],"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."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/28553","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Barbara Liskov."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Gupta, Anjali, 1980-"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2005-09-27T16:58:36Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2005-09-27T16:58:36Z"]},{"key":"dc:date.issued","label":"Date","values":["2004"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]},{"key":"dc:rights","label":"Dc Rights","values":["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."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/28553"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2004.","Includes bibliographical references (p. 51-55)."]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["S.M."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Efficient routing for peer-to-peer systems"]}]}],"canonical_facts":{"dc:contributor.advisor":["Barbara Liskov."],"dc:contributor.department":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:contributor.other":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:creator":["Gupta, Anjali, 1980-"],"dc:date.accessioned":["2005-09-27T16:58:36Z"],"dc:date.available":["2005-09-27T16:58:36Z"],"dc:date.issued":["2004"],"dc:description":["Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2004.","Includes bibliographical references (p. 51-55)."],"dc:description.abstract":["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."],"dc:description.degree":["S.M."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["http://hdl.handle.net/1721.1/28553"],"dc:language.iso":["en_US"],"dc:publisher":["Massachusetts Institute of Technology"],"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."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["Efficient routing for peer-to-peer systems"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:22:24Z"}