1. Approaches Please notice: in this section + = pro, - = con There are five approaches when performing searches in p2p networks. 1.1. Distributed Hash Tables (DHT) +fast routing (aka searching) +scalable (10^9 users, 10^14 data items) +robust +little network traffic -own resources are mapped into the network -keyword/fuzzy search not possible yet -hotspots -DHTs require O(log n) hops to reach arbitrary destinations, assuming that each node maintains information about O(log n) nodes -Of couse, there is the possibility to route in constant times, but it requires that *each** node maintains information about all the nodes in the network. Therefore , practically, this method impossible -Example systems: Chord, CAN, Kademlia, Pastry, Tapestry *Update* -Viceroy system achieves O(log n) hops with only O(1) neighbors -Isn't yet clear whether these improvements will interfere with the robustness -More on this later... 1.2. Small World Networks (SWN) +fast routing (aka searching) +quite scalable, however not as scalable as DHTs +robust +own resources are not mapped into the network +medium network traffic -keyword/fuzzy search not possible yet -hotspots -SWNs require O(log^2 n) hops to reach arbitrary destinations, assuming (*only and only if* !!!) that links between nodes are constructed in the way that they are uniformly distributed over all distances in the network (Kleinberg) -Example systems: SWAN, Freenet 1.3. Flooding Broadcast Networks (FBN) +own resources are not mapped into the network +keyword/fuzzy search possible -not scalable -huge network traffic -not fast routing (in fact, there is no upper limit, because there are multiple simultaneous breadh-first searches in the network) -no guarantee that all data will be located -Example systems: Gnutella, Fastrack family (Kazaa, Morpheus), JXTA Search, Gnutella2 1.4. Hybrid systems (HS) (-text missing) 1.5 Social Discovery Systems (SDS) (-text missing) 1.6. Summary Insert/Delete Space Search Chord: O(log^2 n) O(nlog n) O(log n) CAN: O(r) O(nr) O((r/4)n^(1/r)), where r is the number of dimensions used in a virtual space Pastry: O(log^2 n) O(nlog n) O(log n) Tapestry: O(log^2 n) O(nlog n) O(log n) Kademlia: N/A O(log n) O(log n) Viceroy: N/A 7 O(log n) Small Worlds: N/A O(1) O(log^2 n) Flooding: N/A N/A No limit! Hybrid: N/A N/A N/A Social: N/A N/A N/A *I will try fill in N/As as quickly as possible!* Insert/Delete: Number of messages when a node joins or leaves the network. Space: How many neighbour nodes each node maintains in routing table. Search: Number of messages when an object lookup is performed 2. Thesis research problems 2.1 "Searching for a specific Storm block" 2.1.1 Facts -specific Storm block can be identified with an ID, generated by SHA-1 algorithm -block ID is globally *unique*, e.g. "Front page of New York Times newspaper on 10.10.2002" -each Storm node can host multiple blocks 2.1.2. Objectives -if block exists in the network, algorithm *will* find it -algorithm will find the specific Storm block as quicly as possible (and return it to the user) based on the the block's ID -simple pseudo thinking: "based on block ID, find the specific block fast and return it." 2.1.3. Existing approaches and this specific research problem a) DHT -natural choice, since in DHTs are based on key-value associations -in our case, keys are block IDs (SHA-1) -if exists in the network, specific block will be located based on block ID -Efficient, O(log n) in existing DHT systems -approach specific pseudo thinking: "based on block's ID, go to the node, whose ID is the nearest to block's ID in key space" b) SWN -natural choice, however depends on how system in implemented -In SWAN, every block has unique keys (identities) -in our case, keys are block IDs (SHA-1) -keys are spreaded out in euclidean space, and distances between blocks are calculated normal euclidean methods -quite effiecient, O(log^2 n) in existing SWN systems -approach specific pseudo thinking in SWAN: "based on block's ID, go to the node, whose (euclidean) distance is closest to block's ID in identity space" c) FBN -In this case, there is no benefit from the block's ID at all -not very efficient, since every Storm node has to "ask" every neighbor node it has the specific block ID -there is no guarantee that block will be found in the network -obviously a lot of extra traffic arises in the network -approach specific pseudo thinking: "ask repeating from each node if it has block, whose ID value is X" d) HS (-text missing) e) SDS (-text missing) 2.1.4. Open questions (-This case is quite straight forward, since it resembles very much ordinary "locate file and get it") -Really, how much better are the second generation FBN systems (Gnutella2) compared to the first generation FBN systems (Gnutella) -efficiency ? -netowork traffic ? -will the data will be located, if it exists in the network ? -scalability 2.2. "Searching for most recent Storm block associated with specific urn-5 name, where the block has been signed with a given key" 2.2.1. Facts -urn-5 is random "unique keyword", e.g. "Front page of New York Times newspaper" -urn-5 can be updated -urn-5 name is saved in the header of Storm block (|block urn-5: "Front page of New York Times newspaper"|) -key signings are saved in separate Storm blocks -finding key blocks for data block can be performed locally (in logarithmic time) -node has an internal index for key blocks and associated data blocks -for every urn-5 name, there is zero, one or more Storm blocks associated with it 2.2.2. Objectives -Find the specific (and the most recent) Storm block as quicly as possible (and return it to the user) based on the given urn-5 -simple pseudo thinking: "find all Storm blocks from the network, which uses specific urn-5 name. Compare blocks and return the most recent block, if the signing key is "valid"." 2.2.3. Existing approaches and this specific research problem -First, *all* blocks (with the specific urn-5 name) have to checked and analysed -In this case (urn-5), there is no benefit from the block's ID at all (DHT, SWN) 2.2.4. Open questions: -in this case, is it sensible to maintain two different key-value mappings key-value based systems (DHT, SWN) ? -one fore block IDs -one for urn-5 names, which are associated with block IDs -is this approach too difficult to maintain ? -is there possibility, in the specific urn-5 name, to maintain information about most recent block's ID for better search performance (or moreover, tree based structure for all blocks for specific urn-5 name) ? 2.3. "Searching for Storm blocks associated with specific urn-5 name, where specific date has been defined (or date range), and where Storm block has been signed with a given key" 2.3.1. Facts -in addition to section 2.2.1, in every block's header, there is a timestamp for date&time 2.3.2. Objectives -Find the specific (most recent) Storm block as quicly as possible (and return it to the user) based on the given urn-5 *and* a given date (range ?) -simple pseudo thinking: "find all Storm blocks from the network, which uses specific urn-5 name. Compare blocks and return the most recent block, if the signing key and block's timestamp are "valid"." 2.3.3. Existing approaches and this specific research problem -First, *all* blocks (with the specific urn-5 name) have to checked and analysed -In this case (urn-5), there is no benefit from the block's ID at all (DHT, SWN) 2.3.4 Open questions: -in this case, is it sensible to maintain two different key-value mappings key-value based systems ? -one mapping fore block IDs -one mapping for urn-5 names, which are associated with block IDs -is this approach too difficult to maintain ? -is there possibility, in the specific urn-5 name, to maintain information about most recent block's ID for better search performance (or moreover, tree based structure for all blocks for specific urn-5 name) ?