Dropbox Exhibit 1012 - Page 1
`Dropbox, Inc. v. Entangled Media, LLC
`IPR2024-00285 - U.S. Patent No. 8,484,260
`
`

`

`Lecture Notes in Computer Science
`Commenced Publication in 1973
`Founding and Former Series Editors:
`Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen
`
`3485
`
`Editorial Board
`
`David Hutchison
`Lancaster University, UK
`Takeo Kanade
`Carnegie Mellon University, Pittsburgh, PA, USA
`Josef Kittler
`University of Surrey, Guildford, UK
`Jon M. Kleinberg
`Cornell University, Ithaca, NY, USA
`Friedemann Mattern
`ETH Zurich, Switzerland
`John C. Mitchell
`Stanford University, CA, USA
`Moni Naor
`Weizmann Institute of Science, Rehovot, Israel
`Oscar Nierstrasz
`University of Bern, Switzerland
`C. Pandu Rangan
`Indian Institute of Technology, Madras, India
`Bernhard Steffen
`University of Dortmund, Germany
`Madhu Sudan
`Massachusetts Institute of Technology, MA, USA
`Demetri Terzopoulos
`New York University, NY, USA
`Doug Tygar
`University of California, Berkeley, CA, USA
`Moshe Y. Vardi
`Rice University, Houston, TX, USA
`Gerhard Weikum
`Max-Planck Institute of Computer Science, Saarbruecken, Germany
`
`Dropbox Exhibit 1012 - Page 2
`Dropbox, Inc. v. Entangled Media, LLC
`IPR2024-00285 - U.S. Patent No. 8,484,260
`
`

`

`Ralf Steinmetz Klaus Wehrle (Eds.)
`
`Peer-to-Peer Systems
`and Applications
`
`1 3
`
`Dropbox Exhibit 1012 - Page 3
`Dropbox, Inc. v. Entangled Media, LLC
`IPR2024-00285 - U.S. Patent No. 8,484,260
`
`

`

`Volume Editors
`
`Ralf Steinmetz
`TU Darmstadt
`KOM - Multimedia Communications Lab
`Merckstr. 25, 64283 Darmstadt, Germany
`E-mail: Ralf.Steinmetz@kom.tu-darmstadt.de
`
`Klaus Wehrle
`Universität Tübingen
`Protocol-Engineering and Distributed Systems Group
`Morgenstelle 10 c, 72076 Tübingen, Germany
`E-mail: Klaus.Wehrle@uni-tuebingen.de
`
`Library of Congress Control Number: 2005932758
`
`CR Subject Classification (1998): C.2, H.3, H.4, C.2.4, D.4, F.2.2, E.1, D.2
`
`ISSN
`ISBN-10
`ISBN-13
`
`0302-9743
`3-540-29192-X Springer Berlin Heidelberg New York
`978-3-540-29192-3 Springer Berlin Heidelberg New York
`
`This work is subject to copyright. All rights are reserved, whether the whole or part of the material is
`concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting,
`reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication
`or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965,
`in its current version, and permission for use must always be obtained from Springer. Violations are liable
`to prosecution under the German Copyright Law.
`
`Springer is a part of Springer Science+Business Media
`
`springeronline.com
`
`© Springer-Verlag Berlin Heidelberg 2005
`Printed in Germany
`
`Typesetting: Camera-ready by author, data conversion by Boller Mediendesign
`Printed on acid-free paper
`SPIN: 11530657
`06/3142
`5 4 3 2 1 0
`
`Dropbox Exhibit 1012 - Page 4
`Dropbox, Inc. v. Entangled Media, LLC
`IPR2024-00285 - U.S. Patent No. 8,484,260
`
`

`

`5. First and Second Generation of Peer-to-Peer
`Systems
`
`J¨org Ebersp¨acher, R¨udiger Schollmeier
`(Munich University of Technology)
`
`5.1 General Characteristics of Early Peer-to-Peer
`Systems
`
`Peer-to-Peer (P2P) networks appeared roughly around the year 2000 when a
`broadband Internet infrastructure (even at the network edge) became widely
`available. Other than traditional networks Peer-to-Peer networks do not rely
`on a specific infrastructure offering transport services. Instead they form
`“overlay structures” focusing on content allocation and distribution based
`on TCP or HTTP connections. Whereas in a standard Client-Server con-
`figuration content is stored and provided only via some central server(s),
`Peer-to-Peer networks are highly decentralized and locate a desired content
`at some participating peer and provide the corresponding IP address of that
`peer to the searching peer. The download of that content is then initiated
`using a separate connection, often using HTTP. Thus, the high load usually
`resulting for a central server and its surrounding network is avoided lead-
`ing to a more even distribution of load on the underlying physical network.
`On the other hand, such networks are typically subject to frequent changes
`because peers join and leave the network without any central control.
`While some legal aspects of Peer-to-Peer networks are still heavily con-
`tended between the entertainment industry and some user groups, we focus on
`the technical aspects of this approach. In the last years, several Peer-to-Peer
`technologies were developed. Figure 5.1 provides an overview of current Peer-
`to-Peer technologies and compares them to the conventional Client-Server
`model.
`As shown in Figure 5.1, in a Client-Server system the server is the only
`provider of service or content, e.g. a web server or a calendar server. The
`peers (clients) in this context only request content or service from the server,
`the IP address of which is assumed to be available to the peers. Content in
`this context may be an MP3-compressed audio file, the profile of a person a
`user wants to establish a call to or context information, e.g. where the next
`taxi can be found. The clients do not provide any service or content to run
`this system. Thus generally the clients are lower performance systems and
`the server is a high performance system. This does not exclude that a server
`may be set up as a server farm with one specified entry point for the clients,
`which redirects the clients to different computers to share the load.
`
`R. Steinmetz and K. Wehrle (Eds.): P2P Systems and Applications, LNCS 3485, pp. 35-56, 2005.
`© Springer-Verlag Berlin Heidelberg 2005
`
`Dropbox Exhibit 1012 - Page 5
`Dropbox, Inc. v. Entangled Media, LLC
`IPR2024-00285 - U.S. Patent No. 8,484,260
`
`

`

`36
`
`5. First and Second Generation of Peer-to-Peer Systems
`
`  @  / A  A E I  / A  A E  , 0 6  * =2  2 2 0 O > E  2 2+  J =  E   2 2   )    B K   B  2   2  E  ?  K @ @  )  O   E     E O ?   >    L @ M E D  K      B B K  ? E    E O!     ?     E E"  +    ? E    E   D  L  O   B E N @ ^- N  F   + D  @   + )   )    B K   B  2   2  E  ?  K @ @  )  O   E     E O ?   >    L @ M E D  K      B B K  ? E    E O!  @ O   E ?  ?    E E- N  F   /  K      $   : 6 )  )    B K   B  2   2  E  ?  K @ @  )  O   E     E O ?   >    L @ M E D  K      B B K  ? E    E O!     ?     E E- N  F   /  K      "  .   )    B K   B  2   2  E  ?  K @ @   +     E O  E  ? O   F  L E @  D  L E ? !  +     E O  E     E  @   B E  @ N  C  K F @ >- N  F    F 5 J H K ? J K H A I J H K ? J K H A   4  K ?   D @  > M   D  F  4  K ?  ?   >  ? ? @  @ E ?  O  B     D  F !  2  E  F  L E @   @  G K    5 L  ?   ? F   5 L  E  D  ?    E O   @     O F  L E @   B  L E ?  @  ?      M      C @ > O  D  5 L  5 L   D  D E C D F B    ?  O  !  +  E    D    M F B    ?  O - N  F   9 9 9 A A H  J   A A H+  E A J  5 A H L A H  @  / A  A E I  / A  A E  , 0 6  * =2  2 2 0 O > E  2 2+  J =  E   2 2   )    B K   B  2   2  E  ?  K @ @  )  O   E     E O ?   >    L @ M E D  K      B B K  ? E    E O!     ?     E E"  +    ? E    E   D  L  O   B E N @ ^- N  F   + D  @   + )   )    B K   B  2   2  E  ?  K @ @  )  O   E     E O ?   >    L @ M E D  K      B B K  ? E    E O!  @ O   E ?  ?    E E- N  F   /  K      $   : 6 )  )    B K   B  2   2  E  ?  K @ @  )  O   E     E O ?   >    L @ M E D  K      B B K  ? E    E O!     ?     E E- N  F   /  K      "  .   )    B K   B  2   2  E  ?  K @ @   +     E O  E  ? O   F  L E @  D  L E ? !  +     E O  E     E  @   B E  @ N  C  K F @ >- N  F    F 5 J H K ? J K H A I J H K ? J K H A   4  K ?   D @  > M   D  F  4  K ?  ?   >  ? ? @  @ E ?  O  B     D  F !  2  E  F  L E @   @  G K    5 L  ?   ? F   5 L  E  D  ?    E O   @     O F  L E @   B  L E ?  @  ?      M      C @ > O  D  5 L  5 L   D  D E C D F B    ?  O  !  +  E    D    M F B    ?  O - N  F   9 9 9 A A H  J   A A H+  E A J  5 A H L A H
`
`Fig. 5.1: Summary of the characteristic features of Client-Server and Peer-to-Peer
`networks
`
`In contrast, in Peer-to-Peer systems all resources, i.e. the shared content
`and services, are provided by the peers. Some central facility may still exist,
`e.g. to locate a given content. A peer in this context is simply an application
`running on a machine, which may be a personal computer, a handheld or a
`mobile phone. In contrast to a Client-Server network, we can generally not
`distinguish between a content requestor (client) and a content provider, as
`one application participating in the overlay in general offers content to other
`peers and requests content from other participants. This is often expressed
`by the term “Servent”, composed of the first syllable of the term Server and
`the second syllable of the term Client.
`Using this basic concept Figure 5.1 outlines various possibilities currently
`used. Peer-to-Peer networking started with the first generation centralized
`concept. In this case some central server is still available. However, contrary
`to the Client-Server approach this server only stores the IP addresses of
`peers where some content is available, thus greatly reducing the load of that
`server. However, the address of that server must be known to the peers in
`advance. This concept was widely used and became especially well known
`due to Napster, offering free music downloads by providing the addresses of
`peers sharing the desired content. This approach subsequently lost much of
`its importance due to legal issues.
`
`Dropbox Exhibit 1012 - Page 6
`Dropbox, Inc. v. Entangled Media, LLC
`IPR2024-00285 - U.S. Patent No. 8,484,260
`
`

`

`5.2 Centralized Peer-to-Peer Networks
`
`37
`
`As a replacement for that scheme decentrally organized schemes such as
`Gnutella 0.4 and Freenet became widely used. These schemes do not rely
`on any central facility (except possibly for some bootstrap server to ease
`joining such a network), but rely on flooding the desired content identifier
`over the network, thus reaching a large number of peers. Peers which share
`that content will then respond to the requesting peer which will subsequently
`initiate a separate download session.
`It is an important drawback of these schemes that they generate a po-
`tentially huge amount of signaling traffic by flooding the requests. In fact,
`that signaling traffic dominates the Internet traffic in some cases even today.
`To avoid that, schemes like Gnutella 0.6 or JXTA introduce a hierarchy by
`defining Superpeers, which store the content available at the connected peers
`together with their IP address. Thus the Superpeers are often able to answer
`incoming requests by immediately providing the respective IP address, so
`that on average less hops are required in the search process, thus reducing
`the signaling traffic.
`The above schemes are generally termed “Unstructured Peer-to-Peer”,
`because the content stored on a given node and its IP address are unrelated
`and do not follow any specific structure. Contrary to that also Peer-to-Peer
`approaches have been proposed which establish a link between the stored
`content and the IP address of a node. In the rightmost column of Figure 5.1
`such networks are termed “Structured Peer-to-Peer”. The link between a
`content identifier and the IP address is usually based on Distributed Hash
`Tables (DHT) (cf. Chapter 7). However, in a frequently changing network
`such an approach requires frequent redistribution of content. We therefore
`do not address this approach in more detail.
`
`5.2 Centralized Peer-to-Peer Networks
`
`5.2.1 Basic Characteristics
`
`As described above, centralized Peer-to-Peer networks are characterized by
`the fact that they rely on one central lookup server. The overlay topology
`of a centralized Peer-to-Peer network can therefore be described as a star
`network. Every peer is connected to the centralized lookup server, to which
`it can issue requests for content matching the keywords stated in the request.
`If the request can be resolved by the centralized lookup server, it returns
`the access coordinates of the peers (mostly IP-addresses and ports) offering
`content which is described with the same keywords as stated in the request.
`The content itself is then transmitted out of band, i.e. not via the signaling
`(overlay) network, but via an additional, mostly HTTP-based, connection.
`The most prominent example application, which is based on a central-
`ized Peer-to-Peer network, is Napster http://www.napster.com/what_is_
`napster.html. Napster is used for (free) file sharing between Internet users
`
`Dropbox Exhibit 1012 - Page 7
`Dropbox, Inc. v. Entangled Media, LLC
`IPR2024-00285 - U.S. Patent No. 8,484,260
`
`

`

`38
`
`5. First and Second Generation of Peer-to-Peer Systems
`
`and is considered as the starting point of Peer-to-Peer networks. Due to legal
`issues and the centralized responsibility Napster had to change its service to
`a legal file sharing service. The basic concept and architecture of the Napster
`file sharing system is still used by other applications, e.g. Audiogalaxy [38]
`or WinMX [625]. BitTorrent [127, 320] is a similar file sharing system, the
`major objective of which is to quickly replicate a single large file to a set of
`clients.
`As depicted in Figure 5.1 the Napster network can be characterized by its
`centralized topology. The file searching protocol uses a Client-Server model
`with a central index server. However the file transfer is done in a true Peer-
`to-Peer way. The file exchange occurs directly between the Napster hosts
`without passing the server.
`With Napster, no file can be found, if the central lookup table is not avail-
`able. Only the file retrieval and the storage are decentralized. Thus the server
`represents a bottleneck and a single point of failure. The computing power
`and storage capabilities of the central lookup facility must grow proportional
`to the number of users, which also affects the scalability of this approach.
`As every node wanting to log into the Napster network has to register at
`the central server, no keep alive signal or any electronic heart beat must be
`exchanged between the Napster server and the peer. The server acts compa-
`rable to a DNS server to guide each requesting peer to those peers, which host
`the demanded content. No additional application layer routing is necessary,
`as the server has a complete network view.
`Further on, if the content is shared by at least one participant, the con-
`tent can be found instantly with one lookup. Thus the content availability
`in a Napster network can only take the values zero or one. Zero, if the con-
`tent is not shared by any node, one if the content is shared by at least one
`node, assuming that the server and the peers work correctly. If the content
`is available more than once, only the replication rate, and thus in this case
`the download performance increases, but not the availability of content.
`
`5.2.2
`
`Signaling Characteristics
`
`The messages employed in Napster are fairly simple and easy to track, as
`they are transmitted as plain text messages. We describe in the following the
`basic messages used in Napster to announce and to search for content.
`Each message to/from the Napster server has the basic structure given
`in Figure 5.2. The first four bytes provide the <Length> parameter, which
`specifies the length of the payload of this message. The <Function> param-
`eter stated in the following four bytes, defines the message type, e.g. login
`or search, which are described in the following. The payload finally carries
`parameters necessary for the different messages, e.g. the keywords of a search
`message.
`
`Dropbox Exhibit 1012 - Page 8
`Dropbox, Inc. v. Entangled Media, LLC
`IPR2024-00285 - U.S. Patent No. 8,484,260
`
`

`

`5.2 Centralized Peer-to-Peer Networks
`
`39
`
`Fig. 5.2: Basic Napster message structure
`
`The blocks/parameters in the payload are separated by spaces. This
`makes the separation of the information provided in each incoming message
`possible, as most blocks have no fixed length. We divide the messages in two
`phases, the initialization and the file request. The <Function> parameter of
`each message is given in brackets, e.g. SEARCH (0xC8).
`Initialization
`A registered Napster host, acting as a client, sends to the Napster server a
`LOGIN (0x02) message to become a member of the overlay network. For user
`verification this message includes the nickname (<nick>) and <password> of
`the user who started the application. Further on this message also includes
`the port number (<port>) on which the peer listens for incoming data re-
`quests and information about the clients access data-rate (<Link Type>).
`The <Client-Info> parameter contains information about the version of the
`used software. On average a LOGIN-message is about 40 bytes long.
`
`Fig. 5.3: LOGIN (0x02) message
`
`After a successful login, the server sends a LOGIN ACK (0x03) (size: 20
`bytes) to the client. If the <nick> is registered, the email address given at
`registration time is returned.
`If the <nick> is not registered, a dummy value is returned. As soon as the
`peer is logged in, it sends one “CLIENT NOTIFICATION OF SHARED FILE”
`(0x64) message for every file it wants to share (see Figure 5.4). Thus routing
`is possible, as every client announces its shared objects to the Napster server.
`This message contains the filename (<Filename>) of the file, the MD5-hash
`value of the file <MD5> [519] and the size in byte of the file (<Size>). The
`MD5 (Message Digest 5) algorithm produces a 128-bit “fingerprint” of any
`file. It is extremely unlikely that two messages contain the same hash value.
`The MD5 algorithm is therefore intended to provide any user with the
`possibility to secure the origin of the shared file, even if parts of the file are
`provided by different Napster users. As specific parameters of the music file,
`this message additionally provides the bitrate (<Bitrate>), the sampling rate
`of the MP3 (<frequency>), and the playout time of a music file (<time>). The
`
`Dropbox Exhibit 1012 - Page 9
`Dropbox, Inc. v. Entangled Media, LLC
`IPR2024-00285 - U.S. Patent No. 8,484,260
`
`

`

`40
`
`5. First and Second Generation of Peer-to-Peer Systems
`
`bit rate represents the quality of the used coding and compression algorithm.
`The average size of this message is 74 bytes.
`
`Fig. 5.4: CLIENT NOTIFICATION OF SHARED FILE message (0x64)
`
`File Request
`To be able to download a file from the Napster network, peers which
`share the requested file have to be found. The format of a request is shown
`in Figure 5.5. Therefore the requesting peer sends a SEARCH (0xC8) message
`to the Napster server. To specify the search this message contains several
`parameters stating keywords describing the requested object (artistname and
`parts of the songname). Further on this message also specifies a filter, e.g. to
`state a certain quality of the requested file, like the bitrate and the sampling
`frequency of the requested file. The parameter <compare> can have the values
`“at least”, “at best” or “equal to”. Thus the requesting peer can choose the
`quality of the file and also the file size, which together with the link type
`(parameter <Link Type> e.g. a T1 connection) of the providing peer can
`strongly influence the download speed. The parameter <MAX RESULTS>
`finally states the maximum number of results the requesting peer wants the
`Napster server to return. The average size of such a message is 130 bytes.
`
`Fig. 5.5: SEARCH message (0xC8)
`
`Upon receiving a SEARCH message, the Napster server tries to match the
`parameters stated in the SEARCH message with the entries of its database,
`consisting of data previously received from other peers upon initialization
`(CLIENT NOTIFICATION OF SHARED FILE (0x64) messages). If the server
`can resolve the query, it answers with at least one RESPONSE (0xC9) con-
`taining information about shared files matching the previously stated criteria
`(see Figure 5.6). To provide the requesting peer with information about the
`available data and where it can be downloaded from, this message contains
`the full filename (<File-Name>) and the IP-address (<IP>) of the providing
`peer, so that the requesting peer can download the requested file directly
`via its HTTP-instance [365]. Further on the file size (<Size>), the playout
`time (<length>), the sample and the bitrate of the file are stated (<Freq>,
`<Bitrate>). To check the integrity of the file and to be able to download the
`
`Dropbox Exhibit 1012 - Page 10
`Dropbox, Inc. v. Entangled Media, LLC
`IPR2024-00285 - U.S. Patent No. 8,484,260
`
`

`

`5.2 Centralized Peer-to-Peer Networks
`
`41
`
`file from multiple sources the MD5 hash value of the shared file is also stated
`(<MD5>). The average size of such a message is 200 bytes.
`
`Fig. 5.6: RESPONSE message (0xC9)
`
`5.2.3 Discussion
`
`To summarize the details of the Napster protocol we provide as an exam-
`ple the message sequence chart for the communication between two Napster
`peers and the Napster server in Figure 5.7. Here the requesting peer (Req)
`first initializes at the Napster server. As mentioned above the requesting peer
`(Req) therefore sends a LOGIN message to the Napster server with a payload
`of 36 bytes, which equals to 0x24 bytes in hexadecimal notation. Upon re-
`ceiving the acknowledgement it announces its three shared objects to the
`Napster server. In this example we assume the same message lengths, given
`by the average message length stated above.
`Now the new peer is fully registered with the Napster network and can
`start a search. Therefore it sends a SEARCH message to the Napster server,
`including the search keywords describing the requested object. As the Nap-
`ster server in our example knows two possible peers which share the requested
`object, it answers with two RESPONSE messages. Thus the peer can now re-
`quest a download of the requested object from one of the providing peers
`with a HTTP-Get-request. In case of success, as assumed in this example,
`the providing peer responds to this request with an OK message, which in-
`cludes the requested file. In this figure we can clearly see, that besides the
`initialization traffic only few traffic is caused by this Peer-to-Peer network.
`The reason is that only one central lookup table is available and therefore no
`flooding is necessary to find the requested object. The Napster server thus
`works similar to a DNS-lookup server.
`If we assume a user, which shares 10 files and requests one comparatively
`popular file, which thus would result in 20 responses, we can compute the
`generated bytes to:
`1 · (login + login ack) + 10 · notif + 1 · search + 10· response =
`= 40 + 4 + 10 · 74 + 130 + 10 · 200 = 2914bytes
`If we further on assume an average session length of 10 minutes, we can
`compute the average necessary signaling data rate to 38.85 bits/s, which is
`very reasonable.
`
`(5.1)
`
`Dropbox Exhibit 1012 - Page 11
`Dropbox, Inc. v. Entangled Media, LLC
`IPR2024-00285 - U.S. Patent No. 8,484,260
`
`

`

`42
`
`5. First and Second Generation of Peer-to-Peer Systems
`
`Napster
`Peer (Req)
`
`Napster
`Server
`
`Napster
`Peer (Prov)
`
`Login: [0x24|0x02|…]
`
`Login Ack: [0x00|0x03|…]
`
`Notif: [0x46|0x64|…]
`
`Notif: [0x46|0x64|…]
`
`Notif: [0x46|0x64|…]
`
`Search: [0x7E|0xC8|…]
`
`Response: [0xC4|0xC9|…]
`
`Response: [0xC4|0xC9|…]
`
`HTTP: GET[Filename]
`
`OK[data]
`
`Fig. 5.7: Sample message sequence chart for one Napster server with one request-
`ing and one providing peer
`
`5.3 Pure Peer-to-Peer-Networks
`
`5.3.1 Basic Characteristics
`
`Pure Peer-to-Peer networks/protocols came up shortly after the introduction
`of Napster. Examples of these protocols are the Freenet protocol and the
`Gnutella 0.4 protocol [123, 126, 232] . To analyze the properties, possibilities
`and limitations of pure Peer-to-Peer networks, we describe the Gnutella 0.4
`protocol in this section. The Gnutella 0.4 network [126] consists of a large
`number of nodes which may be distributed throughout the world, without any
`central element. The overlay topology can be characterized by a node degree
`distribution as given by equation 5.2 [328]. With this truncated powerlaw dis-
`tribution, ranging from degree (d) one to a maximum degree of seven, we can
`describe the topology of a Gnutella 0.4 network and can generate networks
`graphs as given by Figure 5.8. Here we can observe that separated subcom-
`ponents may occur due to the random connection establishment. This is also
`expected to happen in real networks, although in this case the subcompo-
`nents are magnitudes larger, as also the total number of considered nodes is
`magnitudes larger.
`c · d
`−1.4, 0 < d ≤ 7
`0, in any other case
`
`(cid:2)
`
`p (d) =
`
`average : ¯d = 2.2
`var (d) = 1.63
`
`(cid:3)(cid:4)
`
`d
`
`(cid:5)−1
`
`p(d)
`c
`
`, with c =
`
`(5.2)
`
`Dropbox Exhibit 1012 - Page 12
`Dropbox, Inc. v. Entangled Media, LLC
`IPR2024-00285 - U.S. Patent No. 8,484,260
`
`

`

`5.3 Pure Peer-to-Peer-Networks
`
`43
`
`A node becomes part of the Gnutella network by establishing an average
`of 3 TCP-connections to other active Gnutella nodes, whose IP addresses it
`may receive from a bootstrap server [549]. New nodes, to which the node can
`connect if an active connection breaks, are explored by broadcasting PING
`messages in the virtual overlay network. These PING messages are also used
`as keep alive pattern and are broadcasted in regular time intervals.
`All messages are coded in plain text. This results in large message sizes
`of QUERY and especially QUERY-HIT messages, as they contain meta data
`about the queried objects. Similar to Napster, Gnutella uses MD5 hash keys
`[519] to identify objects explicitly. For routing Gnutella employs simple flood-
`ing of the request messages, i.e. QUERY and PING messages. Every new in-
`coming PING or QUERY, which has not been received before, is forwarded to
`all neighbors except the one it received the message from, if the Time-to-Live
`(TTL) value (default set to seven hops) is at least one. If a node receives
`the same message more than once, these messages are not further flooded.
`Response messages, like PONG or QUERY-HIT messages, are routed back on
`the same path the request message used, which is called backward routing.
`In Gnutella 0.4 the virtual Peer-to-Peer layer is not matched to the phys-
`ical layer, which leads to zigzag routes, as described in [550]. Only enhance-
`ments, as described by the approach of geo-sensitive Gnutella [550], provide
`means to adapt the virtual network to the physical network.
`
`Fig. 5.8: Sample graph of a simulated Gnutella 0.4 network (100 nodes)
`
`Dropbox Exhibit 1012 - Page 13
`Dropbox, Inc. v. Entangled Media, LLC
`IPR2024-00285 - U.S. Patent No. 8,484,260
`
`

`

`44
`
`5. First and Second Generation of Peer-to-Peer Systems
`
`5.3.2
`
`Signaling Characteristics
`
`The nodes communicate directly with each other without any central instance
`. However at the beginning, i.e. in a bootstrap phase, a central entity like a
`beacon server, from which IP addresses of active nodes can be retrieved,
`is necessary. If a node already participated in the network, it may also be
`able to enter the network by trying to connect to nodes, whose addresses it
`cached in a previous session. As soon as a new node knows the IP address
`and port of one active Gnutella node it first establishes a TCP connection
`to this node and then connects to this node by sending the ASCII encoded
`request string “GNUTELLA CONNECT/<protocol version string>\n\n” to it.
`If the participating peer accepts this connection request it must respond with
`a “GNUTELLA OK\n\n”.
`Gnutella mainly uses four messages as stated above. The messages are
`setup in a similar manner as in Napster. They consist of a general message
`header and the additional payload (see Figure 5.9). However since in Gnutella
`the messages are flooded through the overlay network, some additional pa-
`rameters are necessary beyond those used for Napster. The <Descriptor ID>
`is a 16-byte string uniquely identifying the message on the network. Thus cir-
`cles can be detected, i.e. every message which is received twice by a node is
`not forwarded any further. Simultaneously and backward routing of possible
`response messages is possible.
`Every node therefore has to store this ID and the IP address from which
`it received the message for a certain time. The <TTL> (Time-to-Live) value
`determines the number of hops a message is forwarded in the overlay network.
`This value is decreased by every node which received the message before the
`message is forwarded. When the TTL value reaches zero, the message is not
`forwarded any further, to avoid infinitely circulating messages. Generally a
`TTL value of seven is considered to be sufficient to reach a large fraction
`of the nodes participating in the overlay network. The <Hops>-value states
`the number of hops a message has already been forwarded and is therefore
`increased by one by every forwarding peer. It can be used to guarantee, that
`initially no larger value than seven has been used by a requesting peer, as
`T T L(0) = T T L(i) + Hops(i) ≤ 7
`
`(5.3)
`
`The <Payload length> parameter states the size of the message so that the
`next message in the incoming stream can clearly be identified.
`
`Fig. 5.9: Basic Gnutella message structure
`
`Dropbox Exhibit 1012 - Page 14
`Dropbox, Inc. v. Entangled Media, LLC
`IPR2024-00285 - U.S. Patent No. 8,484,260
`
`

`

`5.3 Pure Peer-to-Peer-Networks
`
`45
`
`However the most important field, which determines the payload is the
`<Payload-Descriptor> field. The messages we distinguish here are 0x00 for
`a PING, 0x01 for a PONG, 0x80 for a QUERY and 0x81 for a QUERYHIT
`message [126]. The network exploration message PING does not contain any
`payload, whereas in the payload of the PONG message in addition to the con-
`tact information (IP address+port) information about the amount of shared
`files is stated. To search for data, the QUERY message contains, besides the
`
`Fig. 5.10: PONG (0x01) payload structure
`
`parameter which states the requested minimum download speed, a null termi-
`nated search string containing the keywords separated by blanks, describing
`the requested object. The average size of this message is 78.4 bytes. If we
`now assume, that an average word has a length of eight characters plus one
`character for the blank, we can also compute the average number of words a
`user states as search criteria, as every character is described with one byte.
`For Gnutella this results in an average of 7.35 words per QUERY. Similar
`to the PING messages, the QUERY messages are flooded through the over-
`lay. As soon as one node receives a QUERY-message, it compares the search
`
`Fig. 5.11: QUERY (0x80) payload structure
`
`keywords to the keywords describing the locally shared content. In case of at
`least one hit, it sends back a QUERYHIT message which is routed back on the
`same way the QUERY message was distributed through the network (back-
`ward routing). A QUERYHIT message contains the information, as shown in
`Figure 5.12 and Figure 5.13. However in contrast to Napster one QUERYHIT
`message can contain in its result set more than only one file. The average size
`of one QUERYHIT message is 748.8 bytes, which is comparatively large.
`
`Fig. 5.12: QUERYHIT (0x81) payload structure
`
`Dropbox Exhibit 1012 - Page 15
`Dropbox, Inc. v. Entangled Media, LLC
`IPR2024-00285 - U.S. Patent No. 8,484,260
`
`

`

`46
`
`5. First and Second Generation of Peer-to-Peer Systems
`
`Fig. 5.13: Result set structure
`
`5.3.3 Discussion
`
`To summarize the basic signaling behavior of a Gnutella network we as-
`sume a sample Gnutella network, where node 1 just joined (see Figure 5.14).
`Therefore node 1 first sends a CONNECT message to the nodes 5, 2 and 3
`(see Figure 5.15). To explore its surrounding further on, node 1 also sends a
`PING message to its neighbors, which forward this message further and thus
`this message and its corresponding PONG messages propagate through the
`network, as shown in Figure 5.15.
`
`5
`
`6
`
`1
`
`8
`
`2
`
`3
`
`4
`
`7
`
`Fig. 5.14: Sample Gnutella 0.4 network
`
`In our example the flooding of the request messages results, as we can see
`from Figure 5.15, in 12 PING and 12 PONG messages, and 6 messages for the
`initial connection establishment. Taking the message sizes from above into
`account (PING: 23 byte, PONG: 37 byte) and assuming for a each connection
`(GnuCon+OK) message pair 34 byte, this results in a total of 462 bytes.
`T