Filter insertion in SIENA_图文

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

1 of 28 slides

Pre?x Forwarding for Publish/Subscribe
DEBS 2007

Zbigniew Jerzak, Christof Fetzer
Dresden University of Technology Friday 22nd June, 2007

{Zbigniew.Jerzak, Christof.Fetzer}@tu-dresden.de

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

2 of 28 slides

Event forwarding in SIENA [CRW01]
103 siena poset

102 time [ms] 101 100 0

5000

10000 15000 filter count

20000

25000

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

3 of 28 slides

Filter insertion in SIENA
103 siena poset

102

time [ms]

101

10

0

10-1

0

5000

10000 15000 filter count

20000

25000

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

4 of 28 slides

Background

Decoupled [EFGK03] communication... ...between publishers and subscribers via routers ...using ?lters (subscriptions) ...and events (noti?cation) ...based on their content

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

4 of 28 slides

Background

Decoupled [EFGK03] communication... ...between publishers and subscribers via routers ...using ?lters (subscriptions) ...and events (noti?cation) ...based on their content

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

4 of 28 slides

Background

Decoupled [EFGK03] communication... ...between publishers and subscribers via routers ...using ?lters (subscriptions)
{movie=”star wars” AND price<15}

...and events (noti?cation) ...based on their content

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

4 of 28 slides

Background

Decoupled [EFGK03] communication... ...between publishers and subscribers via routers ...using ?lters (subscriptions) ...and events (noti?cation)
{movie=”indiana jones” format=”DVD” price=30}

...based on their content

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

4 of 28 slides

Background

Decoupled [EFGK03] communication... ...between publishers and subscribers via routers ...using ?lters (subscriptions) ...and events (noti?cation) ...based on their content

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

5 of 28 slides

Our Approach

Match event only once

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

6 of 28 slides

Our Contributions

New routing structure and algorithms
Routing Tree (matching) Forwarding Pre?x Tree (forwarding)

Content and forwarding decoupling No false negatives

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

7 of 28 slides

Outline – Subscribing

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

7 of 28 slides

Outline – Subscribing

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

7 of 28 slides

Outline – Subscribing

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

7 of 28 slides

Outline – Subscribing

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

8 of 28 slides

Outline – Publishing

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

8 of 28 slides

Outline – Publishing

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

8 of 28 slides

Outline – Publishing

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

8 of 28 slides

Outline – Publishing

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

8 of 28 slides

Outline – Publishing

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

8 of 28 slides

Outline – Publishing

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

8 of 28 slides

Outline – Publishing

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

9 of 28 slides

Routing Tree

stores ?lters used for event matching and forwarding

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

10 of 28 slides

Routing Tree – Filter Insertion

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

10 of 28 slides

Routing Tree – Filter Insertion

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

10 of 28 slides

Routing Tree – Filter Insertion

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

10 of 28 slides

Routing Tree – Filter Insertion

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

10 of 28 slides

Routing Tree – Filter Insertion

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

10 of 28 slides

Routing Tree – Filter Insertion

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

10 of 28 slides

Routing Tree – Filter Insertion

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

11 of 28 slides

Forwarding Pre?x Tree

Represents the pre?x Assigned by the Edge Router

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

12 of 28 slides

Event Matching

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

12 of 28 slides

Event Matching

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

12 of 28 slides

Event Matching

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

12 of 28 slides

Event Matching

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

12 of 28 slides

Event Matching

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

12 of 28 slides

Event Matching

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

13 of 28 slides

Event Forwarding

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

13 of 28 slides

Event Forwarding

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

13 of 28 slides

Event Forwarding

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

13 of 28 slides

Event Forwarding

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

13 of 28 slides

Event Forwarding

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

14 of 28 slides

The Problem

Routing Trees are not deterministic
...but we could ?x it

The whole system is non deterministic
...and we want 0 false-positives

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

14 of 28 slides

The Problem

Routing Trees are not deterministic
...but we could ?x it

The whole system is non deterministic
...and we want 0 false-positives

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

15 of 28 slides

Updating TO

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

15 of 28 slides

Updating TO

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

15 of 28 slides

Updating TO

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

15 of 28 slides

Updating TO

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

15 of 28 slides

Updating TO

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

16 of 28 slides

Updating RT

Push update from the TO the RT
Hey, and what about decoupling?

TO maintains the content of the ?lters
More precisely - insertion order

Routers associate their view of network with received RT TO serializes subscriptions

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

16 of 28 slides

Updating RT

Push update from the TO the RT
Hey, and what about decoupling?

TO maintains the content of the ?lters
More precisely - insertion order

Routers associate their view of network with received RT TO serializes subscriptions

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

16 of 28 slides

Updating RT

Push update from the TO the RT
Hey, and what about decoupling?

TO maintains the content of the ?lters
More precisely - insertion order

Routers associate their view of network with received RT TO serializes subscriptions

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

16 of 28 slides

Updating RT

Push update from the TO the RT
Hey, and what about decoupling?

TO maintains the content of the ?lters
More precisely - insertion order

Routers associate their view of network with received RT TO serializes subscriptions

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

16 of 28 slides

Updating RT

Push update from the TO the RT
Hey, and what about decoupling?

TO maintains the content of the ?lters
More precisely - insertion order

Routers associate their view of network with received RT TO serializes subscriptions

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

17 of 28 slides

Evaluation Environment

SIENA 1.5.4 Stochastic Simulation in Java (SSJ) library AOL 500k User Session Collection Google stats collected on 28th May 2007 Large Graph Layout (LGL)

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

17 of 28 slides

Evaluation Environment

SIENA 1.5.4 Stochastic Simulation in Java (SSJ) library
umontreal.iro.lecuyer.randvar.* umontreal.iro.lecuyer.rng.*

AOL 500k User Session Collection Google stats collected on 28th May 2007 Large Graph Layout (LGL)

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

17 of 28 slides

Evaluation Environment

SIENA 1.5.4 Stochastic Simulation in Java (SSJ) library AOL 500k User Session Collection
?20M web queries ?650k users 3 months

Google stats collected on 28th May 2007 Large Graph Layout (LGL)

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

17 of 28 slides

Evaluation Environment

SIENA 1.5.4 Stochastic Simulation in Java (SSJ) library AOL 500k User Session Collection Google stats collected on 28th May 2007 Large Graph Layout (LGL)

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

17 of 28 slides

Evaluation Environment

SIENA 1.5.4 Stochastic Simulation in Java (SSJ) library AOL 500k User Session Collection Google stats collected on 28th May 2007 Large Graph Layout (LGL)

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

18 of 28 slides

Using AOL 500K – Subscriptions

AOL log line:
AnonID | Query | QueryTime | <ItemRank> | <ClickURL>

Subscriptions:
{q Op.SS Query} {q Op.PF Query} LocalSubscriber≡AnonID

Publications?

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

18 of 28 slides

Using AOL 500K – Subscriptions

AOL log line:
AnonID | Query | QueryTime | <ItemRank> | <ClickURL>

Subscriptions:
{q Op.SS Query} {q Op.PF Query} LocalSubscriber≡AnonID

Publications?

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

18 of 28 slides

Using AOL 500K – Subscriptions

AOL log line:
AnonID | Query | QueryTime | <ItemRank> | <ClickURL>

Subscriptions:
{q Op.SS Query} {q Op.PF Query} LocalSubscriber≡AnonID

Publications?

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

19 of 28 slides

Using AOL 500K – Publications

P1 (sub) =

google results(sub) total indexed pages

1 2 3 4 5

f o r ( sub : a l l S u b s c r i p t i o n s ) { i f ( P1 ( sub )>Random . n e x t D o u b l e ( ) ) { p u b l i c a t i o n s t r i n g+=sub . a t t r i b u t e V a l u e ( ) ; } }
Zbigniew Jerzak, Christof Fetzer

Pre?x Forwarding for Publish/Subscribe

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

20 of 28 slides

Test Data

40k queries
1010 109 10 hits count 10
8

hits for query

1010 109 10 hits count
8

hits for query

107
6

107 106 105 104 103 102 101 0 10000 20000 30000 40000 50000 60000 70000 80000 query # 100 0 5000 1000015000200002500030000350004000045000 query #

105 104 103 102 101 100

Figure 1: 10 queries/user

Figure 2: ≥ 4k queries/user

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

21 of 28 slides

Routing Tree

Figure 3: RT – Op.SS, 10 q/u
Pre?x Forwarding for Publish/Subscribe Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

22 of 28 slides

Forwarding Pre?x Tree (FPT)
140 120 100 nodes # 80 60 40 20 0 1 2 3 level 4 5 6 FPT 10 queries (246 nodes) FPT >=4k queries (175 nodes)

Figure 4: FPT – Op.SS
Pre?x Forwarding for Publish/Subscribe Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

23 of 28 slides

Event forwarding in SIENA vs Pre?x Tree
103 prefix tree siena poset

102

time [ms]

101

10

0

10-1

0

5000

10000 15000 filter count

20000

25000

Figure 5: Op.SS, 10 queries/user
Pre?x Forwarding for Publish/Subscribe Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

24 of 28 slides

Filter storage in SIENA vs Pre?x Tree
103 prefix tree siena poset

102

time [ms]

101

10

0

10-1

0

5000

10000 15000 filter count

20000

25000

Figure 6: Op.SS, 10 queries/user
Pre?x Forwarding for Publish/Subscribe Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

25 of 28 slides

Summary

Match only once per event Pre?x to decouple content and routing Tree Optimizer to handle indeterminism

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

26 of 28 slides

Cool stu? to do

RT deltas Forwarding e?ciency Autonomic con?guration FPT accuracy & false positives Publish/Subscribe Testing System

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

27 of 28 slides

Thank You!
http://wwwse.inf.tu-dresden.de/zib/

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer

Motivation

Overview

Routing Tree

Forwarding Pre?x Tree

TO

Evaluation

Summary

28 of 28 slides

References

Antonio Carzaniga, David S. Rosenblum, and Alexander L. Wolf. Design and evaluation of a wide-area event noti?cation service. ACM Trans. Comput. Syst., 19(3):332–383, 2001. Patrick Th. Eugster, Pascal A. Felber, Rachid Guerraoui, and Anne-Marie Kermarrec. The many faces of publish/subscribe. ACM Comput. Surv., 35(2):114–131, 2003.

Pre?x Forwarding for Publish/Subscribe

Zbigniew Jerzak, Christof Fetzer


相关文档

Insertion and placement of central catheters in [PMIDY20434643]
Insertion loss of a Helmholtz resonator in the intake system of internal combustion engines An exper
TI-logic in live-insertion APP with a focus on gtlp
Simultaneous Shield and Buffer Insertion for Crosstalk Noise Reduction in Global Routing
MEASUREMENT OF INSERTION LOSS OF AN ACOUSTIC TREATMENT IN THE PRESENCE OF ADDITIONAL UNCORR
Li-insertion in hard carbon anode materials for Li-ion batteries
Insertion-deletion polymorphisms (indels) as genetic markers in natural
An Approach for Minimum Insertion Loss Bandpass Filter Design
A New Framework For Automatic Generation, Insertion and Verification of Memory Built-In Sel
Investigation of lithium extraction and insertion from LiCoPO4 by in situ X-ray and neutron diffract
电脑版