Dissemination and Synchronization for Mobility (and Beyond)OutlineIntro: Data DisseminationIntro: Data SynchronizationDiscussionTutorial Goals2. Architectural ConceptsArchitecture (continued)i) Types of NodesNetwork Componentsii) Data Delivery OptionsData Delivery MechanismsNetwork Transparencyiii) User ProfilesWhy are Profiles Needed?Profile ContentsExample ProfileSummary So Far3. Data DisseminationDissemination TopicsDissemination-Based Information Systems (DBIS)DBIS FrameworkDBIS ExampleDBIS ToolkitDBIS ComponentsPowerPoint PresentationMore on BrokersSlide 28DBIS Research IssuesXFilter: XML Document FilteringWhy XML-Based SDI?An XML-Based SDI SystemXPath as a Profile LanguageImportant XPath FeaturesXFilter ArchitectureXML Parsing and FilteringFilter EngineFSM RepresentationPath Node DecompositionHandling Multiple QueriesExamplesQuery Index ConstructionEnhanced AlgorithmsList Balance AlgorithmFSMs in List BalanceQuery Index in List BalancePrefilteringNested Path ExpressionsPerformance EvaluationScalability ExperimentsDocument Depth ExperimentsFilter ExperimentsXFilter SummaryRelated ApproachesRelated Approaches(continued)Approaches in ContextSummary of Data Dissemination4. SynchronizationWhy Synchronize?Synchronization TopicsPalm HotSync BackgroundHotSync ProtocolProtocol (continued)Problems with HotSyncDatabase-Supported SyncEDISON (continued)EDISON TopologyEDISON Protocol (1st Phase)EDISON (Phase 2)EDISON (Phase 3)EDISON SummarySyncML StandardSyncML Sync TypesSyncML (continued)“Data Recharging”Data Recharging - MotivationData Recharging (continued)Some Questions“Data Recharging” ProfilesFirst cut at Profile ModelProfile ExampleExploiting ProfilesOn-going Profile WorkRecharging - Research AgendaData Caching and ConsistencyEpidemic Protocol IllustrationDeno - Cetintemel and KeleherDecentralized CommitmentWrap UpAcknowledgementsDissemination and Synchronization for Mobility (and Beyond)Michael FranklinUC BerkeleyMDM Tutorial7 January 2001© 2001 Michael J. Franklin MDM 2001 Tutorial2Outline1. Dissemination vs. Synchronization2. Architectural Concepts–Types of nodes–Data Delivery Mechanisms–User Profiles3. Data Dissemination–DBIS Toolkit, Xfilter, Continuous Queries4. Synchronization–for PDAs: Palm HotSync, Edison, SyncML–Data Recharging–Consistency for weakly connected devices5. Wrap Up© 2001 Michael J. Franklin MDM 2001 Tutorial3Intro: Data Dissemination•disseminate –1. To scatter widely, as in sowing seed.–2. To spread abroad, promulgate. disseminate information•In a data management context, this refers to the proactive distribution of relevant data to users.•Examples:–News feeds, stock tickers, event broadcasts, SPAM, …© 2001 Michael J. Franklin MDM 2001 Tutorial4Intro: Data Synchronization•synchronize –1. To cause to occur or operate with exact coincidence in time or rate.–2. To cause to occur or operate at the same time as something else.•In a data management context this refers to making base data and device-cached data consistent.•Examples:–Palm HotSync, Email (?), disconnected operation© 2001 Michael J. Franklin MDM 2001 Tutorial5Discussion•From the definitions, you might think that the two concepts are completely unrelated, but are they?•Examples:–Email Lists/On-line communities–Groupware apps such as shared calendars–AvantGo•What are the essential characteristics that distinguish one from the other?•How related? How different?© 2001 Michael J. Franklin MDM 2001 Tutorial6Tutorial Goals•To identify common infrastructure to support large scale data distribution: dissemination and syncrhonization.•To describe recent and on-going research in supporting dissemination.•To describe existing synchronization protocols and future directions for them.•To outline avenues for continuing research and infrastructure development.© 2001 Michael J. Franklin MDM 2001 Tutorial72. Architectural Concepts•Dissemination and Sync are inherently distributed; – Both require a Network architecture.•A key concept is that of an Overlay Network1. “application-level” network built on top of Internet protocols; interacts with the “regular” internet.2. May use both public and private communication links.3. Exploits “Data Centers” deployed around the world.4. Content Routing can be done at the application level so can be based on application and data semantics.5. Caching, Prefetching, Staging, etc. can be done transparently.6. E.g., CDNs such as Akami, FastForward Networks© 2001 Michael J. Franklin MDM 2001 Tutorial8Architecture (continued)•We will focus on three key aspects of such architectures:1. Types of nodes in the system.2. Options for data delivery mechanisms.3. Representation of data needs and preferences through user profiles.© 2001 Michael J. Franklin MDM 2001 Tutorial9i) Types of Nodes•Clients–Interact with end user, may cache data and updates•Client Proxies –Deal with disconnection, provide network interface•Data Sources–The ultimate repositories for data•Intermediaries (“Information Brokers”)–Provide storage/caching, application level routing–value added data processing–communications transducing© 2001 Michael J. Franklin MDM 2001 Tutorial10Network ComponentsInternetprofilequeryresponseprofilequeryresponseDataSourcesInformationBrokersClientProxies© 2001 Michael J. Franklin MDM 2001 Tutorial11ii) Data Delivery Options•There are many ways to move data between sources and receivers:•Pull vs. Push–Does the data move because the receiver asked for it or because the source decided to send it?•Periodic vs. Aperiodic–Does the data move according to a predefined schedule or is movement event/demand driven?•Unicast vs. 1 to N–Does the data go to a single receiver or many?•Reliability Guarantees–best effort, guaranteed once, transactional…© 2001 Michael J. Franklin MDM 2001 Tutorial12Data Delivery MechanismsPushPullAperiodic PeriodicUnicast 1-to-nUnicast 1-to-nAperiodic PeriodicUnicast 1-to-n Unicast 1-to-nrequest/responseon-demandbroad-castpolling pollingw\snoopEmail listspublish/subscribePerson- alizedNewsBroad-castdisksDimensions are largely orthogonal – all combinations are potentially