Peer-To-Peer SystemsIntroductionPeer-to-peer systemsP2P SystemsThree Generations of P2PIP vs. overlay routing for peer-to-peer applicationsCurious to know how GUID is generated?More on GUIDOverlay RoutingNapster: peer-to-peer file sharing with a centralized, replicated indexNapster (contd.)Impact of NapsterFreenet and GnutellaPeer-to-Peer MiddlewareRouting OverlayDistribution of information in a routing overlayBasic programming interface for a distributed hash table (DHT) as implemented by the PAST API over PastryBasic programming interface for distributed object location and routing (DOLR) as implemented by TapestryPastry & Tapestry RoutingFigure 10.7: First four rows of a Pastry routing tableFigure 10.8: Pastry routing example Based on Rowstron and Druschel [2001]Figure 10.9: Pastry’s routing algorithmFigure 10.10: Tapestry routing From [Zhao et al. 2004]SummaryPeer-To-Peer SystemsChapter 10B. Ramamurthy01/14/19B.RamamurthyPage 2Introduction•Monolithic application•Simple client-server•Multi-tier client-server•Request-response–Pull /Push mode–Tightly/loosely coupled•Centralized/distributed systems•Master-slave systems•Peer-to-peer systems•The concept of overlays01/14/19B.RamamurthyPage 3Peer-to-peer systems•Represents a paradigm for construction of distributed systems and applications in which data and computational resources are contributed by many hosts on the internet.•Key issues:–Placement of data objects among many hosts–Provision for accessing data that assures balanced workload and availability–Low overhead01/14/19B.RamamurthyPage 4P2P Systems•Exploit existing naming, routing, data replication, and security techniques to provide reliable resource sharing layer over an unreliable and untrusted collection of computers and networks.•They are more suitable for immutable data.•Fully decentralized and self-organizing.•Important issues are placement and delivery of data.01/14/19B.RamamurthyPage 5Three Generations of P2P•First generation is Napster music exchange server•Second generation: file sharing with greater scalability, anonymity, and fault tolerance–Freenet, Gnutella, Kazaa, BitTorrent•Third generation characterized by emergence of middleware for application independence–Pastry, Tapestry, …01/14/19B.RamamurthyPage 6IP vs. overlay routing for peer-to-peer applications IP Application-level routing overlay Scale IPv4 is limited to 232 addressable nodes. The IPv6 name space is much more generous (2128), but addresses in both versions are hierarchically structured and much of the space is pre-allocated according to administrative requirements. Peer-to-peer systems can address more objects. The GUID name space is very large and flat (>2 128), allowing it to be much more fully occupied. Load balancing Loads on routers are determined by network topology and associated traffic patterns. Object locations can be randomized and hence traffic patterns are divorced from the network topology. Network dynamics (addition/deletion of objects/nodes) IP routing tables are updated asynchronously on a best-efforts basis with time constants on the order of 1 hour. Routing tables can be updated synchronously or asynchronously with fractions of a second delays. Fault tolerance Redundancy is designed into the IP network by its managers, ensuring tolerance of a single router or network connectivity failure. n-fold replication is costly. Routes and object references can be replicated n-fold, ensuring tolerance of n failures of nodes or connections. Target identification Each IP address maps to exactly one target node. Messages can be routed to the nearest replica of a target object. Security and anonymity Addressing is only secure when all nodes are trusted. Anonymity for the owners of addresses is not achievable. Security can be achieved even in environments with limited trust. A limited degree of anonymity can be provided.01/14/19B.RamamurthyPage 7Determine the values for the UTC-based timestamp and clock sequence to be used in the UUID•For the purposes of this algorithm, consider the timestamp to be a 60-bit unsigned integer and the clock sequence to be a 14-bit unsigned integer. Sequentially number the bits in a field, starting with zero for the least significant bit.•Set the time_low field equal to the least significant 32 bits (bits zero through 31) of the timestamp in the same order of significance.•Set the time_mid field equal to bits 32 through 47 from the timestamp in the same order of significance. •Set the 12 least significant bits (bits zero through 11) of the time_hi_and_version field equal to bits 48 through 59 from the timestamp in the same order of significance.•Set the four most significant bits (bits 12 through 15) of the time_hi_and_version field to the 4-bit version number corresponding to the UUID version being created, as shown in the table above.•Set the clock_seq_low field to the eight least significant bits (bits zero through 7) of the clock sequence in the same order of significance. Curious to know how GUID is generated?01/14/19B.RamamurthyPage 8More on GUID•Are usually secure hash of attributes of the resource: so you don’t expect the state of the resource to change.•Hash of global clock + resource state + ip address + http://www.famkruithof.net/uuid/uuidgen•Remember N-fold replication possible, thus many replications of an object of a given GUID may be present.01/14/19B.RamamurthyPage 9Overlay Routing•It is different than IP routing however is strongly influenced by IP routing.•Routing tables may be updated synchronously or asynchronously.•N-fold replication affects the routing.01/14/19B.RamamurthyPage 10Napster: peer-to-peer file sharing with a centralized, replicated indexNapster serverIndex1. File location2. List of peersrequestoff ering the f ilepeers3. File request4. File deliv ered5. Index update Napster serverIndex01/14/19B.RamamurthyPage 11Napster (contd.)•Napster demonstrated the feasibility of building a useful large-scale service which depends wholly on individual computers.•Music files are not updated; state of resource stable•No guarantees about availability; it fit well for music filesImpact of Napster•First application in which a demand for globally-scalable information storage and retrieval storage emerged: downloading music files•Napster demonstrated the use of peer-peer system in sharing files•Several million users were registered at its peek•Involved