Carnegie Mellon Searching Wrap-Up ype O(search) storage Fuzzy Central O(1) O(N) Yes Flood Super Structured
1 6 Searching Wrap-Up Type O(search) storage Fuzzy? Central O(1) O(N) Yes Flood Super Structured
Carnegie Mellon Query Flooding Join Must join a flooding network Usually, establish peering with a few existing nodes Publish: no need, just reply Search: ask neighbors, who ask their neighbors, and so on. When/if found reply to sender TTL limits propagation
1 7 Query Flooding • Join: Must join a flooding network – Usually, establish peering with a few existing nodes • Publish: no need, just reply • Search: ask neighbors, who ask their neighbors, and so on... when/if found, reply to sender. – TTL limits propagation
Carnegie Mellon EXample: Gnutella I have file A I have fileA. PN Reply Query Where is file A? re
1 8 I have file A. I have file A. Example: Gnutella Where is file A? Query Reply
Carnegie Mellon Flooding: Discussion Pros Fully de-centralized Search cost distributed Processing each node permits powerful search semantics Cons Search scope iS O(N Search time is O(???) Nodes leave often network unstable TTL-limited search works well for haystacks For scalability, does NoT search every node. May have to re-issue query later
1 9 Flooding: Discussion • Pros: – Fully de-centralized – Search cost distributed – Processing @ each node permits powerful search semantics • Cons: – Search scope is O(N) – Search time is O(???) – Nodes leave often, network unstable • TTL-limited search works well for haystacks. – For scalability, does NOT search every node. May have to re-issue query later
Flooding: Discussion 2 Overlay topology can be important Connections between peers the underlying network links Might cross country(or world)multiple times
2 0 Flooding: Discussion 2 • Overlay topology can be important – Connections between peers != the underlying network links – Might cross country (or world) multiple times 20