1 Adaptive Push-Pull Disseminating Dynamic Web Dat

1AdaptivePush-Pull:DisseminatingDynamicWebDataPavanDeolaseeAmolKatkarAnkurPanchbudheKrithiRamamrithamPrashantShenoyDepartmentofComputerScienceandEngineering.DepartmentofComputerScienceIndianInstituteofTechnologyBombayUniversityofMassachusettsMumbai,India400076Amherst,MA01003fpavan,amolk,ankurp,[e-mail],[e-mail]sueinthedisseminationoftime-varyingwebdatasuchassportsscoresandstockpricesisthemaintenanceoftemporalcoherency.InthecaseofserversadheringtotheHTTPprotocol,clientsneedtofrequentlypullthedatabasedonthedynamicsofthedataandauser’scoherencyrequirements.Incontrast,serversthatpossesspushcapabilitymaintainstateinformationpertainingtoclientsandpushonlythosechangesthatareofinteresttoauser.Thesetwocanonicaltechniqueshavecomplementarypropertieswithrespecttotheleveloftemporalcoherencymaintained,communicationoverheads,statespaceoverheads,andlossofcoherencydueto(server)failures.Inthispaper,weshowhowtocombinepush-andpull-basedtechniquestoachievethebestfeaturesofbothapproaches.Ourcombinedtechniquetailorsthedisseminationofdatafromserverstoclientsbasedon(i)thecapabilitiesandloadatserversandproxies,and(ii)clients’coherencyrequirements.Ourexperimentalresultsdemonstratethatsuchadaptivedatadisseminationisessentialtomeetdiversetemporalcoherencyrequirements,toberesilienttofailures,andfortheefficientandscalableutilizationofserverandnetworkresources.KeywordsDynamicData,TemporalCoherency,Scalability,Resiliency,WorldWideWeb,DataDissemination,Push,PullI.INTRODUCTIONRecentstudieshaveshownthatanincreasingfractionofthedataontheworldwidewebistime-varying(i.e.,changesfrequently).Examplesofsuchdataincludesportsinformation,news,andfinancialinformationsuchasstockprices.Webproxycachesthataredeployedtoimproveuserresponsetimesmusttracksuchdynamicallychangingdatasoastoprovideuserswithtemporallycoherentinformation.Thecoherencyrequirementsonadataitemdependsonthenatureoftheitemandusertolerances.Toillustrate,ausermaybewillingtoreceivesportsandnewsinformationthatmaybeout-of-syncbyafewminuteswithrespecttotheserver,butmaydesirestrongercoherencyrequirementsondataitemssuchasstockprices.Aproxycanexploituser-specifiedcoherencyrequirementsbyfetchinganddisseminatingonlythosechangesthatareofinterestandignoringintermediatechanges.Forinstance,auserwhoisinterestedinchangesofmorethanadollarforaparticularstockpriceneednotbenotifiedofsmallerintermediatechanges.Intherestofthissection,we(a)describetheproblemoftemporalcoherencymaintenanceindetail,(b)showtheneedtogobeyondthecanonicalPush-andPull-baseddatadissemination,and(c)outlinethekey2contributionsofthispaper,namely,thedevelopmentandevaluationofadaptiveprotocolsfordisseminatingdynamic,i.e.,time-varyingdata.A.TheProblemofMaintainingTemporalCoherencyConsideraproxythatcachesseveraltime-varyingdataitems.Tomaintaincoherencyofthecacheddata,eachcacheditemmustbeperiodicallyrefreshedwiththecopyattheserver.Weassumethatauserspecifiesatemporalcoherencyrequirementtrforeachcacheditemofinterest.Thevalueoftrdenotesthemaximumpermissibledeviationofthecachedvaluefromthevalueattheserverandthusconstitutestheuser-specifiedtolerance.Observethattrcanbespecifiedinunitsoftime(e.g.,theitemshouldneverbeout-of-syncbymorethan5minutes)orvalue(e.g.,thestockpriceshouldneverbeout-of-syncbymorethanadollar).Inthispaper,weonlyconsidertemporalcoherencyrequirementsspecifiedintermsofthevalueoftheobject(maintainingtemporalcoherencyspecifiedinunitsoftimeisasimplerproblemthatrequireslesssophisticatedtechniques).AsshowninFigure1,letS(t),C(t)andU(t)denotethevalueofthedataitemattheserver,cacheandtheuser,respectively.Then,tomaintaintemporalcoherency(t)weshouldhavejU(t)S(t)j:PushorPullPushUserS(t)ServerProxyP(t)U(t)Fig.1.TheProblemofTemporalCoherencyThefidelityofthedataseenbyusersdependsonthedegreetowhichtheircoherencyneedsaremet.Wedefinethefidelityfobservedbyausertobethetotallengthoftimethattheaboveinequalityholds(normalizedbythetotallengthoftheobservations).Inadditiontospecifyingthecoherencyrequirementtr,userscanalsospecifytheirfidelityrequirementfforeachdataitemsothatanalgorithmthatiscapableofhandlingusers’fidelityandtemporalcoherencyrequirements(trs)canadapttousers’needs.Inthispaperwedevelopadaptivepush-andpull-baseddatadisseminationtechniques,tobeemployedbetweenaserverandaproxy,thatmaintainuser-specifiedcoherencyandfidelityrequirements.Techniquesfordisseminatingdatafromproxiestoend-usersarenotconsideredhere,sinceresourcessuchasnetworkbandwidthareoftenplentifulontheproxy-userdatapath.Sinceproxiesactasimmediateclientstoservers,henceforth,weusethetermsproxyandclientinterchangeably(unlessspecifiedotherwise,thelattertermisdistinctfromtheultimateend-usersofdata).3B.TheNeedforCombiningPushandPulltoDisseminateDynamicDataInthecaseofserversadheringtotheHTTPprotocol,proxiesneedtoperiodicallypullthedatabasedonthedynamicsofthedataandauser’scoherencyrequirements.Incontrast,serversthatpossespushcapabilitymaintainstateinformationpertainingtoclientsandpushonlythosechangesthatareofinteresttoauser/proxy.Thefirstcontributionofthispaper