Upload
reinhilde-schiller
View
109
Download
2
Embed Size (px)
Citation preview
Vortrag zur Diplomarbeit in der Vortrag zur Diplomarbeit in der Arbeitsgruppe Datenbanken und InformationssystemeArbeitsgruppe Datenbanken und Informationssysteme
Entwurf und Analyse einesEntwurf und Analyse eineseffizienten verteilten effizienten verteilten
BenachrichtigungssystemsBenachrichtigungssystems
Sven Bittner, 9Sven Bittner, 9. Januar 2004. Januar 2004
Betreuung durchBetreuung durch
Dr. Annika Hinze und Prof. Dr.-Ing. Heinz F. SchweppeDr. Annika Hinze und Prof. Dr.-Ing. Heinz F. Schweppe
2/20
MotivationMotivation
Benach-Benach-richtigungs-richtigungs-
system system (BS)(BS)
e2: t=30°C
e3: r=0,2 liter
ee44:: r=2 r=2
literliter
ee11 :: t=15°C
t=15°C
EreignisseEreignisse
FilterungFilterung
Effiziente, skalier-Effiziente, skalier-bare Filterungbare Filterung
BenachricBenachrich-h-tigungentigungen
((ee 22))
(e1)
((ee33 ), ), ((ee
44 ))
Profile Profile AbonnentenAbonnenten
p1=(t>22°C)
p2=(t<18°C)
p3=(r>0,1 lit.)
AnbieterAnbieter(Sensoren)(Sensoren)
Gebäudesteuerung (mittleres Gebäude)Gebäudesteuerung (mittleres Gebäude)• >10>1044 ProfileProfile• >10>1033 EreignisseEreignisse//SekundeSekunde
3/20
GliederungGliederung
• Zentralisierte FilterungZentralisierte Filterung
• Verteilte FilterungVerteilte Filterung
• ExperimenteExperimente
• ZusammenfassungZusammenfassung
4/20
GliederungGliederung
• Zentralisierte FilterungZentralisierte Filterung
• Verteilte FilterungVerteilte Filterung
• ExperimenteExperimente
• ZusammenfassungZusammenfassung
5/20
Zentralisierte FilterungZentralisierte Filterung
• Schnellste Struktur [GS95]Schnellste Struktur [GS95]– Filterbaum über alle Attribute eines TypsFilterbaum über alle Attribute eines Typs– ProblemeProbleme
–– Hauptspeicherbedarf sehr groß (breiter Baum)Hauptspeicherbedarf sehr groß (breiter Baum)
–– Nur GleichheitsoperatorenNur Gleichheitsoperatoren
–– Statische FilterstrukturStatische Filterstruktur
p4=(s=1,t=20,r=2)p5=(s=2,t=10,r=4)p6=(s=2,t=20,r=8)p7=(s=2,r=8)p8=(s=2,t=20,r=8)
t
s
t
r
r
r
r
p4
p7
p6,7,8
p5
p7
1
2
20
1020
*
2
48
8
8
Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung
6/20
Zentralisierte Filterung: Zentralisierte Filterung: ErweiterungErweiterung
{p{p55, p, p66, p, p77, p, p88}} {p{p77}} {p{p66, p, p77, p, p88}}
ee55: (s=2,t=6,r=8): (s=2,t=6,r=8)
Passende Profile:Passende Profile:== {p{p77}}
1020*t
p5,7
p4,6,7,8
p7
248r
p4
p5
p6,7,8
sp4
p5,6,7,8
12
• Erweiterte Struktur – System PrimAS [Bit02, Erweiterte Struktur – System PrimAS [Bit02, Bit03]Bit03]– Einzelner Knoten je Attribut (Minibaum)Einzelner Knoten je Attribut (Minibaum)– EigenschaftenEigenschaften
++ Weniger Speicherbedarf (keine breiten Bäume) Weniger Speicherbedarf (keine breiten Bäume)
++ Kantenbeschreibung mit Intervallen Kantenbeschreibung mit Intervallen
++ Operatoren: <, >, =, Mengentest, Bereichstest Operatoren: <, >, =, Mengentest, Bereichstest
++ Dynamischer Umbau möglich Dynamischer Umbau möglich
Zusätzlich:Zusätzlich: - Optimierung der Auswertungsreihenfolge [HB02]- Optimierung der Auswertungsreihenfolge [HB02]
Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung
7/20
GliederungGliederung
• Zentralisierte FilterungZentralisierte Filterung
• Verteilte FilterungVerteilte Filterung
• ExperimenteExperimente
• ZusammenfassungZusammenfassung
8/20
Verteilte FilterungVerteilte Filterung
1
3 4
5
BSBS
VerteiltesVerteiltes
62 Zentrale Filter-
komponenten
62
Azyklisches Overlaynetz
zur Verteilung
von Profilen und
Ereignissen
Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung
S
A
Kommunikation mit
beliebigen Vermittler
9/20
• VerteilungsstrategienVerteilungsstrategien– Ereignisweiterleitung (EW) [CRW99]Ereignisweiterleitung (EW) [CRW99]
• Filterung nah bei den AbonnentenFilterung nah bei den Abonnenten• Keine Weiterleitung von ProfilenKeine Weiterleitung von Profilen• Fluten von EreignissenFluten von Ereignissen
Verteilte Filterung: Verteilte Filterung: EreignisweiterleitungEreignisweiterleitung
1
3 4
5
62 BSBS
VerteiltesVerteiltesS1
e3: r=0,2lit.
A1
p3=(r>0,1lit
.)
p3 (e3)
Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung
10/20
Verteilte Filterung: Verteilte Filterung: ProfilweiterleitungProfilweiterleitung
– Profilweiterleitung (PW) [CRW99]Profilweiterleitung (PW) [CRW99]• Filterung nah bei den AnbieternFilterung nah bei den Anbietern• Fluten von ProfilenFluten von Profilen• Keine Weiterleitung von EreignissenKeine Weiterleitung von Ereignissen
1
3 4
5
62 BSBS
VerteiltesVerteiltesS1
e3: r=0,2lit.
A1
p3=(r>0,1lit.
)
p3
p3
p3
p3
p3
p3
(e3)
Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung
11/20
– Rendezvousknoten (RK) [PB02]Rendezvousknoten (RK) [PB02]• Filterung in spezialisierten ereignistypabhängigen Filterung in spezialisierten ereignistypabhängigen
RKRK• Gerichtete Weiterleitung der Profile und Ereignisse Gerichtete Weiterleitung der Profile und Ereignisse
an RKan RK• Praxis: Filterung auch in UnterwegsknotenPraxis: Filterung auch in Unterwegsknoten
Verteilte Filterung: Verteilte Filterung: RendezvousknotenRendezvousknoten
Filterung von Niederschlags-ereignissen
1
3 4
5
62 BSBS
VerteiltesVerteiltesS1
e3: r=0,2lit.
A1
p3=(r>0,1lit
.)p3
(e3)
Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung
12/20
– Ausnutzen von Bedeckungen zwischen ProfilenAusnutzen von Bedeckungen zwischen Profilen• Intuitiv: pIntuitiv: pxx > p > pyy (überdeckt) gdw. zu p (überdeckt) gdw. zu pxx genau die oder genau die oder
mehr Ereignisse als zu pmehr Ereignisse als zu pyy passen passen
– AnwendungAnwendung• Weiterleiten von Profil pWeiterleiten von Profil pxx an Nachbarn nur dann, wenn an Nachbarn nur dann, wenn
noch kein pnoch kein pyy mit p mit pyy > p > px x weitergeleitet wurdeweitergeleitet wurde
• Wenn Profil pWenn Profil pxx von Nachbarn eintrifft, können alle p von Nachbarn eintrifft, können alle pyy dieses Nachbarn mit pdieses Nachbarn mit pxx > p > pyy entfernt werden entfernt werden
– BerechnungBerechnung• Bereichsbasierte Berechnung (aufbauend auf Bereichsbasierte Berechnung (aufbauend auf
Filterstruktur)Filterstruktur)– Analyse der Kanten der Minibäume abhängig vom OperatorAnalyse der Kanten der Minibäume abhängig vom Operator– Bildung der Schnittmenge der Überdeckungen der Bildung der Schnittmenge der Überdeckungen der
AttributeAttribute
Verteilte Filterung: OptimierungVerteilte Filterung: Optimierung
Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung
13/20
GliederungGliederung
• Zentralisierte FilterungZentralisierte Filterung
• Verteilte FilterungVerteilte Filterung
• ExperimenteExperimente
• ZusammenfassungZusammenfassung
14/20
ExperimenteExperimente
• Realisierung der verteilten Filtervarianten und der Realisierung der verteilten Filtervarianten und der zentralisierten Filterkomponente in Prototyp DASzentralisierten Filterkomponente in Prototyp DAS
• Messungen unter Variation zahlreicher ParameterMessungen unter Variation zahlreicher Parameter
– Anteil passender ProfileAnteil passender Profile– Anteil erfüllender EreignisseAnteil erfüllender Ereignisse– VermittlerzahlVermittlerzahl– Überdeckungen zwischen ProfilenÜberdeckungen zwischen Profilen– Anzahl EreignistypenAnzahl Ereignistypen– Lokalitätsverhalten zw. Ereignissen und ProfilenLokalitätsverhalten zw. Ereignissen und Profilen– GesamtprofilanzahlGesamtprofilanzahl
Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung
15/20
Experimente: Auswahl (1)Experimente: Auswahl (1)
• Einfluss der GesamtprofilanzahlEinfluss der Gesamtprofilanzahl
Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung
16/20
Experimente: Auswahl (2)Experimente: Auswahl (2)
• Einfluss der erfüllenden EreignisseEinfluss der erfüllenden Ereignisse
Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung
17/20
Experimente: Auswahl (3)Experimente: Auswahl (3)
• Einfluss der VermittleranzahlEinfluss der Vermittleranzahl
Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung
18/20
Experimente: FazitExperimente: Fazit
• Ergebnisse (Überblick)Ergebnisse (Überblick)– ProfilweiterleitungProfilweiterleitung
• Meist beste Filtereffizienz und geringste NetzlastMeist beste Filtereffizienz und geringste Netzlast• Jedoch größten SpeicherbedarfJedoch größten Speicherbedarf
– EreignisweiterleitungEreignisweiterleitung• Sehr hohe NetzlastSehr hohe Netzlast• Speicherbedarf optimalSpeicherbedarf optimal• Hoher Anteil passender Ereignisse Hoher Anteil passender Ereignisse beste beste
FiltereffizienzFiltereffizienz• Hohe Profilanzahl Hohe Profilanzahl beste Skalierbarkeit beste Skalierbarkeit
– RendezvousknotenRendezvousknoten• Unter keiner getesteten Konfiguration bessere Unter keiner getesteten Konfiguration bessere
Ergebnisse als andere VerfahrenErgebnisse als andere VerfahrenZentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung
19/20
GliederungGliederung
• Zentralisierte FilterungZentralisierte Filterung
• Verteilte FilterungVerteilte Filterung
• ExperimenteExperimente
• ZusammenfassungZusammenfassung
20/20
ZusammenfassungZusammenfassung
• Zentrale Filterkomponente PrimAS mit neuer Zentrale Filterkomponente PrimAS mit neuer Filterstruktur Filterstruktur
• Verteiltes Benachrichtigungssystem DAS mit Verteiltes Benachrichtigungssystem DAS mit drei verteilten Filteralgorithmendrei verteilten Filteralgorithmen
• Experimente: Optimaler Algorithmus abhängig Experimente: Optimaler Algorithmus abhängig von Systemlast, -nutzung und Anwendungvon Systemlast, -nutzung und Anwendung
System sollte verschiedene Filteralgorithmen System sollte verschiedene Filteralgorithmen unterstützen und dynamisch anpassenunterstützen und dynamisch anpassen
Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung
21/20
LiteraturLiteratur
[Bit02] S. Bittner: [Bit02] S. Bittner: Implementierung eines effizienten Matchingverfahrens für Implementierung eines effizienten Matchingverfahrens für BenachrichtigungssystemeBenachrichtigungssysteme, Studienarbeit, Freie Universität Berlin, Institut , Studienarbeit, Freie Universität Berlin, Institut für Informatik, September 2002.für Informatik, September 2002.
[Bit03] S. Bittner: [Bit03] S. Bittner: Entwurf und Analyse eines effizienten verteilten Entwurf und Analyse eines effizienten verteilten BenachrichtigungssystemsBenachrichtigungssystems. Diplomarbeit, Freie Universität Berlin, Institut . Diplomarbeit, Freie Universität Berlin, Institut für Informatik, September 2003.für Informatik, September 2003.
[CRW99] A. Carzaniga, D. S. Rosenblum, A. L. Wolf: [CRW99] A. Carzaniga, D. S. Rosenblum, A. L. Wolf: Interfaces and Algorithms Interfaces and Algorithms for a Wide-Area Event Notification Servicefor a Wide-Area Event Notification Service. Technischer Bericht CU-CS-888-. Technischer Bericht CU-CS-888-99, Universität Colorado, Fachbereich Informatik, Oktober 1999.99, Universität Colorado, Fachbereich Informatik, Oktober 1999.
[GS95] J. Gough und G. Smith: [GS95] J. Gough und G. Smith: Efficient Recognition of Events in a Distributed Efficient Recognition of Events in a Distributed SystemSystem. In: . In: Proceedings of the 18th Australasian Computer Science Proceedings of the 18th Australasian Computer Science Conference (ACSC-18)Conference (ACSC-18),, Adelaide, Australien, 1.-3. Februar 1995. Adelaide, Australien, 1.-3. Februar 1995.
[HB02] A. Hinze und S. Bittner: [HB02] A. Hinze und S. Bittner: Efficient Distribution-Based Event FilteringEfficient Distribution-Based Event Filtering. In: . In: Proceedings of the International Conference on Distributed Computing Proceedings of the International Conference on Distributed Computing Systems Workshops (ICDCSW´02),Systems Workshops (ICDCSW´02), Wien, Österreich, 2.-5. Juli 2002. Wien, Österreich, 2.-5. Juli 2002.
[PB02] P. Pietzuch, J. Bacon: [PB02] P. Pietzuch, J. Bacon: Hermes: A Distributed Event-Based Middleware Hermes: A Distributed Event-Based Middleware ArchitectureArchitecture. . In: Proceedings of the International Conference on Distributed In: Proceedings of the International Conference on Distributed Computing Systems Workshops (ICDCSW´02),Computing Systems Workshops (ICDCSW´02), Wien, Österreich, 2.-5. Juli Wien, Österreich, 2.-5. Juli 2002.2002.