Content-BasedCommunication:aResearchAgenda
AntonioCarzaniga†,‡
FacultyofInformaticsUniversityofLugano6900Lugano,Switzerland
†
‡
∗
CyrusP.Hall†
DepartmentofComputerScience
UniversityofColoradoBoulder,Colorado80309-0430
ABSTRACT
Acontent-basedpublish/subscribesystemisamessage-or-ientedcommunicationfacilitybasedontheideaofinterest-drivenrouting.Amessage,publishedbythesenderwithoutasetdestination,isdeliveredtoanyandallthereceiversthatexpressedaninterestinitscontent.Werefertothiscommunicationstyleandtothedistributedinfrastructurethatrealizesitascontent-basedcommunicationandcontent-basednetworking,respectively.Inthispaperwereviewwhatweconsiderthefoundationsofcontent-basednetworking,in-cludingsomeofthemajoradvancesofthepastyears.Wethenpresentavisionforfurtherresearchinthisareaaswellasforthepracticalrealizationofacontent-basednetwork.Inparticular,wediscusstheimplicationsofcontent-basedcommunicationforthenetwork,themiddleware,andappli-cations.
Keywords
Distributedpublish/subscribesystems,content-basedcom-munication,content-basednetworking.
1.INTRODUCTION
Thepublish/subscribecommunicationstyleisbasedontheideathatreceiverssubscribetoinformationofinterest,thatis,theyspecifytheinformationtheyintendtoreceive,whilesenderssimplypublishinformationwithoutaddressingittoanyparticularreceiver.Athird-partycommunicationsystem,oftencalledbrokerordispatcher,isthenresponsi-blefortransmittingpublishedinformationtoallinterestedreceivers.Thiscommunicationstyleisalsooftenreferredtoas“eventnotification,”wherebypublishedinformationisassumedtodescribe“events.”Consistently,applications∗ResearchsupportedinpartbytheUSNationalScienceFoundation,USArmyResearchOffice,EuropeanCommis-sion,andSwissNationalFundunderagreementnumbersANI-0240412,DAAD19-01-1-0484,IST-026955,and200021-109562.
Permissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprofitorcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationonthefirstpage.Tocopyotherwise,torepublish,topostonserversortoredistributetolists,requirespriorspecificpermissionand/orafee.
SEM’06,November10,2006,Portland,Oregon,USA.Copyright2006ACM...$5.00.
thatusethiscommunicationstylearealsosaidtoconformtoanevent-basedarchitecture,andarealsoreferredtoasevent-basedapplications.
Inthispaper,asintheresearchwehaveconductedinthepastyears,weignoretoalargeextentboththenatureoftheinformationbeingtransmittedandthenatureandarchi-tectureoftheapplicationsthatproduceandconsumesuchinformation.Instead,wefocusonthenovelmodeofcom-municationembodiedinpublish/subscribecommunication,andonthedesignandimplementationofacommunicationsystemthatrealizesthismodeofcommunication.
Ourfirstfundamentalobservationregardingpublish/sub-scribecommunicationisthatitisverysimilartothecom-municationstyleofstandardnetworkservicessuchasIPmulticast.Infact,subscribingisequivalenttojoiningamulticastgroup,andpublishingisequivalenttosendingtoamulticastgroup.TheonlydifferenceisthattheaddressingschemeofIPmulticastdefineswhatamountstoapartitionofthespaceofdatagram,whilemodernpublish/subscribesystemsaregenerallyassumedtobecontent-basedsystemsthatallowexpressiveconditionsoverthecontentofpublica-tions.Thisinturnallowssubscriptionstodefinearbitrarysubsetsofthespaceofpublications.
Toexemplifythisdifference,considerasimplistichighwaytrafficcontrolsystemconsistingoftrafficsensorsandsup-portingprivatemotoristsaswellaspublic-safetypatrols.East-boundandWest-boundmotoristswouldbeinterestedinreceivingaccidentreportsfortheirrespectivedirections,whilehighwaypatrolswouldwanttoreceivebothtypesofalerts.WithIPmulticast,thedesignerofthesystemwouldhavetodecidebetweenalargeandasmallgranularityofmulticastgroups.Withlargegroups,allalertswouldbesentoncetoasinglegroup,motoristsandpatrolswouldjointhisgroup,andmotoristswouldhavetofilteroutalertsregardingtheoppositedirection.Withsmallgroups,East-boundmotoristswouldjoinagroupforalertsintheEastdirection,etc.,whilepatrolswouldjoinbothgroups,andalertswouldhavetobesenttobothgroups.Thefirstso-lutionfavorsthemulticastinfrastructureattheexpenseofapplications.Thesecondsolutionisbetterforapplications,butputsasignificantburdenonthemulticastinfrastructure.Inacontent-basedpublish/subscribesystem,thisproblemwouldhaveamuchsimplersolution:trafficsensorswouldpublishonce,andapplicationswouldalsosubscribeoncewiththeirspecificandpossiblyoverlappinginterests.
Inessence,wearguethatpublish/subscribecommunica-tionisnotspecialbecauseofitspublish/subscribenature,butratherbecauseofitscontent-basedaddressingscheme,
五道口生活网 www.wdklife.com 五道论坛（五道口人自己的论坛） www.wdklife.com/bbs 通洲生活网 www.85118.com
五道口生活网 www.wdklife.com 五道论坛（五道口人自己的论坛） www.wdklife.com/bbs 通洲生活网 www.85118.com
whichismoreexpressivethanthe“channel-based”schemeusedbyIPmulticast.
Thisobservationleadustoadoptandpromoteanewviewandanewterminology.Firstofall,weviewapub-lish/subscribesystemasacommunicationsystem.There-forewedroptheterms“publishers,”“subscribers,”and“no-tifications”or“events.”Insteadwetalkaboutmessages,senders,andreceivers.Wethendefinetheinterfaceofthiscommunicationservicebyexplicitlyreferringtoitscorefunc-tionality,whichistoallowreceiverstodeclaretheirinter-estsintermsofarbitrarysetsofmessages.Thus,wede-fineaninterfaceconsistingoftwomainfunctions:send-message(msg),whichallowsasendertosendamessage,andset-predicate(p),whichallowsareceivertodeclarethesetofmessagesthereceiverisinterestedin.ApredicatepisatotalBooleanfunctiondefinedontheuniverseofmessages,sothesetofmessagesofinterestis{m:p(m)}.Werefertothemodeofcommunicationdefinedbythisinterfaceascontent-basedcommunication.
Havingdefinedcontent-basedcommunicationintermsofitsserviceinterface,wefocusonitsrealizationasadis-tributedsysteminwhichthetransmissionofmessagesiscontrolledbyamoreorlessdecentralizedalgorithm.Inthiscontext,weadoptaviewthatonceagainisinspiredbymod-erncommunicationnetworks.Oursecondobservationistoviewadistributedimplementationofacontent-basedcom-municationservice(andadistributedcontent-basedpub-lish/subscribesystem)exactlyasapacket-switchednetwork.Thus,werefertoadistributedimplementationofacontent-basedcommunicationserviceasacontent-basednetwork.Inparticular,weassumeaninterconnectionofrouters,wheretheconnectionsbetweenroutersmaybephysicallinksoroverlaylinks(thisdistinctionisinessentialatthispoint,althoughitisclearlyimportantwhendesigninganactualsystem).Wethencallcontent-basedroutingthedistributedalgorithmthatcollects,propagates,assembles,andtrans-formsreceiverpredicatesaswellastopologicalinformation(e.g.,linkcosts)tothencompilerouter-localforwardingfunctions.Wecallcontent-basedforwardingtherouter-localalgorithmthat,basedontheinformationestablishedbytheroutingalgorithm,processesincomingmessagestodecidetowhichnext-hoproutersortowhichlocalapplicationstopassthemessage.
Admittedly,thevisionofacontent-basednetworkmaynotbesoprofoundinandofitself.Nevertheless,webelievethatithelpstostructureourresearcheffortsinthisarea,andtorelatethemtothenumerousrelevantresultsavailablefromthenetworkingliterature.
2.RESEARCHQUESTIONS
Thefollowingsectionsdescribeanunsortedlistofopenproblemsandideas,whichwebelievetobeinterestingandimportantintheareaofcontent-basednetworking.
2.1BasicInterface
Theideaofcontent-basedcommunicationrestsontheas-sumptionthatsendersandreceivers“connect”bysomehowspeakingthesamelanguage.Morespecifically,sendersandreceiversmustagreeonthesyntaxandsemanticsofthemessagestheysendandofthepredicatestheydeclare.Oth-erwise,sendersmightnotcommunicatetoreceiverswhentheyshould,ortheymightalsocommunicatewhentheyshouldnot.Forexample,atrafficsensorapplicationmight
send[alert=traffic,level=intense]whileacontrolapplica-tionmightrequest[application=traffic,alert=congestion,intensity>2].Inthiscase,thetwoapplicationswillnotcom-municate.Noticethatwhatisimportantinthiscaseisnotthelow-levelsyntaxofmessages.Obviously,thatmustalsobeagreedupon,butweviewthatasaminorengineeringissuethatmountstoagreeingonabasicexternalrepresen-tationformat.
Theessenceofthisproblemgoeswellbeyondcontent-basedcommunication,andbeyondinformationsystemsingeneral.Noticeinfactthatthisproblemisanalogoustothatoffindingaddressesintraditionaladdress-basednetworks.Networkstypicallyprovidealook-upservice(e.g.,DNSinIPnetworks)wherebyaddressescanbesearchedforbyname,whichhelpsbecausenamesaremoreeasilyrememberedandcommunicatedbyhumanbeings.However,alook-upsystemdoesnotsolvetheessentialproblemoffindingaddresses,whichissimplyshiftedfromthespaceofaddressestothespaceofnames.
Themostcommonapproachtosolvethisproblemistomakeitpossibleandconvenientforsendersandreceivestoagreeonterms(semantics)andstructure(syntax),butthenleavetheburdenoftheactualagreementtohigher-levelsys-temsorprotocols.Webelievethatthisremainsthemostsensibleapproach.However,wenoticethatcurrentsys-temsimplementthisapproachinsuchawaythatsendersandreceiverssharethisresponsibility.Inotherwords,bothsendersandreceiversmustmakeanefforttoreachamid-waypointofcontact.
Moreconcretely,considertheinterfaceofcurrentcontent-basedcommunicationsystems.Allthesystemsweknowofdefineastructureformessagesandapredicatelanguagethatisbasedonthatstructure.Forexample,somesys-temsstructuremessagesasXMLdocuments,anduseselec-tionpredicatesbasedonXPathexpressions.Othersystemsstructuremessagesastuplesofnamedattributes,anduseSQL-likeexpressionsforpredicates.Inthefirstcase,sendersmustchooseaspecificXMLschema(orsimplyasetoftagnames)andreceiversmustwriteXPathexpressionsbasedonthesameschema(ortags).Similarlyinthesecondcase,sendersmustchooseattributenames,andreceiversmustrefertothesameattributenamesintheirpredicates.
Ourviewisthatthis“meet-in-the-middle”approachag-gravatestheproblem,andthatabetterapproachistoshifttheresponsibilityforanagreementalmostcompletelyto-wardsreceivers.Specifically,weproposetoremovecon-strainingmessagestructures,givingsendersmaximumau-tonomyastohowtheyexpressinformation,whileatthesametimegivingreceiversanexpressivelanguagetoselectmessagesoverthepotentiallymanywaysthatsendersex-pressthemselves.
Wehaverecentlystartedworkingonthisnewapproach,andwewillpresentheresomeofourinitialresults.How-ever,beforedoingthat,weshouldclarifyourpositionwithrespecttotherisksofthisapproach.Aswehavearguedinthepast[4],therearegoodreasonstostructuremes-sagesandtolimittheexpressivenessofpredicates.Oneisthatmessagestructuresandsimplepredicatesallowforef-ficientimplementationsofthematchingfunction,whichisacrucialcomponentincontent-basedforwarding.Anotherbenefitofhavingalimitedformofpredicatesisthatrouterscanreasonaboutpredicates,andcancombine,approximate,andindexthemtomaketheroutingproblemtractableon
五道口生活网 www.wdklife.com 五道论坛（五道口人自己的论坛） www.wdklife.com/bbs 通洲生活网 www.85118.com
五道口生活网 www.wdklife.com 五道论坛（五道口人自己的论坛） www.wdklife.com/bbs 通洲生活网 www.85118.com
large-scalenetworks.So,onemightwonderwhetherwearenowproposingtoignorethecomplexitiesofforwardingandrouting.Thisisnotwhatweareproposing.Instead,ourin-tendistorevisitthetrade-offsbetweenexpressivenessandscalabilityinanattempttofacilitatecontent-basedcommu-nication.
Ourfirststepinthisdirectionwastoexperimentwithpredicatelanguagesthatincluderegularexpressions,andinparticularwechoseandrefinedaregularexpressionlan-guagethatisamenabletomatchingalgorithmsthatarefastinthemostcommoncases.Specificallyintermsofpredi-catelanguage,westartedfromtheconcretecaseoftheSienaFastForwardingalgorithm(SFF),whichimplementsatypi-calpredicatelanguagebasedondisjunctionsofconjunctionsofattribute-constraints,andweexploredthreewaystouseregularexpressions.1
•Regularexpressionsoverattributevalues:regularex-pressionsaresimplyaddedasanewoperatorforcon-straintsoverstrings.Forexample,inawebcachingapplication,areceivercouldrequestupdatestoalltheURLsmatchingagivenexpression.Forexample,[url=regex/php(-[0-9.]*)?\\.ini$/].•Regularexpressionstomatchattributenames:acon-straintcouldrefertothevarietyofattributesmatchingagivenregularexpression.Thiscaseisspecificallyin-tendedtoimproveovertherigidstructuredefinedbyattributenamesinpredicates.•Regularexpressionsoverflatmessages:takingtheideaofregularexpressionsincontent-basedcommunicationtotheextreme,wecouldhavefree-textanduseregularexpressionsoverthatwhole,flatmessagecontent.Thesevariationsoverthepredicatelanguagewouldre-quiremoreorlessradicalchangestothecoreinfrastructure.Thefirstextensionrequirestheimplementationofaregu-larexpressionmatcher,butdoesnotrequireanychangesintheroutingorforwardingalgorithms.Infact,wehavealreadyimplementedthematcherinarecentversionofourSienaFastForwardingmodule.Ourimplementationusesamodifiednon-deterministicfinite-stateautomaton(NFA).AllregularexpressionsinthesystemarecomposedintoasingleNFAusinganinitialεtransition.Thisdatastructurehasprovedtobequitefast,forwardingupwardsof15MB/sonmanyreal-worldworkloads(systemmonitoringandspamfiltering).Wehavenotconsideredtheimplicationstotheroutinglayeratthistime.
Intheothertwocases,bothroutingandforwardingal-gorithmswouldhavetoundergosignificantchanges,andpossiblyberedesignedcompletely.
Goingevenfurtherwiththeideaoflessconstrainingmes-sagesandmoreexpressivepredicates,wealsoenvisionacontent-basedcommunicationmodelwherepredicatesareprobabilisticinnature.Apartfromthepotentialincreaseincomplexityfortheforwardingfunction,thisideaseemstobeincontrastwithmuchofthecurrentworkoncontent-basedforwarding,wherefalse-positivesaregenerallyassumedtobeundesirable.Whilewedonotdirectlydisagreewiththisview,webelievethatcontent-basednetworkingisalsoap-plicableinareaswheretheconceptofmatchingapredicateisfuzzyatbest.Oneclearmotivatingexampleofsucha
1
spaceisthenumberboomingsocialnetworkingsites.Imag-ineauserattemptingtofindadateviaanon-linedatingservice.Theyenterinformationdetailingtheiridealpartner(apredicateifyouwill),butyettheywouldneverexpectanexact“match,”leasttheynevergoondate.Insteadtheyarelookingfor“fuzzy”matches,includingthoseuserswhogenerallyfittheirprofile.
Manyalgorithmshavebeendevelopedtoimplementvar-iousformofprobabilisticpattern-matchingfunctions.Forexample,manycommoninformationretrievaltechniquesarebasedontermvectorscombinedwithnatural-languagepro-cessing.However,mostofthesetechniquesfocusonthetrainingandcreationofmodels,andarenotamenabletoindexingwithinaforwardingengine.Itmightbeinterest-ingtostudyspecificalgorithmsorclassesofalgorithmsthatimplementprobabilisticmatchersandthatcanbeexecutedonnumerouspatternswithsublinearcomplexityinthenum-berofpatterns.
Notethatprobabilisticmatchingbyitselfdoesnotelimi-natetheproblemofsendersandreceiversagreeingonmes-sagestructureandterminology.Nevertheless,severalproba-bilisticmatchingalgorithmsarethemselvestoleranttodatasetsinwhichattributenamesand/orpositionschange(e.g.,connectionistapproachestorecognition).Thisseparationofconcerns,wheretheprobabilisticmatchingalgorithmdealswithsmallsemanticsinconsistenciesandthecontent-basedmatcherdealswiththegeneralandwidersearchspace,mayinfactleadtobetterandmoreflexiblecontent-basedsys-tems.
Weenvisionroutingincontent-basednetworkswithprob-abilisticmatchingtolookradicallydifferentthanexistingnetworks.Whereascurrentcontent-basednetworksareei-therhierarchicalorbasedoncoverageproperties,routinginthepresenceofprobabilisticmatchingcouldandprobablyshouldbebasedondifferentproperties.Onesuchpropertyweareexploringisameasureofproximitybetweeninter-ests.Specifically,almostallclassifierscanoutputaformofdistancebetweentwoinputs,inthiscasethepredicateandamessage,ortwopredicates.Bycomparingpredicatestoeachotherwecanstructurenetworksbasedonlinksofvaryingdistance.Wearecurrentlydevelopingasystemthatimplementssucharoutinglayerusingadistributedcluster-ingalgorithmspecificallytargetedatsmall-worldnetworks.
2.2Routing:InternetworkingandPolicies
http://www.cs.colorado.edu/serl/cbn/forwarding/
Theideaofaglobal,planet-widecontent-basednetworkisveryappealing.Likeotherresearchers,wehaveenvisionedsuchalarge-scalesystemasanopennetwork,characterizedbystandardprotocolsandalsobyuniformandgenerallypermissiveaccessandtransitpolicies.Thisideahassomemerits,ifnothingelsefortheviewsthatfueledthedevel-opmentofotherlargescalenetworkssuchastheInternet,oreventhetelephonenetwork.However,ifwetakealookattheevolutionofthosesystems,wecannotfailtonoticethatlargenetworkstendtoevolvenaturallyintohierarchi-calsystemsmadeupofautonomoussystems,whichinturntendtocreatebarriersforcommunication.
Webelievethatthesesubdivisions,groupedandinter-connectedmoreorlessaccordingtonaturalgeographicandsocialboundaries,areunavoidableandtosomeextentareevendesirable.Ourconclusionisthereforethatascalabledesignforacontent-basednetworkmustincludeeffectivemethodstoestablishandtoenforcepoliciesforthetrans-
五道口生活网 www.wdklife.com 五道论坛（五道口人自己的论坛） www.wdklife.com/bbs 通洲生活网 www.85118.com
五道口生活网 www.wdklife.com 五道论坛（五道口人自己的论坛） www.wdklife.com/bbs 通洲生活网 www.85118.com
missionandhandlingofmessagesacrossadministrativedo-mains.FollowingonceagainouranalogywithIPnetworks,wemustbeabletoimplementtheequivalentofpoliciesoftheBorderGatewayProtocol(BGP).Inparticular,anau-tonomoussysteminacontent-basednetworkmustbeabletodeterminewhichmessagesaretransmittedtoothersys-tems,andwhichmessagesareacceptedfromothersystemsforlocaldeliveryand/orfortransit.Similarly,administra-tivepoliciesshouldbeabletodeterminewhichpredicatesarepropagatedoutsideanautonomoussystem,andinwhatform.
Itisnotcompletelycleartouswhichoftheseproblems,ifany,wouldposefundamentallynewresearchquestions.Clearly,somemechanismscouldberealizedbyengineeringexistingarchitecturesandalgorithms.Forexample,estab-lishingfilters,whetherforoutgoing,incoming,ortransitmessages,seemsstraightforward.Infact,thepredicatelan-guageimplementedbythenetworkitselfwouldprobablysufficeforthistask.Ontheotherhand,designingagoodcontent-basedroutingprotocolthatinteractssmoothlywiththevariousfilteringpoliciesdoesnotseemtrivial.There-fore,weproposetostudythedesignofafunctionalandefficientpolicy-controlled,content-basedroutingprotocol.
•Inherentpropertiesofcontent-basedrouting.Ideally,wewouldalsoliketounderstanduniversalpropertiesofcontent-basedrouting.Forexample,wewouldliketoestablishsomelower-boundsforthecomplexityofcontent-basedrouting.Betteryet,wewouldliketocharacterizethetrade-offsbetweenforwardingcostsandmemoryorcontrol-trafficcosts.Non-triviallowerboundsarenotoriouslyhardtofind,sothisisasome-whatambitiousgoal.Nonetheless,weconsiderites-sentialtogainanin-depthunderstandingofcontent-basedrouting.Withthesegoalsinmind,wehavebeguntoformulateatheoryofcontent-basedrouting[3].Onceagain,wegotinspirationsandideasfromthequiteextensiveliteratureontheoreticalapproachestotraditional(unicast)routing.OurinitialapproachwastoextendthestandardnetworkandroutingmodelofPelegandUpfal[9],andbasedonthismodel,studythememoryrequirementsofvariousroutingschemesatsteady-state.Thismeansthememorynecessarytoimplementtheforwardingfunctionsrealizedbyrouters(totalfortheentirenetwork,ormaximumforanindividualrouter).Intuitively,thisistheamountofforwardingstateproducedandmaintainedbyaroutingprotocol.
Therationaleforthischoiceoffocusistwofold.First,theamountofforwardingstategivesagoodindicationofthecomplexityofforwarding.Second,thememoryrequirementatsteadystateisindependentofthedynamicsofboththenetworkanditsapplications,andthereforecharacterizesanessentialpropertyofthechosenroutingscheme.Inordertoanalyzethiscomplexity,wealsointroducetheconceptofdisjunctionadvantage,whichexpressesthememorysavingsobtainedbycombiningpartially-overlappingpredicates.
2.3TheoreticalFoundationsofContent-Based
Routing
Theproblemofcontent-basedrouting,albeitnotexplic-itlycalledthatway,hasbeenstudiedquiteextensively[1,2,5,6,8,11].Mostifnotallthesestudies,includingourown,focusonconcreteroutingprotocols(orcombinedrouting-forwardingprotocols)andusesimulationtoanalyze,compare,andvalidatesolutions.Thisapproachisstandardpracticeinthedesignofnetworkprotocols,and,tobesure,weconsideritverymuchvalidinthecontextofcontent-basednetworking.However,wealsoseetheneedtoframetheproblemofcontent-basedroutingwithinamoregeneralandsolidtheory.Suchatheorywouldhelpus—indeed,itwouldbenecessary—tounderstandmorefundamentalprop-ertiesofroutingprotocols.
•Protocolcorrectness.Asimulationforanetworkpro-tocolisequivalenttotestingforsoftware:itmayun-coverincorrectbehaviors,butitcannotproveapro-tocolcorrect.Inordertodothat,wemustfirstdefinecorrectness.Thenwemustdeducecorrectnessfromasuitablerepresentationoftheprotocolandthenetworkenvironment.Inshort,inordertoanalyzeprotocolcorrectness,wemustformalizecontent-basedrouting.•Protocolcomplexity.Simulationanalysesaredifficulttoreadbecauseofthemanyconfigurationparametersthatdefineeachexperiment.Evenifoneunderstandstheperformancetrendobservedthroughsimulationinasectionoftheparameterspace,itisbynomeansclearwhetherandhowsuchtrendscantellanythingaboutotherpartsoftheparameterspace.Also,sim-ulationsmaynotcaptureessential,implementation-independentpropertiesofaprotocol.Havingaformalmodelofnetworksandprotocolswouldallowustofor-mulatemoregeneralstatementsaboutthecomplexityofprotocols.Inparticular,insteadofshowingthecost(e.g.,intermsofcontrolmessages)ofaprotocolforafewnetworksizes,wewouldliketocharacterizetheasymptoticcomplexityofthatprotocol.
2.4Routing:EngineeringPlusNewIdeas
Afairnumberofideashavebeenexploredincontent-basedrouting.Nonetheless,webelievethatalotremainstobedoneinthisfundamentalarea.Ourownplanistofol-lowtwooppositeresearchdirections.First,webelievethatexistingprotocolsandideasshouldbestudiedindepth,go-ingbeyondsimulation,exploringdeploymentsondistributedtestbeds,andfocusingonprotocolengineering.
Theseconddirectionleadsamountstowhatissometimesreferredtoas“radicaldesign.”Inparticular,wewouldliketoquestionsomebasicassumptionsandweintendtoexplorecompletelynewideasoroldideasthataregenerallyconsid-eredinapplicableorimpractical.Ratherthanexploringanyspecificideaindetailhere,wewilllistsomeinbreadth-firstorder.
2.4.1Peer-to-PeerNetworkModels
Manyhavestudiedwaystoimplementcontent-basednet-workingontopofsimpleandwell-understoodpeer-to-peernetworkssuchasdistributedhashtables(DHTs)[12,13].Weliketheseideas,andbelievethatthisareaofresearchislikelytoevolve,moreorlessfollowingtheevolutionofpeer-to-peersystemsthemselves.Inparticular,researchincontent-basedroutingonpeer-to-peeroverlaysshouldlookatthefollowingquestions.
•Howdoesthecombinationofcontent-basedroutingandthepeer-to-peernetworkbehaveundersignificantchurn?
五道口生活网 www.wdklife.com 五道论坛（五道口人自己的论坛） www.wdklife.com/bbs 通洲生活网 www.85118.com
五道口生活网 www.wdklife.com 五道论坛（五道口人自己的论坛） www.wdklife.com/bbs 通洲生活网 www.85118.com
•IsitpossibletouseDHTsandstillmaintainsomekindoflocalityprinciple,whereshortdistancesinthecontent-basednetworkcorrespondtoshortdistancesintheP2Poverlay?•Howdoesthecombinationofcontent-basedroutingandthepeer-to-peernetworkbehaveinthepresenceofnon-completeoverlays?ManyP2Psystemsarede-signedundertheimplicitassumptionthateverypeercanconnectdirectlytoanyotherpeer.WithIPover-lays,thisispossibleonlyintheory.Inpractice,linksareverymuchasymmetricbecauseoftheprevalenceoffirewallsandnetwork-addresstranslation.•CanDHTsworkonstatically-configured,non-fullnet-worktopologies?Andwhataretheimplicationsoncontent-basedrouting?•Intuitively,itwouldbeeasiertoimplementcontent-basedroutingontopofastructuredpeer-to-peersys-temwheretheaddressingscheme(e.g.,thehashvaluesinaDHT)maintainsomeofthepropertiesofpredi-catesincontent-basedcommunication.Arethereanygood“structures”forpeer-to-peersystemsthatpre-servethe“content-basedrelations”betweenaddresses?Weareexploringsomecombinationsoftheseideas.Specif-ically,weareworkingonnovelpeer-to-peer“structures”constructedonthebasisofcontent-basedaddressesasde-finedbysomeprobabilisticmatchingfunctionasdiscussedinSection2.1.Inparticular,theideahereistobuildatypicalpeer-to-peerindexwhereidentifiersamounttotermvectors,anddistancesaredefinedbyameasureofsimilaritybetweentermvectors.
isverydifficultinthesecasesbecauseroutinginformationisveryquicklyinvalidatedbyfast-pacedchangesinthenet-work.
Extremelyfluidnetworksleadustoconsiderwhatwecallalmost-zero-informationrouting.Theideaistorediscoverroutingprotocolsthatarebasedonlocaldecisionsthatarealmostcompletelyobliviousoftopologyandnon-localpred-icates.Anapproachthattakesthisideatoanextremeistoroutemessagesonarandomwalk.Startingfromthisendofthespectrum,ourintuitionisthatevenlittleroutinginfor-mationcouldstrikeagoodbalancebetweenthewell-knownboundsofrandomwalksandthemoreexpensiveroutingprotocolsbasedonshortest-pathroutes.Atthispoint,wedonothaveanyconcreteprotocolunderdevelopment,butweareplanningtoexplorethisidea.
2.5PrivacyforInterests
2.4.2New,OldIdeasforRouting
Weseeanopportunitytoapplywell-knownprotocolsandothersimple,perhapsna¨ıveprotocolstocontent-basedrout-ing.Theessenceofthisideaisthattheseapproacheshavenotevenbeenconsideredbecausetheirseeminglyhighcost(orloweffectiveness).However,webelievethattheymerittobereconsideredmoreopenly.
Thefirstideahereistorevivesimplebroadcastprotocolstotransmitcontent-basedroutinginformation.Forobviousreasonsofcost,thisisgenerallyconsideredabadideainacontent-basednetwork.However,wearenotconvincedthatthecostsarereallythathigh,especiallyforrelativelysta-blenetworks.Infact,followingonceagaintheinspirationofInternetrouting,webelievethatacontent-basedlink-stateroutingprotocolmightbethebestoptionforsmallandmedium-sizenetworks.Theobviousadvantageofthisapproachisthatitwouldgiveeachrouteracompleteandupdatedviewoftheentirenetwork.Thiswouldthenal-lowrouterstoimplementvarioustypesofroutingschemes,includingschemesthatachieveoptimal(e.g.,functionallycorrectandlatency-minimal)delivery.Inourrecentstudyofmemoryrequirementsofcontent-basedrouting,wedefinetwonewschemesthatdojustthat[3].
Thisfirstideaisbestappliedtonetworkswherethetopol-ogyisverystableandwherecontent-basedinformation(i.e.,predicates)arealsorelativelystable.Anotherideaistofo-cusonanoppositescenario,wherebothtopologyandpred-icatesareveryfluid.Thiscasecorresponds,forexample,toanad-hocnetworkofmobiledevices,butalsoitmayap-plytohigh-churnpeer-to-peernetworks.Effectiverouting
Oneofthefundamentalproblemsincontent-basednet-working,asinanycommunicationservice,isprivacy.How-ever,theprivacygoalinthiscontextdifferssignificantlyfromthatofatraditionalcommunicationservice.Inthetraditionalmodel,AlicesendsamessagetoBobanddoesnotwantanyoneelsetoreadit.ThenetworkmustbetoldtheaddressofBobinordertodeliverthemessage,butthecontentofthemessagecanremainhiddenfromthenetwork.Incontent-basednetworking,Alicedoesnotspecifyadesti-nation,butinsteadsimplysendsamessagetothenetwork.Alice’sintentistohavethecontentofthemessageexaminedinordertohaveitdeliveredtointerestedparties.
Onthereceiverside,Bobdoesnotpassivelywaitformes-sagesaddressedtohim,butinsteadactivelyrequeststhatthenetworkselectmessagesofinterestonhisbehalf.TheproblemisthatBobmusttellthenetworkhisinterests,andhemightconsiderthisdisclosureofpersonalpreferencesanunacceptableviolationofhisprivacy.
Privacyincontent-basednetworkingisthereforeprimarilyaproblemofthetrustrelationshipbetweenreceiversandthenetwork,whichleadstoacontradictoryandchallenginggoal:Howdowedesignaneffectiveandefficientcontent-basednetworkingserviceinwhichreceiverscanhidetheirpreferencesfromthenetworkandyetthenetworkcandeliverallandonlythemessagesinwhichthereceiverisinterested?Wehavebeenstudyingthisproblemforquiteawhile,andinfactwealreadydesignedandimplementedanencod-ingschemethatattemptstohidemessagesandpredicateswhileatthesametimeallowingrouterstoefficientlymatchmessagesandpredicates.Thisencodingalsoallowsrouterstoverifytheinclusionrelationbetweenpredicateswiththesameefficientalgorithms.Thisschemeisbasedonacatego-rizationoffiltersandmessages,andonBloomfiltersbuiltwithcryptographichashfunctions.Inadditiontotheen-coding,wedevelopedseveralmatchingalgorithmsbasedonthepredicateandmessageencoding.
Ourapproachseemspromising.However,itwasdevel-opedfromapurelypracticalandinformalperspective,with-outthenecessarybasisofaprovablesecuritymodel.In-spiredbytheworkofRaiciuandRosenblum[10],weareplanningtostudyourschemeunderthemodelproposedbyChangandMitzenmacher[7].
2.6WorkloadsandNetworkModels
Methodicalevaluationofideasincontent-basednetwork-ingiscrucial.Thisisatruismthatisstillworthmentioning.
五道口生活网 www.wdklife.com 五道论坛（五道口人自己的论坛） www.wdklife.com/bbs 通洲生活网 www.85118.com
五道口生活网 www.wdklife.com 五道论坛（五道口人自己的论坛） www.wdklife.com/bbs 通洲生活网 www.85118.com
Theevaluationofcontent-basednetworkingprotocolsandsystemsisoftendifficultduetothelackofdirectexperiencewithrealdeployments,andthereforeforthelackofmodelsofapplicationsandnetworks.Obviously,researchersdotheirbestindividuallytoevaluatetheirideas.However,theseevaluationsshouldbeunderstoodandgenerallyacceptedbyotherresearchers.Asafirstrequirement,regardlessoftheirvalidity,experimentsmustberepeatablebyothers.Thisfirstissuedoesnotraiseresearchquestions,butisratheramatterofmethodandopenness.Onethingthatcouldhelpistofullypublishallthematerialsrelatedtoexperiments.Wehavetriedtodojustthatconsistentlyinrecentyears,bypublishingthecodeandtheworkloadsthatdefinestheexperimentalresultswepublish,andweencourageotherstodothesame.
Thesecondissuehereisthatthevalidityofanexperi-mentdependsonthevalidityofthemodelsthatdefinetheexperimentalsetup.Generallyspeaking,theproblemisnotthelackofmodels,butratherthelackofwidelyacceptedmodels.Thissuggeststwotypesofefforts.Oneisatyp-icalcommunityeffort,wheremodelsgainacceptancebe-causetheyareformulatedanddiscussedbycommitteesofresearchersratherthanbyindividuals.Thesecondeffort,whichiswhatweproposehereasalineofresearch,isbasedontheideathatgoodmodelscanbeconstructedbasedonbothrealandsyntheticapplicationsandscenarios.Thisresearchwouldamounttostudyingandcharacterizingap-plicationsandnetworksthat,althoughtheydonotcurrentlyusecontent-basedcommunication,maybeconvenientlyre-designedtodothat.
plexedinterfacedescribedabove.Anapplicationcre-atesoneormorecontent-basedsockets,anddynami-callybindsthemtoasetofsubscriptions.Ofcourse,justlikenormalsockets,content-basedsocketswouldhavetheirownmessagequeues,whichtheapplica-tioncanaccesswiththetypicalsynchronousorasyn-chronous,blockingornon-blockingreadoperations.•Contentdirectory:thisserviceshouldaidapplicationsinfindingotherapplicationsorhigher-levelservices.Ataminimum,thisserviceshouldprovideadirectoryoftermsinusebysenders.ThisservicecouldbeseenastheequivalentoftheDomainNameService(DNS).Itisalsoeasytoimaginemoresophisticatedservicesbasedonthesemanticrelationsbetweenterms.Inadditiontothesebasicservices,weenvisionalargesetofhigher-levelservices.Thefollowingarejustafewideasinthisdirection.
•Synthesisofpredicatesanddataadaptation:complexapplicationsarelikelytowanttotakeadvantageofanautomaticderivationorsynthesisofpredicatesaswellasanautomaticadaptationofdataextractedfrommessages.Thesynthesisofpredicatescouldbedrivenbyapplication-specificlanguagesorbytheapplica-tions’datamodel.Asanexample,considerafam-ilyofmanagementapplicationsimplementedwithinaspreadsheet.Specificexamplesincludeaportfo-liomanagementsystemandalogisticssupportinacomputer-aidedmanufacturingsystem.Inthesecases,theapplicationsneedtohaveaccesstoseveraldatasources,anditwouldmakesenseforthespreadsheetapplicationtomediateaccesstothecontent-basednet-workthroughauniforminterface.Inparticular,itwouldmakesenseto(1)derivecontent-basedcommu-nicationpredicatesfromformulasinthespreadsheet,and(2)tofeeddataextractedfrommessagesdirectlyintotheappropriatepositionsinthespreadsheet.Asimilarcontent-basedmiddlewarecouldbedesignedalsofordatabaseapplications.•Guidedcompositionofpredicates:interactiveapplica-tionsmightgiveusersmoreorlessdirectaccesstothecontent-basednetwork.Inthesecases,theuserswouldbenefitfromacompositionandvalidationserviceforbothmessagesandpredicates.Suchaservicewouldguideusersinthecompositionofmessagesandpredi-catessoastoavoiderrorsandinconsistencies.Manysimilarservicesareimplementedinotherclassesofap-plications.Forexample,databaseapplicationshavequeryeditorsandquery-by-exampleinterfaces.•Integrationwithaddress-basedservices:applicationsmayrequiremulti-modalcommunication.Forexam-ple,aclientmightfirstdiscoveraservicethroughaser-viceadvertisementtransmittedthroughthecontent-basednetwork,butthenwouldestablishasessionwiththeserviceproviderthroughanormalunicastconnec-tionusingaremoteprocedurecallprotocol.Inthiscase,itmightbebeneficialornecessarytointegratethesedifferentcommunicationservices—content-basedandaddress-basedunicast—forexample,becausesomepropertiesoftheunicastconnectionmightbespeci-fiedintheserviceadvertisement.Itiseasytoimagine
2.7
AMiddlewareforContent-BasedCom-munication
Thecontent-basedcommunicationinterfacewedefinedinSection1isahostinterface.Whatthismeansinpracticeisthatthenetworkallowsahosttodeclareapredicate,butdoesnotdistinguishmultipleapplicationsrunningonahost.Also,thishostinterfaceisstateless,meaningthateverypredicatedeclarationoverwritesallpreviousdeclara-tions.Noticethatthischoiceofinterfacedifferssignificantlyfromallexistingpublish/subscribesystems,whereapplica-tionscanpublishandsubscribethroughoneormoreinde-pendentinterfaces,andwheresubscriptionsareaccumulatedbythesystemandmustbeexplicitlycanceledbyapplica-tions(with“unsubscriptions”).
Thebasiccontent-basednetworkinginterfaceismoresim-ilarinspirittotheinterfaceofanIPhost,wherethenet-worklayeraddresseshosts(or,moreprecisely,networkin-terfaces)andwhereindividualapplicationscanbeaddressedonlythroughhigher-levelprotocolssuchasUDPandTCP.Whilewedonotseeanythingparticularlywronginhav-inganapplicationaccessthecontent-basedhostinterfacedi-rectly,wealsobelievethatmostapplicationswouldrequirehigher-levelservices.Thesehigher-levelservicesmaybeim-plementedbythehostoperatingsystem—inthesamewaymostmodernoperatingsystemsimplementtheIPprotocolstack—orbyamiddlewareservice,orbylibraryfunctions.Regardlessofthetypeofimplementation,whichwilldependuponengineeringconsiderations,weseetheopportunityandtheneedfordesigninghigh-levelservicesontopofthebasiccontent-basedcommunicationinterface.Thefollowingisaninitiallistofsuchbasicservices.
•Subscriptionservice:thisisthestatefulandmulti-
五道口生活网 www.wdklife.com 五道论坛（五道口人自己的论坛） www.wdklife.com/bbs 通洲生活网 www.85118.com
五道口生活网 www.wdklife.com 五道论坛（五道口人自己的论坛） www.wdklife.com/bbs 通洲生活网 www.85118.com
othersuchtypesofmulti-modalsessions.Therefore,itisnaturaltoassumethatamiddlewareforcontent-basedcommunicationwouldalsointegratetraditionalmiddlewareservices.
3.CONCLUSIONS
Content-basedcommunicationandnetworkinginanex-citingandpromisingresearchareathatcombinesalgorith-micproblems,classicalnetworkingproblems,anddataman-agementproblems,includingsecurity.Wehavebeenwork-inginthisareaforanumberofyears.Ourapproachisbasedonasystems-orientedview,butwealsoattempttocastandanalyzeourideaswithinsolidtheoreticalmodels.Ourin-tentistocontinueinthisgeneraldirection,exploringmanyoftheresearchquestionsthatremainopen.Inthispaperwelistedsomeofthesequestions,alongwithafewconcreteideasandplans.
4.REFERENCES
[10]C.RaiciuandD.S.Rosenblum.Enabling
confidentialityincontent-basedpublish/subscribe
infrastructures.InSecurecomm’06:ProceedingsoftheSecondIEEE/CreatNetInternationalConferenceonSecurityandPrivacyinCommunicationNetworks,2006.
[11]A.C.Snoeren,K.Conley,andD.K.Gifford.
Mesh-basedcontentroutingusingXML.In
ProceedingsoftheEighteenthACMSymposiumonOperatingSystemsPrinciples(SOSP’01),pages160–173.ACMPress,Oct.2001.
[12]P.TriantafillouandI.Aekaterinidis.Content-based
publish-subscribeoverstructuredP2Pnetworks.InThirdInternationalWorkshoponDistributed
Event-BasedSystems(DEBS2004),pages104–109,Edinburgh,Scotland,UK,May2004.
[13]R.vanRenesseandA.Bozdog.Willow:Dht,
aggregation,andpublish/subscribeinoneprotocol.InProceedingsoftheThirdInternationalWorkshoponPeer-to-PeerSystems,pages173–183,2004.
[1]G.Banavar,T.D.Chandra,B.Mukherjee,
J.Nagarajarao,R.E.Strom,andD.C.Sturman.Anefficientmulticastprotocolforcontent-basedpublish-subscribesystems.InThe19thIEEE
InternationalConferenceonDistributedComputingSystems(ICDCS’99),pages262–272,Austin,Texas,May1999.
[2]F.CaoandJ.P.Singh.Efficienteventroutingin
content-basedpublish-subscribeservicenetworks.InIEEEConferenceonComputerCommunications
(INFOCOM’04),pages929–940,HongKong,China,Mar.2004.
[3]A.Carzaniga,A.J.Rembert,andA.L.Wolf.
Understandingcontent-basedroutingschemes.TechnicalReport2006/05,FacultyofInformatics,UniversityofLugano,Sept.2006.
[4]A.Carzaniga,D.S.Rosenblum,andA.L.Wolf.
Achievingscalabilityandexpressivenessinan
internet-scaleeventnotificationservice.InProceedingsoftheNineteenthAnnualACMSymposiumon
PrinciplesofDistributedComputing,pages219–227,Portland,Oregon,USA,July2000.
[5]A.Carzaniga,D.S.Rosenblum,andA.L.Wolf.
Designandevaluationofawide-areaevent
notificationservice.ACMTransactionsonComputerSystems,19(3):332–383,Aug.2001.
[6]A.Carzaniga,M.J.Rutherford,andA.L.Wolf.A
routingschemeforcontent-basednetworking.InIEEEConferenceonComputerCommunications
(INFOCOM’04),pages918–928,HongKong,China,Mar.2004.
[7]Y.-C.ChangandM.Mitzenmacher.Privacy
preservingkeywordsearchesonremoteencrypteddata.CryptologyePrintArchive,Report2004/051,2004.
[8]P.Ji,Z.Ge,J.Kurose,andD.Towsley.Matchmaker:
Signalingfordynamicpublish/subscribeapplications.In11thIEEEInternationalConferenceonNetworkProtocols(ICNP’03),pages222–233,Nov.2003.
[9]D.PelegandE.Upfal.Atrade-offbetweenspaceand
efficiencyforroutingtables.JournaloftheACM,36(3):510–530,July1989.
五道口生活网 www.wdklife.com 五道论坛（五道口人自己的论坛） www.wdklife.com/bbs 通洲生活网 www.85118.com
因篇幅问题不能全部显示，请点此查看更多更全内容