WIXLIB

4.2.SDP-Bloom Overview In DDS, mostly for those scenarios with a big number ofEndpoints in each Participant, we identify two problems to besolved: Memory requirements in nodes. Network traffic.We call SDP-Bloom our new SDP variant, which is based onBloom filter technologyCaused by interchanging and storing the complete remotelist of Endpoints: “give me all information you have”In SDP-Bloom each Participant will send its own Bloom filterwhich encodes its Endpoint set: “give me the information toknow what you have”Javier Sánchez-Monedero, Javier Povedano, Juan M. Lopez-Soler: "Scalable DDS Discovery Protocols Based on Bloom Filters". University of Granada.23

4.2.SDP-Bloom Overview In SPD-Bloom each Participant stores information of allentities but with significantly smaller size. Similarly, network traffic is also reduced. However, new problems must be solved: False positives EndPoint Updates CPU cost for building the BFWhen BFs should be sent to the other Participants?–First approach: to include the filter in Participant DATA messages ofthe PDP, and to use EDP to deal with updates and false positives–Second approach: to sent the BF in the EDP (seems to be closer to theDDS standard)Javier Sánchez-Monedero, Javier Povedano, Juan M. Lopez-Soler: "Scalable DDS Discovery Protocols Based on Bloom Filters". University of Granada.24

Contents1.Introduction2.The State of the Art in Discovery3.Bloom filters4.SDP-Bloom4.1 Discovery Process in DDS4.2 SDP-Bloom Overview4.3 Algorithm Description4.4 Design decisions4.5 Nodes dialog4.6 SDP-Bloom Scalability Analysis5.Hierarchical P2P in DDS Discovery6.ConclusionsJavier Sánchez-Monedero, Javier Povedano, Juan M. Lopez-Soler: "Scalable DDS Discovery Protocols Based on Bloom Filters". University of Granada.25

4.3.SDP-Bloom algorithm description1) Just before enabling the new Participant, a BF is created for representingthe Endpoints set.2) Each time a new local Endpoint is created and enabled, it is added to thefilter.3) The Participant starts discovering remote Participants by using SimpleParticipant Discovery Protocol.4) The Participant asserts all new discovered Participants and applies theEndpoint Discovery Protocol.5) For each remote Participant, it sends its BFs instead of the complete set oflocal Endpoints. In the same way, it will receive the remote Participantfilters and will proceed to match its Endpoints with each filter.Javier Sánchez-Monedero, Javier Povedano, Juan M. Lopez-Soler: "Scalable DDS Discovery Protocols Based on Bloom Filters". University of Granada.26

4.4.SDP-Bloom design decisions Design decisions: the m/n ratio in our Bloom filter The larger the m/n ratio, the lower error rate While the lower the m/n ratio, the lower BW and memoryrequirements The relation n (Endpoints/Participant) is the number of keys toinclude in the filter.Error Rate0.010.010.010.0010.0010.001 N (Keys) M (Required Size) BF 6500102151277Note the Error Rate (f) is the probability of obtaining a falsepositive Endpoint in a given Participant.Javier Sánchez-Monedero, Javier Povedano, Juan M. Lopez-Soler: "Scalable DDS Discovery Protocols Based on Bloom Filters". University of Granada.27

4.4.SDP-Bloom design decisions Design decisions: information updates Participants discovery still working like SDP (soft-state) Endpoints are updated publishing changes on-demand: Initially, we consider that the Endpoints/Participant relation is sosmall that is “cheaper” to send the new filter each time.Deleting imply to rebuild the filter. Counting BF supports deletion, but it probably use too muchspace At the moment we consider to use original Bloom filtersJavier Sánchez-Monedero, Javier Povedano, Juan M. Lopez-Soler: "Scalable DDS Discovery Protocols Based on Bloom Filters". University of Granada.28

4.4.SDP-Bloom design decisions Design decisions: managing false positives The matching process consist in test if a Topic bellows to a filter. For each desired Endpoint which matches with a filter we canassert the desired remote Endpoint and try to connect with it. Normally, we do not have problems, but if it fails we can: Obtain the complete remote Endpoint list for this Participant, asEndpoint Discovery Protocol does. Ask the remote Participant about this Endpoint. Deduce that we got a false positive and do no assert the Endpoint.Javier Sánchez-Monedero, Javier Povedano, Juan M. Lopez-Soler: "Scalable DDS Discovery Protocols Based on Bloom Filters". University of Granada.29

start4.5.SDP-Bloom nodes dialogBuild or update the BFSend BF to the discovered ParticipantsMatch local Endpoint with remote BFTry to Subscribeyesno (fail)Assert remote EndpointDeduce false positiveWait a refresh timeNoLocal changesNoNoNew remoteinformationEnd?Javier Sánchez-Monedero, Javier Povedano, Juan M. Lopez-Soler: "Scalable DDS Discovery Protocols Based on Bloom Filters". University of Granada.30

- We omit PDPinformation- The BF is sent in arefresh perioddefined as a QoSparameter- The light blueshows the supressedtrafficSDP-BloomNode BNode AparticipantA DATATAt B DAnapiparticBF Refresh periodDataWriter A1 createdBF Refresh periodparticipaDataWriter A2 createdDataWriter A3 creatednt A BloomfilterNode CDataWriter An createdATAnt C DapicipartOn-demand updateStorageQoS parameterparticipantA BFparticipantA Bloom filterSDP SDP-BloomNode BNode CBF Refresh periodBF Refresh periodOn-demand updateparticipant A Bloomfilter

SDP-BloomNode BNode A- Participant A whish to informabout its Endpoints- Participant B whish tomach A2, A4 and F- We omit PDP informationDataWriter A1 createdDataWriter A2 createdDataWriter A3 createdparticipantA DATATAt B DAnapiparticBF Refresh periodparticipantA Bloom filterB can not match any topic.DataWriter An createdBF Refresh periodparticipantA Bloomfilter2ribe ASubsc4ribe ASubscribe FSubscI havenot FparticipantB can match A1-N topics,topic F is a false positiveB matchs A2, A4, F and triesto subscribe A2,A4,FBF Refresh periodA BFB deduces it was a falsepossitive and annotates itDataWriter A3 deletedStorageSDP SDP-BloomNode BNode CBF Refresh periodparticipantA BFB can match A1,A2,A4-N topics

4.6.SDP-Bloom Scalability AnalysisParticipant messages (unicast)400000Scenario nameSmall SystemMedium SystemLarge SystemParticipants (P) Topics (T) Endpoints mediumlargeParticipant memory consumed 007500050000250000smallmediumlargeJavier Sánchez-Monedero, Javier Povedano, Juan M. Lopez-Soler: "Scalable DDS Discovery Protocols Based on Bloom Filters". University of Granada.33

Contents1. Introduction2. The State of the Art in Discovery3. Bloom filters4. SDP-Bloom5. Hierarchical P2P in DDS Discovery6. ConclusionsJavier Sánchez-Monedero, Javier Povedano, Juan M. Lopez-Soler: "Scalable DDS Discovery Protocols Based on Bloom Filters". University of Granada.34

5.Hierarchical P2P in DDS DiscoveryMotivation and overview Pure P2P: DHTs and overlay P2P networks providereplication, fault tolerance and scalability up to 2000 nodesHierarchical P2P Global discovery. Global information stored in a DHT. SuperNodes do global discovery according to Nodes petitionsLocal discovery. Each SuperNode “adopts” a set of Nodes The adoption depends of the key assigned in the DHT SuperNodes and Nodes do local discovery in a DomainScalability of Hierarchical P2P: Participants with a short life time should not be included in DHT Only a subset of nodes will be selected in the DHT, then the DHTworks better in terms of the cost of maintaining the selfstructure. Local discovery allows using local cache in each groupJavier Sánchez-Monedero, Javier Povedano, Juan M. Lopez-Soler: "Scalable DDS Discovery Protocols Based on Bloom Filters". University of Granada.35

5.Hierarchical P2P in DDS DiscoveryThe Distributed Hash Tablein Pure P2P Each peer stores a subset of(key, value) pairs in thesystempeer IDresource key0Core operation: Find noderesponsible for a key Map key to node Efficiently routeinsert/lookup/delete requestto this nodeOverlay P2P networks: KeyBased Routing (KBR) networksrange(p)pJavier Sánchez-Monedero, Javier Povedano, Juan M. Lopez-Soler: "Scalable DDS Discovery Protocols Based on Bloom Filters". University of Granada.36

5.Hierarchical P2P in DDS DiscoveryThe Distributed Hash Table in Hierarchical P2P and DDS: The nodes in DHT will be the SuperNodes in discovery The resources Key will be a Topic The value will be the list of Participants which are interestedin a TopicDHT (key,value) (Topic, Participant list)A SuperNode adopts a set of Participants interested in theTopics which the SN manages.The replication and fault tolerance of SuperNodes isdelegated to the DHT implementationJavier Sánchez-Monedero, Javier Povedano, Juan M. Lopez-Soler: "Scalable DDS Discovery Protocols Based on Bloom Filters". University of Granada.37

5.Hierarchical P2P in DDS Discovery0SuperNode IDTopic IDAdopted Topicsrange(p)pAll the Participants interested in SN p'sTopics will receive discovery informationvia DCPS built-in TopicsSNs replication and fault tolerance is delegated on the DHTLookup (T,Participants) in the DHT is O (Log N), where N number of SuperNodesJavier Sánchez-Monedero, Javier Povedano, Juan M. Lopez-Soler: "Scalable DDS Discovery Protocols Based on Bloom Filters". University of Granada.38

5.Hierarchical P2P in DDS DiscoveryDiscovery Process example:0SN1SN4New Participant interesting in TopicBar The hashed TopicBar involve been adoptedby SN4 Created DCPS TopicBar built-in endpointsfor discovery relation with SN4SuperNode SN1: Adopts TopicFoo and managesTopicFoo discovery issuesNew Participant interested inTopicFoo: The hashed TopicFoo involve beenadopted by SN1 Creates DCPS TopicFoo built-inendpoints for discovery relation withSN1 SN1 add the Participant to the(TopicFoo,Participant list) andnotifies existing ParticipantsJavier Sánchez-Monedero, Javier Povedano, Juan M. Lopez-Soler: "Scalable DDS Discovery Protocols Based on Bloom Filters". University of Granada.39

Contents1. Introduction2. The State of the Art in Discovery3. Bloom filters4. SDP-Bloom5. Hierarchical P2P in DDS Discovery6. ConclusionsJavier Sánchez-Monedero, Javier Povedano, Juan M. Lopez-Soler: "Scalable DDS Discovery Protocols Based on Bloom Filters". University of Granada.40

6.Conclusions In this work we propose to use Bloom filters in DDSdiscovery.While in SDP the consumed traffic depends on the number oftopics, by adopting our solution this dependence is relaxed.The improvement will be better as the number of topicsgrows.BFs can reduce network traffic and storage requirementsWe have shown preliminarily that hierarchical P2P can beused in DDS discovery.We provides replication, better fault tolerance and balancedload. Therefore, it promises even better scalabilityJavier Sánchez-Monedero, Javier Povedano, Juan M. Lopez-Soler: "Scalable DDS Discovery Protocols Based on Bloom Filters". University of Granada.41

Thank you very much

Bibliography Burton H. Bloom. Space/time trade-offs in hash coding with allowable errors.Commun. ACM, 13(7):422–426, 1970.Li Fan, Pei Cao, Jussara Almeida, and Andrei Z. Broder. Summary cache: a scalablewide-area web cache sharing protocol. IEEE/ACM Trans. Netw., 8(3):281–293, 2000.Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger, M. Frans Kaashoek,Frank Dabek, and Hari Balakrishnan. Chord: a scalable peer-to-peer lookup protocolfor internet applications. IEEE/ACM Trans. Netw., 11(1):17–32, 2003.Antony Rowstron and Peter Druschel. Pastry: Scalable, decentralized object location,and routing for large-scale peer-to-peer systems. Lecture Notes in ComputerScience, 2218:329, 2001.Noura Limam, Joanna Ziembicki, Reaz Ahmed, Youssef Iraqi, Dennis Tianshu Li,Raouf Boutaba, and Fernando Cuervo. Osda: Open service discovery architecture forefficient cross-domain service provisioning. Comput. Commun., 30(3):546–563,2007.Michael Mitzenmacher, Codes, Bloom Filters, and Overlay Networks.http://www-math.mit.edu/ steng/18.996/MIT Talk.pptFredrik Bjurefors, Lars-Ake Larzon, and Richard Gold. Performance of pastry in aheterogeneous system. In P2P ’04: Proceedings of the Fourth InternationalConference on Peer-to-Peer Computing (P2P’04), pages 278–279, Washington, DC,USA, 2004. IEEE Computer Society.Celeste Campo. Directory facilitator and service discovery agent, 2002.Javier Sánchez-Monedero, Javier Povedano, Juan M. Lopez-Soler: "Scalable DDS Discovery Protocols Based on Bloom Filters". University of Granada.43

The filter represents a list of valid words Summary Cache (Cache Digest in Squid) Squid is a high-performance proxy caching server for web clients, supporting FTP, gopher, and HTTP data objects. A Cache Digest is a summary of the contents of an Internet Object Caching Server. It contains, in a compact (i.e.