Design and Evaluation of a Wide-Area Event Notification ServiceOverviewIntroduction (1)Introduction (2)Critical Design IssuesAPI and Semantics (1)API and Semantics (2)API and Semantics (3)Architectures (1)Architectures (2)Routing Strategies used in SIENARouting Strategies : Generic principlesRouting Strategies: Generic Principles (2)Two Classes of Routing AlgorithmsTwo classes of Routing Algorithms (2)Optimizations in SIENAThe Filters PosetThe Filters Poset (2)Algorithms for Hierarchical ArchitectureAlgorithms for Hierarchical Architecture (2) : SubscriptionsPowerPoint PresentationAlgorithms for Hierarchical Architecture (3) : NotificationsAlgorithms for Hierarchical Architecture (4) : UnsubscriptionsAlgorithms for Hierarchical Architecture (5) : Advertisement forwardingAlgorithms for peer-to-peer ArchitectureAlgorithms in peer-to-peer Architecture (2) : SubscriptionsAlgorithms in peer-to-peer Architecture (3) : NotificationsAlgorithms in peer-to-peer Architecture (4) : Advertisement ForwardingEvaluationSimulation StudiesSlide 31Slide 32Slide 33Slide 34Slide 35Slide 36Future ChallengesDesign and Evaluation Design and Evaluation of a Wide-Area Event of a Wide-Area Event Notification ServiceNotification ServiceAntonio CarzanigaAntonio CarzanigaDavid S. RosenblumDavid S. RosenblumAlexander L. WolfAlexander L. WolfOverviewOverview IntroductionIntroduction Critical design issuesCritical design issues TopologiesTopologies Routing StrategiesRouting Strategies EvaluationEvaluation Simulation studiesSimulation studies Future ChallengesFuture ChallengesIntroduction (1)Introduction (1)Distributed event notification service Distributed event notification serviceIntroduction (2)Introduction (2)Key activities of an event notification Key activities of an event notification serviceservice–Notification selectionNotification selection–Notification deliveryNotification deliveryChallenges in a wide-area settingChallenges in a wide-area setting–Maximize expressiveness in the Maximize expressiveness in the selection mechanismselection mechanism–Maintain scalability in the delivery Maintain scalability in the delivery mechanismmechanismCritical Design IssuesCritical Design IssuesInterconnection topologyInterconnection topology–Hierarchy, adopted by JEDIHierarchy, adopted by JEDI–General graph, adopted by SIENAGeneral graph, adopted by SIENARouting algorithmRouting algorithm–Broadcast notificationsBroadcast notifications–Broadcast subscriptionsBroadcast subscriptions–Broadcast advertisementsBroadcast advertisementsProcessing strategyProcessing strategy–Pruning – Pruning – A server propagates a subscription only if it A server propagates a subscription only if it defines new notifications that are not covered by previously defines new notifications that are not covered by previously propagated subscriptions.propagated subscriptions.API and Semantics (1)API and Semantics (1)Interfaces of SIENAInterfaces of SIENA–publishpublish (notification n) (notification n)–subscribesubscribe (string identity, pattern expression) (string identity, pattern expression)–unsubscribeunsubscribe (string identity, pattern expression) (string identity, pattern expression)–advertiseadvertise (string identity, filter expression) (string identity, filter expression)–unadvertiseunadvertise (string identity, filter expression) (string identity, filter expression)NotificationNotification – a set of typed attributes – a set of typed attributes–Each attribute has a type, a name, and a value.Each attribute has a type, a name, and a value.API and Semantics (2)API and Semantics (2)FiltersFilters -- -- specify a set of attributes and specify a set of attributes and constraints on the values of those attributesconstraints on the values of those attributesPatternsPatterns – – a sequence of filters matched a sequence of filters matched by a temporally ordered sequence of by a temporally ordered sequence of notifications, each one matching the notifications, each one matching the corresponding filtercorresponding filterAPI and Semantics (3)API and Semantics (3)Two variants of the semantics of Two variants of the semantics of SIENASIENA–Subscription-based semanticsSubscription-based semanticsA notification A notification nn is delivered to an interested party is delivered to an interested party XX XX submitted at least one subscription submitted at least one subscription ss such that such that nn matches matches s.s.–Advertisement-based semanticsAdvertisement-based semanticsA notification A notification nn published by object published by object YY is delivered to is delivered to interested party interested party XX YY advertised a filter advertised a filter aa that that covers covers nn and and XX registered a subscription registered a subscription ss that covers that covers nn. .Architectures (1)Architectures (1)Hierarchical client/server architectureHierarchical client/server architectureAcyclic peer-to-peer architectureAcyclic peer-to-peer architectureArchitecturesArchitectures (2)(2)General peer-to-peer architectureGeneral peer-to-peer architecture Hybrid architecturesHybrid architecturesRouting Strategies used in SIENARouting Strategies used in SIENA To ensure delivery of notifications to To ensure delivery of notifications to interested parties that subscribe for them.interested parties that subscribe for them. Employs principles found in multicast Employs principles found in multicast routing protocols.routing protocols. Main Idea – Send Notification only towards Main Idea – Send Notification only towards event servers that have interested clients , event servers that have interested clients , possibly using shortest path.possibly using shortest path.Routing Strategies : Generic principlesRouting Strategies : Generic principles1.1.Downstream Replication Downstream ReplicationRouting Strategies: Generic Principles Routing Strategies: Generic Principles (2)(2)2. Upstream Evaluation2. Upstream EvaluationTwo Classes of Routing AlgorithmsTwo Classes of Routing Algorithms Subscription forwarding :Subscription forwarding : •Subscriptions set the path for notificationsSubscriptions set the path for notifications•Subscriptions are broadcast throughout the Subscriptions are broadcast throughout the networknetwork•Forms a spanning tree that connects Forms a
View Full Document