Transcript Mathew George

Matching Patterns
Servers assemble sequences of notifications from smaller subsequences or
from single notifications.This technique requires an advertisement based
semantics.
•Pattern Factoring
Subscription factored into
elementary components.
Output of factoring process is
always a sequence.
•Pattern Delegation
Server sends out necessary
subscriptions to collect the required
Subpatterns and uses a monitor that will observe and distribute the
occurrence of the whole pattern.
Evaluation
•Reasoning qualitatively about the rationale for the expressiveness of the
notification selection mechanism
•Performing simulation studies
•Constructing a prototype
More study required to fully validate the design, but achieved the goal of
a Wide area event notification service
Rationale for chosen
Expressiveness
Factors unaccounted for – Network Latency and Data Structure size
(Also restricted the expressiveness of Patterns in Siena in the
interests of efficiency )
Factors under control – Definitions of notifications, filters, patterns
and complexity of computing covering relations.
Covering Relations
Complexity of determining whether a given subscription and a
given notification are related by
is O(n+m) where n = No. of Attribute constraints in the subscription
filter
m = No. of Attributes in the notification
Values of n and m small so computations negligible compared
to the network costs .
SIENA = SQL in terms of expressiveness
Simulation Studies ( to assess scalability )
Simulation Framework
•
Configuration of servers and clients mapped onto the sites of a wide area
network
• An assignment of application behaviors to objects of interest and
Clients
Servers
interested parties
Network Configuration
•
•
•
Site
Costs
Links
Assumptions
1. Links have constant latency
2. Sites and links have infinite
capacity
3. Costs of computation at sites and communication
through links are linear functions of load
Effect of congestion unaccounted?
Sites
Links
Homogenous Architecture
Application Behavior
Objects of Interest executes m sequences like
Interested party executes p sequences like
Main purpose of simulations is to highlight the relative behaviors of the
architectures and algorithms.
Simulation was conducted on objects of interest and interested parties
associated with only one particular kind of event.
Additional kinds of events (with their own publishers and subscribers)
not considered ?Why (inspite of chances of final results getting affected) ?
Four event notification service architecture/algorithms:
ce = centralized architecture ( omitted because total cost far outweighs that
of distributed architectures )
hs = hierarchical client-server with subscription forwarding
as = acyclic peer to peer with subscription forwarding
aa = acyclic peer to peer with advertisement forwarding
1.Total Cost
Saturation point
Total cost = sum of the costs of all site to site message traffic
It captures an important aspect of scalability by revealing how
communication cost is impacted by increases to load presented to the service.
Observations
• When more than 100 interested parties, total cost constant beyond the
saturation point (no additional cost incurred)
- since there is an object of interest at every site
• All architectures scale sub linearly when No. of Interested parties is below
saturation point
- since object of interest and interested party are not at the same site
• As No.of Objects of interest increases, ‘hs’ performs worst
when compared to ‘as’
- ‘as’ is penalized by its broadcast of subscriptions whereas ‘hs’ propagates
notifications towards the root of the hierarchy and it is forced to do so
whether or not interested parties exist on the other side of the root of the
network
• ‘aa’ depicts unstable cost profile for low densities of interested parties
- objects of interest unadvertises and readvertises frequently
Overall ‘as’ scales well and predictable under all circumstances
Comparison of total costs below
saturation point
2.Cost per service request
Avg. per service cost = Total Cost
-----------------------------------Total number of Client requests
hs does well
hs does well
as does well
as does well
Observations
1.
‘ce’ unreasonable in all scenarios as compared to other architectures
2. Advertisement forwarding becomes unstable for high no. of objects
of interest
3.
For low number’s of objects of interest and interested parties, the costs
are dominated by message passing costs internal to ‘SIENA’
3.Cost per subscription and per
Notification
Avg per subscription cost = Total cost of all subscription related messages
-------------------------------------------------------Number of subscriptions processed
Avg per notification cost = Total cost of all notification related messages
---------------------------------------------------------Number of notifications processed
‘as’ higher cost
‘hs’ higher cost
How‘hs’ and ‘as’ forwards
subscriptions
In ‘as’ a subscription is propagated throughout the network, in a network
of N sites, a subscription goes through O(N) hops
Cost = O(N)
In ‘hs’ a subscription is forwarded upward only to the root server
Cost = O(log N)
4. Worst-case Per-site Cost
Calculated by averaging the cost of communication incurred by each site
over the 10 simulations of that scenario, and then by computing the maximum
over those average per site costs
‘hs’ incurs maximum per site cost than ‘as’ for high densities of objects
of interest and therefore high volumes of notifications
Summary
Costs
as
hs
PerSubscription
cost
Higher
O(N)
Lower
O(logN)
Worst-case
per-site cost
Lower
Higher( for
higher
densities)
Cost of
ignored
notifications
Nil
Fixed cost
O(log N)
Cost of
delivering
notification
Same
Same
•‘hs’ performs better at low densities of interested parties that subscribe
unsubscribe frequently
•‘as’ performs well in the presence of ignored notifications
SIENA Prototype
• Implemented in C++ and Java
• Java event server based on hierarchical client-server algorithm
• C++ event server based on acyclic peer to peer architecture with
subscription forwarding
• Client/server and server/server communication implemented on top
of TCP/IP connections
• Also encapsulated application level protocols such as HTTP and SMTP
Comparing Siena with other related
technologies
Subscription Languages
Scope
• whether a subscription is limited to considering a single notification
or multiple notifications
• whether a subscription is limited to considering a single, designated field
in a notification or whether it can consider multiple fields
Expressive Power
• Concerned with sophistication of operators used in forming
subscription predicates
1. Content based language
2. Channel based language
3. Subject based language
Related Technologies
1.Yeast (event action system) / Siena (event notification service)
• In Siena responses to events are executed by interested parties externally
to the service
• Yeast is also responsible for executing the actions taken in response to
event notifications
2. IP Multicast similar to Siena
• Addresses are not explicit host addresses but rather arbitrary expressions
of interest, and in which subscribing is equivalent to joining a group
3. Active networks (can be used as an implementation platform)
4. CORBA Notification service and Java Message Service (interfaces)
5. iBus, TIBCO TIB/Rendezvous, Talarian’s (NOT SCALABLE)
6. IBM’S Gryphon
• uses fast algorithm
• propagates every subscription everywhere in the network, whereas
Siena propagates only the most generic subscriptions
7. Peer to peer architecture
Conclusion
Future areas of research of Siena
• Which algorithms most sensitive to different classes of applications
• Enhance the design of interface and algorithms to support mobility
• QoS
• Other aspects of Wide area event notification service
• Secure publish/ subscribe connection
• Mechanisms for reliability and fault tolerance
• Content based Routing