Transcript 슬라이드 1

Forwarding in a
Content-Based Network
SIGCOMM 2003
Antonio Carzaniga, Alexander L.Wolf
14th January, 2004
Presented by Sookhyun, Yang
Contents

Introduction
 Content-Based Networking
 Content-Based Routing Scheme
 Problem Statement
 Contribution
 Forwarding Algorithm
 Evaluation
 Conclusion
Computer Network Lab
LAB Seminar 2004
2/26
Introduction

Content-based network




Flow of messages is driven by the content of the messages, not by the
IP address
Sender simply publish messages
Receiver declare and advertise their interests by means of selection
predicates
Service delivers to receivers each messages that matches the selection
predicates declared by those receivers
[Content-based addressing scheme]
• M - the universe of messages
• P: M
{true, false} - the universe of predicates over M
• predicate pn advertised by n - content-based address of node n
• pn(m) = true – message is implicitly addressed by its content to node n

Application-level overlay network consisting of client nodes and router
nodes
• Routers perform specialized routing and forwarding functions
Computer Network Lab
LAB Seminar 2004
3/26
Background

Reverse path forwarding (RPF) algorithm

Transmit the packet on all of its outgoing links only if the packet arrived on the
link that is on its own shortest path back to the sender
source
Not forwarded
forwarded
Computer Network Lab
LAB Seminar 2004
4/26
Content-Based Networking

Practical refinement of definitions


Concrete syntax and semantics embodied in the disjunctive normal form
of Siena event notification service [7]
Message is a set of typed attributes

Attribute is uniquely identified within the message by a name, and has a
type and a value
[string carrier= UA; string dest=ORD; int price=300;
bool upgradeable=true;]

Predicate is a disjunction of conjunctions of constraints on the
values of individual attributes
[string dest=ORD Λ int price < 400]
Computer Network Lab
LAB Seminar 2004
5/26
Content-Based Routing scheme (1/4)

Content-based routing [8]



Start from a basis of a broadcast system
Prune branches of the broadcast distribution system using advertised
predicates
Limit the propagation of each message to only those node that
advertised predicates matching the message
Computer Network Lab
LAB Seminar 2004
6/26
Content-Based Routing scheme (2/4)

Two types of routing protocols

Broadcast routing protocol
• Topological information
• Maintain the forwarding state that would be necessary to implement
broadcast system

Content-based routing protocol
• Predicate advertised by nodes
• Maintain the forwarding state that decide (for each router interface) whether
a message matches the predicates advertised by any downstream node

Mechanisms for the propagation of routing information


Push based on receiver advertisements (RA)
Pull based on sender requests (SR) and update replies (UR)
Push
Receiver
Sender
Computer Network Lab
Pull
LAB Seminar 2004
7/26
Content-Based Routing scheme (3/4)

Receiver advertisements (RAs)




Issued by nodes periodically and/or when they advertise new contentbased addresses
Carry the content-based address (predicate) and identifier of its issuer
Push routing information from the issuer (receiver) out to all the potential
senders
Propagation of RA

Follow the broadcast tree rooted at the issuer node
• Sets up RPFs towards the issuer



Predicate advertised by an RA is combined in a disjunction to the
predicate associated with the interface on the reverse path to the issuer
If this combination generates a new predicate for that interface, then the
node continues the propagation of RA
Otherwise, the node simply stop propagating RA
Computer Network Lab
LAB Seminar 2004
8/26
Content-Based Routing scheme (4/4)

Sender request (SR)



Router uses a SR to collect routing information from other routers
Pull content-based routing information from receivers back to senders
Flow of SR/UR




Follow the broadcast tree rooted at the issuer (sender)
Routers respond to SRs by generating update replies (URs) containing
their content-based address
URs are returned back to the issuer of the SR, on the reverse path of
the SR, combining content-based addresses with URs along the way
Issuer (sender) of the SR receives one UR per interface, each one
carrying the combined content-based address of the nodes reachable
through that interface
Computer Network Lab
LAB Seminar 2004
9/26
Problem Statement

Propose a forwarding process consisting of the combination of broadcast
forwarding and content-based forwarding
 Focus on the design of the content-based forwarding algorithm

Assumption 1: broadcast forwarding and routing function


Assumption 2: Content-based routing function



Output for message m originating at a node s is a set of output interfaces B
Maintain a content-based forwarding table
Table represent a map between interfaces and predicates
Contention-based forwarding function CBF
CBF(m, B, T) = { i : i ∈ B Λ matches(pi, m)}
Fast
m - message
B - a set of broadcast output interfaces
T - content-based forwarding table {p1, p2, … ,pI}
Computer Network Lab
LAB Seminar 2004
10/26
Contribution




Use indexing data structure developed by Yan and Carcia-Molina
[20]
Enhance functionality of the matching algorithm
Make it appropriate for use in the forwarding function of a contentbased network
Extensions of algorithm

Extend the set of types and operators in predicates
• Prefix, suffix, and substring operators for strings


Add the explicit expression of disjunctions to predicates
Optimize using the construction of selectivity table
Computer Network Lab
LAB Seminar 2004
11/26
Background

Ternary search trie (TST)
m
b
a
y
m e
e
g
o
n
y
o
s
o
am
as
be
by
go
me
my
no
so
s
Computer Network Lab
LAB Seminar 2004
12/26
Forwarding Algorithm (1/6)

Recall of definition





Forwarding table is a one-to-one association of predicates to interfaces
Predicate is a disjunction of conjunctions of elementary constraints
filter
Constraint is a quadruple <type, name, op, value>
Forwarding a message m amounts to computing the set of interfaces
associated with a predicate matching m
Counting algorithm


Founded on a particular index structure representing the forwarding
table
match
Matching problem
message
Computer Network Lab
LAB Seminar 2004
13/26
Forwarding Algorithm (2/6)

High level view of structure of forwarding table
constraint
Conjunctions
of constraints
disjunctions
of filters
attribute
Boolean
Need optimized
lookup function!!!
Left-hand side
Computer Network Lab
LAB Seminar 2004
Right-hand side
14/26
Forwarding Algorithm (3/6)

Optimization 1 – “Extended counting algorithm”
For a given message m,
for each attribute a in m{
find constraints matched by a
for each constraint c in a{
find the matched filter f
}
when (counter_filter == total # of constraints of f)
add interface to set of matched interfaces
}

Disjunction of filters
• Eliminate a lookup in the table of counters for all the filters linked to interface
that has already been matched

Termination
• Set of matched interfaces = complete set of neighbor interfaces
Computer Network Lab
LAB Seminar 2004
15/26
Forwarding Algorithm (4/6)

Optimization 2 – “Multi-Operator Index”


Speed up the process of finding the constraint
Combine TST (Ternary Search Trie) for attribute name and a simple switch on
the type
Attribute name and type
Multi-operator index
prefix,
suffix, substring op for strings
Attribute name
and type
<Integer constraint indexing>
Computer Network Lab
LAB Seminar 2004
16/26
Forwarding Algorithm (5/6)

Optimization 2 – “Multi-Operator Index” (cont’d)

Extended TST (Ternary search trie)
• Capability of matching partial strings (prefix and substring constraints)
• Pair of “crown” lists linking the sequence of >, < constraints as leaves in TST
• Pair of backtrack functions moving from partial to alphabetically closest complete match
(use to jump to the >, < chains)

Lookup function







Start from the first character of the input string
When partial-match node is reached, return prefix constraint and/or the substring
constraint
If final node touched is #, return the corresponding =, >, <, and suffix constraints
If final node touched is not a leaf, backtracks to the two closest leaf nodes, one
preceding and the other following the final node in alphabetical order
Jump onto <, > chains from matching final node or closest matching nodes
Repeat for each character of the input string
Complexity of complete lookup function = O( l(logN + l) + |result|)
Computer Network Lab
LAB Seminar 2004
17/26
z
<
sfpf
=ss
>
Computer Network Lab
LAB Seminar 2004
18/26
Forwarding Algorithm (6/6)

I1
price
Eliminate interfaces from consideration as soon as possible I2
Determinant attribute
I3
stock
Optimization 3 – “Exploiting attribute selectivity”


• Every filter of interface I contains at least one constraint on determinant
attribute
• If a message does not contain a determinant attribute of interface I, interface
I can be ignored during the processing of the message

Selectivity table
• Map that associates determinant attribute with the interfaces
• Compute the intersection of attribute names of all filters for each interface
• Sort in descending order by the cardinality of the set of excluded interfaces

Pre-processing function
• Use selectivity table to calculate excluded set of interfaces that will not
match the messages
• Parameterize pre-processing function by { # of pre-processing rounds}

Round – how far down the selectivity table pre-processing function will traverse
Computer Network Lab
LAB Seminar 2004
19/26
Evaluation (1/6)


Experiments are intended to provide an initial exploration of the
parameter space
Experimental setup





Algorithm in C++
950MHz computer with 512Mb of main memory
Auxiliary programs for generating loads of filters and messages
100 messages, each one between 1 and 19 attributes (avg = 10)
Experimental parameter

Scalability
• Total number of constraints C ≈ I ⅹ f ⅹ c (I: interface, f : filter, c: constraint)
• Up to five million constraints

Attribute and constraint name
• Set of 1000 elements
• Select random words out of a common dictionary using a Zipf distribution
Computer Network Lab
LAB Seminar 2004
20/26
Evaluation (2/6)

Experimental parameter (cont’d)

Attribute and constraint value
• Combination of dictionary values for strings and a range for integers
• 1000 words, 100 integers
• Uniform distribution for selecting values

Attribute and constraint type
• 50% strings and 50% integers
• Operators in integer constraints: 60% (equality), 20% (less-than),
20% (greater-than)
• Operators in string constraints: 35% (equality), 15% (prefix), 15%
(substring), 10% (less-than), 10% (greater-than)
Computer Network Lab
LAB Seminar 2004
21/26
Evaluation (3/6)

Basic results
One filter per interface<-worst case
Pre-processing round
Reduction of matching time up to 40%
Centralized Architecture
Computer Network Lab
LAB Seminar 2004
22/26
Evaluation (4/6)

Basic results (cont’d)
Fixed number of interfaces
=> More closely modeling
High ratio of filters
per interface
Distributed Architecture
Computer Network Lab
LAB Seminar 2004
23/26
Evaluation (5/6)

Basic results (cont’d)
Computer Network Lab
LAB Seminar 2004
24/26
Evaluation (6/6)

Sensitivity to the number of pre-processing rounds
Performance gain over
simple counting algorithm
Computer Network Lab
LAB Seminar 2004
25/26
Conclusion

In this paper




Present the first algorithm designed specifically for the implementation
of the forwarding function of routers in a content-based network
Refine, adapt, and extend earlier work in the area of centralized content
filtering
Formulate a variant of the counting algorithm that can handle disjunctive
predicates
Develop optimization targeted specifically at the disjunctions that are the
semantics of network interfaces in a content-based network
Computer Network Lab
LAB Seminar 2004
26/26